计算机图形学基础教程——第2章1.ppt

《计算机图形学基础教程——第2章1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章光栅图形学什么是光栅图形学？光栅显示器－>图形光栅化、光栅化图形的处理清华大学计算机科学与技术系计算机图形学基础光栅图形学的研究内容直线段的扫描转换算法圆弧的扫描转换算法多边形的扫描转换与区域填充字符裁剪反走样消隐清华大学计算机科学与技术系计算机图形学基础2.1直线段的扫描转换算法直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。清华大学计算机科学与技术系计算机图形学基础2.1.1数值微分(DDA)法基本思想已

2、知过端点的直线段L：直线斜率为从的左端点开始，向右端点步进。步长=1(个象素)，计算相应的y坐标；取象素点(x,round(y))作为当前点的坐标。清华大学计算机科学与技术系计算机图形学基础作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。由此出发点，导致增量算法的思想。清华大学计算机科学与技术系计算机图形学基础计算当时;即：当x每递增1，y递增k(即直线斜率)；清华大学计算机科学与技术系计算机图形学基础例：画直线段xint(y+0.5)y+0.5000

3、100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：网格点表示象素清华大学计算机科学与技术系计算机图形学基础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;清华大学计算机科学与技术系计算机图形学基础问题：当k1时，会

4、如何？清华大学计算机科学与技术系计算机图形学基础注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换k<1示意图清华大学计算机科学与技术系计算机图形学基础2.1.2中点画线法采用增量思想的DDA算法，每计算一个象素，只需计算一个加法，是否最优？如非最优，如何改进？目标：进一步将一个加法改为一个整数加法。新思路－>DDA算法采用点斜式，可否采用其他的直线表示方式？清华大学计算机科学与技术系计算机图形学基础基本思想当前象素点为(xp,yp)。下一个象素点

5、为P1或P2。设M=(xp+1,yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。当M在Q的下方，则P2应为下一个象素点；M在Q的上方，应取P1为下一点。清华大学计算机科学与技术系计算机图形学基础构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1,b=x1-x0,c=x0y1-x1y0当d<0，M在L(Q点)下方，取右上方P2为下一个象素；当d>0，M在L(Q点)上方，取右方P1为下一个象素；当d=0，选P1或

6、P2均可，约定取P1为下一个象素；清华大学计算机科学与技术系计算机图形学基础但这样做，每一个象素的计算量是4个加法，两个乘法。“山穷水尽疑无路”如果也采用增量算法呢？d是xp,yp的线性函数，因此可采用增量计算，提高运算效率。清华大学计算机科学与技术系计算机图形学基础若当前象素处于d0情况，则取正右方象素P1(xp+1,yp),要判下一个象素位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量为a若d<0时，则取右上方象素P2(xp+1,yp+1)。要判断再下一象素，则要计算

7、d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量为a＋b清华大学计算机科学与技术系计算机图形学基础至此，至少新算法可以和DDA算法一样好。能否再做改进？能否实现整数运算？清华大学计算机科学与技术系计算机图形学基础画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b=a+0.5b。可以用2d代替d来摆脱小数，提高效率。令d0=2a+b,d1=2a,d2=2a+2b,我们有如下算法。清华大学计算机科学与技术系计算机图形学基础voidM

8、idpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x