(计算机图形学)基本图形的扫描转换

第二章3.1直线的扫描转换3.2直线的Wu反走样算法3.3圆的扫描转换3.4椭圆的扫描转换（自学）3.6本章小结本章内容直线、圆、椭圆是二维场景中的最基本图形。尽管MFC的CDC类已经提供了相关的绘制函数，但直接使用这些函数仍然无法满足真实感图形绘制的要求。光栅扫描显示器是画点设备，基本图形的光栅化就是在像素点阵中确定最佳逼近于理想图形的像素点集，并用指定颜色显示这些像素点集的过程。当光栅化与按扫描线顺序绘制图形的过程结合在一起时，也称为扫描转换。本章从基本图形的生成原理出发，使用绘制像素点函数实现基本图形的扫描转换。绘制像素点函数的原型为BOOLSetPixelV(intx,inty,COLORREFcrColor);直线、圆、椭圆的扫描转换主要使用Bresenham算法实现。JackEltonBresenhamPlottermovementBresenham算法最初是为数字绘图仪提出，但同样适用于光栅显示器。直线的扫描转换是在屏幕像素点阵中确定最佳逼近于理想直线的像素点集的过程。计算机图形学要求直线的绘制速度要快，即尽量使用加减法（增量算法），避免乘、除、开方、三角等复杂运算。最著名的算法是由J.E.Bresenham于1965年提出的Bresenham算法。3.1直线的扫描转换yxO直线的扫描转换提出问题：•许多软件中都供了绘制直线的函数，为什么要讲直线绘制算法？如，MFC的CDC类就提供了MoveTo与LineTo函数。•连续理想直线是用直线路径上的离散像素点来绘制的。•MoveTo与LineTo函数无法绘制光滑的（颜色渐变）走样或反走样直线。而上述直线是光照模型的基础。颜色渐变走样直线光照线框球光栅扫描显示器的本质决定它难以生成完美的直线段，也不能保证直线段精确地通过起点和终点。绘制直线段的基本要求：•直线要直。要求具有精确的起点和终点。•直线无方向性。从起点绘制到终点的直线段与从终点绘制到起点的直线段要重合。•直线的绘制速度要快。即尽量使用加减法整数运算，避免乘、除、开方、三角等复杂运算。但随着计算机处理浮点数与整数的速度趋于一致，这点要求在减弱。•MSDN:Drawsalinefromthecurrentpositionupto,butnotincluding,thepointspecifiedbyxandy(orpoint).Thelineisdrawnwiththeselectedpen.Thecurrentpositionissettox,yortopoint.红绿两段直线连结点处的颜色应该是红色还是蓝色？连结点像素要求不绘制两次。Bresenham算法的特点：•Bresenham算法是一个经典的增量算法。在一个迭代算法中，如果每一步的x，y值是用前一步的值加上一个增量来获得的，那么这种算法就称为增量算法。•Bresenham算法有几种变体，计算方法略有不同。本章只介绍中点Bresenham算法（MidpointBresenhamAlgorithm）。•对于直线，中点Bresenham算法与Bresenham算法产生同样的像素点，而且还可以扩展为更复杂的图形扫描转换算法，如绘制圆的中点Bresenham算法和绘制椭圆的中点Bresenham算法。3.1.1算法原理直线的中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点误差项的值。给定理想直线的起点坐标为P0(x0,y0)，终点坐标为P1(x1,y1),则直线的隐函数方程为：0),(bkxyyxF（3-1）其中，直线的斜率：0101xxyyxyk直线水平方向位移：01xxx直线垂直方向位移：01yyyPi(xi,yi)PuPdMPdPuMPdPuPi(xi,yi)Pi(xi,yi)理想直线将平面划分成三个区域：对于直线上的点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0；对于直线下方的点，F（x，y）＜0。假设直线的斜率为0≤k≤1，则△x≥△y，所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点误差项的值。直线中点Bresenham算法原理假定直线的当前点是P，沿主位移x方向走一步，下一点只能在Pu和Pd两点中选取，Pu和Pd的中点为M。显然，若中点M在理想直线的下方，则Pu点距离直线近，否则选取Pd。3.1.2构造中点误差项从Pi(xi,yi）点出发选取下一像素时，需将Pu和Pd的中点M(xi＋1,yi＋0.5)代入隐函数方程，构造中点误差项di。bxkyyxFdiiiii)1(5.0)5.0,1(（3-2）)0(,)0(,11iiiiidydyy（3-3）3.1.3递推公式1.中点误差项的递推公式M(xi+2,yi+1.5）M(xi+2,yi+0.5)Pi(xi,yi）（a）di0（b）di≥0中点的递推Pi(xi,yi）PuPdPdPu(1)当di0时，下一步的中点坐标为M（xi+2，yi+1.5），下一步中点误差项为)5.1,2(1iiiyxFdkbxkyii1)1(5.0⑵当di≥0，时下一步的中点坐标为M（xi+2，yi+0.5），下一步中点误差项为)5.0,2(1iiiyxFdkbxkyii)1(5.0（3-5）（3-4）bxkyii)2(5.1kdi1bxkyii)2(5.0kdib1)k(x0.5ydiii直线的起点坐标为P0(x0,y0)，x为主位移方向。因此，第一个中点是M(x0+1,y0+0.5)，相应的di的初始值为：bxkyyxFd)1(5.0)5.0,1(000005.000kbkxy其中，因为（x0，y0）在直线上，所以000bkxy则：kd5.00（3-6）2.中点误差项的初始值说明：由于使用的是di的符号，可以用2di△x代替di来摆脱小数，使得算法只涉及整数运算。——孙家广《计算机图形学（第3版）》。现有的研究已经证明：端点采用整数坐标没有什么益处，因为现在的CPU可以按照与处理整数同样的速度处理浮点数。因此本课程中使用的中点Bresenham算法采用了浮点数运算并且方便解决了直线的反走样问题。0≤k≤1的Bresenham算法：（1）输入直线段的两个端点坐标P0(x0,y0)，P1(x1,y1)。（2）计算△x=x1-x0，△y=y1-y0，k=△y/△x,d=0.5-k。（3）绘制点P(x,y)，判断d的符号。如果d0，则P(x,y)点更新为P(x+1,y+1)，d更新为d+1-k；否则，P(x,y)点更新为P(x+1,y)，d更新为d-k。（4）当P点的x坐标小于P1点的x坐标时，重复步骤（3），否则结束程序。例:从(20,10)到(30,18),画直线.ixiyipiixiyipi02010662615212111272716-222212-28281614323121492917104241310103018525146思考：K1时如何画线？voidCTestView::BresenhamLine(CDC*pDC){CPointp0(-100,-50),p1(200,50),p;intdx,dy;dx=p1.x-p0.x;dy=p1.y-p0.y;doublek,d;k=(double)dy/dx;d=0.5-k;for(p=p0;p.xp1.x;p.x++)//不包括终点(x1,y1){pDC-SetPixelV(p,RGB(0,0,0));if(d0){p.y++;d+=1-k;}elsed-=k;}}k=-1k=10≤k≤1k=0|k|=∞k＜-1k＞1-1≤k＜0k-10≤k≤1-1≤k＜0k＜-1直线斜率的对称性3.1.4绘制任意斜率的直线任意斜率的直线3.1.4颜色渐变直线绘制光滑过渡的彩色直线段时，需要使用公式（3-28）进行前景色线性插值c=(1-t)c0+tc1（3-28）式中，c为颜色渐变直线段上任一点的颜色；c0为直线段起点的颜色；c1为直线段终点的颜色。颜色渐变直线voidCTestView::CLine(CDC*pDC){CPointp0(-100,-50),p1(200,50),p;intdx=p1.x-p0.x,dy=p1.y-p0.y;doublek,d;k=(double)dy/dx;d=0.5-k;doubledc=1/(double)dx;for(p=p0;p.xp1.x;p.x++)//不包括终点p1{doubler,g,b;r=(1-(p.x-p0.x)*dc),g=0,b=(p.x-p0.x)*dc;pDC-SetPixelV(p,RGB(r*255,g*255,b*255));if(d0){p.y++;d+=1-k;}elsed-=k;}}后面讲解的圆的中点Bresenham算法与椭圆的中点Bresenham算法，采用类似的步骤，请同学们掌握学习的技巧。直线是构成复杂图形的基本图元，场景中的模型往往由成千上万条直线组成，所以直线的中点Bresenham算法是本章学习的重点。直线的中点Bresenham算法小结：1.确定主位移方向。在主位移方向上每次加1，另一个方向上加不加1，取决于中点误差项。2.计算d的初始值。3.区分di0与di≥0两种情况，分别计算di的递推公式。3.2反走样技术直线扫描转换算法在处理非水平、非垂直且非45°的直线段时会出现锯齿，这是因为直线段在光栅扫描显示器上显示的图像是由一系列亮度相同而面积不为零的离散像素点构成的。这种由离散量表示连续量而引起的失真称为走样（aliasing）。用于减轻走样现象的技术称为反走样（anti-aliasing,AA）或者抗锯齿。走样是理想直线（理想直线宽度为零）扫描转换后（真实像素点面积不为零）的必然结果。走样是光栅扫描显示器的一种固有现象，不可避免，只能减轻。不走样直线走样直线未开抗锯齿开启抗锯齿“word”绘制的斜线“画图”绘制的斜线反走样技术主要分为两类：一类是硬件技术，通过提高显示器的分辨率来实现；另一类是软件技术，通过改进软件算法来实现。从硬件角度把显示器的分辩率提高了一倍。由于每个锯齿在x方向和y方向都只有原先分辨率的一半，所以看上去走样现象有所改善。虽然如此，硬件反走样技术由于受到硬件条件和成本的限制，实现起来较为困难，很难达到理想的反走样效果。显示器的分辨率提高一倍的效果图软件反走样技术主要是加权区域采样。算法的实质是利用人眼视觉特性，通过加权平均的方法，调节像素的亮度和灰度，以产生模糊的边界，从而达到较好的视觉效果以消除“锯齿”。加权参数可以选择距离、面积和体积等。下面主要讲解直线的距离加权反走样算法，关于面积加权和体积加权反走样算法请参考相关文献。3.2Wu反走样算法武筱林（XiaolinWu）教授1982年毕业于武汉大学，1988年获得加拿大卡尔加里大学计算机科学博士学位，现任加拿大麦克马斯特大学电子与计算机工程系终身教授，并担任加拿大NSERC-DALSA数字影院首席科学家。武筱林教授1998年获得加拿大UWO卓越研究教授奖，2000年获得丹麦Monsteds研究奖（每年仅一人），2003年获得芬兰诺基亚国际研究奖（每年三人）等。武筱林于1991年在computerGraphics上提出“EfficientAntialiasingTechnique”。3.2.1算法原理P6P4P2P3P1P5F1F3距离理想直线0.8个像素远的像素亮度为80％距离理想直线0.2个像素远的像素亮度为20％距离理想直线0.45个像素远的像素亮度为45％距离理想直线0.1个像素远的像素亮度为10％距离理想直线0.55个像素远的像素亮度为55％距离理想直线0.9个像素远的像素亮度为90％AB距离加权反走样算法原理F1F2F3Wu反走样算法是采用空间混色原理来对走样进行修正。空间混色原