Efficient ray shooting and hidden surface removal (Q1330784)

This paper deals with the computational ray-shooting problem for polyhedral objects in \(R^ 3\). With preprocessing, efficient (i.e. logarithmic) query time algorithms are shown for axis-parallel polyhedra, curtains (hanging vertically down from a segment), horizontal triangles whose angles cannot be too small, as well as general triangles in \(R^ 3\). As a novel feature, they do not assume a depth order between the objects (as in the painter's algorithm).