测试 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() 的公开实现。我自己的编程库 Geogram 中也有一个实现 [3]。

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

注意：如果你很懒并且不想实现符号扰动，则可以在每次 orient3d() 测试之一返回零时选择一个随机方向（然后你不能保证它不会永远搜索，但实际上它是极不可能发生）。无论如何，我建议仅将其用于原型设计，并最终实现符号扰动。

[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/itation.cfm?id=77639