Figure 1: Reconstruction algorithm. (a) Points
extracted from CT volume
via isosurfacing. (b) 
-solid of points in (a). (c)
Supporting tetrahedral mesh and surface A-patches approximating
the
surface of the -solid. (d) Reconstructed surface model of
the distal end of the femur. Curves highlight patch
boundaries.
Our first algorithm is based on the concept of signed distance.
For a
point q in 
, let 
be the Euclidean distance
between q and the closest point on D.
An orientable, closed manifold in partitions the space in two
regions, an interior and an exterior. We define
the signed
distance function 
as the mapping 
that
associates to the point q the distance to the closest
point on D,
with a positive sign if q lies in the exterior of
D, and a negative
sign otherwise.
We build an initial piecewise-linear approximation of D,
so
that we can compute 
for any given q. Obviously for
we
know that 
.
We then proceed to compute, in an adaptive fashion, a piecewise
polynomial approximation of 
. The zero-contour of this
function will implicitly define the shape of the reconstructed
manifold.
Both steps of the algorithm make use of an incremental 3D
Delaunay
triangulation construction. In the first phase, we compute the
Delaunay triangulation of P. We then extract a
triangulated
two-manifold T (the boundary of what we call an -solid,
see [2]) from it
using a technique inspired by
-shapes [9] and
sculpturing [6].
For a point 
we can now compute its distance from T
and
its sign, so that an approximate function is defined. The
data structures associated with the triangulation and its dual
allow
us to compute the value of efficiently.
We then start the incremental construction of another 3D Delaunay
triangulation, which we will use as the support mesh of our
piecewise
polynomial reconstruction. We begin with a single tetrahedron
containing the region of interest, and compute the 20 weights of
the
associated polynomial patch based on least-squares approximation
of
samples of in its interior. We then introduce a new site,
update the triangulation, and compute the weights of the new
tetrahedra, continuing in this way until the approximation error
becomes smaller than the given 
. At each step, the new
site introduced is the circumcenter of the tetrahedron with the
largest associated approximation error. We also make sure that
the
single-sheetedness constraints are satisfied for each patch.
We build in this way a hierarchy of volume-splines, whose zero-contour converges to the shape of D. Figure 1 shows an example of reconstruction using this algorithm.
