High-speed image generation of complex solid objects using octree encoding

摘要

An image generator for generating two-dimensional images of three-dimensional solid objects at a high speed defines a scene to be displayed within a cuboid three-dimensional universe which has been hierarchically subdivided into a plurality of discrete volumes of uniform size and similar orientation. The three-dimensional universe is represented by a tree structure having a plurality of nodes, one for each volume in the three-dimensional universe which is at least partially occupied by objects in the scene. A user may select a point of view for viewing the object. Nodes in the tree structure representing the three-dimensional universe are visited in a sequence determined by the point of view selected by the user so that nodes corresponding to volumes which are unobstructed by other volumes are visited first. Each visited node which is enclosed by the object is projected onto a subdivided view plane organized into a hierarchy of a plurality of discrete areas. Areas of the view plane which are completely enclosed by the projection are painted onto a display screen. Areas which intersect but are not enclosed by the projection are further subdivided to locate those areas which are enclosed. A representation of the hierarchically-subdivided view plane arranged in a tree structure is stored in a store. Each time an area of the view plane is painted, an entry in the representation of the view plane corresponding to that area is marked. The corresponding entry in the representation of the view plane is checked before an area is painted, to ensure that no area is painted more than once so that hidden surfaces are not displayed. To create sectional views, a user may define a region of the three-dimensional universe, and volumes outside of that region are not projected. Due to the hierarchical structure of the three-dimensional universe and the two-dimensional view plane, the symmetry of subdivisions, and the resulting simplicity of the calculations necessary to create an image, real time image generation wherein calculations necessary to create the image are performed by hard-wired digital logic elements to increase speed performance is possible.