[an error occurred while processing this directive]

"Volume Graphics" IEEE Computer, Vol. 26, No. 7 July 1993 pp. 51-64

[an error occurred while processing this directive]

Sidebar:  Fundamentals of Voxelization

Introduction

An indispensable stage in volume graphics is the synthesis of voxel-represented objects. This stage, which is called voxelization , is concerned with converting geometric objects from their continuous geometric representation into a set of voxels that best approximates the continuous object. As this process mimics the scan-conversion process that pixelizes (rasterizes) 2D geometric objects, it is also referred to as 3D scan-conversion . In 2D rasterization the pixels are directly drawn onto the screen to be visualized and filtering is applied to reduce the aliasing artifacts. However, the voxelization process does not render the voxels but merely generates a database of the discrete digitization of the continuous object.

Intuitively, one would assume that a proper voxelization simply selects all voxels which are met (if only partially) by the object body. Although  this approach could be satisfactory in some cases, the objects it generates are commonly too coarse and include more voxels than are necessary. For example, in Figure 13 a 2D curve is rasterized into a connected sequence of pixels. Although the discrete curve does not cover the entire continuous curve, it is connected and concisely and successfully separates both sides of the curve.

One practical meaning of separation is apparent when a voxelized scene is rendered by casting discrete rays from the image plane to the scene. The penetration of the background voxels (which simulate the discrete ray traversal) through the voxelized surface causes the appearance of a hole in the final image of the rendered surface. Another type of error might occur when a 3D flooding algorithm is employed either to fill an object or to measure its a volume, surface area, or other properties. In this case the nonseparability of the surface causes leakage of the flood through the discrete surface.

Unfortunately, the extension of the 2D definition of separation to the third dimension and to surfaces is not straightforward since voxelized surfaces cannot be defined as an ordered sequence of voxels and a voxel on the surface does not have a specific number of adjacent voxels. Furthermore, there are important topological issues, such as the separation of both sides of a surface, which cannot be well-defined by employing 2D terminology. The theory that deals with these topological issues is called 3D discrete topology . We sketch below some basic notions and informal definitions used in this field.  Figure 13. An example of a 2D discrete curve (shaded pixels) that intuitively separates its two sides even without containing all those pixels pierced by the continuous line. Figure 14. The three types of voxel adjacencies in 3D discrete space: (1) the six voxels that a are 6-adjacent to the voxel at the center (not seen), (2) the eighteen voxels that are 18- adjacent to the voxel at the center, (3) the twenty six voxels that are 26-adjacent to the voxel at the center.

Fundamentals of 3D Discrete Topology

The 3D discrete space is a set of integral grid points in 3D Euclidean space defined by their Cartesian coordinates (x ,y ,z ). A voxel is the unit cubic volume centered at the integral grid point. The voxel value is mapped into {0,1}: the voxels assigned "1" are called the "black" voxels representing opaque objects, and those assigned "0" are the "white" voxels representing the transparent background. Outside the scope of this paper are non-binary approaches where the voxel value is mapped onto the interval [0,1] representing either partial coverage, variable densities, or graded opacities. Due to its larger dynamic range of values, this approach may support higher quality rendering.

Two voxels are 26-adjacent if they share either a vertex, an edge, or a face (see Figure 14). Every voxel has 26 such adjacent voxels: eight share a vertex (corner) with the center voxel (Figure 14(1)), twelve share an edge (Figure 14(2)), and six share a face (Figure 14(3)). Accordingly, face-sharing voxels are defined as 6-adjacent , and edge-sharing and face-sharing voxels are defined as 18-adjacent.

The prefix N is used to define the adjacency relation, where N= 6, 18, or 26. We say that a sequence of voxels having the same value (e.g., "black") is an N-path if all consecutive pairs are N-adjacent. A set of voxels A is N-connected if there is an N-path between every pair of voxels in A . An N-connected component is a maximal N-connected set.

Figure 15 shows a 2D discrete 8-connected black curve and a sequence of 8-connected white pixels (8-component) that passes from one side of the black component to its other side without intersecting it. This phenomenon is a discrete disagreement with the continuous case a where there is no way of penetrating a closed curve without intersecting it. To avoid such scenario, it has been the convention to define "opposite" types of connectivity for the white and black sets. Opposite types in 2D space are 4 and 8, while in 3D space 6 is opposite to 26 or to 18.  Figure 15. An example of a 2D 8-curve that does not separate its two sides. The white 8- curve penetrates from one side to the other. Figure 16. (1) a 6-connected surface that is not 6-separating. (2) a 6-connected surface that is not 18-separating.

