c++ - 点的法线通过其在 STL 网格模型上的位置

Question

谁能告诉我估计 CAD STL 几何体上某个点的法线的最佳方法？

这不完全是代码问题，而是效率和方法问题。

我使用了一种方法，将需要估计其法线的点与网格中的所有三角形进行比较，并使用重心坐标测试检查它是否位于三角形内。 (如果每个重心坐标的值都在 0 和 1 之间，则该点在里面。)这篇文章对此进行了解释

https://math.stackexchange.com/questions/4322/check-whether-a-point-is-within-a-3d-triangle

然后我计算该三角形的法线以获得法线点。

我的方法的问题是，如果我有大约 1000 个点，并且如果网格有 500 个三角形，那就意味着要进行一些 500X1000 检查。这需要很多时间。

我可以使用一种有效的数据结构或方法来查明直角三角形吗？还是可以完成工作的图书馆？

Answer 1

一个相对简单的解决方案是使用网格:分解 3D 体素阵列中的空间，并为每个体素保留一个干扰它的三角形列表。

我所说的干扰是指体素和三角形的边界框之间存在非空交集。 (当您知道边界框时，可以直接判断它覆盖了哪些体素。)

当你想测试一个点时，找到它所属的体素并与三角形列表进行比较。您将实现等于 N/M 的加速比，其中 M 是每个体素的平均三角形数。

应谨慎选择体素大小。太小会导致数据结构太大；太大会使该方法无效。如果可能，调整为每个体素“几个”三角形。 (使用平均三角形大小 - 双面积的平方根 - 作为起始值。)

为了提高效率，您可以使用 3D 多边形裁剪算法(而不是单纯的边界框测试)计算三角形和体素之间的精确交点，但这实现起来更复杂。