# General OBB question

## Recommended Posts

I can check for collisions between 2 OBBs just fine. But I've wondered, how do physics engine make sure that 2 OBBs never overlap? Say I have 2 boxes, 1 static and the other moving which has to stop as soon as it collides, I often get the moving box overlapping the static one and I can't find a calculation to accurately push it back a bit to it only touches the static box.

##### Share on other sites
two general methods, you either step back in time until there is no intersection, or you push them apart, most commonely using SAT (Seperating Axis Theorem) which you may well be using already to detect the intersection of the two OBB, for each potential intersection axis, the objects are projected onto the axis and checked for overlap, and if all axis have an overlap the objects are intersecting.

To go further you would when checking for overlaps, find the minimum overlap, and using that minimum overlap and the axis you seperate the objects.

##### Share on other sites
About SAT, so far every algorithm I found that uses it relies on the center point of the OBB. I create my OBB from 8 points and it's also not always a perfect box but close and always convex.

Isn't going back in time and doing another check again and again very costly?? Because I don't see how you can calculate the exact time of the first collision with boxes.

##### Share on other sites
the SAT can work on any convex hull, but using OBB's general form gives better optimisations (less axes to test against).

To find the distance of ointersection, so you can push boxes in a way that minimise the 'work' and make them just aobut touch, you need to upgrade the SAT a little bit.

TO find the time of collision, given the boxes velocities, you need further upgrades :)

http://www.metanetsoftware.com/technique/tutorialA.html

http://members.gamedev.net/oliii/polygon.rar

this is for 2D cases, but the SAT works exactly the same in 3D. All it changes is what axes to test against and the support functions.

at the end of the day, the SAT decompose the problem into a set of 1D problems, so you end up solving the collision by projections.

##### Share on other sites
Thank you, very interesting reading material.
However, pretty much every piece of source material uses a center point and a specific rotation for that OBB. I don't have that rotation since I make my OBB at runtime based on 8 vertices. So I also don't have an exact center point.

I don't use SAT right now, I check if any of the segments of OBB1 collide with any of the triangles of OBB2 and as result I get the intersect points on the segments of OBB1 where it collides.

SAT still confuses me, most websites use 2D example to explain it and that all sounds very logical, but there are hardly any 3D examples. I just don't get how to determine the axis in 3D.
I'm using XNA and I found a SAT collision check and it's like this:

public bool Intersects(OBB b)
{
Matrix matB = b.rotation * this.InverseRotation;
Vector3 vPosB = Vector3.Transform(b.center - this.center,
this.inverseRotation);

Vector3 XAxis = new Vector3(matB.M11, matB.M21, matB.M31);
Vector3 YAxis = new Vector3(matB.M12, matB.M22, matB.M32);
Vector3 ZAxis = new Vector3(matB.M13, matB.M23, matB.M33);

How can I find these axis without a rotation matrix?

##### Share on other sites
Hmmm I believe that if you don't have an orientation matrix, you could base your projection axes on the normals of the 6 quads that make up your bounding box. As long as you have the vertices the normals should be easy enough to calculate.

[Edited by - Dancin_Fool on May 31, 2009 12:53:57 PM]

##### Share on other sites
Quote:
 However, pretty much every piece of source material uses a center point and a specific rotation for that OBB. I don't have that rotation since I make my OBB at runtime based on 8 vertices. So I also don't have an exact center point.I don't use SAT right now, I check if any of the segments of OBB1 collide with any of the triangles of OBB2 and as result I get the intersect points on the segments of OBB1 where it collides.
Regarding the representation, first of all, if the eight points don't actually form a box (i.e. rectangular cuboid), then it's not an OBB. As mentioned above, the SAT can certainly be used for shapes of this type, but it's not particularly efficient (due to the large number of axes that must be checked).

I'm not sure that per-feature intersection tests (which is what you're using) are particularly useful, or very commonly used in practice. They don't detect containment (which may or may not be important to you), and also don't do a very good job of returning useful information about the intersection (such as the time of intersection, penetration depth, or a minimum translation vector for resolving the intersection). Per-feature tests can also be less efficient than the common alternatives, and less robust as well.

