计算机图形学教程（第5版 微课版）课件 第3章 基本图形生成算法1

第三章基本图形生成算法

图形的扫描转换基本图形生成算法图元扫描转换直线段扫描转换圆弧扫描转换实区域填充光栅图形中点的表示…(x,y)坐标地址线性表1D表示显示屏幕2D表示像素由其左下角坐标表示光栅图形中点的表示地址=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址xyxmaxxminymaxymin每行像素点数行数行中位置(x,y)光栅图形中点的表示Address(x,y)=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址

=k1+k2y+xAddress(x±1,y)=k1+k2y+(x±1)=Address(x,y)±1Address(x,y±1)=k1+k2(y±1)+x=Address(x,y)±k2Address(x±1,y±1)=k1+k2(y±1)

+(x±1)=Address(x,y)±k2±1对像素连续寻址时，如何减少计算量？增量法的优点？直线段扫描转换假设像素间均匀网格，整数型坐标系，直线段斜率0<m<1X方向每次迭代都增1，y方向不一定对m＞1，x、y互换直线段的扫描转换算法直线的扫描转换

确定最佳逼近于该直线的一组象素按扫描线顺序，对这些象素进行写操作三个常用算法：1数值微分法（DDA）2中点画线法3Bresenham算法。数值微分(DDA)法(1/5)已知线段端点：P0(x0,y0),P1(x1,y1)直线方程

y=kx+b{(xi,

yi)},i=0,….n.浮点数取整:yi=round(yi)=(int)(yi+0.5)用到浮点数的乘法、加法和取整运算数值微分(DDA)法(2/5)增量算法yi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)→(xi+1,yi+k)缺点：有浮点数取整运算不利于硬件实现效率低仅适用于

k

≤1的情形:x每增加1,y最多增加1。当

k

1时，必须把x，y互换。数值微分(DDA)法(3/5)digitaldifferentialanalyzer基本思想用数值方法解微分方程

dx/dt=xdy/dt=y

xn+1=xn

+єx

yn+1=yn

+єy

如何选取є？选取є的原则：使0.5≤|єx|,|є

y|≤1数值微分(DDA)法(4/5)对称的DDA取є=2-n使2n-1≤max(|x

|,|

y|)≤2n简单的DDA取є=1/max(|x

|,|

y|)使є|x|,є|

y|中必有一个是单位步长x为最大时，єx=1,єx

=ky为最大时，єy=1,єy

=1/k数值微分(DDA)法(5/5)缺点：浮点数运算不易硬件实现中点画线法（1/4）问题：判断距离理想直线最近的下一个象素点已知：线段两端点(x0,y0)，(x1,y1)直线方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判断M点在Q点上方还是在Q点下方？MP1P2P直线上方点：F(x,y)＞0直线下方点:F(x,y)＜0构造判别式：d=F(M)=F(Xp+1,Yp+0.5)由d＞0，d＜0可判定下一个象素(Xp+1,Yp+0.5)中点画线法（2/4）分两种情形考虑再一下个象素的判定：若d≥0，中点M在直线上方，取正右方象素P1(Xp+1,Yp)再下一个象素的判别式为：

d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+ad的增量为a若d＜0，中点M在直线下方，取右上方象素P2(Xp+1,Yp+1)再下一个象素的判别式为：

d2=F((Xp+1)+1,(Yp+1)+0.5)=a(Xp+2)+b(Yp+1.5)+c=d+a+b

