Piecewise smooth surface reconstruction.
We present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface models from scattered range data. The method can be used in a variety of applications such as reverse engineeringthe automatic generation of CAD models from physical objects. Novel aspects of the method are its ability to model surfaces of arbitrary topological type and to recover sharp features such as creases and corners. The method has proven to be effective, as demonstrated by a number of examples using both simulated and real data.A key ingredient in the method, and a principal contribution of this paper, is the introduction of a new class of piecewise smooth surface representations based on subdivision. These surfaces have a number of properties that make  them ideal for use in surface reconstruction: they are simple to implement, they can model sharp features concisely, and they can be fit to scattered range data using an unconstrained optimization procedure.
Introduction
In this paper, we present a new representation for piecewise smooth
surfaces of arbitrary topological type, 1 and a method for fitting such
surface models to scattered range data, where neither the topological
type of the surface, its geometry, nor the location of its sharp
features are known in advance. We also present examples showing
that the surface representation and fitting method are useful for im-
3 Department of Computer Science and Engineering, FR-35
y Department of Mathematics, GN-50
z Apple Computer
x Department of Statistics, GN-22
This work was supported in part by IBM, Silicon Graphics Inc., the
Xerox Corporation, and the National Science Foundation under grants CCR-
8957323 and DMS-9103002.
1 The topological type of a surface refers to its genus, the presence of
boundaries, etc.
portant applications such as reverse engineering - the automatic
generation of CAD models from laser range data.
In previous work [4, 10, 11], we developed a method for fitting
compact, accurate piecewise linear surfaces to scattered range data.
The generalization to piecewise smooth surfaces is a natural and
necessary extension. Many objects of interest are piecewise smooth;
their surfaces consist of smoothly curved regions that meet along
sharp curves and at sharp corners. Modeling such objects as piece-wise
linear surfaces requires a large number of triangles, whereas
curved surface models can provide both a more accurate and a more
compact representation of the true surface. It is critical, however, to
use a surface representation that is capable of explicitly modeling
sharp features. Using an everywhere smooth surface representation
to model sharp features either results in a large number of surface
elements, or in a poor geometric fit, as illustrated in Color Plate 1m.
Additionally, the surface representation should be capable of modeling
surfaces of arbitrary topological type.
The most popular smooth surface representations are tensor product
NURBS. However, NURBS can only represent surfaces of arbitrary
topological type by partitioning the model into a collection
of individual NURBS patches. Adjacent patches must then be explicitly
stitched together using geometric continuity conditions [6].
A large number of parameters (the B-spline coefficients) are therefore
introduced, most of which are constrained by the continuity
conditions. As a consequence, fitting NURBS in general requires
high-dimensional constrained optimization.
Subdivision surfaces, first introduced by Doo/Sabin [5] and Cat-
mull/Clark [3], offer a promising alternative. They are capable of
modeling everywhere smooth surfaces of arbitrary topological type
using a small number of unconstrained parameters.
Our surface representation is a generalization of the subdivision
surface scheme introduced by Loop [13]. Loop's scheme, like all
subdivision schemes to date, produces tangent plane continuous surfaces
of arbitrary topological type. A principal contribution of our
work is to show that it is possible to locally modify Loop's subdivision
rules to model sharp features such as creases and corners. The
modified subdivision rules also model boundary curves, as shown
for instance in the spout of the Utah teapot (Color Plate 2).
Our reconstruction method consists of three major phases, the
first two of which have been described elsewhere:
1. Estimation of topological type [10]: Given an unorganized
set of points (Color Plate 1j) on or near some unknown surface
(Color Plate 1i), phase 1 constructs a triangular mesh consisting of a
relatively large number of triangles (Color Plate 1k). This phase determines
the topological type of the surface and produces an initial
estimate of the geometry.
2. Mesh optimization [4, 11]: Starting with the output of phase
phase 2 reduces the number of triangles and improves the fit to
the data (Color Plate 1l). Our approach to this phase is to cast the
problem as optimization of an energy function that explicitly models
the trade-off between the competing goals of concise representation
and good fit. The free variables in the optimization procedure are
the number of vertices in the mesh, their connectivity, and their positions

