基本图形生成算法

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

2、ddress(x,y) 1Address(x,y1) = k1 + k2(y 1) + x = Address(x,y) k2Address(x1,y1) = k1 + k2(y 1) + (x1) = Address(x,y) k2 1对像素连续寻址时，如何减少计算量？增量法的优点？5图形显示的几种方式图形显示前需要：扫描转换+裁剪裁剪扫描转换：最常用，节约计算时间扫描转换裁剪：算法简单6直线段扫描转换假设像素间均匀网格，整型坐标系，直线段斜率0m1对m1，x、y互换7直线段的扫描转换算法直线的扫描转换 确定最佳逼近于该直线的一组象素按扫描线顺序，对这些象素进行写操作三个常用算法：1数值微分

3、法（DDA）2中点画线法3Bresenham算法。8数值微分(DDA)法(1/5)已知线段端点：P0(x0,y0), P1(x1,y1)直线方程 y=kx+b (xi, yi), i=0,.n.浮点数取整 : yi=round(yi)=(int)(yi+0.5)用到浮点数的乘法、加法和取整运算9数值微分(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互换。10数值微分(DDA)法(3/5)digital di

4、fferential analyzer基本思想用数值方法解微分方程 dy/dt = xdy/dt = y xn+1 = xn + x yn+1 = yn + y 如何选取？选取的原则：使0.5|x|,|y|111数值微分(DDA)法(4/5)对称的DDA取=2-n使 2n-1max(|x |,|y|)2n简单的DDA取= 1/max(|x |,|y|)使 |x |, |y|中必有一个是单位步长x为最大时， x =1, x =ky为最大时， y =1, y =1/k12数值微分(DDA)法(5/5)缺点：浮点数运算不易硬件实现13中点画线法（1/4）问题：判断距离理想直线最近的下一个象素点已知：

5、线段两端点(x0,y0)，(x1,y1)直线方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判断M点在Q点上方还是在Q点下方？14MP1P2P直线上方点： F(x,y)0 直线下方点: F(x,y)0构造判别式： d=F(M)=F(Xp+1,Yp+0.5)由d0，d0可判定下一个象素(Xp+1,Yp+0.5)中点画线法（2/4）15分两种情形考虑再一下个象素的判定：若d0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp)再下一个象素的判别式为： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的

6、增量为a若d0，中点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+bMP1P2MP1P216d的初始值d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b用2d代替d后，d0=2a+bd的增量都是整数优点：只有整数运算，不含乘除法可用硬件实现因(X0,Y0)在直线上，所以F(X0,Y0)=0中点画线法（4/4）17Bresenham画线算法（1/7）使用最广泛与中点画线法的思想类似由误差项符号决定下一个象素取正右

7、方像素还是右上方像素18Bresenham画线算法（2/7）基本思想比较从理想直线到位于直线上方的像素的距离d1和相邻的位于直线下方的像素的距离d2根据距离误差项的符号确定与理想直线最近的象素19Bresenham画线算法（3/7）最大位移方向每次走一步k1时，x为最大位移方向y方向走步与否取决于误差e值的大小误差计算初值：e0= y/ x当e0.5时，最接近P2(xi+1,yi+1)y方向走一步当e0.5时，最接近P1(xi+1,yi)y方向不走步eP1P2PeeP1P2Pe20Bresenham画线算法（4/7）为方便与0比较，设e=e-0.5e0=y/ x-0.5当e0时，最接近P2(x

8、i+1,yi+1)y方向走一步当e0时，最接近P1(xi+1,yi)y方向不走步有除法，不宜硬件实现eP1P2PeeP1P2Pe21Bresenham画线算法（5/7）设e=e2x，不影响判断的准确性e0=2y - x 当e0时，最接近P2(xi+1,yi+1)y方向走一步当e0时，最接近P1(xi+1,yi)y方向不走步eP1P2PeeP1P2Pe22Bresenham画线算法（6/7）下一步误差的计算当e0时，y方向走一步e=2y/ x - 1 =e + y/ x - 1 e=e + 2y - 2x当e0时，y方向不走步e=2y/ x=e + y/ xe=e + 2yeP1P2PeeP1P

9、2Pe23Bresenham画线算法（7/7）优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现24圆弧的扫描转换圆的八对称性只考虑第二个八分圆假设圆心在原点 x2+y2=R2 yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR25圆弧的扫描转换两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点：计算量大所画像素位置间的间距不一致 26中点画圆法（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距离圆弧近，取P227

10、中点画圆法（2/2）若 d=0, 取P1为下一象素，再下一象素的判别式为 初始象素是（0,R），判别式d的初值为P1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替de0=1-R28DDA画圆法（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/ yn xn+1 - xn = yn yn+1 - yn = -xn实际画出的曲线不是圆，而是螺旋线，为什么？29DDA画圆法（2/3）将递推公式写成矢量形式：构造一个行列式值为1的矩阵对应的圆

11、方程递推关系为 xn+1 = xn + yn yn+1 = -xn +(1-2)yn= yn- xn+1 30DDA画圆法（3/3）针对不同象限及顺逆时针画圆，赋给适当的符号 不同，圆形状不同， 大近似椭圆31Bresenham画圆算法（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)HPiVD(xi+1,yi)(xi,yi-1)(xi+1

12、,yi-1)32Bresenham画圆算法（2/7）圆弧与点(xi,yi)附近光栅网格的相交关系有5种右下角像素D (xi,yi)与实际圆弧的近似程度i=(xi+1)2+(yi-1)2-R2当i0时，D在圆外，当i=0时，D在圆上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)33Bresenham画圆算法（3/7）当i0时，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)-

13、1若d0，则选D若d=0，则选H情形也适用34Bresenham画圆算法（4/7）当i0时，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若d0，则选V若d=0，则选D情形也适用35Bresenham画圆算法（5/7）当i=0时，D在圆上，按d判别，有d0，应选D按d判别，有d0，应选D36Bresenham画圆算法（6/7）当i0，选D当i0时,若d 0，选D 若d0，选V当i=0时，选D37Bresenham画圆算法（7/7）判别式的递推关系当取H(xi+1,yi)时i+1=(xi+1+1)2+(yi-1)2-R2= i