python - 绘制一个由 Xaolin Wu 描述的抗锯齿圆

Question

我正在努力实现“快速抗锯齿圆圈生成器”例程，吴晓林在他的论文“一种有效的抗锯齿技术”中描述了 Siggraph '91。

这是我使用 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

OK，初始化 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 ，然后停止。 IE。我们正在绘制一个八分圆。

    i += 1

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

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

IE。 s是一个浮点数，它是点 i 处八分圆的 y 分量在 x 轴上。 IE。 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:

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

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)

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

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)

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

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

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)位置，您可能希望圆在 (0, outer_radius - 1) 处平滑地混叠至 50% 的不透明度。和 (0, outer_radius)位置，这个算法没有给你，因为它忽略了原点。因此，如果您想准确地使用此算法，则必须在传入原点之前对其进行四舍五入，因此使用浮点数没有任何好处。