论文导读：采用克莱姆法则研究了射线与三角形相交。用一般线性代数的方法来研究射线与三角形相交的条件及数学结论，并通过鼠标在屏幕上的点击位置，利用变换矩阵换算成拾取射线，计算该拾取射线与任意3D物体中的任意三角形是否相交。
关键词：克莱姆法则，变换矩阵，射线，重心坐标
0.引言
用鼠标拾取3D场景中的指定物体，是D3D编程中的一种较为常见，但比较复杂的算法，本文旨在从一般数学的方法来得到该算法的核心组成部分，并用实际代码实现该算法。为了得到拾取的数学结论，本文中将给出演算过程。科技论文。
1.理论部分
1.1 重心坐标
设三角形所在平面一点P的重心坐标为（a,b,c）则 a+b+c = 1;三角形所在平面的所有点都可以用重心坐标表示，如果在三角形外面，则：
a,b,c三个数当中必有一个为负数，这一点P的3D坐标为(Px, Py, Pz)
1.2 前提条件
三角形的三个点为（顺时针）v0, v1, v2 则 v0*a + v1*b + v2*c = (Px, Py,Pz); (设v0,v1,v2是点，且同样用重心坐标方式表示。)
因为：a+b+c = 1;
所以: v0*a + v1*b + v2*c
= v0 *(1-b-c) + v1*b + v2*c ;
= b * (v1 - v0)+ c * (v2 - v0) + v0;
-----------------1
假设射线方程式F(x,y,z)= Orgin + rayVec * t;（其中Orgin为射线起点，rayVec为射线方向向量）
----------------2
1.3 矩阵演算
从1.2得知射线和P点的交点方程(由1和2)： Orgin + rayVec * t = b * (v1 - v0) + c * (v2 - v0) + v0；
列成矩阵形式： 设v1 - v0 =edge1; v2 - v0 = edge2;
则：Orgin + rayVec * t = b * edge1+ c * edge2 + v0
变一下型：b * edge1 - rayVec *t + c * edge2 = Orgin - v0;
我们设fDist =-t; 去掉负号;
得到：b * edge1 - rayVec * fDist + c * dege2 = Orgin - v0;
将上式按向量分量展开成方程组形式为：
b * edge1.x -rayVec.x * fDist + c * edge2.x = (Orgin - v0).x;
b * edge1.y - rayVec.y * fDist+ c * edge2.y = (Orgin - v0).y;
b * edge1.z - rayVec.z * fDist+ c * edge2.z = (Orgin - v0).z;
则可视为用使用克莱姆法则求b , fDist, c三个量
Dot(edge1, Cross(rayVec, edge2))，即rayVec与edge2的叉乘，再与edge1点乘。科技论文。
3个分子分别和det相除就行了
2.射线与三角形相交函数实现
该函数输入射线的起点、方向向量、三角形的3个顶点，返回BOOL类型值表示是否和三角形相交，并通过参数输出t、u、v
bool IntersectTriangle(const D3DXVECTOR3& orig, const D3DXVECTOR3& dir,
D3DXVECTOR3& v0, D3DXVECTOR3& v1, D3DXVECTOR3& v2,
FLOAT*t, FLOAT* u, FLOAT* v )
{
D3DXVECTOR3 edge1 = v1 - v0; //我们的edge1
D3DXVECTOR3 edge2 = v2 - v0; //我们的edge1
D3DXVECTOR3 pvec;
D3DXVec3Cross( &pvec, &dir, &edge2 ); //求det过程中
// 如果det接近0，则说明该射线在三角形所在平面
FLOATdet = D3DXVec3Dot( &edge1, &pvec ); //求得了det
//这下面注意了，这里用了矩阵的一个性质，用k乘以一个矩阵的某一行或者
//某一列时，相当于用k乘以这个矩阵。科技论文。当然k可以等于-1
D3DXVECTOR3 tvec;
if( det> 0 )
{
tvec = orig - v0; //
}
else
{
tvec = v0 - orig; //我们的公式可是 orgin - v0 ,这里相当于乘了个-1,相当于矩阵外乘以-1,相当于和det的变号抵消了。
det = -det; // 132 这里分母变负了
}
//上面det変正主要是为了方便后头的比较。
if( det< 0.0001f )
return FALSE;
*u = D3DXVec3Dot( &tvec, &pvec );
//u为重心坐标之一，不可能大于det.
if( *u< 0.0f || *u > det )
return FALSE;
D3DXVECTOR3 qvec;
D3DXVec3Cross( &qvec, &tvec, &edge1 );
//u+v > 1自然剩的一个就为负了，这也不成立。
*v =D3DXVec3Dot( &dir, &qvec );
if( *v< 0.0f || *u + *v > det )
return FALSE;
*t =D3DXVec3Dot( &edge2, &qvec );
FLOATfInvDet = 1.0f / det;
*t *=fInvDet;
*u *=fInvDet;
*v *=fInvDet;
returnTRUE;
}
参考文献
[1]Steve Cunningham.计算机图形学.机械工业出版社,2008.
|
