# Extracting face/hit data after a GJK step

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

## Recommended Posts

My collision routine returns the distance if valid. However, I seem to be missing a few basic steps, which might well be leading me down the wrong path.

1) once I have my simplex, is it safe to assume that:
a) in the case of one vertex (0-simplex), the collision is between a vertex and a vertex|edge|face OR an edge and an edge?
b) for a 1-simplex the collision is between an edge and any other feature, but NOT a vertex?
c) for a 2-simplex I can always use the three known indexes to match the colliding face on either shape?
d) for a 3-simplex the shapes are either touching or penetrating and require separation?

2) my main problem is coming up with a way to sample either object for a face, edge or vertex in case I arrive at a 0-, 1- or 3-simplex. In particular - I'm having trouble with balancing a smaller box on the edge of a larger one so that exactly half of it is hanging over the edge. I'm getting all kinds of screwy normals here, causing the smaller box to fall through the larger one when I try to balance and slide it around under gravity. Is the solution here to separate motion along all three axes?

For now all I want is a normal, but for that I need a direction in shape local space. How do I extract this from the simplex?

PS - I'm taking the dumb route and writing this stuff from scratch. Don't ask...

##### Share on other sites

A followup.

This thread has a fair amount of useful information on the issue. However, I'm still struggling with the edge/edge case.

Here's a top-down view of my test case:

The purple boxes are the floor. The small pink box is the subject resting on top of it, affected by gravity - hence it is falling down the z axis (away from the screen). It started centered exactly where the two floor meshes meet. Then it moved up along the y axis until it reached the edge of the floor meshes as shown, causing an edge/edge case simplex.

This is an extremely unfortuitous case, because the box is clearly resting on the floor, but the edge collision generates vertex pairs that on closer inspection run along the positive and the negative x-axis, respectively. This means the cross product between the two is zero, completely failing to extract any meaningful surface features. This causes the box to clip through the floor.

The points in the simplex do not follow consistent winding, which means that while I could otherwise use the vertex indexes to identify the face, that is not possible as a reliable solution.

I don't see any way to handle this case, except:

a) if an edge/edge case is detected and a previous non-edge/edge contact exists between the two shapes, ignore the current case and reuse those features
b) if no previous contact exists,  test if the edges are parallel as in this case:
b1) if not, extract the normal as Dirk suggests in the linked thread
b2) if yes, then the shapes are meeting for the first time exactly edge-to-edge, so pick a random face on either object that contains the vertices [a0, a1] or [b0, b1], respectively

Anyways - I'm looking for a more robust solution, so suggestions are very much welcome

##### Share on other sites

IIRC that thread was about identifying closest features of two *disjoint* convex sets. It sounds like you want to identify features that contribute to the axis of minimum separation in the colliding case -- this isn't something that can easily be done after running GJK, since GJK does not really help in this case.

##### Share on other sites
9 minutes ago, Randy Gaul said:

IIRC that thread was about identifying closest features of two *disjoint* convex sets. It sounds like you want to identify features that contribute to the axis of minimum separation in the colliding case -- this isn't something that can easily be done after running GJK, since GJK does not really help in this case.

Hm. My sets can be disjoint or touching, but not penetrating at the start of the measurement. In either case - the distance is calculated to determine the time of impact with the assumption that collision will occur during the current step. I need the surface features to know how to respond to this contact (calculate TOI and then stop or slide in my case).

The next best thing I can think of is raycasting to determine the faces involved, but this is also something I can't do without additional information from something that would give me a direction to test. GJK gives me a direction in most cases.

##### Share on other sites

You can't really use GJK to get the contact info unless you combine it with some other approach such as EPA (expanding polytope algorithm), or add a margin around the objects. The problem is that GJK only determines if the objects are intersecting, but not the exterior points on each object. If you try to use the final simplex to generate contact info, you will find that objects tend to sink into each other over time. The simplex does not necessarily lie on the surface of the minkowski difference.

In my engine, I use EPA to push the simplex boundary out to the edge of the minkowski difference. Then, the contacts can be determined from the nearest point on the minkowski difference to the origin in configuration space. EPA produces a convex hull made up of triangles and the contact lies on the closest triangle to the origin. Find the barycentric coordinates of the closest point on the triangle, then use those barycentric coordinates to find the point on each object (you need to store {pointOnA, pointOnB, pointOnB-pointOnA} for each convex hull vertex). This gives you 1 contact on each frame. You would then need to combine it with contact caching over multiple frames to get multiple contacts that are needed to achieve stable stacking.

Edited by Aressera

##### Share on other sites
18 hours ago, Aressera said:

You can't really use GJK to get the contact info [...]

This is actually what I was kind of afraid of, as alluded to in my original post. Thanks for clearing it up.

In any case - not being able to access more specific information largely defeats the purpose of my current narrowphase. I simply need surface features to perform things like sliding. Other than that I only need collision data for stuff like trigger overlaps - eg no actual physics.

##### Share on other sites

Even if you are implementing a TOI solver and then stop + slide, you will still have the possibility to enter colliding configurations, in which case you'd need full manifold generation in order to resolve the collision.

This is because when a TOI is found, your shape is moved to the TOI. However, you can't move *directly* to the TOI, otherwise you cannot perform a sliding action as the next TOI search will hit the previously found shape and not move at all. Typically people move their shape to the TOI and then back up ever so slightly to make a numeric buffer for the TOI solver to find the next subsequent TOI. This backing up action usually happens along the collision normal, meaning it's completely possible to back up into colliding configuration.

