The priority face determination tree for hidden surface removal

James, A. and Day, A. M. (1998) The priority face determination tree for hidden surface removal. Computer Graphics Forum, 17 (1). pp. 55-71. ISSN 0167-7055

Full text not available from this repository. (Request a copy)

Abstract

Many virtual environments are built from a set of polygons that form the basis of objects in the scene. Using priority-list algorithms, the sequence in which these polygons are drawn is dependent upon the location of an observer; the polygons must be ordered correctly before a realistic image can be displayed. It is necessary for a scene to be drawn correctly in real time from all locations before the observer can move interactively around the scene with complete freedom. The binary-space partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 1980 stores the view independent priority of a set of polygons which can be used to obtain the correct order for any given view-point. However, the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linearly the number of tests necessary to traverse the tree to obtain the priority of the set of polygons. The algorithm presented here is built using its associated BSP tree, but attempts to reduce the number of tests to, log4/3n, at the cost of a tree of size of O(N1.5log4/3n−1), where n is the initial number of polygons in the scene, and N the resulting number after BSP splitting. To achieve the increase in run-time efficiency, a height plane is used to restrict the view point of the observer to a fixed height, but the key to the efficiency of the algorithm is in the use of polygonal dependencies. In the scene; if we know our location relative to the front or back of a polygon, then our position relative to one-quarter of the remaining polygons, in the expected worst-case, can be determined.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computer Graphics (former - to 2018) Faculty of Science > Research Groups > Interactive Graphics and Audio
Depositing User:	Vishal Gautam
Date Deposited:	28 Feb 2011 10:19
Last Modified:	16 Jun 2023 23:53
URI:	https://ueaeprints.uea.ac.uk/id/eprint/21704
DOI:	10.1111/1467-8659.00215

Actions (login required)

View Item