Peter Popov wrote:
> 
> On Mon, 17 May 1999 09:47:46 +0200, Marc Schimmler
> <sch### [at] icauni-stuttgartde> wrote:
> 
> >For my next IRTC entry I need an algorithm that will allow me to check
> >if two boxes occupy a common volume or not. The methods I can think of
> >work only with a huge amount of plane intersections. Is there a better
> >(faster) way?
> >
> >
> >Thanks in advance,
> >
> >Marc
> 
> You define a box as follows:
> 
> box { corner1, corner2 [transformations] }
> 
> It's dimensions are:
> 
> X : corner2.x - corner1.x etc.
> 
> If you define an orthogonal vector base i, j, k attached to corner1
> then the coordinates of corner2 will be <X*i, Y*j, Z*k> . At first i
> will equal <1,0,0>, j will equal <0,1,0> and k -- <0,0,1> . If the box
> undergoes some transformations, apply the same transforms to the i, j
> and k vectors using the vector functions available in POV and the
> vectorial equations will still be true.
> 
> To check if a point A is inside a box defined by its corner1 , its
> vectors i, j, k and dimensions X, Y, Z , one just has to check if the
> following system of inequalities is true:
> 
> | corner1.i < A.i < corner2.i
> | corner1.j < A.j < corner2.j
> | corner1.k < A.k < corner2.k
> 
> where corner1.i, A.k etc. are the projections of these vectors onto i,
> j, and k . I can't tell you from the top of my head how this is done
> algebraically, but I'm sure someone else can (Mr. VanSickle?).
> 
> So all you have to do is check all vertices of a box against the
> inside of another box and voila!
> 
> I think this will be faster than solving plane intersection equations.
> 
> ---------
> Peter Popov
> ICQ: 15002700

Thank you Peter!

The problem with this method is as Ron pointed out that it is possible
that not one vertice of both boxes lie in the volume of the other and
they still share some common space. This leaves only the plane/plane
intersections.

All the best,

Marc
-- 
Marc Schimmler

Post a reply to this message