Sign in to follow this  
Haegr

SAT - finding face directions / normals

Recommended Posts

I've searched for threads relating to this and currently not find an answer, though that could be due to me not looking hard enough.

I have used the code from [url="http://www.essentialmath.com/tutorial.htm"]http://www.essential...om/tutorial.htm[/url] to start my implementation of SAT.

Currently I am trying to find the 3 face directions of each object, as well as the edge directions.

Any help would be much appreciated.

Share this post


Link to post
Share on other sites
For an OBB, both the face normals and the edges will be parallel to the local axes of the OBB, so if you have the transform for the box (which I assume you do), you have the face normals and edge directions.

There are some additional details related to optimization and robustness, but as for your specific question, the local-space axes of the box transforms are what you're looking for.

Share this post


Link to post
Share on other sites
The box shares a matrix with the mesh it encapsulates, the vertices themselves are stored in an array of vectors.

I shall take the directions from the matrix and test the code.

A somewhat unrelated question, what would the cross product of the same vector be?

Share this post


Link to post
Share on other sites
[quote name='Haegr' timestamp='1298410148' post='4777707']
A somewhat unrelated question, what would the cross product of the same vector be?[/quote]
If you mean AxA, it would be the zero vector. Similarly, AxB where A and B are nearly parallel will result in a vector with very small magnitude. (Dealing with parallel or near-parallel axis pairs has to be handled carefully for this reason.)

Share this post


Link to post
Share on other sites
I currently have an error where the values of both my boxes are the same for some reason, something I am working through right now and has nothing to do with SAT.

I'd just like to confirm, these values will always be [1, 0, 0] [0, 1, 0] [0, 0, 1] as this is what I am always being presented with.

Editted to add code:

[code]
bBox._dir[0] = D3DXVECTOR3( passedMatrix._11, passedMatrix._21, passedMatrix._31 );
bBox._dir[1] = D3DXVECTOR3( passedMatrix._12, passedMatrix._22, passedMatrix._32 );
bBox._dir[2] = D3DXVECTOR3( passedMatrix._13, passedMatrix._23, passedMatrix._33 );
[/code]

The above code is where I set the direction, where the passedMatrix is the matrix for the object (contains translation, scale and rotation). Edited by Haegr

Share this post


Link to post
Share on other sites
[quote name='Haegr' timestamp='1298553280' post='4778411']
I'd just like to confirm, these values will always be [1, 0, 0] [0, 1, 0] [0, 0, 1] as this is what I am always being presented with.
[/quote]
Which values are you referring to? If you're referring to the box axes, then they will only be the cardinal axes (as shown above) if the box transform is identity. In the general case though, the box axes will not be the cardinal axes.

Share this post


Link to post
Share on other sites
Yes, I was referring to the box axes.

Currently the bounding boxes themselves seem not to be storing the correct data, or are at least over writing it with the incorrect data somewhere. In any case, the axes should not remain cardinal as the boxes themselves do move.

I shall post my functions that handle SAT below, if you have the time give them a quick glance to see if you can spot any obvious errors.

[code]
void BoundingBox::getInterval( BoundingBox passedbBox, D3DXVECTOR3 axis, float& min, float& max )
{
min = max = dotProduct( axis, passedbBox._objectBounds[0] );
//Check the number of vertices (constant, always 3)
for( int i = 1; i < 3; i++ )
{
float value = dotProduct( axis, passedbBox._objectBounds[i] );
min = getMin( min, value );
max = getMax( max, value );
}

}

