Three-dimensional scan-conversion of geometric objects
Daniel C. Cohen · 1993
Volumetric Graphics is the subfield of computer graphics that employs a 3D raster of voxels for scene representation. We compare in this work the characteristic properties of the voxel-based representation with the traditional continuous geometric representation of 3D objects. When the voxel-based model is represented by a full 3D array it can be regarded as the 3D counterpart of the 2D raster. The process of approximating a continuous geometric object with a voxel-based representation is called 3D scan-conversion or voxelization. The development of voxelization methods is focused on mechanisms that obey 3D discrete topology requirements in order to guarantee a discrete representation that is well-matched to the continuous geometric object. Unfortunately, in 3D space there are many important topological properties that cannot be stated only in terms of connectivity. As a remedy, we introduce new concepts with which the voxelized object can be topologically and geometrically matched to the continuous object it approximates. The study of those concepts form a theoretical framework for the voxelization process. Based on the theory of voxelization, new techniques for the voxelization of basic primitive objects are developed. A 3D line is especially important, first, as a building block for the voxelization of more complex objects (e.g., cylinders, cones). In addition, 3D discrete lines are also used to simulate the traversal of rays through voxel space. Discrete lines are classified by their connectivity which implies an accuracy-speed tradeoff. An adaptive technique that switches between connectivities and capitalizes on the advantage of the different connectivities, is proposed. A 3D circle is another fundamental primitive employed in the generation of circular and quadric objects. Several efficient algorithms which use the symmetry and planarity of the 3D circle are suggested. We further introduce the weaving technique that generates a web of voxels by sweeping one curve along another. When the curves maintain their shapes a foil is generated. This technique offers some control over the foil topology by varying the web density, and it is extremely efficient when employing a template mechanism. In this work we elaborate on planar foils used for the voxelization of planar objects (e.g., polygons, disks).