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;
}