• Create Account

## GJK Simplex Caching and Circles

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

21 replies to this topic

### #1RastaRunna  Members

159
Like
0Likes
Like

Posted 22 August 2013 - 11:35 AM

Hi, I've just finished implementing GJK for collision detection in my 2D physics engine. However, I'm trying to modify my implementation so that it will work with circles as well. Normally, this would be pretty straight forward since a support function for a circle is really simple (circle.pos + |dir|*radius). However, I'm also warmstarting my GJK implementation using the cached support vertices from the previous frame. Since circles obviously don't have vertices (to cache say the index), and the actual support point will change between frames it suddenly doesn't seem so clear. Does anyone have a good suggestion on how to go about caching a simplex that also involves a circle?

Thanks!

### #2CulDeChu  Members

2856
Like
1Likes
Like

Posted 22 August 2013 - 04:06 PM

Ok let me see if I can explain this coherently, as I'm messaging from my phone right now.

My physics engine doesn't do any sort of caching of collision information because of the memory hell that would ensue. My engine uses only quadtrees because, for the purposes of my games, I don't usually need anything else. I wouldn't discard caching as an option though without testing.

But as for your question, you want to store the simplex of *each collision detected by the broadphase*, because each manifold might have multiple GJK tests a frame. The inherent problem with trying to reduce redundancy, however, is detecting the redundancy that you're trying to minimize. The question is how would you use the simplex information that you're storing if you don't know if it's the same one you would generate on the next frame?

What I would do is store the previous closest point generated by GJK, and use that as the starting point for the next frame's GJK test, which would solve your circle problems. The reason I would advise against storing a full simplex is that, in addition to the redundancy check, the simplex would only be more helpful is when two shapes are actually colliding, which is an extremely small percentage of objects usually tested in games. It'd be more worth your while to speed up the part of your code that throws out false collisions than the part that detects the true ones. That's just my opinion though.

Hope this helped!
~CulDeVu

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #3RastaRunna  Members

159
Like
1Likes
Like

Posted 23 August 2013 - 06:15 AM

Thanks CullDeVu for the quick response.

I'm not sure I follow you on the redundancy check? When I start up GJK, my first step is to find the closest point to the current simplex whether it was cached or from a previous iteration; so I'm not sure I see the overhead there.

I agree with you that there are likely more non-collisions than there are collisions which warrants focusing optimizations towards the majority. However, caching the support vertices from the previous frame not only helps speed up collision cases but non collisions as well under the assumption that relative orientation and positions between a pair of objects tend not to change drastically between single frames regardless of collision status. Additionally, GJK doesn't run until after my broadphase completes which would reduce the number of cached simplices quite a bit.

It seems I've seen some implementations where they've found some way of making circles appear to have vertices (where say v[0] somehow corresponds to the support vertex). But I think you're right with only caching the previous the point for circles. I'll look into that more.

### #4RastaRunna  Members

159
Like
0Likes
Like

Posted 23 August 2013 - 07:50 AM

I should also clarify that when I'm caching the support vertices, it is the index of the vertices that I'm caching, not the vertex coordinates. This allows me to quickly get a fresh copy of the vertex coordinates for the current frame without the need for any checks. I think it's this aspect of my implementation -- coupling with vertices and their index -- that is making it difficult to add circles; I won't say infeasible yet. Could also be a case of premature optimization on my part. Should have perhaps gotten it working with non-vertex based shapes and then figured out the best caching structures.

### #5CulDeChu  Members

2856
Like
1Likes
Like

Posted 23 August 2013 - 09:41 AM

Ooooh Ok I see what the problem you were having is.

What I saying about redundancy checks is that, given a previous simplex, how would you know that it's the same one that you would generate on this frame? For slow moving and stationary objects, it most likely will be, but it won't always. Because you can't be sure if the simplex will be generated in the same way as last time, you can't discount certain sides of the simplex as you normally would. It was just my thought that storing the previous closest point might be your best bet, at the very least because it's a good starting point for GJK. Because remember, you can start from anywhere on the shape, not just a vertex.

