Hey guys!

Been trolling these forums for years now, finally decided to sign up and not lurk anymore. =)

I'm the physics programmer in my team and I am trying to implement OBBs in 3D. It's been a bit of a challenge, as there is a lot of good reference material (thanks Randy Gaul, Dirk Gregorious and Erin Catto, among others) but most of it pertains to 2D collision.

And I get it! You can extrapolate that to the third dimension, but it's hard sometimes you know?

Anyway, I'm working on generating contact points. Been following this tutorial:

dyn4j.org/2011/11/contact-points-using-clipping/

It's allowed me to understand the clipping process, at least in 2 dimensions. When I implemented it however (naively expecting the process to still apply for 3D) I obviously did not find the results to my satisfaction.

Later on when I saw Dirks 2013 GDC slides, I saw that an object in 3D must have at least 4 contact points in its manifold!

And it was only too obvious in hindsight.

Anyway, the problem itself.

1) There is a lot of mention made about edge - edge collisions being clipped differently from *something*-face collisions. Which makes absolute sense, it's just that I am drawing a blank as for HOW to know a collision is of a specific type.

2) When you know that a collision is *something*-face, the problem then becomes clipping an edge/face against the plane of a face for example.

David Eberlys paper "Clipping a Mesh Against a Plane", has some algorithms that allow you to deal with this.

I understand how vertex clipping and edge clipping work. Which are fine in 2D, but when you ascend to 3D, you need face clipping as well.

But I cannot for the life of me understand how face processing is supposed to happen.

An explanation with an example would be a tremendous help.

Thanks!

Hi there, looks like you're on the right track. Have you seen this explanation and this source code example? For your specific questions:

1. The type is determined by which axis is the axis of minimum penetration.
2. Only clip faces to another face. With OBBs this clipping can be done in an orthographic manner with 1-dimensional lerps. See my linked code example, search for q3Orthographic. For edge to edge a closest point computation can gather enough info to make some good contact points.

Hope this helps! Overall creating contacts is a bit of an art since we have to approximate the volume of intersection (manifold) and lends to some open interpretation :)

Hey Randy!

I'll admit I'm a teeny bit starstruck right now, cause I've been learning everything I know of physics from your excellent resources. Thanks for compiling those by the way!

I've taken a look at that explanation and the source code, and some of the specifics of the orthographic clipping are going over my head. I'm going to try to explain what I think is going on, and hopefully it is right. If not, feedback on where I am going wrong would be helpful.

1) Arguments to the function are the input vertex set to be clipped (from each face), number of vertices, and the resultant vertex set after clipping. I'm assuming that 'axis' is the index of the axis the clipping is being performed on (x, y or z), 'sign' is used to flip the values being calculated for either body. 'e' is still an enigma. If you could point me to where qOrthographic is called it might help in gaining more context about what 'e' is supposed to represent.

2) 'a' and 'b' are two vertices, if both 'a' and 'b' are in front of(positive side of plane), or on the plane of clipping, they are not clipped. If either of them are on the negative side of the plane (Behind) then you interpolate to find the new clipped point. After all this clipping is done and the final vertex set is produced, you return the count of output vertices. Is this the manifold? (ClipVertex * out)

3) I'm not sure why/how the ClipVertex 'cv' has an unsigned integer being used to represent its Reference and Incident edge. Or why there is an InR and OutR (similar for I). Or perhaps R and I mean something else in this context?

But I think I begin to see the idea behind this orthographic clipping. I'm so close I can taste it! Accurate 3D OBB collisions will yet be mine!

EDIT : After reading this : http://gamedevelopment.tutsplus.com/tutorials/sutherland-hodgman-clipping--gamedev-11917 some of my previous question were cleared up. However I now have some new ones.

for ( i32 i = 0; i < 4; ++i )  
    in[ i ].v = q3MulT( basis, incident[ i ].v - rPos );

What does 'rPos' represent here? I feel like this code is used to transform from the world space to the object space of one of the other objects so as to simplify the math.

Gah, don't mind the question about where qOrthographic is called. The function qClip is what calls it, right after qOrthographic. I'm as blind as a bat.

Dirk Gregorius wrote down the details about using SAT for convex objects and about plane clipping also in this old thread:

http://www.gamedev.net/topic/667499-3d-sat-problem/

In general, we have the following cases. (Achronyms for features: V = Vertex, E = Edge, F = Face.)

FV/FE/FF, VF/EF/FF, EE, and VV.

Since VV only occurs if the shapes aren't actually penetrating, then you handle it in the FF case. FV/FE/VF/EF are handled by the FF case.

Then you use Dirk's implementation. Here's an example of clipping if you need help: https://github.com/irlanrobson/Bounce-Lite/tree/master/Src/Collision.

Note: In this code you could actually have an early out when checking the separations (e.g. if (separation > 0.0f) then quit), but ultimately you want to search for a best axis so you can cache it and gain temporal coherence succesively between frames.

3) Maybe I can answer this before Randy. This is because you need unique contact IDs. With clipping, clipping points are uniquely defined by the features that clipped out them. So I guess InR means incoming reference and inI means incoming incident.

