曲面网格三角形:查询空间

Question

我有一个三角形的表面网格。假设表面网格是封闭的。

​

​

我打算做一个空间查询，以确定是否在我的曲面网格中。空间单元可以用包围框、体素或任何其他空间工具来表示。

• 有哪些数据结构可用于执行上述查询？
• 有什么算法可以从零开始实现查询？
• 有现成的库可用吗？

谢谢=)

Answer 1

我不认为R-树会直接帮助找到封闭网格中的内容。

如果数据有单独的“气泡”，由网格包围的空间块，这些数据可以用包围框表示，并放入R-树索引。这将有助于找出哪些气泡可能与查询对象相交，这样就可以进行进一步的检查(实际上，它将消除不能相交的气泡，因此不需要检查它们)。

如果您可以以某种方式将网格中的空间分解为较小的块，则可以将这些块编入索引。如果它们重叠或扩展到网格之外，则确定。

Answer 2

如果网格是完全封闭的，对于单个点，您可以使用射线追踪从点到任意方向拍摄一条射线，并查看它击中网格的次数。如果它碰到奇数，它就在里面，如果它碰到偶数，它就在外面。然而，对于其他形状，您可能需要碰撞检测。

现有的库将取决于您所使用的平台/编程语言，但是如果您有选择的余地，可以从统一开始

正如安东宁在他们的回答中提到的，一个R树索引将帮助你，但不会直接检查一个点或其他形状是否在你的网格内。如果你能把网格内的空间分解成方框，R-树将帮助你快速检查你的点或形状在网格内的正面情况。

Answer 3

VDB:空心与填充

在下面的视频中，我们演示了如何通过Houdini创建两种类型的VDB：

• 距离：中空卷:在外部几何学上创建一个体素外壳
• Fog:实心体积：用体素填充几何

https://youtu.be/jqNRu8BYYXo?t=259

含蓄

这意味着VDB可以标记空心体素和填充体素。但我不知道如何用voxel代码编程。