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?
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
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.
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.
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.
Hope I made sense
~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
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?
};
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.
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 :P
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
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)?
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
