Hi all! I need to compute the contact set (for collision/contact handling) for two convex polytopes when they are penetrating each other. The rest of my computation (non-penetration case) work very well, but til now I couldn't find a good algorithm which delivers me the correct penetration-contact set for (nearly) each case. For each contact-point-pair I'd need the collision points, normals and penetration depth! For collision detection I use V-Clip and my contact-set-algorithm by now uses the separating axis theorem to find the minimum penetration direction & depth. Afterwards I return those extremal features to compute the contact set... But it just doesn't work in each case. Is there a better way to compute it, or an existing algorithm which I could use (found nothing on google)? Atm it doesn't matter how good the performance of the algo is... Thanks in advance!

I'll give it a shot.

Using your contact normal, you can determine the supporting features of the two convexes. You will get either a point, a edge, or a face (a convex polygon). Or you may have another method to determine what the supporting feature is, what matters is that you can get a point, edge or face, for each convex.

if you do that for both convexes, you will have a few cases to deal with.

point-point (although using the SAT, that should never occur realistically).
point-edge (again, not a feasable state given how the SAT works).
point-face
edge-point (again, not a feasable state given how the SAT works).
edge-edge
edge-face
face-point
face-edge
face-face

for each the possibilities, that will give you pairs of contact points.

point-point is straight forward, the contact pairs are the points themselves.

point-edge, one contact is the point, the other contact is the closest point on edge.

edge-edge, the contact pairs are the points on the edges the closest to each other.

edge-face, means you will have two pairs of contact points, that you can find by 'clipping' the edge with the face extrusion. The other part of the contact pairs would be the points on the polygon the closest.

face-point, the contact pairs are the point, and the point on the face the closest.

face-face, you will need to clip one face with the extrusion of the other.

By clipping, if you imagine looking down on the two supporting features, along the collision normal, you should get the idea.

I also apply this method for swept tests.

Black-Panther, just a head’s up: the V-Clip algorithm is patented, which is why it is never used.

Legally you would need to switch to Johnson-Gilbert-Keerthi or Chung-Wang, which brings me to a follow-up of this same question.

#1:
What are the advantages of using Johnson-Gilbert-Keerthi over Chung-Wang? Chung-Wang is a million (give or take) times easier to implement and much faster when the last separating plane between 2 objects is used to start the next query between them. Yet Johnson-Gilbert-Keerthi remains the most popular and Chung-Wang is seldom mentioned. Chung-Wang does not give detailed penetration information, but Johnson-Gilbert-Keerthi returns unreliable penetration information and is only acceptably accurate when used in sweeping. In that case, you could use Chung-Wang in sweeping as well and get just-as-accurate penetration information (right)?


#2:
If everything I said above is true then Chung-Wang would be the hands-down most popular algorithm, so I am going to assume some kind of error in my assumptions. If there is one, it should be related to getting accurate penetration information (I have not yet seen an implementation for either algorithm in that respect).
If he/I switches to/implement either the Johnson-Gilbert-Keerthi or Chung-Wang, how does that change the answer to his question? Both of them just return a collision and a general idea of where it is, and you still have to use that information to do a closest-features test. Right?


L. Spiro

I'll add another one, the Minkowski Portal Refinement.

V-Clip is patented?? I found a paper where it is described (with pseudo-code) perfectly, this is why I implemented it... Are you sure about that?
Anyway, I implemented Chung-Wang as well... So there would be no problem to change to that one!

@oliii
Thanks for hints, but that far I already was... The problem is, that the contact sets aren't computed in a right manner, when interpenetration occurs...

Perhaps it helps if I show some code?

Contact-Set-Computations

Edit:
"
This work may not be copied or reproduced in whole or in part for any commercial purpose. Permission to copy in whole or in part
without payment of fee is granted for nonprofit educational and research purposes provided that all such whole or partial copies include
the following: a notice that such copying is by permission of Mitsubishi Electric Research Laboratories, Inc.; an acknowledgment of
the authors and individual contributions to the work; and all applicable portions of the copyright notice. Copying, reproduction, or
republishing for any other purpose shall require a license with payment of fee to Mitsubishi Electric Research Laboratories, Inc. All
rights reserved.
"

How I understand this, I am allowed to use it for non comercial purposes?

If you never want to sell your product you can use it (if you put that entire copyright notice in your source along with its other instructions).
Personally I feel that patenting such an algorithm is just slapping people in the faces and driving the algorithm away from success (not to mention a petty attempt at milking dollars from people when there are already better alternatives available), so I would not use it anyway regardless of whether or not my usage fell under their terms. But that is just me (though I admit I do have a patent myself related to iPhone/iPod touch devices).


L. Spiro

Hmm... You spoke of better alternatives? Which algorithm works better than V-Clip? I didn't find one!