AN IMPROVED TECHNIQUE FOR OUTPUT-SENSITIVE HIDDEN SURFACE REMOVAL

Authors
OVERMARS MH SHARIR M
Citation
Mh. Overmars et M. Sharir, AN IMPROVED TECHNIQUE FOR OUTPUT-SENSITIVE HIDDEN SURFACE REMOVAL, Algorithmica, 11(5), 1994, pp. 469-484
Citations number
24
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
11
Issue
5
Year of publication
1994
Pages
469 - 484
Database
ISI
SICI code
0178-4617(1994)11:5<469:AITFOH>2.0.ZU;2-Y
Abstract
We derive a new output-sensitive algorithm for hidden surface removal in a collection of n triangles, viewed from a point z such that they c an be ordered in an acyclic fashion according to their nearness to z. If k is the combinatorial complexity of the output visibility map, the n we obtain a sophisticated randomized algorithm that runs in (randomi zed) time O(n4/3 log2.89 n + k3/5n4/5+delta) for any delta > 0. The me thod is based on a new technique for tracing the visible contours usin g ray shooting.