Testing whether two cubes are touching in space

Question

Does anyone have any clean ideas on testing whether two cubes in 3D space touch? By touch I mean, touch at corners or on a face or on an edge. Say that the cubes are axis aligned and there is no nesting of the cubes. So either the cubes touch or they don't. There is no overlap of the cubes at all (except of course possibly an edge or corner point).

Everything I have thought of ends up needing a ton of cases. Also numerical stability is a factor. I don't want to just test == on all the edges/points.

I guess I could utilize some sort of epsilon instead of testing whether something == 0. The main thing however is minimizing the number of cases to test.

Answer 1

If your cubes overlap or they just touch, they have to overlap or touch in all three axis. In one axis it looks like this (for two intervals a and b):

So what you have to test is:

if ((min_a <= min_b && min_b <= max_a) || 
    (min_b <= min_a && min_a <= max_b))

First part (before ||) is for case when min_a < min_b, second for case when min_b < min_a.

For all three axis it looks like this:

if ( 
   ((min_x1 <= min_x2 && min_x2 <= max_x1) || (min_x2 <= min_x1 && min_x1 <= max_x2)) &&
   ((min_y1 <= min_y2 && min_y2 <= max_y1) || (min_y2 <= min_y1 && min_y1 <= max_y2)) &&
   ((min_z1 <= min_z2 && min_z2 <= max_z1) || (min_z2 <= min_z1 && min_z1 <= max_z2)) 
   )

Where for example min_x and max_x are minimal and maximal coordinates of cube in x axis. x1 is for first cube, x2 for second.

As I sad, this tests overlaping, but because there is "<=" and not only "<", it test also "touching".

//EDIT:

If you want to have more stable solution (there can be some floating point value errors), you should use epsilon. So it will look like: min_x1 - epsilon <= min_x2 && min_x2 <= max_x1 + epsilon

Answer 2

An alternate way to check for AABB collisions is to rule out all cases where you can't collide.

if (min_x1 > max_x2) no collision
if (max_x1 < min_x2) no collision
if (min_y1 > max_y2) no collision
if (max_y1 < min_y2) no collision
if (min_z1 > max_z2) no collision
if (max_z1 < min_z2) no collision
otherwise, collision.

Answer 3

You certainly want to minimise the number of tests being performed. You can do the test using only three comparisons.

Let (x1,y1,z1) and (x2,y2,z2) be the centres of the cubes. Let a1 and a2 be their respective extents (ie. half their edge length). The cubes touch by your definition if and only if the distances between the projections of their centres is a1+a2 in each of the three directions of the coordinate system.

/* Returns true if two axis-aligned cubes touch or overlap */
return fabs(x1-x2)-(a1+a2) <= EPSILON
    && fabs(y1-y2)-(a1+a2) <= EPSILON
    && fabs(z1-z2)-(a1+a2) <= EPSILON;

Where EPSILON is a small number suitable for your typical object sizes and distances. Note that the above meethod will also return true if the cubes overlap, but since this does not happen, it is not a problem.

If the platform you target has fast min/max selection, you can do it using only one test:

/* Returns true if two axis-aligned cubes touch or overlap */
return max3(fabs(x1-x2),fabs(y1-y2),fabs(z1-z2))-(a1+a2) <= EPSILON;

Answer 4

Various spatial tree algorithms are designed to prevent the extra checks you mention. You could easily add to said structures via a single distance (sphere) check from the cube's center to cull bad results. Or you could just sphere bound check each cube against the others (O(n^2)) to see if you need further tests. Note that test can be done without a sqrt if you compare via squared radii. The spatial trees (oct tree, quad tree, BST) take that O(N^2) term way, way down. Of course AA boxes means you only need compare 6 values for collisions /left,right, right/left, top/bottom, bottom/top, front/back, back/front. 6 'less than or equal to' compares isn't that bad!

Answer 5

Most likely you will need a spatial data representation that allows for fast dismissal of uninteresting objects. The Octtree is one of the most used structures and fits perfectly with your requirements, plus they are easy to implement. A BSP Tree might be an alternative, depending how your data is set up.

A fast and dirty solution would be to a hash-map to store all points and a reference to all cubes sharing that point. The query would be very fast but at the cost of (a lot of) memory. Although for a small number of cubes that might be applicable.

