ISSN:
1432-0541
Keywords:
Computational geometry
;
Hidden surface removal
;
Ray shooting
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01293267