测试 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

现在有两个大陷阱：

如果浮点精度不够会发生什么计算 Orient3d ?
当所选线段恰好通过三角形的顶点或边 ?

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

现在对于2.，它更棘手，最好的方法是实现符号扰动[4]。简而言之，想法是 'disambiguate' 配置，其中 orient3d() returns 通过考虑点沿着由时间参数化的轨迹移动，并在时间趋于零时取位置的限制（另一种说法是：如果位置没有给出答案，请查看时间 t=0 时的 'speed vector'。原始参考文献 [4] 为 "point in polygon" 测试（问题的二维版本）给出了 orient2d() 的符号扰动。

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

[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

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

Testing whether a 3D point is inside a 3D polyhedron

triangulation

point-in-polygon