Graphics Gems III (IBM Version)

V.8

FAST n-DIMENSIONAL EXTENT OVERLAP TESTING

Len Wanger and Mike Fusco,     SimGraphics Engineering, South Pasadena, California

Publisher Summary

The detection of overlapping extents is a common technique used in operations such as clipping, hidden surface removal, and collision detection. Efficient determination of overlapping extents allows rejection of objects that do not overlap without resorting to computationally expensive intersection testing. A naive O(n²) implementation of extent testing checks each extent against all others. By sorting the extents on each dimension, the runtime characteristics can be reduced to O(n log n); however, if care is not taken, a large amount of time is spent on linear searches among the list of extents. ...