椭圆的扫描转换-中点Bresenham算法

椭圆的扫描转换是在屏幕像素点阵中选取最佳逼近于理想椭圆像素点集的过程。椭圆是长半轴和短半轴不相等的圆，椭圆的扫描转换与圆的扫描转换有类似之处。本节主要讲解顺时针绘制1/4椭圆的中点Bresenham算法原理，根据对称性可以绘制完整椭圆。

默认的椭圆是圆心位于坐标系原点，长半轴为a、短半轴为b的椭圆 。需要进行圆心平移或使用自定义坐标系可以绘制椭圆。
如果“x方向上每次加1，y方向上减不减1取决于中点误差项的值”。绘制结果是圆，如何能绘制为椭圆？

算法原理

圆心在原点、长半轴为a、短半轴为b的椭圆方程的隐函数表达式为 ：
F(x,y)=b2x2+a2y2−a2b2=0$F(x,y)=b^2{x}^2+a^2{y}^2-a^2{b}^2=0$
椭圆将平面划分成三个区域：对于椭圆上的点，F(x，y)＝0；对于椭圆外的点，F（x，y）＞0；对于椭圆内的点，F（x，y）＜0。

考虑到椭圆的对称性，可以用对称轴x＝0，y＝0，把椭圆分成4等份。只要绘制出第一象限内的1/4椭圆弧，根据对称性就可绘制出整个椭圆，这称为四分法绘制椭圆算法。已知第一象限内的点P(x,y)，可以顺时针得到另外3个对称点：P(x,-y)，P(-x,-y)和P(-x,y)。

N(x,y)=∂F∂xi+∂F∂yj=2b2xi+2a2yj$N(x,y)=\frac{\mathrm{\partial }F}{\mathrm{\partial }x}i+\frac{\mathrm{\partial }F}{\mathrm{\partial }y}j=2b^{2}xi+2a^{2}yj$
部分Ⅰ的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方向为主位移方向。
在部分Ⅰ椭圆的中点Bresenham的原理:每次在主位移x方向上走一步，y方向上退不退步取决于中点误差项的值。在部分Ⅱ：每次在主位移方向y上退一步，x方向上走不走步取决于中点误差项的值。

构造上半部分Ⅰ的中点误差项

在上半部分Ⅰ，x方向每次加1，y方向上减不减1取决于中点误差项的值。从Pi(xi,yi)$P_i(x_i,y_i)$点出发选取下一像素时，需将Pu(xi+1，yi)$P_u(x_i+1，y_i)$和Pd(xi+1,yi−1)$P_d(x_i+1,y_i-1)$的中点M(xi+1,yi−0.5)$M(x_i+1,y_i-0.5)$代入隐函数，构造中点误差项：
d1i=F(xi+1,yi−0.5)=b2(xi+1)2+a2(yi−0.5)2−a2b2$d_{1i}=F(x_i+1,y_i-0.5)=b^2(x_i+1{)}^2+a^2(y_i-0.5{)}^2-a^2{b}^2$

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

