Polygon visibility ordering via Voronoi diagrams |
| |
Authors: | Shinichi Fukushige Hiromasa Suzuki |
| |
Affiliation: | (1) Graduate School of Engineering, Osaka University, 2-1 Yamada-oka, Suita Osaka, 565-0871, Japan;(2) Research Center for Advanced Science and Technology, The University of Tokyo, Komaba 4-6-1, Meguro Tokyo, 153-8904, Japan |
| |
Abstract: | Visibility determination is one of the oldest problems in computer graphics. The visibility, in terms of back-to-front polygon
visibility ordering, is determined by updating a priority list as the viewpoint moves. A new list-priority algorithm, utilizing
a property of Voronoi diagrams, is proposed in this paper. The operation is in two phases. First, in a pre-processing phase
the scene is divided into Voronoi cells. A sub-list associated with each cell contains references to those polygons that intersect
with it. The polygons are assigned a fixed set of view-independent priority orders within the cluster. Last, an interactive
phase sorts the clusters according to the depth value of each Voronoi site. The most time-consuming work is performed during
the pre-processing phase that only has to be executed once for the scene. Since all the polygons in a cell are pre-computed
to obtain the fixed priority order within the cluster, a relatively simple task is left in the interactive phase, which is
only to sort the clusters repeatedly when the viewpoint is changed. This method contains performance benefits that make it
better shaped than previous BSP based methods. |
| |
Keywords: | Visibility determination Voronoi diagrams Space subdivision Visibility ordering Priority algorithm |
本文献已被 SpringerLink 等数据库收录! |
|