绘制抗锯齿圆形的方法（Xaolin Wu所述）

Question

绘制抗锯齿圆形的方法（Xaolin Wu所述）

10

我正在尝试实现Xiaolin Wu在他的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，用0初始化j，然后定义循环条件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：如果我想要输入位置和半径为浮点数，会有什么陷阱吗？

- ChristopherC

5

你应该添加一个链接到你使用的论文，否则任何想要帮助的人都必须去搜索它，并希望找到相同的论文而不是一些衍生版......这会让大多数人望而却步，不愿意真正提供帮助。 - Spektre

我希望它是一份免费的论文，但似乎不是：http://dl.acm.org/citation.cfm?id=122734&dl=ACM&coll=DL&CFID=794955035&CFTOKEN=47936980。 - ChristopherC

2个回答

2

我在我的电脑上成功运行了以下内容:

def draw_antialiased_circle(renderer, position, radius, alpha_max=sdl2.SDL_ALPHA_OPAQUE):

    def _draw_points(i, j):
        '''Draws 8 points, one on each octant.'''
        #Square symmetry              
        local_coord = [(i*(-1)**(k%2), j*(-1)**(k//2)) for k in range(4)]
        #Diagonal symmetry
        local_coord += [(j_, i_) for i_, j_ in local_coord]
        for i_, j_ in local_coord:
            sdl2.SDL_RenderDrawPoint(renderer, position.x + i_, position.y + j_)

    def set_alpha_color(alpha, r=255, g=255, b=255):
        '''Sets the render color.'''
        sdl2.SDL_SetRenderDrawColor(renderer, r, g, b, alpha)

    i, j, T = radius, 0, 0

    #Draw the first 4 points
    set_alpha_color(alpha_max)
    _draw_points(i, 0)

    while i > j:
        j += 1
        d = math.ceil(math.sqrt(radius**2 - j**2))

        #Decrement i only if d < T as proved by Xiaolin Wu
        i -= 1 if d < T else 0

        """
        Draw 8 points for i and i-1 keeping the total opacity constant
        and equal to :alpha_max:.
        """
        alpha = int(d/radius * alpha_max)
        for i_, alpha_ in zip((i, i-1), (alpha, alpha_max - alpha)):
            set_alpha_color(alpha_)
            _draw_points(i_, j)
        #Previous d value goes to T
        T = d

上述是下图的简单实现。

该图中有一个错误：最底部的测试应该是 D(r,j) < T 而不是 D(r,j) > T，这可能解释了你为什么会有点困惑。

回答你的第二个问题，我怀疑你不能将一些 float 数字作为位置和半径传递，因为最终的 C 函数 SDL_RenderDrawPoint 需要 int 参数。

你可以将一些浮点数传递给你的 Python 函数，但在使用 SDL_RenderDrawPoint 之前，你必须将它们转换为 int。不幸的是，目前还没有半像素这样的东西 ;)

- Jacques Gaudin

谢谢Jacques！看起来条件while i > j可以重写为while i > j + 1，但无论如何它都很好用！现在我正在尝试理解差异，似乎归结于您计算D(r, j)与我在论文中阅读并翻译为变量d的不同。在我的论文版本（似乎比您的旧），我读到D(r, j) = floor((2^m - 1) * (ceil(sqrt(r^2 - j^2)) - sqrt(r^2 - j^2)) + 0.5)，这里的m = 255，但您的版本似乎只有D(r, j) = ceil(sqrt(r^2 - j^2))。 - ChristopherC

你对 alpha 值的计算方式也与半径有关，这让我更加困惑。如果您不介意对这两个点进行详细解释，我将不胜感激！最后，我问到“float”输入是因为我想绘制一个粒子系统，我担心速度非常慢的粒子可能会在每 20 帧左右突然从一个像素“跳动”到另一个像素，从而看起来很抖动。我不知道该如何处理？2/2 - ChristopherC

等一下，看起来我说话太快了。生成的圆没有毛刺，但没有反锯齿！ - ChristopherC

谢谢您的反馈。昨天我研究了一下alpha计算。我会详细说明这个问题和其他细节。你提出的问题实际上非常好！ - Jacques Gaudin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- daphtdazz · Accepted Answer

让我们来分解你的实现，找出你所犯的错误：

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)

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

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 是什么，它是环的外半径，环的宽度显然为1像素。或者至少，这个特殊情况告诉我们是这样...让我们看看通用代码是否能支持这一点。

while i < j + 1:

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

    i += 1

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

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

即s是指点 i 在x轴上八分之一的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时，它也会再次降低。

那么在开始时它取什么值呢？由于 i 为1，s 几乎等于 radius（假设圆的大小不平凡），因此假设我们有一个整数半径（第一个特殊情况的代码明显是这样假设的），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)

这就解释了为什么我们在_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)

在第一次迭代中，我们写入的是上方的位置，但是完全不透明。这意味着实际上我们使用的是内半径，而不是特殊情况错误使用的外半径。也就是说，有一种类似于偏移一的错误。

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

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) 和 (0, outer_radius) 位置均平滑地半透明，而这个算法无法实现，因为它忽略了原点。因此，如果您想准确使用此算法，则必须在传入之前将原点四舍五入，因此使用浮点数没有任何好处。