用C/C++绘制填充椭圆的简单算法

Question

在SO上,找到了以下用于绘制实心圆的简单算法:

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

绘制填充椭圆是否有同样简单的算法？

Answer 1

更简单,没有double和没有除法(但要注意整数溢出):

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        if(x*x*height*height+y*y*width*width <= height*height*width*width)
            setpixel(origin.x+x, origin.y+y);
    }
}

我们可以利用两个事实来显着优化这一点:

• 椭圆具有垂直和水平对称性;
• 当您远离轴线时,椭圆的轮廓越来越倾斜.

第一个事实是节省了四分之三的工作(几乎); 第二个事实极大地减少了测试次数(我们只测试椭圆的边缘,即使在那里我们也不必测试每个点).

int hh = height * height;
int ww = width * width;
int hhww = hh * ww;
int x0 = width;
int dx = 0;

// do the horizontal diameter
for (int x = -width; x <= width; x++)
    setpixel(origin.x + x, origin.y);

// now do both halves at the same time, away from the diameter
for (int y = 1; y <= height; y++)
{
    int x1 = x0 - (dx - 1);  // try slopes of dx - 1 or more
    for ( ; x1 > 0; x1--)
        if (x1*x1*hh + y*y*ww <= hhww)
            break;
    dx = x0 - x1;  // current approximation of the slope
    x0 = x1;

    for (int x = -x0; x <= x0; x++)
    {
        setpixel(origin.x + x, origin.y - y);
        setpixel(origin.x + x, origin.y + y);
    }
}

这是有效的,因为每条扫描线比前一条扫描线短,至少与前一条扫描线相比更短.由于四舍五入到整数像素坐标,这不完全准确 - 线可以比那个短一个像素.

换句话说,从最长扫描线(水平直径)开始,dx在代码中表示的每条线比前一条线短的量减少至多一个,保持相同或增加.第一个内部for找到当前扫描线比前一个扫描线更短的精确数量,从上到下开始dx - 1,直到我们落在椭圆内部.

                       |         x1 dx x0
                       |######    |<-->|
 current scan line --> |###########    |<>|previous dx
previous scan line --> |################  |
two scan lines ago --> |###################
                       |##################### 
                       |###################### 
                       |######################
                       +------------------------

为了比较内椭圆测试的数量,每个星号是在天真版本中测试的一对坐标:

 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************

......并在改进版中:

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **

Answer 2

椭圆(关于原点)是沿x或y轴线性拉伸的圆.所以你可以像这样修改你的循环:

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        double dx = (double)x / (double)width;
        double dy = (double)y / (double)height;
        if(dx*dx+dy*dy <= 1)
            setpixel(origin.x+x, origin.y+y);
    }
}

你可以看到,如果width == height == radius,那么这相当于你绘制圆的代码.

Answer 3

更换

x*x+y*y <= radius*radius

同

Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius

你有三个常数,Axx,Axy,Ayy.当Axy = 0时,椭圆的轴将水平和垂直.Axx = Ayy = 1成一个圆圈.Axx越大,宽度越小.类似于Ayy和身高.对于以任何给定角度倾斜的任意椭圆,需要一些代数来计算常数.

数学Axx,Axy,Ayy是一个"张量",但也许你不想进入那个东西.

更新 - 详细的数学.我不认为SO可以像Math SE那样做出很好的数学运算,所以这看起来很粗糙. 你想用x,y坐标中的椭圆绘制(或做任何事情).椭圆是倾斜的.我们创建了一个与椭圆对齐的替代坐标系x',y'.显然,椭圆上的点满足

(x'/a)^2 + (y'/b)^2 = 1  

通过考虑一些精心挑选的随机点,我们可以看到

x' =  C*x + S*y
y' = -S*x + C*y

其中S,C是sin(θ)和cos(θ),θ是x'轴与x轴的角度.我们可以用符号x =(x,y)来缩短它, 并且类似于引用,R a 2x2矩阵涉及C和S:

x' = R x

可以写出椭圆方程

T(x')A''x' = 1

其中'T'表示转置,并删除'^'以避免戳到眼中的每个人,所以"a2"真的意味着^ 2,

A''=

1/a2     0  
 0     1/b2

使用x' = R x 我们找到

T(R x)A''R x = 1

T(x)T(R)A''R x = 1

T(x)A x = 1

A,你需要知道的事情,使你的倾斜绘图扫描线算法工作,是

A = T(R)A''R =

C2/a2+S2/b2     SC(1/a2-1/b2)
SC/(1/a2-1/b2)  S2/a2 + C2/b2    

根据T(x)A x将它们乘以x和y ,你就得到了它.

Answer 4

如本文所提出的,快速的Bresenham型算法非常有效.这是我为此编写的OpenGL实现.

基本前提是您在一个象限上绘制曲线,我们可以将其镜像到其他三个象限.这些顶点使用误差函数计算,类似于您在圆的中点圆算法中使用的顶点.我上面链接的论文对方程式有一个非常好的证明,并且算法提炼到仅检查给定顶点是否在椭圆内,只需在误差函数中替换它的值.该算法还跟踪我们在第一象限中绘制的曲线的切线斜率,并根据斜率值递增x或y - 这进一步提高了算法的性能.这是一张显示正在发生的事情的图像:

至于填充椭圆,一旦我们知道每个象限中的顶点(基本上是跨越x和y轴的镜像反射),我们为每个计算的顶点得到4个顶点 - 这足以绘制四边形(无论如何都在OpenGL中) .一旦我们为所有这些顶点绘制四边形,我们就得到一个填充的椭圆.由于性能原因,我给出的实现采用VBO,但您并不严格需要它.

该实现还向您展示了如何使用三角形和直线而不是绘制四边形来实现填充椭圆 - 虽然四边形明显更好,因为它是一个基元,我们只为4个顶点绘制一个四边形,而不是每个顶点一个三角形.三角实现.