triangulation - 测试 3D 点是否在 3D 多面体内部

Question

给定一个 3D 多面体，其边界由三角网格表示，我如何实现一种算法来确定给定的 3D 点是否属于多面体的内部？

Answer 1

有几种方法可以实现这个功能。

最简单的方法是创建一条从点开始指向任意方向的无限射线(或很长的线段)，然后计算射线与三角形之间的交点数。如果交点的个数是奇数，则该点在多面体内部。

Inside(Polyhedron P, point q)
   Segment S = [q, q+(0,0,1e30)]
   count = 0
   For each triangle T of P
      If Intersect(S,T)
            count = count + 1
      End if
   End for
   return odd(count)
End

现在计算线段和三角形之间是否存在交集的函数:

Intersect([q1,q2],(t1,t2,t3))
  s1 = orient3d(q1,t1,t2,t3)
  s2 = orient3d(q2,t1,t2,t3)
  // Test whether the two extermities of the segment
  // are on the same side of the supporting plane of
  // the triangle
  If(s1 == s2) 
     return false
  End if
  // Now we know that the segment 'straddles' the supporing
  // plane. We need to test whether the three tetrahedra formed
  // by the segment and the three edges of the triangle have
  // the same orientation
  s3 = orient3d(q1,q2,t1,t2)
  s4 = orient3d(q1,q2,t2,t3)
  s5 = orient3d(q1,q2,t3,t1)
  return (s3 == s4 AND s4 == s5)
End

最后，orient3d函数:

   Orient3d(a,b,c,d)
      // Computes the sign of the signed volume  
      // of the tetrahedron (a,b,c,d)
      return Sign( dot(cross(b-a,c-a),d-a) )
   End

现在有两个大陷阱:

1. 如果浮点精度不够会发生什么情况计算 Orient3d ?

2. 当所选线段恰好通过三角形的顶点还是边？

对于 1.，必须使用任意精度的算术 [1]。在 [2] 中，引用文献 [1] (Jonathan Shewchuk) 的作者公开了 orient3d() 的实现。我自己的编程库 [3] Geogram 中也有一个实现。

现在对于 2.，它更棘手，最好的方法是实现符号扰动 [4]。简而言之，这个想法是通过考虑点沿着由时间参数化的轨迹移动并在时间趋于零时取位置限制来“消除”orient3d() 返回零的配置(另一种说法:如果位置没有给出答案，请查看时间 t=0 时的“速度矢量”)。原始引用文献 [4] 给出了 orient2d() 的符号扰动，用于“多边形中的点”测试(问题的 2D 版本)。

注意:如果您很懒惰并且不想实现符号扰动，您可以在每次 orient3d() 测试之一返回零时选择一个随机方向(那么您不能保证它不会永远搜索，但在实践中它不太可能发生)。无论如何，我建议仅将其用于原型(prototype)制作，并在最后实现符号扰动。

[1] https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf

[2] https://www.cs.cmu.edu/~quake/robust.html

[3] http://alice.loria.fr/software/geogram/doc/html/index.html

[4] http://dl.acm.org/citation.cfm?id=77639