The hidden face determination tree

摘要

Hidden surface removal can be achieved using the priority face determination (PFD) tree to create a priority ordering of n polygons in log_4/3 n time. In this paper, we show how the number of polygons stored in the tree and drawn to the screen can be minimized significantly by determining, at the pre-processing state, which polygons are completely hidden by other polygons from particular regions of the scene. The removal of hidden polygons at the pre-processing stage means that there is no need to even consider them at run time. The cost for the resulting decrease in run time is an increase in the pre-processing time, but techniques for reducing this are presented.