I guess if you're not planning on supporting curves or any sort of user-defined paths, then you can go ahead and store vertices for simplexes. But for any sort of curves and paths, you can't.

How are you dealing with simplexes in your code? Are you passing indecies or points? You should base the cached data around what's easiest for you algorithm to use.

~CulDeVu

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #6RastaRunna  Members

159
Like
0Likes
Like

Posted 23 August 2013 - 02:26 PM

I see what you mean by redundancy checks. My implementation doesn't actually have them because the first thing it does (step 1) is get the closest point, P, to the origin on the current frame's simplex (the current frame's simplex is computed by taking the indices of the cached support vertices, transforming them into global coordinates, and of course subtracting). -P is my new search direction, if the candidate Vertex in direction -P is one of my existing simplex vertices, I can exit early knowing the simplex hasn't changed (which I guess is a redundancy check), otherwise I add the vertex to the simplex, update my closest distance and proceed as normal with a second iteration of GJK (back to step 1).

Code-wise I'm passing indices. Here is an abbreviated version of my simplex struct (it currently has more parameters but just because I'm still cleanup up):

// structure for caching simplex data between frames
struct Simplex
{
Vector2D P;           // closest point in Minkowski CH of (A - B)
int supportA[3];      // support vertices from A which make up the simplex
int supportB[3];      // support vertices from B which make up the simplex
int dim;              // simplex dimensions (e.g. 2-simplex, dim == 2, a triangle)
int initialized;      // is simplex initialized?
};


Edited by RastaRunna, 23 August 2013 - 02:32 PM.

### #7RastaRunna  Members

159
Like
1Likes
Like

Posted 23 August 2013 - 02:30 PM

I guess if you're not planning on supporting curves or any sort of user-defined paths, then you can go ahead and store vertices for simplexes. But for any sort of curves and paths, you can't.

I think this really is the heart of the question. Can you? I suppose not, at least not with-out special casing GJK, or representing them as a high-res polygon. Which in my mind kind of eliminates the beauty of GJK to begin with right, as long as the shape has a support function, you can plug it in GJK.

### #8CulDeChu  Members

2856
Like
0Likes
Like

Posted 23 August 2013 - 03:31 PM

I guess if you're not planning on supporting curves or any sort of user-defined paths, then you can go ahead and store vertices for simplexes. But for any sort of curves and paths, you can't.

I think this really is the heart of the question. Can you? I suppose not, at least not with-out special casing GJK, or representing them as a high-res polygon. Which in my mind kind of eliminates the beauty of GJK to begin with right, as long as the shape has a support function, you can plug it in GJK.

The awesome part of the GJK is that it's independent of shape. The inner theory of the algorithm is rooted in mathematics of convex manifolds and is completely free of any other context, like corners and curves. While using indices to refer to simplex vertices may reduce memory, using actual points separates the algorithm from context.

I personally think it's easier to do it that way anyways

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #9RastaRunna  Members

159
Like
0Likes
Like

Posted 23 August 2013 - 06:34 PM

So let me ask you this then, since it somewhat relates. For your vertex-based shapes do you pre-transform each shape vertex to global coordinates prior to running GJK (say at the beginning of each frame / end of previous frame) or only as needed (such as directly within the support function)?

### #10CulDeChu  Members

2856
Like
0Likes
Like

Posted 23 August 2013 - 08:36 PM

So let me ask you this then, since it somewhat relates. For your vertex-based shapes do you pre-transform each shape vertex to global coordinates prior to running GJK (say at the beginning of each frame / end of previous frame) or only as needed (such as directly within the support function)?

Actually, in my engine I've decoupled shape information from position, so I'm forced to take it into account during the algorithm. If this wasn't the case, though, I'd have the support function take care of it. It just helps to focus the algorithm on operating directly on the minkowski difference as much as possible