Answer 6

if your cubes are axis aligned then you may construct tree interval Trees one for each axis.

An intervall tree is a data structure that let you query for an intervall overllapping or a point hit of a set of intervall.

If you can ensure that no cube will ever have an edge less than ε then you can easely see if a cube touches other cubes by querying your trees.

To understand how this works lets scale the problem down to "1D cubes" i.e. segments

It the testing segments is AB then take the points A-ε,A+ε,B-ε,B+ε check the intervall tree for the hit. For every segment that matches there are a few of possible relation with your testing segment:

Testing Segment   A- A+ B- B+
Case              -  -  -  -  impossible : no match
Case              X  -  -  -  touch: the segments are disjoint but very near
Case              -  X  -  -  overlap
Case              X  X  -  -  overlap: segments touches for more that 2 epsilon
Case              -  -  X  -  overlap
Case              X  -  X  -  impossible: no holes in segments
Case              -  X  X  -  overlap: the segments are nearly the same
Case              X  X  X  -  overlap: the segments are nearly the same
Case              -  -  -  X  touch: disjointed segments but very near
Case              X  -  -  X  impossible: no holes in segments
Case              -  X  -  X  impossible: no holes in segments
Case              X  X  -  X  impossible: no holes in segments
Case              -  -  X  X  overlap: segments touches for more that 2 epsilon
Case              X  -  X  X  impossible: no holes in segments
Case              -  X  X  X  overlap: the segments are nearly the same
Case              X  X  X  X  overlap: the segments are nearly the same

As you can see a segment touches our testing one if A- matches but A+ does not OR B+ matches but B- does not; in any other case (excluding the impossible ones) there is an overlap.

In interval trees other data can be stored alongside the start and the end of the intervall. This possibility can be used to give names to the segments so you can wrap the query function so given a couple of points it gives you a list of (segment_name,"touch") or (segment_name,"overlap").

Now we need a way to use 1D results to get 2D results, a way that possibly scale up to 3D and over.

We can say that a rectangle touches another if there is a touch in an axis and an overlap in the other (edge touch) or a touch in both axes (corner touch).

To do this we need to store our intervals into two separate trees taking care of naming intervals correctly.

Let say that we are looking if the rectangle (Ax,Ay)(Bx,By) touches some of the stored rectangle, then we have to query the X-tree for Ax,Bx and the Y-tree for Ay,By.

Lets suppose that the result is [("alpha","touch"),("beta","touch")] by X-tree and [("alpha","overlap")] for Y-tree whe can say that our rectangle touches "alpha" ("edge" touches) but don't touches "beta" nor other rectangles.

The test can be easely managed using a dictionary that keep the rectangle name as key and stores the X,Y values for example: {"alpha":[0,1],"beta":[0,-1]} means that "alpha" touches(0) in X and overlap(1) in Y while "beta" touches(0) in X but is disjoint in Y(-1).

This reasoning can be extended further adding other dimensions: there is a touch if at least one dimension touches and there are no disjoint dimensions:

3D (0:touch, 1:overlap)
X Y Z
0 0 0 corner touch
0 0 1 edge touch (over one of the four Z edge)
0 1 0 edge touch (over one of the four Y edge)
0 1 1 surface touch (over one of the two X surfaces)
1 0 0 edge touch (over one of the four X edge)
1 0 1 surface touch (over one of the two Y surfaces)
1 1 0 surface touch (over one of the two Z surfaces)
1 1 1 eerrr no touch... the cubes are nested (remeber, at least one dimension touch)

[Appendix]

To speed up the interval query match you can test only A- and B+; when you find a match with A- then you get the upper end of the segment that matches and measure the distance with A-: if the distance is greather then 2ε this means that the overlap is too large to be considered a touch so you don't have to continue.

The same has to be done with B+ but this time you have to check the value of B+ with the lower end of the matching segments, again to see if the overlap you find with the extended segment is too large to be considered a simple touch.

A balanced interval tree takes ~log(n) iterations to check if a point hits against n intervals, this means that if you keep (by using red black trees for example) your trees balanced you can check against a huge set in reasonable time