多边形填充算法

Question

我正在研究用于3d打印目的的网格切片实用程序.通常,它应该将3d网格模型切割成2d形状(多个多边形,可能带有孔),并使用特定图案填充确定厚度的路径.这些路径将用于生成3d打印机固件的gcode命令.

有各种开源工具具有相同的目的,用python和perl编写.但我的目标是了解切片器的工作流程,并用C或C++编写自己的工具.

到目前为止,我能够获得切片的轮廓,现在要用路径填充它们.问题是我发现没有有效的算法来做到这一点.填充示例的示意图:

任何人都可以建议如何生成这些填充路径？谢谢.

---

目前我正在使用以下算法:

1. 找到形状的边界框
2. 用线垂直分割bb(行数= bb.width/path.thickness)
3. 找到形状和每条线的交叉点(每条线应该是两个点)
4. 从这些点构造一个从边界偏移的线段
5. 添加一段将原始段连接在一起形成一条线条
6. 我们准备生成gcode或绘制路径

这是一种简单快速的算法,但它不适用于凹多边形和带孔的多边形.它也只使用一个指定的模式.

Answer 1

只要有可能,下面的方法将产生一个由单个路径组成的填充模式(即填充喷嘴永远不会被关闭,移动和重新打开).

在步骤4("从边界偏移构造这些点的线段")之后,将每个垂直线段转换为2个或更多点:顶部和底部端点,加上(想象您的图表是在透明幻灯片上绘制的;放置一张纸,下面有水平线,并标记图中垂直线段与纸张上的水平线相交的位置).

现在形成一个边加权图,其中包含每个点的顶点,每当它们的对应点小于或等于一个网格单元时,边连接两个顶点.还要在线段的相邻最顶点之间以及相邻最底点之间添加边.使用点之间的欧氏距离作为边缘权重.最后,神奇的部分:在此图上找到最小权重哈密​​尔顿路径.这是一个完全访问每个顶点一次并具有最小长度的路径.最小长度约束保证路径永远不会跨越自身,因为如果任何两条线交叉,例如从a到b的线和从c到d的线,那么通过删除这些线总是可以创建更短的整体路径使用不同的端点组合(a --- c和b --- d,或a --- d和b --- c)创建两条线并创建两条新线.这是您要填写的路径.

寻找汉密尔顿路径(更不用说最小权重的汉密尔顿路径)是一个NP难问题,与更着名的旅行商问题密切相关.由于已经存在许多精确的TSP求解器(例如协和式飞机),因此使用其中一个来寻找旅行推销员之旅,然后简单地删除其中一个边缘以产生短哈密尔顿路径是明智的.(即使你删除了最重的边缘,这也不一定会产生最小长度的哈密顿路径,因为可能存在不在相邻顶点开始和结束的较短路径;但我们并不真正关心这里的总长度,我们只需要一个访问所有顶点并且不会跨越自身的路径.)

不幸的是,图表不能保证包含汉密尔顿路径或旅行推销员之旅.(例如,如果图形断开连接,它们显然不存在,但即使连接的图形也可能无法具有其中之一或两者:例如,任何1度顶点的图形都不能进行TSP巡视.)在这种情况下,如果您正在使用的TSP求解器可以找到不访问所有顶点的游览,您可以重复此操作直到覆盖所有顶点.如果做不到这一点,我会回到原来的算法上.

Answer 2

经过一段时间的研究，我最终得出以下算法： 不过，还有很多优化机会。