Hidden-surface removal in polyhedral cross-sections |
| |
Authors: | Peter Egyed |
| |
Affiliation: | (1) School of Computer Science, McGill University, 805 Sherbrooke St. West, H3A 2K6 Montreal, Quebec, Canada |
| |
Abstract: | Many of the fundamental problems in computer graphics involve the notion of visibility. In one approach to the hiddensurface problem, priorities are assigned to the faces of a scene. A realistic image is then rendered by displaying the faces with the resulting priority ordering. We introduce a tree-based formalism for describing priority orderings that simplifies an existing algorithm. As well, a decompositionbased algorithm is presented for classes of scenes that do not in general admit priority orderings. The algorithm requiresO(n logn) time ift=1 andO(tn logn+n logn logm) time ift>1, wheren andm are respectively the number of faces and polyhedra in the scene, andt is a minimum decomposition factor of the scene. Finally, the tree-based formalism is used in the development ofO(n) time insertion and deletion algorithms that solve the problem of dynamically maintaining a priority ordering. |
| |
Keywords: | Hidden-surface problems Computational geometry Priority orderings Decomposition techniques Dynamization techniques |
本文献已被 SpringerLink 等数据库收录! |
|