There are all kinds of weird solutions to this problem. Some people try "blacklisting" shapes, others trying solving for TOI on only one of the principles axes at a time, which effectively triples computational cost. Though so far the only working solution I've ever come up with is to just back up along the normal to create a numeric buffer.

Lots of people try to implement some kind of character controller or physics simulation using GJK as their only collision detection workhorse -- it's not possible the moment non-trivial behavior is needed. Typically this kind of endeavor comes from ignorance of how the GJK algorithm actually works. It is fairly obvious that in the colliding case there is no useful information as the algorithm terminates. Since the GJK simplex crawls through the middle of the volume via support points, the origin can be enclosed by any arbitrary simplex within the volume. This means when GJK terminates all you know is your two volumes intersect *somewhere*, with no intelligent book-keeping to tell you *where* the overlap occurred.

If GJK terminates with witness points (closest points), the contributing features are actually useful, since they are on known positions on each surface of each volume. These features are by definition the "closest features", and can be enumerated from the simplex vertices. However, care needs to be taken to look out for degenerate cases!

Once people realize this they panic and try and implement EPA to build a contact manifold, which is not a very favorable strategy in 3D for many reasons.

The only way to implement robust collision detection is old-fashioned building the contact manifold. Expanding Polytope Algorithm (EPA), (Separating Axis Theorem/Test) SAT-based alorithms, and Minkowski Portal Refinement (MPR) are the algorithms I am aware of. In my opinion the best by far are the SAT-based algorithms for both 2D and 3D.

Edited by Randy Gaul

##### Share on other sites

After GJK returns it is challenging to extract feature information. It will provide you a separating axis which realizes the closest points. You can then use this axis to find the support faces on each shape. That means you scan for the most parallel face normal on A and anti-parallel face normal on B. You can then clip these faces to build a manifold. You would need to be careful with the manifold normal direction though. Using the witness features will be very tricky. E.g. you can get edge/edge witness features but these edges are actual diagonal across a face. So you need to make sure that you don't create an incomplete manifold accidentally. The code will become very ugly to handle all cases.

In practice you would also need to run another algorithm if GJK detects overlap and you have no separating axis or witness features. As Randy pointed out you can try EPA, SAT or brute force sampling.

The implementations for manifold generation that I am aware of use either incremental manifolds (e.g. find one point at a time and collect/reject in a persistent data structure) using a GJK/EPA/Brute Force method (you need the brute force fallback since EPA will fail in practice as well). Or SAT based full manifolds as I described in my two talks here.

Both will work. I go over limitations a bit in my presentation. Personally I chose the SAT based approach because it can be implemented in one straight forward code path as compared to a GJK/EPA/BF pipeline with all kind of hoops to jump through. Also EPA is a numerical nightmare and none of the publically available implementations I am aware deal with numerical problems and would be useful in real production in my opinion. People are often concerned about the SAT performance (which is still O(n^2) with my suggested optimizations). In practice I found it really doesn't matter whether you call GJK or SAT as your primary collision routine, but what matters is that you don't call them at all utilizing temporal coherence.

Edited by Dirk Gregorius

##### Share on other sites

Thanks for the explanations, Dirk and Randy!

First off - I've read horror stories of EPA in the past, which is why I was hoping I wouldn't need to spend time on it. In my case I really only need feature information in order to figure out what type of surface my actor is in contact with. I've now completely rethought my approach.

To give a little bit of perspective and describe what I ended up doing - the initial problem I was tackling was basically handling a car-like vehicle, which I was maintaining as a dynamic actor, applying impulses to steer it as needed. I only need it to report contact with walls, which basically terminate the game or throw the actor off in some direction, or the ground, which can have a number of surface types that affect gameplay. I could sample this data directly, but I was naively hoping I might be able to integrate surface queries into my physics code. I gave up on that.

Ultimately I ended up converting my dynamic player into a separately simulated kinematic actor. I'm now emulating all forces on it as a separate step and completely bypass the physics loop. Instead, I'm colliding it manually with a dynamically build poly soup, which already contains surface information.

On 11/12/2017 at 11:54 PM, Dirk Gregorius said:

... but what matters is that you don't call them at all utilizing temporal coherence.

Just to clarify - you mean to "make sure to take advantage of temporal coherence", right?

##### Share on other sites

Yeah, he means try to cache something from the last frame, that if validated on the next frame, can let you just simply not call your GJK or SAT routines.

A good example for GJK is in Box2D. Typically for GJK caching the first step is to cache the "separating axis" from the previous frame. This can be used to warm start GJK, and in practice does work quite well, reducing GJK to a very early out with a couple support calls.

The next step, like in Box2D, could be to cache an entire simplex. This can give GJK a good guess and at the very least skip the first couple iterations of building the simplex. In colliding configurations the previous simplex is probably still going to enclose the origin, or be very close.

SAT algorithms can probably use similar techniques. Back in university I spent a couple months trying out all kinds of different caching methods to avoiding calling SAT. In the end I was unhappy with all results, as I could never really avoid running clipping routines. I wouldn't really know of good solutions here.

1. 1
Rutin
69
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633430
• Total Posts
3011831
• ### Who's Online (See full list)

There are no registered users currently online

×