Determining the Lines Through Four Lines

Abstract

This paper describes how to compute the line or lines which intersect four given lines in three dimensions. This intersection computation arises in computer graphics (for visibility computations), computational geometry (for line traversals), and computer vision (for object recognition).

Given four distinct lines in three dimensions, there exist zero, one, two, or various infinities of lines intersecting the given lines. We use the Pliicker coordinatization of lines to cast this problem as a null-space computation in five dimensions, and show how the singular value decomposition (SVD) yields a simple, stable characterization of the incident lines, and an efficient algorithm to determine them.

Finally, we enumerate the types of input degeneracies that may arise, show how to detect each type in practice, and describe for each case the solution set of lines that arises.