[comp.graphics] Answer to overlapping boxes

shirley@m.cs.uiuc.edu (10/11/89)

I received several replies to my question of how to determine if
two 'boxes' overlap.  They were all basically the same.  One should 
check each dimension in turn and return FALSE as soon is there is no
overlap.  This gives a good trivial reject.  The following pseudocode
is well suited for the C "()? ():()" construct.  

From: raymond@bosco.Berkeley.EDU
> 
> If the sides of the rectangle are all parallel to the axes
> (as you seemed to imply), then the algorithm is very simple:
> 
> Let us represent the rectangles in n-space by two opposite corners,
> 
>	 R = (a_1, a_2, ...)   (b_1, b_2, ...)
> 
> without loss of generality, a_i < b_i
> 
> Then the following algorithm determines whether two rectangles R and S
> intersect:
> 
>	 Let R = (a_1, a_2, ...)   (b_1, b_2, ...)
>	 Let S = (c_1, c_2, ...)   (d_1, d_2, ...)
> 
>	 for i = 1 to n
>		 if not intersect( (a_1, b_1), (c_1, d_1) )
>			 then return false
>	 endfor
> 
>	 return true
> 
> Where the function "intersect" is defined by
> 
>	 intersect( (a,b), (c,d) )
>		 { returns TRUE if the two intervals intersect }
> 
>	 if a < c then return b >= c
>		 else return d >= a


I wanted this code for the space subdivision tree for a ray tracer.  In
the ray tracer I need to decide membership for polygons in a "box" defined
as above.  I approximate this by using the bounding box of the polygon
because false positives are OK.  The way I originally coded it
there would be trouble if the counding box of the polygon degenerated to
2D.  This is not true of the above algorithm.

Many thanks for the people who responded, and thanks also for not telling
me what a bonehead I am.

pete shirley
shirley@cs.uiuc.edu

it coded 

shirley@m.cs.uiuc.edu (10/11/89)

Another response made me realize this can be coded a little more
concisely.  If I have two boxes b1 and b2, the function can be:

boolean intersect( b1, b2 )
{
   if ( (b1.max.x < b2.min.x) || (b1.min.x > b2.max.x) return FALSE;
   if ( (b1.max.y < b2.min.y) || (b1.min.y > b2.max.y) return FALSE;
   if ( (b1.max.z < b2.min.z) || (b1.min.z > b2.max.z) return FALSE;
   return TRUE;
}