# Ray-Mesh collision by trangle

This topic is 2069 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Sorry for all the code, but I have a problem. This code works, but I end up having transforming each vertex (sometimes multiple times) within my collision detection function. When I tried to transform the ray's origin and direction (inverse matrix), it doesn't work.

Here is the code that works:

bool EFFECTMESH::RayIntersectSubset(RAY *Ray,int Subset,float keyFrame){
bool hit=false;
if (Subset>=NumSubsets) return false;
D3DXVECTOR3 u,v,n;              // triangle vectors
D3DXVECTOR3 dir, w0, w;           // ray vectors
float r, a, b;					// params to calc ray-plane intersect

float dist=-1;

NMVertex *vb=0;
VB->Lock(0,0,reinterpret_cast<void**>(&vb),0);
LPVOID lpv;
IB->Lock(0,0,&lpv,0);

short *ib=(short*)lpv;

dir=Ray->d;
D3DXMATRIX tmp;
if (keyFrame==int(keyFrame)) tmp=indexInfo[Subset].KeyframeMatrix[int(keyFrame)];
else tmp=MatrixLerp(indexInfo[Subset].KeyframeMatrix[int(keyFrame)],indexInfo[Subset].KeyframeMatrix[int(keyFrame)+1],keyFrame-int(keyFrame));

for (UINT i=indexInfo[Subset].iStart;i<indexInfo[Subset].iStart+indexInfo[Subset].iCount*3;i+=3){//this is a face count.
D3DXVECTOR3 P0,P1,P2;
D3DXVec3TransformCoord(&P0,&vb[ib[i]].pos,&tmp);
D3DXVec3TransformCoord(&P1,&vb[ib[i+1]].pos,&tmp);
D3DXVec3TransformCoord(&P2,&vb[ib[i+2]].pos,&tmp);

u=P1-P0;
v=P2-P0;

D3DXVec3Cross(&n,&u,&v);

if (D3DXVec3LengthSq(&n)>0.0f){
w0=Ray->o-P0;
a=-D3DXVec3Dot(&n,&w0);
b=D3DXVec3Dot(&n,&dir);
if (fabs(b) > 0.0001f) {     // make sure ray is not parallel
r = a / b;
if (r > 0.0f){//ray must go toward triangle
if ((r<dist)||(dist==-1.0f)){//check to see if point is inside the triangle
D3DXVECTOR3 colPoint=Ray->o+dir*r;
float    uu, uv, vv, wu, wv, D;
uu=D3DXVec3Dot(&u,&u);
uv=D3DXVec3Dot(&u,&v);
vv=D3DXVec3Dot(&v,&v);
w=colPoint-P0;
wu=D3DXVec3Dot(&w,&u);
wv=D3DXVec3Dot(&w,&v);

D = uv * uv - uu * vv;
float s, t;
s = (uv * wv - vv * wu) / D;
if ((s >= 0.0f)&&( s <= 1.0f)){
t = (uv * wu - uu * wv) / D;
if ((t >= 0.0f)&&((s + t) <= 1.0f)){
//is inside the triangle
dist=r;
Ray->Col=colPoint;
Ray->Dist=r;
hit=true;
}
}
}
}
}
}
}

IB->Unlock();
VB->Unlock();
return hit;
}



As I said, this works fine except the costly transformations I am doing to each vertex.

