RAY SHOOTING ON TRIANGLES IN 3-SPACE

We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines in R3 into points and hyperplanes in five-dimensional projective space (Plucker space). We obtain new results on the following problems: 1. Preprocess n triangles so as to answer efficiently the query: ''Given a ray, which is the first triangle hit?'' (Ray-shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles. 2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with a subquadratic overhead term. 3. Construct the arrangement of n intersecting triangles in 3-space in an output-sensitive way, with a subquadratic overhead term. 4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra. 5. Preprocess n lines (segments) so as to answer efficiently the query ''Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?'' (Isotopy problem). If the movement is possible produce an explicit representation of it.