P.S. I find it funny how this thread has been like a public PM between us two
~CulDeVu

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #11RastaRunna  Members

159
Like
0Likes
Like

Posted 23 August 2013 - 10:03 PM

Okay, I'm computing them that way as well; it seems more scalable since the number of transformations for a given candidate pair within GJK seems fairly constant (assuming the algorithm terminates within a known/maximum number of iterations), whereas the total number of vertices between two shapes can be arbitrarily large.

Going further off topic, you mentioned earlier that you use Quadtrees in your engine. How do you like it? I'm still debating what I will use for my broad phase. I've mostly used spatial grids and some custom spin off of sort and sweep in the past. However this time around I'm trying to go for something more flexible / able to handle arbitrary sized regions. It seems some sort of tree implementation may be the way to go, though updating the tree regularly seems like it would be a pain. I'd be interested to hear your opinions.

P.S. I find it funny how this thread has been like a public PM between us two

Haha. It's nice discussing this with someone who has already faced many of these issues.

### #12CulDeChu  Members

2856
Like
0Likes
Like

Posted 24 August 2013 - 12:02 AM

Okay, I'm computing them that way as well; it seems more scalable since the number of transformations for a given candidate pair within GJK seems fairly constant (assuming the algorithm terminates within a known/maximum number of iterations), whereas the total number of vertices between two shapes can be arbitrarily large.

Does it terminate in a known number of iterations? I've never really checked because the algorithm seems to me to be highly recursive and that's how I coded it, probably at the expense of performance.

You've got me thinking about caching collision information now. I've always just used a simple distamce-between-centers ray as a starting point for my narrow phase, and it's usually enough to reduce most my GJK tests to finish at the first iteration (the 0-simplex). I might test it out though sometime.

Going further off topic, you mentioned earlier that you use Quadtrees in your engine. How do you like it? I'm still debating what I will use for my broad phase. I've mostly used spatial grids and some custom spin off of sort and sweep in the past. However this time around I'm trying to go for something more flexible / able to handle arbitrary sized regions. It seems some sort of tree implementation may be the way to go, though updating the tree regularly seems like it would be a pain. I'd be interested to hear your opinions.

There's actually a discussion going on on gamedev right now. Here's the linky: http://www.gamedev.net/topic/646919-collisions-n2-checks/

A lot of people swear by sweep and prune, but I found that being able to sleep large amounts of objects is made simple and fast using quadtrees. I just use a simple linear quadtree using indices to and a pool for storing and retrieving cells. It works pretty well, and I have plans to implement a "find objects close to another" functionality.

Updating the tree is usually rather trivial. It's an O(n) operation, but it's usually a very simple calculation that doesn't require ridiculous precision. I'm not going to have 10,000 dynamic objects on screen and active at a time, so it works well enough for me

P.S. I find it funny how this thread has been like a public PM between us two

Haha. It's nice discussing this with someone who has already faced many of these issues.

No problemo. It took me many an hour to build my own physics system, and any more pacing over the design problems. I hope your physics engine is as nice of an experience as mine was

~CulDeVu

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #13RastaRunna  Members

159
Like
0Likes
Like

Posted 24 August 2013 - 10:31 AM

Just had a thought on how to keep the index-cached simplex implementation with curved / non-vertex based shapes. The way my implementation of GJK is set up, the support functions return a single value representing the support point (e.g. the index of the point). There is no reason this can't also be a floating point / scalar. Since shapes in GJK are convex I can simply return the angle of the point (for convex shapes there is only ever one point along a given angle). Since each shape implements its own "get vertex" and "get support" functions, it can easily manage whether it is expecting angle or index. Obviously the disadvantage of this is the overhead in using trig functions. But it seems there are ways to get around that as well (such as via look up tables, etc..).

This would however make circle-circle queries more inefficient than they otherwise would be. But perhaps the cost would be worth it for circle-OBB or circle-polygon queries?

Edited by RastaRunna, 24 August 2013 - 10:37 AM.

