布雷森汉姆直线算法是众所周知的且实现相当简单。
虽然有更先进的方法来绘制抗锯齿线条，但我想编写一个函数，基于浮点坐标绘制单像素宽度的非抗锯齿线条。
这意味着虽然第一个和最后一个像素将保持不变，但在它们之间绘制的像素将根据两个端点的子像素位置而偏移。
原则上，这不应该太复杂，因为我认为可以使用子像素偏移量来计算绘制线条时要使用的初始误差值，而所有其他部分的算法保持不变。
没有子像素偏移：
X###
###X
例如，带有亚像素偏移：
X######
X
注意：
GL_LINE，但是从快速搜索中没有找到任何答案 - 可能使用了错误的搜索术语？我刚遇到了同样的挑战，我可以确认你期望的是可行的。
首先，回到算法的最简形式：（忽略分数，它们后面会消失）
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为整数时会发生什么:(这也假设坐标相对于每个像素的左下角而非像素中心1，因为一旦支持亚像素位置，可以将半个像素宽度加到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
# 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
我不确定这是否可以被视为Bresenham算法，但它非常相似。我将解释一下第一象限的情况。假设你希望在像素网格上从点(Px,Py)到(Qx,Qy)绘制一条直线，网格宽度为W。网格宽度W > 1允许子像素端点。
对于在第一象限中的直线，起始点很容易计算，只需取(Px,Py)的floor值。如后面所述，这仅适用于Qx >= Px & Qy >= Py。
现在你需要找到下一个要去的像素。有三种可能性：(x+1,y), (x,y+1), & (x+1,y+1)。为了做出这个决定，我使用定义如下的二维叉积：
为了决定下一个像素点，比较线段P-Q [下图中的红色]与点P和右上角像素(x+1,y+1)之间的连线（下图中的蓝色）的叉积。
P和右上角像素之间的向量可以计算如下：
因此，我们将使用二维叉积的值：
蓝色向量从线的起始点开始，并更新为每个像素的(x+1,y+1)。选择哪个像素的规则相同。如您所见，红色向量在蓝色向量的右侧。因此，下一个像素将是绿色像素的右侧像素。
如果下一个像素是(x+1)，则添加dx，如果像素是(y+1)，则添加dy。如果像素到达(x+1,y+1)，则两者都要添加。
重复此过程，直到到达结束像素(Qx / W, Qy / W)。
综合起来，得到以下代码：
int dx = x2 - x2;
int dy = y2 - y1;
int local_x = x1 % width;
int local_y = y1 % width;
int cross_product = dx*(width-local_y) - dy*(width-local_x);
int dx_cross = -dy*width;
int dy_cross = dx*width;
int x = x1 / width;
int y = y1 / width;
int end_x = x2 / width;
int end_y = y2 / width;
while (x != end_x || y != end_y) {
SetPixel(x,y,color);
int old_cross = cross_product;
if (old_cross >= 0) {
x++;
cross_product += dx_cross;
}
if (old_cross <= 0) {
y++;
cross_product += dy_cross;
}
}
让它适用于所有象限是通过反转本地坐标和一些绝对值来实现的。以下是适用于所有象限的代码：
int dx = x2 - x1;
int dy = y2 - y1;
int dx_x = (dx >= 0) ? 1 : -1;
int dy_y = (dy >= 0) ? 1 : -1;
int local_x = x1 % square_width;
int local_y = y1 % square_width;
int x_dist = (dx >= 0) ? (square_width - local_x) : (local_x);
int y_dist = (dy >= 0) ? (square_width - local_y) : (local_y);
int cross_product = abs(dx) * abs(y_dist) - abs(dy) * abs(x_dist);
dx_cross = -abs(dy) * square_width;
dy_cross = abs(dx) * square_width;
int x = x1 / square_width;
int y = y1 / square_width;
int end_x = x2 / square_width;
int end_y = y2 / square_width;
while (x != end_x || y != end_y) {
SetPixel(x,y,color);
int old_cross = cross_product;
if (old_cross >= 0) {
x += dx_x;
cross_product += dx_cross;
}
if (old_cross <= 0) {
y += dy_y;
cross_product += dy_cross;
}
}
这里有一些像素与该线段不相交：
A' - 如果一条线显然不会与像素相交，那么像素不会被绘制。
B' - 如果一条垂直线显然不会与像素相交，那么像素不会被绘制。
C' - 如果一条水平线显然不会与像素相交，那么像素不会被绘制。
D' - 如果一条垂直线恰好接触像素的右侧，那么像素不会被绘制。
E' - 如果一条水平线恰好接触像素的顶部，那么像素不会被绘制。
F' - 如果一条线段的端点恰好从像素的右上角开始沿着（+，+）方向前进，那么像素不会被绘制。
G' - 如果一条线段的端点恰好从像素的顶部开始沿着（+，+）方向前进，那么像素不会被绘制。
H' - 如果一条线段的端点恰好从像素的右侧开始沿着（+，+）方向前进，那么像素不会被绘制。
I' - 如果一条线段恰好接触像素的任意一个角落，那么像素不会被绘制。这适用于所有角落。
这就像上面的图G'，只不过y轴被翻转了，因为Qy < Py。有4x4个红点，因为W等于4，使得像素尺寸为4x4。每个4个点都是线条唯一可以触及的端点。所画的线从(1.25, 1.0)到某个地方。不要将线的端点向下取整，而是需要在x和y维度上将最小端点向下取整，并将最大端点减1向上取整。
因此，这里是完成这种向下/向上取整的完整代码：
int dx = x2 - x1;
int dy = y2 - y1;
int dx_x = (dx >= 0) ? 1 : -1;
int dy_y = (dy >= 0) ? 1 : -1;
int local_x = x1 % square_width;
int local_y = y1 % square_width;
int x_dist = (dx >= 0) ? (square_width - local_x) : (local_x);
int y_dist = (dy >= 0) ? (square_width - local_y) : (local_y);
int cross_product = abs(dx) * abs(y_dist) - abs(dy) * abs(x_dist);
dx_cross = -abs(dy) * square_width;
dy_cross = abs(dx) * square_width;
int x = x1 / square_width;
int y = y1 / square_width;
int end_x = x2 / square_width;
int end_y = y2 / square_width;
// Perform ceiling/flooring of the pixel endpoints
if (dy < 0)
{
if ((y1 % square_width) == 0)
{
y--;
cross_product += dy_cross;
}
}
else if (dy > 0)
{
if ((y2 % square_width) == 0)
end_y--;
}
if (dx < 0)
{
if ((x1 % square_width) == 0)
{
x--;
cross_product += dx_cross;
}
}
else if (dx > 0)
{
if ((x2 % square_width) == 0)
end_x--;
}
while (x != end_x || y != end_y) {
SetPixel(x,y,color);
int old_cross = cross_product;
if (old_cross >= 0) {
x += dx_x;
cross_product += dx_cross;
}
if (old_cross <= 0) {
y += dy_y;
cross_product += dy_cross;
}
}
假设您想从P1 = (x1, y1) 绘制一条线到P2 = (x2, y2) ，其中所有的数字都是 浮点数 像素坐标。
Calculate the true pixel coordinates of P1 and P2 and paint them: P* = (round(x), round(y)).
If abs(x1* - x2*) <= 1 && abs(y1* - y2*) <= 1 then you are finished.
Decide whether it is a horizontal (true) or a vertical line (false): abs(x1 - x2) >= abs(y1 - y2).
If it is a horizontal line and x1 > x2 or if it is a vertical line and y1 > y2: swap P1 with P2 (and also P1* with P2*).
If it is a horizontal line you can get the y-coordinates for all the x-coordinates between x1* and x2* with the following formula:
y(x) = round(y1 + (x - x1) / (x2 - x1) * (y2 - y1))
If you have a vertical line you can get the x-coordinates for all the y-coordinates between y1* and y2* with this formula:
x(y) = round(x1 + (y - y1) / (y2 - y1) * (x2 - x1))
这里有一个演示，您可以尝试在第12行上尝试不同的点。
e = frac(x1) * (y2 - y1) + frac(y1) * (x2 - x1)来进行种子填充，尽管使用定点坐标可以避免舍入误差。我的观点是，DDA内循环（基本上是加法和移位）通常比Bresenham更快，缺点是有一个小的初始化开销，除非你的线段非常短或者除法非常昂贵，否则这个开销通常是无关紧要的。 - doynax