There must be a solution for this! Ever have that feeling, but can't figure it out? Well, here's one for anyone who wants to prove they're a genius.

I'll assume you know about the GJK algorithm. Essentially it determines whether the volumes of two convex 3D objects overlap, by finding out whether the "Minkowski sum" of objectA and -objectB includes the origin (0,0,0). Wonderful algorithm, very clever, and made much more practical by some other smart folks who tack on the notion of "support functions".

Well, that's great! So now, thanks to GJK, we know whether two objects overlap or not.

So, let's say you have a big honking mothership that contains a big tube or rectangular box-shape room open to outer space. You know... a "landing bay" where small spacecraft fly in and land, or take off and fly out.

So you've got this convex object (the cylinder or rectangular box), and you need to know when some other object (small spacecraft) enters the "landing bay".

Why would you need to know that? Well, for one thing, that small spacecraft just "collided" with the mothership. You see, to be a shape that works in GJK, the mothership (or each section) must be "convex" (which simply means, no "craters" or "insets"). So a solid cylinder is convex, a solid box is convex, even a disk or triangle is convex. But you can't have "holes" or "insets" like that "landing bay" and still qualify as "convex".

Well, one lucky thing is, the way GJK works (or at least GJK algorithms), is that they simply assume any "hole" or "inset" is filled in solid. So as far as a GJK test is concerned, that opening in your mothership doesn't exist... the whole end of the mothership where you put the "landing bay" is solid. Which is okay... good enough to handle most collisions of most objects with most places on your mothership.

But... you really do need to allow spacecraft to fly into your "landing bay", and you really can't afford some 10x or 20x or 100x slower routine that works on concave objects too.

No, you want to solve this problem as elegantly as GJK solved the problem for convex objects.

So you have a "really brilliant idea"! You'll just make up a simple rule and apply GJK twice! Your rule is this. If an object is in collision with the mothership, then look to see if that object is also in collision with your "landing bay". And if it is... then ignore the GJK collision with the mothership! Brilliant! You ignore the collision with the mothership AND the "landing bay" as long as the object is in collision with the cylinder or rectangular box that is your "landing bay". In other words, if an object is in collision with the "landing bay", it is not in collision with the mothership. This lets objects fly into your mothership, and oh so nicely defeats the convex limitation of GJK.

!!!! OOPS !!!!

That sounded right, and is in fact close to right... but isn't quite right. Why? Well, consider the case of a newbie pilot who flies into the "landing bay" too low. The top half of his spacecraft does collide with the "landing bay" cylinder or box, but the bottom half of his spaceship smashes into the side of the mothership. So that rule... that "in collision with the convex shape that is the "landing bay" is not sufficient.

In fact, the appropriate test is "the object needs to be completely contained by the landing bay".

Hmmmm. This is a different test. The classic "collision test" tells us whether ANY part of an object overlaps another object. What we need is a "contained test" that tells us whether ALL parts of an object overlaps (is contained by) another object.

And so there you have your "genius question".

Find a similarly elegant and efficient way to tweak the GJK algorithm to detect "fully overlapping" instead of "at least barely overlapping"... and you win your IQ 180 badge. Actually, no need to limit yourself to GJK or Minkowski land... ANY fast and efficient routine will suffice. Add 5 more points for an algorithm faster than GJK. You can still assume the objects are convex. But if your routine works on non-convex objects and still remains fast and efficient, well then! Add another 20 points!

After I thought up this basic idea... but before I realized the "oops" part, I just felt there has to be an equivalent test for "full overlap". Yet my supposed genius label fell off after a couple hours of repeatingly thinking "I found it"... but then realizing "no, that doesn't quite work" time and time again.

So, I surrender to superior intelligence (sounds like something outta StarTrek II vaguely). Show me up! And prove you're a bonafide genius in the process.

And if you do... I suspect you'll become famous in the world of 3D games, graphics and simulations, because this is a nasty problem.

-----

PS: I have an idea myself, which is a little clever, but probably too "brute force", and thus probably too slow. It involves walking from vertex to whichever adjacent vertex on each of the two objects reduces distance-squared between the vertices until you cannot progress (a bit like the final simplex in GJK), watching the dot product of the normals of the vertex-pairs along the way. But that's only the first stage... and I haven't perfected the second stage yet. I only mention this to say... I don't think this is the direction the "genius solution" will take. Somewhat clever maybe, but too brute force by the endgame. Plus, unlike my engine, not all 3D engines know what are the 4~6 neighbor vertices, in which case performance will suffer even more.

So, there is the genius challenge. Anyone up to this?

I would simply subdivide the mothership's concave shape in the union of a set of (not necessarily disjoint) convex shapes. If the small ship intersect any of them, it intersects the mothership. This is simpler to implement than trying to add additional steps to handle each hole or inset separately.

I see a problem with this idea: Let's say the landing ship is halfway in the hangar, and halfway in space.

You'll detect a partial collision with the mothership, and WON'T get full overlap with the hangar, yet you *still* don't want the landing ship to collide with the mothership.

You can't just extend the hangar zone into space because you'll still run into problems around the edges of the hangar entrance.


If you absolutely must avoid using an algorithm that handles concavity, I would split the mothership's single convex hull into multiple convex hulls that take the empty hangar space into account, then see if the landing ship is colliding with any of them.

Right, there are at least two difficult cases:

#1: object starts to enter landing bay, and therefore overlaps both landing bay and mothership, but is not fully contained in either.

#2: object is fully in landing bay, and therefore fully contained by both landing bay and mothership.

Case #2 is solved if some genius figures out an efficient algorithm for "fully contained".

Case #1 is still a problem. Seems so easy visually... just not algorithmically --- if that's a word?

-----

It is easy to say "decompose huge objects into zillions of convex objects", but not so easy in practice for a great many objects. Also, my engine is optimized for procedurally generated content, and making procedures that support making great looking objects is difficult enough, without also trying to make them aware of how to automagically decompose objects into convex objects.

Incidentally, imagine a huge egg-shape or spherical mothership. You must break that into EVERY SINGLE TRIANGLE to get "convex shapes". That's just insane --- a big mothership could have millions of triangles!

A better way is called for. We just need to figure out what it is.

Incidentally, imagine a huge egg-shape or spherical mothership. You must break that into EVERY SINGLE TRIANGLE to get "convex shapes". That's just insane --- a big mothership could have millions of triangles!

What's wrong with this? Just use a BVH of some kind (probably AABB tree) and then treat your mothership mesh as a surface. Then you can do collision detection against the surface of the mesh. Suddenly the mesh doesn't even need to be "water tight", since you only care about surfaces. If you can build your tree through insertion the tree can even represent deformable meshes. If needed adjacency information can be computed upon the surface to allow rigid shapes to roll around without catching triangle or polygon edges. If tunneling is a worry a time of impact (TOI) can be computed and tunneling can be entirely avoided. If the TOI computation is too hard to engineer or not enough time can be spent to develop it alternative forms of tunneling avoidance can be used.

Given two convex shapes, it is quite easy to compute a test like "completely contained in it".. You simply have to compute the convex hull of the union of the two shapes and verifies if the convex hull is equal to the containing shape. There may be easier methods but this is the first that comes to my mind. But I still think subdiving the mesh is the easiest solution.

This is the first time I've played with Minkowski sums, so: thanks for bringing those to my attention!

I can't answer your question, but I did notice something interesting while playing around them: given shapes A and B, B is contained entirely within A if (B-B) does *not* intersect with XOR[(A-B),(B-A)]. This seems to be true for concave shapes as well as convex ones. Seems like cheating to use XOR, though...

I also *think* that lofting (B-B) along the edges of (A-B) will result in a hollow shape (donut-like in 2D) whose interior hole contains (0,0) if B is entirely within A. I'm just graphing things on paper to check though, so I could be wrong!

In any case, checking the convex hull of the union sure seems like a better choice for convex shapes!

Given two convex shapes, it is quite easy to compute a test like "completely contained in it".. You simply have to compute the convex hull of the union of the two shapes and verifies if the convex hull is equal to the containing shape. There may be easier methods but this is the first that comes to my mind. But I still think subdiving the mesh is the easiest solution.

Could you elaborate on that a bit? What is the "union"? Something related to the minkowski sum or difference? And does any efficient way exist to perform this computation?

Incidentally, imagine a huge egg-shape or spherical mothership. You must break that into EVERY SINGLE TRIANGLE to get "convex shapes". That's just insane --- a big mothership could have millions of triangles!

What's wrong with this? Just use a BVH of some kind (probably AABB tree) and then treat your mothership mesh as a surface. Then you can do collision detection against the surface of the mesh. Suddenly the mesh doesn't even need to be "water tight", since you only care about surfaces. If you can build your tree through insertion the tree can even represent deformable meshes. If needed adjacency information can be computed upon the surface to allow rigid shapes to roll around without catching triangle or polygon edges. If tunneling is a worry a time of impact (TOI) can be computed and tunneling can be entirely avoided. If the TOI computation is too hard to engineer or not enough time can be spent to develop it alternative forms of tunneling avoidance can be used.

Actually, I already have a collision detection function that works on concave objects in a similar manner (essentially two parallel sweep and prune routines on the triangles in the two objects). It is totally general and works on absolutely everything for some of the reasons you mention. The problem is, that routine is 2x to 20x slower than GJK. As you say, one of the advantages over GJK is the fact these kinds of approaches work on overlap of object surfaces, not object volumes like GJK. After the first frame the test is faster due to temporal coherency (the triangle sorts are much quicker). But still... too slow, which is why I'm looking for alternatives.

Thanks for the suggestion though. It is a good one.