如何使用 Bresenham 的线条绘制算法进行剪裁？

Question

当使用Bresenham 线绘制算法绘制一条线时，该线可能不在所写入位图的边界内 - 裁剪结果以使它们适合所写入图像的轴对齐边界会很有用。

虽然可以先将线条剪裁到矩形，然后再绘制线条。这并不理想，因为它通常会给线条稍微不同的倾斜度（假设正在使用 int 坐标）。

由于这是一个如此原始的操作，是否有既定的方法可以在保持相同形状的同时剪切线？

如果有帮助，这里是该算法的参考实现- 它使用 int coords，避免在绘制线条时进行 int/float 转换。

---

我花了一些时间研究这个：

• 问题在virtual-dub 的网页上有详细描述。
• Alan Tiedemann 的可能解决方案
  ......尽管我需要根据文本实现代码 - 看看它的效果如何。
• Bresenham's Line Generation Algorithm with Built-in Clipping
  （1995 年的论文，找不到整个文档？-PDF 是没有引用的 C 代码的单个页面，看起来像是付费墙）。

Answer 1

让我们重新构建这个问题，以便我们可以看到 Bresenham 算法的实际工作原理......

假设您正在绘制一条主要水平的线（该方法与主要垂直的线相同，但轴交换）从(x0,y0)到(x1,y1)：

y整条线可以描述为x（所有整数）的函数：

y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )

这精确地描述了您在绘制整条线时将绘制的每个像素，并且当您一致地剪切线时，它仍然精确地描述了您将绘制的每个像素 - 您只需将其应用于较小范围的x值即可。

我们可以通过单独计算除数和余数，使用所有整数数学来评估该函数。对于x1 >= x0和y1 >= y0（否则进行正常变换）：

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}

布雷森纳姆算法只是一种在更新时增量更新此公式结果的快速方法x。

以下是我们如何利用增量更新来绘制从 x=xs 到 x=xe 的同一直线的部分：

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= remlimit)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}

如果你想将余数与 0 进行比较，你可以在开头偏移它：

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = ( (x-x0) * dy % dx ) - remlimit;
y = y0 + (x-x0) * dy / dx;
if (rem >= 0)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= 0)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}