EFFICIENT RAY SHOOTING AND HIDDEN SURFACE REMOVAL

In this paper we study the ray-shooting problem for three special clas ses of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to the z-axis and extend downward to minus infinity), and fat horizontal tri angles (triangles parallel to the xy-plane whose angles are greater th an some given constant). For all three problems structures are present ed using O(n2+epsilon) preprocessing, for any fixed epsilon > 0, with O(log n) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that uses O(n4+epsilon) preprocessing and has a query time of O(log n). We use t he ray-shooting structure for curtains to obtain an algorithm for comp uting the view of a set of nonintersecting prolyhedra. For any epsilon > 0, we can obtain an algorithm with running time O(n1+epsilon square -root k), where n is the total number of vertices of the polyhedra and k is the size of the output. This is the first output-sensitive algor ithm for this problem that does not need a depth order on the faces of the polyhedra.