3. Piecewise smooth surface optimization: Phase 3 is the subject
of this paper. Starting with the optimized mesh (a piecewise
linear produced in phase 2, this phase fits an accurate, concise
piecewise smooth subdivision surface (Color Plate 1o), again
by optimizing an energy function that trades off conciseness and fit
to the data. The phase 3 optimization varies the number of vertices
in the control mesh, their connectivity, their positions, and the number
and locations of sharp features. The automatic detection and
recovery of sharp features in the surface is an essential part of phase
3. Our piecewise smooth subdivision surface scheme is introduced
in Section 3. The optimization problem and algorithm are described
in Section 4.
Phase 2 can in principle be eliminated, but has proven to be convenient
for two reasons: first, is it computationally more efficient to
optimize over a piecewise linear surface in the early stages of op-
timization, and second, initial estimates of sharp features are much
more robust when obtained from the phase 2 mesh.
The principal evidence for our method's success is its application
to a wide variety of data, including simulated and real laser scanner
data. A number of examples, shown in the Color Plates, are discussed
in Section 5.
2 Background on subdivision surfaces
A subdivision surface is defined by repeatedly refining an initial
control mesh as indicated in Color Plates 1a-1d. (Formally, a mesh
M is a pair (K; V ), where: K is a simplicial complex specifying the
connectivity of the vertices, edges, and faces, and thus determining
the topological type of the mesh;
is a set of vertex positions defining the shape of the mesh in R 3 .)
The first and most popular subdivision surface schemes, introduced
by Doo/Sabin [5] and Catmull/Clark [3], are based on quadrilateral
meshes, and generalize biquadratic and bicubic tensor product
B-splines, respectively. A subdivision scheme based on triangles
is more convenient for our purposes. We use a generalization of
the triangular scheme introduced by Loop [13], as it is the simplest
known scheme leading to tangent plane smooth surfaces.
2.1 Loop's subdivision: Loop's subdivision scheme is a generalization
of C 2 quartic triangular B-splines. The refinement step
proceeds by splitting each triangular face into four subfaces. The
vertices of the refined mesh are then positioned using weighted averages
of the vertices in the unrefined mesh. Formally, starting
with the initial control mesh each subdivision step
carries a mesh M refined mesh M
are computed as affine
combinations of the vertices of V r . Some of the vertices of V r+1
naturally correspond to vertices of V r - these are called vertex
points; the remaining vertices in V r+1 correspond to edges of the
mesh M r - these are called edge points. Let v r denote a vertex
of V r having neighbors v r
n as shown in Figure 1a. Such a
vertex is said to have valence n. Let v r+1
i denote the edge point of
corresponding to the edge v r v r
i , and let v r+1 be the vertex
point of V r+1 associated with v r . The positions of v r+1 and v r+1
are computed according to the subdivision rules
(1)
r
r
vertex mask edge mask31

Figure

1: The neighborhood around a vertex v r of valence n (left);
Loop's vertex mask (center); Loop's edge mask (right).
where subscripts are taken modulo n, and where
with 2. Affine combinations such as
those in Equation 1 can be nicely visualized by diagrams called
masks, as shown in Figure 1.
2.2 Computing surface points and tangent vectors: Loop's
surfaces in particular, and subdivision surfaces in general, are defined
only as the limit of an infinite refinement process. In most
cases closed form expressions for the limit surfaces are not known,
but somewhat surprisingly, various properties of subdivision sur-
faces, such as exact points on the surface and exact tangent planes,
can nonetheless be computed.
To study the properties of subdivision surfaces, it is convenient
to write Equation 1 in matrix form as
(v
where superscript T denotes matrix transpose. The matrix Sn is
called the local subdivision matrix [5].
As r !1, each point v r approachesa point on the limit surface.
Equation 2 suggests that the limit point can be obtained by analyzing
the eigenstructure of the local subdivision matrix. Indeed, the limit
point can be expressed as an affine combination of the initial vertex
positions [8]:
is the dominant left eigenvector of Sn . For
Loop's surfaces this affine combination can be expressed as the position
mask shown in Figure 2 [13].
Eigenanalysis of the local subdivision matrix can also be used
to establish smoothness. It can be shown, for instance, that Loop's
surfaces are indeed tangent plane continuous [13, 19]. Moreover,
Halstead et al. [8] show that the tangent vectors to the limit surface
at v 1 can be computed using the two left eigenvectors of Sn
corresponding to the second largest eigenvalue (this eigenvalue has
multiplicity 2). For Loop's surfaces the vectors
with span the tangent plane of the surface. Their
cross product therefore gives an exact normal vector to the surface
which is useful, for example, to create Phong-shaded renderings
such as those shown in the Color Plates. The formulas given in
Equation 3 can be visualized as the tangent masks shown in Figure
2.
Eigenanalysis will again be used in Section 3.2 to study the properties
of piecewise smooth subdivision surfaces.
c
c
c
c
c43
c c 4tangent masks
position mask

Figure

2: Masks for computing positions and tangents to Loop's
surfaces, where
, and where c
3 Piecewise smooth subdivision surfaces
Fitting smooth surfaces to non-smooth objects often produces unacceptable
results. As an example, fitting an everywhere smooth
subdivision surface to the points in Color Plate 1j produces the surface
shown in Color Plate 1m.
In this section we develop new subdivision rules to accurately
model objects with tangent discontinuities. These subdivision rules
produce commonly occurring sharp features that we call creases,
corners, and darts, as illustrated in Color Plate 1e-h. A crease is a
tangent line smooth curve along which the surface is C 0 but not C
a corner is a point where three or more creases meet; finally, a dart
is an interior point of a surface where a crease terminates. Although
this list of sharp features is not exhaustive (for instance, we cannot
model a cone or two coincident darts), it has proven sufficient for
the examples we have encountered.
Subdivision surfaces produced by the new rules are tangent plane
smooth everywhere except along creases and at corners. A detailed
theoretical analysis of the behavior along creases and at corners is
beyond the scope of this paper and will be presented in subsequent
work. In Section 3.2 we summarize the relevant results of the analysis

3.1 Subdivision rules: To model creases, corners, and darts using
subdivision surfaces, a subset L of edges in the simplicial complex
K is tagged as sharp. We refer to the pair (K;L) as a tagged
simplicial complex. The subdivision masks are modified so that
tangent plane continuity across sharp edges is relaxed. Boundary
curves are produced by tagging all boundary edges of the mesh as
sharp. 2 In the subdivision process, edges created through refinement
of a sharp edge are tagged as sharp.
Subdivision rules at crease vertices must be chosen carefully in
order for the surface on each side of the crease to have a well-defined
tangent plane at each point along the crease. Similar considerations
apply to corners and darts. It should be noted that the specific subdivision
masks we use are by no means unique. Indeed, there is considerable
flexibility in selecting them. The masks we present here
are simple and have worked well in practice, but further research
should be done to explore other alternatives.
We classify vertices into five different types based on the number
and arrangement of incident edges. A smooth vertex is one where
the number of incident sharp edgess is zero; a dart vertex has
a crease vertex has corner vertex has s ? 2. Crease
vertices are further classified as regular and non-regular depending
on the arrangement of smooth edges. An interior crease vertex is
regular if it has valence 6 with exactly two smooth edges on each
side of the crease; a boundary crease vertex is regular if it has valence
4. All other crease vertices, whether interior or boundary, are
non-regular.

Figure

3 shows our vertex and edge subdivision masks. As in-
In related work, Nasri [15, 16] developed a method to model boundary
curves in a Doo-Sabin subdivision procedure by augmenting the control
mesh rather than by modifying the subdivision masks.1
0smooth or
dart vertex
regular or non-regular
crease vertex
corner vertex003151(3) non-regular
crease edge(2) regular
crease edge
(1) smooth edge

Figure

3: Vertex and edge subdivision masks. Double lines denote
sharp edges.
dart reg non-reg corner
crease crease
reg crease 1 2 3 3
non-reg crease 1
corner

Table

1: Assignment of sharp edge subdivision masks as a function
of the types of the two incident vertices. Masks are numbered as
shown in Figure 3.
dicated in the figure, vertex subdivision masks are chosen based on
the type of the vertex.
We use three different types of edge subdivisionmasks. A smooth
edge (one not tagged as sharp) is subdivided using the smooth edge
mask. The mask used to subdivide a sharp edge depends on the
types of the incident vertices as shown in Table 1. When applying
edge subdivision mask 3, the regular crease vertex incident to the
edge receives the weight 5.
Those familiar with B-spline curve subdivision may recognize
that the crease subdivision masks have been designed so that the
sharp edges converge to uniform cubic B-splines except near non-regular
crease and corner vertices. The zeros in the crease subdivision
masks completely decouple the behavior of the surface on one
side of the crease from the behavior on the other side.
3.2 Computing surface points and tangent vectors: As explained
in Section 2.2, limiting points and tangent planes can be
computed using masks. These masks are determined by the eigenstructure
of local subdivision matrices, which depend on the type of
the vertex (smooth, dart, regular and non-regular crease, and cor-
ner).
Smoothanddart vertices: At smoothand dart vertices, our local
subdivision matrix is identical to Loop's matrix. The position and
tangent masks are therefore as in Figure 2.
Crease vertices: Since the zeros in the crease subdivision masks

Figure

decouple the behavior of the surface on one side of the
crease from the behavior on the other side, we can decouple the
analysis, focusing on a local subdivision matrix that describes the
behavior on one side of the crease. As indicated earlier, boundary
curves are modeled as one-sided creases.
position masks tangent masks1400
along crease across crease
non-regular crease
regular crease
(a) (b) (d)
(c)

Figure

4: Position and tangent masks for crease vertices.
In the following, we assume that the vertices v 0
surrounding
one side of a crease vertex v 0 of valence n are indexed as shown
in

Figure

4d.
At a regular crease vertex, the dominant left eigenvector of the local
subdivision matrix yields the position mask shown in Figure 4a,
meaning that
is a point on the limit crease. Similarly, when the crease vertex is
non-regular, we obtain the position mask shown in Figure 4b.
For crease vertices of valence 4 or higher, the subdivision rules
described in the previous section give rise to well-defined tangent
planes on both sides of the crease. 3 As for smooth vertices, tangent
masks are again determined by the two left eigenvectors corresponding
to the 2nd and 3rd largest eigenvalues. For both regular
and non-regular crease vertices, a tangent along the crease
is obtained by the tangent mask shown in Figure 4c. To compute
a tangent vector transverse to the crease, we use the tangent
mask shown in Figure 4d, where the weights are defined as fol-
lows. At a regular crease vertex, the valence is 4 and the mask
is given by (w0 ; :::; At a non-regular
crease vertex, for n - 4, sin ', and
finally,
Corner vertices: The subdivision masks at a corner vertex are
much like those at a crease vertex. If the corner vertex has s sharp
edges, the local subdivision matrix decouples into s separate matrices
(or s 0 1 matrices if the corner vertex lies on a boundary),
each describing a smooth region of the surface. Since the corner
vertex does not move during subdivision, it is itself a point on
the surface (equivalently, (1; 0; :::; 0) is the dominant left eigenvec-
tor). The tangent masks in this case reduce to simple differences:
Fitting piecewise smooth subdivision surfaces
In this section, we describe an algorithm for phase 3 of the reconstruction
problem as outlined in Section 1.
The input to phase 3 is an unstructured collection
xng of data points scattered in three dimensions, together
with the mesh obtained from phase 2. Edges are initially tagged as
sharp if the dihedral angle of the faces incident to the edge is above
a threshold (e.g. 40 degrees). The output of phase 3 is a concise
piecewise smooth surface that accurately fits the data.
As in phase 2 (mesh optimization), we cast the problem as one of
minimizing an energy function that captures the competing goals of
conciseness and accuracy.
3 The techniques we use to prove smoothness do not apply to vertices of
valence 2 and 3, althoughnumerical experiments suggest that tangent planes
are well-defined in these cases, too.
4.1 Definition of the energy function: The energy function is
given by
where Edist is the total squared distance from the data points to the
subdivision surface; crepm is a penalty on the number m of vertices;
and csharpe is a penalty on the number e of sharp edges.
The parameter crep controls the trade-off between conciseness
and fidelity to the data and should be set by the user. The parameter
csharp controls the tradeoff between smoothness of the surface and
fidelity to the data. Setting worked well in all
our examples.
We minimize the energy function over the space M of tagged
meshes is of the same topological type
as the phase 2 mesh, and L is the subset of sharp edges of K . The
goal is to find the tagged mesh in M that minimizes E.
The reader familiar with Hoppe et al. [11] will notice the absence
of a "spring energy" term, which was introduced to guide the mesh
optimization algorithm into a good local energy well. For the type
of examples shown in the Color Plates, that energy term has been
unnecessary in phase 3.
4.2 Minimization: Our algorithm for energy minimization
closely parallels the one presented in Hoppe et al. [11]. We decompose
the problem into two nested subproblems: an inner, continuous
optimization over the control vertex positions V for fixed (K;L),
and an outer, discrete optimization over (K;L).
4.2.1 Optimization over V for fixed (K;L): We want to determin

the minimum energy for fixed (K;L). Since m and e are fixed,
this is equivalent to minimizing the distance energy over the vertex
positions V . In the following, V is treated as an m23 matrix whose
rows contain the (x; coordinates of the vertices.
Computing the distance energy Edist involves projecting the data
points x i onto the subdivision surface S. This is not feasible in
practice as the surface is defined only as the limit of an infinite pro-
cess. Instead, we project onto a piecewise linear approximation ~
to S obtained by subdividing the original mesh r times to produce
a refined mesh M r , then pushing all the vertices of M r to their
limit positions using the position masks. (Typically we use
Since each of the vertices of M r can be written as an affine combination
of the vertices V of M (using the subdivision rules), and
since the limit position of any vertex can be obtained using the position
masks, each of the vertices of ~
S can be written as an affine
combination of the vertices V . That is, each vertex ~
v of ~
S can be
written as ~
where the entries of the row vector y can be
computed by combining the effects of r-fold subdivision followed
by application of a position mask. Moreover, since ~
S is piecewise
linear, every point on ~
S - not just the vertices - can be written as
an affine combination of the vertices V .
For each data point x i , let w i be the closest point on ~
S . As argued
above, w i can be written as y i V , meaning that Edist can be
expressed as
This expression for Edist is quadratic in V . Hence, for fixed y i ,
optimizing over V is a linear least-squares problem. Moreover, the
vectors y i are sparse since the subdivision rules are local.
This suggests an iterative minimization scheme alternating between
the following steps:
edge collapse edge tag
edge split edge swap
initial configuration

Figure

5: Elementary mesh transformations.
1. For fixed V , compute the projections y i V of the data points
S .
2. For fixed Edist over V .
Step 2, which is a sparse linear least squares problem, can be solved
as described in [11].
4.2.2 Optimization over (K;L): Our algorithm for solving the
outer minimization problem, minimizing E(K;L), again closely
parallels the algorithm of [11].
We define a set of four elementary mesh transformations, edge
collapse, edge swap, edge split, and edge tag, taking a tagged
simplicial complex (K;L) to another tagged simplicial complex
shown in Figure 5. The first three transformations are
discussed in [11]. The fourth transformation, edge tag, is a toggle
that either adds an edge to the set L of sharp edges, or removes one
from it. These four transformations are complete in the sense that
they form a transitive set of transformations on the set of tagged
simplicial complexes (of a given topological type).
A legal move is the application of one of these elementary transformations
to an edge of K that leaves the topological type of K
unchanged. The criterion for determining whether a move is legal
is given in [11]. Our goal is to find a sequence of legal moves taking
us from an initial tagged simplicial complex (K0 ; L0 ) to one for
which a minimum of E is achieved.
This is accomplished via a variant of random descent: We form
a candidate set, initially consisting of all edges of K . We randomly
select an edge from the candidate set and try the four elementary
transformations in turn until we find a legal move (K;L) )
E(K;L). If none is found, we remove
the edge from the candidate set; otherwise, we accept the move and
expand the candidate set to include edges whose vertices were affected
by the transformation. The process is repeated until the candidate
set is empty.
Due to the expense of computing E(K speculative
move, the idealized algorithm just described is too inefficient
to be of practical use. We therefore replace the exact computation
of E(K by an approximate one.
Our approximate computation of E is based on the observation
that the effect of an elementary transformation on the geometry of
the subdivision surface is localized to a neighborhood of the affected
edge. Thus, when speculating upon an elementary transformation,
we only optimize over the positions of control vertices in a neighborhood
of the affected edge, and recompute projections of data points
originally projecting onto the neighborhood of ~
S supported by these
control vertices. For details, see [9, 12].
The main motivation for moving from piecewise linear to piecewise
smooth surfaces is to obtain more accurate and concise models of
point sets. The last row of Color Plate 1 and the first 2 rows of
Color Plate 2 show results of our experiments with range data. The
leftmost column shows the original point sets; the second column
shows the optimized piecewise linear surfaces obtained from phase
(mesh optimization); the third column shows the optimized tagged
meshes resulting from phase 3 (subdivision surface optimization),
with sharp edges L highlighted in yellow; finally, the rightmost column
shows the subdivision surfaces associated with these control
meshes. Modeling surfaces such as the one shown in Color Plate 1t
using NURBS would be very cumbersome and would likely require
significant user intervention. In contrast, our subdivision surface
approach is both simple and automatic.
Our method can also be used for the approximation of known sur-
faces. To this end, we first generate a set of points on the surface to
be approximated, and then run the three phases of the reconstruction
procedure. The lower three rows of Color Plate 2 show the resulting
approximations of a dense triangular mesh, a swept surface, and
a NURBS surface. Since the NURBS teapot was defined as a set
of mutually intersecting patches, we had to manually remove some
of the sample points. Note how this teapot is modeled as a single
subdivision surface of genus 1 (the handle of the teapot makes it
homeomorphic to a torus), without resort to explicit continuity constraints
or trimming curves.
Another advantage of optimizing using a piecewise smooth
model is that the resulting surface not only fits the data more accurately
than a piecewise linear model, but also is a better predictor
of the true underlying surface. As a validation, we sampled a different
set of 10,000 points from the swept surface (knot). As shown
in

Table

2, even though the subdivision control mesh has a fifth as
many vertices as the mesh from phase 2, the subdivision surface fits
the new set of points with one fourth the distance energy.
dist
vertices original points new points
phase

Table

2: Validation results
Color dist Time
Plate ph2 ph3 ph2 ph3 ph2
ph3 ph2 ph3 ph2
ph3 hrs
04 3.2 0.9
1.2 7.7
1.6 2.8
1.1 4.1
2.3
2.2
1.3 2.2
1.2 5.3

Table

3: Parameter settings and optimization results
In most examples, the representation constant crep was set to
the same value that was used in phase 2. As indicated in

Table

3, the control meshes obtained from phase 3 are more concise
than those of phase 2, and at the same time, the subdivision
surfaces fit the points more accurately than the triangular meshes
of phase 2. Because the point sets for the swept surface and the
NURBS teapot are sampled without error from piecewise smooth
surfaces, we could afford to raise crep in order to produce very concise
control meshes, while still reducing Edist .
The phase 3 execution times listed in Table 3 were obtained
on a DEC Alpha workstation. In all test cases we set
crep=5 and the number of subdivision iterations (referred to in Section
4.2.1) to 2.
6 Related work
There is a large body of literature on reconstructing surfaces of fixed
topological type. Bolle and Vemuri [1] review methods for fitting
embeddings of a rectangular domain. Schudy and Ballard [22, 23],
Brinkley [2], and Sclaroff and Pentland [24] fit embeddings of a
sphere. Schmitt et al. [20, 21] fit embeddings of a cylinder to data
from cylindrical range scans. Goshtasby [7] works with embeddings
of cylinders and tori.
There is also extensive literature on smooth interpolation of triangulated
data of arbitrary topological type using parametric surface
patches; see Lounsbery et al. [14] for a survey. These schemes are
designed to interpolate sparse data, rather than to fit dense, noisy
point sets of the type obtained from range scanners.
Two recent articles describing methods for fitting either piece-wise
linear or everywhere smooth surfaces of arbitrary topological
type are Veltkamp [27] and Szeliski et al. [26].
We are not aware of any previous method for fitting piecewise
smooth surface models of arbitrary topological type to dense, noisy
data, although one could imagine developing such a procedure
based on a piecewise smooth triangular patch method such as Niel-
son's side-vertex patch [17], or Shirman and S-equin's split domain
scheme [25].
In many respects, our work can be considered a generalization
to surfaces of the parametric curve fitting method of Plass and
Stone [18]: they cast the fitting process as non-linear optimization,
and they also produce piecewise smooth, rather than everywhere
smooth models.
7 Summary and future work
We have described a piecewise smooth surface reconstruction procedure
that produces concise and accurate surface models from unorganized
points. Our method automatically determines the topological
type of the surface, and the presence and location of sharp
features. A key ingredient of the method is a new subdivision surface
scheme that allows the modeling of surface features such as
corners, boundaries, creases, and darts. Finally, we have demonstrated
the effectiveness of the subdivision surface optimization procedure
in recovering piecewise smooth models from range data, and
in approximating other surface forms such as swept surfaces and
NURBS.
There are a number of areas for future research, including:
1. Development of subdivision rules that can model a wider variety
of sharp features such as cones, multiple darts meeting at
a smooth vertex, and darts meeting at a corner.
2. Development of alternative optimization algorithms that allow
direct control over maximum error.
3. Speedup of the algorithm and implementations on parallel architectures

4. Development of an on-line algorithm for use in real-time data
capture.
5. Experimentation with sparse, non-uniform data.

Acknowledgments

We wish to thank the Ford Motor Co. for providing
the cross section data, Technical Arts Co. for the laser range
data, Rob Sharein for the swept surface, and Pratt & Whitney for
the dense tessellation of the gas turbine engine component.



--R

On three-dimensional surface reconstructionmethods

Recursively generated B-spline surfaces on arbitrary topological meshes
Fitting of surfaces to scattered data.
Behaviour of recursive division surfaces near extraordinary points.
Curves and Surfaces for Computer Aided Geometric Design.
Surface reconstruction from scattered measure- ments
Efficient, fair interpolation using Catmull-Clark surfaces

Surface reconstruction from unorganized points.
Mesh optimization.
Surface reconstruction from unorganized points.
Smooth subdivision surfaces based on triangles.
Parametric surface interpolation.
Polyhedral subdivision methods for free-form sur- faces

A transfinite

A unified approach to subdivision algorithms.
An adaptive subdivision method for surface fitting from sampled data.
Adaptive G 1 approximation of range data using triangular patches.
Model detection of cardiac chambers in ultrasound images.
Towards an anatomical model of heart motion as seen in 4-d cardiac ultrasound data
Generalized implicit functions for computer graphics.
Local surface interpolation with B-ezier patches
Modeling surfaces of arbitrary topologywith dynamic particles.
3D computational morphology.
--TR
An adaptive subdivision method for surface-fitting from sampled data
Polyhedral subdivision methods for free-form surfaces
On Three-Dimensional Surface Reconstruction Methods
Adaptive G<supscrpt>1</supscrpt> approximation of range data using triangular patches
Generalized implicit functions for computer graphics
Boundary-corner control in recursive-subdivision surfaces
Surface reconstruction from unorganized points
Curves and surfaces for computer aided geometric design (3rd ed.)
Mesh optimization
Efficient, fair interpolation using Catmull-Clark surfaces
Surface reconstruction from unorganized points
Parametric Surface Interpolation
Curve-fitting with piecewise parametric cubics

--CTR
Kerstin Mller , Lars Reusche , Dieter Fellner, Extended subdivision surfaces: Building a bridge between NURBS and Catmull-Clark surfaces, ACM Transactions on Graphics (TOG), v.25 n.2, p.268-292, April 2006
Xinguo Liu , Hujun Bao , Heung-Yeung Shum , Qunsheng Peng, A novel volume constrained smoothing method for meshes, Graphical Models, v.64 n.3/4, p.169-182, May/July 2002
Takeo Igarashi , John F. Hughes, Smooth meshes for sketch-based freeform modeling, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
S. Schaefer , J. Hakenberg , J. Warren, Smooth subdivision of tetrahedral meshes, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Takeo Igarashi , John F. Hughes, Smooth meshes for sketch-based freeform modeling, Proceedings of the symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California
Daniel Freedman, An incremental algorithm for reconstruction of surfaces of arbitrary codimension, Computational Geometry: Theory and Applications, v.36 n.2, p.106-116, February, 2007
D. Rypl , Z. Bittnar, Triangulation of 3D surfaces: from parametric to discrete surfaces, Proceedings of the third international conference on Engineering computational technology, p.33-34, September 04-06, 2002, Stirling, Scotland
Jorg Peters, Smooth patching of refined triangulations, ACM Transactions on Graphics (TOG), v.20 n.1, p.1-9, Jan. 2001
Ye Duan , Hong Qin, Intelligent balloon: a subdivision-based deformable model for surface reconstruction of arbitrary topology, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.47-58, May 2001, Ann Arbor, Michigan, United States
Hong Qin , Chhandomay Mandal , Baba C. Vemuri, Dynamic Catmull-Clark Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.4 n.3, p.215-229, July 1998
Weiyin Ma , Xiaohu Ma , Shiu-Kit Tso, A new and direct approach for loop subdivision surface fitting, Geometric modeling: techniques, applications, systems and tools, Kluwer Academic Publishers, Norwell, MA, 2004
Chhandomay Mandal , Hong Qin , Baba C. Vemuri, Dynamic Modeling of Butterfly Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.6 n.3, p.265-287, July 2000
Dvir Steiner , Anath Fischer, Cutting 3D freeform objects with genus-n into single boundary surfaces using topological graphs, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Peter Rander , P. J. Narayanan , Takeo Kanade, Virtual
ized
Guillaume Lavou , Florence Denis , Florent Dupont, Technical Section: Subdivision surface watermarking, Computers and Graphics, v.31 n.3, p.480-492, June, 2007
Jan Neumann , Yiannis Aloimonos, Spatio-Temporal Stereo Using Multi-Resolution Subdivision Surfaces, International Journal of Computer Vision, v.47 n.1-3, p.181-193, April-June 2002
Bill Baxter , Vincent Scheib , Ming C. Lin , Dinesh Manocha, DAB: interactive haptic painting with 3D virtual brushes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.461-468, August 2001
Kai Hormann , Ulf Labsik , Martin Meister , Gunther Greiner, Hierarchical extraction of iso-surfaces with semi-regular meshes, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Michal Varnuska , Ivana Kolingerova, Improvements to surface reconstruction by the CRUST algorithm, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia
Kevin T. McDonnell , Hong Qin , Robert A. Wlodarczyk, Virtual clay: a real-time sculpting system with haptic toolkits, Proceedings of the 2001 symposium on Interactive 3D graphics, p.179-190, March 2001
Bill Baxter , Vincent Scheib , Ming C. Lin , Dinesh Manocha, DAB: interactive haptic painting with 3D virtual brushes, ACM SIGGRAPH 2005 Courses, July 31-August
Zhangjin Huang , Guoping Wang, Distance between a Catmull-Clark subdivision surface and its limit mesh, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
Lee Markosian , Michael A. Kowalski , Daniel Goldstein , Samuel J. Trychin , John F. Hughes , Lubomir D. Bourdev, Real-time nonphotorealistic rendering, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.415-420, August 1997
Jing Ren, Towards a smooth scattered data reconstruction with sharp features, Proceedings of the 37th annual Southeast regional conference (CD-ROM), p.33-es, April 1999
Henning Biermann , Adi Levin , Denis Zorin, Piecewise smooth subdivision surfaces with normal control, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.113-120, July 2000
Daniel Freedman, Efficient Simplicial Reconstructions of Manifolds from Their Samples, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1349-1357, October 2002
Takashi Maekawa , Yasunori Matsumoto , Ken Namiki, Interpolation by geometric algorithm, Computer-Aided Design, v.39 n.4, p.313-323, April, 2007
Lee Markosian , Jonathan M. Cohen , Thomas Crulli , John Hughes, Skin: a constructive approach to modeling free-form shapes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.393-400, July 1999
Won-Ki Jeong , Chang-Hun Kim, Direct reconstruction of a displaced subdivision surface from unorganized points, Graphical Models, v.64 n.2, p.78-93, March 2002
Chhandomay Mandal , Hong Qin , Baba C. Vemuri, A novel FEM-based dynamic framework for subdivision surfaces, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.191-202, June 08-11, 1999, Ann Arbor, Michigan, United States
Henning Biermann , Ioana M. Martin , Denis Zorin , Fausto Bernardini, Sharp features on multiresolution subdivision surfaces, Graphical Models, v.64 n.2, p.61-77, March 2002
Gerald Dalley , Patrick Flynn, Pair-wise range image registration: a study in outlier classification, Computer Vision and Image Understanding, v.87 n.1-3, p.104-115, July 2002
Yu-Sung Chang , Hong Qin, A framework for multi-dimensional adaptive subdivision objects, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
Hui Xie , Jianning Wang , Jing Hua , Hong Qin , Arie Kaufman, Piecewise C1 Continuous Surface Reconstruction of Noisy Point Clouds via Local Implicit Quadric Regression, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.13, October 22-24,
Matthias Eck , Hugues Hoppe, Automatic reconstruction of B-spline surfaces of arbitrary topological type, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.325-334, August 1996
Martin Marinov , Leif Kobbelt, Optimization methods for scattered data approximation with subdivision surfaces, Graphical Models, v.67 n.5, p.452-473, September 2005
Andrei Khodakovsky , Peter Schrder, Fine level feature editing for subdivision surfaces, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.203-211, June 08-11, 1999, Ann Arbor, Michigan, United States
Guiqing Li , Weiyin Ma, Interpolatory ternary subdivision surfaces, Computer Aided Geometric Design, v.23 n.1, p.45-77, January 2005
Seth Green , George Turkiyyah , Duane Storti, Subdivision-based multilevel methods for large scale engineering simulation of thin shells, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996
Denis Zorin , Peter Schrder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996
Leif Kobbelt, 3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000
Dimitris Metaxas , Eunyoung Koh , Norman I. Badler, Multi-Level Shape Representation Using Global Deformations andLocally Adaptive Finite Elements, International Journal of Computer Vision, v.25 n.1, p.49-61, Oct. 1997
Hui Xie , Kevin T. McDonnell , Hong Qin, Surface Reconstruction of Noisy and Defective Data Sets, Proceedings of the conference on Visualization '04, p.259-266, October 10-15, 2004
M. Marinov , L. Kobbelt, Optimization techniques for approximation with subdivision surfaces, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996
Thomas W. Sederberg , Jianmin Zheng , David Sewell , Malcolm Sabin, Non-uniform recursive subdivision surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.387-394, July 1998
J. Barhak , A. Fischer, Parameterization and Reconstruction from 3D Scattered Points Based on Neural Network and PDE Techniques, IEEE Transactions on Visualization and Computer Graphics, v.7 n.1, p.1-16, January 2001
Rene Berndt , Dieter W. Fellner , Sven Havemann, Generative 3D models: a key to more information within less bandwidth at higher quality, Proceedings of the tenth international conference on 3D Web technology, March 29-April 01, 2005, Bangor, United Kingdom
Wenping Wang , Helmut Pottmann , Yang Liu, Fitting B-spline curves to point clouds by curvature-based squared distance minimization, ACM Transactions on Graphics (TOG), v.25 n.2, p.214-238, April 2006
Mark A. Halstead , Brain A. Barsky , Stanley A. Klein , Robert B. Mandell, Reconstructing curved surfaces from specular reflection patterns using spline surface fitting of normals, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.335-342, August 1996
Martin Bertram, Biorthogonal wavelets for subdivision volumes, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Denis Zorin , Peter Schrder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997
Ye Duan , Hong Qin, A subdivision-based deformable model for surface reconstruction of unknown topology, Graphical Models, v.66 n.4, p.181-202, July 2004
Henrik Weimer , Joe Warren, Subdivision schemes for fluid flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.111-120, July 1999
Mark Foskey , Miguel A. Otaduy , Ming C. Lin, ArtNova: touch-enabled 3D model design, ACM SIGGRAPH 2005 Courses, July 31-August
Aaron W. F. Lee , Wim Sweldens , Peter Schrder , Lawrence Cowsar , David Dobkin, MAPS: multiresolution adaptive parameterization of surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.95-104, July 1998
Chandrajit L. Bajaj , Guoliang Xu , Robert J. Holt , Arun N. Netravali, Hierarchical multiresolution reconstruction of shell surfaces, Computer Aided Geometric Design, v.19 n.2, p.89-112, February 2002
Daniel Freedman, Combinatorial curve reconstruction in Hilbert spaces: a new sampling theory and an old result revisited, Computational Geometry: Theory and Applications, v.23 n.2, p.227-241, September 2002
Claus-Peter Alberts, Surface reconstruction from scan paths, Future Generation Computer Systems, v.20 n.8, p.1285-1298, November 2004
Herv Delingette, General Object Reconstruction Based on Simplex Meshes, International Journal of Computer Vision, v.32 n.2, p.111-146, Aug. 1999
U. Diewald , S. Morigi , M. Rumpf, A cascadic geometric filtering approach to subdivision, Computer Aided Geometric Design, v.19 n.9, p.675-694, December 2002
Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999
Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
Dinesh K. Pai , Kees van den Doel , Doug L. James , Jochen Lang , John E. Lloyd , Joshua L. Richmond , Som H. Yau, Scanning physical interaction behavior of 3D objects, ACM SIGGRAPH 2005 Courses, July 31-August
Dinesh K. Pai , Kees van den Doel , Doug L. James , Jochen Lang , John E. Lloyd , Joshua L. Richmond , Som H. Yau, Scanning physical interaction behavior of 3D objects, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.87-96, August 2001
Shachar Fleishman , Daniel Cohen-Or , Cludio T. Silva, Robust moving least-squares fitting with sharp features, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
F. Dong , G. J. Clapworthy, Muscle modeling and rendering, Geometric modeling: techniques, applications, systems and tools, Kluwer Academic Publishers, Norwell, MA, 2004
M. Gopi , D. Manocha, A unified approach for simplifying polygonal and spline models, Proceedings of the conference on Visualization '98, p.271-278, October 18-23, 1998, Research Triangle Park, North Carolina, United States
Igor Guskov , Andrei Khodakovsky , Peter Schrder , Wim Sweldens, Hybrid meshes: multiresolution using regular and irregular refinement, Proceedings of the eighteenth annual symposium on Computational geometry, p.264-272, June 05-07, 2002, Barcelona, Spain
Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001
Jean-Daniel Boissonnat , Frdric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
Martin Bertram , Mark A. Duchaineau , Bernd Hamann , Kenneth I. Joy, Bicubic subdivision-surface wavelets for large-scale isosurface representation and visualization, Proceedings of the conference on Visualization '00, p.389-396, October 2000, Salt Lake City, Utah, United States
Aaron Hertzmann , Denis Zorin, Illustrating smooth surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.517-526, July 2000
Guiqing , Li Hua, Blending parametric patches with subdivision surfaces, Journal of Computer Science and Technology, v.17 n.4, p.498-506, July 2002
Chandrajit L. Bajaj , Guoliang Xu, Anisotropic diffusion of surfaces and functions on surfaces, ACM Transactions on Graphics (TOG), v.22 n.1, p.4-32, January
Aaron Lee , Henry Moreton , Hugues Hoppe, Displaced subdivision surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.85-94, July 2000
Gabriel Peyr , Stphane Mallat, Surface compression with geometric bandelets, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January
Zo J. Wood , Peter Schrder , David Breen , Mathieu Desbrun, Semi-regular mesh extraction from volumes, Proceedings of the conference on Visualization '00, p.275-282, October 2000, Salt Lake City, Utah, United States
Michael Lee , Hanan Samet, Navigating through triangle meshes implemented as linear quadtrees, ACM Transactions on Graphics (TOG), v.19 n.2, p.79-121, April 2000
Anders Adamson , Marc Alexa, Point-sampled cell complexes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States
Marco Attene , Bianca Falcidieno , Jarek Rossignac , Michela Spagnuolo, Sharpen&Bend: Recovering Curved Sharp Edges in Triangle Meshes Produced by Feature-Insensitive Sampling, IEEE Transactions on Visualization and Computer Graphics, v.11 n.2, p.181-192, March 2005
Jrg Haber , Frank Zeilfelder , Oleg Davydov , Hans Peter Seidel, Smooth approximation and rendering of large scattered data sets, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
Anders Adamson , Marc Alexa, Approximating and intersecting surfaces from points, Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
F. Dong , G. J. Clapworthy , M. A. Krokos , J. Yao, An Anatomy-Based Approach to Human Muscle Modeling and Deformation, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.154-170, April 2002
Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997
Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995
Marcos Rodrigues , Robert Fisher , Yonghuai Liu, Special issue on registration and fusion of range images, Computer Vision and Image Understanding, v.87 n.1-3, p.1-7, July 2002
Denis Zorin, Modeling with multiresolution subdivision surfaces, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
Sandra Baldassarri , Diego Gutierrez Perez , Francisco Seron Arbeloa, Modelling objects with changing shapes: a survey, Machine Graphics & Vision International Journal, v.11 n.4, p.399-430, 2002
Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
subdivision surfaces;surface fitting;shape recovery;geometric modeling;range data analysis