Chinaunix首页 | 论坛 | 博客
  • 博客访问: 128365
  • 博文数量: 44
  • 博客积分: 2500
  • 博客等级: 少校
  • 技术积分: 470
  • 用 户 组: 普通用户
  • 注册时间: 2009-12-07 23:06
文章分类

全部博文(44)

文章存档

2010年(6)

2009年(38)

我的朋友

分类:

2009-12-07 23:40:33

射线三角面相交的数学算法


使用d3d扩展函数,毕竟有时不能满足具体需求,掌握了该方法,我们才能够获得最大的控制自由度,任意修改算法。

   

已知条件: 射线源点orginPoint,三角形三个顶点 v1,v2,v3,射线方向 Dir
(均以三维坐标向量形式表示)
算法目的: 判断射线与三角形是否相交,如果相交求出交点的重心坐标(U,V)和射线原点到交点的距离T。

我们可先假设射线与三角形相交则交点(注以下均为向量运算,*数乘,dot(X,Y) X,Y 点乘,cross(X,Y)X,Y叉乘;U,V,T为标量)
则:
IntersectPoint = V1 + U*(V2-V1) + V*(V3-V1) ;
IntersectPoint = originPoint + T*Dir;

所以
orginPoint + T*Dir = V1 + U*(V2-V1) + V*(V3-V1);
整理得:

这是一个简单的线性方程组,若有解则行列式 不为0。
根据T,U,V的含义当T>0, 0解此方程组即可获得我们关心的值,具体解法不再赘述,克莱姆法则就够了(详细见线性代数):射线原点到相交点的距离T,和交点的中心坐标(U,V)。
下面给出Direct 9 SDK示例程序中的实现代码

IntersectTriangle( const D3DXVECTOR3& orig,

               const D3DXVECTOR3& dir, D3DXVECTOR3& v0,

                   D3DXVECTOR3& v1, D3DXVECTOR3& v2,

                   FLOAT* t, FLOAT* u, FLOAT* v )

{

// 算出两个边的向量

D3DXVECTOR3 edge1 = v1 - v0;

D3DXVECTOR3 edge2 = v2 - v0;


D3DXVECTOR3 pvec;

D3DXVec3Cross( &pvec, &dir, &edge2 );


// 如果det为0,或接近于零则射线与三角面共面或平行,不相交

//此处det就相当于上面的

FLOAT det = D3DXVec3Dot( &edge1, &pvec );


D3DXVECTOR3 tvec;

if( det > 0 )

{

       tvec = orig - v0;

}

else

{

       tvec = v0 - orig;

       det = -det;

}


if( det < 0.0001f )

       return FALSE;


// 计算u并测试是否合法(在三角形内)

*u = D3DXVec3Dot( &tvec, &pvec );

if( *u < 0.0f || *u > det )

       return FALSE;


// Prepare to test V parameter

D3DXVECTOR3 qvec;

D3DXVec3Cross( &qvec, &tvec, &edge1 );


//计算u并测试是否合法(在三角形内)

*v = D3DXVec3Dot( &dir, &qvec );

if( *v < 0.0f || *u + *v > det )

       return FALSE;


/*计算t,并把t,u,v放缩为合法值(注意前面的t,v,u不同于算法描述中的相应量,乘了一个系数det),注意:由于该步运算需要使用除法,所以放到最后来进行,避免不必要的运算,提高算法效率*/

*t = D3DXVec3Dot( &edge2, &qvec );

FLOAT fInvDet = 1.0f / det;

*t *= fInvDet;

*u *= fInvDet;

*v *= fInvDet;


return TRUE;

}


3 拾取完成根据获得的中心坐标计算我们关心的常见量,。
根据重心坐标(U,V),我们可以很容易的算出各种相关量比如纹理坐标和交点的差值颜色,假设以纹理坐标为例设V1,V2,V3的纹理坐标分别为T1(tu1,tv1),T2(tu2,tv2),T3(tu3,tv3)则交点的坐标为
阅读(1197) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~