计算机图形学 第三章 直线、圆、椭圆生成算法课件.ppt

《计算机图形学 第三章 直线、圆、椭圆生成算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章直线、圆、椭圆生成算法图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。图形显示前需要：扫描转换+裁剪●裁剪---〉扫描转换：最常用，节约计算时间。●扫描转换---〉裁剪：算法简单；本章内容？扫描转

2、换直线段DDA算法中点画线法Bresenham画线算法？圆弧、椭圆弧扫描转换中点算法内接正多边形迫近法等面积正多边形逼近法生成圆弧的正负法直线段的扫描转换算法直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。数值微分法（ＤＤＡ）假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。数值微分(D

3、DA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。数值微分(DDA)法计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换数值微分(DDA)法增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步

4、的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x++)drawpixel(x,int(y+0.5),color);y=y+k;数值微分(DDA)法例：画直线段P0(0,0)--P1(5,2)xint(y+0.5)y+0.5000+0.5100.4

5、+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。中点画线法原理：假定直线斜率0

6、关系？M中点画线法假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知，令F(x,y)=ax+by+c：将任意（x,y）代入F(x,y)∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。中点画线法构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法

7、呢？中点画线法若d0，则M在直线上方，取P1;此时再下一个象素的判别式为d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量为a中点画线法若d<0，则M在直线下方，取P2;此时再下一个象素的判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为a＋b中点画线法画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=

8、a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b由于只用d的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。公式：已知两个端点P0(x0,y0),P1(x1,y1)a=y0-y1,b=x1-x0,c=x0y1-x1y0d0=2a+bd=d+ad0,x=x+1d=d+a+bd<0,x=x+1,y=y+1X从x0变化到x1中点画线