THE PRIORITY FACE DETERMINATION TREE FOR HIDDEN SURFACE REMOVAL

Many virtual environments are built from a set of polygons that form t he basis of objects in the scene. Using priority-list algorithms, the sequence in which these polygons are drawn is dependent upon the locat ion of an observer; the polygons must be ordered correctly before a re alistic image can be displayed. It is necessary for a scene to be draw n correctly in weal time from all locations before the observer can mo ve interactively around the scene with complete freedom. The binary-sp ace partitioning (BSP) tree developed by Fuchs, Kedem and Naylor in 19 80 stores the view independent priority of a set of polygons which cal l be used to obtain the correct order for any given viewpoint. However , the number of polygons grows significantly due to the BSP splitting stage, increasing the number of nodes in the tree. This affects linear ly the number of tests necessary to traverse the ti ee to obtain the p riority of the set of polygons. The algorithm presented here is built using its associated BSP tl ee, but attempts to reduce the number of t ests to, log(4/3) n, at the cost of a tl ee of size of O(N1.5(log4/3) (n-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 r un-time efficiency, a height plane is used to restrict the view point of the observed to a fixed height, but the key to the efficiency of th e algorithm is in the use of polygonal dependencies. In the scene; if we know our location relative to the front ol back of a polygon, then our position relative to one-quarter of the remaining polygons, in the expected worst-case, can be determined.