Graphics Gems III (IBM Version)

V.7

TRIANGLE-CUBE INTERSECTION

Douglas Voorhies,     Silicon Graphics, Inc., Mountain View, California

Publisher Summary

3-D triangles must occasionally be tested for intersection with axis-aligned cubes, most commonly when the cubes subdivide space in some classification scheme such as octrees. The conventional approach of successive polygon clipping by six cube–face half-spaces is computationally expensive because it determines the actual polygonal intersection. That is not usually required when triangles are only being organized into cubic regions. In such cases, all that is needed is a yes-or-no detection of whether they touch. This chapter describes an algorithm that exploits simple tests to give quick answers most of the time and to ...