利用代数方法进行相交检测

原理基本上是高等代数和解析几何 、 三角学的应用

优点：适用性广，快速，可以适用于N维Euclidean 空间中任意点、线、面、三角区域的相交检测，缺点：复杂情况下提高检测准确率引起的计算开销较大，比如三角形相交检测时，判定共面相交的情形，这需要计算一个3D逆矩阵作为基变换，然后在2D中检测相交。

实现原理的部分来自 Mathematics for 3D Game Programming and Computer Graphics, Third Edition

以下给出几个情形的范例，代码只求理解，不是最快的，还可以延伸出很多情形，可以自己补充哦：）

//3D 线段与三角形的检测，不检测共面相交的情形

float det3DMatrix( const D3DXVECTOR3& a, const D3DXVECTOR3& b,const D3DXVECTOR3& c) {
return a.x * (b.y * c.z - c.y * b.z)
+ b.x * (c.y * a.z - a.y * c.z)
+ c.x * (a.y * b.z - b.y * a.z);
}

bool TriSecIntersec(const D3DXVECTOR3 & vTri1, const D3DXVECTOR3 & vTri2, const D3DXVECTOR3 & vTri3,
const D3DXVECTOR3& vSec1,const D3DXVECTOR3 & vSec2 ,D3DXVECTOR3 & vContact)
{

D3DXVECTOR3 fafb = vTri2 - vTri1;
D3DXVECTOR3 fafc = vTri3 - vTri1;

D3DXVECTOR3 sasb =vSec2 - vSec1 ;
D3DXVECTOR3 fasa = vSec1 - vTri1;
float det_sasb = det3DMatrix(fafb, fafc, sasb);

float det_alphasa1 = det3DMatrix(fasa, fafc, sasb);
float det_alphasa2 = det3DMatrix(fafb, fasa, sasb);
float det_fasa = det3DMatrix(fafb, fafc, fasa);

if ((-det_fasa * det_sasb) <= det_sasb * det_sasb
&& 0 <= (-det_sasb * det_fasa) // not Parallel or Coplanar
&& 0 <= det_sasb * det_alphasa1
&& 0 <= det_sasb * det_alphasa2
&& (det_alphasa1 * det_sasb + det_sasb * det_alphasa2) <= det_sasb * det_sasb)
{
vContact = vSec1 - sasb*(det_fasa/ det_sasb); // Contact point
return true;
}

return false;
}

//3D 线段与平行四边形区域（矩形）的检测，不检测共面相交的情形

bool TriPRegionIntersec(const D3DXVECTOR3 & vTri1, const D3DXVECTOR3 & vTri2, const D3DXVECTOR3 & vTri3,

const D3DXVECTOR3& vSec1,const D3DXVECTOR3 & vSec2 )
{

D3DXVECTOR3 fafb = vTri2 - vTri1;
D3DXVECTOR3 fafc = vTri3 - vTri1;

D3DXVECTOR3 sasb =vSec2 - vSec1 ;
D3DXVECTOR3 fasa = vSec1 - vTri1;
float det_sasb = det3DMatrix(fafb, fafc, sasb);

float det_alphasa1 = det3DMatrix(fasa, fafc, sasb);
float det_alphasa2 = det3DMatrix(fafb, fasa, sasb);
float det_fasa = det3DMatrix(fafb, fafc, fasa);

if ((-det_fasa * det_sasb) <= det_sasb * det_sasb
&& 0 <= (-det_sasb * det_fasa)
&& 0 <= det_sasb * det_alphasa1
&& 0 <= det_sasb * det_alphasa2
&& (det_alphasa1 * det_sasb ) <= det_sasb * det_sasb

&& ( det_sasb * det_alphasa2 ) <= det_sasb * det_sasb) 
{
return true;
}
return false;
}

//2D 点与三角形相交的检测

float det2DMatrix( const D3DXVECTOR2& a, const D3DXVECTOR2& b) {
return a.x * b.y - a.y * b.x;
}

bool TriPointIntersec2D(const D3DXVECTOR2 & vTri1, const D3DXVECTOR2 & vTri2, const D3DXVECTOR2 & vTri3,

const D3DXVECTOR2& X )
{

D3DXVECTOR2 fafb = vTri2 - vTri1;
D3DXVECTOR2 fafc = vTri3 - vTri1;

D3DXVECTOR2 fasa = X - vTri1;
float det_sasb = det2DMatrix(fafb, fafc);

float det_alphasa1 = det2DMatrix(fasa, fafc);
float det_alphasa2 = det2DMatrix(fafb, fasa);

if ( 0 <= det_alphasa1 * det_sasb
&& 0 <= det_alphasa2 * det_sasb
&& (det_alphasa1 * det_sasb+ det_alphasa2 * det_sasb) <= det_sasb * det_sasb
)
{
return true;
}
return false;
}