计算机图形学-基本图形生成算法-图形的扫描转换
- 格式：pdf
- 大小：4.24 MB
- 文档页数：46
下载文档原格式
合集下载
第三章 基本图形的扫描转换讲解
第三章
本章学习目标
扫描转换的基本概念 Jack Elton Bresenham简介 直线的扫描转换算法 圆的扫描转换算法
本章内容
直线的扫描转换 圆的扫描转换 本章小结
直线、圆、椭圆是二维场景中的最基本图形。尽管 MFC的CDC类已经提供了相关的绘制函数，但直接使用 这些函数仍然无法满足真实感图形绘制的要求。光栅扫 描显示器是画点设备，基本图形的光栅化就是在像素点 阵中确定最佳逼近于理想图形的像素点集，并用指定颜 色显示这些像素点集的过程。当光栅化与按扫描线顺序 绘制图形的过程结合在一起时，也称为扫描转换。本章 从基本图形的生成原理出发，使用绘制像素点函数实现 基本图形的扫描转换。绘制像素点函数的原型为
1,
(di 0) (di 0)
（3-3）3.1.3 递推公式来自1.中点误差项的递推公式
M(x i+2,y i+1.5）
M(x i+2,y i+0.5)
Pu
Pu
Pi(xi,yi）
Pd
Pd
（a）di<0
Pi(xi,yi） （b）di≥0 中点的递推
(1)当d<0时
di1 F(xi 2, yi 1.5)
k y y1 y0 x x1 x0
直线水平方向位移 ：
x x1 x0
直线垂直方向位移 ：
y y1 y0
理想直线将平面划分成三个区域：对于直线上的 点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0； 对于直线下方的点，F（x，y）＜0。
假 设 直 线 的 斜 率 为 0≤k≤1 ， 则 |△x|≥|△y| ，
y
O
x
圆的扫描转换
本章学习目标
扫描转换的基本概念 Jack Elton Bresenham简介 直线的扫描转换算法 圆的扫描转换算法
本章内容
直线的扫描转换 圆的扫描转换 本章小结
直线、圆、椭圆是二维场景中的最基本图形。尽管 MFC的CDC类已经提供了相关的绘制函数，但直接使用 这些函数仍然无法满足真实感图形绘制的要求。光栅扫 描显示器是画点设备，基本图形的光栅化就是在像素点 阵中确定最佳逼近于理想图形的像素点集，并用指定颜 色显示这些像素点集的过程。当光栅化与按扫描线顺序 绘制图形的过程结合在一起时，也称为扫描转换。本章 从基本图形的生成原理出发，使用绘制像素点函数实现 基本图形的扫描转换。绘制像素点函数的原型为
1,
(di 0) (di 0)
（3-3）3.1.3 递推公式来自1.中点误差项的递推公式
M(x i+2,y i+1.5）
M(x i+2,y i+0.5)
Pu
Pu
Pi(xi,yi）
Pd
Pd
（a）di<0
Pi(xi,yi） （b）di≥0 中点的递推
(1)当d<0时
di1 F(xi 2, yi 1.5)
k y y1 y0 x x1 x0
直线水平方向位移 ：
x x1 x0
直线垂直方向位移 ：
y y1 y0
理想直线将平面划分成三个区域：对于直线上的 点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0； 对于直线下方的点，F（x，y）＜0。
假 设 直 线 的 斜 率 为 0≤k≤1 ， 则 |△x|≥|△y| ，
y
O
x
圆的扫描转换
计算机图形学第3章 基本图形生成算法
基函数（基本样条） 在局部参数区域分布 （支撑区间），因此 影响范围有限。
例题：有点P0（4，3）；P1（6，5）；P2（10，
6 ）；P3（12，4），用以上4点构造2次B样条曲线。
2.1.7 非均匀有理B样条
非均匀有理B样条NURBS（Non Uniform Rational BSpline）；
3.2.2
Bresenham画圆法
该算法是最有效的算法之一。
不失一般性，假设圆心(xc，yc) ,圆上的点(x′，y′)，则：
x' x xc
y ' y yc
圆心为原点，半径为R的位于第一象限1/8圆弧的画法，即(0, R)～( R , R )。
2 2
yi )， 思想:每一步都选择一个距离理想圆周最近的点P( xi ， 使其误差项最小。
画其他曲线。
3.3
自由曲线的生成
正弦函数曲线
指数函数曲线
多项式函数曲线
自 由 曲 线
概率分布曲线及样条函数曲线
3.3.1 曲线的基本理论
基本概念
2.1.4
规则曲线：可用数学方程式表示出来的，如抛物 线等。
自由曲线：很难用一个数学方程式描述的，如高
速公路等。可通过曲线拟合(插值、逼近)的方法来
例题： 利用Bresenham算法生成P （0，0）到Q（6，5）的直 线所经过的像素点。要求先 列出计算式算出各点的坐标 值，然后在方格中标出各点。
（1，1）
3.1.5 双步画线法 原理
模式1：当右像素位于右下角时，中间像素位于底线 模式4：当右边像素位右上角时，中间像素位于中线 模式2和模式3：当右像素位于中线时，中间像素可能位于底线 上，也可能位于中线上，分别对应于模式2和模式3，需进一步 判断。 当0≤k≤1/2时，模式4不可能出现，当1/2≤k≤1时，模式1不 可能出现。
例题：有点P0（4，3）；P1（6，5）；P2（10，
6 ）；P3（12，4），用以上4点构造2次B样条曲线。
2.1.7 非均匀有理B样条
非均匀有理B样条NURBS（Non Uniform Rational BSpline）；
3.2.2
Bresenham画圆法
该算法是最有效的算法之一。
不失一般性，假设圆心(xc，yc) ,圆上的点(x′，y′)，则：
x' x xc
y ' y yc
圆心为原点，半径为R的位于第一象限1/8圆弧的画法，即(0, R)～( R , R )。
2 2
yi )， 思想:每一步都选择一个距离理想圆周最近的点P( xi ， 使其误差项最小。
画其他曲线。
3.3
自由曲线的生成
正弦函数曲线
指数函数曲线
多项式函数曲线
自 由 曲 线
概率分布曲线及样条函数曲线
3.3.1 曲线的基本理论
基本概念
2.1.4
规则曲线：可用数学方程式表示出来的，如抛物 线等。
自由曲线：很难用一个数学方程式描述的，如高
速公路等。可通过曲线拟合(插值、逼近)的方法来
例题： 利用Bresenham算法生成P （0，0）到Q（6，5）的直 线所经过的像素点。要求先 列出计算式算出各点的坐标 值，然后在方格中标出各点。
（1，1）
3.1.5 双步画线法 原理
模式1：当右像素位于右下角时，中间像素位于底线 模式4：当右边像素位右上角时，中间像素位于中线 模式2和模式3：当右像素位于中线时，中间像素可能位于底线 上，也可能位于中线上，分别对应于模式2和模式3，需进一步 判断。 当0≤k≤1/2时，模式4不可能出现，当1/2≤k≤1时，模式1不 可能出现。
计算机图形学——多边形的扫描转换（基本光栅图形算法）
计算机图形学——多边形的扫描转换（基本光栅图形算法）⼀、多边形扫描转换在光栅图形中，区域是由【相连的】像素组成的集合，这些像素具有【相同的】属性值或者它们位于某边界线的内部1、光栅图形的⼀个基本问题是把多边形的顶点表⽰转换为点阵表⽰。
这种转换成为多边形的扫描转换。
2、多边形的扫描转换与区域填充问题是怎样在离散的像素集上表⽰⼀个连续的⼆维图形。
3、多边形有两种重要的表⽰⽅法：（1）顶点表⽰：⽤多边形的定点序列来表⽰多边形优点：直观、⼏何意义强、占内存少、易于进⾏⼏何变换缺点：没有明确指出那些象素在多边形内，故不能直接⽤于上⾊（2）点阵表⽰：是⽤位于多边形内的象素集合来刻画多边形缺点：丢失了许多⼏何信息（eg:边界、顶点等）但是【点阵表⽰是光栅显⽰系统显⽰时所需的表现形式。
】多边形的扫描转换就是把多边形的顶点表⽰转换为点阵表⽰，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜⾊。
实际上就是多边形内的区域的着⾊过程。
4、多边形分类⼆、X扫描线算法X扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再⽤要求的颜⾊显⽰这些区间的象素，即完成填充⼯作。
区间的端点可以通过计算扫描线与多边形边界线的交点获得。
如扫描线y=3与多边形的边界相交于4点（2,3）、（4,3）、（7,3）、（9,3）这四个点定义了扫描线从x=2到x=4，从x=7到x=9两个落在多边形内的区间，该区间内像素应取填充⾊。
算法的核⼼是按x递增顺序排列交点的x坐标序列。
由此可得到扫描线算法步骤如下：算法步骤：1.确定多边形所占有的最⼤扫描线数，得到多边形定点的最⼩最⼤值（y min和y max）；2.从y min到ymax每次⽤⼀条扫描线进⾏填充；3.对⼀条扫描线填充的过程分为四个步骤：a)求交点；b)把所有交点按递增顺序排序；c)交点配对（第⼀个和第⼆个，第三个和第四个）；d)区间填⾊。
计算机图形学基础（第2版）课后习题答案__陆枫__何云峰
计算机图形学基础（第2版）课后习题答案__陆枫__何云峰第⼀章绪论概念：计算机图形学、图形、图像、点阵法、参数法、图形的⼏何要素、⾮⼏何要素、数字图像处理；计算机图形学和计算机视觉的概念及三者之间的关系；计算机图形系统的功能、计算机图形系统的总体结构。
第⼆章图形设备图形输⼊设备：有哪些。
图形显⽰设备：CRT的结构、原理和⼯作⽅式。
彩⾊CRT：结构、原理。
随机扫描和光栅扫描的图形显⽰器的结构和⼯作原理。
图形显⽰⼦系统：分辨率、像素与帧缓存、颜⾊查找表等基本概念，分辨率的计算第三章交互式技术什么是输⼊模式的问题，有哪⼏种输⼊模式。
第四章图形的表⽰与数据结构⾃学，建议⾄少阅读⼀遍第五章基本图形⽣成算法概念：点阵字符和⽮量字符；直线和圆的扫描转换算法；多边形的扫描转换：有效边表算法；区域填充：4／8连通的边界／泛填充算法；内外测试：奇偶规则，⾮零环绕数规则；反⾛样：反⾛样和⾛样的概念，过取样和区域取样。
5.1.2 中点 Bresenham 算法（P109）5.1.2 改进 Bresenham 算法（P112）习题解答习题5（P144）5.3 试⽤中点Bresenham算法画直线段的原理推导斜率为负且⼤于1的直线段绘制过程（要求写清原理、误差函数、递推公式及最终画图过程）。
（P111）解： k<=-1 |△y|/|△x|>=1 y为最⼤位移⽅向故有构造判别式：推导d各种情况的⽅法(设理想直线与y=yi+1的交点为Q)：所以有： y Q-kx Q-b=0 且y M=y Qd=f(x M-kx M-b-(y Q-kx Q-b)=k(x Q-x M)所以，当k<0，d>0时，M点在Q点右侧（Q在M左），取左点 P l(x i-1,y i+1)。
d<0时，M点在Q点左侧（Q在M右），取右点 Pr(x i,y i+1)。
d=0时，M点与Q点重合（Q在M点），约定取右点 Pr(x i,y i+1) 。
计算机图形学二、多边形的扫描转换算法
2
做一个
E
2
A
C C
2
D
B
2
局部极大或局部极小点， 交点看做是二个
非局部极值点，交点看
2
做一个
E
非局部极值点将这些相
邻边分割开来
2
A
如何计算扫描线与多边形边界线的所有交点？
若扫描线yi与多边形边界线交点的x坐标是xi， 则对下一条扫描线yi+l，它与那条边界线的交点的x 坐标xi+1，可如下求出：
m
yi1 yi xi1 xi
, yi1
yi
1
xi 1
xi
1 m
扫描线与多边形边的交点计算 C
B
yk 1 yk
x AC k 1
xkAC
1 mAC
x BC k 1
xkBC
1 mBC
A
活跃(活性)边：与当前扫描线相交的边 活跃(活性)边表AET：存贮当前扫描线相交的各边的表。
ymax x 1/m next
…
扫描线5 扫描线6
e2 92 0
e2 92 0
e6 5 13 6/4 λ
e5 11 13 0 λ
9∧
8∧
e3
e4
7
9 7 -5/2
11 7 6/4 λ
e5
6
11 13 0 λ
5∧
e2
e3
4
9 2 0λ
3∧
e2
2∧
e1
e6
1
3 7 -5/2
5 7 6/4 λ
e1
0∧
ymax xmin 1/m
e4 e5
e6 5 111/2 6/4 λ
9∧
计算机图形学——圆的扫描转换（基本光栅图形算法）
计算机图形学——圆的扫描转换（基本光栅图形算法）与直线的⽣成类似，圆弧⽣成算法的好坏直接影响到绘图的效率。
本篇博客将讨论圆弧⽣成的3个主要算法，正负法、Bresenham 法和圆的多边形迫近法，在介绍算法时，只考虑圆⼼在原点，半径为R的情况。
⼀、正负法1、基本原理假设已选取Pi-1为第i-1个像素，则如果Pi-1在圆内，就要向圆外⽅向⾛⼀步；若已在圆外就要向圆内⾛⼀步。
总之，尽量贴近圆的轮廓线。
2、正负法的具体实现1）圆的表⽰：设圆的圆⼼为(0,0),半径为R，则圆的⽅程为：F(x,y)=x2+y2–R2=0当点(x,y)在圆内时，F(x,y)<0。
当点(x,y)在圆外时，F(x,y)>0。
2）实现步骤第1步：x0=0，y0=R第2步：求得Pi(x i,y i)后找点P i+1的原则为：当P i在圆内时(F(xi,yi)≤0)，要向右⾛⼀步得P i+1，这是向圆外⽅向⾛去。
取x i+1= x i+1, y i+1= y i当P i在圆外时(F(xi,yi)>0)，要向下⾛⼀步得P i+1，这是向圆内⽅向⾛去，取x i+1= x i, y i+1= y i-1⽤来表⽰圆弧的点均在圆弧附近且 F(xi, yi)时正时负假设已经得到点（x i, y i），则容易算出F(x i, y i)，即确定了下⼀个点（x i＋1, y i＋1），则如何计算F(x i+1, y i+1)，以确定下下个点（x i＋2, y i＋2）？分为两种情况：右⾛⼀步后：x i+1=x i+1，y i+1=y i，此时：F(x i+1, y i+1)=x i+12+y i2-R2=x i2+y i2-R2+2x i+1 = F(x i, y i)+2x i+1下⾛⼀步后：x i+1=x i，y i+1=y i-1， 此时：F(x i+1, y i+1)=x i2+（y i-1)2-R2= F(x i, y i)-2y i+1由此可得：确定了F(xi+1, yi+1)之后，即可决定下⼀个点(xi+2, yi+2)，选择道理同上。
计算机图形学的基本算法
计算机图形学的基本算法计算机图形学是研究如何利用计算机生成、处理和显示图像的学科。
图形学的基本算法涵盖了多个方面，包括图像绘制、几何变换、光照和渲染等。
以下将详细介绍计算机图形学的基本算法及其步骤。
1. 图像绘制算法：- 像素绘制算法：基于像素的图形绘制算法包括点绘制、线段绘制和曲线绘制。
例如，Bresenham线段算法可用于绘制直线。
- 多边形填充算法：多边形填充算法用于绘制封闭曲线图形的内部区域。
常见的算法包括扫描线填充算法和种子填充算法。
2. 几何变换算法：- 平移变换：平移变换算法用于将图像在平面上进行上下左右的平移操作。
- 旋转变换：旋转变换算法用于将图像按照一定的角度进行旋转。
- 缩放变换：缩放变换算法用于按照一定的比例对图像进行放大或缩小操作。
- 剪切变换：剪切变换算法用于按照一定的裁剪方式对图像进行剪切操作。
3. 光照和渲染算法：- 光照模型：光照模型用于模拟物体与光源之间的相互作用。
常见的光照模型有Lambert模型和Phong模型等。
- 阴影生成算法：阴影生成算法用于在渲染过程中生成逼真的阴影效果。
例如，阴影贴图和阴影体积等算法。
- 光线追踪算法：光线追踪算法通过模拟光线的路径和相互作用，实现逼真的光影效果。
常见的光线追踪算法包括递归光线追踪和路径追踪等。
4. 图像变换和滤波算法：- 傅里叶变换算法：傅里叶变换算法用于将图像从时域转换到频域进行分析和处理。
- 图像滤波算法：图像滤波算法用于对图像进行平滑、锐化、边缘检测等操作。
常见的滤波算法包括均值滤波、高斯滤波和Sobel算子等。
5. 空间曲线和曲面生成算法：- Bézier曲线和曲面算法：Bézier算法可用于生成平滑的曲线和曲面，包括一阶、二阶和三阶Bézier曲线算法。
- B样条曲线和曲面算法：B样条算法可用于生成具有更高自由度和弯曲度的曲线和曲面。
以上列举的是计算机图形学中的一些基本算法及其应用。
计算机图形学基础课后部分习题答案
DDA 算法： void CMainFrame::OnDdaline() { // TODO: Add your command handler code here CDC* pDC=GetDC(); int xa=0,ya=0,xb=8,yb=6,c=RGB(255,0,0); int x,y; float dx, dy, k; dx=(float)(xb-xa),dy=(float)(yb-ya); k=dy/dx,y=ya; if ((0<k&&k<1)||(-1<k&&k<0)) { for(x=xa;x<=xb;x++) {pDC->SetPixel(x,int(y+0.5),c); y=y+k;} } if(abs(k)>=1) { for(y=ya;y<=yb;y++) {pDC->SetPixel(int(x+0.5),y,c); x=x+1/k;} } ReleaseDC(pDC); } Bresenham 算法： void CMainFrame::OnBresenhamline() { // TODO: Add your command handler code here CDC*pDC=GetDC(); -4-
xi+1 xi+2
第四象限
-6-
d0=F(x0+1,y0-0.5)=-(k+0.5) 令 Di=2dxdi,得 D0=-(dx+2dy),D 与 d 同号 当 Di≥0,下一点(xi,yi-1),Di+1=Di-2dy 当 Di≤0,下一点(xi+1,yi-1),Di+1=Di-2(dx+dy)
xi+1 xi+2
第四象限
-6-
d0=F(x0+1,y0-0.5)=-(k+0.5) 令 Di=2dxdi,得 D0=-(dx+2dy),D 与 d 同号 当 Di≥0,下一点(xi,yi-1),Di+1=Di-2dy 当 Di≤0,下一点(xi+1,yi-1),Di+1=Di-2(dx+dy)
东北大学计算机图形学4
xi 1 xi x xi yi 1 yi y yi 1 1 x xi y k 1 y yi 1 y
DDA算法原理
• 对求出的xi+1，yi+1进行四舍五入，即 round(xi+1)=(int)(x i+1+0.5)或round(y i+1)=(int)(y i+1+0.5)
DDA算法原理
xi 1 xi x yi 1 yi y
其中，
yi+1 ε△y yi xi ε△x xi+1 x
y
1 / | x |, | x || y | 1 / max(|x |, | y |) 1 / | y |, | y || x |
示例图片
右图中，
红色填充点表示的线段： 起点为(0，0) 终点为(10，20)
绿色填充点表示的线段：
起点为(0，0) 终点为(20，10)
• • • • • • • • • • • • • • • • •
Void DDAline(int x0,int y0,int x1,int y1) { int dx,dy,epsl,k; 变量定义：整数型： dx,dy,epsl,k; float x,y,xIncre,yIncre; 符点型：x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; 变量赋初值：线段起点与终点的x,y轴向 x=(float)x0; y=(float)y0; 增量；起点变量类型转换后赋值。 if( abs(dx)>abs(dy)) epsl=abs(dx); else 求x,y轴向增量的大值。 epsl=abs(dy); xIncre=(float)dx/(float)epsl; 求线段在x,y轴向上的步进增量 yIncre=(float)dy/(float)epsl; for(k=0;k<=epsl;k++) { putPixel((int)(x+0.5),(int)(y+0.5))); x+=xIncre; y+=yIncre; } 增量式依次计算线段上个点，并输出。 }
DDA算法原理
• 对求出的xi+1，yi+1进行四舍五入，即 round(xi+1)=(int)(x i+1+0.5)或round(y i+1)=(int)(y i+1+0.5)
DDA算法原理
xi 1 xi x yi 1 yi y
其中，
yi+1 ε△y yi xi ε△x xi+1 x
y
1 / | x |, | x || y | 1 / max(|x |, | y |) 1 / | y |, | y || x |
示例图片
右图中，
红色填充点表示的线段： 起点为(0，0) 终点为(10，20)
绿色填充点表示的线段：
起点为(0，0) 终点为(20，10)
• • • • • • • • • • • • • • • • •
Void DDAline(int x0,int y0,int x1,int y1) { int dx,dy,epsl,k; 变量定义：整数型： dx,dy,epsl,k; float x,y,xIncre,yIncre; 符点型：x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; 变量赋初值：线段起点与终点的x,y轴向 x=(float)x0; y=(float)y0; 增量；起点变量类型转换后赋值。 if( abs(dx)>abs(dy)) epsl=abs(dx); else 求x,y轴向增量的大值。 epsl=abs(dy); xIncre=(float)dx/(float)epsl; 求线段在x,y轴向上的步进增量 yIncre=(float)dy/(float)epsl; for(k=0;k<=epsl;k++) { putPixel((int)(x+0.5),(int)(y+0.5))); x+=xIncre; y+=yIncre; } 增量式依次计算线段上个点，并输出。 }
基本图形的扫描转换
= xi +1/k 即当y每递增1时，x递增斜率1/k
18 of 126
输出坐标求整
• 由于屏幕上的坐标为整数坐标，则真正作 为输出显示为：y输出=ROUND(yn)，其中函 数ROUND ()是指舍尾的整数 • 因此y输出和yn 之间的量化误差最大为1。 为了改善这方面的误差，使x和y的值增加 0.5,使量化误差在(-0.5,0.5)范围之间 x=x0+0.5 y=y0+0.5 • ROUND(a)=(int)(a+0.5)
– （5）显示线段的速度应快
• 生成直线可用软件和硬件来实现，一般情况下，硬 件要比软件实现得快。
14 of 126
3.1.2 数值微分DDA直线生成算法
• 数值微分法，DDA（Digital Differential Analyzer）是根据数学上直线的微分方程来设计 的 • 设A(x0,y0)，B(x1,y1)是直线的端点坐标，首先计 算出直线的斜率 k=dy/dx=△y/△x=(y1-y0)/(x1-x0) 直线方程为：y=kx+B 或 x=1/k*y+T
确定一个像素集合及其颜色用于显示一个图形的过程称为图形的扫描转换或光栅化也叫图形的生成126图形生成图形生成是根据图形的几何信息和属性信息结合图形生成算法计算出要显示的中间像素而不像图像生成是保存了图像的每一像素点的信息基本图形的生成首先要根据基本图形的特征找出它的几何信息然后根据一定的生成算法实时地在显示器上显示出完整的图形126图形扫描转换步骤一般分为两个步骤
24 of 126
3.1.3 中点直线生成算法
• 假定直线斜率0<K<1，且 已确定点亮象素点P(xi,yi)， 则下一个与直线最接近的 像素只能是P1(xi+1,yi)点或 P2(xi+1,yi+1)点。设 M(xi+1,yi+0.5)为中点，Q 为交点 • 问题：如何确定下一个点 亮的象素？
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
)
①
④③
V
D (xi+1,yi-1)
(xi,yi-1) ⑤
使其与实际圆弧的距离平方达到最小
Bresenham画圆算法（2/7）
v 圆弧与点(xi,yi)附近光栅网格的相交关系有5种
v 右下角像素D (xi,yi)与实际圆弧的近似程度
i=(xi+1)2+(yi-1)2-R2 当i<0时，D在圆内，①②
x
x-- x++ x增1
y≥0时，s2=1,否则s2=-1
y-- y--
y减1 y减1
Bresenham画线算法（9/11）
v 确定误差e的计算方法，并根据e确定在非最 大位移方向上如何走步
v 误差初值的计算
|k|<1时， e=2|y| - |x| |k|>1时， e=2|x| - |y|
Bresenham画线算法（10/11）
Bresenham画线算法（1/11）
v 使用最广泛 v 与中点画线法的思想类似 v 由误差项符号决定下一个象素取正右方像素
还是右上方像素
Bresenham画线算法（2/11）
v基本思想
比较从理想直线到位于直线上方的像素的距离d1和 相邻的位于直线下方的像素的距离d2 根据距离误差项的符号确定与理想直线最近的象素
大位移方向上如何走步
Bresenham画线算法（8/11）
v 先确定最大位移方向
|k|<1时，x为最大位移方向 |k|>1时，y为最大位移方向
y y增1 y增1
v 增1还是减1，取决于直线
所在象限
x减1
x≥0时，s1=1,否则s1=-1 x减1
x-y++
x++ yx++++ y++
x增1
o(x0,y0)
用到浮点数的乘法、加法和取整运算
数值微分(DDA)法(2/5)
v 增量算法
yi+1=kxi+1+b=k(xi+1)+b=yi+k (xi,yi)→(xi+1,yi+k)
v 缺点：
有浮点数取整运算 不利于硬件实现 效率低 仅适用于k ≤1的情形:x每增加1,y最多增加1。
当 k 1时，必须把x，y互换。
e’
e’=2y/ x - 1 =e + y/ x - 1
e
e’=e + 2y - 2x
P P1
v当e<0时，y方向不走步
e’=2y/ x=e + y/ x
P2
e’=e + 2y
e
e’
P
P1
Bresenham画线算法（7/11）
v 先确定最大位移方向 v 确定误差e的计算方法，并根据e确定在非最
=2 (i-xi)-1
若d’<0，则选D
情形④也 适用
若d’>0，则选V
若d’=0，则选D
Bresenham画圆算法（5/7）
v 当i=0时，D在圆上，⑤ v 按d判别，有d>0，应选D v 按d’判别，有d’<0，应选D
Pi(xi,yi) H (xi+1,yi )
V
D (xi+1,yi-1)
①
V
D (xi+1,yi-1)
(xi,yi-1)
=|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2|
=(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2
=2 (i+yi)-1
若d<0，则选H 若d>0，则选D
情形②也 适用
若d=0，则选H
Bresenham画圆算法（4/7）
v 当i>0时，D在圆外，③④
Pi(xi,yi) H (xi+1,yi
)
v v
情形③，选mv ，mD d’=mD - mV =|(xi+1)2+(yi-1)2-R2
中最小者 ④ V③ | - |xi2+(yi-1)2-R2|(xi,yi-1)
D
(xi+1,yi-1)
=(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2
=d+a+b
M
d的增量为a+b
P1
中点画线法（4/4）
v d的初始值
d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5b =a+0.5b
用2d代替d后，d0=2a+b d的增量都是整硬件实现
因(X0,Y0)在直线上， 所以F(X0,Y0)=0
v 构造一个行列式值为1的矩阵
v 对应的圆方程递推关系为 xn+1 = xn + єyn yn+1 = -єxn +(1-є2)yn= yn- єxn+1
DDA画圆法（3/3）
v 针对不同象限及顺逆时针画圆，赋给є适当的 符号
v є不同，圆形状不同， є大近似椭圆
Bresenham画圆算法（1/7）
M
再下一个象素的判别式为：
d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c
P1
= d+a
d的增量为a
v 若d＜0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1)
再下一个象素的判别式为：
P2
d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c
中点画圆法（2/2）
若 d<0, 取P1为下一象素，再下一象素的判别式为
若d>=0, 取P2为下一象素，再下一象素的判别式为
初始象素是（0,R），判别式d的初值为
使用e=d-0.25代替d e0=1-R
P1(Xp+1,Yp) P2(Xp+1,Yp-1)
DDA画圆法（1/3）
v 圆的方程：f(x,y)=x2+y2-R2=0
v 顺时针画第一四分圆，下一步选择哪个点？
v 基本思想：
通过比较像素与圆的距离平方来避免开方运算
v 下一像素有3种可能的选择
mH=|(xi+1)2+yi2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|xi2 +(yi-1)2-R2 |
v 选择像素的原则
②
Pi(xi,yi) H (xi+1,yi
数值微分(DDA)法(3/5)
vdigital differential analyzer
v基本思想
用数值方法解微分方程
dx/dt = x dy/dt = y
如何选取є ？
xn+1 = xn + єx yn+1 = yn + єy
选取є的原则：使0.5≤|єx|,|єy|≤1
数值微分(DDA)法(4/5)
v 三个常用算法：
1数值微分法（DDA） 2中点画线法 3Bresenham算法。
数值微分(DDA)法(1/5)
v 已知线段端点：P0(x0,y0), P1(x1,y1) v 直线方程
y=kx+b {(xi, yi)}, i=0,….n. v 浮点数取整 : yi=round(yi)=(int)(yi+0.5)
v设e=e×2x，不影响判断的准确性
ve0=2y - x v当e≥0时，最接近P2(xi+1,yi+1)
y方向走一步 v当e<0时，最接近P1(xi+1,yi)
P2
e’
e P P1
y方向不走步
P2
e
e’
P
P1
Bresenham画线算法（6/11）
v下一步误差的计算
v当e≥0时，y方向走一步
P2
v 全微分：df(x,y)=2xdx+2ydy=0
v 微分方程：dy/dx=-x/y
v 递推方程:
(yn+1-yn)/ (xn+1-xn)=-єxn/ єyn
实际画出的曲线不
xn+1 - xn = єyn
是圆，而是螺旋线，
为什么？
yn+1 - yn = -єxn
DDA画圆法（2/3）
v 将递推公式写成矢量形式：
= Address(x,y)± k2 ± 1 增量法的优点？
直线段扫描转换
v 假设
像素间均匀网格，整数型坐标系，直线段斜率0<m<1
v X方向每次迭代都增1，y方向不一定
对m＞1，x、y互换
直线段的扫描转换算法
v 直线的扫描转换
确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作
每行像素点数
行数
行中位置
光栅图形中点的表示
Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x
对像素连续寻址时，如何减少计算量？
Address(x±1,y) = k1 + k2y + (x±1) = Address(x,y) ± 1 Address(x,y±1) = k1 + k2(y ±1) + x = Address(x,y) ± k2 Address(x±1,y±1) = k1 + k2(y ±1) + (x±1)