Jef*_*ins 14 algorithm intersection point mesh
什么是用于确定点是否在3D网格内的快速算法？为简单起见,您可以假设网格是所有三角形并且没有孔.
到目前为止我所知道的是,确定光线是否穿过网格的一种流行方法是计算光线/三角形交叉点的数量.它必须很快,因为我将它用于触觉医疗模拟.所以我无法测试光线交叉的所有三角形.我需要某种散列或树数据结构来存储三角形,以帮助确定哪个三角形是相关的.
另外,我知道如果我对顶点进行任意2D投影,则需要进行简单的点/三角交点测试.但是,我仍然需要知道哪些三角形是相关的,此外,哪些三角形位于该点的前面并且仅测试这些三角形.
Jef*_*ins 16
我解决了自己的问题.基本上,我采用任意2D投影(抛出其中一个坐标),并将三角形的AABB(轴对齐边界框)散列为2D数组.(由titus提到的一组3D立方体是过度的,因为它只会给你一个恒定的因子加速.)使用2D数组和你正在测试的点的2D投影来获得一小组三角形,你做了一个3D射线/三角交叉测试(参见3D中的光线,分段,平面和三角形的交点)并计算光线交叉处的三角形数量,其中z坐标(抛出的坐标)大于z坐标点.偶数个交叉点意味着它在网格之外.奇数个交叉点意味着它位于网格内部.这种方法不仅速度快,而且易于实现(这正是我所寻求的).