测量两个不规则形状的三维物体的交集

Question

我正在尝试实现一个目标函数，它最小化了两个不规则形状的3D物体之间的重叠。虽然交集体积是最准确的重叠度量，但由于我处理的是具有1000多个面且不是凸面的复杂对象，因此计算成本太高。

我想知道是否有其他更快速计算的3D物体交集度量方法？度量的两个要求是：1.当度量为0时，没有重叠；2.度量应该是一个标量（而不是布尔值），表示重叠程度，但这个值不需要非常精确。

我正在考虑的可能的度量包括某种2D交集面积，或者1D穿透深度。或者，我可以使用基于样本的方法估计体积，在一个物体内采样点并测试存在于另一个物体中的点的百分比。但我不知道在复杂的3D形状内采样点以及测试点是否被这样的形状包围会有多大的计算成本。

我将非常感激在这个问题上的任何建议、代码或方程式。如果您能建议任何接受.obj、.ply等文件并执行3D几何计算的库（最好是Python库），那就太棒了！如果我找到一个好的方法，我也会在这里发布。

更新： 我找到了一个很好的Python库叫做Trimesh，它执行了我和其他人在这个帖子中提到的所有计算。它使用Blender后端计算确切的交集体积；它可以对网格进行voxelize并计算共占用的voxels的体积；它还可以在一个网格内执行表面和体积点采样，并测试点包含在另一个网格内。我发现表面点采样和包含测试（类似于表面交集）以及网格方法是最快的。

- Susie

---

该问题不涉及代码，所以纯粹是数学问题。最后一部分询问库，两者都不属于SO的主题。 - Klaus D.

@KlausD。编程不仅仅是变量和分号。 - Sneftel

Answer 1

通过直接体素化：

如果面的大小相似（必要时三角化大面），您可以使用网格化方法：定义一个间距大于最长边的常规3D网格，并在每个体素中存储一个比特。

然后，对于网格的每个顶点，设置所包含的单元格的位（这只需要截断坐标）。通过这样做，您将获得对象的边界作为连接表面。您将通过3D泛洪算法从内部或外部像素获得体积的估计值。（外部将更容易，但请确保在对象周围留出一个体素边缘。）

使用此机制轻松估算两个对象的体积以及交集或并集。成本将取决于面数和体素数。

- user1196549

---

谢谢您的回答！我个人认为体素方法是最计算效率高的方法之一，特别是您可以控制网格分辨率。而且，由于我只对交集体积感兴趣，而不关心两个网格的比例，所以我不需要担心两个网格的并集或大小比较，我只需使用共同占用的体素数量*体素的体积即可。 - Susie

Answer 2

我会尝试基于样本的方法。在联合边界框（AABB）中生成一堆点，并将A和B中的点数除以A或B中的点数。 （您可以根据您的用例调整此度量-当A和B具有非常不同的体积时，它不起作用。）要检查给定点是否在给定体积中，请使用交叉数量测试，Google一下即可。 有加速结构可以帮助进行此测试，但我猜测，为了获得合理的准确性所需的样本数量要比构建加速结构所需的样本数量低。

作为此方法的一个变体，您可以检查线交集而不是点交集：生成随机（轴对齐，以提高效率）线，并测量其中多少包含在A、B和A和B中。 这需要更多的记录，但将为您提供更好的逐个样本信息，从而减少您迭代所有面的次数。

- Sneftel