Thanks for all your answers and algorithms and suggestions.


> I tried something like this: If one of the 8 corners of a cube is inside
> the other one than the cubes intersect:
>
> |  for corner = cubeA.corner0 … cubeA.corner7:
> |     if( corner is_inside_of cubeB ) return true;
> |
> |  for corner = cubeB.corner0 … cubeB.corner7:
> |     if( corner is_inside_of cubeA ) return true;
>
> But it is possible that 2 cubes intersects even if none of the corners
> is inside of the other cube. :-(
>
> Has anyone a better formula for me?

Only use the circumspheres for intersection testing would left over a
lot of free space around each cube that is never filled with cubes. So
it can only be an optimization for cubes that "clearly do not intersect"
(=if their circumspheres don't intersect), as step 0 before my corner
testing algorithm from above starts.

I want to avoid to check all 12 edges of cube A for intersection with
all 6 faces of cube B (not only with the planes of the faces!). But
costly pre-computions to avoid some of these checks wouldn't speed-up
the whole intersection test, I think. :-/


A completely different approach might be the 3D version of the following
calculus:

The 3D space is subdivided into 27 sub-spaces (9 in this 2D variant):

    A |  B | C
  ----+====+----
    D #  E # F
  ----+====+----
    G |  H | J


E is the interior of a cube. Now I can make simple distinction:

if the two points of an edge are in sectors A and B -> no intersection
possible; same for A and C, A and D, A and G.

Problematic are the cases A-H, A-J, A-F, B-D, B-F, B-G, B-J. :-/

Would this be an easier/simpler way?


Lars R.

Post a reply to this message