Browse Prior Art Database

Original Publication Date: 1994-Feb-28
Included in the Prior Art Database: 2004-Apr-06

Publishing Venue

Xerox Disclosure Journal


In computer graphics, operations on a scene are often necessary when two objects in the scene intersect or overlap. To image the scene one must first determine which objects within it overlap so that they may be processed. The ease of determining if objects overlap depends on the shape of the objects, but can in general be quite expensive. For this reason one often performs a simple bounding-box test to rule out many of the cases before invoking the expensive test. Referring to the figure, which represents an image display 12, one generally forms rectangular box 20 aligned with the coordinate axes which enclose the object, 18. Two objects cannot overlap if their bounding boxes do not overlap. The test for overlapping boxes is a simple one; if the minimum of one box is greater than the maximum of the other box for either x or y direction, then they do not overlap. However, for some objects the bounding box can be much larger than the object and, therefore, will not provide as much assistance as desired in eliminating overlaps. The worst case object is a line segment slanted at 45 degrees with respect to the axes.