### DIMACS Workshop on Surface Reconstruction

#### April 30 - May 2, 2003 DIMACS Center, Rutgers University, Piscataway, New Jersey

Organizers:
Nina Amenta, University of California - Davis, amenta@cs.ucdavis.edu
Fausto Bernardini, IBM - T. J. Watson Research Center, fausto@watson.ibm.com
Presented under the auspices of the Special Focus on Computational Geometry and Applications.

### Abstracts

Title: Evaluating the performance of 3-D active vision systems

Frederic Cazals, INRIA Sophia-Antipolis, France

Title: Point clouds, Surface Reconstruction, and Differential Geometry: two selected topics.

Surface Reconstruction is the process which consists of turning a 3D point cloud into a surface, either triangulated, defined implicitly, or defined parametrically. most surface reconstruction methods rely at some point upon estimates of differential quantities, so that several interesting questions lie at the crossroads of surface reconstruction and applied differential geometry. this talk will discuss two of them. in the first part, we will recall the fundamentals of the so-called natural interpolation method, and will discuss its application to surface reconstruction. in the second part, we will present a provably good algorithm to estimate local differential properties of any fixed order over a sampled smooth surface. the method consists of fitting the local representation of the manifold using a jet ---i.e. a truncated Taylor expansion, using either a polynomial interpolation or approximation.

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.

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.

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
To appear in the proceedings of SIGGRAPH 2003

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,
Leader of the Digital Michelangelo Project

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

DIMACS Homepage
Contacting the Center