计算机图形学3- 基本图形的扫描转换.ppt

,基本图形（直线、圆、椭圆）的扫描转换,扫描转换的基本概念绘制像素点函数SetPixel的用法直线圆和椭圆的中点Bresenham原理直线反走样原理,本章学习目标,本章内容,3.1直线的扫描转换3.2圆的扫描转换3.3椭圆的扫描转换3.4反走样算法3.6本章小结3.7习题,4,什么是扫描转换？直线、圆、椭圆是图形设计的最基本的图形（图元）。图形的扫描转换（光栅化）：在像素点阵中确定最佳逼近于理想图形的像素占集的过程。,5,步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。,6,图形显示前需要：扫描转换+裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；,3.1直线的扫描转换,直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。,8,数值微分法（）,假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。,(Xi+1,Yi+k),(Xi,Int(Yi+0.5),(Xi,Yi),栅格交点表示象素点位置,。,。,。,。,9,基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为设x=x1-x0,y=y1-y0设xy0,让x从起点到终点变化，每步递增1个像素，计算对应的y坐标。,10,计算yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k即：当x每递增1个像素，y递增k(即直线斜率)；注意上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换，怎么实现？,11,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,12,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;xx1,x+)drawpixel(x,int(y+0.5),color);y=y+k;,13,例：画直线段P0(0,0)-P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,012345,3,2,1,Line:P0(0,0)-P1(5,2),缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,一、原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为：,中点画线法,其中，直线的斜率：,直线水平方向位移：,直线垂直方向位移：,（3-1）,16,理想直线将平面划分成三个区域：对于直线上的点，F(x，y)0；对于直线上方的点，F（x，y）0；对于直线下方的点，F（x，y）0。假设直线的斜率为0k1，则，所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点偏差判别式的值。,17,假定直线的当前点是，沿主位移x方向走一步，下一点只能在和两点中选取。和的中点为，如图3-2所示。显然，若中点M在理想直线的下方，则点距离直线近，点亮；否则点亮。,18,F（x，y）0,F（x，y）=0,F（x，y）0,直线中点Bresenham算法原理,19,二、构造中点偏差判别式,从P（xi，yi）点走第一步后，为了进行下一像素点的选取，需将Pu和Pd的中点M（xi1，yi0.5）代入隐函数方程，构造中点偏差判别式d。,（3-2）,20,当d0时，中点M在直线的上方，Pd点离直线距离近，下一像素点应点亮Pd，即y方向上不走步；当d0时，中点M在直线上，Pu、Pd与直线的距离相等，点亮Pu或Pd均可，约定取Pd。,（3-3）,21,三、递推公式,M（xi2，yi1.5）,M（xi1，yi0.5）,P（xi，yi）,M（xi1，yi0.5）,M（xi2，yi0.5）,P（xi，yi）,中点偏差判别式的递推,d0,d0,1.中点偏差判别式的递推公式在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素，如图3-3所示，分两种情况讨论。,22,(1)当d0,F（x，y）=0,F（x，y）0,26,3.2.1算法原理,圆心在原点、半径为R的圆方程的隐函数表达式为：,圆将平面划分成三个区域：对于圆上的点，F(x，y)0；对于圆外的点，F（x，y）0；对于圆内的点，F（x，y）0。,（3-7）,27,事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。因为AC段圆弧和CB段圆弧以对称轴xy完全对称，如图3-6所示，所以可以用四条对称轴x0，y0，xy,xy把圆分成8等份。只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。假定第一象限内的任意点为P（x,y），可以顺时针确定另外7个点：P（y，x）P（y，x）,P（x,y）,P（x，y），P（y，x），P（y，x），P（x，y）。,28,P（-y，x）,P（-y，-x）,x=-y,P（-x，-y）,P（x，-y）,P（y，-x）,P（y，x）,P（x，y）,P（-x，y）,x=y,x=0,y=0,3-6圆的对称性,29,本算法只考虑图3-6所示阴影部分的45圆弧，即第一象限内的1/8圆弧。,顺时针确定最佳逼近于该段圆弧的像素点集。为什么是顺时针画圆？中点Bresenham算法的原理简化为：x方向上每次加1，y方向上减不减1取决于中点偏差判别式的值。,此时中点Bresenham算法要从（0，R）到(,）,30,假定圆当前点是P（xi，yi）,下一点只能在Pu（xi1，yi）和Pd（xi1，yi1）中选取，如图3-7所示。Pu和Pd的中点为M（xi1，yi0.5）显然，若M点在理想圆弧的下方，则Pu点离圆弧近，点亮Pu；否则应点亮Pd。,31,Pu（xi1，yi）,y,P（xi，yi）,M（xi+1，yi0.5）,Pd（xi1，yi1）,圆中点Bresenham算法原理,32,3.2.2构造中点偏差判别式,从P（xi，yi）开始，为了进行下一像素点的选取，需将Pu和Pd的中点M（xi1，yi0.5）代入隐函数，构造中点偏差判别式：,（3-9）,当d0时，中点M在圆外，下一像素点应点亮Pd，即y方向退一步；当d0时，中点M在圆上，Pu、Pd和圆的距离相等，点亮Pu或Pd均可，约定取Pd。,因此，,（3-10）,33,3.2.3递推公式,1.中点偏差判别式的递推公式现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步应该点亮的像素，分两种情况讨论。,34,当d0时，下一步的中点坐标为：M（xi2，yi0.5）。,所以下一步中点偏差判别式为：,（3-11）,当d0时，下一步的中点坐标为：M（xi2，yi1.5）。,所以下一步中点偏差判别式为：,（3-12）,35,P（xi，yi）,M（xi1，yi0.5）,M（xi+2，yi0.5）,M（xi1，yi0.5）,M（xi2，yi1.5）,d0,F（x，y）=0,F（x，y）0,理想椭圆,图3-9椭圆的扫描转换,39,3.3.1原理,圆心在原点、长半轴为a、短半轴为b的椭圆方程的隐函数表达式为：,（3-14）,椭圆将平面划分成三个区域：对于椭圆上的点，F(x，y)0；对于椭圆外的点，F（x，y）0；对于椭圆内的点，F（x，y）0，如图3-9所示。,40,考虑到椭圆对称性，可以用对称轴x0，y0，把椭圆分成4等份。只要绘制出第一象限内1/4椭圆弧，如图3-10的阴影部分和所示，根据对称性就可绘制出整个椭圆，这称为四分法绘制椭圆算法。已知第一象限内的点P（x，y），可以顺时针得到另外3个对称点：P（x,y），P（x，y），P（x，y）。,P（x，y）,P（x，y）,P（x，y）,y,P（x，y）,图3-10椭圆的对称性,41,在处理第一象限的1/4椭圆弧时，进一步以法矢量两个分量相等的点把它分为两部分，上半部分和下半部分（切线斜率为-1所在的点作为分界点）。该椭圆上一点P（x，y）处的法矢量为：,（3-15）,式中，i和j是沿x轴向和沿y轴向的单位矢量。,42,在图3-11所示的部分的AC椭圆弧段，法矢量的x向分量小于y向分量，斜率k处处满足|k|1，|x|y|，所以x方向为主位移方向；在C点，法矢量的x向分量等于y向分量，斜率k满足k1，|x|y|；在部分的CB椭圆弧段，法矢量x向分量大于y向分量，斜率k处处满足|k|1，|y|x|，所以y方向为主位移方向。,A（0，b）,B（a，0）,y向分量,法矢量,x向分量,C(,),图3-11椭圆的法矢量,43,椭圆的中点Bresenham算法的原理：在部分：每次在主位移x方向上走一步，y方向上退不退步取决于中点偏差判别式的值；在部分：每次在主位移方向y上退一步，x方向上走不走步取决于中点偏差判别式的值。,图3-12椭圆中点Bresenham算法原理,A（0，b）,B（a，0）,Pu,Pd,Pl,Pr,44,先考虑图3-12所示部分的AC段椭圆弧。此时中Bresenham画椭圆算法要从A（0，b）到（,)顺时针确定顺时针确定最佳逼近于该段椭圆弧的像素点集。由于x方向为主位移方向，假定当前点是P（xi，yi），下一步只能在正右方的像素Pu（xi1，yi）和右下方的像素Pd（xi1，yi1）中选取。,45,再考虑图3-12所示部分CB段椭圆弧。此时中Bresenham画椭圆算法要从C（,)到B（a，0）顺时针确定最佳逼近于该段椭圆弧像素点集。由于y方向为主位移方向，假定当前点是P（xi，yi），下一步只能在正下方像素Pl（xi，yi1）和右下方的像素Pr（xi1，yi1）中选取。,46,3.3.2构造上半部分中点偏差判别式,在上半部分，x方向每次加1，y方向上减不减1取决于中点偏差判别式的值。从P（xi，yi）走第一步，为了选取下一像素点的，需将Pu（xi1，yi）和Pd（xi1，yi1）的中点M（xi1，yi0.5）代入隐函数，构造中点偏差判别式：,当d10时，中点M在椭圆外，下一像素点应点亮Pd，即y方向退一步；当d0时，中点M在椭圆上，Pu、Pd和椭圆的距离相等，点亮Pu或Pd均可，约定取Pd，如图3-13所示。,（3-16）,47,P（xi，yi）,Pu（xi1，yi）,M（xi+1，yi-0.5）,Pd（xi1，yi1）,图3-13上半部分像素点的选取,因此，,（3-17）,48,3.3.3上半部分的递推公式,P（xi，yi),M（xi1，yi0.5）,M（xi2，yi0.5）,P（xi，yi）,M（xi1，yi0.5）,M（xi2，yi1.5）,d10,d10,图3-14上半部分中点偏差判别式的递推,图3-13中，为了能够继续判断椭圆上的每个点，需要给出中点偏差判别式d1的递推公式和初始值。,49,1.中点偏差判别式的递推公式现在如果考虑主位移方向再走一步，应该选取哪个中点代入中点偏差判别式以决定应该点亮的像素，如图3-14所示，分两种情况讨论。当d10时，下一步的中点坐标为：M（xi2，yi-0.5）。所以下一步中点偏差判别式为：,（3-18）,50,当d10时，下一步的中点坐标为：M（xi2，yi1.5）。所以下一步中点偏差判别式为：,（3-19）,51,2.中点偏差判别式d1的初值上半部分椭圆的起点为A（0，b），因此，第一个中点是（1，b0.5），对应的d1的初值为：,（3-20）,52,（3-21）,y,x,P（xi，yi）,Pr（xi1，yi1）,图3-15下半部分像素点的选取,3.3.4构造中点偏差判别式,构造中点偏差判别式：,Pl（xi，yi1）,53,当d20时，中点M在椭圆外，下一像素点应点亮Pl，即x方向上不走步；当d20时，中点M在椭圆上，Pl、Pr和椭圆的距离相等，点亮Pl或Pr均可，约定取Pl，如图3-15所示。,因此，,（3-22）,54,3.3.5下半部分的递推公式,1.中点偏差判别式的递推公式现在如果考虑主位移方向上再走一步，应该选择哪个中点代入中点偏差判别式以决定应该点亮的像素，如图3-16所示，分两种情况讨论。,P（xi，yi）,M（xi0.5，yi1）,M（xi1.5，yi2）,d20,P（xi，yi）,M（xi0.5，yi1）,M（xi0.5，yi2）,d20,图3-16下半部分中点偏差判别式的递推,55,当d20时，下一步的中点坐标为：M（xi1.5，yi2）。所以下一步中点偏差判别式为：,（3-23）,当d20时，下一步的中点坐标为：M（xi0.5，yi2）。所以下一步中点偏差判别式为：,（3-24）,56,则对于上半部分椭圆上一点任意P（xi，yi）,如果在其当前中点M（xi1，yi0.5）处，满足x向分量小于y向分量：,2.中点偏差判别式d2的初值由图3-11知道，在上半部分，法矢量的x向分量小于y向分量；在C点，法矢量的x向分量等于y向分量；在下半部分，法矢量的x向分量大于y向分量。由公式3-15知道：x向分量为：y向分量为：,（3-25）,57,假定图3-17中P（xi，yi）点是椭圆上半部分的最后一个像素，M（xi1，yi0.5）是用于判断点亮Pu和Pd像素的中点。由于下一像素转入了下半部分，所以其中点改为判断Pl和Pr的中点M（xi0.5，yi1），所以下半部分的初值d20为：,（3-26）,58,P（xi，yi）,Pu（xi1，yi）,Pl（xi，yi1）,M（xi1，yi0.5）,Pd（xi1，yi1）=Pr（xi1，yi1）,图3-17下半部分的初值,59,3.4反走样算法,考虑将偏差e作为加权参数，同时用上下（或左右）两个像素点的颜色来表示交点f的颜色。像素a的颜色为c1RGB（e255，e255，e255），像素b的颜色为c2RGB（1e）255，（1e）255，（1e）255），两个像素点颜色的各个相应分量级别之和等于255。,60,当偏差e越小时，c1的分量e255值越小，颜色越暗，同时c2的分量（1e）255值越大，颜色越亮；反之亦然。用两个像素来表示理想线条上的一个点，并依据两个像素与理想直线的距离而调节其灰度级别，所绘制的线条可以达到视觉上消除阶梯的效果。,61,P6,P4,P2,P3,P1,P5,1,2,3,距离理想直线0.8个像素远的像素灰度为80,距离理想直线0.2个像素远的像素灰度为20,距离理想直线0.45个像素远的像素灰度为45,距离理想直线0.1个像素远的像素灰度为10,距离理想直线0.55个像素远的像素灰度为55,距离理想直线0.9个像素远的像素灰度为90,A,B,62,3.6本章小结,本章主要讲解了直线、圆和椭圆的中点Bresenham算法原理以及直线的反走样技术。直线、圆和椭圆作为图形基本图元，其生成算法的优劣对整个图形系统的效率至关重要。在像素级生成算法中，中点Bresenham算法避免了复杂运算，使用了最小的计算量，使单点基本图形生成算法已无优化的余地，已经成为使用最广泛的扫描转换算法。走样是直线光栅化扫描转换的必然结果，只能减轻，不可避免，如何设计直线的反走样算法是计算机图形学的前沿研究课题。,63,3.7习题,计算起点坐标为（0,0），终点坐标（12,9）直线的中点Bresenham算法的每一步坐标值以及中点偏差判别式d的值，填入表3-1中，并用黑色点亮图3-29中的直线像素。,图3-29像素点阵,64,表3-1x,y和d的值,65,2.给定直线的起点坐标为P0（x0，y0）、终点坐标为P1（x1，y1），容易计算出直线的斜率k。假设0k1且x0x1，则x方向为主位移方向，绘制