yi+1={yi,yi−1,d1i<0d1i≥0$$y_{i+1}=\{\begin{array}{ll}{y}_i,& d_{1i}<0\\ y_i-1,& d_{1i}\ge 0\end{array}$$

上半部分Ⅰ的递推公式

如果考虑主位移方向再走一步，应该选择哪个中点代入中点误差项以决定下一步应该选取的像素，分两种情况讨论。

1. 当d1i<0时，下一步的中点坐标为M(xi+2，yi−0.5)，下一步中点误差项为$当d_{1i}<0时，下一步的中点坐标为M(x_i+2，y_i-0.5)，下一步中点误差项为$
   d1(i+1)=F(xi+2,yi−0.5)=b2(xi+2)2+a2(yi−0.5)2−a2b2$d_{1(i+1)}=F(x_i+2,y_i-0.5)=b^2(x_i+2{)}^2+a^2(y_i-0.5{)}^2-a^2{b}^2$
   =b2(xi+1)2+a2(yi−0.5)2−a2b2+b2(2xi+3)$=b^2(x_i+1{)}^2+a^2(y_i-0.5{)}^2-a^2{b}^2+b^2(2x_i+3)$
   =d1i+b2(2xi+3)$=d_{1i}+b^2(2x_i+3)$
2. 当d1i≥0时，下一步的中点坐标为M(xi+2，yi−1.5)，下一步中点误差项为$当d_{1i}\ge 0时，下一步的中点坐标为M(x_i+2，y_i-1.5)，下一步中点误差项为$
   d1(i+1)=F(xi+2,yi−1.5)=b2(xi+2)2+a2(yi−1.5)2−a2b2$d_{1(i+1)}=F(x_i+2,y_i-1.5)=b^2(x_i+2{)}^2+a^2(y_i-1.5{)}^2-a^2{b}^2$
   =b2(xi+1)2+a2(yi−0.5)2−a2b2+b2(2xi+3)+a2(−2yi+2)$=b^2(x_i+1{)}^2+a^2(y_i-0.5{)}^2-a^2{b}^2+b^2(2x_i+3)+a^2(-2y_i+2)$

中点误差项的初始值

上半部分椭圆的起点为A（0，b），因此，第一个中点是（1，b－0.5），对应的d1i$d_{1i}$的初值为
d10=F(1,b−0.5)=b2+a2(b−0.5)−a2b2=b2+a2(−b+0.25)$d_{10}=F(1,b-0.5)=b^2+a^2(b-0.5)-a^2{b}^2=b^2+a^2(-b+0.25)$

构造下半部分Ⅱ的中点误差项

在下半部分Ⅱ，主位移方向发生变化，中点Bresenham算法原理为：y方向上每次减1，x方向上加1不加1取决于中点误差项的值。从上半部分Ⅰ的终止点Pi(xi,yi)$P_i(x_i,y_i)$出发选取下一像素时，需将Pl(xi,yi−1)$P_l(x_i,y_i-1)$和Pr(xi+1,yi−1)$P_r(x_i+1,y_i-1)$的中点M(xi+0.5,yi−1)$M(x_i+0.5,y_i-1)$代入隐函数，构造中点误差项
d2i=F(xi+0.5,yi−1)=b2(xi+0.5)2+a2(yi−1)2−a2b2$d_{2i}=F(x_i+0.5,y_i-1)=b^2(x_i+0.5{)}^2+a^2(y_i-1{)}^2-a^2{b}^2$

当d2i<0$d_{2i}<0$时，中点M在椭圆内，下一像素点应选取Pr$P_r$，即x方向上走一步；当d2i>0$d_{2i}>0$时，中点M在椭圆外，下一像素点应选取Pl$P_l$，即x方向上不走步；当d2i＝0$d_{2i}＝0$时，中点M在椭圆上，Pl、Pr$P_l、P_r$和椭圆的距离相等，选取Pl$P_l$或Pr$P_r$均可，约定取Pl$P_l$。 （l代表left，左面的像素；r代表right，右面的像素）

下半部分Ⅱ的递推公式

现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点误差项以决定应该选取的像素。分两种情况讨论。

1. 当d2i<0时，下一步的中点坐标为M(xi+1.5，yi−2)，下一步中点误差项为$当d_{2i}<0时，下一步的中点坐标为M(x_i+1.5，y_i-2)，下一步中点误差项为$
   d2(i+1)=F(xi+1.5，yi−2)=b2(xi+1.5)2+a2(yi−2)2−a2b2$d_{2(i+1)}=F(x_i+1.5，y_i-2)=b^2(x_i+1.5{)}^2+a^2(y_i-2{)}^2-a^2{b}^2$
   =b2(xi+0.5)2+a2(yi−1)2−a2b2+b2(2xi+2)+a2(−2yi+3)$=b^2(x_i+0.5{)}^2+a^2(y_i-1{)}^2-a^2{b}^2+b^2(2x_i+2)+a^2(-2y_i+3)$
   =d2i+b2(2xi+2)+a2(−2yi+3)$=d_{2i}+b^2(2x_i+2)+a^2(-2y_i+3)$
2. 当d2i≥0时，下一步的中点坐标为M(xi+0.5，yi−2)，下一步中点误差项为$当d_{2i}\ge 0时，下一步的中点坐标为M(x_i+0.5，y_i-2)，下一步中点误差项为$
   d2(i+1)=F(xi+0.5，yi−2)=b2(xi+0.5)2+a2(yi−2)2−a2b2$d_{2(i+1)}=F(x_i+0.5，y_i-2)=b^2(x_i+0.5{)}^2+a^2(y_i-2{)}^2-a^2{b}^2$
   =b2(xi+0.5)2+a2(yi−1)2−a2b2+a2(−2yi+3)$=b^2(x_i+0.5{)}^2+a^2(y_i-1{)}^2-a^2{b}^2+a^2(-2y_i+3)$
   =d2i+a2(−2yi+3)$=d_{2i}+a^2(-2y_i+3)$

中点误差项的初始值

在上半部分Ⅰ，法矢量的x向分量小于y向分量；在C点，法矢量的x向分量等于y向分量；在下半部分Ⅱ，法矢量的x向分量大于y向分量。则对于上半部分椭圆上一点P(xi，yi)$P(x_i，y_i)$，如果其当前中点M(xi+1,yi−0.5)$M(x_i+1,y_i-0.5)$，满足x向分量小于y向分量
b2(xi+1)2<a2(yi−0.5)2$b^2(x_i+1{)}^2<a^2(y_i-0.5{)}^2$
而在下一个中点，不等号改变方向，则说明椭圆从上半部分Ⅰ转入了下半部分Ⅱ。

假定Pi(xi,yi)$P_i(x_i,y_i)$点是椭圆上半部分Ⅰ的最后一个像素，MⅠ(xi+1,yi−0.5)$MⅠ(x_i+1,y_i-0.5)$是用于判断选取Pu$P_u$和Pd$P_d$像素的中点。由于下一像素转入了下半部分Ⅱ，其中点改为判断Pl$P_l$和Pr$P_r$的中点MⅡ(xi+0.5,yi−1)$MⅡ(x_i+0.5,y_i-1)$，所以下半部分的初值d₂₀为
d20=b2(x+0.5)2+a2(y−1)2−a2b2$d_{20}=b^2(x+0.5{)}^2+a^2(y-1{)}^2-a^2{b}^2$

double x,y,d1,d2,a,b;
a=fabs(p1.x-p0.x)/2;
b=fabs(p1.y-p0.y)/2;
x=0;y=b;
d1=b*b+a*a*(-b+0.25);
EllipsePoint(x,y,pDC);
//椭圆AC弧段
while(b*b*(x+1)<a*a*(y-0.5))
{
    if (d1<0)
    {
        d1+=b*b*(2*x+3);
    }
    else
    {
        d1+=b*b*(2*x+3)+a*a*(-2*y+2);
        y--;
    }
    x++;
    EllipsePoint(x,y,pDC);
}
//椭圆CB弧段
d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;
while(y>0)
{
    if (d2<0)
    {
        d2+=b*b*(2*x+2)+a*a*(-2*y+3);
        x++;
    }
    else
    {
        d2+=a*a*(-2*y+3);
    }
    y--;
    EllipsePoint(x,y,pDC);
}