Even better results were obtained for Gaußian profiles g(x) =
Z x
−∞
et/σdt (3.42)
where σ = 1. However, interpolation is by a tricubic filter and gradients are calculated using the Gabor filter [172]. This combination yields very small surface errors for spheres of radii down to 1 and virtually no errors on gradient direction. However, rendering is slower (by 20–35 %) and voxelization took up to twice as long for the Gaußian profile as for the linear.
3.5 Discussion
It is costly in terms of computational effort to reconstruct a smooth surface from a binary solid. Moreover, it is essentially guesswork. The same is not true of the scalar volume representation. Here, the fidelity depends on the choice of V–
model, reconstruction filters and volume resolution. By tuning these parameters, we can make the volume representation as precise as required.
Therefore, we can conclude that it is sensible to choose the V–model paradigm as the basis for a representation of (smooth) free-form shapes. However, the pre-filtered V–models have been shown to suffer from certain problems: A curvature dependent error is introducedbefore sampling of the V–model. More precisely, this means that (3.28) does not always hold. The error is usually small, but the distance field approach avoids it all together. In addition, central differences cannot be used for gradient reconstruction without introducing an error that depends on surface orientation.
Thus, it seems sensible to choose a V–model that is based on a distance profile;
simply using unbounded distances is problematic. It would mean that the ma-nipulations (which will be discussed in part III) will have to maintain correct V–model values for all voxels and not merely those in the neighbourhood of the surfaces of represented solids. Furthermore (as mentioned in the introduc-tion) it is more space efficient to clamp the values, mainly because it facilitates compression of the volume data.
Sr´amek has demonstrated that the Gaußian profile allows us to reconstructˇ rather small features with good precision. However, this profile entails the use of tricubic interpolation filters and the Gabor filter for reconstructing gradi-ents. A linear profile (i.e. (3.41)) on the other hand has the advantage that we can use our knowledge of the Hesse normalform to simplify curvature com-putations. In addition this profile incurs less overhead for reconstruction and
gradient reconstruction because trilinear interpolation and central differences gradient estimates yield acceptable results.
For these reasons, the V–model that will be employed in the rest of this thesis is the clamped, signed distance function
V(S)(p) = min(max(−r, dS(p)), r) (3.43) where
dS(p) =
−inf∀q∈∂S||p−q|| p∈S
inf∀q∈∂S||p−q|| p∈/S (3.44)
Chapter 4
Solids Suitable for Volume Representation
In the previous chapter, we discussed various V–models and found that the clamped, signed distance V–model is a good choice. However, not all solids are well suited to the volume representation. The V–model itself does not ensure that we can sample and reconstruct a solid with adequate fidelity. The aim of this chapter is to develop a criterion for whether a solid is suitable for voxelization at a given resolution. The essence of the criterion is to test that the surface curvature does not exceed a given bound and that the features of the solid are not too fine for the resolution.
In the first section, the scope is narrowed by the definition of permissible solids.
A solid that is not permissible is not suited for volume representation at all, and throwing away such solids simplifies the criterion. In Section 4.2 we shall see how we can guarantee a transition region where the signed distance function isC1. In Section 4.4 tools for characterizing solids in terms of mathematical morphology are provided, and in Section 4.5 these are tied to reconstruction filters. Finally, a closed–form and an empirical error bound for the trilinear reconstruction error are provided in 4.6. In both cases, we assume that the clamped, signed distance V–model is used. It is also assumed that trilinear interpolation and central differences gradient reconstruction are used for the reconstruction of distance values and gradients, respectively. In Section 4.7 contains a discussion of the
results and their practical application.
4.1 Permissible Solids
What solids are suitable for volume representation? Clearly the suitability of a given solid depends on the relative scale of the solid and the voxel grid. How-ever, some solids are not suitable regardless of scale, and as a starting point, we shall define permissible solids as those that might be suitable for volume representation atsome scale.
A reasonable starting point is to require that a permissible solidS ⊂R3 must be a three-dimensional manifold with boundary and that its boundary∂S⊂S is a two–dimensional manifold [184, 75]. In fact, we only need to require that the solid is a three–dimensional manifold with boundary, since it follows that its boundary must then be a two–dimensional manifold. These requirements are typical in solid modelling and while traditional CAD–systems based on bound-ary representations can, in principle, handle non–manifold topology1, the same is not true of the volume representation where we can only represent structures if they have some thickness. In other words, non–manifold structures such as dangling edges or isolated points are not permissible.
It is also important that the boundary ∂S is reasonably smooth, since sharp edges are a problem in the volume representation. Therefore, as a minimum, we require that∂SisC1–smooth [184]. Basically, this means that for any point pi ∈∂S we can locally represent the surface ∂S with parameterizations of the form ψi :R2→R3 that have continuous first order partial derivatives and the Jacobian matrix ofψi must have rank 2 [105].
In summary, we can definepermissible solids in terms of two conditions Definition 4.1 Permissible Solids: Solid S is permissible if it fulfills the fol-lowing two conditions:
1. Manifold topology: S must be a three–dimensional manifold R3 with boundary ∂S⊂S. ∂S is then a two–dimensional manifold inR3.
2. Minimal smoothness: ∂S must be, at least, aC1 smooth surface.
1 Typically CAD systems also require solids to have manifold topology, but some solid modellers like ACIS allow for modelling of non–manifold objects.