使用另一个网格切割网格的算法
Algorithm for cutting a mesh using another mesh
我正在寻找一种算法，给定两个网格可以使用另一个来剪切一个。
最简单的形式是使用平面裁剪网格。我已经通过遵循类似于 here.
所描述的内容来实现它
它所做的基本上是检查相对于平面的所有网格顶点和三角形（给出了平面的法线和点）。如果三角形完全位于平面上方，则保持不变。如果它完全落在平面下方，则将其丢弃。如果三角形的某些边与平面相交，则计算与平面的交点并将其添加为新顶点。最后在网格被切割的地方为孔生成一个盖子。
问题在于算法假定平面是无限的，因此其路径中的任何内容都会被裁剪掉。在最简单的形式中，我需要在不假设 "infinite" 大小的平面的情况下对此进行扩展。
为了澄清，假设我们有一张桌子的 3D 模型，上面有 2 个盒子。这些盒子是相邻的（但不接触或堆叠）。用户将在第一个框下方定义一个有限宽度和高度的切割平面并执行切割。我们最终得到一个桌面模型（网格），上面有一个盒子和另一个可以自由移动的盒子（网格）around/manipulated。
在一般形式中，我希望用户能够为 he/she 想要与桌面模型分离并使用该边界框执行切割的框定义边界框。
如果我可以将我已有的算法扩展到具有有限大小平面的算法，那现在就很好了。
您正在寻找的是具有任意网格的建设性实体 geometry/boolean 算法。它比通过无限平面切割网格要复杂得多。
Trumbore 和 Hughes 的 Constructive Solid Geometry for Polyhedral Objects 是该领域最早和最简单的研究之一，也是一个很好的起点。
http://cs.brown.edu/~jfh/papers/Laidlaw-CSG-1986/main.htm
来自原文：
更详细的解决方案使用各种数据结构扩展了这个主题。
操作的真正复杂性在于将一个三角形对另一个三角形进行切片的切片算法。实现健壮的 CSG 的噩梦在于数值精度。当你涉及比立方体复杂得多的对象时，这很容易 运行 进入切片刚好靠近顶点的情况（此时你有一个艰难的决定是否合并新的分割顶点之前进行更多拆分），其中多边形共面（或几乎共面）等
因此，我建议一开始宁可使用精度非常高的浮点数，甚至可能高于双精度，以专注于让某些东西正确、稳健地工作。您可以稍后进行优化（第一步应该是使用像 octree/kd-tree/bvh 这样的加速器），但是您可以在第一次迭代中通过这种方式避免很多麻烦。
如果您专注于光线追踪器而不是建模软件，那么在渲染时实现起来要简单得多，例如使用光线追踪器，要进行这种任意裁剪，您所要做的就是假装用于从另一个对象中减去的对象在剔除过程中翻转了多边形，例如在射线层面上稳健地求解很容易，但在几何层面上稳健地求解就难多了。
如果您负担得起，您可以做的另一件事可以让您的生活变得更轻松，那就是对对象进行体素化，找到 subtractions/additions/unions 体素，然后将体素转换回网格。这更容易变得健壮，但更难有效地完成，如果你想要比行进立方体提供的更好的结果，体素->多边形转换可能会涉及到很多。
这是一个很难做到极致的领域，需要毅力，所以才会有这样的事情存在的原因：http://carve-csg.com/about.
如果有人感兴趣，目前CGAL库中有解决这个问题的方法。它允许使用另一个网格作为包围体来裁剪一个三角形网格。可以找到使用示例 here.
我正在寻找一种算法，给定两个网格可以使用另一个来剪切一个。
最简单的形式是使用平面裁剪网格。我已经通过遵循类似于 here.
所描述的内容来实现它
它所做的基本上是检查相对于平面的所有网格顶点和三角形（给出了平面的法线和点）。如果三角形完全位于平面上方，则保持不变。如果它完全落在平面下方，则将其丢弃。如果三角形的某些边与平面相交，则计算与平面的交点并将其添加为新顶点。最后在网格被切割的地方为孔生成一个盖子。
问题在于算法假定平面是无限的，因此其路径中的任何内容都会被裁剪掉。在最简单的形式中，我需要在不假设 "infinite" 大小的平面的情况下对此进行扩展。
为了澄清，假设我们有一张桌子的 3D 模型，上面有 2 个盒子。这些盒子是相邻的（但不接触或堆叠）。用户将在第一个框下方定义一个有限宽度和高度的切割平面并执行切割。我们最终得到一个桌面模型（网格），上面有一个盒子和另一个可以自由移动的盒子（网格）around/manipulated。
在一般形式中，我希望用户能够为 he/she 想要与桌面模型分离并使用该边界框执行切割的框定义边界框。
如果我可以将我已有的算法扩展到具有有限大小平面的算法，那现在就很好了。
您正在寻找的是具有任意网格的建设性实体 geometry/boolean 算法。它比通过无限平面切割网格要复杂得多。
Trumbore 和 Hughes 的 Constructive Solid Geometry for Polyhedral Objects 是该领域最早和最简单的研究之一，也是一个很好的起点。
http://cs.brown.edu/~jfh/papers/Laidlaw-CSG-1986/main.htm
来自原文：
更详细的解决方案使用各种数据结构扩展了这个主题。
操作的真正复杂性在于将一个三角形对另一个三角形进行切片的切片算法。实现健壮的 CSG 的噩梦在于数值精度。当你涉及比立方体复杂得多的对象时，这很容易 运行 进入切片刚好靠近顶点的情况（此时你有一个艰难的决定是否合并新的分割顶点之前进行更多拆分），其中多边形共面（或几乎共面）等
因此，我建议一开始宁可使用精度非常高的浮点数，甚至可能高于双精度，以专注于让某些东西正确、稳健地工作。您可以稍后进行优化（第一步应该是使用像 octree/kd-tree/bvh 这样的加速器），但是您可以在第一次迭代中通过这种方式避免很多麻烦。
如果您专注于光线追踪器而不是建模软件，那么在渲染时实现起来要简单得多，例如使用光线追踪器，要进行这种任意裁剪，您所要做的就是假装用于从另一个对象中减去的对象在剔除过程中翻转了多边形，例如在射线层面上稳健地求解很容易，但在几何层面上稳健地求解就难多了。
如果您负担得起，您可以做的另一件事可以让您的生活变得更轻松，那就是对对象进行体素化，找到 subtractions/additions/unions 体素，然后将体素转换回网格。这更容易变得健壮，但更难有效地完成，如果你想要比行进立方体提供的更好的结果，体素->多边形转换可能会涉及到很多。
这是一个很难做到极致的领域，需要毅力，所以才会有这样的事情存在的原因：http://carve-csg.com/about.
如果有人感兴趣，目前CGAL库中有解决这个问题的方法。它允许使用另一个网格作为包围体来裁剪一个三角形网格。可以找到使用示例 here.