Efficient ray shooting and hidden surface removal
Mark de Berg, Dan Halperin, M.H. Overmars, Jack Scott Snoeyink, Marc J. van Kreveld · 1991
In this paper we study the ray shooting problem for three special classes 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 triangles (triangles parallel to the y-plane whose angles are greater than some fixed constant). For all three problems structures are presented using O(n 2+) preprocessing, for any fixed e > 0, with O(log n) query time. We also study the general ray shooting problem in an arbitrary set of (possibly intersecting) triangles. Here we present a structure that uses O(n 4+e) preprocessing and has a query time of O(log n). As an