A projectively invariant intersection test for polyhedra

Abstract

Although intersection relations are projectively invariant, most existing intersection detection tests for arbitrary polyhedra can give different results before and after a nonsingular arbitrary projective transformation of the polyhedra under test. This paper presents a projectively invariant intersection test for general polyhedra whose only numerical part is the computation of 4×4 determinants of homogeneous vertex coordinates. Degeneracies are resolved using a technique of symbolic infinitesimals which also reduces to the computation of 4×4 determinants. This greatly simplifies the implementation of the test in hardware. Moreover, its projective invariance permits applying it at any point in the graphics pipeline. Since no auxiliary geometric entities need to be computed, the presented test can be concisely expressed as a Boolean formula, instead of a procedure.