Title: Cocone algorithm and its variants for surface reconstruction
The Cocone algorithm is a Voronoi based method for surface reconstruction which has geometric and topological guarantees for the output surface given that the input point sample is sufficiently dense. It draws upon the concepts introduced by the Crust algorithm while simplifying both its proof and the method. The Cocone algorithm has been extended to handle surfaces with boundaries, to handle large data sets and to produce water-tight surfaces. All these algorithms have been implemented and tested on various data sets. In this talk I shall present the overviews of the Cocone algorithm and its variants and show our results.
Ye Duan and Hong Qin, State University of New York at Stony Brook
Title: 2.5D Active Surface for Surface Reconstruction
In this paper, we present a new deformable model --- 2.5D Active Surface --- that is capable of directly extracting shape geometry from 3D unorganized point clouds datasets. The reconstructed surfaces are either open or closed. Furthermore, the new model can reconstruct and discover non-manifold geometry hidden in the point-cloud dataset. Our algorithm starts from a simple seed (e.g. a triangle) that can be automatically initialized, and always enlarges the model boundary outwards along its tangent direction suggested by the underlying dataset. This mechanism ensures that our novel models "flow" directly over the data boundary through the expansion of its bounding contour. To maintain the regularity of the model and the stability of the numerical integration process, commonly used mesh optimization techniques are employed throughout the deformation process. In addition, the new model can recover fine details of the underlying shape through local/adaptive refinement. We demonstrate both the accuracy and the robustness of our algorithm through a number of experiments on both real and synthetic datasets.
Yates Fletcher, Geomagic.com
Most commercial scanners acquire their data from a sequence of "shots" during which the scanner and the object are fixed but between which one or the other is moved in order to achieve full coverage of the surface. As a consequence, the raw data from these scans all lie in different coordinate systems and require some computational process to accurately place them in a single coordinate system before further processing can proceed. This is known as the registration problem for multiple partial scans, and a robust solution to this problem is one the keys to engineering reliable optical scanning systems for inspection, metrology, and reverse engineering applications. Current methods rely on heuristics that often break down when the number of scans is large, and tend to be quite slow to converge.
We define a merge as a solution to the registration problem for an arbitrary subset of the scans, and describe merge implementations in terms of ICP alignments of scan pairs. A full registration can now be specified by a tree whose nodes represent the merge of their children. The leaves of this "merge" tree are the individual scans and the root is the completed registration. If it is binary the tree describes a schedule of pair alignments yielding the registration. At the other extreme a depth one tree represents a global merge of all the scans. Each merge contains the possibility of alignment errors that may affect the accuracy of the parent merge and so propogate up the tree. As the degree of the nodes increases we can expect the depth of the tree to decrease, thus minimizing these cumulative effects. On the other hand, when the merge involves more than two scans we expect an increase in complexity and a decrease in stability of the calculations as the number of scans in the merge increases. The merge tree regime allows us to consider schedules which balance these considerations.
We consider the problem of constructing a merge tree from information provided by a graph whose nodes are the scans and whose edges are weighted by an a priori estimate of the registration potential of the corresponding pair. We introduce the notions of overlap strength and lockability to specify registration potential.
Outline
- preliminaries
- - ICP algorithm for congruent pair alignment
- - assumption of approximate registration
- constructing the graph
- - weighting the edges
- (the "registration potential" of a scan pair)
- - overlap
- - lockability
- - pruning
- - two-connected graphs
- - bottleneck spanning graphs
- constructing a schedule
- - merging sub-collections
- (the implementation of simultaneous registration)
- - weighted lockability
- a practical example (alignment of the "water passage" part)
- recap and conclusions
Herbert Edelsbrunner, Arts and Sciences Professor of Computer Science and Mathematics, Duke University
Title: The Importance of Topology in Surface Reconstruction
The original Wrap algorithm for surface reconstruction is based on discrete counterparts of Morse theoretic ideas. This talk presents both the intuition derived from the smooth category and the translation of that intuition into the combinatorial framework expressed by the Voronoi and Delaunay diagrams of the data. By the end of the talk we will have given an effective algorithm whose result is defined by a rather simple mathematical formalism.
Daniel Freedman, Assistant Professor of Computer Science Rensselaer Polytechnic Institute
Title: Surface and Manifold Reconstruction in Arbitrary Embedding Spaces
A new algorithm for combinatorial surface reconstruction is presented. This algorithm's novelty derives from two sources. First, it may be applied to surfaces embedded in arbitrary dimensional Hilbert spaces; this allows for the application of the algorithm to a wider variety of surfaces, including the class of non-orientable surfaces (such as the Klein Bottle). Second, the algorithm may be generalized to the case reconstruction of manifolds, of arbitrary dimension and codimension. An incremental technique is used to reconstruct the surface / manifold; as a result, the algorithm's complexity, as a function of the number of simplices, is independent of the dimension of the manifold or embedding space.
Ping Fu, CEO and President of Raindrop Geomagic
Title: Surface Reconstruction in Commercial Software
This talk presents the landscape of commercial software that uses and benefits from the latest surface reconstruction research. Based on applications in various industries, it illustrates the different requirements, such as software speed, accuracy of reconstruction, degree of automation, and reliability of implicit or explicit feature recognition. The talk concludes with some challenging problems that need further research.
Joachim Giesen, Matthias John
Title: Surface Reconstruction based on a dynamical system
We present an efficient algorithm that computes a manifold
triangular mesh from a set of unorganized sample points in
$\mathbb{R}^3$. The algorithm builds on the observation made
by several researchers that the Gabriel graph of the sample
points provides a good surface description. However, this
surface description is only one-dimensional. We associate
the edges of the Gabriel graph with index 1 critical points
of a dynamical system induced by the sample points. Exploiting
also the information contained in the critical points of index
2 provides a two-dimensional surface description which can
be easily turned into a manifold.
Title: Tight Cocone : A Water-tight Surface Reconstructor
Surface reconstruction from unorganized sample points is an important
problem
in computer graphics, computer aided design, medical imaging and
solid modeling. Recently a few algorithms have been developed that
have theoretical guarantee of computing a topologically correct and
geometrically close surface under certain condition on sampling density.
Unfortunately, this sampling condition is not always met in practice due
to noise, non-smoothness or simply due to inadequate sampling.
This leads to undesired holes and other artifacts in the output
surface. Certain CAD applications such as creating a prototype
from a model boundary require a water-tight surface, i.e., no hole
should be allowed in the surface. In this paper we describe a simple
algorithm
called Tight Cocone that works on an initial mesh generated by
a popular surface reconstruction algorithm and fills up all holes to
output
a water-tight surface. In doing so, it does not introduce any extra
points and produces a triangulated surface interpolating the input
sample points. In support of our method we present
experimental results with a number of difficult data sets.
Michael E. Henderson, IBM
Title: Using Power Diagrams to Compute Implicitly Defined Surfaces
I will describe an algorithm for computing implicitly defined surfaces. These are surfaces defined by an equation F(u)=0, with u in IR^n and F in IR^{n-k}. (When n=3 and k=2 this is the isosurface extraction problem.) The Implicit Function Theorem states that when the Jacobian F_u(u_0) is full rank, solutions near u_0 are a k-dimensional manifold, and typically implicitly defined surfaces are made of pieces of k-dimensional manifolds, which cross along (k-1)-dimensional curves. In applications from engineering and physics n can be quite large.
There have been several attempts to develop practical algorithms for solving these problems. The marching cubes algorithm for computing isosurfaces is probably the most familiar. Analogues of Marching Cubes exist for higher n and k (they are called Piecewise-Linear Methods, see Allgower&Georg's survey paper). However, when n is larger than about 6 the volume of space, and the combinatorics of n-dimensional simplices, makes these approaches impractical.
An alternative approach is to put a mesh on the surface, and advance the boundary of the mesh. This works well when k=1, where it is called Path Following. Initial efforts to extend the technique to higher k have always had to confront the fact that advancing a front is a difficult mesh generation problem (focusing, selfintersection, ...).
If instead of a mesh (a tiling) we use a covering (a set of overlapping neighborhoods) the difficult operation of extending the mesh is replaced by the problem of finding a point on the boundary of the covered bit of the surface. Finding and adding a neighborhood of the boundary point to the covering is easy. If the neighborhoods covering the surface are spherical balls (or spherical balls in the tangent space of the surface), a modification of the power diagram offers a simple way of finding a point on the boundary. The surface is represented as a list of balls in the tangent space at a set of points on the surface (a radius, a point and k tangent vectors). Each ball is associated with a finite, convex polyhedron. If the polyhedron has a vertex whose radius is larger than that of the ball, the ball is on the boundary of the covered bit of the surface, and a point on the boundary can be easily found using a vertex of the polyhedron that is outside the ball.
The resulting algorithm is very robust, since it only requires that the new point be near the boundary to progress. It does not rely on maintaining a mesh on the surface, instead the polyhedra are an approximation to the part of the power diagram interior to the covered region. I will give some simple geometrical examples, including the sphere, torus, and the interior of a cube, as well as some examples from dynamical systems -- periodic motions of coupled pendula, configurations of twisted rods, and invariant manifolds in the Lorenz system.
Thouis Jones, MIT LCS Graphics Group
Title: Non-Iterative, Feature-Preserving Mesh Smoothing Thouis R. Jones, Frédo Durand, Mathieu Desbrun With the increasing use of geometry scanners to create 3D models,
there is a rising need for fast and robust mesh smoothing to remove
inevitable noise in the measurements. While most previous work has
favored diffusion-based iterative techniques for feature-preserving
smoothing, we propose a radically different approach, based on robust
statistics and local first-order predictors of the surface. The
robustness of our local estimates allows us to derive a
\emph{non-iterative} feature-preserving filtering technique applicable
to arbitrary ``triangle soups''. We demonstrate its simplicity of
implementation and its efficiency, which makes it an excellent
solution for smoothing large, noisy, and non-manifold meshes.
Marc Levoy, Stanford University, Title: Why is 3D scanning hard?
Improvements in optical rangefinding technology have made it easy to acquire
dense 3D samples of an object or scene. However, a fully automated procedure
for assembling this data to create a geometric model still eludes us. This is
especially true for large or complicated objects scanned under non-laboratory
conditions. For example, although Stanford's Digital Michelangelo Project
produced some nice models, it did not achieve many of its stated objectives.
In this talk, I briefly survey the unsolved problems of 3D scanning. For some
of these problems, well defined solutions exist, and steady progress can be
made on them. Examples of this type include calibration of scanning platforms,
multi-view registration, surface reconstruction, view planning, and the
handling of large datasets. For other problems, solutions exist but the
problem is usually badly conditioned due to noise. Examples of this type
include multi-view registration in the presence of scanner miscalibration,
estimation of surface reflectance, and the scanning of optically uncooperative
materials. In still other cases, the problem itself is ill-posed, admitting
multiple correct answers. Classic examples of this type are surface
reconstruction in the presence of missing data (i.e. holes), and estimation of
surface shape and reflectance in the presence of interreflections or subsurface
scattering. Finally, there are problems for which no good solutions exist,
such as scanning geometrically convoluted objects, and insuring safety for the
objects being scanned.
I end with a (mostly) upbeat assessement of the long-term prospects for 3D
scanning and some predictions concerning its likely impact on industry and
popular culture.
T. J. Peters,University of Connecticut
Title: Ambient Isotopy for Topological Equivalence in Surface Reconstruction
Topological equivalence for surface reconstruction has
attracted considerable attention. We first show why
traditional topological equivalence based upon homeomorphisms
is inadequate and why the stronger equivalence relying upon
ambient isotopy should be preferred. We then show
how an established sampling and reconstruction technique
does meet this stronger equivalence. We continue to offer new
techniques for ambient isotopic approximations -- which need not
be piecewise linear. The first proof relies upon the medial axis,
whereas the second technique does not, using instead an analysis
of focal points. Advantages of each will be described.
This talk describes two sets of collaborations; 1. with N. Amenta
and A. C. Russell and 2. with K. Abe and T. Sakkalis.
Marc Pollefeys , University of North Carolina Title: Reconstructing 3D surfaces from 2D images
In this talk a complete approach to reconstruct 3D surfaces from camera
images is presented. The approach deals with uncalibrated image
sequences acquired with a hand-held camera. Based on tracked or matched
features the relation between multiple views are computed. From this
both the structure of the scene and the motion of the camera are
retrieved. The ambiguity on the reconstruction is restricted from
projective to metric through self-calibration. A flexible multi-view
stereo matching scheme is used to obtain a dense estimation of the
surface geometry. From the computed data different types of visual
models are constructed. Both 3D surface models and lightfield
representations can be constructed. The recovered information can also
be used to augment video footage with virtual objects. Some ongoing
research towards real-time reconstruction of dynamic events from
multiple cameras will also be presented.
Holly Rushmeier, IBM Watson Research Center
Title: 3D Scanning for Cultural Heritage Applications
Over the past 5 years there has been a great deal of interest in using 3D
scanning in cultural heritage projects. Applications range from
documentation for subject experts to communication to the general public.
We have been involved with two cultural heritage projects at IBM
Research- the now completed study of Michelangelo's Florence Pieta` and an
on-going project with the Egyptian National Center for Documentation of
Cultural and Natural Heritage. We will present some new algorithms for
geometric and photometric processing we developed to address problems we
encountered in the Pieta` project. I will also show preliminary results
from the Egyptian culture project and discuss issues that we are working
on.
Szymon Rusinkiewicz,Princeton University Title: Fast and Flexible 3D Scanning
The digitization of the 3D shape of real objects is a rapidly expanding
field, with applications in design, manufacturing, and mapping spaces such
as buildings and caves. This talk will describe recent research aimed at
increasing the speed and flexibility of 3D scanning systems. Two scanner
designs will be presented, one based on active temporal stereo and the
other based on projected structured light with stripe boundary coding.
Both are based on a space-time stereo framework, in which correspondences
between two cameras or between a camera and projector are obtained by
correlating windows with extent in both space and time. The scanners are
the first stage in a 3D model acquisition pipeline, which also includes
algorithms for aligning and merging successive range images. The talk will
discuss the value of having the entire pipeline operate in real time, which
allows the user to see holes in the model and determine when the object has
been completely covered. Results are presented from a prototype that
incorporates 60 Hz. structured-light rangefinder, a real-time variant of
ICP (iterative closest points) for alignment, and point-based merging and
rendering algorithms.
Claudio T. Silva, Oregon Health & Science University Title: Using Points for Rendering and Modeling Surfaces
Point sets are emerging as a robust technique for representing
surfaces. The primary appeal of point sets is their generality: every
shape can be represented by a set of points on its boundary, where the
degree of accuracy typically depends only on the number of points.
In order to model 3D surfaces, it is necessary to develop a
mathematical definition (and algorithm) for attaching a topology and
geometric shape to the set of points. A natural way to do this is to
use the inherent spatial interrelation among the points as implicit
connectivity information to define the manifolds. This can be
non-trivial since it is unclear what spacing of points represents
connected or disconnected pieces of the surface.
In this talk, we will present some recent techniques for point-based
modeling and rendering of surfaces. We believe that the importance of
point-set representation is likely to play an increasing role in 3D
geometric modeling. Part of the reason is that although considerable
research has been devoted to developing and optimizing the
``mesh-based world'', using meshes is unnatural in several
applications (e.g., 3D photography).
Joint work with Marc Alexa, Daniel Cohen-Or, and Shachar Fleishman.
Hongkai Zhao , University of California Title: Computer Visualization using Partial Differential Equations and
Implicit Surfaces
I will present mathematical formulations and efficient numerical
algorithms for the construction, deformation and operation of implicit
surfaces using variational methods and partial differential equations. In
particular I will discuss surface resonctruction from unorganized data
points using distance contours and minimal surfaces and solving partial
differential equations on moving interfaces
To appear in the proceedings of SIGGRAPH 2003
Leader of the Digital Michelangelo Project
DIMACS Homepage
Contacting the Center
Document last modified on April 30, 2003.