GJK variant for some concave situations ???

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Posts: 12
Joined: Tue Aug 09, 2011 1:08 am

GJK variant for some concave situations ???

Post by bootstrap »

I understand the basic nature of GJK, and managed to implement GJK for convex narrow-phase in my engine, but I'm not nearly good enough at fancy math to tweak or extend the algorithm. But I see how maybe GJK could be tweaked or extended to support certain kinds of concave collision scenarios, so I want to mention the general concept here in case someone can say whether the desired tweak exists, might exist, or definitely cannot exist.

The idea is very simple.

GJK tells us whether object A is entirely outside object B or not. If so, then object A and object B are not in collision, otherwise they are in collision.

Now consider the following collision detection scenario, which on the face appears to be a classic situtation that GJK cannot handle because one object is [massively] concave.

The scenario is simply... toss a coin [convex object] into a cup [concave object].

For these situations, typically I see the advice is to break the [massively concave] cup into a bunch of vertical bars, each of which is convex, then test against those strips. Of course that works, and often coarse phase collision tests are sufficient to rule out collision between the coin and each bar, one by one.

However, note the following:

- The coin is convex.
- The empty volume inside the cup is convex.

Now we have two convex objects... so can we somehow apply GJK to say whether the convex coin is inside the convex open volume of the cup?

The problem is this.

GJK answers this question
- Does ANY part of the convex coin overlap the empty volume of the cup?

But the question we need to answer is:
- Does ALL of the coin overlap the empty volume of the cup ("yes" means "no collision")?

These are very similar questions, but they are not identical. The classic GJK tells us whether some part of the coin is inside the cup, but not whether the entire coin is inside the cup.

My question is this. Can anyone see a way to perform subtraction (or other math operation) somewhat differently and end up with a variant that tests what we want to test? This is such an analogous situation, it just feels like there must be some similar operation that could work just like GJK, and put the origin within the composite object when ALL of object A is within object B, rather than ANY of object A is within object B.

Or am I just a wishful thinker who wants math to do what math cannot be made to do?

It would be wonderful if this could be made to work, because I notice that a very common category of collision scenarios could be addressed by this [so far fictional] tweak of the GJK idea.

While I also implemented a completely general collision detection routine that can test for collision between arbitrarily irregular "concave" objects, it typically takes 2 to 20 times as long to execute as GJK. So a GJK tweak for one convex and one conave object would be very worthwhile.
Post Reply