ISSN:
1432-0541
Keywords:
Computational geometry
;
Ray shooting
;
Multilevel data structures
;
Hidden surface removal
;
Output-sensitive
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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 thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01377182
Permalink