To add to what Irlan wrote: Collecting information about colliding features is important to cache solutions for the constraint solver over multiple frames. If features can be uniquely identified then caching solutions can be implemented. Box2D Lite has an example of implementing this feature tracking. It's not much different for 3D.

1. e stands for "extent vector" of an OBB. 'sign' is for a 1-dimensional dot product -- it's computing distance to plane. In 3D we have ax + by + cz - d = 0, in 1D we have ax - d = 0, so 'a' is 'sign' and 'e' is 'd', where in general d can be thought of as distance of plane to the origin.
2. I think you're right. To be sure check out Christer Ericson's orange book "Real-Time Collision Detection", he has a good chapter on Sutherland-Hodgman clipping. The "I, B" comments come from his book.
3. (read Irlan's post and Dirk's forum posts)
4. rPos is probably reference position. Affine transformations are of the form Ax + b, where A is a linear transformation (in q3's case just rotation), and b is a translation vector. rPos is b. To invert Ax + b we can do: A^T * (x - b). Being comfortable transforming data to and from different spaces is an important skill and, like you observed, can simplify a lot of calculations.

Thank you so much for all your help guys its' been invaluable. =)

I've made some progress! Not much, but some..

The contact points are being generated and are somewhat close to being correct. You'll see in the picture below, the 4 points are offset from the right most cube (the OBB they are the contact points of).

[attachment=30816:Capture.JPG]

And in some cases it actually delivers correct values. It's hard to capture in a screenshot as the contact points are occurring within the body itself and hence the camera occludes the mesh.

It seems to be working when there is no rotation involved in the OBBs configuration. (or at least that is my first guess at what is wrong)

Any ideas/suggestions? As always, the advice is appreciated. =D

EDIT: Changed how I was finding the reference and incident faces, and suddenly things seem to be a lot more accurate. Are these contact points right?

[attachment=30817:Capture.JPG]

Everything seems to be bouncing and moving as it should.

I'm using a global restitution value of 0.2 right now, as I haven't yet implemented it for individual objects.

Things are moving accurately, however I cannot seem to get resting contact (i.e. the objects to lie on the surface ,even if jittering slightly, due to minimal amounts of impulse, not the actual resting contacts method by a LCP solver or anything).

When applying the impulse to a 3D body, how do I fit the fact that I have more than 2 manifold points into the impulse formula?

From Chris Heckers 1997 article in Game Developer, I have derived and understood the impulse formula, but considering that you need to take cross product of the vector from the center of mass to the contact point (manifold values) and the collision normal, how do you use those manifold values here?

[attachment=30818:Capture2.JPG]

EDIT 2: Contact points working!

[attachment=30819:Capture.JPG]

I needed to clip the output polygon of the Clipping functions by the reference plane to obtain the final manifold.

So basically everything is done except the impulse resolution bits. Would love some help on this last stretch! So very close!

1) No.

2) In the fancy formula Chris Hecker came up with, j is also called lambda, the magnitude of a contact impulse for only *one pair of body*. Generally you solve for this formula for each manifold point. This is fine for a sphere on a plane since you have just one contact point. But in your case you have more than just one. Therefore, consider using the constraint-based formulation. For that we recommend reading Erin Catto slides on the subject or even searching here on the forum. That will save you and us a few words.

After you have the incident face clipped by the reference face *side* planes, you only keep in the manifold the points whose distance (actually the penetration) to the reference plane is below or equal to zero. Do not clip against the reference face since it adds unecessary points to the manifold!

Hey guys,

At this point the OBBs are colliding perfectly well with AABBs. I need to look into Sequential Impulse resolution, but I'm setting that aside for now.

An issue I've been facing is getting the OBBs to collide with other OBBs. I believe this is because of the Inverse Transformation I am using to unify the basis of the calculations.

Here is the code for getting the inverse transform to use:

inline glm::mat4 GetInverseTransform() const {
Transform * t = mOwner_->GetComponent<Transform>();
// "If I put on socks and then shoes, to reverse the operation I must first take off my shoes and then take off my socks."
// http://www.randygaul.net/2014/05/17/transposed-matrix-properties/
return glm::transpose(glm::mat4_cast(t->GetOrientation())) * glm::inverse(glm::translate(t->GetPosition()));
}

For the OBB whose world space I am transforming to the other OBBs model space, this is how I perform the transformation:

ComputationCenter = glm::vec4(self.GetCenter(), 1);
ComputationCenter = other.mOwner->GetInverseTransform() * ComputationCenter;

For the OBB whose model space the calculations are performed in, to convert it to its own model space from world space:

ComputationCenter = glm::vec4(self.GetCenter(), 1);
ComputationCenter = self.mOwner->GetInverseTransform() * ComputationCenter;

Some clarification on this would be helpful. Don't we need to take translation into account for the inverse transform? Otherwise it wouldn't be centered around the origin...

After more than a day spend restructuring my transforms to look more like Irlans in his Bounce3D project, despite having the exact replica of the code, I have not achieved success.

I am making the decision to move forward with my version instead, seeing as I understand it better anyway. However, I am still at a blank when it comes to the transforms.

Would appreciate any and all help.