Assume that a voxel space, denoted by , includes one subset of "black" voxels S . If -S is not N-connected, that is, -S consists of at least two white N-connected components, then S is said to be N-separating in . Loosely speaking, in 2D, an 8-connected black path that divides the white pixels into two groups is 4-separating and a 4-connected black path that divides the white pixels into two groups is 8-separating. There are no analogous results in 3D space. For example, Figure 16 shows a 6-connected set of voxels that is not 6-separating (Figure 16(1)) and a 6-connected set of voxels that is not 18-separating (Figure 16(2)).

Let A be an N-separating surface. A voxel p A is said to be an N-simple voxel if A -p is still N-separating. An N-separating surface is called N-minimal if it does not contain any N-simple voxel. A cover of a continuous surface is a set of voxels such that every point of the continuous surface lies in a voxel of the cover. A cover is said to be a minimal cover if none of its subsets is also a cover. The cover property is essential in applications that employ space subdivision for fast ray tracing . The subspaces (voxels) which contain objects have to be identified along the traced ray. Note that a cover is not necessarily separating, while on the other hand, as mentioned above, it may include simple voxels. In fact, even a minimal cover is not necessarily N-minimal for any N.

Voxelization Algorithms

In the past, digitization of solids was performed by spatial enumeration algorithms which employ point or cell classification methods in either an exhaustive fashion or by recursive subdivision . However, subdivision techniques for model decomposition into rectangular subspaces are computationally expensive and thus inappropriate for medium or high resolution grids. Instead, objects should be directly voxelized, preferably generating an N-separating, N-minimal, and covering set, where N is application dependent. The voxelization algorithms should follow the same paradigm as the 2D scan-conversion algorithms; they should be incremental, accurate, use simple arithmetic (preferably integer only), and have a complexity that is not more than linear with the number of voxels generated.

The literature of 3D scan-conversion is relatively small. Danielsson  and Mokrzycki  developed similar 3D curve algorithms where the curve is defined by the intersection of two implicit surfaces. Voxelization algorithms have been developed for 3D lines, 3D circles, and .a variety of surfaces and solids, including polygons, polyhedra, and quadric objects  Efficient algorithms have been developed for voxelizing polygons using an integer-based decision mechanism embedded within a scan-line filling algorithm , for parametric curves, surfaces, and volumes using an integer-based forward differencing technique , and for quadric objects such as cylinders, spheres, and cones using "weaving" algorithms by which a discrete circle/line sweeps along a discrete circle/line . Figures 2-9 consist of a variety of objects voxelized by using the above methods. These pioneering attempts should now be followed by enhanced voxelization algorithms that, in addition to being efficient and accurate, will also adhere to the topological requirements of separation, coverage, and minimality.

References

1. Cohen, D. and Kaufman, A., "Scan Conversion Algorithms for Linear and Quadratic Objects", in Volume Visualization, A. Kaufman, (ed.), IEEE Computer Society Press, Los Alamitos, CA, 1990, 280-301.

2. Danielsson, P. E., "Incremental Curve Generation", IEEE Transactions on Computers, C-19, (1970), 783-793.

3. Glassner, A. S., "Space Subdivision for Fast Ray Tracing", IEEE Computer Graphics and Applications, 4, 10 (October 1984), 15-22.

4. Kaufman, A. and Shimony, E., '3D Scan-Conversion Algorithms for Voxel-Based Graphics', Proc. ACM Workshop on Interactive 3D Graphics, Chapel Hill, NC, October 1986, 45-76.

5. Kaufman, A., "An Algorithm for 3D Scan-Conversion of Polygons", Proc. EUROGRAPHICS'87, Amsterdam, Netherlands, August 1987, 197-208.

6. Kaufman, A., "Efficient Algorithms for 3D Scan-Conversion of Parametric Curves, Surfaces, and Volumes", Computer Graphics, 21, 4 (July 1987), 171-179.

7. Lee, Y. T. and Requicha, A. A. G., "Algorithms for Computing the Volume and Other Integral Properties of Solids: I-Known Methods and Open Issues; II-A Family of Algorithms Based on Representation Conversion and Cellular Approximation", Communications of the ACM, 25, 9 (September 1982), 635-650.

8. Mokrzycki, W., "Algorithms of Discretization of Algebraic Spatial Curves on Homogeneous Cubical Grids", Computers & Graphics, 12, 3/4 (1988), 477-487.