Jump to content
  • Advertisement
Sign in to follow this  
Kekko

Is this SAT collision algorithm correct?

This topic is 5397 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'm desperatly trying to find what's wrong in my collision detection code, and I'n having a hard time since I haven't worked with this kind of math before. So I'm asking you, should this code work?
for( int i = 0 ; i < 15 ; i++ )
	{
		float Ra, Rb, T;

                // radius of the first box along the axis
		Ra =	Size.x*fabs(D3DXVec3Dot( &Unit_Axes[0], &Col_Vectors))+
			Size.y*fabs(D3DXVec3Dot( &Unit_Axes[1], &Col_Vectors))+
			Size.z*fabs(D3DXVec3Dot( &Unit_Axes[2], &Col_Vectors));
                // radius of the second box along the axis
		Rb =	Box.Size.x*fabs(D3DXVec3Dot( &Box_Axes[0], &Col_Vectors))+
			Box.Size.y*fabs(D3DXVec3Dot( &Box_Axes[1], &Col_Vectors))+
			Box.Size.z*fabs(D3DXVec3Dot( &Box_Axes[2], &Col_Vectors));
                // distance between the two boxes, along the axis.
		T = fabs(D3DXVec3Dot(  &Box_Pos, &Col_Vectors ));
		if( (Ra + Rb) < T )
			return false;
}


Share this post


Link to post
Share on other sites
Advertisement
Sorry, I'm a little stressed...

The problem lies either here or in the code that transform one box into the other's coordinate space.

Therefore I'm asking if this collision detection algorithm should work, assuming all else is correct.

Ra and Rb are the radii of the two boxes along each of the 15 axes. These axes are stored in Col_Vectors, which is an array of 15 vectors(!).

Since one box is always located in (0,0,0) because where in it's local coordinate frame, I just use the other box's position as the distance between the two.
This distance is then projected on the axis in Col_Vector and stored in T.

Have I made any wrong assumptions? Are there some stupid errors in the code that you can see?

Share this post


Link to post
Share on other sites
You should use the search Engine of GameDev, the One that uses Google. Oiii posted his code several times here. He also gives some code samples on his site. Click stats, find his profile, his linkies, etc... Then compare with your code.

I haven't checked your code. But maybe it's how you define the axes, and you don't show it here.

Share this post


Link to post
Share on other sites
try

D3DVECTOR3 xDiff;
D3DXVec3Sub(&Box_Pos, &Pos, &xDiff);

T = fabs(D3DXVec3Dot( &xDiff, &Col_Vectors ));

or something like that.... You need to consider the position of the other box as well to calculate T.

Otherwise, that looks OK, provided your Col_Vectors are correct?

Share this post


Link to post
Share on other sites
oliii

The position of the other box is in 0,0,0 per definition. The other box is rotated by the inverse of the first one to get it's position, relative to the first box.

And *that* is where I think the problem lies.
Y'see, my grasp on matrices are quite basic.

Col_Vectors are defined like this:


D3DXVECTOR3 Col_Vectors[] = {
Unit_Axes[0], Unit_Axes[1], Unit_Axes[2],
Box_Axes[0], Box_Axes[1], Box_Axes[2],
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[2])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[2]))
};




Where unit_Axes and Box_Axes are defined like this


D3DXVECTOR3 Unit_Axes[3] = {D3DXVECTOR3(1, 0, 0),
D3DXVECTOR3(0, 1, 0),
D3DXVECTOR3(0, 0, 1) };

D3DXVECTOR3 Box_Axes[3] = {D3DXVECTOR3(1, 0, 0),
D3DXVECTOR3(0, 1, 0),
D3DXVECTOR3(0, 0, 1) };
if( RotMtr ) D3DXMatrixInverse( &Transform, NULL, RotMtr ); // Transform is the inverse of Box1's rotation matrix
else D3DXMatrixIdentity( &Transform ); // If Box1 doesn't have a rotation matrix, Transform is identity.

if( Box.RotMtr ) Transform = *Box.RotMtr * Transform; //Multiply Transform by Box2's rotation matrix.

// Transform the axes of box2.
D3DXVec3TransformCoord( &Box_Axes[0], &Box_Axes[0], &Transform );
D3DXVec3TransformCoord( &Box_Axes[1], &Box_Axes[1], &Transform );
D3DXVec3TransformCoord( &Box_Axes[2], &Box_Axes[2], &Transform );








Now, if there's something wrong in there, which I suspect there is, I wouldn't be able to spot it. But my guess is that multiplying the matrices together like that won't get me the rotation I want. Correct?

EDIT: Code in windows looked messy :)

Share this post


Link to post
Share on other sites
your code looks quite complicated for a start. If you are unsure about matrices, you might as well forget about them and don't use local transforms.


D3DXVECTOR3 Unit_Axes[3] = {D3DXVECTOR3(RotMtr._11, RotMtr._12, RotMtr._13),
D3DXVECTOR3(RotMtr._21, RotMtr._22, RotMtr._23),
D3DXVECTOR3(RotMtr._31, RotMtr._32, RotMtr._33) };

D3DXVECTOR3 Box_Axes[3] = {D3DXVECTOR3(Box.RotMtr._11, Box.RotMtr._12, Box.RotMtr._13),
D3DXVECTOR3(Box.RotMtr._21, Box.RotMtr._22, Box.RotMtr._23),
D3DXVECTOR3(Box.RotMtr._31, Box.RotMtr._32, Box.RotMtr._33) };

D3DXVECTOR3 Col_Vectors[] = {
Unit_Axes[0], Unit_Axes[1], Unit_Axes[2],
Box_Axes[0], Box_Axes[1], Box_Axes[2],
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[0], &Box_Axes[2])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[1], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[0])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[1])),
(*D3DXVec3Cross( &Storage, &Unit_Axes[2], &Box_Axes[2]))
};

D3DXVECTOR3 xDiff(Box_Pos - Pos);

for( int i = 0 ; i < 15 ; i++ )
{
float Ra, Rb, T;

// radius of the first box along the axis
Ra = Size.x*fabs(D3DXVec3Dot( &Unit_Axes[0], &Col_Vectors))+
Size.y*fabs(D3DXVec3Dot( &Unit_Axes[1], &Col_Vectors))+
Size.z*fabs(D3DXVec3Dot( &Unit_Axes[2], &Col_Vectors));
// radius of the second box along the axis
Rb = Box.Size.x*fabs(D3DXVec3Dot( &Box_Axes[0], &Col_Vectors))+
Box.Size.y*fabs(D3DXVec3Dot( &Box_Axes[1], &Col_Vectors))+
Box.Size.z*fabs(D3DXVec3Dot( &Box_Axes[2], &Col_Vectors));
// distance between the two boxes, along the axis.
T = fabs(D3DXVec3Dot( &xDiff, &Col_Vectors ));
if( (Ra + Rb) < T )
return false;
}


Share this post


Link to post
Share on other sites
I'm quite tired now, so I guess that was not the exact answer you were looking for, but try this first before playing around with transforms. It will be easier if you have the basic brute force algorithm working first. then you can compare values one to one. A lot easier to debug than jumping straight into something you are not even sure about :)

After that, you can optimise the algo, by for example, not calculating the axes first, but when you need them. Lots of micro-optimisations specific for each axis. You can look at the RAPID coll det library for a start, or hop to Dave Eberly's website and look at the docs on the separation axis. I think he has some optimised math tables for each of the axes.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!