Hidden Surface Removal through Object Space Decomposition.

摘要

Hidden surface removal is a computer graphics problem involving a great deal of computation. The problem involves two facets: determining which objects should appear in front of others (prioritization), and elimination of invisible portions of the objects through geometric calculations. Prioritization is accomplished using object space decomposition, which divides object space in a binary fashion such that the objects in a scene (or critical portions of those objects) occupy unique sub-volumes of the object space. An octal-tree is used to map the decomposition, and a simple traversal of the tree, with minor interruptions for more sophisticated decision-making, results in a stream of objects in priority order. The second phase of the hidden surface problem, removal of invisible portions of objects, often requires a great deal of computation. Parallel processing offers potential for savings in response time, and the second part of this thesis investigates a number of algorithms which attempt to take advantage of inherent concurrency. Three algorithms are presented: a quad-tree image space decomposition algorithm, a purely geometric algorithm, and an algorithm which combines ideas from the first two. (Author)