按照 Xaolin Wu 的描述绘制抗锯齿圆圈
Drawing an antialiased circle as described by Xaolin Wu
我正在尝试实现 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，只有当半径为[=15=时才为真].此更改导致我对所描述的内容进行了一些其他小的修改，并且我还将 if d > T 更改为 if d < T 只是因为它看起来不完整。
除在每个八分圆的开始和结束处出现一些故障外，此实现大部分情况下都运行良好。
上面的圆的半径为 1。正如您所见，在每个八分圆的开始处（例如在 (0, 1) 区域），在环内绘制的像素未与第一个像素对齐在循环开始之前绘制。在每个八分圆的末尾也出现了严重错误（例如在 (sqrt(2) / 2, sqrt(2) / 2) 区域）。我设法通过将 if d < T 条件更改为 if d <= T 使最后一个问题消失，但同样的问题随后出现在每个八分圆的开始处。
问题 1：我做错了什么？
问题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。不幸的是，还没有像半像素这样的东西 ;)
让我们解构您的实现以找出您犯了什么错误：
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))
即s 是一个浮点数，它是 x 轴上点 i 处八分圆的 y 分量。 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 是相等的，因为 floor 已经消除了它们的差异，我们不会在这种情况下减少 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)
因此，在第一次迭代中，我们写入上面的位置，但完全不透明。这意味着实际上我们使用的是 inner 半径，而不是特殊情况错误使用的 outer 半径。 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) 和 (0, outer_radius) 位置平滑地别名到 50% 的不透明度，这这个算法不给你，因为它忽略了原点。因此，如果你想准确地使用这个算法，你必须在传入它之前将你的原点四舍五入，所以使用浮点数没有任何好处。
我正在尝试实现 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，只有当半径为[=15=时才为真].此更改导致我对所描述的内容进行了一些其他小的修改，并且我还将 if d > T 更改为 if d < T 只是因为它看起来不完整。
除在每个八分圆的开始和结束处出现一些故障外，此实现大部分情况下都运行良好。
上面的圆的半径为 1。正如您所见，在每个八分圆的开始处（例如在 (0, 1) 区域），在环内绘制的像素未与第一个像素对齐在循环开始之前绘制。在每个八分圆的末尾也出现了严重错误（例如在 (sqrt(2) / 2, sqrt(2) / 2) 区域）。我设法通过将 if d < T 条件更改为 if d <= T 使最后一个问题消失，但同样的问题随后出现在每个八分圆的开始处。
问题 1：我做错了什么？
问题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。不幸的是，还没有像半像素这样的东西 ;)
让我们解构您的实现以找出您犯了什么错误：
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))
即s 是一个浮点数，它是 x 轴上点 i 处八分圆的 y 分量。 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 是相等的，因为 floor 已经消除了它们的差异，我们不会在这种情况下减少 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)
因此，在第一次迭代中，我们写入上面的位置，但完全不透明。这意味着实际上我们使用的是 inner 半径，而不是特殊情况错误使用的 outer 半径。 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) 和 (0, outer_radius) 位置平滑地别名到 50% 的不透明度，这这个算法不给你，因为它忽略了原点。因此，如果你想准确地使用这个算法，你必须在传入它之前将你的原点四舍五入，所以使用浮点数没有任何好处。