第三章基本图形的扫描转换

孔令德

第三章基本图形的扫描转换扫描转换的基本概念JackEltonBresenham简介直线的扫描转换算法圆的扫描转换算法椭圆的扫描转换算法Wu反走样算法本章学习目标3.1直线的扫描转换3.2圆的扫描转换3.3椭圆的扫描转换3.4反走样技术3.5Wu反走样算法3.6本章小结本章内容直线、圆和椭圆是图形设计的基本图形元素。尽管在MFC的CDC类中已有绘制这三种基本图元的成员函数，但是基于光栅扫描显示器的真实感图形生成技术要求使用绘制像素点函数来逐点绘制这些基本图元。光栅扫描显示器是画点设备，不能从像素点阵的一个可编址像素点直接绘制一段直线到达另一个可编址的像素点，只能用靠近这段直线的像素点集来近似地表示。光栅扫描显示器的绘图过程就是在像素点阵中确定最佳逼近于理想图元的像素点集，并用指定颜色显示这些像素点集的过程，这称为图形的扫描转换。JackEltonBresenham

Plottermovement

Bresenham算法最初是为数字绘图仪提出，但同样适用于CRT光栅显示器。BresenhamretiredfromofserviceatIBMasaSeniorTechnicalStaffMemberin1987.Hetaughtfor16yearsatWinthropUniversity.Bresenham‘slinealgorithm,developedin1965,ishismostwell-knowninnovation.“Algorithmforcomputercontrolofadigitalplotter”。Itdetermineswhichpointsona2-dimensionalrastershouldbeplottedinordertoformastraightlinebetweentwogivenpoints,andiscommonlyusedtodrawlinesonacomputerscreen.Itisoneoftheearliestalgorithmsdiscoveredinthefieldofcomputergraphics.

直线的扫描转换就是在屏幕像素点阵中确定最佳逼近于理想直线的像素点集的过程。如图3-1所示。计算机图形学要求直线的绘制速度要快，尽量使用加减法，避免乘除、开方、三角等复杂运算。直线的扫描转换有许多算法，如数值微分法、逐点比较法等，最著名的是中点Bresenham算法。3.1直线的扫描转换图3-1直线的扫描转换理想直线

3.1.1算法原理

直线的中点Bresenham算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点误差项的值。给定理想直线的起点坐标为P0(x0,y0)，终点坐标为P1(x1,y1),则直线的隐函数方程为：（3-1）

其中，直线的斜率：

直线水平方向位移：

直线垂直方向位移：b是直线在y轴上的截距理想直线将平面划分成三个区域：对于直线上的点，F(x，y)＝0；对于直线上方的点，F（x，y）＞0；对于直线下方的点，F（x，y）＜0。假设直线的斜率为0≤k≤1，则△x≥△y，所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点误差项的值。

图3-2直线中点Bresenham算法原理假定直线的当前点是P，沿主位移x方向走一步，下一点只能在Pu和Pd两点中选取，Pu和Pd的中点为M。显然，若中点M在理想直线的下方，则Pu点距离直线近，否则选取Pd。3.1.2构造中点误差项（3-2）

（3-3）

从Pi（xi，yi）点走第一步后，为了选取下一个像素点，需将Pu和Pd的中点M（xi＋1，yi＋0.5）代入直线的隐函数方程，构造中点误差项di。当di<0时，下一像素点应选取Pu，当di>0时，下一像素点应选取Pd，当di＝0时，选取Pu或Pd均可，约定取Pd，如图3-2所示。

3.1.3递推公式

