如何使用具有亚像素偏差的 Bresenham 画线算法？

Question

Bresenham 的画线算法是众所周知的，而且很容易实现。

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

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

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

无子像素偏移：

X###
    ###X

假设右手点有一个靠近顶部的子像素位置，这条线可能如下所示：

以子像素偏移为例：

X######
       X

是否有一种经过验证的真实方法来绘制考虑亚像素坐标的线条？

---

笔记：

• 这似乎是一个常见的操作，我已经看到 OpenGL 驱动程序考虑到这一点，例如 - 使用GL_LINE，但从快速搜索中我没有在网上找到任何答案 - 可能使用了错误的搜索词？
• 乍一看，这个问题看起来可能是以下内容的重复：
  精确的子像素线绘制算法（光栅化算法）
  但是，这是询问绘制宽线，这是询问偏移单个像素线。
• 如果没有一些标准方法，我会尝试将其写下来作为答案发布。

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

唯一的变化是初始误差计算。新值来自简单的三角函数，用于计算 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。这允许它吸收原始公式中的除法和分数，但这意味着我们需要在我们使用它的任何地方应用相同的比例。

显然这里有很大的优化空间，但这是基本算法。如果我们假设 scale 是 2 的幂 ( 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 样式坐标系，但根据您的特定情况，它可能是左上角。}