General OBB question
Author
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.
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.
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.
Author
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.
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.
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.
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.
Author
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?
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?
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]
[Edited by - Dancin_Fool on May 31, 2009 12:53:57 PM]
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.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 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.
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).
Author
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.
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.
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]
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]
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)
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)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