bool BoundingBox::testIntersection( BoundingBox bBoxA, BoundingBox bBoxB)
{
float min1, max1, min2, max2;

//Check face directions from object 1
for( int i = 0; i < 3; i++ )
{
getInterval( bBoxA, bBoxA._dir[i], min1, max1 );
getInterval( bBoxB, bBoxA._dir[i], min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
//Check face directions from object 2
for( int i = 0; i < 3; i++ )
{
getInterval( bBoxA, bBoxB._dir[i], min1, max1 );
getInterval( bBoxB, bBoxB._dir[i], min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
//Edges Directions
for( int i = 0; i < 3; i++ )
{
for( int i = 0; i < 3; i++ )
{
D3DXVECTOR3 axis = crossProduct( bBoxA._dir[i], bBoxB._dir[i] );

getInterval( bBoxA, axis, min1, max1 );
getInterval( bBoxB, axis, min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
}

//There is collision
return true;
}
[/code]

Share this post


Link to post
Share on other sites
I would start by making sure your input data is correct. If the box orientations are changing but the matrix returned is always identity, that's the first problem you'll want to address.

Share this post


Link to post
Share on other sites
Alright then. Update on this.

Collision works for both objects but only on the forward face of the bounding box. Collisions with the side faces and back face do nothing.
Bounding box co-ordinates and directions seem to be working.

Code for collisions below:

[code]
void BoundingBox::getInterval( BoundingBox passedbBox, D3DXVECTOR3 axis, float& min, float& max )
{
min = max = dotProduct( axis, passedbBox._worldBounds[0] );
//Check the number of vertices (constant, always 3)
for( int i = 1; i < 3; i++ )
{
float value = dotProduct( axis, passedbBox._worldBounds[i] );
min = getMin( min, value );
max = getMax( max, value );
}

}

bool BoundingBox::testIntersection( BoundingBox bBoxA, BoundingBox bBoxB)
{
float min1, max1, min2, max2;

//Check face directions from object 1
for( int i = 0; i < 3; i++ )
{
getInterval( bBoxA, bBoxA._dir[i], min1, max1 );
getInterval( bBoxB, bBoxA._dir[i], min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
//Check face directions from object 2
for( int i = 0; i < 3; i++ )
{
getInterval( bBoxA, bBoxB._dir[i], min1, max1 );
getInterval( bBoxB, bBoxB._dir[i], min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
//Edges Directions
for( int i = 0; i < 3; i++ )
{
for( int i = 0; i < 3; i++ )
{
D3DXVECTOR3 axis = crossProduct( bBoxA._dir[i], bBoxB._dir[i] );

getInterval( bBoxA, axis, min1, max1 );
getInterval( bBoxB, axis, min2, max2 );
if( max1 < min2 || max2 < min1 )
{
return false;
}
}
}

//There is collision
return true;
}
[/code]

Share this post


Link to post
Share on other sites
It doesn't look like you're computing the projected intervals correctly.

What does _worldBounds refer to?

Share this post


Link to post
Share on other sites
_worldBounds is the bounding box co-ordinates relative to the world matrix.

I am not certain where I've gone wrong if I am not computing the intervals correctly, I think I followed the article properly.

Share this post


Link to post
Share on other sites
[quote name='Haegr' timestamp='1299019567' post='4780713']
_worldBounds is the bounding box co-ordinates relative to the world matrix.[/quote]
By 'bounding box coordinates', do you mean the corners of the box? If so, why are there only three, rather than 8?

Share this post


Link to post
Share on other sites
And with that tiny change, it works. Not sure where I read that it was supposed to be 3.

Many thanks for helping me through this.

Share this post


Link to post
Share on other sites
[quote name='Haegr' timestamp='1299020896' post='4780732']
And with that tiny change, it works. Not sure where I read that it was supposed to be 3.

Many thanks for helping me through this.
[/quote]
Great, glad you got it working :)

I'm obliged to mention that a) there's a variety of ways the box-box SAT can be optimized relative to what you have there, and B) your cross-product axis tests as implemented currently may be vulnerable to numerical error. But, as far as a basic implementation goes, what you have looks correct.

Share this post


Link to post
Share on other sites
A basic implementation is all I am after right now, I may look into optimising it later but currently all I wanted was for it to work hehe.

Would you be able to expand on point B a little as I'd like to avoid such errors.

Share this post


Link to post
Share on other sites
[quote name='Haegr' timestamp='1299022247' post='4780743']
Would you be able to expand on point B a little as I'd like to avoid such errors.[/quote]
If the cross product input vectors are nearly parallel, the resulting axis may have a very small magnitude, which can result in the axis test for that axis being unreliable.

Good references on the SAT for OBBs are Dave Eberly's code and references, and Christer Ericson's collision detection book. As for the issue in question, there's more than one way to work around it, but a fairly simple method (although perhaps not the best solution) is to skip the axis if the (squared) magnitude is below some threshold value.

Share this post


Link to post
Share on other sites
I had a feeling the numeric error might have something to do with the cross product, you mentioned it earlier :P

I have already ordered the book by Christer Ericson, simply waiting for it to be delivered.

Once again, my thanks for all the help.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this