### #14RastaRunna  Members

159
Like
0Likes
Like

Posted 24 August 2013 - 10:49 AM

Although, comparing the two implementations:

// Vector-based Support function for a circle
void Support(const Vector2D & dir, Vector2D & out)
{
float mag = radius / sqrt(dir.x * dir.x + dir.y * dir.y);
out.x = pos.x + dir.x * mag;
out.y = pos.y + dir.y * mag;
}


﻿

// Radial-based Support function for circle
float Support(const Vector2D & dir)
{
return atan2(dir.y, dir.x);
}


The first has four multiplies, a divide, and a square root. The second has a trig function. What is more expensive? I suppose the real expense comes into getting the vertices. For the first implementation, there is no need to get a vertex because we already have it from the support function. For the second:

// Get point along direction (in radians)
void GetWorldVertex(float angle, Vector2D & point)
{
point.x = pos.x + radius * sin(angle);
point.y = pos.y + radius * cos(angle);
}


That's two trigs and two multiplies. So net across both methods we have:

vector-based: 4 multiplies, 1 divide, 1 square root

Perhaps a toss-up? Should probably do some benchmarking.

Edited by RastaRunna, 24 August 2013 - 11:07 AM.

### #15CulDeChu  Members

2856
Like
0Likes
Like

Posted 24 August 2013 - 02:07 PM

Perhaps a toss-up?

To save you from overthinking the problem, most people just go with the vector approach, just because it's easier. In particular, it will come in handy if you move away from discrete collision detection and into more continuous methods. Don't get me wrong; it's not an incorrect way to do things. It'll just make your codebase harder to maintain and keep up with if hacks are built in to the design.

I find it interesting how you coded yourself into a rut like that. Most people usually start with circles, and then squares. If you're comfortable doing it that way, go ahead. Just keep in mind the most elegant solutions are often the simplest

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

### #16RastaRunna  Members

159
Like
0Likes
Like

Posted 24 August 2013 - 03:20 PM

it's not an incorrect way to do things. It'll just make your codebase harder to maintain and keep up with if hacks are built in to the design.

True. It seems though that it does play nicely into abstraction. Let each shape type determine it's own support / vertex query mechanism. The algorithm itself is none the wiser. The support "key" could even be wrapped in something more nicely so it doesn't feel like I'm trying to stuff indices and angles into the same result.

it will come in handy if you move away from discrete collision detection and into more continuous methods.

That's a justifiable reason to change.

### #17Dirk Gregorius  Members

2431
Like
0Likes
Like

Posted 24 August 2013 - 09:08 PM

I recommend not using GJK for quadric shapes with floating point position since it doesn't work in practice from my experience. Anyway for spheres and capsules you can use a point and segment and add the radius later. Then the simplex caching also works again.

### #18RastaRunna  Members

159
Like
0Likes
Like

Posted 24 August 2013 - 10:26 PM

I recommend not using GJK for quadric shapes with floating point position since it doesn't work in practice from my experience

Is that because of numerical robustness? I have been starting to think I'll only use GJK for polygon-polygon tests and then special case the rest as it seems it will likely be more efficient in some cases (e.g circle vs circle in gjk seems overkill). But if there's a robustness issue as well that's good to know.

### #19Dirk Gregorius  Members

2431
Like
1Likes
Like

Posted 25 August 2013 - 11:00 PM

Yes, GJK has severe numerical issues in 32 bit floating point math. I would not use it for anything else but polyhedra. Both Christers and Ginos books explain the details. For sphere and capsule I use the center point and segment while adding the radius afterwards.

### #20RastaRunna  Members

159
Like
0Likes
Like

Posted 26 August 2013 - 10:44 AM

For sphere and capsule I use the center point and segment while adding the radius afterwards.

I'm not sure I understand what this means. For sphere, is this just a point-polygon distance test verifying that distance is greater than radius? Or do you mean that you use GJK to get closest point between point and polyhedral and then do a radius check?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.