计算机图形学ppt课件第二章基本图形的生成与计算.pptx

第二章

基本图形的生成与计算

图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：确定有关像素用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。

扫描转换---〉裁剪：算法简单；图形显示前需要：扫描转换+裁剪裁剪---〉扫描转换：最常用，节约计算时间。

直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。2.1直线的生成算法

直线DDA算法设直线起点为（x1,y1），终点（x2,y2），则斜率m为

这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。计算yi+1=mxi+1+b =mxi+b+k?x =yi+m?x当?x=1; yi+1=yi+m即：当x每递增1，y递增m(即直线斜率)；注意上述分析的算法仅适用于?m?≤1的情形。在这种情况下，x每增加1,y最多增加1。当?m??1时，必须把x，y地位互换

1a011b022b032a043a053b064b074a08(x1,y1)09(x2,y2)10

直线从（x1，y1）到（x2，y2）的方向不同，分为8个极限。方向在第1a象限内的直线，取增量Dx=1，Dy=m；在1b象限内的，取增量Dy=1，Dx=1/m。表２.1象限|dx||dy|?DxDy象限|dx||dy|?DxDy1aTrue1m3aTrue-1-m1bFalse1/m13bFalse-1/m-12aTure-1m4aTure1-m2bFalse-1/m14bFalse1/m-1

研究表２.1的数据，可以得到如下规律：当|dx||dy|时|Dx|=1，|Dy|=m否则|Dx|=1/m，|Dy|=1Dx，Dy的符号与dx，dy的符号相同依据上述规律可以生成直线，每生成一条直线做两次除法，画线中的每点做两次加法，所以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;??

例：画直线段P0(0,0)--P1(5,2)xint(y+0.5) y+0.50 0+0.50 0.4+0.51 0.8+0.5 1 1.2+0.52 1.6+0.52 2.0+0.5

缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。

当M在Q的下方-P2离直线更近更近-取P2在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？直线中点画线法

01假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：020304∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。直线中点画线法

构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)下方，取右上方P2；当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？直线中点画线法

若d?0-M在直线上方-取P1;01d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c03增量为a05此时再下一个象素的判别式为02=a(xp+1)+b(yp+0.5)+c+a=d+a；04直线中点画线法

若d0-M在直线下方-取P2;此时再下一个象素的判别式为d2=