# SAT - finding face directions / normals

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

## 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 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 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 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 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.

[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 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 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 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 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 on other sites
It doesn't look like you're computing the projected intervals correctly.

What does _worldBounds refer to?

##### 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 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 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 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 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 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 on other sites
I had a feeling the numeric error might have something to do with the cross product, you mentioned it earlier

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 on other sites

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628666
• Total Posts
2984131

• 12
• 10
• 9
• 9
• 10