A final method is, of course, to construct a smooth volume by blurring the binary volume with a large, discrete filter. This simple approach is discussed by Gibson [64] who reports that only very large smoothing filters (as large as 19×19×19vu3 Gaußian filters) suffice to hide the artifacts. Filtering with so large kernels is time consuming. Moreover, the blurring will remove small features which is not desirable.
In summary, the proposed methods for reconstructing smooth boundary surfaces from binary volume data are either very costly [61, 179] or yield a result that is not completely satisfying [39, 53]. Simply blurring the volume combines both demerits.
3.4 V–models
The characteristic function associated with a solid is simply a trivariate function that represents the solid but is more amenable to sampling and reconstruction than the inside–outside function. Obviously, there are infinitely many ways in which we can construct characteristic functions, and it is clear that we might have to deal with a large family of methods. To be able to discuss such methods more effectively, ˇSr´amek introduced the notion of aV–model [172].
A V–model is simply a trivariate function which represents the solid but can be sampled and reconstructed with greater fidelity than the inside–outside func-tion. The term V–model can be used in two senses. There are V–models of specific solids. In that case the word V–model is synonymous with the term characteristic function which has been used so far. However, the word V–model will also be used in an abstract sense to denote a particular type or class of characteristic functions.
In the following, the V–model of a solidS ⊂R3 will be denoted V(S) and the value of a V–model at given pointp∈R3 isV(S)(p).
There are several conditions that a good V–model should fulfill. First of all there should be an isovalueτ so that
V(S)(∂S) =τ (3.28)
In other words, the boundary of the solid should be represented by some unique value. This is because all methods for visualizing surfaces in volume data basi-cally render iso–surfaces.
In general, the value of V(S) lies in some interval, say V(S)∈[a, b]. At points
far away from the boundary ofS, the value of the V–model is usually eitheraor b depending on whether the point is inside or outside. The rest of the interval ]a, b[ is used only in a transition region that envelops the boundary surface.
The transition region is of widthrifV(S) =aor V(S) =bonly for points at a distance greater thanrfrom∂S.
Since our main concern is to be able to reconstruct the value of the V–model from the volume in the vicinity of the boundary surface, we require of the V–
model that the transition region is wide enough to accommodate the entire support of the reconstruction filters and gradient reconstruction filters if the centre of the support is on or very close to the boundary surface. These issues are illustrated in Figure 3.5.
(S) = a V
(S) = b V Reconstruction filter support
Boundary surface Transition
region
Figure 3.5: A V–model. The boundary surface (heavy line) and transition region (filled area). The support of the reconstruction filter is shown as a dashed circle inside the transition region.
3.4.1 Prefiltering
The first work on non–binary volume sampling of geometric primitives (solids or polygons) was done by Wang and Kaufman in [173]. Their method, known as prefiltering was to convolve the inside–outside function of a geometric primitive
3.4 V–models 57
with a Bartlett filter3before sampling in order to band-limit the function. While the Bartlett filter is not the ideal filter, it is probably a good choice, because it contains a lot of smoothing and does not introduce ringing. In practice its application is a weighted averaging of the inside–outside function in the region within its support.
It is only necessary to know the value of the convolution at voxel positions, hence a numerical solution is feasible, and the method was successful in producing voxelized objects with few visible aliasing artifacts.
At first it seems that prefiltering is an obvious way to construct V–models; the inside–outside function is discontinuous, hence cannot be reconstructed with ad-equate fidelity. The prefiltering approach band–limits the inside–outside func-tion before sampling which solves that problem. However, there is another problem. It was stated above that there should be an iso–value, τ, so that V(S)(∂S) =τ, but if
V(S) =IS⋆Ba (3.29)
where IS is the inside–outside function andBa is the Bartlett filter, the value ofV(S) at a pointp ∈∂S will depend on the curvature of∂S atp.
The problem is illustrated in Figure 3.6 where we observe that only a planar surface divides a spherical support in two identical halves when the centre of the support is exactly on the surface of the solid. The greater the curvature at the boundary point, the greater the difference between the part of the support that intersects the solid and the part that does not, and as the filter is positive at all points within the support, the result of the convolution will also differ.
Note that the error is not a byproduct of sampling and interpolation, but an intrinsic problem with the method.
There is one more problem with the prefiltering approach which pertains to gradient estimation: It has been shown theoretically and verified experimentally by ˇSr´amek et al. [171] that systematic errors in the reconstructed gradient direction are introduced if central differences are used to reconstruct gradients from a Wang V–model.
The problem is analyzed theoretically by showing that even for a planar surface a gradient error is introduced if the V–model does not vary linearly with the distance to the surface. If the V–model is constructed by convolving the inside–
outside function with a Gaußian, the error is as large as 0.07 radians – even for planar surfaces; the error depends only on orientation and how much the
3Also known as the hypercone filter. The filter has its maximum in the centre of the support and the value decreases linearly with the distance to the centre to 0 at the edge of the support
Convolution kernel support
Solid
Figure 3.6: Intersection of solid and filter support
V–model deviates from linearity.
3.4.2 Distance Fields
Recently, another and simpler technique has been employed for solid voxeliza-tion by e.g. ˇSr´amek [171, 172], Gibson [64], and Breen [21]. The idea is to simply sample the distance function (3.30) or a function that is proportional to the distance function. It is possible to sample and interpolate the distance func-tion just like the convolved inside–outside funcfunc-tion; in addifunc-tion, this approach has the advantage that it is simpler (in fact the prefiltering method uses the dis-tance field), and has experimentally been shown to yield superior results [171].
Moreover, it is obvious that the zero–set of the distance function corresponds to the boundary surface of the solid. Hence, there is no gratuitous error in this type of characteristic function.
Formally, we define the distance function associated with a solidS in the fol-lowing way
dS(p) =
−inf∀q∈∂S||p−q|| p∈S
inf∀q∈∂S||p−q|| p∈/S (3.30) It is apparent from (3.30) that we use the convention thatdS is positive outside and negative inside the solid, so it is really a signed distance function.
A typical example of a solid is the sphere. The entire sphere with centrep0and
3.4 V–models 59 Various reconstruction filters may be applied to the voxel raster to reconstruct the value at arbitrary locations, and the trilinear filter yields quite good results.
Sr´amek shows experimentally that the surface reconstruction error for a sphereˇ decreases as the radius increases and reports an average error of less than 0.05 vu [172] for the reconstruction of a sphere of a radius of 4 vu. Both Gibson and ˇSr´amek conjecture that the error is curvature dependent, and Gibson also notes that certain special cases must be taken into account. These special cases are when critical points in the distance field come so close to the surface that they are within the support of reconstruction or gradient reconstruction filters.
This can either be due to sharp edges or, in the case of an object with a smooth surface, due to two surfaces (or surface components) that are close to each other.
These conditions will be made more specific in the next chapter.
The signed distance function associated with a solid is sometimes called aHesse normalform [77]. The normalform has several useful properties. For instance, the gradient is always unit length, and we can easily find foot points on the boundary of the solid. A foot point is simply the orthogonal projection of a point onto a surface:
pfoot=p−dS(p)∇dS(p) (3.34) This turns out to be very useful, because it means that the solid can be rendered using point rendering [70, 131] which is much simpler than either ray casting or polygonization.
Additionally, it is easier to compute curvature from a normalform than from other types of V–models. To demonstrate this, I discuss some formulas below which are taken from [77].
The Hessian,H, ofdS is the matrix of second order partial derivatives H =
The mean curvature at a given surface point can be found very easily, if we can evaluate the Hessian at that point:
κM = 1
2Tr(H) =1
2 (dS xx+dS yy+dS zz) (3.36)
The Gaußian curvature is
and the principal curvatures are the two non–zero eigenvalues ofH. The last eigenvalue is 0 reflecting the fact thatdS changes linearly in the gradient direc-tion – hence the second order change is 0 in that direcdirec-tion. The characteristic polynomial ofH is
λ3+ 2κMλ2−κGλ= 0 (3.38) Letf be a generic V–model that does not change linearly with the distance to the solid. In that case, the mean curvature is computed using the formula below
κM =
(fyy+fzz)fx2+ (fxx+fzz)fy2+ (fxx+fyy)fz2
−2(fxfyfxy+fxfzfxz+fyfzfyz)
(fx2+fy2+fz2)3/2 (3.39) which is found in the literature [156]. Clearly, (3.36) is simpler than (3.39) which indicates that one can estimate curvature properties more easily from volumes if the voxels are samples of the distance function.
3.4.3 Distance Profiles
In [172] various V–models are examined. These are all constructed as functions of the signed distance function. In other words
V(S)(p) =g(dS(p)) (3.40)
where g is thedensity profile associated with the V–model. ˇSr´amek finds that two profiles are of special interest, namely the piece-wise linear profile4
g(x) = min(max(−r, x), r) (3.41) where r is the width of the transition region. This distance profile does not change the actual distance value but simply clamps its value to the [−r, r] range.
It was found experimentally that for r > 1.8 the surface position could be reconstructed using trilinear interpolation to within a tolerance of 0.2vu(which was deemed acceptable) for spheres of radii down to 2. For spheres of radii down to 10, the normal error is negligible when the normal is based on a trilinearly interpolated central differences gradient estimate. From the plots, it is clear that normal error stays below 0.01 radians for spheres down to radius 4.
4In [172]g(·)∈[0,1] but there is no practical difference between this profile and (3.41).