圆和椭圆光栅化算法

Question

在我的项目中，我需要实现圆形和椭圆光栅化（如果可能的话，用 C++ 或汇编 + SIMD）。我了解中点圆算法和布雷森纳姆圆算法。但这些算法使用整数值（中心 x、中心 y 和半径）。在我的例子中，半径和中心必须以浮点格式（或至少定点）表示。而且半径也可以小于 1px。所以我需要一个适用于浮点值的算法。有人可以帮助我吗？

Answer 1

我将为您提供圆的中点算法的基本介绍，但是您可以在大多数计算机图形学教科书中找到完整的中点算法。我假设中心和半径不是整数。从以圆为中心的隐式方程开始 在 (x_c,y_c) 处，半径为 R:

因此，给定平面上的任意点 (x,y)，我们可以测试该点是否在圆内、圆上或圆外。我们首先仅在第一个八分圆中绘制圆的部分，其中 x - x_c < y_c - y. 在这种情况下，我们将始终在每次迭代中沿 x 方向步进一个像素。 我们将根据 (x+1,y) 和 (x+1,y+1) 之间的中点 m 的符号，在 y 方向上步进 0 或 1：

x = round(xc), y = round(yc - R);  // top of circle, y-axis pts down
m = f(x+1,y + 0.5);      // initial midpoint value
while x - cx < yc - y {  // while in first octant
    plot(x,y)            // draw point at pixel grid point (x,y)
    x = x + 1            // step in x by 1
    if m < 0             // if midpoint inside circle
        y = y + 1        // then increment y too
    m = f(x,y)           // update value at midpoint
}

剩下的主要技巧是

• 推广到所有 8 个八分圆以完成圆；
• 为了速度，不要在每次迭代时从头开始评估 f， 而是计算每个 f 的二阶差 水平和对角线步长以及增量更新日期 m 每次迭代。
• 或者，如果您使用的是支持矢量的机器和/或有 访问硬件点积，然后直接评估f可能 非常快。
• 如果输入值是整数，则可以缩放m = f(x + 1, y + 0.5) 这样它始终是一个整数（我们只关心 f 的符号）并且只用整数算术来做所有事情。
• 推广到一个椭圆，其轴平行于 主轴，您只需将隐式方程更改为 一个椭圆并修改 while 循环条件来检查 f 的梯度可了解您何时完成了一个八分圆。
• 如果你想光栅化一个有向椭圆，那么答案 超出了本回复的范围:)。你可以画一个“快速而 使用椭圆的参数形式创建脏”椭圆并调整 参数步长连续，这样你的步长总是 0.5 到 1.5 之间。

Answer 2

根据维基百科的Bresenham算法，认为在屏幕的像素中画一个圆圈。

这就是为什么你可以用浮点数来计算你的圆，将中心放在任何非整数的位置，任何非整数的半径，你的圆将被精确地绘制到整数像素的位置。