绘制一个抗锯齿的圆圈,如Xaolin Wu所描述

Question

我正在努力实施"小快速消极圆形发生器"程序,该程序由Xiaolin Wu在Siggraph '91的论文"An Efficient Anasingiasing Technique"中描述.

这是我用Python 3和PySDL2编写的代码:

def draw_antialiased_circle(renderer, position, radius):
    def _draw_point(renderer, offset, x, y):
        sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y + y)
        sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y + y)
        sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y - y)
        sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y - y)

    i = 0
    j = radius
    d = 0
    T = 0

    sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, sdl2.SDL_ALPHA_OPAQUE)
    _draw_point(renderer, position, i, j)

    while i < j + 1:
        i += 1
        s = math.sqrt(max(radius * radius - i * i, 0.0))
        d = math.floor(sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) + 0.5)

        if d < T:
            j -= 1

        T = d

        if d > 0:
            alpha = d
            sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha)
            _draw_point(renderer, position, i, j)
            if i != j:
                _draw_point(renderer, position, j, i)

        if (sdl2.SDL_ALPHA_OPAQUE - d) > 0:
            alpha = sdl2.SDL_ALPHA_OPAQUE - d
            sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha)
            _draw_point(renderer, position, i, j + 1)
            if i != j + 1:
                _draw_point(renderer, position, j + 1, i)

这是我认为在他的论文中描述的一个天真的实现,除了我指定了半径值j而不是i因为我误解了某些东西或者他的论文中有错误.实际上,他i用半径值初始化,j用0,然后定义循环条件i <= j,只有当半径为时才能为真0.这种变化使我从做什么的描述其他一些小的修改,我也改if d > T以if d < T简单,因为它看起来否则打破.

除了每个八分圆的开始和结束之外,这种实现工作效果很好,其中出现一些毛刺.

上面的圆的半径为1.正如您在每个八分圆的开头看到的那样(例如在(0,1)区域中),在循环内绘制的像素不会与在绘制之前绘制的第一个像素对齐.循环开始.在每个八分圆的末端(例如在该(sqrt(2) / 2, sqrt(2) / 2)区域中)也有一些错误.我设法通过改变if d < T条件使最后一个问题消失if d <= T,但同样的问题然后出现在每个八分圆的开始.

问题1:我做错了什么？

问题2:如果我想输入位置和半径是浮点,会不会有任何问题？

Answer 1

让我们解构您的实现以找出您犯了哪些错误：

def  draw_antialiased_circle(renderer, position, radius):

第一个问题，什么radius意思？不可能画一个圆，你只能画一个圆环（圆环/甜甜圈），因为除非你有一定的厚度，否则你看不到它。因此半径是不明确的，是内半径、中点半径还是外半径？如果你没有在变量名中指定，就会变得混乱。也许我们可以找到答案。

def _draw_point(renderer, offset, x, y):
    sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y + y)
    sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y + y)
    sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y - y)
    sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y - y)

好的，由于圆是对称的，我们将一次绘制四个地方。为什么不一次8个地方呢？

i = 0
j = radius
d = 0
T = 0

好的，初始化i为 0 和j半径，这些必须是x和y坐标。d和是什么T？不具描述性的变量名称没有帮助。复制科学家的算法以使它们实际上可以通过更长的变量名称来理解是可以的！

sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, sdl2.SDL_ALPHA_OPAQUE)
_draw_point(renderer, position, i, j)

啊？我们正在绘制一个特殊情况？我们为什么要这么做？没有把握。但这意味着什么？这意味着以完全不透明的方式填充正方形(0, radius)。现在我们知道是什么radius了，它是环的外半径，环的宽度显然是一个像素。或者至少，这就是这个特殊情况告诉我们的……让我们看看这在通用代码中是否成立。

while i < j + 1:

我们将循环直到到达圆上的点i > j，然后停止。即我们正在绘制一个八分圆。

    i += 1

所以我们已经在该位置绘制了我们关心的所有像素i = 0，让我们继续下一个。

    s = math.sqrt(max(radius * radius - i * i, 0.0))

Ies是一个浮点数，它是ix 轴上的点的八分圆的 y 分量。即x轴上方的高度。由于某种原因，我们max在那里有一个，也许我们担心非常小的圆圈......但这并不能告诉我们该点是否在外半径/内半径上。

    d = math.floor(sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) + 0.5)

