algorithm - 如何使用具有亚像素偏差的 Bresenham 线绘制算法？

Question

Bresenham's line drawing algorithm众所周知，实现起来也很简单。

虽然有更高级的方法来绘制抗锯齿线，但我有兴趣编写一个基于浮点坐标绘制单个像素宽度的非抗锯齿线的函数。

这意味着虽然第一个和最后一个像素将保持不变，但在它们之间绘制的像素将具有基于两个端点的子像素位置的偏差。

原则上这不应该那么复杂，因为我假设可以使用子像素偏移来计算初始 error 值，以便在绘制线条和所有其他部分时使用的算法保持不变。

No sub pixel offset:

X###
    ###X

假设右手边的点有一个靠近顶部的子像素位置，则该线可能如下所示:

With sub pixel offset for example:

X######
       X

是否有一种行之有效的方法来绘制一条考虑了子像素坐标的线？

---

注意:

• 这似乎是一个常见的操作，我已经看到 OpenGL 驱动程序考虑了这一点，例如 - 使用 GL_LINE，尽管通过快速搜索我没有在网上找到任何答案 - 可能使用错误搜索字词？
• 乍一看，这个问题可能与以下问题重复:
  Precise subpixel line drawing algorithm (rasterization algorithm)
  然而，这是关于绘制一条宽线的问题，这是关于偏移单个像素线的问题。
• 如果没有一些标准方法，我会尝试将其写下来作为答案发布。

Answer 1

刚遇到同样的挑战，我可以确认这是可能的，如您所料。

首先，回到算法的最简单形式:(忽略分数；稍后它们会消失)

x = x0
y = y0
dx = x1 - x0
dy = y1 - y0
error = -0.5
while x < x1:
    if error > 0:
        y += 1
        error -= 1
    paint(x, y)
    x += 1
    error += dy/dx

这意味着对于整数坐标，我们从像素边界上方半个像素开始(error = -0.5)，对于我们在 x 中前进的每个像素，我们将理想的 y 坐标(以及当前的 error)增加 dy/dx。

首先让我们看看如果我们停止强制 x0、y0、x1 和 y1 为整数会发生什么: (这也假设坐标不是使用像素中心，而是相对于每个像素的左下角¹，因为一旦你支持子像素位置，你可以简单地添加像素宽度的一半到 x 和 y 以返回以像素为中心的逻辑)

x = x0
y = y0
dx = x1 - x0
dy = y1 - y0
error = (0.5 - (x0 % 1)) * dy/dx + (y0 % 1) - 1
while x < x1:
    if error > 0:
        y += 1
        error -= 1
    paint(x, y)
    x += 1
    error += dy/dx

唯一的变化是初始误差计算。新值来自简单的 trig，用于计算 x 位于像素中心时的 y 坐标。值得注意的是，您可以使用相同的想法将线条的起始位置限制在某个范围内，这是您在开始优化时可能会面临的另一个挑战。

现在我们只需要将其转换为纯整数算术。我们需要一些用于小数输入的固定乘数 (scale)，并且可以通过将它们相乘来处理除法，就像标准算法一样。

# assumes x0, y0, x1 and y1 are pre-multiplied by scale
x = x0
y = y0
dx = x1 - x0
dy = y1 - y0
error = (scale - 2 * (x0 % scale)) * dy + 2 * (y0 % scale) * dx - 2 * dx * scale
while x < x1:
    if error > 0:
        y += scale
        error -= 2 * dx * scale
    paint(x / scale, y / scale)
    x += scale
    error += 2 * dy * scale

请注意，x、y、dx 和 dy 与输入变量保持相同的比例因子( scale)，而 error 有一个更复杂的比例因子:2 * dx * scale。这允许它吸收其原始公式中的除法和分数，但这意味着我们需要在我们使用它的任何地方应用相同的比例。

显然这里有很大的优化空间，但这是基本算法。如果我们假设规模是二次方 (2^n)，我们就可以开始让事情变得更高效:

dx = x1 - x0
dy = y1 - y0
mask = (1 << n) - 1
error = (2 * (y0 & mask) - (2 << n)) * dx - (2 * (x0 & mask) - (1 << n)) * dy
x = x0 >> n
y = y0 >> n
while x < (x1 >> n):
    if error > 0:
        y += 1
        error -= 2 * dx << n
    paint(x, y)
    x += 1
    error += 2 * dy << n

与原始版本一样，这仅适用于 (x >= y, x > 0, y >= 0) 八分圆。通常的规则适用于将其扩展到所有情况，但请注意，由于坐标不再以像素为中心(即反射变得更加复杂)，因此存在一些额外的问题。

您还需要注意整数溢出:error 的精度是输入变量的两倍，范围是行长度的两倍。相应地规划您的输入、精度和变量类型!

^{1:坐标相对于最接近 0,0 的角点。对于左下角的 OpenGL 风格坐标系，但根据您的特定情况，它也可能是左上角。}