A priori based techniques for determining visibility priority for 3-d scenes
Bruce F. Naylor · 1981
Currently, simulation of real time motion of 3-D images requires expensive special purpose hardware and consequently is limited chiefly to training simulators. Only a restricted number of types of scenes can be generated, the primary limiting factor being the difficulty of solving the surface problem. Simulators provide an environment in which it has been acceptable to restrict simulated movement primarily to the trainee's viewing position. As the chief modeling technique is to approximate objects with closed polyhedra, restricting the database to a static condition geometrically allows for offline preprocessing to be performed which is able to capitalize on the time invariant geometric relations of the polygons comprizing the polyhedra. Such preprocessing produces a data structure which enables a faster solution to the hidden surface problem than methods which involve no preprocessing. However, methods based on preprocessing that have been developed heretofore are not automated, which greatly restricts the displayable objects. Presented is a formalization of the concepts of a priority ordering and of partitioning a collection of sets of points by a hyperplane. These form a basis from which it is possible to develop two methods which allow for a complete automation of the preprocessing and which is capable of handling any arbitrary scene. One approach involves creation of a directed graph of the relation of potential visibility obstruction. It is known that a primary limitation to the previous approach is the presence of cycles in this graph which consequently prevent an assignment of a priority ordering. This graph is reduced to its strongly connected components, and a technique is presented for obtaining a priority ordering for a given viewing position which is based on a solution for a single simple cycle. The second approach entails the construction of a space partitioning This data structure is a generalization of multidimensional binary search trees (k-d trees). The method involves recursively partitioning space by the planes of the polygons comprizing the visible database and the attendent construction of a binary space partitioning tree which corresponds to this partitioning. It is then possible to obtain a priority ordering on (parts of) the polygons by an inorder-like traversal of the tree, where polygons are represented by the nodes of the tree. The order of the traversal is dependent upon the current viewing position.