测量 2 个不规则形状的 3d 物体的交点
Measurement for intersection of 2 irregular shaped 3d object
我正在尝试实现一个 objective 函数来最小化 2 个不规则形状的 3d 对象的重叠。虽然最准确的重叠测量是相交体积，但它的计算成本太高，因为我正在处理具有 1000 多个面且不是凸面的复杂对象。
我想知道是否还有其他计算速度更快的 3d 对象之间的交点测量值？ 2 对测量的要求是： 1、测量为0时，不能有重叠； 2. measurement应该是一个标量（不是布尔值）表示重叠的程度，但是这个值不需要非常准确。
我正在考虑的可能测量包括某种 2D 相交表面积或 1D 穿透深度。或者，我可以使用基于样本的方法来估计体积，该方法对一个对象内的点进行采样并测试另一个对象中存在的点的百分比。但是我不知道在复杂的 3d 形状内采样点以及测试一个点是否被这种形状包围的计算成本是多少。
我将非常感谢关于此事的任何建议、代码或方程式。此外，如果您可以建议任何接受 .obj、.ply...等文件并执行 3D 几何计算的库（最好是 python 库），那将是很棒的！找到好的方法我也会post这里
更新：
我找到了一个很好的 python 库，名为 Trimesh，它执行我和其他人在这个 post 中提到的所有计算。它计算与 Blender 后端的精确交集体积；它可以体素化网格并计算共同占据的体素的体积；它还可以在一个网格中执行表面和体积点采样，并在另一个网格中测试点包含。我发现表面点采样和遏制测试（某种表面相交）和网格方法是最快的。
sample-based 方法是我首先尝试的方法。在联合边界 AABB 中生成一堆点，并将 A 和 B 中的点数除以 A 或 B 中的点数。（您可以根据您的用例调整此度量——效果不是很好当 A 和 B 的体积非常不同时。）要检查给定点是否在给定体积中，请使用交叉数测试，Google。有一些加速结构可以帮助进行此测试，但我的猜测是，可以为您提供合理准确度的样本数量低于从构建加速结构中整体受益所需的样本数量。
作为其变体，您可以检查线交点而不是点交点：生成随机（axis-aligned，为了提高效率）线，并测量它在 A、B、并且在 A 和 B 中。这需要比 point-in-polyhedron 更多的簿记，但会为您提供更好的 per-sample 信息，从而减少您最终遍历所有面孔的次数。
直接体素化：
如果面的大小相似（如果需要对较大的面进行三角剖分），您可以使用网格化方法：定义一个间距大小大于最长边的规则 3D 网格，并为每个体素存储一位。
然后对于网格的每个顶点，设置它所在的单元格的位（这只是截断坐标）。通过这样做，您将获得对象的边界作为连接的表面。您将通过 3D 泛洪填充算法从内部或外部像素获得体积估计值。 （外面会更容易，但一定要在物体周围留出一个体素的边距。）
使用此机器可以直接估算两个对象的体积以及交集或并集。成本将取决于面数和体素数。
我正在尝试实现一个 objective 函数来最小化 2 个不规则形状的 3d 对象的重叠。虽然最准确的重叠测量是相交体积，但它的计算成本太高，因为我正在处理具有 1000 多个面且不是凸面的复杂对象。
我想知道是否还有其他计算速度更快的 3d 对象之间的交点测量值？ 2 对测量的要求是： 1、测量为0时，不能有重叠； 2. measurement应该是一个标量（不是布尔值）表示重叠的程度，但是这个值不需要非常准确。
我正在考虑的可能测量包括某种 2D 相交表面积或 1D 穿透深度。或者，我可以使用基于样本的方法来估计体积，该方法对一个对象内的点进行采样并测试另一个对象中存在的点的百分比。但是我不知道在复杂的 3d 形状内采样点以及测试一个点是否被这种形状包围的计算成本是多少。
我将非常感谢关于此事的任何建议、代码或方程式。此外，如果您可以建议任何接受 .obj、.ply...等文件并执行 3D 几何计算的库（最好是 python 库），那将是很棒的！找到好的方法我也会post这里
更新： 我找到了一个很好的 python 库，名为 Trimesh，它执行我和其他人在这个 post 中提到的所有计算。它计算与 Blender 后端的精确交集体积；它可以体素化网格并计算共同占据的体素的体积；它还可以在一个网格中执行表面和体积点采样，并在另一个网格中测试点包含。我发现表面点采样和遏制测试（某种表面相交）和网格方法是最快的。
sample-based 方法是我首先尝试的方法。在联合边界 AABB 中生成一堆点，并将 A 和 B 中的点数除以 A 或 B 中的点数。（您可以根据您的用例调整此度量——效果不是很好当 A 和 B 的体积非常不同时。）要检查给定点是否在给定体积中，请使用交叉数测试，Google。有一些加速结构可以帮助进行此测试，但我的猜测是，可以为您提供合理准确度的样本数量低于从构建加速结构中整体受益所需的样本数量。
作为其变体，您可以检查线交点而不是点交点：生成随机（axis-aligned，为了提高效率）线，并测量它在 A、B、并且在 A 和 B 中。这需要比 point-in-polyhedron 更多的簿记，但会为您提供更好的 per-sample 信息，从而减少您最终遍历所有面孔的次数。
直接体素化：
如果面的大小相似（如果需要对较大的面进行三角剖分），您可以使用网格化方法：定义一个间距大小大于最长边的规则 3D 网格，并为每个体素存储一位。
然后对于网格的每个顶点，设置它所在的单元格的位（这只是截断坐标）。通过这样做，您将获得对象的边界作为连接的表面。您将通过 3D 泛洪填充算法从内部或外部像素获得体积估计值。 （外面会更容易，但一定要在物体周围留出一个体素的边距。）
使用此机器可以直接估算两个对象的体积以及交集或并集。成本将取决于面数和体素数。