Publication

A projectively invariant intersection test for polyhedra

Journal Article (2002)

Journal

The Visual Computer

Pages

405-414

Volume

18

Number

7

Doc link

http://dx.doi.org/10.1007/s003710100158

File

Download the digital copy of the doc pdf document

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.

Categories

robots.

Author keywords

intersection detection, projective invariance, degenerate configurations, 4×4 determinant method

Scientific reference

F. Thomas and C. Torras. A projectively invariant intersection test for polyhedra. The Visual Computer, 18(7): 405-414, 2002.