Can you describe how you compute the eight vertices at run time? I'd be surprised if you couldn't adjust things so that you had a 'true' OBB available in center-axes-extents form. If nothing else, you should be able to compute the extents in the local space of the object as a pre-processing step, and then grab the center and axes from the object's current world-space transform (which you must have available in some form or another, I would think).

##### Share on other sites
I have an animated character and his collision has to be pretty precise and a tree of spheres isn't going to cut it. So in my modelling program I place boxes where I want collisions, when my game loads it turns those boxes into an OBB.
At the moment, not all are boxes, some are 3d trapezoids (sorry English isn't my primary language, I don't know the correct word) but they all have 6 sides. But I can change that so they're all rectangular cuboids.

Well, the only thing I can get from these per-feature tests are the intersection points, so that's why I'm stuck with overlapping boxes.

##### Share on other sites
Collision detection usually works with 'primitives'. The advantage is that you can use each particular primitive representation for faster and more reliable tests.

Primitives have little use in rendering (unless you start doing stuff like a ray-casting engine), where they are usually broken down to triangles and such.

I would consider storing your OBBs and Frustum (your trapezoids) as primitives, brake them down to the geometrical information about the volume they define. The way you want to represent your OBB can be specific to the algorithm you want to use to test for collisions.

In general, for OBBs, it's quite simple. You can break down an OBB to a centre position, its size (width, breadth and length), and it's orientation (usually, three orthonormal vectors).

For a frustum, it's a bit trickier.

The bottom line with the SAT is that you need to be able to supply, for each object type, a list of face normals, a list of edge directions, and a support function, that is used to compute the size of the object along a direction.

Essential Maths For Games Programming.

Collisions using separating-axis tests.

That should explain how the SAT works in 3D. But to be honest, it's not that much harder in 3D.

The SAT axes that you should use for two convex object A and B are.

face normals of A
face normals of B
edge directions of A cross product the edge directions of B

Obviously, you don't need to test for faces that share the same (or opposite) normal, same thing for the edges.

for a box, you end up with 3 face normals, and 3 edge directions to consider.

Testing two boxes, you will then have 3 + 3 + 3 x 3 = 15 axes to test against.

then you need a support function for the boxes, projecting them along a direction. As you work with vertices, you can just take the min and max of each vertex dot product the axis direction.

For a frustum would have 5 faces worth considering, 6 unique edge directions.

a frustum against another frustum will give you 5 + 5 + 6 x 6 = 46 axes to test against.

a frustum against a box, you will have 5 + 3 + 6 x 3 = 26 axes to test against.

a triangle has 1 face, 3 edges.

a triangle against a box, you will have 1 + 3 + 3 x 3 = 13 axes to test against.

ect...

The rest of the 2D algorithm (finding the MTD, the time of collision, the collision normal) is exactly the same as in 2D.

[Edited by - oliii on June 1, 2009 11:35:55 AM]

##### Share on other sites
if you still want to work with your vertices, and you can assume, in good faith, that your vertices do indeed approximate a OBB, or a frustum, you can just take the vertices themselves to compute the face normals and edge directions you need.

you actually do not need the centre of the shape, nor your axes being normalised, which is a bonus.

say you have a box/frustum made up of 8 vertices, one face, counter-clockwise vertices v0, v1, v2, v3, the other face v4, v5, v6, v7.

BOX :
-----

the three SAT edges would be
(v1 - v0)
(v2 - v1)
(v4 - v0)

the three SAT face normal would be

(v2 - v0) x (v3 - v1)
(v1 - v0) x (v4 - v0)
(v2 - v1) x (v5 - v1)

For a trapezoid (a squashed box), which I define as a frustum (same as a viewing frustum, with a near plane, a far plane, and a field of view) :

TRAPEZOID :
-----------

SAT faces
(v2 - v0) x (v3 - v1)
(v1 - v0) x (v4 - v0)
(v2 - v1) x (v5 - v1)
(v3 - v2) x (v6 - v2)
(v0 - v3) x (v7 - v3)

SAT edges
(v1 - v0)
(v2 - v1)
(v4 - v0)
(v5 - v1)
(v6 - v2)
(v7 - v3)

