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

摘要

To generate two-dimensional images of three-dimensional solid objects at high speed, an object is defined within a three-dimensional universe hierarchically subdivided into a plurality of discrete volumes of uniform size and similar orientation. The three-dimensional universe is represented by an octree structure having a plurality of nodes, one for every volume in the three-dimensional universe which is at least partially occupied by the object. An arbitrary point of view is selected. Nodes in the tree structure representing the three-dimensional universe are visited in a sequence determined by the selected point of view so that nodes corresponding to volumes which are unobstructed by other volumes are visited first. Each visited node contained by the object is projected onto a subdivided view plane organized into a hierarchy of discrete areas. Areas of the view plane enclosed by the projection are painted onto a display screen. View plane areas which intersect but are not enclosed by the projection are further subdivided. To create sectional views, a user may define a region of the three-dimensional universe, and volumes outside of that region are not projected. 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.