# Physics Simulation Forum

 All times are UTC

 Page 1 of 1 [ 13 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Help with GJK finding contact normal + positionPosted: Sat Oct 07, 2006 8:00 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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?

Top

 Post subject: Re: Help with GJK finding contact normal + positionPosted: Sat Oct 07, 2006 11:45 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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

Top

 Post subject: Posted: Sat Oct 28, 2006 12:15 am

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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

Top

 Post subject: Posted: Sun Oct 29, 2006 5:10 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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?

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

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

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

Top

 Post subject: Posted: Thu Nov 02, 2006 6:31 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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:

The FindPenetration method in that class is where I most need help.
Code:
static Vec2 FindPenetration(Shape s1, Shape s2)
{
final float iter = 8;
Vec2 diff = s2.position.Subtract(s1.position);
//diff.Normalise();
float ang = (float)Math.atan2(diff.y, diff.x);
Vec2 norm = new Vec2();
float minNorm = 100000;
for (int i=0;i<iter;i++)
{
Vec2 dir = new Vec2(ang + (float)((i-(iter/2))/iter * Math.PI * 0.25f));
//Vec2 dir = new Vec2(ang);
Vec2 p1 = s1.Support(dir);
Vec2 p2 = s2.Support(dir.Negate());
Vec2 s = p1.Subtract(p2);
float d = Vec2.Dot(s, dir);
if (d < minNorm)
{
norm = s;
minNorm = d;
lastPointA = p1;
lastPointB = p2;
}
}
return norm;
}

Top

 Post subject: Posted: Thu Nov 02, 2006 6:55 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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.

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

Code:
btGjkPairDetector::ClosestPointInput input;

btVector3 newOrg = transA.getOrigin() + offset;

btTransform displacedTrans = transA;
displacedTrans.setOrigin(newOrg);

input.m_transformA = displacedTrans;
input.m_transformB = transB;
input.m_maximumDistanceSquared = 1e30f;

MyResult res;
gjkdet.getClosestPoints(input,res,debugDraw);

float correctedMinNorm = minProj - res.m_depth;
if (res.m_hasResult)
{
pa = res.m_pointInWorld - minNorm * correctedMinNorm;
pb = res.m_pointInWorld;
}

Hope this helps,
Erwin

Top

 Post subject: Posted: Thu Nov 02, 2006 10:21 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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?

Top

 Post subject: Posted: Thu Nov 02, 2006 11:00 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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?

Top

 Post subject: Posted: Thu Nov 02, 2006 11:07 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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

Top

 Post subject: Posted: Fri Nov 03, 2006 12:58 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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

Top

 Post subject: Posted: Fri Nov 03, 2006 9:21 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
Thanks for your help, I think I've got it working now

Top

 Post subject: Posted: Sun Nov 12, 2006 4:19 pm

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
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

Top

 Post subject: Posted: Sun Nov 12, 2006 4:54 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 13 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: DannyChapman, Google [Bot] and 6 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities