c++ - 切片网格的算法或软件

Question

切片3D网格的正确方法是什么？网格都是封闭的表面，切片必须是网格内部的二进制图像。因此，例如，代表球体和切片图像的网格是实心圆的网格。

我正在寻找可以集成到当前C++项目中的软件库或算法。

Answer 1

我的开源游戏库包含网格切片的实现。它可以与Irrlicht api一起使用，但是可以重写以使用其他API进行适当的工作。您可以根据BSD许可的条款使用代码，或从中学习自己的实现。

参见this file for an implementation of mesh slicing中的MeshTools::splitMeshZ。

如果您只想了解算法，这是我所做工作的高级描述:

我最初想到使用轴对齐的边界框来指定在哪里切割网格。这是有问题的，因为它引入了许多特殊情况。例如，与盒子一角交叉的边缘可以分为三部分，而不仅仅是两部分。

使用平面将网格切成左网格和右网格可以减少特殊情况的数量，因为一条边在该平面的一侧或另一侧，或者与该平面相交，因此被切成两截件。

可以通过以下方法简单地进行任何所需的切割配置:切割一次，获取一个所得的网格，然后在另一个位置再次切割，依此类推。特别是在您在本节中描述的情况下，可以通过切掉一个球体的一半，将平面移开一点，然后切掉另一半，只留下一条细带，从而从球体上切出一个圆。 (您不能使用我编写的代码将网格切成几乎没有深度，但是您可以将网格切成您将浮点相等阈值设置为的任何值。我想我在代码中任意选择了0.001。)

使用类似的逻辑，可以使用固定平面实现切割平面的任何所需角度；您只需要变换网格以使其相对于固定的切割平面旋转，然后将结果变换回去即可。 (对于我的游戏，我只需要垂直于XY平面的切口，所以为简单起见，我只允许设置切口的Z值，并假定切口位于该Z位置。)

好的，现在我们已经简化了问题，算法还不错:

起始条件:您有一架切割机。您有一组源三角形。您有两个多边形的目标位置(不是三角形；可以通过切割三角形来生成四边形)。这两个目标集称为“左”和“右”。

过程:遍历三角形的三个点。计算少于切割平面的点数。我将那些小于切割平面Left的那些称为大于切割平面Right的那些。只有少数情况:

所有三角形点都在左边:将三角形放在左边集

所有点都在右边:将三角形放在右边集

一个点是“左”，其他点是“右”:如果您在两个边缘上切一个三角形，而您持有其中一个点，则最终会持有一个较小的三角形。在由左点和边缘与平面相交的两个点组成的左集中放置一个三角形。在“Right”集中放一个四边形(请参阅下一种情况)。

左为两点，右为一点。如果您握住三角形的一条边并在其他两条边上切开，则您将保持梯形。将四边形放到由您的手上两点组成的左集合中，再加上穿过切口的两个点。在右边的集合中放置一个三角形(上面案例的镜像)。

完成后，通过在最短部分上添加链接将四边形变成三角形。

而已。那是基本算法。实际的代码会处理其他几种情况，例如如果一条边与切角完全相等，该怎么办，如果一个三角形正好在边上，不添加退化的多边形(例如没有主体的点)等等。

杂项问题(所有链接代码均涵盖):

不要过分复杂化数学运算，以便在边缘与切割平面交叉的位置进行LERP。它不需要完整的线性插值，实际上只是Highschool Algebra II:超越速度乘以

缓存生成的(LERP'ed)点是有利的，这样在未切割的网格中共享顶点的三角形将在切割的网格中共享相应的新顶点。

如果要保留顶点共享，并且使用的是三角形索引缓冲区，那么不幸的是，当您第一次生成要放置在Left和Right集中的形状时，尚不知道索引。我使用一个称为“PossibleVertex”的类来表示将来的三角形索引号。

如果要显示网格，则缠绕顺序很重要。仔细考虑如何进行编码，可以确保所得的多边形与它们所使用的三角形使用相同的缠绕顺序。在对四边形进行三角剖分时，这特别棘手。我不记得详细信息，但所有内容都在链接的代码中处理。

在我的游戏中，我想制作一条扁平的丝带来连接两个切开的网格。这就是为什么splitMeshZ生成3个网格而不是两个网格的原因。您可以使用中间网格，也可以忽略它。