布雷森汉姆直线算法

Bresenham的直线算法是一种算法，它确定应该选择的n维光栅的点，以便形成两点之间的直线的近似近似。 它通常用于在位图图像中（例如在计算机屏幕上）绘制线基元，因为它仅使用整数加法，减法和位移，所有这些都是标准计算机体系结构中非常便宜的操作。 它是一种增量错误算法。 它是计算机图形学领域最早开发的算法之一。 原始算法的扩展可用于绘制圆圈。

布雷森汉姆直线算法介绍

Bresenham的直线算法是一种算法，它确定应该选择的n维光栅的点，以便形成两点之间的直线的近似近似。 它通常用于在位图图像中（例如在计算机屏幕上）绘制线基元，因为它仅使用整数加法，减法和位移，所有这些都是标准计算机体系结构中非常便宜的操作。 它是一种增量错误算法。 它是计算机图形学领域最早开发的算法之一。 原始算法的扩展可用于绘制圆圈。

布雷森汉姆直线算法历史

Bresenham的线算法以Jack Elton Bresenham命名，他于1962年在IBM开发。 2001年Bresenham写道：

我在IBM的圣何塞开发实验室的计算实验室工作。 Calcomp绘图仪已通过1407打字机控制台连接到IBM 1401。 在1962年夏天投入生产，可能提前一个月左右。当时的节目在公司之间自由交换，因此Calcomp（Jim Newland和Calvin Hefte）有副本。当我在1962年秋季回到斯坦福时，我在斯坦福大学中心图书馆里放了一份副本。 1963年在科罗拉多州丹佛举行的ACM全国大会上接受了线描例程的描述。这一年没有出版任何会议记录，只有发言人的议程和ACM通讯问题的议题。一位来自IBM Systems Journal的人在我发表演讲后问我是否可以发表论文。我很高兴地同意了，他们在1965年将它打印出来。

Bresenham的算法后来被扩展为产生圆，所得到的算法有时被称为Bresenham的圆算法或中点圆算法。

布雷森汉姆直线算法代码案例

通过检查y是否需要增加或减少（即dy <0），可以扩展算法以覆盖0和-1之间的梯度。

plotLineLow(x0,y0, x1,y1)  dx = x1 - x0  dy = y1 - y0  yi = 1  if dy < 0    yi = -1    dy = -dy  end if  D = 2*dy - dx  y = y0  for x from x0 to x1    plot(x,y)    if D > 0       y = y + yi       D = D - 2*dx    end if    D = D + 2*dy

通过切换x和y轴，可以写出正或负陡梯度的实现：

plotLineHigh(x0,y0, x1,y1)  dx = x1 - x0  dy = y1 - y0  xi = 1  if dx < 0    xi = -1    dx = -dx  end if  D = 2*dx - dy  x = x0  for y from y0 to y1    plot(x,y)    if D > 0       x = x + xi       D = D - 2*dy    end if    D = D + 2*dx

布雷森汉姆直线算法类似的算法

Bresenham算法可以解释为略微修改的数字微分分析仪（使用0.5作为误差阈值而不是0，这是非重叠多边形光栅化所必需的）。

使用增量错误代替除法运算的原理在图形中有其他应用。 可以使用此技术在纹理映射多边形的光栅扫描期间计算U，V坐标。 在一些PC游戏中看到的体素高度图软件渲染引擎也使用了这个原理。

Bresenham还发布了Run-Slice（而不是Run-Length）计算算法。

处理粗线的算法的扩展是由Alan Murphy在IBM创建的。