《计算机图形学》04二维图形生成技术ppt课件.ppt

《《计算机图形学》04二维图形生成技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章二维图形生成技术4.1直线图形yx1234n1234mp1p2一.生成直线的DDA算法假设直线的起点坐标为P1(x1,y1)，终点坐标为P2(x2,y2)x方向的增量为△x＝x2－x1；y方向上增量为△y＝y2－y1直线的斜率为k＝△y／△x当△x＞△y时，让x从x1到x2变化，每步递增1，那么，x的变化可以表示为xi+1＝xi＋1y的变化可以表示为yi+1＝yi＋k用上式可求得图中直线P1P2和y方向网格线的交点，但显示时要用象素点(图中的网格结点)耒表示，所以要用舍入的办法耒找到最靠近交点处的象素点，并用其耒表

2、示直线段。这个方法称之为数字微分分析法，简称DDA。算法描述如下：intx1，y1，x2，y2；intx；floatdx，dy，k，y；dx＝x2－x1dy＝y2－y1k＝dy／dxx＝x1y＝y1for(x＝x1；x＜＝x2；x＋＋){putpixel(x，(int)(y)，pixelcolor)y＝y＋k}该算法仅适用于｜k｜≤1的情况，而当｜k｜＞1时，则需将x和y的位置交换。二.生成直线的Bresenham算法设k＝△y／△x，先讨论0≤k≤1的情况：若以屏幕上x方向的象素点作为横坐标，则有xi+1－xi＝1而y

3、i+1＝yi＋k(xi+1－xi)＝yi＋k(1)设b点是直线上的点，其实际坐标是(xi+1，yi+1)。在屏幕上是用象素点c还是d耒表示？设a为c、d的中点，判断。关键问题：(1)如何判断b是在a的上面还是下面，设置一个标志变量e；(2)如何建立标志变量e的递推公式。xiXi+1Yi'Yi+1Yi+1'bacd设e(xi+1)＝yi+1－yi′－0.5(2)若b在a的下面，则有e(xi+1)<0若b在a的上面，则有e(xi+1)>0由图中可知：当e(xi+1)≥0时y′i+1＝yi′＋1e(xi+1)<0时y′i+1＝

4、yi＇递推：由(2)、(3)式可得：e(xi+2)＝yi+2－y′i+1－0.5＝yi+1＋k－y′i+1－0.5yi+1－yi′－0.5＋k－1e(xi+1)≥0yi+1－yi′－0.5＋ke(xi+1)<0e(xi+1)＋k－1e(xi+1)≥0e(xi+1)＋ke(xi+1)<0==(3)算法描述如下：△x＝x2－x1△y＝y2－y1k＝△y／△xe＝k－0.5(若起始点在象素中心，则e的初始值为－0.5)x＝x1y=y1for(i＝1；i＜＝△x；i＋＋){putpixel(x，y，pixelcolor)x＝x＋

5、1if(e＜0)e＝e＋kelse{y＝y＋1；e＝e＋k－1}}讨论：斜率不同时：以上讨论的是0≤k≤1的情况，即0＜△y＜△x的情况；若是0＜△x＜△y的情况，则需将x和y的位置交换。方向不同时：若△y＜0或△x＜0时，要将算法中的y＝y＋1换成y＝y－1、x＝x＋1换成x＝x－1。4.2二次曲线一、圆的生成算法即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。下面仅以圆心在原点的圆为例，讨论圆的生成算法。1.圆弧扫描算法x2+y2=r2y=Sqrt(r2-x2)在一定范围内，每给定一x值，可得一y值。

6、当x取整数时，y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法x=x0+rcosy=y0+rsindx=-rsinddy=rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。3.Bresenham画圆算法该算法以点(0,r)为起点，按顺时针方向生成圆时，相当于在第一象限内，所以y是x的单调递减函数。从圆上任一点出发，

7、按顺时针方向生成圆时，为了最佳地逼近该圆，对于下一个象素的取法只有三种可能的选择，即右方象素(H)、右下角象素(D)、下方象素(V)。（0，r)yx(xi,yi)(xi,yi)(xi+1,yi)H(xi,yi-1)V(xi+1yi-1)D设△i＝(xi+1)2＋(yi-1)2－r2若△i＜0，则右下角点在圆内，此时只可能取象素点H或D设δ1＝｜(xi+1)2＋(yi)2－r2｜－｜(xi+1)2＋(yi-1)2－r2｜若δ1＜0取Hδ1＞0取Dδ1＝0二者距离相等，规定取右方象素H并可将δ1进一步化简成δ1＝2(△i＋y

8、i)－1若△i＞0，则右下角点在圆外，此时只可能取象素点D或V设δ2＝｜(xi+1)2＋(yi-1)2－r2｜－｜(xi)2＋(yi-1)2－r2｜若δ2＜0取Dδ2＞0取Vδ2＝0二者距离相等，规定取右下角象素D并可将δ2进一步化简成δ2＝2(△i－xi)－1若△i＝0，此时圆上点正好是D，即取D。导出简单增量算法