##### Share on other sites
Sorry it took me a while to reply. It took some time to read all that and implementing it.

oliii, thank you very much, that second link and your explanation were great . I implemented the code from that powerpoint and part of it works great, another part not so great.

The problem seems to be the edge SATs, everytime the check gets past the face normal checks, it automatically returns a collision even if there isn't any.
What's strange is that my edge directions and face normals are correct, I'm drawing them in my scene and they are where they're supposed to be.

Pics, blue lines means no collision, red cubes means collision is detected.
Purple lines are the edge directions, the yellow lines the face normals.
Still good: it doesn't check the edges here
Collision detected: it goes through the full test here

This is my code:
Intersect test: straight from the powerpoint presentation, just ported to C#/XNA
Updating my edge directions: I keep an EdgeList, which holds edges by storing the vertex indexes they have in the vertex array. So basically, I look for the 3 edges that have vertex 0 as a point and calculate the direction from there, then add that direction to an array which is the one I use in the TestIntersection function.
Is there something I did wrong? Is there an error in the intersect function? Because my directions and normals seem correct judging from drawing them in the scene.

##### Share on other sites
I must say, I fail to see a problem there. I'm not too sure about the edge calculations, but looking at the pictures, they look all right.

As for the edge directions, for a box, the edge directions are basically the same as the face directions. So you can try and replace the edges with faces in the cross product.

You also have to consider the case of degenerate edges, i.e. edges that are parallel to each other. That means the cross product is close to zero, and you can run into floating point imprecisions that lead to a test always failing or always returning true.

you can use a tolerance to make sure that doesn't happen.

const float tolerance = 1.0E-6f;
if (max1 < min2 - tolerance || max2 < min1 - tolerance) return false;

another thing to test is to use unit tests. Have the box configured in a predictable way, and check the results. I'd start with two unit box, axis aligned, then rotate one around the y axis 45 degrees, and so on.

EDIT : hmmm the pictures don't make sense. Wether you check the edges or not, the test should return false as the boxes are clearly separated along the face normal going along the negative X axis. Unless it's a perspective effect.

##### Share on other sites
It's not a perspective effect.
I tried to add tolerance but it didn't change anything. I also tried to do a 12 + 12 + 12x12 check for all edges and normals but again, nothing changed.

I tried replacing the edgedirections in the calculation by the face normals, all edge checks, all normals checks, combinations with that, and it all gives the same result.

When both are axis alligned, it works. When 1 is rotated around the Y axis, it works. When both are rotated around the Y axis, it's inaccurate but the gap between them has to be pretty small. When 1 is rotated around the X and Y axis, it's terribly inaccurate and there can be a huge gap between them and it still detects collision.

1 rotated around Y
1 rotated around Y, collision

1 rotated around both X and Y
1 rotated around both X and Y, collision

Both rotated around Y
Both rotated around Y, collision

##### Share on other sites
this is mad. I can't find anything wrong in the code example. The last example should return no collision even before doing the edge-edge tests.

Clutching at straws here, but did you clear the boxes' collided flag before calling the routine.

Basically, you need to check the numbers, single stepping through the code... Because that is the SAT, and the SAT works!

##### Share on other sites
Try normalizing the axis in TestIntersection for the edge code before the call to GetInterval.

Edit: Actually I think that shouldn't matter unless you want an accurate penetration depth, but shouldn't hurt to try.

##### Share on other sites
I'm an idiot...
I found the problem. I'm storing the 3 normals and 3 edge directions in a struct that contains 2 arrays. When it has to update the normals and directions, it adds the updated values to that struct, but if the arrays are already filled, it doesn't do anything. So basically, the calculation was correct, it draws them correctly but they didn't get stored so the checks kept using the original normals and directions with the updated vertex intervals.

Now I just need to expand it a bit so it returns the difference and I can push one back.
But first I think I'm gonna go hate myself for a while.

Thank you so much everyone, I couldn't have done it without your excellent links and explanations.

##### Share on other sites
no worries. Calculating the separation vector (aka MTD, push vector...) can be extracted from the SAT as well, without normalisations.

##### Share on other sites
I really hate bothering you even more than I already have but you seem so experienced in this.

