如何将Bresenham的画线算法与裁剪一起使用? [英] How to use Bresenham's line drawing algorithm with clipping?

问题描述

使用 Bresenham画线算法绘制线时，该行可能不在要写入的位图的范围内-剪切结果将很有用，以便它们适合要写入的图像的轴对齐范围内.

When drawing a line with Bresenham line drawing algorithm, where the line may not be within the bounds of the bitmap being written to - it would be useful to clip the results so they fit within the axis aligned bounds of the image being written to.

虽然可以先将线剪裁到矩形，然后再画线.这是不理想的，因为它常常使(假设使用int坐标)线的倾斜度稍有不同.

While its possible to first clip the line to the rectangle, then draw the line. This isn't ideal since it often gives a slightly different slant to the line (assuming int coords are being used).

由于这是原始操作，是否存在在保持相同形状的同时剪切线的方法?

Since this is such a primitive operation, are there established methods for clipping the line while maintaining the same shape?

如果有帮助，请这是该算法的参考实现-它使用int坐标，这样可以避免在绘制直线时进行int/float转换.

In case it helps, here is a reference implementation of the algorithm - it uses int coords, which avoids int/float conversion while drawing the line.

我花了一些时间研究这个问题:

I spent some time looking into this:

• virtual-dub的网页上详细描述了问题a>.
• 艾伦·蒂德曼(Alan Tiedemann)可能的解决方案
  ...尽管我需要基于文本实现代码-才能查看其效果.
• 具有内置剪切功能的布雷森汉姆线生成算法
  (论文来自1995年，找不到整个文档吗?-PDF是没有参考的C代码的单个页面，看起来像是付费的墙.

推荐答案

让我们重新构造问题，以便我们了解布雷森汉姆算法的真正工作原理...

Let's reframe the problem so we can see how Bresenham's algorithm really works...

让我们说您正在画一条从(x0，y0)到(x1，y1)的基本上是水平的线(该方法对于大多数是垂直的，但是轴已切换):

Lets say you are drawing a mostly horizontal line (the method is the same for mostly vertical, but with the axes switched) from (x0,y0) to (x1,y1):

整行可以用 x (所有整数)描述为 y 的函数:

The full line can be described as a function of y in terms of x (all integers):

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

这精确地描述了绘制整条线时要绘制的每个像素，并且当连续裁剪线时，它 still 精确地描述了要绘制的每个像素-您只需将其应用于较小的 x 值的范围.

This describes precisely each pixel you will paint when drawing the full line, and when you clip the line consistently, it still describes precisely each pixel you will paint -- you just apply it to a smaller range of x values.

我们可以使用所有整数数学，通过分别计算除数和余数来评估此函数.对于 x1> = x0 和 y1> = y0 (否则请进行常规转换):

We can evaluate this function using all integer math, by calculating the divisor and remainder separately. For x1 >= x0 and y1 >= y0 (do the normal transformations otherwise):

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;
}

布雷森纳姆(Bresenham)算法是在更新 x 时递增地更新此公式结果的一种快速方法.

Bresenham's algorithm is a just a fast way to update the result of this formula incrementally as you update x.

在这里，我们可以利用增量更新来绘制从x = xs到x = xe的同一行的一部分:

Here's how we can make use of incremental updates to draw the portion of the very same line from x=xs to 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进行余数比较，则可以在开始时将其偏移:

If you want do to your remainder comparisons against 0, you can just offset it at the beginning:

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);
}

这篇关于如何将Bresenham的画线算法与裁剪一起使用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！