algorithm - 两个网格之间非常快的 bool 差异

Question

假设我有一个静态物体和一个可以移动和旋转的可移动物体，快速计算这两个网格差异的最佳方法是什么？

这里的精度不是那么重要，速度很重要，因为我必须在主循环的更新阶段使用它。

也许，考虑到严格的时间限制，直接修改静态对象的顶点和三角形可能是首选。在这里应该首选体素吗？

编辑:用例是木板(平行六面体)和铣削工具(旋转轮廓，类似于 these)的交互式查看器。
铣刀可以旋转，可以不同角度(5轴)定向工作。

编辑 2:铣刀不能刺穿木材。

编辑 3:面板可以大到 6000x2000mm，铣刀可以小到 3x3mm。

Answer 1

如果您需要最佳性能，那么通用 CSG 方法对您来说可能太慢(但仍取决于网格和目标硬件)。

您可以尝试找到一些专门的算法，为您的特定网格编码。假设您有两个立方体 - 一个是“墙”，第二个是“窗口” - 那么使用您的自定义代码计算生成的网格比完整的 CSG 更容易/更快。不幸的是你没有说任何关于你的网格的事。

您也可以尝试将其变成二维问题，使用一些简化的网格来计算“看起来像预期的”结果。

如果网格的移动受到某种限制，您可以预先计算不同网格组合的全部或部分结果，以便在运行时使用。

您可以在预计算阶段使用 BSP 或 Octrees 等空间分区来划分网格。通过这种方式，您可以将一个大问题拆分为许多较小的问题，这些问题可能会更快地计算或至少使解决方案成为多线程的。

您已经谈到了体素 - 如果您对它们的外观和限制没有意见，您可以对两个网格进行体素化，然后只读取并混合两个体素值，而不是一个。然后，您将使用 Marching Cubes 等算法对其进行三角测量。

这些只是一些一般性的想法，但我们需要更好的信息来为您提供更多帮助。

编辑:

根据您的描述，您似乎正在为一些浅浮雕建模，因此您可以使用 Relief Mapping伪造这种效果。它基于存储为纹理的高度图，因此您只需更新纹理的几个像素并渲染一个平面。与其他方法相比，它应该相当快，缺点是它基于高度图，因此您无法获得 T 型槽或燕尾槽切割器会创建的形状。

如果您想要真实的几何形状，那么我将从一个简单的平面开始作为您的面板(不需要完整的 3D，只需要一个前表面)并用 2D 网格划分它。网格元素应略大于钻孔尺寸，每个元素都是一个单独的网格。在框架更新中，您将切割一个或最多 4 个用钻头接触的元素。多亏了这个网格，您所有的切割操作都将以非常简单的网格运行，因此它们可以按照您的预期速度进行。您还可以在单​​独的线程中剪切所有当前元素。切割完成后，您将仅将当前修改的元素上传到 GPU，因此您最终可能会得到相当复杂的网格，但每帧的修改很小。