多边形填充算法

Question

多边形填充算法

algorithmgeometrypolygonslice

7

我正在开发一个用于3D打印的网格切片工具。通常情况下，它应该将3D网格模型切割成2D形状（一些多边形，可能带有孔），并使用特定的图案填充它们，确定其厚度。这些路径将用于生成3D打印机固件的gcode命令。

现在有各种不同的开源工具，用于相同的目的，其中包括Python和Perl编写的工具。但我的目标是理解切片器的工作流程，并以C或C ++编写自己的工具。

到目前为止，我已经能够获得切片轮廓，现在要对其进行填充。问题是我找不到有效的算法来完成这个任务。 infill示例的简略过程如下：

是否有人能够建议如何生成这些填充路径？谢谢。

当前我正在使用以下算法：

查找形状的边界框
使用线条在垂直方向上分割bb（线条数量= bb.width / path.thickness）
查找形状与每条线的交点（每行应该有两个点）
从这些点构造偏移量为边界的线段
添加连接原始线段的线段，形成一条带状的线段
我们已经准备好生成gcode或绘制路径了

这是一个简单而快速的算法，但它不适用于具有凹多边形和孔的多边形。此外，它只使用一种指定的图案。

- san

图中的两个点都是蓝色的。其中一个应该改成绿色吗？ - ElKamina

此外，填充路径有哪些限制？ - ElKamina

请注意，有两条不同的路径，每条路径都有起点和终点。 - san

路径的限制仅在于其厚度和图案，数量应尽可能少，但并不是关键。 - san

使用插入多边形是一个选择吗？ - sloriot

@sloriot，插入多边形用于生成多个周长。但是，这不适合生成填充物，因为我们应该为每个打印层使用相反的填充方向形成“十字”填充。这样，我们可以获得模型的强大拓扑结构。 - san

3个回答

3

经过一段时间的研究，我得出了以下算法：

但是，还有许多优化机会。

- san

1

重新开启一个旧的线程。

根据这里提供的答案描述的技术，我创建了一个名为“Mandoline”的实现。请在这里查看：https://github.com/Tannz0rz/Mandoline

- Tannz0rz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

以下方法将产生一种填充图案，由一个单一路径（即填充喷嘴永远不会关闭、移动和重新打开）组成，只要可能就会这样做。

在第4步（"使用边界的偏移量从这些点构建线段"）之后，将每个垂直线段转换为2个或更多点：顶部和底部端点，加上（想象你的图表是画在透明幻灯片上的；在下面放一张带有水平线的纸，并标记你的图表中的垂直线段与纸上水平线相交的位置）。

现在形成一个边权重图，每个点都有一个顶点，如果它们对应的点小于或等于一个网格单位，则连接两个顶点的边。还要在线段的相邻最高点和相邻最低点之间添加边。使用欧几里得距离作为边权重。最后，神奇的部分：在这个图上找到一条最小权重的哈密顿路径。这是一条恰好访问每个顶点，并具有最小长度的路径。最小长度约束保证了路径永远不会交叉，因为如果任何两条线交叉，比如从a到b的线和从c到d的线，那么总是可以通过删除这两条线并使用不同的端点组合创建两条新线（要么是a---c和b---d，要么是a---d和b---c）来创建一个更短的整体路径。这就是你需要填充的路径。

寻找哈密顿路径（更不用说最小权重的哈密顿路径了）是一个NP难问题，与更著名的旅行商问题密切相关。由于已经存在许多良好的精确TSP求解器（例如Concorde），因此使用其中之一来找到旅行商路径，然后简单地删除一条边以生成短的哈密顿路径是明智的。（即使删除最重的边，这也不一定会产生最小长度的哈密顿路径，因为可能存在不以相邻顶点为起点和终点的更短路径；但我们并不真正关心整体长度，我们只想要访问所有顶点且不交叉的路径。）

不幸的是，图形不能保证包含哈密顿路径或旅行推销员之旅。（例如，如果图形是不连通的，它们显然不存在，但即使是连通的图形也可能缺少其中一个或两个：例如，任何度数为1的顶点的图形都不能有TSP之旅。）在这种情况下，如果您使用的TSP求解器可以找到不访问所有顶点的旅行，您可以重复此操作，直到涵盖所有顶点。如果失败，我会退回到您的原始算法。