Physics Simulation Forum

I have watched this tutorial video on the gjk:(https://mollyrocket.com/forums/viewtopic.php?t=245)

it describes the basics of how to detect a collision with a gjk, and i understand it for the most part. What im not so sure about is how I would go about using simplex containing the origin to determine the penetration depth, position of the contacts themselves, and the contact normal. I have tryed to read the papers on GJK, but as he sais in the video, they seem overly complex and I cant understand how to extract this information. Any hints?

I can recommend the GJK notes/presentation by Christer Ericson, see http://realtimecollisiondetection.net/pubs/

GJK doesn't calculate penetration depth by default. You can add a margin to collision shapes, which allows you to use GJK to calculate shallow penetration depth (not deeper then the added margins of the 2 involved objects). For a sphere, you can use the full radius as margin, and use a point as shape. As long as there is no overlap (without the margins) when GJK terminates, the simplex solver (either johnson or 'geometric/voronoi' can be used as world-space contact points.
For deeper penetrations, use either EPA (expanding polytope algorithm) or sample the pentration depth in several directions, using the support mapping.

Have you tried to learn from Bullet's implementation?
http://www.continuousphysics.com/Bullet ... tml#l00046

Thanks,
Erwin

if using a timestep of say, 1/60, is the deep penetration case unlikely enough that i could get by with using only the margin depth calculation method?

I looked at bullets code, but im still a little confused on the overall method. When you generate contact points using only the margins, how do you determine where exactly those are, and how many there are?

The way I see it, if two body's margins are slightly inside each other there will be an infinite number of points. I see that bullet does some kind of contact reduction based on the 4 most extreme points, which makes sense.

and just so im clear, the only information needed for valid impulse based dynamics are contact position (for both bodys?), as well as the normal from B to A, and a penetration depth

With default gravity and default collision margin (0.04) and units in meters, for resting contact you won't exceed penetrations deeper then 4 centimeter typically. So the deep penetration case only happens for collisions, and there you can sample (approximate) the penetration depth, like Bullet's btMinkowskiPenetrationDepthSolver. If you like you can also use a more accurate penetration depth method, called EPA (expanding polytope algorithm) but this is very complicated.

Bullet contains a contact cache and contact reduction. Every frame, the deepest point gets added to the cache, and the old points are updated. Both the reduction (up to 4 points, maximizing the area while keeping the deepest point) Certain heuristic is used to throw away points: points that exceed a certain distance.

The contact points position, normal and penetration depth and other information like mass, inertia, friction and restitution is needed. The 2 points are separated by the normal with the given penetration depth.

Hope this helps,
Erwin

I still havent figured out the shallow penetration thing, but im writing a small java program (2d) that shows the shapes, the minkowski difference, simpex and contact info.

I got the basic GJK working that tells me if two bodys are colliding or not, and I have tried to do what bullet does for deep penetrations by sampling the support function and finding the minimum distance, but its not really working how its supposed to (at least I think)

For two spheres, the sampling works perfectly and gives the right results all the time, but whenever I introduce something like a box or convex polygon with defined verticies, it either returns one vertex or the other, never a point on the line connecting them liek it should.

Its hard to explain exactly whats going on, but here is what I have if you would'nt mind taking a look. Its fairly cleanly written so its easy to follow. GJK.java contains the main method.
CollisionDetection.java contains all the collision detection and closest point code, I suspect my problem is in there somewhere, though it could also be in the support functions for all my shape types..

controls:
a,s,d,w - move the current shape
z,x - rotate current shape
q - change current shape

Link for the code + classes:
http://www.upshack.com/./uploaded-files/200611/GJKJava.zip

The FindPenetration method in that class is where I most need help.
(heres the method if you dont have time to download it)

Hi,

I haven't looked into your code yet, but the sampling penetration depth only finds a minimum translational vector: penetration depth+normal. You still need to run GJK once more to find the actual points as follows:

Separate the two objects by moving one object along this penetration vector so they come into touching contact. You can move this object a bit more, to make sure that GJK finds closest points. Then find the closest points, and project them back along the penetration vector.

See http://www.continuousphysics.com/Bullet ... tml#l00095



Hope this helps,
Erwin

Thanks for your help, I think I see how it works now, I just need to get the depth and normal right.

Does the code I posted above look like it should be returning the correct penetration normal/depth?

The problem only arises with shapes that have define verticies like the shaft of a capsule, sides of a box/polygon, ect.
Do I need to be returning more than one point in my Support function?

For sampling the penetration depth you don't need to calculate the actual points. In Bullet they are only kept for debugging. You just measure the minimum translational distance (penetration depth) given your own sampled normal directions (dir).

GJK will take care of finding the actual point, in a more complicated way. Only one support is returned for a given direction, if there are multiple candidates then just pick one.

Did you already implement or port GJK to java for non-overlapping cases?

At the moment I dont do anything if they do not overlap as I still cant get gjk to return a minimum distance.

But, it does work correctly in determining if they collide, and returns the simplex containing the origin.

Maybe I am getting confused on what exactly the penetration depth is. Im thinking of it as the vector between the origin and the closest point in the minkowski difference to the origin

You need GJK or EPA for penetration points that represent the penetration vector in worldspace. You are right, penetration depth is just a distance, penetration vector is the minimum translation that brings objects into contact.

If you just need distance and direction then you are fine.
If you need points in worldspace, you need GJK. Or EPA but let's not open a can of worms

You cannot transform the closest point to the origin in minkowski space into worldspace point. It might represent a 'collapsed feature': for example an edge in worldspace can collapse into one single point in minkowski space. There is no way of telling which point on that edge in worldspace is the right one, unless you measure it using GJK (or EPA).

Thanks,
Erwin

PS: apart from GJK, there is also SAT, separating axis theorem based approach, but this doesn't work as generic as GJK. If you just deal with polyhedra (that have vertices, edges, faces) you can use that too. Bullet includes an implementation in Extras/SATConvexCollision

Thanks for your help, I think I've got it working now

I took a look at Bullet's EPA implementation, and as you said, its very complicated

However, how does EPA's speed and accuracy compare with that of the random sampling?

From the looks of it, it seems like it would be faster because you dont need to call the support function many times, but i'm not really sure

The sampling method in Bullet takes a fixed number of orientations into account, they are uniform distributed over the unit sphere, so not really random. Also the latest Bullet 2.30 adds 'preferred' penetration directions, like the face normals of triangles and cubes, to improve accuracy.

Bullet's sampling method is more reliable then the EPA implementations, but less accurate and less performance indeed. A lot of cases don't require high accuracy: if your objects are fairly moderate sized and have enough collision margin, the penetration depth algorithm will seldomly called in practice. EPA can fail to find a 'starting tetrahedron' that encapsulates the minkowski origin, and also degenerate triangles can become problematic. Pierre Terdiman pointed out problems in EPA (http://www.continuousphysics.com/Bullet ... .php?t=638 ) and it is part of Bullet 2.30 in Demos/EPAPenDepthDemo (projectfiles are not in project solution, but can be manually added from msvc/8/ folder).

So in short: the most pragmatic solution is to use enough margin, hybrid GJK method and sampling the penetration depth.
Or investigate a lot of time in EPA, but still require some safety gap for the degenerate cases (like the sampling method). EPA is work-in-progress for Bullet.

Thanks,
Erwin