Here is the code I modified (that doesn't work):

bool EFFECTMESH::RayIntersectSubset(RAY *Ray,int Subset,float keyFrame){
bool hit=false;
if (Subset>=NumSubsets) return false;
D3DXVECTOR3 u,v,n;              // triangle vectors
D3DXVECTOR3 dir, w0, w;           // ray vectors
float r, a, b;					// params to calc ray-plane intersect

float dist=-1;

NMVertex *vb=0;
VB->Lock(0,0,reinterpret_cast<void**>(&vb),0);
LPVOID lpv;
IB->Lock(0,0,&lpv,0);

short *ib=(short*)lpv;

dir=Ray->d;
D3DXVECTOR3 rayO;
D3DXMATRIX tmp;
D3DXMatrixInverse(&tmp,0,&indexInfo[Subset].KeyframeMatrix[keyFrame]);
D3DXVec3TransformCoord(&rayO,&Ray->o,&tmp);
D3DXVec3TransformCoord(&dir,&dir,&tmp);
D3DXVec3Normalize(&dir,&dir);

for (UINT i=indexInfo[Subset].iStart;i<indexInfo[Subset].iStart+indexInfo[Subset].iCount*3;i+=3){//this is a face count.

u=vb[ib[i+1]].pos-vb[ib[i]].pos;
v=vb[ib[i+2]].pos-vb[ib[i]].pos;

D3DXVec3Cross(&n,&u,&v);

if (D3DXVec3LengthSq(&n)>0.0f){
w0=rayO-vb[ib[i]].pos;
a=-D3DXVec3Dot(&n,&w0);
b=D3DXVec3Dot(&n,&dir);
if (fabs(b) > 0.0001f) {     // make sure ray is not parallel
r = a / b;
if (r > 0.0f){//ray must go toward triangle
if ((r<dist)||(dist==-1.0f)){//check to see if point is inside the triangle
D3DXVECTOR3 colPoint=rayO+dir*r;
float    uu, uv, vv, wu, wv, D;
uu=D3DXVec3Dot(&u,&u);
uv=D3DXVec3Dot(&u,&v);
vv=D3DXVec3Dot(&v,&v);
w=colPoint-vb[ib[i]].pos;
wu=D3DXVec3Dot(&w,&u);
wv=D3DXVec3Dot(&w,&v);
D = uv * uv - uu * vv;
float s, t;
s = (uv * wv - vv * wu) / D;
if ((s >= 0.0f)&&( s <= 1.0f)){
t = (uv * wu - uu * wv) / D;
if ((t >= 0.0f)&&((s + t) <= 1.0f)){
//is inside the triangle
dist=r;
Ray->Col=colPoint;
Ray->Dist=r;
hit=true;
}
}
}
}
}
}
}

IB->Unlock();
VB->Unlock();
return hit;
}



EFFECTMESH is a structure that has DirectX index and vertex buffers. I also have "subsets" identified within the IB. Here is the structure:

struct MESHINDEXINFO{
MESHINDEXINFO(){vStart=vCount=iStart=iCount=0;}
UINT vStart,vCount,iStart,iCount;

//amimation stuff here
vector <D3DXMATRIX> KeyframeMatrix;
};
struct EFFECTMESH{
EFFECTMESH(){VB=NULL;}
IDirect3DVertexBuffer9 *VB;
LPDIRECT3DINDEXBUFFER9 IB;
vector <MESHINDEXINFO> indexInfo;
int NumSubsets;
void Release(void);
bool RayIntersection(RAY *Ray,float keyFrame);
bool RayIntersectSubset(RAY *Ray,int Subset,float keyFrame);
};



The RAY structure:

struct RAY{
RAY(){o=d=Col=Col2=D3DXVECTOR3(0,0,0);Dist=-1;}
D3DXVECTOR3 o,d;
//d is normalized vector of the ray
//o is ray origin
D3DXVECTOR3 Col;//outputs the coordinate along the ray from the origin at the distance
D3DXVECTOR3 Col2;//the far side point
float Dist;
};



Some of the info is not used for this (it's used elsewhere in the program for a different purpose).

***EDIT: I took out the "keyframe" lerp in the code that doesn't work. This was an attempt to simplify it. Both functions work the same with or without the "keyfram" lerp, so that's not the issue......

Can anyone tell me what I'm doing wrong? I sure it's the transformation, but I can't get my head around it........

Edited by Hawkblood

##### Share on other sites

It appears your trying to pick a skinned mesh. Is that correct? Sometimes a bit more of an explanation of what you're doing helps people better understand the code.

Just a quick look at your code: noticed that you transform the direction vector as if it were a position. I.e., for dir, you should be using D3DXVec3TransformNormal (vs. TransformCoord) with the transpose of the inverse of the transformation. I haven't a clue if that's the problem, BTW, just an observation.

Also, in the non-working code, is there a reason you don't interpolate the keyframe? Unless you have keyframes at every tick, it may make a difference.

##### Share on other sites

Not a skinned mesh, just an animated rigid mesh. I will do skinned meshes at a later time.

D3DXVec3TransformNormal

THAT was what I was missing!

It works fine now. Thanks.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 18
• 19
• 11
• 9