clipka <ano### [at] anonymousorg> wrote:
> Am 26.01.2013 23:11, schrieb Trevor G Quayle:
> > clipka <ano### [at] anonymousorg> wrote:
> >> Am 26.01.2013 15:43, schrieb Trevor G Quayle:
> >>> clipka <ano### [at] anonymousorg> wrote:
> >>
> >>>> (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.
> >>
> >> Not necessarily: The smaller cube could be entirely contained in the
> >> larger one.
> >
> > OK, you are right about that, didn't think of that.  The way to check that is to
> > check for intersecting spheres based on the inner boundary (distance from cube
> > center to face).
>
> That's insufficient if the smaller cube is /very/ small and embedded in
> the larger cube close to one of its corners.

Stop thinking of everything!

OK one more think at this:

1) check outer boundary sphere intersection (radius = center to vertex).  If no
intersection (distance > r1 + r2), cubes don't intersect,

else

2) check inner boundary sphere intersection (radius = center to face).  If
intersection (distance < r1 + r2), cubes intersect or nest.

else

3) determine closest vertex for each cube to the center of other (don't need to
check each vertex). if either vertex is inside other cube, intersected or nested

else

4) for one cube, check each edge from closest vertex for intersection with each
face from each vertex of other cube, if intersect, cubes intersect. (don't need
to check every single one, only 3 edges from 1 and 3 faces from other)

else

5) cubes don't intersect!

Does that cover it all?  Or is there some other scenario that falls outside
these rules?

-tgq

Post a reply to this message