It was mentioned earlier that binary volumes are not suitable for the represen-tation of smooth surfaces. On the other hand, binary volumes do have some virtues. For instance, it has been observed [179] that compressed binary volume data is a rather compact representation. In addition, the implementation of constructive operations is trivial. For instance, the union of two binary volumes is the result of a Boolean OR operation applied pairwise between all voxels at the same location in each volume [53]. Of course, voxelization of solids becomes simpler too. All we need to do is for each voxel to check if its centre is interior or exterior with respect to the solid. These examples show that there is ample mo-tivation for using binary volumes, and we need to explain why the binary volume representation is wholly unsuitable for the representation of smooth surfaces.
Binary voxelization amounts to sampling the inside–outside function of a solid directly. We can reconstruct an approximation of the original 3D solid, simply by construing each voxel as a small cuboid box around the voxel position that is either empty (it the the value is 0) or full (if the value is 1). This is illustrated in 2D in Figure 3.4. Unfortunately, if we simply draw each voxel as a little box, the result is, of course, blocky. The solution would be simple, if we could recon-struct the inside–outside function at arbitrary points in space. However, this is difficult: The inside–outside function is discontinuous at the boundary of the solid, and functions with discontinuities are known to be prone to aliasing since the discontinuities are represented by high frequencies in the Fourier domain.
We can also approach the problem in the spatial domain which is perhaps more intuitive. Looking at Figure 3.4 it becomes clear that the smooth shape whose outline is shown is not the only one that could have given rise to the correspond-ing binary approximation. This leads us to the fundamental problem of binary volumes: The same binary volume corresponds to infinitely many continuous solids. Conversely, two very different solids may give rise to the same binary volume when their inside–outside functions are sampled.
3.3 The Binary Volume Representation 53
Figure 3.4: A 2D example of a binary volume
One approach to this problem is to approximate the boundary of the solid with a deformable model. A deformable model is basically a representation of the shape (or its boundary surface) that we are able to deform. Associated with a deformable model is an energy function. The model is deformed until the energy is minimized subject to the constraint that the inside–outside function corresponding to the deformable model must give rise to the same binary volume as the original solid. The result is the most likely surface (in terms of the energy function) that could have given rise to the binary volume.
This is exactly the approach taken by Gibson in [61]. The deformable model is a net of connected nodes. The net is deformed by moving each node. The associated energy functional is the sum of squared distances between connected nodes.
For each cell2in the binary volume we check if at least one of the corner voxels is different from the others. If that is the case, a node is placed in the center of the cell. The next step is to connect each node to the nodes in face–adjacent cells. In this way a representation of the boundary is built. This representation serves as a deformable model, and each node is now moved so as to be at the same distance from each neighbour. This process is iterated until the energy is minimized.
It is trivial to construct a triangle mesh from this deformable model, and the
2Recall that a cell is a cube whose eight vertices lie at voxel positions.
mesh can either be rendered or revoxelized to create a distance volume. The main weakness of the method is that the deformable model is an explicit surface representation. If the desired end–product is a volume, we have to revoxelize the mesh.
This problem was addressed by Ross Whitaker [179]. Whitaker uses the Level–
Set Method (See Section 7.3). Hence, the deformable model is represented implicitly as the level–set of a time–varying volume. The level–set model is deformed with a flow that minimizes surface area subject to the constraint that the surface should remain close to the surface of the original binary volume.
The method works well on many examples, but seems to have problems with certain features such as sharp edges where aliasing artifacts are not removed.
The fundamental problem is that the goal – surface area minimization – is not always the goal that leads to the most correct surface.
While the methods are interesting, they are not suitable for interactive visual-ization of volume data. Gibson has no timings, but the method involves iterative minimization of energy; something that cannot be accomplished quickly for large volumes. Whitaker reports timings on the order of minutes.
A very different and much simpler approach is to accept the binary nature of the voxels but to ensure that gradients are smooth. In [53] Fang et al. estimate the gradients using the Zucker–Hummel gradient operator [188] of size 3×3×3 or 5×5×5. The volume is subsequently rendered using the texture mapping approach [176]. The results are not completely satisfactory, however, and the authors mention a better rendering method as a part of their future research.
Yet another approach is taken in [39]. Here, Cohen et al. propose a method to reconstruct smooth surfaces from binary volume data by constructing a smooth scalar field from the binary volume. The authors construct a pair of functionsg andhthat are defined on the voxel lattice. The former represents the distance from an interior (exterior) voxel to the closest exterior (interior) voxel; the latter is the number of voxels in a given neighbourhood that differ from the given voxel.
A weighted sum of these two functions yields a pseudo–distance measure at each voxel. A smooth scalar field is constructed by tricubic interpolation (using the Hermite polynomials) of this measure.
The result is a smooth surface from very low resolution binary volume data.
Judging from the figure in the paper, the method produces a visually pleasing result. However, it does not hide the block–structure of the binary volume data – it merely makes the blocks blend in a smooth fashion. The model used in the paper is extremely low resolution (9×6×3 voxels). At higher resolutions one suspects that the blocky appearance would be almost as apparent as when using simpler methods, although the blocks would be smoothly blended.