3d计算几何：空间中两个三角形求取交线的算法

sandartist

[这个贴子最后由sandartist在 2009/12/14 04:35pm 第 1 次编辑]

首先判断两个三角形是否在一个平面内：
一 如果在同一个平面内，那么空间中两个三角形求取交线的问题就变成了平面中两个三
角形求取交线的问题了，求取的过程：三角形S1每条边和三角形S2每条边分别求取交点，
有可能会出现重复的点，排序的时候删除掉，最后将所有的交点进行spline化（按照求取
凸包的算法进行spline化，因为最多六个交点的时候是一个凸六边形），这样就将交线求
出了。
二 如果不在同一个平面内的话，问题首先简化为三角形S1每条边和三角形S2求取交点，
然后三角形S2每条边和三角形S1求取交点，大部分情况是，如果有两个不重复交点的话，
那么这两个交点的连线就他们的交线，特殊情况：顶点与顶点相交，顶点和边相交，边和
边相交，顶点在另一个三角形内部相交，边在另一个三角形内部。
   空间中的线段和三角面片的求交过程：首先判断过线段的直线与三角形所在平面的交
点，然后判断交点是否在线段内。
空间中直线和三角面片求交的实现
class CVector  
{
public:
union
{
  float vec[3];
  struct  { float x,y,z;};
};
}
class CCommonTools  
{
public:
CCommonTools();
virtual ~CCommonTools();
public:
static bool ValidPoint(CVector &LinePoint, CVector &LineV,
                                  CVector &TrianglePoint1, CVector &TrianglePoint2, CVector &TrianglePoint3,CVector &result);
static float Area(float a, float b, float c);
static float Distance(CVector &p1, CVector &p2);
};
///////////////////////////////
CCommonTools::CCommonTools()
{
}
CCommonTools::~CCommonTools()
{
}
//计算p1到p2的距离的平方
float CCommonTools:istance(CVector &p1, CVector &p2)
{
float dist;
dist = ((p2.x-p1.x)*(p2.x-p1.x)
  + (p2.y-p1.y)*(p2.y-p1.y)
  + (p2.z-p1.z)*(p2.z-p1.z));
return (float)sqrt(dist);
}
//利用海伦公式求变成为a,b,c的三角形的面积
float CCommonTools::Area(float a, float b, float c)
{
float s = (a+b+c)/2;
return (float)sqrt(s*(s-a)*(s-b)*(s-c));
}
bool CCommonTools::ValidPoint(CVector &LinePoint1, CVector &LinePoint2, CVector &TrianglePoint1, CVector
&TrianglePoint2,CVector &TrianglePoint3,CVector &result)
{
  //三角形所在平面的法向量
  CVector TriangleV;
  //三角形的边方向向量
  CVector VP12, VP13;
  //直线与平面的交点
  CVector CrossPoint;
  //平面方程常数项
  float TriD;
  CVector LineV = LinePoint2 - LinePoint1;
  /*-------计算平面的法向量及常数项-------*/
  //point1->point2
  VP12.x = TrianglePoint2.x - TrianglePoint1.x;
  VP12.y = TrianglePoint2.y - TrianglePoint1.y;
  VP12.z = TrianglePoint2.z - TrianglePoint1.z;
  //point1->point3
  VP13.x = TrianglePoint3.x - TrianglePoint1.x;
  VP13.y = TrianglePoint3.y - TrianglePoint1.y;
  VP13.z = TrianglePoint3.z - TrianglePoint1.z;
  //VP12xVP13
  TriangleV.x = VP12.y*VP13.z - VP12.z*VP13.y;
  TriangleV.y = -(VP12.x*VP13.z - VP12.z*VP13.x);
  TriangleV.z= VP12.x*VP13.y - VP12.y*VP13.x;
  //计算常数项
  TriD = -(TriangleV.x*TrianglePoint1.x
    + TriangleV.y*TrianglePoint1.y
    + TriangleV.z*TrianglePoint1.z);
  /*-------求解直线与平面的交点坐标---------*/
  /* 思路：
   *     首先将直线方程转换为参数方程形式，然后代入平面方程，求得参数t，
   * 将t代入直线的参数方程即可求出交点坐标
  */
  float tempU, tempD;  //临时变量
  tempU = TriangleV.x*LinePoint1.x + TriangleV.y*LinePoint1.y
    + TriangleV.z*LinePoint1.z + TriD;
  tempD = TriangleV.x*LineV.x + TriangleV.y*LineV.y + TriangleV.z*LineV.z;
  //直线与平面平行或在平面上
  if(tempD == 0.0)
  {
  // printf("The line is parallel with the plane.\n");
   return false;
  }
  //计算参数t
  float t = -tempU/tempD;
  //计算交点坐标
  CrossPoint.x = LineV.x*t + LinePoint1.x;
  CrossPoint.y = LineV.y*t + LinePoint1.y;
  CrossPoint.z = LineV.z*t + LinePoint1.z;
  /*----------判断交点是否在三角形内部---------*/
  //计算三角形三条边的长度
  float d12 = Distance(TrianglePoint1, TrianglePoint2);
  float d13 = Distance(TrianglePoint1, TrianglePoint3);
  float d23 = Distance(TrianglePoint2, TrianglePoint3);
  //计算交点到三个顶点的长度
  float c1 = Distance(CrossPoint, TrianglePoint1);
  float c2 = Distance(CrossPoint, TrianglePoint2);
  float c3 = Distance(CrossPoint, TrianglePoint3);
  //求三角形及子三角形的面积
  float areaD = Area(d12, d13, d23);  //三角形面积
  float area1 = Area(c1, c2, d12);    //子三角形1
  float area2 = Area(c1, c3, d13);    //子三角形2
  float area3 = Area(c2, c3, d23);    //子三角形3
  //根据面积判断点是否在三角形内部
  if(fabs(area1+area2+area3-areaD) > 0.001)
  {
  return false;
  }

  result = CrossPoint;
  return true;
}

上面的代码是判断两点构成的直线和三点构成的面片是否相交，要判断线段的话，需要再判断交点是否在线段的两个端点之间:  交点和两个端点可以形成两个向量，判断这两个向量的方向即可。
盼望高手们能完善一下其他的算法实现过程！