There are a 2 steps, as the others already mentioned:

1) calculating the separating vector (normal+signed distance, where negative distance implies penetration)
2) gathering all contact points, potentially using information from step 1

SAT and GJK provide solutions for step 1 (GJK doesn't calculate penetration, it relies on another approach)
Olivier Renault (oliii's) SAT tutorial called Cube3d.zip is a good starting point.

At http://bullet.sf.net I provide an open source collision detection and rigid body dynamics library, Bullet, that includes solutions for 1 and 2, using GJK and SAT. The CcdPhysicsDemo shows stable stack of cylinders.

For 2, by default Bullet has a complex contact point reduction algorithm, so it works with implicit shapes like cylinder, cones as well as convex polyhedra, boxes, spheres etc, all using GJK. Therefore, instead of calculating all points in one go, it collects them over several frames and performs reduction. Alternatively Bullet provides a direct contact clipping approach for polyhedra, that calculates all contact points based on the separating normal and the most parallel features. (this is not enabled by default, and the sources are in 'Extras/SATCollision'). This is similar to oliii's approach.

In Bullet, I prefered to use GJK and contact caching/reduction, so one code path can solve all combinations. However, Bullet allows to register collision algorithms for each pair, so it is easy to compare SAT with GJK, and contact caching/reduction with direct clipping. The constraint solver stores extra information in the cached contact points, like the previous frames solution (warm starting).

Hope this helps,
Erwin Coumans
http://continuousphysics.com

Quote:Original post by daniel_i_l
Thanks, but i really have no clue how the clipping works, do you think that you could provide some links or an explanation?

Just as a side note, be aware that implementing robust collision detection and response at the level under discussion here is non-trivial. If you're pursuing it out of interest by all means do so, but if this is more in the service of a particular game or project, you might consider either a less complicated collision detection and response scheme, or perhaps a third-party library. Just something to think about.

As for your question, the type of clipping that will be required depends on the support feature pair, that is, the two support features, one from each box, along the minimum axis. The possible support feature pairs and clipping types are:

1. vertex-vertex

Obviously no clipping is required here (or the clipping is trivial, depending on how you want to look at it). This case will hardly ever, if ever, occur in practice.

2. vertex-edge

Similarly, this case is very unlikely; the point of contact is trivially the vertex.

3. vertex-face

Again the point of contact is trivially the vertex; this will probably be the most common type of contact.

4. edge-edge

This type of contact may be fairly common, depending. In most cases the edges will be skew with respect to one another, in which case the contact point can be computed as the average of the pair of closest points between the two line segments. The algorithm for finding this pair of points is well documented and is described and implemented at geometrictools.com, in Graham's article in GPG, and many other places. Googling 'closest point line segments' will probably also turn it up.

In the exceedingly rare case where the edges are parallel or nearly parallel (not so rare, I suppose, if the boxes have one axis that has a consistent alignment), the line segments must be clipped together to find the pair of points that describes the contact manifold. Robustness issues are introduced here, as an appropriate tolerance must be used for detecting the parallel case, otherwise the closest-points algo may fail. The clipping can be done by projecting the endpoints of one segment onto the other segment, and finding the set intersection in the parametric space of the second segment. Not entirely trivial, but pretty easy, especially compared to...

5. edge-face

In an environment where no particular orientation or set of orientations is favored, this will be rare. Here you actually have to perform 'real' clipping of the line segment against the extruded planes of the face. Robustness is again an issue here, since the segment may be parallel or nearly parallel to one or more face planes (well, exactly two in the case of an OBB).

6. face-face

Again, fairly uncommon, and requires the same attention to detail with respect to clipping. Here you apply the Sutherland-Hodgman clipping algorithm to one of the faces against each of the extruded planes of the other face in sequence. Be aware that the SH clipping algo is not always presented in the same way, and some implementations are less robust than others. For an excellent discussion of this (and many other things relevant to this topic) check out Christer Ericson's book.

Now although I described some of these cases as rarely occuring, if your environment includes gravity, and you wish for objects to stack and/or come to rest, those cases will move from the 'rare' category to the 'inevitable' category. In this case your edge-face and face-face clipping functions will get a workout.

Anyway, that's a brief summary of at least one way you can go about it. As shown in previous posts there are several different approaches and algorithms you can bring to bear on the problem. Alas, none of them is trivial, and once you get your coldet working you still have the physics to contend with!

Quote:
Just as a side note, be aware that implementing robust collision detection and response at the level under discussion here is non-trivial. If you're pursuing it out of interest by all means do so, but if this is more in the service of a particular game or project, you might consider either a less complicated collision detection and response scheme, or perhaps a third-party library. Just something to think about.

Feel free to use and learn from Bullet's collision detection and physics library. It supports not only boxes,spheres,capsules, but also convex hulls, implicit cylinders and cones and all convex combinations (and static triangle meshes obviously).

So the contact point management is more complex then just clipping, because in the case of non-polyhedral convex collision shapes there are no vertices,edges and planes available. Instead, a contact reduction and contact caching mechanism is used, that updates existing points. Additionally the constraint solver stores its solution in each contact point, for faster convergence.

When points,edges,planes are available, its good to use oliies description of clipping (its implemented in Extras/SATcollision.

Thanks,
Erwin
https://bullet.sf.net

Quote:1) lets say that i get a face-face collision, does it matter which face i take as the clipping plane and which face gets clipped?

Not really. In a perfect world the results would be exactly the same either way; in practice they will be slightly different depending on which face gets clipped, but I can't think of a reason at the moment why you would choose one face over the other.

Quote:2)for the EdgePlane.Position can't I just use A? why the dot products?

I think it's just a little confusion of terminology. I'm guessing that 'Position' here actually refers to the plane distance, which is a scalar value computed as the dot product of the plane normal and any point on the plane (such as A).