验证体积/3D 空间中的点

Question

我一直致力于网格库的开发。我想添加一个功能，以便它可以检测某个点是否位于 3D 网格内部。

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

但问题是， 在我的算法中，为了测试可能性，我将点沿 Z 轴投影到平面上。如果投影点在四边形/三边形内并且投影点的 z 值大于原始点的 Z 值，我将计算面。如果不是，我不会。如果总计数为奇数，则意味着该点位于 3D 体积内。

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);
}
}

如果该算法中的投影点等于该面上的顶点，则它将被多次计数，因为相同的顶点将被 4 个四边形/许多三角形共享。是否有更好的算法。 我应该如何避免这种过度计算？？？如果我跳过投影点作为面上顶点的可能性。，我将不会得到正确的结果。

Answer 1

处理这种情况的通常方法是对整个系统应用小的变换（旋转或剪切变换）。在某些情况下（至少在 2d 中），您甚至不需要知道变换的确切数量，但您可以象征性地执行此操作并相应地调整算法。

在你的情况下，我可能会首先检查你的光线是否击中顶点（或边缘，这会引起相同的问题，因为这次击中至少会被计算两次）。如果是这样，我会稍微修改您的投影方向，然后再次进行测试。由于更改投影方向可能需要对算法进行重大更改，因此您可以通过对系统的所有点应用小旋转（使用预先计算的旋转矩阵）来实现此目的。