1.中点误差项的递推公式M(xi+2,yi+1.5）M(xi+2,yi+0.5)Pi(xi,yi）

（a）di<0（b）di≥0图3-3中点误差项的递推Pi(xi,yi）PuPdPdPuM(xi+1,yi+0.5）M(xi+1,yi+0.5）

(1)当di<0时

⑵当di≥0时

（3-5）

（3-4）

直线的起点坐标为P0(x0,y0)，x为主位移方向。因此，第一个中点是M(x0+1,y0+0.5)，相应的di的初始值为：

其中，因为（x0，y0）在直线上，所以

则：

（3-6）

2.中点误差项的初始值3.1.4整数化处理中点Bresenham算法有一个缺点：在计算误差项di时，其初始值和递推公式分别包含有小数0.5和斜率k。计算过程中使用了除法，不利于硬件实现。由于中点Bresenham算法中只用到误差项di的符号，可以使用正整数乘以di来摆脱小数运算。这样得到了绘制直线的整数中点Bresenham算法。整数化处理后，误差项的初始值为当di<0时，误差项的递推公式为当di≥0时，误差项的递推公式为

（3-7）

（3-8）（3-9）中点Bresenham算法并不仅用于绘制一段直线，常用于绘制折线构成的多边形。假定多边形各条边的颜色为单色且不相同，如图3-4（a）所示，需要考虑直线段连接点的正确着色问题。对每段折线的两个端点一般采用“起点闭区间、终点开区间”的处理方法，且要考虑折线绘制的方向如图3-4（b）图所示。使用本算法绘制的三角形边界放大效果如图3-5所示。（a）折线的方向（b）端点处理图3-4折线绘制三角形图3-5三角形边界放大效果图3.2圆的扫描转换圆的扫描转换就是在屏幕像素点阵中确定最佳逼近于理想圆的像素点集的过程。圆的绘制可以使用简单方程画圆算法或极坐标画圆算法，但这些算法涉及开方运算或者三角运算，效率很低。本节主要讲解仅包含加减操作的顺时针绘制1/8圆的中点Bresenham算法原理。图3-6圆的扫描转换

圆心在原点、半径为R的圆方程的隐函数表达式为：圆将平面划分成3个区域：对于圆上的点，F(x，y)＝0；对于圆外的点，F（x，y）＞0；对于圆内的点，F（x，y）＜0，如图3-6所示。。根据圆的对称性，可以用四条对称轴x＝0，y＝0，x＝y，x＝－y将圆分成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)。

（3-10）

3.2.1算法原理首先考虑扫描转换图3-7中阴影部分所示的第一象限内的1/8圆弧。此时中点Bresenham算法要从(0,R)到(，)顺时针确定最佳逼近于该段圆弧的像素x=-yx=yP（-x,y）P(x,y）P（-y,x）P(y,x)P（-y,-x）P（y,-x）P（-x,-y）P（x,-y）图3-7圆的对称性点集。此段圆弧的斜率k处处满足|k|≤1，即：|△x|≥|△y|，因此：x方向为主位移方向，中点Bresenham算法的原理简化如下：x方向上每次加1，y方向上减不减1取决于中点误差项的值。图3-8圆中点Bresenham算法原理假定圆弧上当前点是Pi(xi,yi)，下一像素只能在Pu（xi＋1，yi）和Pd（xi＋1，yi－1）两点中选取，如图3-8所示。Pu和Pd的中点为M（xi＋1，yi－0.5）显然，若M点在理想圆弧的下方，则Pu点离圆弧近，选取Pu；否则应选取Pd。3.2.2构造中点误差项

从P（xi，yi）开始，为了进行下一像素点的选取，需将Pu和Pd的中点M(xi+1,yi-0.5)代入隐函数，构造中点误差项：（3-11）

当di<0时，中点M在圆内，下一像素点应选取Pu，即y方向上不退步；当di>0时，中点M在圆外，下一像素点应选取Pd，即y方向上退一步；当di＝0时，中点M在圆上，Pu、Pd和圆的距离相等，选取Pu或Pd均可，约定取Pd。因此，

（3-12）1.中点误差项的递推公式

现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点误差项以决定下一步应该选取的像素，分两种情况讨论，如图3-9所示。3.2.3递推公式

Pi(xi,yi)M(xi+2,yi-0.5)Pi(xi,yi)M(xi+2,yi-1.5）(a)di<0(b)di≥0

图3-9中点误差项的递推⑴当d<0时，下一步的中点坐标

M（xi＋2，yi－0.5），下一步中点误差项为：

（3-13）⑵当d≥0时，下一步的中点坐标M（xi＋2,yi－1.5）。下一步中点误差项为（3-14）

圆的起点为P0（0，R），x为主位移方向。因此，第一个中点是（1，R-0.5），对应的di的初始值为：

（3-15）

2.中点误差项的初始值圆中点Bresenham算法3.3椭圆的扫描转换椭圆的扫描转换是在屏幕像素点阵中选取最佳逼近于理想椭圆像素点集的过程。椭圆是长半轴和短半轴不相等的圆，椭圆的扫描转换与圆的扫描转换有类似之处。本节主要讲解顺时针绘制1/4椭圆的中点Bresenham算法原理，根据对称性可以绘制完整椭圆。图3-10椭圆的扫描转换F(x,y)<0F(x,y)=0F(x,y)>0理想椭圆提出问题：默认的椭圆是圆心位于坐标系原点，长半轴为a、短半轴为b的椭圆。需要进行圆心平移或使用自定义坐标系可以绘制椭圆。如果“x方向上每次加1，y方向上减不减1取决于中点误差项的值”。绘制结果是圆，如何能绘制为椭圆？3.3.1算法原理圆心在原点、长半轴为a、短半轴为b的椭圆方程的隐函数表达式为：（3-16）

椭圆将平面划分成三个区域：对于椭圆上的点，F(x，y)＝0；对于椭圆外的点，F（x，y）＞0；对于椭圆内的点，F（x，y）＜0，如图3-10所示。考虑到椭圆的对称性，可以用对称轴x＝0，y＝0，把椭圆分成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)P(x,-y)图3-11椭圆的对称性ACBX方向分量y方向分量法矢量图3-12椭圆的法矢量在处理第一象限的1/4椭圆弧时，进一步以法矢量两个分量相等的点分为两部分：上半部分Ⅰ和下半部分Ⅱ。椭圆上任意一点P(x,y)处的法矢量为

（3-17）式中，i和j是沿x轴向和沿y轴向的单位矢量。在图3-12所示的部分Ⅰ的AC椭圆弧上，法矢量的x方向分量小于y方向分量，斜率k处处满足|k|＜1，|△x|＞|△y|，所以x方向为主位移方向；

在C点，法矢量的x方向分量等于y方向分量，斜率k满足k＝－1，|△x|＝|△y|；

在部分Ⅱ的CB椭圆弧上，法矢量的x方向分量大于y方向分量，斜率k处处满足|k|＞1，|△y|＞|△x|，所以y方向为主位移方向。本算法需要分Ⅰ和Ⅱ两个部分，按顺时针方向绘制1/4椭圆。在上半部分Ⅰ，x方向上每次加1，y方向上减1不减1取决于中点误差项的值；在下半部分Ⅱ，y方向上每次减1，x方向上加不加1取决于中点误差项的值。椭圆的中点Bresenham的原理先考虑图3-13所示部分Ⅰ的AC段椭圆弧。此时中点Bresenham算法要从点A（0，b）向点C（，），沿顺时针方向确定最佳逼近于该段椭圆弧的像素点集。由于x方向为主位移方向，假定当前点是Pi(xi,yi)，下一步只能在正右方的像素Pu（xi+1，yi）和右下方的像素Pd（xi+1，yi-1）两点中选取。，PPuPdPPlPA（0，b）B（a，0）ⅠⅡCPrP图3-13椭圆中点Bresenham算法原理再考虑图3-13所示部分Ⅱ的CB段椭圆弧。此时中点Bresenham绘制椭圆算法要从点C（，），向点B(a,0)，沿顺时针方向确定最佳逼近于该段椭圆弧的像素点集。由于y方向为主位移方向，假定当前点是Pi（xi，yi），下一步只能在正下方的像素Pl（xi，yi-1)和右下方的像素Pr（xi+1，yi-1）两点中选取。下标l代表left，r代表right。3.3.2构造上半部分Ⅰ的中点误差项在上半部分Ⅰ，x方向每次加1，y方向上减不减1取决于中点误差项的值。从Pi(xi,yi)点出发选取下一像素时，需将Pu(xi+1，yi)和Pd(x

i+1,yi-1)的中点M(xi+1,yi-0.5)代入隐函数，构造中点误差项（3-18）

上半部分椭圆中点Bresenham算法原理当d1i<0时，中点M在椭圆内，下一像素点应选取Pu，即y方向上不退步；当d1i>0时，中点M在椭圆外，下一像素点应选取Pd，即y方向上退一步；当d1i＝0时，中点M在椭圆上，Pu、Pd和椭圆的距离相等，选取Pu或Pd均可，约定取Pd。因此，

（3-19）3.3.3上半部分Ⅰ的递推公式

1.中点误差项的递推公式

如果考虑主位移方向再走一步，应该选择哪个中点代入中点误差项以决定下一步应该选取的像素，分两种情况讨论。Pi(xi,yi)M(xi+2,yi-0.5)Pi(xi,yi)M(xi+2,yi-1.5）(a)di<0(b)di≥0图3-15上半部分中点误差项的递推（3-20）(1)当d1i<0，下一步的中点坐标为M（xi＋2，yi－0.5）。下一步的中点误差项为：

（2)当d1i≥0时，下一步中点坐标为M（xi＋2，yi－1.5）。下一步中点误差项为：

（3-21）2.中点误差项的初始值上半部分椭圆的起点为A（0，b），因此，第一个中点是（1，b－0.5），对应的d1i的初值为

（3-22）3.3.4构造下半部分Ⅱ的中点误差项

在下半部分Ⅱ，主位移方向发生变化，中点Bresenham算法原理为：y方向上每次减1，x方向上加1不加1取决于中点误差项的值。从上半部分Ⅰ的终止点Pi(xi,yi)出发选取下一像素时，需将Pl(xi,yi-1)和Pr(xi+1,yi-1)的中点M(xi+0.5,yi-1)代入隐函数，构造中点误差项（3-23）因此，（3-21）当d2i<0时，中点M在椭圆内，下一像素点应选取Pr，即x方向上走一步；当d2i>0时，中点M在椭圆外，下一像素点应选取Pl，即x方向上不走步；当d2i＝0时，中点M在椭圆上，Pl、Pr和椭圆的距离相等，选取Pl或Pr均可，约定取Pl。3.3.5下半部分Ⅱ的递推公式

现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点误差项以决定应该选取的像素。分两种情况讨论。（a）d2i<0（b）d2i≥0图3-17下半部分中点误差项的递推Pi(xi,yi)M(xi+1.5,yi-2)Pi(xi,yi)M(xi+0.5,yi-2)中点误差项的递推公式⑴当d2i<0，下一步的中点坐标为M（xi＋1.5，yi－2）。下一步的中点误差项为：

（3-26）⑵当d2i≥0时，下一步中点坐标为M（xi＋0.5，yi－2）。下一步的中点误差项为：

（3-25）2.中点误差项的初始值在上半部分Ⅰ，法矢量的x向分量小于y向分量；在C点，法矢量的x向分量等于y向分量；在下半部分Ⅱ，法矢量的x向分量大于y向分量。则对于上半部分椭圆上一点P（xi，yi），如果其当前中点M(xi+1,yi-0.5)，满足x向分量小于y向分量（3-27）而在下一个中点，不等号改变方向，则说明椭圆从上半部分Ⅰ转入了下半部分Ⅱ。Pl(xi,yi)Pl(xi,yi-1)Pd(xi+1,yi-1)=Pr(xi+1,yi-1)MⅡ(xi+0.5,yi-1)MⅠ(xi+1,yi-0.5)Pu(xi+1,yi)图3-18确定下半部分的初始值

假定Pi(xi,yi)点是椭圆上半部分Ⅰ的最后一个像素，MⅠ(xi+1,yi-0.5)是用于判断选取Pu和Pd像素的中点。由于下一像素转入了下半部分Ⅱ，其中点改为判断Pl和Pr的中点MⅡ(xi+0.5,yi-1)。所以下半部分的初值d20为（3-28）椭圆中点Bresenham算法3.4反走样技术直线扫描转换算法在处理非水平、非垂直且非45°的直线段时会出现锯齿，这是因为直线段在光栅扫描显示器上显示的图像是由一系列亮度相同而面积不为零的离散像素点构成的。这种由离散量表示连续量而引起的失真称为走样（aliasing）。用于减轻走样现象的技术称为反走样（anti-aliasing,AA）或者抗锯齿。走样是理想直线（理想直线宽度为零）扫描转换后（真实像素点面积不为零）的必然结果。走样是光栅扫描显示器的一种固有现象，不可避免，只能减轻。不走样直线走样直线未开抗锯齿开启抗锯齿“word”绘制的斜线“画图”绘制的斜线图3-24中，从硬件角度把显示器的分辩率提高了一倍。由于每个锯齿在x方向和y方向都只有原先分辨率的一半，所以看上去走样现象有所改善。虽然如此，硬件反走样技术由于受到硬件条件和成本的限制，实现起来较为困难，很难达到理想的反走样效果。反走样技术主要分为两类：

一类是硬件技术，通过提高显示器的分辨率来实现；另一类是软件技术，通过改进软件算法来实现。图3-24显示器的分辨率提高一倍的效果图

软件反走样技术主要是加权区域采样。算法的实质是利用人眼视觉特性，通过加权平均的方法，调节像素的亮度和灰度，以产生模糊的边界，从而达到较好的视觉效果以消除“锯齿”。加权参数可以选择距离、面积和体积等。下面主要讲解直线的距离加权反走样算法，关于面积加权和体积加权反走样算法请读者参考相关文献。3.5Wu反走样算法1998年获得加拿大UWO卓越研究教授奖，2000年获得丹麦Monsteds研究奖（每年仅一人），2003年获得芬兰诺基亚国际研究奖（每年三人）等。武筱林于1991年在computerGraphics上提出“EfficientAntialiasingTechnique”。

武筱林（XiaolinWu）教授1982年毕业于武汉大学，1988年获得加拿大卡尔加里大学计算机科学博士学位，现任加拿大麦克马斯特大学电子与计算机工程系终身教授，并担任加拿大NSERC-DALSA数字影院首席科学家。3.5.1算法原理P6P4P2P3P1P5F1F3距离理想直线0.8个像素远的像素亮度为80％距离理想直线0.2个像素远的像素亮度为20％距离理想直线0.45个像素远的像素亮度为45％距离理想直线0.1个像素远的像素亮度为10％距离理想直线0.55个像素远的像素亮度为55％距离理想直线0.9个像素远的像素亮度为90％AB图3-25距离加权反走样算法原理F1F2F3

Wu反走样算法是采用空间混色原理来对走样进行修正。空间混色原理指出，人眼对某一区域颜色的识别是取这个区域颜色的平均值。Wu反走样算法原理是对于理想直线上的任一点，同时以两个不同亮度级别的相邻像素来表示。理想直线段上的点F1，扫描转换后可用像素点P1和像素点P4以不同的亮度级别共同显示，像素点离理想直线段越近，其亮度值越小，像素越暗；像素点离理想直线段越远，其亮度值就越大，像素越亮，但二者的亮度级别之和等于像素F1的灰度值。从图3-25可知，Wu算法是用两个相邻像素来共同表示理想直线段上的一个点，依据两个像素与理想直线段的距离而对其亮度等级进行调整，使所绘制的直线段达到视觉上消除锯齿的效果。实际使用中，两个像素宽度的直线反走样的效果较好，视觉效果上直线的宽度会有所减小，看起来好像是一个像素宽度的直线。3.5.2构造距离误差项

Pi(xi,yi)Fi(xi+1,ei）Pu(xi+1,yi+1)Pd(xi+1,yi)图3-26Wu反走样算法设通过原点的直线方程为y＝kx（3-29）式中，k为直线的斜率，假定0≤k≤1。设理想直线段的当前像素点为Pi(xi,yi)，在主位移x方向上走一步，下一像素点只能在Pu（xi+1，yi+1）和Pd（xi+1，yi）两点中选取，如图3-26所示。

理想直线段与Pu和Pd像素中心连线的交点为Fi。ei为Fi与Pd的距离。设Pd（xi+1，yi）像素的亮度级别为RGB（ei×255，ei×255，ei×255），则Pu（xi+1，yi+1）像素的亮度级别为RGB（（1-ei）×255，（1-ei）×255，（1-ei）×255）。当ei>0.5时，直线更接近于像素点Pu；当ei<0.5时，直线更接近于像素点Pd；当ei=0.5时，直线与Pu、Pd点的距离相等，约定取Pd。

（3-30）误差项ei的初始值为k。主位移方向上每走一步，有ei+1＝ei+k。当ei≥1.0时，相当于y方向上走一步，即yi+1=yi+1，此时将ei减1，即ei+1=ei-1。3.5.3计算机化if(0.0<=k&&k<=1.0)//绘制0≤k≤1{for(p=P0,e=k;p.x<P1.x;p.x++){COLORREFcd=CRGB(e,e,e);//Pd像素颜色COLORREFcu=CRGB((1.0-e),(1.0-e),(1.0-e)););//Pu像素颜色pDC->SetPixelV(Round(p.x),Round(p.y),RGB(cd.red*255,cd.green*255,cd.blue*255));pDC->SetPixelV(Round(p.x),Round(p.y+1),RGB(cu