language-agnostic - 确定三角形与平面的交点

Question

我有一个三角形和一个平面（在3维空间中），如何计算两个相交的线段，如果没有相交，则需要检测这种情况。

我正在寻找的最终结果是两个3维向量，它们定义了线段的起点和终点。

为了帮助您一点，我已经计算了脸部平面和平面之间的相交光线，我只需要找到端点以将该光线裁剪为线段即可。

对于那些喜欢阅读代码的人：

Face face;        //a face, defined by 3 points
Plane plane;      //a plane, defined by a normal vector and a distance
Ray intersection; //a ray, defined by a point and a direction, initialised to the intersection of the face plane and the face

Segment s = CalculateSegment(face, plane, intersection); //this method needs defining

Answer 1

这是一些建议的伪代码。首先是简单版本，后来是更强大的版本（只是为了帮助将原理与新特性区分开）。
简单版本：

// Assume the plane is given as the equation dot(N,X) + d = 0, where N is a (not
// neccessarily normalized) plane normal, and d is a scalar. Any way the plane is given -
// DistFromPlane should just let the input vector into the plane equation.

vector3d planeN;
float planeD;

float DistFromPlane( vector3d P)
{
// if N is not normalized this is *not* really the distance, 
// but the computations work just the same.
    return dot(planeN,P) + planeD;
}

bool GetSegmentPlaneIntersection( vector3d P1, vector3d P2, vector3d& outP)
{
  float d1 = DistFromPlane(P1),
        d2 = DistFromPlane(P2);

  if (d1*d2 > 0)  // points on the same side of plane
     return false;

  float t = d1 / (d1 - d2); // 'time' of intersection point on the segment
  outP = P1 + t * (P2 - P1);

  return true;
}

void TrianglePlaneIntersection(vector3d triA, vector3d triB, vector3d triC,
                               vector3dArray& outSegTips)
{
   vector3d IntersectionPoint;
   if( GetSegmentPlaneIntersection( triA, triB, IntersectionPoint))
     outSegTips.Add(IntersectionPoint);

   if( GetSegmentPlaneIntersection( triB, triC, IntersectionPoint))
     outSegTips.Add(IntersectionPoint);

   if( GetSegmentPlaneIntersection( triC, triA, IntersectionPoint))
     outSegTips.Add(IntersectionPoint);
}

现在增加一些健壮性：
[编辑：增加了平面上单个顶点情况的明确考虑]

vector3d planeN;
 float planeD;

float DistFromPlane( vector3d P)
{
    return dot(planeN,P) + planeD;
}

void GetSegmentPlaneIntersection( vector3d P1, vector3d P2, vector3dArray& outSegTips)
{
  float d1 = DistFromPlane(P1),
        d2 = DistFromPlane(P2);

  bool  bP1OnPlane = (abs(d1) < eps),
        bP2OnPlane = (abs(d2) < eps);

  if (bP1OnPlane)
     outSegTips.Add(P1);

  if (bP2OnPlane)
     outSegTips.Add(P2);

  if (bP1OnPlane && bP2OnPlane)
     return;

  if (d1*d2 > eps)  // points on the same side of plane
     return;

  float t = d1 / (d1 - d2); // 'time' of intersection point on the segment
  outSegTips.Add( P1 + t * (P2 - P1) );
}

void TrianglePlaneIntersection(vector3d triA, vector3d triB, vector3d triC,
                               vector3dArray& outSegTips)
{
   GetSegmentPlaneIntersection( triA, triB, outSegTips));
   GetSegmentPlaneIntersection( triB, triC, outSegTips));
   GetSegmentPlaneIntersection( triC, triA, outSegTips));

   RemoveDuplicates(outSegTips);  // not listed here - obvious functionality 
}

希望能给出一个主意，但仍有许多潜在的优化方法。例如，如果要为大型网格中的每个三角形计算这些相交，则可以为每个顶点计算并缓存一次DistanceFromPlane，然后针对该顶点参与的每个边检索它。还可以进行更高级的缓存，取决于您的方案和数据表示形式。