在体积/3D空间中验证一个点

Question

我一直在开发一个网格库。我想添加一个功能，能够检测一个点是否位于一个三维网格内部。

我尝试过类似射线投射的算法。

但问题是，在我的算法中，为了测试这个可能性，我将点沿着Z轴投影到一个平面上。如果投影后的点在四边形或三角形内，并且投影点的Z值大于原始点的Z值，我就会计算这个面。如果不是，我就不计算。如果总的计数是奇数，那就意味着这个点在三维体积内部。

ispointinside3Dspace(point,facelist)
{
for faces in the object:
{
  project the point onto the face along Z axis;
  if( projected point is within the face):
  {
        if( projectedpoint->z > point->z ):
        {
           face_hit++;
        }
   }
}
if(face_hit%2==1)
{
   return(1);
}
else
{
   return(0);
}
}

但是在这个算法中，如果投影点恰好等于那个面的一个顶点，它会被多次计算，因为同一个顶点会被四个四边形或多个三角形共享。有没有更好的算法呢？我该如何避免这种重复计数？如果我跳过投影点是面上顶点的可能性，我就得不到正确的结果。

Answer 1

遇到这种情况，通常的做法是对整个系统进行一些小的变换，比如旋转或者剪切变换。在某些情况下（至少在二维空间里），你甚至不需要知道具体的变换量，而是可以用符号的方式来处理，然后相应地调整算法。

在你的情况中，我可能会先检查一下你的光线是否击中了一个顶点（或者边，因为这两者会引发同样的问题，因为这种碰撞至少会被计算两次）。如果是这样的话，我会稍微调整一下你的投影方向，然后再进行测试。由于改变投影方向可能会对你的算法造成很大的影响，你也可以选择用一个小的旋转（使用预先计算好的旋转矩阵）来对系统中的所有点进行处理。