# Trimesh Collision detction problem

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

## Recommended Posts

i have written some code to check for ray/trimesh intersection, in the middle i try to get the angle between the point of intersection of the fay with the plane of each triangle of the trimesh, then calculate the angle between the vectors from this point to the 3 vertices of the tri, to know if this point really exists in the polygon not just on its plane. amidst this, the value of the total angle becomes indefined(the VC++ 1.#iND mark). how can this occur? there're totally no devisions happening, so u can avoid assuming a division by zero... here's the code:
vec3 res(NULL,NULL,NULL);
for(int i = 0; i < Size; i++)
{
for(int j = 0; j < SubGeom.nVert; j+= 3)
{
vec3 Norm = CalcNormal(SubGeom.Vertex[j],SubGeom.Vertex[j+1],SubGeom.Vertex[j+2]);
Norm.Normalize();
float ACos = Ray.Dir % Norm;
if((ACos) != 0) //they're NOT parallel
{
float NegD = Norm % SubGeom.Vertex[j];
float Coeff = NegD/ACos;
vec3 TempPt = Ray.Dir * Coeff;
//now to look for a real collision
float TotalAngle = 0;
vec3 VertVector[3];
VertVector[0] = SubGeom.Vertex[j] - TempPt;
VertVector[1] = SubGeom.Vertex[j+1] - TempPt;
VertVector[2] = SubGeom.Vertex[j+2] - TempPt;
//float temp;
for(int k  = 0; k < 2; k++)
{
TotalAngle += acos(VertVector[k] % VertVector[k+1]);
}
//now for the last one
TotalAngle += acos(VertVector[2] % VertVector[0]);
if(((TotalAngle - 6.2831) <= 0.00001) && (dist(Ray.Pos, TempPt) <= Ray.Length))
{
res = TempPt;
return res;
}
}
}
}
return res;



##### Share on other sites
the VertVectors need to be normalized.

acos(A dot B) only works on normalized vectors... passing a value beyond [-1,1] to acos will get you a #IND

##### Share on other sites
FYI this is a really bad algorithm for ray/polygon intersection. It's slow and not very stable.

A search for 'ray triangle intersection' or 'ray polygon intersection' will turn up some threads that go into great detail on the subject, and have links to professional implementations.

Ray/tri tests can be optimized further in some cases than ray/poly tests, so it's best to stick with those. Options for algorithms include side planes, Plucker coordinates/tetrahedral volumes, barycentric coordinates, and other more 'hacky' algorithms. Choose one of those - you'll be happier in the long run!

##### Share on other sites
Ok, i've fixed it, now the code's like this:
vec3 res(NULL,NULL,NULL);for(int i = 0; i < Size; i++){	for(int j = 0; j < SubGeom.nVert; j+= 3)	{		vec3 Norm = CalcNormal(SubGeom.Vertex[j],SubGeom.Vertex[j+1],SubGeom.Vertex[j+2]);		Norm.Normalize();		float ACos = Ray.Dir % Norm;		if((ACos) != 0) //they're NOT parallel		{			float NegD = Norm % SubGeom.Vertex[j];			float Coeff = NegD/ACos;			vec3 TempPt = Ray.Dir * Coeff;			//now to look for a real collision			float TotalAngle = 0;			vec3 VertVector[3];			VertVector[0] = SubGeom.Vertex[j] - TempPt; 			VertVector[1] = SubGeom.Vertex[j+1] - TempPt;			VertVector[2] = SubGeom.Vertex[j+2] - TempPt;			VertVector[0].Normalize();			VertVector[1].Normalize();			VertVector[2].Normalize();			//float temp;			for(int k  = 0; k < 2; k++)			{             				TotalAngle += acos(VertVector[k] % VertVector[k+1]);		  	}			//now for the last one			TotalAngle += acos(VertVector[2] % VertVector[0]);			if((fabs(TotalAngle - 6.2831) <= 0.00001) && (dist(Ray.Pos, TempPt) <= Ray.Length))			{				res = TempPt;				return res;			}		}	}}return res;

and i'm still getting some iNDs , and it still won't work. any help will be appreciated!

##### Share on other sites
These 2 lines
float Coeff = NegD/ACos;vec3 TempPt = Ray.Dir * Coeff;

should probably be:
float Coeff = (NegD - Norm % Ray.Pos)/ACos;vec3 TempPt = Ray.Pos + Ray.Dir * Coeff;

You should try to derive this... ray-plane intersection is a very important thing to know in many situations. Also, I certainly do respect that you're trying to write your own ray-tri algorithm... but you should take jyk's advice and look around for better alternatives. This will be quite slow, and there are many interesting techniques around.

##### Share on other sites
ok, i've understood and added these two lines, now the code's like this:
vec3 res(NULL,NULL,NULL);				for(int i = 0; i < Size; i++)				{					for(int j = 0; j < SubGeom.nVert; j+= 3)					{						vec3 Norm = CalcNormal(SubGeom.Vertex[j],SubGeom.Vertex[j+1],SubGeom.Vertex[j+2]);						Norm.Normalize();						float ACos = Ray.Dir % Norm;						if(ACos != 0) //they're NOT parallel						{							float NegD = Norm % SubGeom.Vertex[j];														float Coeff = (NegD - Norm % Ray.Pos)/ACos;							vec3 TempPt = Ray.Pos + Ray.Dir * Coeff;							//now to look for a real collision							float TotalAngle = 0;							vec3 VertVector[3];							VertVector[0] = SubGeom.Vertex[j] - TempPt; 							VertVector[1] = SubGeom.Vertex[j+1] - TempPt;							VertVector[2] = SubGeom.Vertex[j+2] - TempPt;							VertVector[0].Normalize();							VertVector[1].Normalize();							VertVector[2].Normalize();							//float temp;							for(int k  = 0; k < 2; k++)							{                 				TotalAngle += acos(clamp(VertVector[k] % VertVector[k+1],-1,1));						  	}							//now for the last one							TotalAngle += acos(clamp(VertVector[2] % VertVector[0],-1,1));							if((fabs(TotalAngle - 6.2831) <= 0.00001) && (dist(Ray.Pos, TempPt) <= Ray.Length))							{								res = TempPt;								return res;							}						}					}				}				return res;

i added the clamping part for the value going to acos, but it still doesn't work correctly... what's the problem here???

• 10
• 19
• 14
• 19
• 15