At this point, we can define the inverse,Si, of a solidS. We would expect that Siis a permissible solid. Unfortunately, we cannot simply define the inverse solid as thecomplementofS. Because a permissible solidS includes its boundary, it must be aclosed set. It follows that its complement,Sc, isopen. Fortunately, the problem is easy to fix, if we define theinverse solid in the following way
Si=Sc[
∂S (4.1)
According to this definition, a solid and its inverse share their boundary, formally STSi = ∂S. Note that this is quite compatible with the V–model concept and in particular our chosen V–model (3.43). The V–model is designed so that the zero–set of the V–model is identical to the boundary of the solid:
∂S = {x| V(S)(x) = 0}. If we flip the sign of the V–model, the zero–set is unaffected while the inside and outside are swapped. Thus
V(Si) =−V(S) (4.2)
4.2 Curvature and Singularities
Of course, permissibility is not sufficient to ensure that a solid is suitable for representation in any voxel grid. In [64] Gibson discusses issues that influence the choice of volume resolution. Two causes of error in reconstruction and gradient reconstruction are singled out, namely high surface curvature and sin-gularities (meaning gradient discontinuities) in the distance field. Both issues are relatively unsurprising. The quality of interpolation generally depends on the smoothness of the function that is being interpolated. If one uses trilinear reconstruction, one can only exactly reconstruct a function that is linear in x, y, and z. Thus, a high quality reconstruction depends on the assumption of linearity being reasonable, and the presence of high curvature and singularities adversely affect the validity of this assumption.
Later in this chapter, a closed form bound on the reconstruction error as a func-tion of curvature is presented as well as experiments which show the dependence of reconstruction error on surface curvatures. However, various measures of cur-vature are used, so first we need a definition of what is meant by “curcur-vature”. In this chapter, we will not use Gaußian or average curvature, socurvature means normal curvature. We recall that a normal curvature at a given pointpis the curvature of a curve resulting from the intersection of the surface and a plane containing the normal [32]. The principal curvatures at a given point are the greatest and smallest normal curvature.
The boundary surface of the solid is really just one iso–surface of the distance function (the zero–level isosurface). It will prove useful to have a definition of
the curvature at a point which is not on the boundary of the solid but belongs to some other iso–surface. These considerations lead to the following definitions
Definition 4.2 Maximum curvature
LetdS be the signed distance function of a solidS.
• The maximum curvature Kmax(p) at a pointpis the numerical value of the numerically greatest principal curvature (of the iso–surface ofdS cor-responding to the isovaluedS(p)) atp.
• The maximum curvature of a regionX ⊂R3 is Kmax(X) = sup
p∈X
Kmax(p) (4.3)
With this definition, it is possible to formulate a bound on the reconstruction error as a function of maximum curvature.
However, low curvature is not sufficient to guarantee good reconstruction. The reconstruction and gradient reconstruction is also sensitive to singularities in the distance field, but where do these singularities occur? Recall that the distance field of a solid is a function that returns the shortest distance to the closest point on the boundary of the solid. This function is continuous everywhere but the same is not true of the mapping that maps a point to its closest boundary point, and the singularities occur where the closest boundary point changes abruptly.
This is clear because the gradient of the distance field at a point pis equal to the normalized vector from the closest point on ∂S to p. For example, if S consists of two disconnected solid spheres arranged as shown in Figure 4.1, the gradient field is discontinuous along the plane illustrated by the vertical line.
A central differences gradient stencil is also shown in the figure. Note that all but one voxel is closer to the left disk. Clearly, this may result in a poor gradient estimate since the value of the last voxel represents the distance to the right sphere whereas the other voxels represent the distance to the left.
The locus where the closest point changes abruptly is called the medial surface2, and for permissible solids we can show that the gradient of the distance field is only discontinuous on points belonging to the medial surface of either the solid or its inverse.
Hence, to avoid singularities, we need only ensure that the medial surfaces of the solid and its inverse do not intersect the transition region. Because the
2The medial surface is the three–dimensional analogue of the two–dimensional medial axis.
4.2 Curvature and Singularities 67
M(S )i
S
Figure 4.1: Gradient stencil whose voxels are distributed on both sides of the medial surface ofSi.
thickness of the transition region is defined in terms of voxel units (vu) this is where scale becomes important. A condition which ensures exactly that the medial surface is outside of the transition region will be presented in Section 4.4, but first we need to show that the distance field isC1 for all other points than those belonging to the medial surfaces. That this is the case, can be inferred from the works of Wolter [184] and Krantz and Parks [94].
Definition 4.3 Medial SurfaceM(S) of a solidS
Ifpis the centre of a closed ball,brp, of radius rand there is no ball of greater radius which properly includesbrp whilst itself being included in S, then brp is maximal, and its centre p belongs to the medial surface. To ensure that the medial surface is a closed set, the limit points of the centres of maximal balls are included.
The medial surface is closely linked to a similar concept known as the cut locus:
Definition 4.4 Cut LocusC(A) of a setA⊂R3The closure of the set of points that have at least two distinct nearest neighbours inA, a nearest neighbour being the closest point inA.
Both of these definitions are adapted from a technical report by F.–E. Wolter [184]. Theorem one from the same report states that the medial surfaceM(S)
of a solid S is equal to the intersection of the solid and the cut locus of its boundary. Formally: M(S) =C(∂S)T
S. Equivalently,M(Si) =C(∂Si)T Si. the medial surface of the inverse solidSi is equal toC(∂S)T
Si.
Figure 4.2: Medial surface of a solid and parts of the medial surface of the inverse.
According to theorem 2B of [184] theunsigned distance function of a closed set A is aC1 continuous function in R3\(AS
C(A)). If we identify∂S withA, we now have a function that differs from the signed distance function only by the sign in the interior ofSwhich cannot affect its differentiability. Thus, it is clear that the signed distance function is C1 except at points belonging to the cut locus or the boundary.
What remains is to make sure that the signed distance function is alsoC1 on the boundary. This can be shown if we assume that ∂S is of positive reach.
Essentially, this means that the cut locus of ∂S does not touch the surface.
More precisely, any point on the∂S must have an open neighbourhood inside of which each point has a unique nearest point on ∂S [94]. The first theorem of [94] proves that if ∂S is C1 and of positive reach, then there is an open neighbourhood of the surface where the signed distance function isC1.
We conclude that if the cut locus of∂Sdoes not touch∂S, we are ensured that the distance function is C1 everywhere except at the cut locus. Actually, the cut locus is guaranteed not to touch the boundary, if we require something that is slightly stronger than permissibility, namely that the partial derivatives of ψ are Lipschitz continuous3. Theorem 4 of [184] asserts that given the same conditions as those for a permissible solid plus the condition that the partial derivatives of a parameterizationψ are Lipschitz, the cut locus does not touch the surface.
3A function, e.g. f : R → R is Lipschitz continuous, if there is a constant c so that
|f(a)−f(b)| ≤c|a−b|for any pair ofaandb.