如何使用Bresenham创建任意厚度的线？

Question

我目前正在使用Bresenham的算法绘制线条，但它们（当然）厚度为一个像素。我的问题是绘制任意厚度线条的最有效方法是什么？

我使用的语言是C.

Answer 1

我认为最好的方法是绘制一个矩形而不是一条线，因为宽度为一条线的线是一个二维对象。要绘制一组平行线以避免过度绘制（以减少写入带宽）和欠拉（缺少像素）将非常复杂。从起点和终点以及宽度计算矩形的角点并不太难。

因此，在下面的评论之后，执行此操作的过程将是： -

1. 创建一个长度与所需的线宽相同的矩形，宽度等于所需的宽度，所以（0,0）到（宽度，长度）
2. 使用2D变换将矩形角坐标旋转并转换为所需位置
3. 使用硬件加速渲染器（例如OpenGL quad）或使用软件栅格化器对旋转的矩形进行栅格化。它可以使用四边形栅格化器或一对三角形（例如，左上角和右下角）进行渲染。

注意*：如果您正在使用OpenGL，您也可以同时执行步骤2。当然，使用OpenGL确实意味着理解OpenGL（大而复杂），并且这个应用程序可能会在开发的这个后期阶段实现这个棘手的事情。

Answer 2

前段时间我遇到了同样的问题。基于这个paper，我创建了一个Matlab参考实现，我想在GitHub上分享。

Answer 3

创建几乎任意厚度的线的最简单方法是先做一个bresenham，然后根据需要应用尽可能多的dilation迭代。每个扩张垫均匀地填充线的两侧，但通过使用不同的面罩，您可以实现均匀的厚度：

厚度1：

面具：

1 1 1
1 1 1
1 1 1

产生的厚度：3

面具：

0 1 0
1 1 1
0 1 0

产生的厚度：2

Answer 4

采取另一个Bresenham循环并使用它来修改矩形方向上原始线的起始和结束位置。问题是有效地找到正确的起点，而不是在绘制下一行时绘制任何像素两次（或跳过一个像素）。

工作和测试的C代码可从Github C code获得。

这是一个测试页面，包括由此代码创建的一些示例行。黑色像素是算法的起点。

Answer 5

这是一个用于绘制加粗线条的Bresenham算法的修改版本的paper and Delphi implementation。

您可能还想看看Anti-Grain Geometry，这是一个用于2D图形的高质量和高性能软件渲染的库。看看demo page，了解它能做些什么。

Answer 6

为了获得最佳精度，尤其是较粗线条的良好性能，您可以将线条绘制为多边形。一些伪代码：

draw_line(x1,y1,x2,y2,thickness)
  Point p[4];
  angle = atan2(y2-y1,x2-x1);
  p[0].x = x1 + thickness*cos(angle+PI/2);
  p[0].y = y1 + thickness*sin(angle+PI/2);
  p[1].x = x1 + thickness*cos(angle-PI/2);
  p[1].y = y1 + thickness*sin(angle-PI/2);
  p[2].x = x2 + thickness*cos(angle-PI/2);
  p[2].y = y2 + thickness*sin(angle-PI/2);
  p[3].x = x2 + thickness*cos(angle+PI/2);
  p[3].y = y2 + thickness*sin(angle+PI/2);
  draw_polygon(p,4)

并且可选地，可以在每个端点处绘制圆圈。

Answer 7

一些简单的使用路线：

1. 对于任何宽度n，其中n是奇数。对于任何点p，也绘制了n / 2上方/下方的点（如果线是> 45度角，则相反地绘制）。 不是正确厚度的正确线条，更像斜体笔，但非常快。
2. 对于起始点p（x，y），选择点t0和b使得它们以p为中心但是n个像素分开。对于终点做同样的结果导致t1 b1。从t0 - > t1，t1-> b1，b1 - > t0，b0 - > t1画线。填写生成的矩形。 这里的技巧是选择点，使它们看起来与路径方向正交。
3. 对于线上的每个点p而不是绘制一个点画一个圆。 无论方向如何，这都具有使端点“清洁”的优点。 除了第一个之外，不需要渲染任何实心圆圈。 有点慢

Answer 8

我假设您将从一条边界线绘制水平跨度到另一条边界线，并按照Bresenham的方法计算每条线的x值（在单个循环中）。

没试过。

终点可能需要一些注意，以免它们看起来奇怪地截止。

Answer 9

http://members.chello.at/~easyfilter/bresenham.html

这个链接底部的例子是javascript，但应该很容易适应C.这是一个相当简单的抗锯齿算法来绘制可变厚度的线条。

Answer 10

我经常这样做以产生用于多孔介质模拟的纤维和球体的图像。我有一个很简单的方法，使用非常标准的图像分析技术，称为“距离变换”。这需要访问某些图像分析包。我使用Python和Scipy，所以这没问题。这是一个将随机分布的点转换为球体的演示：

import scipy as sp
import scipy.ndimage as spim

im1 = sp.rand(100, 100) < 0.995  # Create random points in space
dt = spim.distance_transform_edt(im1)
im2 = dt < 5  # To create sphere with a radius of 5

就是这样！对于非常大的图像，距离变换可能很慢，但是那里有高效的版本。例如，ImageJ有一个并行的。显然，要创建粗纤维，只需创建薄图像，然后应用上面的步骤2和3。

Answer 11

对于我的嵌入式热敏打印机应用程序，使用Bresenham的算法，线条太薄了。我没有GL或任何花哨的东西。我最终简单地减少了Y值并在第一个下面画了更多的线。每个厚度的数量增加了另一条线。非常快速地实现并制作从单色位图到热量的打印所需的结果。