logo标签列表

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

c++calgorithmgraphics
15

在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);

有没有同样简单的算法来绘制填充椭圆？

2
请查看这个问题：http://math.stackexchange.com/questions/5799/how-do-i-determine-if-a-point-is-interior-to-an-elliptical-cone - Greg Hewgill
@Mark 但是它仍然会丢失像素。 - Konrad Rudolph
你只需要完全水平和垂直轴的省略号，还是你想要绘制一些任意角度的省略号？ - DarenW
1
@DarenW：我的特定项目是在嵌入式设备上呈现月相。我通过渲染半个圆和半个椭圆来实现这一点。如果我有一个可以绘制任意角度椭圆的算法，我就可以更接近地呈现从给定纬度看到的月亮。 - Roger Dahl
这种方法的问题在于它不能捕捉到与圆的实际周长重叠的每个像素。x和y对应于像素的中点，如果周长低于某个坐标但在相应像素的下半部分切割，则会忽略这些像素。您需要类似Bresenham算法的东西。请参考@Prathap答案中的论文。 - picmate 涅
显示剩余2条评论
4个回答
21

更简单，没有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 ，最多减少1个像素，保持不变或增加。第一个内部循环找到当前扫描线比前一条扫描线短的准确数量，从dx-1开始递减，直到我们刚好落在椭圆内部。

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

为了比较椭圆内部测试的数量，每个星号代表在朴素版本中测试的一对坐标：

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

...在改进版本中：

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **
谢谢您的改进。您能否通过将dx和dy更改为x和y来修复代码？ - Roger Dahl
2
哦，如果你想要性能，你可以从0到高度运行y，并在内部循环中执行两个setpixels，一个用于origin.y+y，另一个用于origin.y-y。 - Mr Lister
2
如果你想要更好的性能，那么你需要使用不同的算法。你可以取消内部循环。对于每个y值，该算法会找到椭圆所属的最左和最右像素的x值；然后你只需绘制水平线即可。如果允许使用平方根，则查找线段端点非常简单，但是稍加努力就可以修改为仅使用整数（有点类似于Bresenham算法）。 - cvoinescu
8

椭圆（关于原点）是一个沿着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，那么这相当于您绘制圆的代码。
4
在内部循环中使用setpixel()，整个算法本身就不太可能高效。另外，任何优化编译器都会将dy的计算提升出x循环。 - Greg Hewgill
1
如果您将所有术语乘以 width*height，则可以进行整数运算。它简化为 x*height*x*height+y*width*y*width <= width*height*width*height。 - Mark Ransom
8
替换。
x*x+y*y <= radius*radius

with 

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是“张量”，但也许您不想涉及那些东西。
更新-详细数学内容。我认为S.O.无法像Math S.E.那样制作漂亮的数学公式，因此这看起来很粗糙。 您想要在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）来简化此项，类似于primed，并且R是涉及C和S的2x2矩阵： x' = R x 椭圆方程可以写成：
T（x'）A'' x' = 1
其中“T”表示转置，并省略“^”以避免刺痛所有人的眼睛，因此“a2”实际上意味着a²，
A'' =
1/a2     0  
 0     1/b2

使用 x' = Rx，我们可以得到：

T(Rx) A'' Rx = 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

将这些数乘以x和y，根据T(x)A x的公式计算即可得出结果。
1
谢谢您。有没有可能您能回复一个完整的算法，同时还考虑了角度？ - Roger Dahl
5
一个快速的Bresenham类型算法，如此论文所提出的那样，效果非常好。这是我为同样的OpenGL实现编写的。
基本原理是将曲线绘制在一个象限上，我们可以将其镜像到其他三个象限上。这些顶点使用错误函数计算，类似于用于圆的中点圆算法中使用的函数。我上面链接的论文对于方程有一个相当巧妙的证明，算法归结为仅检查给定顶点是否在椭圆内，只需通过将其值代入错误函数来检查。该算法还跟踪我们在第一象限中绘制的曲线的切线斜率，并根据斜率值递增x或y - 这进一步提高了算法的性能。这里是一个展示正在进行的情况的图像：

enter image description here

关于填充椭圆，一旦我们知道每个象限中的顶点（这本质上是沿x和y轴的镜像反射），我们就会得到每个计算顶点的4个顶点 - 这足以绘制一个四边形（在OpenGL中）。一旦我们为所有这样的顶点绘制四边形，我们就得到了一个填充的椭圆。我给出的实现采用VBO进行性能优化，但你不一定需要它。
该实现还向您展示了如何使用三角形和线条来实现填充椭圆，但四边形显然更好，因为它是一个基元，我们只为4个顶点绘制一个四边形，而在三角形实现中，需要为每个顶点绘制一个三角形。
1
链接很好，带有相关引用和示例的链接更好。如何回答 - crashmstr
@crashmstr 抱歉 - 我提供了更好的解释 - Prathap
感谢您提供的论文链接和回答。非常有效。 - picmate 涅
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接