SAT 3D

[Marvin Wyss]

I've tried to make a simple SAT implementation for two tetrahedral's.
But It works not correct.
It works if theres a collision, but if there's no, he may return true anyway sometimes:

I'm not sure if i've made a mistake, or if the whole system is wrong.

I was searching all day. THe Code should explain itself.

I know its not your task to check my Code for me, but I'm desperatet.

bool getcollision3d(tetrahedral A,tetrahedral B){


	Vector3d xAxis[64]; // note : a maximum of 32 vertices per poly is supported
	int    iNumAxes=0; //counter for sep. axis

	for(int i=0;i<4;i++){ //Loop for  tetrahedral A

		xAxis[iNumAxes]=Vector3d::getcross(A.points[(i+0)%4]-A.points[(i+1)%4],A.points[(i+0)%4]-A.points[(i+2)%4]); //get cross-product for the Normals of the face
		float maxa,mina,minb,maxb; //projectet points
		GetInterval3d(A,xAxis[iNumAxes],mina,maxa);//get highest and lowaest projection for A
		GetInterval3d(B,xAxis[iNumAxes],minb,maxb);//get highest and lowaest projection for B
		float d0 = minb - maxa;
		float d1 = mina - maxb;

		if (d0 > 0.0f || d1 > 0.0f) //compare for overlap
		{
			return false; //no overlap
		}
		iNumAxes++;
	}


	for(int i=0;i<4;i++){//Loop for  tetrahedral A

		xAxis[iNumAxes]=Vector3d::getcross(B.points[(i+0)%4]-B.points[(i+1)%4],B.points[(i+0)%4]-B.points[(i+2)%4]);
		float maxa,mina,minb,maxb;
		GetInterval3d(A,xAxis[iNumAxes],mina,maxa);
		GetInterval3d(B,xAxis[iNumAxes],minb,maxb);
		float d0 = minb - maxa;
		float d1 = mina - maxb;

		if (d0 > 0.0f || d1 > 0.0f)
		{
			return false;
		}

		iNumAxes++;

	}




	return true; //collision!!!

	}

[ne555]

for(int j=4-1,i=0;i<4;j=i,i++) is obfuscated. You don't even use 'j' inside the loop.
Same for A.points[0].getcross(//... as it doesn't participates in the operation.

I don't see where you return true; in the collision algorithm.
¿Could you show an example where the result is incorrect?

[Marvin Wyss]

sorry, used the old version, heres the correct version

[Marvin Wyss]

Here's a little summaray:

i made this for each polyhedron.

I made the face normals with the cross product of two edges, like this:
getcross((PointB-PointA)),(PointC-PointA));
for each face, to get the normal.
then i searched the biggest and smallest Projection value.
then I compered them for overlap.

Did i forget something?

[mik2718]

Yes,

The face normal directions are not enough

You also need to check the directions produced by taking the cross products of the edges, one from each polyhedron

from

Eberly, 3D game engine design, 2nd ed page 410

[Marvin Wyss]

I don't get what you mean by one from each polyhedron.

Do you mean the cross products for each combination of the edges, just any two edges or which ones?

i think in tetrahedral the crossproduct of the edges are the face normals

[Marvin Wyss]

okay, just to make sure you understand me:

I made the face normals by taking this cross product:

getcross((PointB-PointA)),(PointC-PointA));

for each face of both polyhedrons.

so whats the difference between that and take the cross product of the edges(sides)?

sorry, but i don't get what you mean.

[mik2718]

My reading of it is that for each pair of edges, one from polyhedron 1 and one from polyhedron 2
you take the cross product and that gives a a direction on which to project.

For two tetrahedra there will be 6x6 = 36 combinations - of course you exit from the function as soon as you find a separation

heres from the book:

"The set of potential separating directions that capture these types of contacts includes the normal vectors
to the faces of the polyhedra and vectors generated by a cross product of two edges, one from each polyhedron.
The necessity of testing more than just the face normals is shown by figure 8.13"

This figure show two cubes, they touch each other at the mid-point of one edge but don't overlap.
In this case all face normals show an overlap but a direction derived as described shows a separation.

[Marvin Wyss]

thanks, it shines to work now!