The Priority Face Determination Tree for Hidden Surface Removal

dc.contributor.authorJames, A.en_US
dc.contributor.authorDay, A. M.en_US
dc.date.accessioned2015-02-15T18:30:37Z
dc.date.available2015-02-15T18:30:37Z
dc.date.issued1998en_US
dc.description.abstractMany 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.en_US
dc.description.number1en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume17en_US
dc.identifier.doi10.1111/1467-8659.00215en_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages55-71en_US
dc.identifier.urihttps://doi.org/10.1111/1467-8659.00215en_US
dc.publisherBlackwell Publishers Ltd and the Eurographics Associationen_US
dc.titleThe Priority Face Determination Tree for Hidden Surface Removalen_US
Files
Collections