Jump to content
  • Advertisement
Sign in to follow this  

Differentiating between an edge-edge and *something*-face collision

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:




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.



Share this post

Link to post
Share on other sites

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 :)

Edited by Randy Gaul

Share this post

Link to post
Share on other sites

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. biggrin.png


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! laugh.png


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. smile.png

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.

Edited by Nightmask3

Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites

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




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




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.


Generally for the face-face case use Sutherland-Hodgman clipping. Since in the edge-edge case you don't check paralell edges and they must be overlapping then use the closest point between the *lines* made of those edges. Quick looked at Randy's code and that might be q3EdgesContact. Here is another example commented out. If you are stuck on how to do this part then use Chister Ericson RTCD book to understand. This might save you quite few words here and ultimatelly help you to understand.


1) Basically, you just choose the feature that realize the minimum separation axis. 


If I would to implement that again I would check first if I really need generic shapes or specific ones. If you plan to extend your engine to more than just OBBs then it is worth to implement the general SAT. For learning, an specialization might help. In general there is basically no big difference if you're using the optimizations Dirk has mentioned.


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. 

Edited by Irlan Robson

Share this post

Link to post
Share on other sites

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.
Edited by Randy Gaul

Share this post

Link to post
Share on other sites

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



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?




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?



EDIT 2: Contact points working! 




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!

Share this post

Link to post
Share on other sites

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. 

r_1 = Manifold.Point - Body_1.CenterOfMass

r_2 = Manifold.Point - Body_2.CenterOfMass 


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!  

Edited by Irlan Robson

Share this post

Link to post
Share on other sites

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()));

Considering that the MVP matrix that converts from model space to World space, and the transformation is in the order : Scale, Rotate, Translate, the inverse transformation should be Translate, Rotate, Scale (but scale is not used as we want to take it into account).


Where am I going wrong here? The rotation seems to be the logical source of error, I am using a transpose to get the inverse which works because the rotation matrix is orthogonal. 


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;

I am however, having difficulties with resolving my method of doing things with how Randy has stated it here:


The relative rotation matrix to transform from B’s frame to A’s frame is defined as:  C=RTa?Rb




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

Edited by Nightmask3

Share this post

Link to post
Share on other sites

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. smile.png

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!