• Advertisement
Sign in to follow this  

Trimesh Collision detction problem

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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???

thanks for your help everyone!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement