The union is simply the boolean union of the two shapes.. But you do not have to compute it at all. If your two convex shapes are polygonal meshes, then you just have to compute the convex hull of all the nodes of the two shapes. If the boundary of this convex hull contains any of the nodes of the mesh you are testing, then it is not inside the other shape. Alternatively, if all the faces of the containing shape are oriented in a uniform way (there is no "inverted normal"), you can also test if the contained shape is at the same side of all the planes defined by the faces of the containing shape.

I might just be old and tired, but I always go for the simplest solution to these sort of problems.

A beautiful, clean, efficient system is great if the advantages of the resulting solution out weigh the time taken to produce the solution.

So a solution that runs twice as fast as the simple case, but takes 2 years to write wouldn't be attractive to me.

A solution that runs twice as fast as the simple case, and takes twice as long to write.... maybe.

For me I would just get the artist's to create a collision mesh. A very low polygon version of the mother ship with the landing bay.

I would then create a set of points on the small spacecraft, typically the equivalent of left wing tip, right wing tip, nose and tail (I actually define the landing gear as well, but that's another story).

Then my collision detecting would be in three stages ...

1) centre of small craft against bounding sphere of mothership

2) centre of small craft against AABB of mother ship

3) Point detect against collision mesh.

I know this isn't as nice and clean as what you want to do, but it'll take you half a day to write and will produce reasonable results.

You could refine the point against collision mesh code a lot with a few more hours work.

Maybe it's just me being old and tired....

I might just be old and tired, but I always go for the simplest solution to these sort of problems.

A beautiful, clean, efficient system is great if the advantages of the resulting solution out weigh the time taken to produce the solution.

So a solution that runs twice as fast as the simple case, but takes 2 years to write wouldn't be attractive to me.

A solution that runs twice as fast as the simple case, and takes twice as long to write.... maybe.

For me I would just get the artist's to create a collision mesh. A very low polygon version of the mother ship with the landing bay.

I would then create a set of points on the small spacecraft, typically the equivalent of left wing tip, right wing tip, nose and tail (I actually define the landing gear as well, but that's another story).

Then my collision detecting would be in three stages ...

1) centre of small craft against bounding sphere of mothership

2) centre of small craft against AABB of mother ship

3) Point detect against collision mesh.

I know this isn't as nice and clean as what you want to do, but it'll take you half a day to write and will produce reasonable results.

You could refine the point against collision mesh code a lot with a few more hours work.

Maybe it's just me being old and tired....

Well, my experience is, during the process of brainstorming it is very wise to take a wide variety and attitudes (including, "I'm old, tired and lazy"), and see where they lead. So... can't complain about that. In fact, though I don't have the same attitude as you for reasons I'll mention later, you reminded me of an old idea from another problem.

Typically, a "landing bay" will be a big box, the entire volume of which is empty. Of course, a mothership isn't some stationary object sitting flat on the ground, so the landing bay will always be oriented at some random fractional x, y, z angles. Otherwise the landing bay would actually be an AABB itself. However, I already have functions to transform from world to [object] local coordinates, so it is trivial to transform the 8 corner points of the landing bay to local-coordinates to create an AABB that exactly matches the open volume of the landing bay.

Now, I'm not sure what I need to do with the x,y,z position part of this world-to-local transformation matrix, but... I assume I can at least apply the 3x3 part of the matrix to rotate the AABB of the smaller spacecraft into the orientation of the corresponding coordinate system (the local coordinates of the landing-bay object). So if I can also figure out how to fiddle the position.xyz of the smaller spacecraft to place it in the same relative position as the landing bay (hopefully just one or two vector subtracts), then we can first perform a quick bounding-sphere test on the smaller spacecraft, which if does not pass (says "overlapping"), we can then compare the AABBs of the "landing bay" and spacecraft for overlap, which if does not pass (says "overlapping"), would might then lead to a full GJK test against whichever of the 5 sides of the landing bay box the AABB tests indicates are "overlapping".

Actually, it is probably much smarter to transform the AABB instead of the hundreds or thousands of vertices in the small spacecraft, and the resulting AABB on the small spacecraft will almost always tightly and efficiently enclose that spacecraft.

By simply skipping AABB or GJK tests against the 6th face of the landing bay, we avoid any problems of the spacecraft not being fully inside the landing bay (on that side). And by testing against the sides of the landing bay box one at a time, we don't have to detect that elusive "fully contained" situation. However, that is at the price of needing to run the GJK up to 5 times instead of only once!

Of course, this doesn't work so well when the shape of the landing bay isn't some convenient shape like a rectangular box.

As an aside, the technique you described is exactly what I did when I designed a PS2 game engine under contract for a video game company in the 1990s.

Now I'm creating a much more advanced game/simulation engine, as general purpose as possible (for many kinds of simulations and games). So the notion of a limited number of collision points just doesn't meet the requirements of this new engine. Also, one focus of this engine is "procedurally generated content", most definitely including 3D objects. In fact, that's how the engine creates objects now, though it can load existing artist-drawn objects too. The point being, the engine cannot depend on "artist identified anything", because brand new, never-before-seen objects will be created on-the-fly by the engine, depending on what is happening in the game (plus profiles of the players generated by watching them play, plus many other factors).

Which means, by the time all this works, we'll be "old and tired too". But hopefully not until "after"... hahaha.

But this also means we are spending a lot of time and effort to make highly-efficient, highly-general (and/or specialized, and/or self-adaptive) mechanisms for many aspects of the engine.

Thanks for your suggestion... it got me thinking in another direction.

Can you split the collision test in two? Check for collision against the mothership, but treat the docking bay as an exception. The solution would decompose to something like this:

If the player's spacecraft is in collision with any part of the mothership (don't include the convex docking bay in the collision model at this point), then test (only) the portion of the player's spacecraft which is inside the volume of the mother-ship's collision model against the docking bay's collision model -- if that portion of the player's ship (and eventually the whole ship) is entirely inside the docking bay's collision model, then there is no collision -- otherwise the player's spacecraft is colliding with the mother ship.

[Edit] I see now that you went down something like this line of reasoning already and rejected it. Reading the rest of your asks more carefully then, maybe I'm missing something (and maybe I'm not real versed in the gotcha's of 3D collisions or GJK), but why is it difficult to determine if one convex shape is entirely within another or not?

I've done a lot of work on procedural generation of 3D objects, (at one company I was brought in to attempt procedural generation of complete games, start the app, tell it a few game style parameters and a random number seed, hit go. Leave for two days, test game. Horrible.).

In each case when I had some generated 3D content, the code had rules which allowed me to make sure key elements in the structure could be identified by code after generation.

So for characters I could always work out the skeleton and generate a set of animations.

For spacecraft I could always find ground contact points and weapon mounts.

Just because it's procedurally generated doesn't mean it's totally random. You can still have key structures you need identified and available to the engine.

If you can't, I think you need to re-examine the generation code and make some design changes before you find your self in a situation that requires a change to the code, and you are two days away from alpha.....

Hate it when that happens.

You can always use some voxel approximation techniques to generate a low poly collision mesh.

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.

You can still use GJK on a triangle and on a convex shape. You can also use GJK on two triangles. So you can still compute a TOI like I mentioned in my first reply, and you can use GJK to compute the TOI. You can even do some optimizations in the "root finder" so that you can call GJK even less. On top of this you can also form a GJK cache to warm start GJK during TOI iterations. It can all be pretty efficient. Maybe you could read into Erin Catto's recent information from GDC 2014 on the topic.

I'd really assert that this would be a good, efficient solution. Of course it's a lot of work to compute TOI and build AABB trees, so alternatives might be preferred.

The gist of my idea is like this (pardon the crudity of the hastily constructed image):

The red area is the mothership, the purple is the ship coming in for a landing. The green area represents the landing bay. The blue area represents the actual collision box for the landing bay, shrunk by an amount proportional to the size of the landing ship's collision volume. The blue area should be shrunk enough that if the ship is in collision with it at all, then it can not be in collision with the walls of the bay because they are too far away. Navigation mesh construction algorithms use a similar technique: they'll render all walkable polygons then "erode" the walkable areas based on the agent radius so that any agent of the given radius, if it is located on a resulting polygon, can not by definition be colliding with the walls. In this case, if the ship is colliding with the red zone but not the blue zone, then it's crashed into the mothership because it lies outside the "walkable" region.

Sounds like the containment idea went bust, but answering this question nevertheless in case it might be useful.

Testing whether a convex polyhedron A is fully contained withing another convex polyhedron B can be done in V*F steps, where V is the number of vertices in polyhedron A, and F is the number of faces in B. The algorithm is very simple:

for(f in F):

for(v in V):

if v is in positive halfspace of f:

return False // The vertex v of A is not contained in B, so the whole object is not contained.

return True // All vertices of A are in the negative halfspace of all the faces of B, so A is contained fully in B.

There is a faster way to do this in practice, by implementing a hill climbing search of the vertex neighbor graph of A. Instead of looping through each vertex v in V linearly, start from an arbitrary vertex, and climb up vertex neighbors towards the direction of the plane normal of f, until the you reach a vertex v that is in positive halfspace, or determine that all vertices are in negative halfspace. This is much faster, but still theoretically O(V*F). In practice it's best to sort the faces of B in such order that the six most closest cardinal axes are first in the list. Then iterating over the six first faces is effectively a broadphase "convex polyhedron contained in AABB" test which rejects invalid cases very quickly. Also with SSE, one can process four vertices against one plane in one go (or one vertex against four planes, whichever suits better).

Third, there is a way to preprocess a convex polyhedron to use what is called a Dobkin-Kirkpatrick hierarchy. After that, the convex polyhedron is contained in another convex polyhedron can be done in log(V)*F steps. This optimization comes from the faster way to locate supporting vertices that Dobkin-Kirkpatrick hierarchy guarantees.

Sorry, I was away for a couple days.

I think both of the last two posts have merit, at different phases of the process. The algorithm that is most efficient at a rough approximation stage will probably not be best at the precision stage. Which is why we have SAP (sweep and prune) for broad phase and GJK for narrow-phase in the first place. And at this point, frankly, we have about 5 phases (or sub-phases), from "swept bounding sphere SAP", to "compute earliest-possible TOI based on bounding spheres (or possibly realize they do not collide)", to "compute earliest-possible TOI based upon AABBs of rotating objects", to "enhanced GJK that reports distance and a separating axis and perpendicular plane" (which again lets us compute earliest-possible TOI based upon knowing vertex at maximum distance from center-of-mass and rotation axis ala erin catto), and continued "sorta" conservative advancement based upon our enhanced GJK routine. BTW, though they probably don't arise very often in most games, we've identified a whole slew of cases that completely hose conventional conservative advancement techniques, so we found ourselves needing to be a little more "clever" and practical than their conservative advancement techniques. Or so we hope.

All that's great (if not a bit exhausting to create) for conventional convex objects. But when it comes to this fairly common case of intentionally flying objects into voids in other objects, some new problems pop up, which we'd like to solve efficiently if not simply.

I think the approach mentioned by Jtippetts looks good at broad phase or perhaps one small notch down from there. Actually, I think two variants of that probably work fine - the first based upon the bounding-sphere of the landing spacecraft (which only requires transformation of one point to world coordinates (plus the fixed radius)), and another [perhaps] based upon the AABB of the landing spacecraft versus the real (arbitrarily rotated) planes of the 5 walls of the landing bay.

I'll have to think more about the techniques proposed by clb. First I better go read about Dobkin-Kirkpatrick to gain some background. As for that hill-climbing approach, that sounds quite a bit like that approach I mentioned in my original post. Fortunately the fundamental 3D shapes that everything is created from in my engine contains "n sides" and "m levels", and the indices of those vertices are retained in arrays in objects for later applications like these. Which means, walking the vertices in objects is very efficient, and can be done intelligently for most purposes.

So, I'll fiddle.