d的增量为a+bMP1P2MP1P2d的初始值d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b=a+0.5b用2d代替d后，d0=2a+bd的增量都是整数优点：只有整数运算，不含乘除法可用硬件实现因(X0,Y0)在直线上，所以F(X0,Y0)=0中点画线法（4/4）Bresenham画线算法（1/11）使用最广泛与中点画线法的思想类似由误差项符号决定下一个象素取正右方像素还是右上方像素Bresenham画线算法（2/11）基本思想比较从理想直线到位于直线上方的像素的距离d1和相邻的位于直线下方的像素的距离d2根据距离误差项的符号确定与理想直线最近的象素Bresenham画线算法（3/11）最大位移方向每次走一步k<1时，x为最大位移方向y方向走步与否取决于误差e值的大小误差计算初值：e0=y/x当e≥0.5时，最接近P2(xi+1,yi+1)y方向走一步当e<0.5时，最接近P1(xi+1,yi)y方向不走步eP1P2Pe’eP1P2Pe’Bresenham画线算法（4/11）为方便与0比较，设e=e-0.5e0=y/x-0.5当e≥0时，最接近P2(xi+1,yi+1)y方向走一步当e<0时，最接近P1(xi+1,yi)y方向不走步有除法，不宜硬件实现eP1P2Pe’eP1P2Pe’Bresenham画线算法（5/11）设e=e×2x，不影响判断的准确性e0=2y-x当e≥0时，最接近P2(xi+1,yi+1)y方向走一步当e<0时，最接近P1(xi+1,yi)y方向不走步eP1P2Pe’eP1P2Pe’Bresenham画线算法（6/11）下一步误差的计算当e≥0时，y方向走一步e’=2y/x-1=e+y/x-1e’=e+2y-2x当e<0时，y方向不走步e’=2y/x=e+y/xe’=e+2yeP1P2Pe’eP1P2Pe’Bresenham画线算法（7/11）先确定最大位移方向确定误差e的计算方法，并根据e确定在非最大位移方向上如何走步Bresenham画线算法（8/11）先确定最大位移方向|k|<1时，x为最大位移方向|k|>1时，y为最大位移方向增1还是减1，取决于直线所在象限x≥0时，s1=1,否则s1=-1y≥0时，s2=1,否则s2=-1yxx++y++x增1x增1ox++y++x++y--x--y++x--y--y增1x减1y增1y减1x减1y减1(x0,y0)Bresenham画线算法（9/11）确定误差e的计算方法，并根据e确定在非最大位移方向上如何走步误差初值的计算|k|<1时，e=2|y|-|x||k|>1时，e=2|x|-|y|Bresenham画线算法（10/11）确定误差e的计算方法，并根据e确定在非最大位移方向上如何走步e<0,不走步|k|<1时，x=x+s1,e=e+2|y||k|>1时，y=y+s2,e=e+2|x|e≥0,走步|k|<1时，x=x+s1,y=y+s2,e=e+2|y|-2|x||k|>1时，y=y+s2,x=x+s1,e=e+2|x|-2|y|Bresenham画线算法（11/11）优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现圆弧的扫描转换圆的八对称性只考虑第二个八分圆假设圆心在原点

x2+y2=R2

yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR圆弧的扫描转换两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点：计算量大所画像素位置间的间距不一致

中点画圆法（1/2）F(X,Y)=X2+Y2-R2=0中点M=(Xp+1,Yp-0.5)当F(M)＜0时，M在圆内，P1距离圆弧近，取P1当F(M)＞0时，M在圆外，P2距离圆弧近，取P2中点画圆法（2/2）若d<0,取P1为下一象素，再下一象素的判别式为

若d>=0,取P2为下一象素，再下一象素的判别式为初始象素是（0,R），判别式d的初值为P1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替de0=1-RDDA画圆法（1/3）圆的方程：f(x,y)=x2+y2-R2=0全微分：df(x,y)=2xdx+2ydy=0微分方程：dy/dx=-x/y递推方程:(yn+1-yn)/(xn+1-xn)=-єxn/єynxn+1-xn

=єyn

yn+1-yn

=-єxn实际画出的曲线不是圆，而是螺旋线，为什么？DDA画圆法（2/3）将递推公式写成矢量形式：构造一个行列式值为1的矩阵对应的圆方程递推关系为

xn+1=xn

+єyn

yn+1=-єxn+(1-є2)yn=yn-єxn+1

DDA画圆法（3/3）针对不同象限及顺逆时针画圆，赋给є适当的符号є不同，圆形状不同，є大近似椭圆Bresenham画圆算法（1/7）顺时针画第一四分圆，下一步选择哪个点？基本思想：通过比较像素与圆的距离平方来避免开方运算下一像素有3种可能的选择mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2+(yi-1)2-R2|选择像素的原则使其与实际圆弧的距离平方达到最小(xi,yi)HPi①VD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)②③④⑤Bresenham画圆算法（2/7）圆弧与点(xi,yi)附近光栅网格的相交关系有5种右下角像素D(xi,yi)与实际圆弧的近似程度i=(xi+1)2+(yi-1)2-R2当i<0时，D在圆内，①②当i>0时，D在圆外，③④当i=0时，D在圆上，⑤(xi,yi)HPi①VD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)②③④⑤Bresenham画圆算法（3/7）当i<0时，D在圆内，①②情形①，选mH

，mD

中最小者d=mH

-mD

=|(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情形②也适用(xi,yi)HPi①VD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)②Bresenham画圆算法（4/7）当i>0时，D在圆外，③④情形③，选mv

，mD

中最小者d’=mD

-mV=|(xi+1)2+(yi-1)2-R2|-|xi2+(yi-1)2-R2|=(xi+1)2+(yi-1)2-R2+xi2+(yi-1)2-R2=2(i-xi)-1若d’<0，则选D若d’>0，则选V若d’=0，则选D情形④也适用(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)③④Bresenham画圆算法（5/7）当i=0时，D在圆上，⑤按d判别，有d>0，应选D按d’判别，有d’<0，应选D(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)⑤Bresenham画圆算法（6/7）当i<0时,若d≤0，选H若d>0，选D当i>0时,若d’≤0，选D若d’>0，选V当i=0时，选D(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)Bresenham画圆算法（7/7）判别式的递推关系当取H(xi+1,yi)时i+1=(xi+1+1)2+(yi-1)2-R2=i+2(xi+1)+1当取V(xi,yi-1)时i+1