I can barely find any info on getting the push vector. The one I did find requires the distance between the 2 centerpoints, which I don't have.
I tried doing an extra check using my movement direction axis and getting those intervals but the results weren't accurate at all.
Any chance you have some wisdom to share on this?

##### Share on other sites
for each axis you check, you have
- axis direction
- min, max of box1
- min, max of box2

the min-max values will tell you how much the objects intersect along the axis.

examples :

Quote:
  mina maxa---------|--------------------|------------------ minb maxb----------------------|--------------------|-------- push |-------> mina maxa--------------------|--------------------|------------------ minb maxb----|--------------------|------------------ push <----| mina maxa---------|---------------------------|------------------ minb maxb-------------------|------------|------------------ push |----------------->

among all the 15 push vectors for each axes, you take the one that gives you the smallest length (the minimum translation distance, or MTD).

Quote:
 bool TestAxisIntersection(const Vector& axis, const CollisionBox& a, const CollisionBox& b, Vector& mtd, float& mtd2){ // compute intervals float mina, maxa; float minb, maxb; GetInterval(a, axis, mina, maxa); GetInterval(b, axis, minb, maxb); // compute the two possible interval intersections float tolerance = 1.0E-8f; float d0 = maxb - mina; float d1 = maxa - minb; // intervals don't intersect // therefore the box dont intersect if(d0 < tolerance || d1 < tolerance) return false; // minimum intersection between the two intervals float d = (d0 < d1)? -d0 : d1; // length of axis, squared float axis2 = axis.DotProduct(axis); // push vector along axis (normalised). Vector push = axis * (d / axis2); float push2 = push.DotProduct(push); // length squared // in the push vector along axis the minimum among all push vectors // or we haven't computed a push vector yet, use this // as our best candidate. if(mtd2 < 0.0f || push2 < mtd2) { mtd = push; mtd2 = push2; } // boxes intersected along axis. return true;}bool TestIntersection(const CollisionBox& a, const CollisionBox& b, Vector& mtd){ // length of mtd (push vector), squared. initialised to impossible value. float mtd2 = -1.0f; // reset push vector to zero. mtd = Vector(0, 0, 0); for(int i = 0; i < 3; i ++) { if(!TestAxisIntersection(a.QuadDir[i],a, b, mtd, mtd2)) return false; } //...... // ect //......}

[Edited by - oliii on June 4, 2009 11:24:38 AM]

##### Share on other sites
Thank you so much, it works great.
Although, when a collision is detected, it looks for the shortest vector to get out of the overlap. I want it so that it gets pushed back in the oposite direction as my initial movement.

I tried this:
        public bool TestIntersection(CollisionBox cbox1, CollisionBox cbox2, ref Vector3 mtd)        {            // length of mtd (push vector), squared. initialised to impossible value.            float mtd2 = -1.0f;            // reset push vector to zero.            mtd = new Vector3(0, 0, 0);              // example of te movement of box1            Vector3 dir = new Vector3(1,0,0);            Vector3 x;            if (!TestAxisIntersection(ref dir,ref cbox1, ref cbox2,ref mtd, ref mtd2))                return false;            x = mtd;            //... all the checks            float length = (x.X + x.Y + x.Z) / 3;            x = Vector3.Multiply(dir, length);            mtd = x;            cbox1.Collides = true;            cbox2.Collides = true;            return true;

It works most of the time but not always so I'm guessing this probably isn't the right method.

##### Share on other sites
I suppose you can detect the minimum MTD by doing the dot product of the axis MTD against the velocity, and take the minimum. I dont think that will give you always the best case, but you can also do a swept test, to fond the tine of collision, and also the normal of collision.

The code is a bit more complicated though. Worth 1/2 hour. This is lifted from the 2D polygon test, and not tested.

Quote:
 struct Box{public: Box() : m_centre(Vector(0, 0, 0)) , m_halfsize(Vector(0, 0, 0)) , m_color(0x00000000) { m_orientation[0] = Vector(0, 0, 0); m_orientation[1] = Vector(0, 0, 0); m_orientation[2] = Vector(0, 0, 0); } Box(const Vector& centre, const Vector& halfsize, const Vector* orientation, unsigned int color) : m_centre(centre) , m_halfsize(halfsize) , m_color(color) { m_orientation[0] = orientation[0]; m_orientation[1] = orientation[1]; m_orientation[2] = orientation[2]; } void render() { RenderBox(m_centre, m_halfsize, m_orientation, m_color, 0xffffffff); } // Separation Axis Theorem interface. virtual int SAT_FaceCount() const { return 3; } virtual const Vector& SAT_FaceNormal(int index) const { return m_orientation[index]; } virtual int SAT_EdgeCount() const { return 3; } virtual const Vector& SAT_EdgeDir(int index) const { return m_orientation[index]; } virtual void SAT_Project(const Vector& axis, float& min, float& max) const { float rx = fabs(axis * m_orientation[0]) * m_halfsize[0]; float ry = fabs(axis * m_orientation[1]) * m_halfsize[1]; float rz = fabs(axis * m_orientation[2]) * m_halfsize[2]; float c = m_centre * axis; float r = rx + ry + rz; min = c - r; max = c + r; } void place(const Vector& position) { m_centre = position; }public: unsigned int m_color; Vector m_centre; Vector m_halfsize; Vector m_orientation[3];};struct SAT{public: //---------------------------------------------------------------------------------------------------- // test collision and intersection along a direction. // axis : the direction along which test for collision // a, b : the two collision boxes. // vel : relative velocity of box a against box b // mtd, mtd2, intersecting : current state of our separation vector. // Nenter, Nleave, tenter, tleave, colliding : current state of when and where the two boxes collide along vector 'vel'. //---------------------------------------------------------------------------------------------------- static bool TestAxis( const Vector& axis, const Box& a, const Box& b, const Vector& vel, // axis and box info Vector& mtd, float& mtd2, bool& intersecting, // intersection info Vector& Nenter, Vector& Nleave, float& tenter, float& tleave, bool& colliding) // collision info { // intervals along axis float mina, maxa; float minb, maxb; a.SAT_Project(axis, mina, maxa); b.SAT_Project(axis, minb, maxb); // calculate the two possible overlap ranges. // either we overlap on the left or right sides. float d0 = (maxb - mina); // 'left' side float d1 = (maxa - minb); // 'right' side float v = (axis * vel); // project velocity on axis for swept tests // test intersections intersecting &= TestAxis_Intersection(axis, d0, d1, mtd, mtd2); // test collisions colliding &= TestAxis_Collision(axis, d0, d1, v, Nenter, Nleave, tenter, tleave); // we should be either intersecting or colliding return (intersecting || colliding); } static bool TestAxis_Intersection( const Vector& axis, float d0, float d1, Vector& mtd, float& mtd2) { // the axis length squared float axis_length_squared = axis * axis; // axis is degenerate. ignore. if(axis_length_squared < 1.0E-8f) return true; // intervals do not overlap. no intersection. if(d0 < 0.0f || d1 < 0.0f) return false; // find out if we overlap on the 'right' or 'left' of the object. float overlap = (d0 < d1)? d0 : -d1; // the mtd vector for that axis Vector sep = axis * (overlap / axis_length_squared); // the mtd vector length squared. float sep_length_squared = (sep * sep); // if that vector is smaller than our computed MTD (or the mtd hasn't been computed yet) // use that vector as our current mtd. if(sep_length_squared < mtd2 || mtd2 < 0.0f) { mtd2 = sep_length_squared; mtd = sep; } return true; } // SAT collision along an axis. t_enter and t_leave represent the first time of collision, and the time // when the objects stop intersecting. static bool TestAxis_Collision( const Vector& axis, float d0, float d1, float v, Vector& Nenter, Vector& Nleave, float& tenter, float& tleave) { // velocity perpendicular to axis or axis degenerate or velocity too small. ignore test. if(fabs(v) < 1.0E-8f) return true; Vector N0 = axis; Vector N1 = -axis; float t0 = d0 / v; // estimated time of collision to the 'left' side float t1 =-d1 / v; // estimated time of collision to the 'right' side // sort values on axis so we have a valid swept interval. if(t0 > t1) { float ttemp = t0; t0 = t1; t1 = ttemp; Vector Ntemp = N0; N0 = N1; N1 = Ntemp; } // swept interval outside our range. if(t1 < 0.0f) // || t0 > 1.0f) return false; // first swept test. if(tenter > tleave) { tenter = t0; tleave = t1; Nenter = N0; Nleave = N1; return true; } // collision missed. if(t0 > tleave || t1 < tenter) return false; // minimise the collision interval if (t0 > tenter) { tenter = t0; Nenter = N0; } if (t1 < tleave) { tleave = t1; Nleave = N1; } // colliding. return true; } static bool TestBoxes( const Box& a, const Vector& va, const Box& b, const Vector& vb, Vector& mtd, Vector& ncoll, float& tcoll, bool& colliding, bool& intersecting) { intersecting = true; colliding = true; mtd = Vector(0, 0, 0); ncoll = Vector(0, 0, 0); tcoll = 0.0f; // initialise to impossible values. float mtd2 = -1.0f; float t_enter = 1.0f; float t_leave = 0.0f; // the normals of the faces when we first collide, and when the two objects stop intersecting along the velocity vector. Vector n_enter; Vector n_leave; // relative velocity of the boxes. Vector vel = (va - vb); // test a face dirs for(int i = 0; i < a.SAT_FaceCount(); i ++) { if(!TestAxis(a.SAT_FaceNormal(i), a, b, vel, mtd, mtd2, intersecting, n_enter, n_leave, t_enter, t_leave, colliding)) { return false; } } // test b face dirs for(int i = 0; i < b.SAT_FaceCount(); i ++) { if(!TestAxis(b.SAT_FaceNormal(i), a, b, vel, mtd, mtd2, intersecting, n_enter, n_leave, t_enter, t_leave, colliding)) { return false; } } // test edges cross dirs for(int i = 0; i < a.SAT_EdgeCount(); i ++) { const Vector& a_edge = a.SAT_EdgeDir(i); for(int j = 0; j < b.SAT_EdgeCount(); j ++) { const Vector& b_edge = b.SAT_EdgeDir(j); Vector axis = a_edge ^ b_edge; if(!TestAxis(axis, a, b, vel, mtd, mtd2, intersecting, n_enter, n_leave, t_enter, t_leave, colliding)) { return false; } } } // no intersections were ever tested. if(mtd2 < 0.0f) intersecting = false; // no collision were ever tested. if(t_enter > t_leave) colliding = false; // intersection failed. reset mtd to 0. if(!intersecting) { mtd = Vector(0, 0, 0); } // we have collided. setup collision params. if(colliding) { tcoll = t_enter; ncoll = n_enter; ncoll.Normalise(); } // no collision reported (box could have the same velocity). // in that case, use the mtd as normal of collision. else { if(intersecting) { ncoll = mtd; ncoll.Normalise(); } } // return intersection or collision. return (colliding || intersecting); }};

NOTE : the operator '*' between two vectors is a dot product.
NOTE : the operator '^' between two vectors is a cross product.

[Edited by - oliii on June 24, 2009 4:30:11 AM]

##### Share on other sites
The collision part is based on a ray-box intersection routine (or indeed a ray versus any convex object). It would take a while to explain, but if you look at some ray-tracing example, they'd be using something similar.

http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm

[Edited by - oliii on June 5, 2009 9:38:39 AM]

##### Share on other sites
Thank you oliii that worked perfectly
Thank you so much for all your help

##### Share on other sites
Hmm I can't get it to work correctly.

I do

falling from the sky
MyObject.Move(0,-5,0);

then I try the collisioncheck
bool check = Engine.CollisionChecker.CollBoxAx_CollBoxBx(OurHero.GetModel(), "foot", MyObjects.StaticLevelCollection.GetStaticObject("Island01").GetModel(),
"ground", new Vector3(0, -0.5f, 0), new Vector3(0, 0.5f, 0), ref mtd, ref normal, ref time, ref intersect, ref collide);

It detects collision when there isn't any and the mtd is never accurate.

##### Share on other sites
I'll have to look into it in more detail.

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

• ### Forum Statistics

• Total Topics
628379
• Total Posts
2982350

• 10
• 9
• 15
• 24
• 11