第3章基本图元的扫描转换 本章学习目标 .了解扫描转换的基本概念。 .掌握绘制像素点函数的用法。 .掌握直线的扫描转换算法。 .熟悉圆的扫描转换算法。 .了解椭圆的扫描转换算法。 .掌握Wu 反走样算法。 直线、圆和椭圆是二维场景中常用的2D 图元。尽管MFC 的CDC 类已经提供了相关的绘 图函数,但直接使用这些成员函数仍然无法完全满足计算机图形学的绘图要求,如对基本图形 进行反走样处理,绘制颜色光滑过渡的直线等。图形的光栅化(n)就是在像素点阵 rasterizatio 中确定最佳逼近于理想图元的像素点集,并用指定颜色显示这些像素点集的过程。当光栅化 与按扫描线顺序绘制图形的过程结合在一起时,也称为扫描转换(scanconversion)。本章从基 本图元的生成原理出发,使用绘制像素点函数研究其扫描转换算法。 3.直线的扫描转换 1 光栅扫描显示器是画点设备,因此不能直接从一像素点到另一像素点绘制一段直线。 直线扫描转换的结果是一组在几何上距离理想直线(daie) ielln最近的离散像素点集。图31中,像素使用放大了很多倍的小圆表示。白色空心圆表示未选择(或称为未点亮)的像素 点,黑色实心圆表示已选择(或称为已点亮)的像素点。假定从像素点 P 开始,向右方递增 一个单位,理想直线与像素网格的交点为Q,如图3-2所示。 Q 点在光栅扫描显示器上是从 上下像素点对(Pu 和Pd )中选择一个来显示的。选择的依据是比较Pu 和Pd 到直线的距 离(用nu 和nd 来表示), 取距离 Q 点最近的像素点来表示 Q 点。观察相似三角形,也可以 使用du 和dd 来近似表示Pu 和Pd 到直线的距离。这里,有du +dd =1,其中,下标“ u ”代 表up,下标“d”代表down 。 图3-1 直线的扫描转换图3-2 选取离直线最近的像素点 计算机图形学要求直线的绘制速度要快,即尽量使用加减法,避免乘、除、开方、三角等 复杂运算。有多种算法可以对直线进行扫描转换,如DDA 算法、Bresenham 算法、中点算 法等。本章重点介绍Bresenham 算法和中点算法。对于直线,中点算法与Bresenham 算法 产生同样的像素点集。 给定直线的起点坐标为P0(x0,y0),终点坐标为P1(x1,y1),用斜截式表示的直线方 程为 y =kx +b (3-1) 其中,直线的斜率为k=Δy Δx=y1-y0 x1-x0,Δx=x1-x0 为水平方向位移,Δy=y1-y0 为垂直 方向位移,b 为y 轴上的截距。 扫描转换算法中,常根据|Δx|和|Δy|的大小来确定绘图的主位移方向。在主位移方 向上执行的是±1操作,另一个方向上是否±1,需要建立误差项来判定。如果|Δx|>|Δy|, 则取x 方向为主位移方向,如图3-3(a)所示;如果|Δx|=|Δy|,取x 方向为主位移方向或 取y 方向为主位移方向皆可,如图3-3(b)所示;如果|Δx|<|Δy|,则取y 方向为主位移方 向,如图3-3(c)所示。 图3-3 主位移方向 除特别声明外,以下给出的直线扫描转换算法是针对斜率满足0≤k≤1的情形,其他 斜率情况下,可以根据直线的对称性类似推导。第一象限包含两个八分象限(octant)。斜 率满足0≤k≤1的情形位于第1个八分象限内,斜率k>1的情形位于第2个八分象限内, 如图3-4所示。 说明:在计算机图形学中,“直线”这个术语表示一段直线,而不是数学意义上两端无限 延伸的直线。 3.1.1 DDA 算法 数值微分法(digitaldifferentialanalyzer,DDA)是用数值方法求解微分方程的一种算 法[19]。式(3-1)的微分表示为 dy dx =k (3-2) 其有限差分近似解为 xi+1 =xi +Δx yi+1 =yi +Δy =yi +kΔx { (3-3) ·73· 图3-4 八分象限示意图 式(3-3)表示直线上的像素点Pi+1与像素点Pi 的递推关系。可以看出,xi+1和yi+1的 值可以根据xi 和yi 的值推算出来,这说明DDA 算法是一种增量算法。在一个迭代算法 中,如果每一步的x,y 值是用前一步的值加上一个增量来获得的,那么,这种算法就称为增 量算法(incrementalalgorithm)。 当直线的斜率满足0≤k≤1时,有Δx≥Δy,所以x 方向为主位移方向。取Δx=1,有 Δy=k。DDA 算法简单表述为 xi+1 =xi +1 yi+1 =yi +k { (3-4) 图3-5中,Pi(xi,yi)为理想直线的起点扫描转换后的像素点。Q (xi+1,yi+k)为理 想直线与下一列垂直网格线的交点。从Pi 像素点出发,沿主位移x 方向上递增一个单位, 下一列上只有1像素点被选择,候选像素点为Pu(xi+1,yi+1)或Pd (xi+1,yi)。最终选 择哪个像素点,可以通过对直线斜率进行圆整计算来决定。 图3-5 DDA算法原理示意图 ·74· 式(3-4)中,x 方向的增量为1,y 方向的增量为k。x 是整型变量,y 和k 是浮点型变 量。DDA 算法使用宏命令ROUND(yi+1)=int(yi+1+0.5),来选择Pd 像素点(yi+1= yi),或者选择Pu 像素点(yi+1=yi +1)。这种圆整计算是为了选择距离直线最近的像素 点,即 yi+1 = yi +1, k ≥0.5 yi, k <0.5 { (3-5) DDA 算法中,斜率涉及浮点数运算,而且对y 取整要花费时间,这不利于硬件实现。为 此Bresenham 提出了一个只使用整数运算就能完成直线绘制的经典算法。 3.1.2 Bresenham 算法 1965年,Bresenham 为数字绘图仪开发了一种绘制直线的算法[20],如图3-6所示。该 算法同样适用于光栅扫描显示器,被称为Bresenham 算法。Bresenham 算法是一个只使用 整数运算的经典算法,能够根据前一个已知坐标(xi,yi)进行增量运算得到下一个坐标 (xi+1,yi+1),而不必进行取整操作。 1.Bresenham 算法原理 Bresenham 算法在主位移方向上每次递增一个单位。另一个方向的增量为0或1,取 决于像素点与理想直线的距离,这一距离称为误差项,用d 表示。 图3-7中,直线位于第一个八分象限内,0≤k≤1,因此x 方向为主位移方向。Pi(xi,yi) 点为当前像素,Q(xi+1,yi+d)为理想直线与下一列垂直网格线的交点。假定直线的起点 为Pi,该点位于网格点上,所以di 的初始值为0。 图3-6 数字化绘图仪画笔运动路径 图3-7 Bresenham 算法原理 沿x 方向递增一个单位,即xi+1=xi+1。下一个候选像素点是Pd (xi+1,yi)或Pu (xi+1,yi+1)。究竟是选择Pu 还是Pd ,取决于交点Q 的位置,而Q 点的位置是由直线 的斜率决定的。Q 点与像素点Pd 的误差项为di+1=k。当di+1<0.5时,像素点Pd 距离 Q 点近,选取Pd ;当di+1>0.5时,像素点Pu 距离Q 点近,选取Pu ;当di+1=0.5时,像素点 Pd 与Pu 到Q 点的距离相等,选取任一像素点均可,约定选取Pu 。 因此 yi+1 = yi +1, di+1 ≥0.5 yi, di+1 <0.5 { (3-6) 算法的关键在于计算递推计算误差项di。从d0=0开始,沿x 方向递增一个单位,有 ·75· di+1=di+k。一旦di+1≥0,y 方向上走了一步,就将d 减去1。由于只需要检查误差项的 符号,令ei+1=di+1-0.5,以消除小数的影响。式(3-6)改写为 yi+1 = yi +1,ei+1 ≥0 yi, ei+1 <0 { (3-7) 取e 的初始值为e0=-0.5。沿x 方向每递增一个单位,有ei+1=ei +k。当ei+1≥0 时,下一像素点更新为(xi+1,yi+1),同时将ei+1更新为ei+1-1;否则,下一像素点更新为 (xi+1,yi)。 2.整数Bresenham 算法原理 虽然当前点的x 坐标和y 坐标均使用了加1或减1的整数运算,但是在递推计算直线 误差项e 时,仍然使用了浮点型变量k,除法也参与了运算。按照Bresenham 的说法,使用 整数运算可以加快算法的速度。应对算法进行修正,以避免除法运算。由于Bresenham 算 法中只用到误差项的符号,而Δx 在第一个八分象限内恒为正,可以进行如下替换e=2Δx× e。改进的整数Bresenham算法如下: e 的初值为e0=-Δx,沿x 方向每递增一个单位,有ei+1=ei+2Δy。当ei+1≥0时,下 一像素点更新为(xi+1,yi +1),同时将ei+1更新为ei+1-2Δx;否则,下一像素点更新为 (xi+1,yi)。 3.通用整数Bresenham 算法原理 以上整数Bresenham 算法绘制的是第一个八分象限内的直线。在绘制图形时,要求编 程实现能绘制任意斜率的通用直线。根据对称性,可以设计通用整数Bresenham 算法。 图3-8中,x 和y 是加1还是减1,取决于直线所在的象限。例如,对于第一个八分象限 (0≤k≤1),x 方向为主位移方向。Bresenham 算法的原理为x 每次加1,y 根据误差项决 定是加1或者加0;对于第二个八分象限,y 方向为主位移方向。Bresenham 算法的原理为 y 每次加1,x 是否加1需要使用误差项来判断。使用通用整数Bresenham 算法绘制从原 点发出的360条射线,效果如图3-9所示。 图3-8 通用整数Bresenham 算法判别条件 图3-9 直线算法的校核图 3.1.3 中点算法 1967年Pitteway等提出了一个中点算法[21]。1984年,Aken等对中点算法进行了改 ·76· 进[22]。中点算法是基于隐函数方程设计的,使用像素网格中点来判断如何选取距离理想直 线最近的像素点。 1. 中点算法原理 每次沿主位移方向上递增一个单位,另一个方向上增量为1或0,取决于中点误差项 的值。由 式(3-1)得到理想直线的隐函数方程为 F(x,(8) y)=y-k-b=03 理想直线将平面划分成三个区域:对于直线上(x) 的点,F(x,y)=0;对于直线上方的点, F(x,对于直线下方的点,F(y)<0 。 y)>0; x, 考查斜率位于第一个八分象限内的理想直线。假定直线上的当前像素点为Pi(xi,i), yQ 点是直线与网格线的交点。沿着主位移 x 方向上递增一个单位,即执行xi+1=xi+1,下 一像素点将从Pu (yi+1) xi+1,两个候选像素点中选取。连接像素点Pu xi+1,和Pd (yi) 和像素点Pd 的网格中点为 M (xi+1,5), 如图3-10 所示。显然,若中点 M 位于理想 yi+0. 直线的下方,则像素点Pu 距离直线近;否则,像素点Pd 距离直线近。 图3-10 直线中点算法原理 2. 构造中点误差项 从Pi(xi,像素点出发,沿主位移方向选取直线上的下一像素点时,需要将连接Pu yi) 和Pd 两个候选像素点连线的网格中点 M 代入隐函数方程(3-8), 构造中点误差项 d di=F(xi+1,5)=5-k(-(39) yi+0.yi+0.xi+1)b 当di<0 时,中点 M 位于直线的下方,像素点Pu 距离直线近,下一像素点应选取Pu , 即 y 方向上增量为1;当di>0 时,中点 M 位于直线的上方,像素点Pd 距离直线近,下一像 素点应选取Pd ,即 y 方向上增量为0;当di =0时,中点 M 位于直线上,像素点Pu 、Pd 与 直线的距离相等,选取任一像素点均可,约定选取Pd ,如图3-11 所示。 图3-11 中点算法分析 ·77· 因此 yi+1 = yi +1, di <0 yi, di ≥0 { (3-10) 3.中点误差项的递推 图3-11中,根据当前像素点Pi 确定下一像素点是选取Pu 还是选取Pd 时,使用了中 点误差项d 进行判断。为了能够继续光栅化直线上的后续像素点,需要给出中点误差项的 递推公式。 在主位移x 方向上已递增一个单位的情况下,考虑沿x 方向再递增一个单位,应该选 择哪个网格中点来计算误差项,分两种情况讨论。 当di<0时,下一步进行判断的中点为Mu(xi+2,yi+1.5),如图3-12(a)所示。中点 误差项的递推公式为 di+1 =F(xi +2,yi +1.5)=yi +1.5-k(xi +2)-b =yi +0.5-k(xi +1)-b+1-k =di +1-k (3-11) 所以,中点误差项的增量为1-k。 当di≥0时,下一步进行判断的中点为Md (xi+2,yi+0.5),如图3-12(b)所示。中点 误差项的递推公式为 di+1 =F(xi +2,yi +0.5)=yi +0.5-k(xi +2)-b =yi +0.5-k(xi +1)-b-k =di -k (3-12) 所以,中点误差项的增量为-k。 图3-12 中点的递推 4.中点误差项的初始值 直线的起点坐标扫描转换后的像素点为P0(x0,y0)。从像素点P0 出发沿主位移x 方 向递增一个单位,第一个参与判断的中点是M (x0+1,y0+0.5)。代入中点误差项计算公 式(3-9),d 的初始值为 d0 =F(x0 +1,y0 +0.5)=y0 +0.5-k(x0 +1)-b =y0 -kx0 -b-k +0.5 其中,因为像素点P0(x0,y0)位于直线上,所以y0-kx0-b=0,则 d0 =0.5-k (3-13) ·78· 5 . 中点算法整数化 上述的中点算法有一个缺点:在计算中点误差项 d 时,其初始值与递推公式中分别包 含有小数0.5和斜率k。由于中点算法只用到 d 的符号,可以使用正整数2Δx 乘以 d 来摆 脱小数运算。 ei=2Δxdi 整数化处理后,中点误差项的初始值为 e0=Δx-2Δy (3-14) 当ei<0 时,中点误差项的递推公式为 (ei+1=ei+2Δx-2Δy 3-15) 所以,中点误差项的增量为2Δx-2Δy。 当ei≥0 时,表示选择Pd ,中点误差项的递推公式为 所以,中点误差项的增量为-2Δy。 ei+1=ei-2Δy (3-16) 20 世纪70 年代,由于计算机运算速度受限,完全整数的光栅化算法是计算机图形学研 究者追求的一个目标。现有的研究成果已经证明:端点采用整数坐标没有什么益处,因为 现在的CPU 可以按照与处理整数同样的速度处理浮点数。 例3- 1 绘制起点为红色,终点为蓝色的颜色渐变直线。 如果直线上每像素点的颜色由两个端点的颜色经过线性插值得到,则可以实现直线颜色 的光滑渐变。假设直线位于第一个八分象限内,基于整数中点算法开发颜色渐变直线算法。 RGB 宏有红色分量byteR、绿色分量byteG和蓝色分量byteB。每个分量占1字节,数 值范围为0~255 。编程时,常将颜色分量规范化到[0,1]闭区间,使用时乘以255 即可。这 样,红色对应的颜色为(1,0,0), 绿色对应的颜色为(0,1,0)。蓝色对应的颜色为(0,0,1)。 注意,沿主位移方向,当 x 坐标从x0 执行加1操作到达x1 时,byteR分量从1减小到0, byteG分量保持不变,byteB分量从0增加到1。令Δx=x1-x0,则byteR的步长增量 incrR为-1/Δx,绿色分量的步长增量incrG为0,蓝色分量的步长增量incrB为1/Δx。 由于颜色分量的运算包含浮点数运算,所以使用直线的浮点数中点算法来编程实现。 3.圆的扫描转换 2 圆的扫描转换是在屏幕像素点阵中确定最佳逼近于理想圆的像素点集的过程。绘制圆 可以使用简单方程画圆算法或极坐标画圆算法,但这些算法涉及开方运算或三角运算,效率 很低。1977 年,Bresenham 开发了一种绘制圆弧算法[23],假设笔式绘图仪递增地沿着圆弧 前进,能为圆心在原点的圆产生所有像素点。这里介绍一种运用中点准则推导的中点画圆 算法,它也能产生一组优化的像素。中点画圆算法本质上与Bresenham 绘制圆弧算法一 致,但更容易理解。本节主要讲解仅包含加减运算的顺时针绘制圆弧的中点算法,根据对称 性可以绘制整圆。 3.1 简单方程画圆算法 2. 1. 直角坐标算法 圆心位于原点,半径为 R 的圆的直角坐标方程为 ·79· x2 +y2 =R2 (3-17) 可以解得y=f(x)的表达式为 y =± R2 -x2 (3-18) 当x 从0逐像素递增到R 时,根据式(3-18)可以计算出每一步的y,从而顺时针绘制 出第一象限内的1/4圆弧,效果如图3-13(a)所示。注意,当x 靠近R (图中取R =20)时, 圆上的像素会有较大的间断,因为圆的斜率在此处变得无穷大。 2.极坐标算法 圆心位于原点,半径为R 的圆的极坐标方程为 x =Rcosθ y =Rsinθ { (3-19) 当θ 从0°一度一度地递增到90°时,根据式(3-19)可以计算出每一步的x 和y,从而逆 时针绘制出第一象限内的1/4圆弧,效果如图3-13(b)所示。极坐标画圆算法与直角坐标 方程算法相比,该方法避免像素出现大的间断。 图3-13 简单方程画圆弧效果图 3.2.2 中点画圆算法 1.八分圆弧 圆心位于原点、半径为R 的圆的隐函数方程为 F(x,y)=x2 +y2 -R2 =0 (3-20) 圆将平面划分成3个区域:对于圆上的点,F(x,y)=0;对于圆外的点,F(x,y)>0;对 于圆内的点,F(x,y)<0,如图3-14所示。 根据圆的对称性,可以用4条对称轴x=0,y=0,x=y,x=-y 将圆划分8等份,如 图3-15所示。只要绘制出第一象限内编号为②的八分圆弧(以下简称为圆弧),根据对称 性就可以生成其他7个八分圆弧,这称为八分法画圆算法。假定圆弧②上的任意点为 (x,y),可以顺时针方向确定另外7个点:(y,x)、(y,-x)、(x,-y)、(-x,-y)、(-y,-x)、 (-y,x)、(-x,y)。 2.中点算法原理 从图3-15中所示的圆弧②可以看出,y 是x 的单调递减函数。假设圆弧起点x=0, y=R 精确地落在像素点上,中点算法要从x=0绘制到x=y,顺时针方向确定最佳逼近于 圆弧的像素点集。此段圆弧上各个点的切线斜率k 处处满足|k|<1,即|Δx|>|Δy|,所以 ·80· 图3-14 圆的扫描转换 x 方向为主位移方向。中点算法原理表述为:x 方向上每次加1,y 方向上减不减1取决于 中点误差项的值。 假定圆弧上当前像素点是Pi(xi,yi),Q 点是圆弧与网格线的交点。下一像素点将从 Pu(xi+1,yi)和Pd (xi+1,yi-1)两个候选像素点中选取,如图3-16所示。连接像素点 Pu 和像素点Pd 的网格中点为M (xi+1,yi-0.5)。显然,若M 点位于理想圆弧的下方,则 像素点Pu 离圆弧近;若M 点位于理想圆弧的上方,则像素点Pd 离圆弧近。 图3-15 圆的对称性 图3-16 圆的中点算法原理 3.构造中点误差项 从Pi(xi,yi)像素出发选取下一像素点时,需将Pu 和Pd 两个候选像素点连线的网格 中点M (xi+1,yi-0.5)代入隐函数方程,构造中点误差项di di =F(xi +1,yi -0.5)=(xi +1)2 + (yi -0.5)2 -R2 (3-21) 当di<0时,中点M 位于圆弧内,下一像素点应选取Pu ,即y 方向上不减1;当di>0时, 中点M 位于圆弧外,下一像素点应选取Pd ,即y 方向上减1;当di=0时,中点M 位于圆弧 上,像素点Pu 、Pd 与圆弧的距离相等,选取任一像素点均可,约定选取Pd ,如图3-17所示。 因此 yi+1 = yi, di <0 yi -1, di ≥0 { (3-22) ·81· 图3-17 中点算法分析 4. 递推公式 图3-17 中,根据当前点Pi 确定了下一像素是选取Pu 还是Pd 时,使用了中点误差项 di。为了能够继续判断圆弧上的后续像素点,需要给出中点误差项的递推公式和初始值。 1)中点误差项的递推公式 在主位移 x 方向上已递增一个单位的情况下,考虑沿主位移方向上再递增一个单位, 应该选择哪个中点来计算误差项,以判断下一步要选取的像素,分两种情况讨论。 当di<0 时,下一步的中点坐标为Mu (yi-5), 如图3所示。中点误差 xi+2,0.-18(a) 项的递推公式为 2 xi+2,5)=(xi+2)2+ (5)-R2 di+1=F(yi-0.yi-0. 2 =xi+1)5)xi+3=xi+3 (2+ (yi-0.-R2+2di+2(323) 图3-18 中点的递推 yi-5), 当di≥0 时,下一步的中点坐标为Md (xi+2,1.如图3-18(b)所示。中点误差 项的递推公式为 2 xi+2,5)=(2+ (5)-R2 yi-0.2-2 di+1=F(yi-1.xi+2)yi-1. 2+ ( =(xi+1)5)-R2+2xi+3+ (yi+2) =di+2(xi-yi)+5 (3-24) 2)中点误差项的初始值 圆弧的起点扫描转换后的像素为P0(0,R)。若沿主位移 x 方向递增一个单位,第一个 参与判断的中点为 M (1,R-0.相应的中点误差项 d 的初始值为 5), 2 d0=F(1,5)=1+ (5)-R2=25- R ( R-0.R-0.1.325) ·82· 5. 整数中点画圆算法 由于使用的只是 d 的符号,可以通过一些简单的变换来摆脱小数。定义ei=di-0. 25, 初始值d0= R 对应于e0=R。误差项di<0 对应于e25 。由于e始终是 1.25-1-i<-0. i<-0.20 整数,可以将e25 等价为ei<0 。基于整数中点画圆算法扫描转换R=的圆,(i) 放大 效果如图3-19 所示。 图3-19 中点画圆算法扫描转换效果图 3.椭圆的扫描转换 3 椭圆的扫描转换是在屏幕像素点阵中选取最佳逼近于理想椭圆的像素点集的过程。椭 圆是长半轴与短半轴不相等的圆。椭圆的扫描转换与圆的扫描转换有相似之处,但也有不 同,主要区别是椭圆弧上存在改变主位移方向的临界点[22]。本节主要讲解顺时针绘制四分 椭圆弧的中点算法,根据对称性可以绘制完整椭圆。 1. 四分椭圆弧 中心在原点、长半轴为a、短半轴为 b 的轴对称椭圆方程为 x2 y2 a2 +b2 =1 (3-26) 隐函数表示为 F(x,=b2x2+a2y2-a2b2=( y)0 327) 椭圆将平面划分成3个区域:对于椭圆上的点,F(y)0;对于椭圆外的点,x,> 0;对于椭圆内的点,F(x,如图320 所示。 x,=F(y) y)<0, 图3-20 椭圆的扫描转换·83· 考虑到椭圆的对称性,可以用对称轴x=0,y=0,将椭圆四等分。只要绘制出第一象 限内的四分椭圆弧(以下简称为椭圆弧), 如图3-21 阴影区域所示,根据对称性就可以生成 其他3个椭圆弧,这称为四分法画椭圆算法。已知第一象限内的一点(y), - y --y)-yx,可以顺时针确 定另外3个对称点:(x,)、(x,和(x,)。 2. 临界点分析 在处理第一象限的四分椭圆弧时,进一步以法向量(normalvector)的两个分量相等的 点把其划分为两个区域:区域Ⅰ和区域Ⅱ,该点称为临界点,如图3-22 所示。特别地,在临 界点处,曲线的斜率为-1。相比圆的绘制,椭圆弧需要计算临界点的位置。椭圆上任一点 y) y)(x,处的法向量 N (x, N 为 (x,. F .Fb2( y) = .xi+.yj=2xi+2a2yj 3-28) 式中,法向量的 x 方向的分量为Nx =b2法向量的 y 方向的分量为Ny =a2i 和 j 是 沿 x 轴向和沿 y 轴向的标准单位向量 2 。 x,2y, 图3-21 椭圆的对称性图3-22 椭圆的临界点 从曲线上一点的法向量角度看,在区域Ⅰ内,Nx Ny 。显然,在临界点处,法向量分量的大小发生了变化。 从曲线上的斜率角度看,在临界点处,dy=-1。区域Ⅰ内,有dy>-1,即dx>dy,所 dx dx 以 x 方向为主位移方向;在临界点处,有dx=dy;在区域Ⅱ内,有dy<-1,即dy>dx,所以 y 方向为主位移方向。显然,在临界点处,主位移方向发生了改变 d 。 x 3. 中点算法原理 在区域Ⅰ, x 方向上每次递增一个单位, y 方向上减1或减0取决于中点误差项的值; 在区域Ⅱ, x 方向上加1或加0取决于中点误差项的值。 y 方向上每次递减一个单位1, 先考虑图3-23 所示区域Ⅰ的AC 段椭圆弧。此时中点算法要从起点A(b) a2/b2/a0,到临界点 C(a2+b2,2+b2)顺时针方向确定最佳逼近于该段椭圆弧的像素点集。由于 x xi,xi +1,yi) 方向为主位移方向,假定当前点是Pi(yi), 下一步将从正右方的像素Pu (和 右下方的像素Pd (xi+1,1)两个候选像素中选取。 b2/顺时针方向确定最佳逼近于该段椭圆弧的像素点 集。由于 y 方向为主位移方向,假定当前点是Pi (xi,yi ), 下一步将从正下方的像素Pl ·84· yi 再考虑图3-23 所示区域Ⅱ的CB 段椭圆弧。此时中点画椭圆算法要从临界点C(a2/ a2+b2,a2+b2)到终点B(a,0) (xi,yi-1)和右下方的像素Pr (xi+1,yi-1)两个候选像素中选取。这里,下标“l”代表 left,下标“r”代表right。 图3-23 椭圆弧的中点算法原理 4.构造区域Ⅰ的中点误差项 从当前点Pi 出发选取下一像素时,需将Pu 和Pd 两个候选像素连线的网格中点M (xi+1,yi-0.5)代入隐函数方程,构造中点误差项d1i d1i =F(xi +1,yi -0.5)=b2 (xi +1)2 +a2 (yi -0.5)2 -a2b2 (3-29) 当d1i<0时,中点M 位于椭圆弧内,下一像素应选取Pu ,即y 方向上不减1;当d1i>0 时,中点M 位于椭圆弧外,下一像素应选取Pd ,即y 方向上减1;当d1i=0时,中点M 位于 椭圆上,像素Pu 和Pd 与椭圆弧的距离相等,选取任一像素均可,约定选取Pd ,如图3-24 所示。 图3-24 区域Ⅰ内像素点的选取 因此 yi+1 = yi, d1i <0 yi -1, d1i ≥0 { (3-30) 5.区域Ⅰ内中点误差项的递推 图3-24中,根据当前点Pi 选取Pu 还是Pd ,使用了中点误差项d1i。为了能够继续选 取椭圆弧上的后续像素,需要给出中点误差项d1i的递推公式和初始值。 1)中点误差项d1 的递推公式 在主位移x 方向上已递增一个单位的情况下,考虑沿主位移方向再递增一个单位,应 该选取哪个中点来计算误差项,以判断下一步要选取的像素,分两种情况讨论。 当d1i<0时,下一步的中点坐标为Mu(xi+2,yi-0.5),如图3-25(a)所示。中点误差 ·85· 项的递推公式为 d1(i+1)=F(xi +2,yi -0.5)=b2 (xi +2)2 +a2 (yi -0.5)2 -a2b2 =b2 (xi +1)2 +a2 (yi -0.5)2 -a2b2 +b2(2xi +3) =d1i +b2(2xi +3) (3-31) 当d1i≥0时,下一步的中点坐标为Md (xi+2,yi-1.5),如图3-25(b)所示。中点误差 项的递推公式为 d1(i+1)=F(xi +2,yi -1.5)=b2 (xi +2)2 +a2 (yi -1.5)2 -a2b2 =b2 (xi +1)2 +a2 (yi -0.5)2 -a2b2 +b2(2xi +3)+a2(-2yi +2) =d1i +b2(2xi +3)+a2(-2yi +2) (3-32) 图3-25 区域Ⅰ内中点的递推 2)中点误差项d1i的初始值 在区域Ⅰ内,椭圆弧的起点扫描转换后的像素为P0(0,b)。沿主位移x 方向递增一个 单位,第一个参与判断的中点是M (1,b-0.5),相应的中点误差项d1i的初始值为 d10 =F(1,b-0.5)=b2 +a2 (b-0.5)2 -a2b2 =b2 +a2(-b+0.25) (3-33) 6.构造区域Ⅱ的中点误差项 在区域Ⅱ内,主位移方向发生变化,由x 方向转变为y 方向。从区域Ⅰ椭圆弧的终止 点Pi(xi,yi)出发选取下一像素时,需将Pl(xi,yi-1)和Pr(xi+1,yi-1)的中点M (xi+ 0.5,yi-1)代入隐函数方程,构造中点误差项d2i d2i =F(xi +0.5,yi -1)=b2 (xi +0.5)2 +a2 (yi -1)2 -a2b2 (3-34) 当d2i<0时,中点M 位于椭圆弧内,下一像素点应选取Pr,即x 方向上加1;当d2i>0 时,中点M 位于椭圆弧外,下一像素点应选取Pl,即x 方向上不加1;当d2i=0时,中点M 位于椭圆弧上,Pl、Pr 与椭圆弧的距离相等,选取任一像素均可,约定选取Pl,如图3-26 所示。因 此 xi+1 = xi +1, d2i <0 xi, d2i ≥0 { (3-35) 7.区域Ⅱ内中点误差项的递推 图3-26中,根据Pi 确定下一像素点是选取Pl 还是Pr 时,使用了中点误差项d2i。为 了能够继续选取椭圆弧上的后续像素,需要给出中点误差项d2i的递推公式和初始值。 ·86· 图3-26 下半部分像素点的选取 1)中点误差项d2 的递推公式 在主位移 y 方向上已递增一个单位的情况下,考虑沿主位移方向上再递增一个单位, 应该选择哪个中点来计算误差项,以判断下一步要选取的像素,分两种情况讨论。 当d2i<0 时,下一步的中点坐标为Mr(5,2), 如图3a)所示。中点误差 xi+1.yi--27( 项的递推公式为 2 F(5,5)-a2b2 d2(xi+1.=xi+1.yi-2) i+1)=yi-2)b2(2+a2( 2 2+a2(b2+b2( b2(5)a2xi+2)+a2( =xi+0.yi-1)-2-2yi+3) =d2i+b2(2xi+2)+a2(-2yi+3) (3-36) 当d2i≥0 时, xi +0.yi-2), -b) 下一步的中点坐标为Ml(5,如图327(所示。中点误差 项的递推公式为 2 5,b2(xi+0.2+a2(a2b2 d2(i+1)=F(xi+0.yi-2)=5)yi-2) 2 b2(2+a2(b2+a2( =xi+0.5)yi-1)-a2-2yi+3) =d2i+a2(-2yi+3) (3-37) 图3-27 区域Ⅱ内中点的递推 2)中点误差项d2 的初始值 0.对于区域Ⅰ内椭圆弧上一点Pi(xi,yi), 如果在当前中点 M Ⅰ(xi +1,yi -5)处,假 -yi) xi +1,yi -0. 定图328 中Pi(xi,点为区域Ⅰ内椭圆弧上的最后一像素, M Ⅰ(5)是Pu 和Pd 像素的中点。满足法向量的 x 方向分量小于法向量的 y 方向分量 b2(xi+1)