首页 文章

用于确定点是否在3D网格内的算法

提问于
浏览 次
13

什么是用于确定点是否在3D网格内的快速算法？为简单起见，您可以假设网格是所有三角形并且没有孔 .

到目前为止我所知道的是，确定光线是否穿过网格的一种流行方法是计算光线/三角形交叉点的数量 . 它必须很快，因为我将它用于触觉医疗模拟 . 所以我无法测试光线交叉的所有三角形 . 我需要某种散列或树数据结构来存储三角形，以帮助确定哪个三角形是相关的 .

另外，我知道如果我对顶点进行任意2D投影，则需要进行简单的点/三角交点测试 . 但是，我仍然需要知道哪些三角形是相关的，此外，哪些三角形位于该点的前面并且仅测试这些三角形 .

algorithm intersection point mesh ray

3 回答

  • 0

    我解决了自己的问题 . 基本上，我采用任意2D投影（抛出其中一个坐标），并将三角形的AABB（轴对齐边界框）散列为2D数组 . （由titus提到的一组3D立方体是过度的，因为它只会给你一个恒定的因子加速 . ）使用2D数组和你正在测试的点的2D投影来获得一小组三角形，你做了一个3D射线/三角形相交测试（参见Intersections of Rays, Segments, Planes and Triangles in 3D）并计算光线交点的三角形数量，其中z坐标（抛出的坐标）大于点的z坐标 . 偶数个交叉点意味着它在网格之外 . 奇数个交叉点意味着它位于网格内部 . 这种方法不仅速度快，而且易于实现（这正是我所寻求的） .

    回复于
  • 3

    只有当您有许多查询来证明构造数据结构的时间时，这种算法才是有效的 .

    将空间划分为相同大小的立方体（我们包含任何内容 . 执行维基百科上显示的光线投射算法，但是如果线条与每个三角形相交，则测试所有与线条相交的立方体，然后执行光线测试只使用这些立方体中的三角形进行投射 . 注意不要多次测试同一个三角形，因为它存在于两个立方体中 .
    找到合适的立方体大小是棘手的，它应该't be neither to big or too small. It can only be found by trial and error. Let'说 number of cubes 是 c 而 number of triangles 是 t .
    多维数据集中的三角形平均数为 t/c
    k 是与光线相交的立方体的平均数
    线 - 立方体交叉点这些立方体中的线 - 三角形交叉点必须是最小的
    c+k*t/c=minimal => c=sqrt(t*k)
    在 c=sqrt(t*k) 为真之前，您必须测试多维数据集大小的值
    一个很好的起始猜测立方体的大小将是 sqrt(mesh width)
    为了获得一些视角，对于1M三角形，您将测试1k交叉点的顺序

    回复于
  • 15

    Ray Triangle Intersection在准确性方面似乎是一个很好的算法discussion . Wiki有更多算法 . 我在这里链接它，但你可能已经看过了 .

    您可以通过维持点与它们构成顶点的平面之间的关系矩阵来表达吗？该主题似乎是学术界的一个调查主题 . 不确定如何访问与此相关的更多讨论 .

    回复于

相关问题