clipka <ano### [at] anonymousorg> wrote:
> Am 25.01.2013 14:52, schrieb Lars R.:
> > I wrote a C++ program that generates the scene you see in the attached
> > image. (40k non-intersecting spheres)
> >
> > Now I'd like to change it to use many,many small cubes (randomly
> > rotated, of course), so I need an intersection formula for cubes.
> >
> > 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?
>
> Not a formula, but an algorithm:
>
> (0) [optional, just for speed] If the cubes' bounding boxes don't
> intersect, the cubes don't intersect.
>
> (1) If any corner of the smaller cube is inside the larger cube, they
> intersect. (No need to test the other way round.)
>
> (2) If any edge of the smaller cube intersects any surface of the larger
> cube, they intersect. (Again no need to test the other way round.)
>
> (3) In any other case, they don't intersect.
>
>
> Note that this only works for cubes, not for generic boxes.

#2 is the key.  if #1 is true then #2 is true as well.

Based on this, the long way is to:
- check all 12 edges of one cube, extend to lines (determine 3d line equation)
- check for the intersection point with the plane associated with each of the 6
faces of the other cube (determine 3d plane equation)
- if intersection point lies on edge segment of line AND with the face boundary
of the plane, then the cubes intersect
- you only have to do this one way (not check edges of one against faces of
other then vice versa)

This adds quite a bit of computation so you can try to find simplifiers:
- as clipka mentions, find length from center of cube to a corner and treat as
spheres, if spheres don't intersect, cubes don't
- find a way to determine which edges and faces are on facing sides and only
check those ones
- checking for corner intersection may help if it is simpler

-tgq

Post a reply to this message