分解它，(math.ceil(s) - s)给我们一个 0 到 1.0 之间的数字。这个数字会随着s减少而增加，随着i增加而增加，然后一旦达到 1.0 将重置为 0.0，因此呈锯齿状。

sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s)提示我们使用锯齿输入来生成一定程度的不透明度，即对圆进行抗锯齿处理。0.5 常数的添加似乎没有必要。这floor()表明我们只对整数值感兴趣——API 可能只接受整数值。所有这些都表明d最终成为 0 和 之间的整数水平SDL_ALPHA_OPAQUE，从 0 开始，然后逐渐增加i，然后当ceil(s) - s从 1 回到 0 时，它也再次回落到低位。

那么一开始它的值是多少呢？s几乎radius因为i是 1，（假设一个非常大的圆）所以假设我们有一个积分半径（第一个特殊情况代码显然假设）ceil(s) - s是 0

    if d < T:
        j -= 1
    d = T

在这里，我们发现它d已经从高移动到低，然后我们向下移动屏幕，以便我们的j位置保持在理论上环应该在的位置附近。

但现在我们也意识到之前方程的下限是错误的。想象一下，一次迭代的结果d是 100.9。然后在下一次迭代中它有所下降，但仅降至 100.1。因为d和T是相等的，因为下限消除了它们的差异，所以在这种情况下我们不会递减j，这是至关重要的。我想这可能解释了八分圆两端的奇怪曲线。

if d < 0:

只是一个优化，如果我们要使用 alpha 值 0，则不绘制

alpha = d
sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha)
_draw_point(renderer, position, i, j)

但是等一下，第一次迭代的效率d很低，所以这会绘制到(1, radius)一个几乎完全透明的元素。但特殊情况一开始就绘制了一个完全不透明的元素(0, radius)，所以显然这里会出现图形故障。这就是你所看到的。

进行中：

if i != j:

另一个小的优化，如果我们绘制到同一位置，我们就不会再次绘制

_draw_point(renderer, position, j, i)

这解释了为什么我们只在 中画 4 个点_draw_point()，因为你在这里做了另一个对称。它会简化你的代码而不是。

if (sdl2.SDL_ALPHA_OPAQUE - d) > 0:

另一种优化（你不应该过早地优化你的代码！）：

alpha = sdl2.SDL_ALPHA_OPAQUE - d
sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha)
_draw_point(renderer, position, i, j + 1)

因此，在第一次迭代中，我们正在写入上面的位置，但完全不透明。这意味着我们实际上使用的是内半径，而不是特殊情况误差所使用的外半径。即一种相差一错误。

我的实现（我没有安装该库，但您可以从检查边界条件的输出中看到它是有意义的）：

import math

def draw_antialiased_circle(outer_radius):
    def _draw_point(x, y, alpha):
        # draw the 8 symmetries.
        print('%d:%d @ %f' % (x, y, alpha))

    i = 0
    j = outer_radius
    last_fade_amount = 0
    fade_amount = 0

    MAX_OPAQUE = 100.0

    while i < j:
        height = math.sqrt(max(outer_radius * outer_radius - i * i, 0))
        fade_amount = MAX_OPAQUE * (math.ceil(height) - height)

        if fade_amount < last_fade_amount:
            # Opaqueness reset so drop down a row.
            j -= 1
        last_fade_amount = fade_amount

        # The API needs integers, so convert here now we've checked if 
        # it dropped.
        fade_amount_i = int(fade_amount)

        # We're fading out the current j row, and fading in the next one down.
        _draw_point(i, j, MAX_OPAQUE - fade_amount_i)
        _draw_point(i, j - 1, fade_amount_i)

        i += 1

最后，如果您想传入浮点原点，会出现问题吗？

是的，会有的。该算法假设原点位于整数/整数位置，否则完全忽略它。正如我们所看到的，如果您传入一个整数outer_radius，算法会在该(0, outer_radius - 1)位置绘制一个 100% 不透明的正方形。但是，如果您想要对位置进行变换，您可能希望圆在和位置(0, 0.5)处平滑地锯齿至 50% 的不透明度，但该算法无法实现这一点，因为它忽略了原点。因此，如果您想准确地使用此算法，则必须在传入原点之前对其进行四舍五入，因此使用浮点数没有任何好处。(0, outer_radius - 1)(0, outer_radius)