On visible surface generation by a priori tree structures

This paper describes a new algorithm for solving the hidden surface (or line) problem, to more rapidly generate realistic images of 3-D scenes composed of polygons, and presents the development of theoretical foundations in the area as well as additional related algorithms. As in many applications the environment to be displayed consists of polygons many of whose relative geometric relations are static, we attempt to capitalize on this by pre processing tile environment,s database so as to decrease the run-time computations required to generate a scene. This preprocessing is based on generating a "ninary space partitioning" tree whose inorder traversal of visibility priority at run-time will produce a lineaL" order, dependent upon the viewing position, on (parts of) the polygons, which can then be used to easily solve the hidden surfac6 problem. In the application where the entire environment is static with only the viewing-position changing, as is common in simulation, the results presented will be safficient to solve completely tlae llidden surface problem.