《计算机图形学教学资料》

1,Chapter3BasicRasterGraphicsAlgorithmsforDrawing2DPrimitives基本二维图元的生成算法,2,Scan-conversion（扫描转换）:确定图形对应的象素集合及其颜色，用于显示一个图形的过程，也称为图形的光栅化。,3,本章内容(outline),直线的扫描转换(SCANCONVERTINGLINES)圆与椭圆的扫描转换(SCANCONVERTINGCIRCLEANDELLIPSE)区域填充(FILLINGREGION)字符生成(GENERATINGCHARACTERS)反走样(ANTIALIASING)二维裁剪(2DCLIPPING),4,图形扫描转换(scan-conversion),Scan-conversion:确定图形对应的象素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。图形扫描转换分为两步：1、确定有关（组成图形的）象素；2、用图形的颜色或其他属性对象素进行写操作。第2步通常是通过调用设备驱动程序完成的，不属于计算机图形学的研究范围。计算机图形学研究前者，即如何确定最佳逼近于图形的象素集。,5,问题给定直线段的两个端点P0(x0,y0)和P1(x1,y1)，把其在光栅扫描显示器上显示出来.描述理想的直线段:没有线宽,由无数个点构成光栅扫描显示器上:有限个不重叠象素组成,SCANCONVERTINGLINES(直线的扫描转换),6,p0,p1,最佳表示:用最靠近理想直线的一些网格点（象素）来代表直线（即确定最佳的最近点和最大似点的集合）。,直线的表示,直线的表示(therepresentationoflines),7,数值微分法（1）(DDA-DigitalDifferentialAnalyzer),X的变化大于y的变化方法：,最简单方法：利用直线方程直接计算象素集。但方法用到了浮点数的乘法，加法和取整运算，影响效率。,8,数值微分法(2),9,令yir=round(yi)其中，round（）表示对yi进行四舍五入。则所求点坐标为(xi+1,round(yi+1)其中,xi+1=xi+1,yi+1=yi+m;,数值微分法(3),10,数值微分法(4),待解决问题若|m|1,则x向每变化1个单位,y向有可能超出1个步长。,解决方法：此时应令yi为自变量。,11,数值微分法(5),在算法中若能保证在一个方向上增量为1，在另一个方向的增量1，就能保证产生最大似点集，从而克服前述问题。最大步长(步距),步进方向:的方向,12,数值微分法(6),voidLine(/*Assumes-1ml,x0x1*/intx0,inty0,/*Leftendpoint*/intx1,inty1,/*Rightendpoint*/intvalue)/*Colorvaluetoplaceinlinespixels*/intx;/*xrunsfromx0tox1inunitincrements*/doubledy=y1y0:doubledx=x1-x0;doublem=dy/dx;doubley=y0;for(x=x0;x=x1;x+)PutPixel(x,Round(y),value);/*Setpixeltovalue*/y+=m;/*Stepybyslopem*/*Line*/Theincrementallinescan-conversionalgorithm.,13,算法优点：简单、自然，消除了最简单方法中的浮点数的乘法。算法缺点：用到了浮点加法运算和取整运算，计算效率低。自变量的选择可根据斜率确定，以得到最佳的直线效果：,数值微分法(7),14,中点画线法(MidpointLineAlgorithm)（1）,问题引出为解决DDA算法中需要浮点数进行加运算，且输出时需取整的不利条件，可以用中点画线法。假设直线的斜率m0,1，两个端点分别是（x0,y0）,（x1,y1）。,15,MidpointLineAlgorithm(2),思想当前一点已确定,用P(xp,yp)来代表时，下一点仅可能在P1和P2中选用M表示P1,P2的中点，M(xp+1,yp+0.5)。Q是理想直线上x=xp+1处的点.比较M和Q的位置关系,可以确定下一点的走向.,16,比较M和Q:若M位于Q的下方,即yMyQ,则应取p1点;原则：当两侯选点的中点落在直线下方时，选较高点，否则选较低点。,MidpointLineAlgorithm(3),17,MidpointLineAlgorithm(4),定义直线函数：,特点：,由于Q点的f(xQ,yQ)=0，若能计算出中点M的f(xM,yM)的正负，则可判定出Q点和M点的位置关系。,其中：ay0y1，bx1x0，cx0y1x1y0,18,MidpointLineAlgorithm(5),Definedecisionfunction(构造判别函数)：,Definedecisionvariable(引入判别参数):,其中：ay0y1，bx1x0，cx0y1x1y0,19,MidpointLineAlgorithm(6),算法描述：斜率m0,1时,问题：如何快速计算判别参数的值？,采用增量计算方法优化判别参数的计算,20,图,4-2,中点绘线法原理示意图,如黄色线所示情形,MidpointLineAlgorithm(7),21,MidpointLineAlgorithm(8),如蓝色线所示情形,22,MidpointLineAlgorithm(9),第一个决策变量dstart为,第1个中点在(x0+1,y0+0.5),因为（x0，y0）点在直线上，ax0by0c0，则,23,算法的递推公式是：,MidpointLineAlgorithm(10),递推公式：,d的初值中存在小数。由于判别时只考虑d的符号，且d的增量都是整数，为消除浮点数计算，可在d的计算公式两侧同乘2。并仍用d表示2d。,24,算法公式是：,MidpointLineAlgorithm(11),问题：以上分析过程只考虑了直线斜率m0,1的情况。,递推公式：,25,MidpointLineAlgorithm(12),26,此时，可利用两候选点的中点与直线的位置关系，选出更接近直线的候选点,MidpointLineAlgorithm(13),27,点/线位置关系的判别计算,采用增量计算方法优化判别公式的计算,MidpointLineAlgorithm(14),28,例：用中点画线法光栅化一条连接两点(0,0)和(5,2)的直线段，写出计算过程。,Example(1),斜率m=(20)/(5-0)=0.4,29,递推如下：,Example(2),30,4,5,6,3,2,1,0,0,1,2,3,3,4,5,6,7,Themidpointlinefrompoint(0,0)topoint(5,2).,Example(3),31,P(xi,yir),Bresenham判别方法示意图,BresenhamLineAlgorithm(1),P(xi,yi),(xi+1,yi+1),构造判别参数:i+1=yi+1-yir0.5,32,BresenhamLineAlgorithm(2),判别参数：i+1=yi+1-yir0.5当i+10时，选择P2(xi+1,yir+1)点当i+10时，选择P1(xi+1,yir)点,采用增量计算方法优化判别参数的计算,第i+2次的i+2yi+2yi+1r0.5,33,BresenhamLineAlgorithm(3),第i+1次的i+1=yi+1-yir0.5第i+2次的i+2yi+2yi+1r0.5(a)若在i+1次时，i+10，则选择P1(xi+1,yir)点i+2=yi+2yi+1r0.5=yi+1+myir0.5=i+1+m,34,BresenhamLineAlgorithm(3),第i+2次的i+2yi+2yi+1r0.5(b)若在i+1次时，i+10，则选择P2(xi+1,yir+1)点i+2=yi+1+m（yir+1)0.5=i+1+m1由此可得如下递推公式初值：x=x0,y=y0=y1y0r0.5=m0.5第i+1步：当0时,选择P2(xi+1,yir+1)点，=+m-1当0时，选择P1(x