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

Post a reply to this message