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
-- 
Marc Schimmler

Post a reply to this message

On Mon, 17 May 1999 09:47:46 +0200, Marc Schimmler 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?

Are the boxes axis-aligned?  If so, a few coordinate comparisons should
be able to do the trick.

If not, are they at least aligned with each other?  If so, a few 
coordinate comparisons in a transformed coordinate system should do
the trick.

If they're neither, I think the plane intersections are all you have
left, as it's conceivable that two boxes could intersect yet have all
their corners on the outside of each other (though you could get away
with edge-face comparisons, which might be preferable to face-face
comparisons.) In fact, you'll still have to be careful, as it's also 
conceivable that two boxes can occupy a common volume yet not intersect 
at all.

Post a reply to this message

Ron Parker wrote:
> 
> 
> Are the boxes axis-aligned?  If so, a few coordinate comparisons should
> be able to do the trick.
> 
> If not, are they at least aligned with each other?  If so, a few
> coordinate comparisons in a transformed coordinate system should do
> the trick.
> 
> If they're neither, I think the plane intersections are all you have
> left, as it's conceivable that two boxes could intersect yet have all
> their corners on the outside of each other (though you could get away
> with edge-face comparisons, which might be preferable to face-face
> comparisons.) In fact, you'll still have to be careful, as it's also
> conceivable that two boxes can occupy a common volume yet not intersect
> at all.

The third case is true and I came to same conclusions. Good to know that
I wasn't wrong there. I guess I have to sit down on my bud and work it
out.


Thank you Ron,

Marc
-- 
Marc Schimmler

Post a reply to this message

On Mon, 17 May 1999 16:03:59 +0200, Marc Schimmler wrote:
>The third case is true and I came to same conclusions. Good to know that
>I wasn't wrong there. I guess I have to sit down on my bud and work it
>out.

Glad I'm not your bud (American slang for buddy, friend, pal, whatever...) :)

Post a reply to this message

Ron Parker wrote:
> 
> On Mon, 17 May 1999 16:03:59 +0200, Marc Schimmler wrote:
> >The third case is true and I came to same conclusions. Good to know that
> >I wasn't wrong there. I guess I have to sit down on my bud and work it
> >out.
> 
> Glad I'm not your bud (American slang for buddy, friend, pal, whatever...) :)


You should be happy not being my butt! :-)
Good one!

Bye,

Marc

P.S.: Some guy in the house linked me to a package named Icollide. I
will try it.
-- 
Marc Schimmler

Post a reply to this message

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

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

On Tue, 18 May 1999 08:55:19 +0200, Marc Schimmler
<sch### [at] icauni-stuttgartde> wrote:

>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

Stupid me! Had to think of this before I posted! Sorry.

---------
Peter Popov
ICQ: 15002700

Post a reply to this message

On Tue, 18 May 1999 08:55:19 +0200, Marc Schimmler wrote:
>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.

And the plane/edge intersections.  These will be easier to test, I think,
because the intersection is a point instead of a line.  Making sure that
point is in the bounds reduces roughly to the result Peter just gave.
Making sure the line formed by a plane/plane intersection is in bounds 
reduces to the plane/edge intersection test.  You'll also want to test 
at least one vertex from each box to see if it's inside the other box.

Post a reply to this message