Seminar on 3D Model Reconstruction
(600.659)


This course is motivated by the recent development of techniques for the reconstruction of solid models from an input point set. The course will review a number of the existing surface reconstruction techniques developed in the last decade and will cover such topics as: convex hulls, Voronoi diagrams, Delaunay triangulations, the Poisson equation, moving least squares, and partitions of unity.
General Breakdown
This course will be broken up into three separate areas. First, we will consider surface reconstruction techniques that leverage tools from the domain of computational geometry in order to compute a triangulation of the input point set. Next, we will consider surface fitting algorithms, which locally fit the surface of a mesh to the input data. Finally, we consider the class of implicit function fitting techniques, which generate an output by fitting an implicit function to the input data and then extract the reconstructed mesh as an iso-surface of the function.
Student Responsibilities
Students will be regularly assigned papers to read in the area of surface reconstruction, and two students each week will present papers to the seminar. Additionally, there will be two projects that students will be expected to complete. The first will be an implementation project, focused on exposing students to some of the technical challenges of reconstruction by having them implement an existing method. The second will be a research project, motivating students to explore new methods for surface reconstruction.

As part of preparing the assigned reading, students will be expected to answer the following four questions:

  1. What is the problem addressed by the paper?
  2. What is the approach used to resolve the problem?
  3. What are the key ideas/observations behind the approach?
  4. What are the limitations of the method?
  5. What are the contributions of the method?

Date Subject Presenter Reading Notes Misc
9/12/05 Introduction Kazhdan Notes
9/13/05 Computational Geometry (1) Convex Hulls Kazhdan Notes QHull
9/19/05 Voronoi Diagrams and Delaunay Triangulations Kazhdan Notes
9/20/05 Alpha Shapes Bolitho Edelsbrunner et al., 1994 Notes
9/26/05 The Power Crust Amenta Amenta et al., 2001 Amenta et al., 2001 Notes
9/27/05 Cocone and Tight Cocone Ahmad Amenta et al., 2000 Dey et al., 2003
10/03/05 Ball Pivoting Bilodeau Bernardini et al., 1999
10/04/05
Rosh HaShanah / Class Cancelled
10/10/05 Surface Fitting Adaptive Meshes Chen Terzopoulos et al., 1991 Notes
10/11/05 Balloon Fitting Niski Chen et al., 1995 Notes
First Project Proposal Due
10/17/05
Fall Break / Class Cancelled
10/18/05 Surface Inferencing Sadowsky Guy et al., 1997 Tang et al., 1998 Notes
10/24/05
First Project Due
Moving Least Squares Kazhdan McLain, 1974 (Sections 1 and 2) Levin, 2003 Notes MLS Viewer
10/25/05 Point Set Surfaces Bolitho Alexa et al., 2003 Notes
10/31/05 Triangulating Point Set Surfaces Chen Shen et al., 2004 Notes
11/01/05 Implicits from Polygon Meshes Gray Yngve et al., 2002 Notes
11/07/05 Surfaces from Polygon Soup Ahmad Scheidegger et al., 2005
11/08/05 Implicit Function Fitting Surfaces from Unorganized Points Niski Hoppe et al., 1992 Notes
11/14/05 Volumetric Range Image Reconstruction Bilodeau Curless et al., 1996
11/15/05 Radial Basis Functions Bolitho Carr et al., 2001 Notes
11/21/05 Volumetric Diffusion Gray Davis et al., 2002 Notes
11/22/05 Adaptive Radial Basis Functions Sadowsky Ohtake et al., 2004 Notes
11/28/05 FFT-Based Reconstruction Kazhdan Kazhdan, 2005 Notes
11/29/05 Computational Geometry (2) Atomic Volumes Sadowsky Podolak et al., 2005 Notes
12/05/05 Spectral Analysis Ahmad Kolluri et al., 2004 Notes
12/06/05
Final Project Presentations
12/12/05
Papers
Alexa et al., Point Set Surfaces. (2001)
Alexa et al., Computing and Rendering Point Set Surfaces. (2003)
Amenta et al., A New Voronoi-Based Surace Reconstruction Algorithm. (1998)
Amenta and Bern, Surface Reconstruction by Voronoi Filtering. (1999)
Amenta and Kolluri, Accurate and Efficient Union of Balls. (2000)
Amenta et al., A Simple Algorithm for Homeomorphic Surface Reconstruction. (2000)
Amenta et al., The Power Crust. (2001)
Amenta et al., The Power Curst, Union of Balls, and the Medial Axis Transform. (2001)
Bajaj et al., Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans. (1995)
Bernardini et al., The Ball-Pivoting Algorithm for Surface Reconstruction. (1999)
Bittar et al., Automatic Reconstruction of Unstructed 3D Data: Combining a Medial Axis and Implicit Surfaces\. (1995)
Boissonnat et al., Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions. (2002)
Bajaj et al., Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans. (1995)
Boyer and Petitjean, Curve and Surface Reconstruction from Regular and Non-Regular Point Sets. (2001)
Carr et al., Reconstruction and Representation of 3D Objects with Radial Basis Functions. (2001)
Carr et al., Smooth Surface Reconstruction from Noisy Range Data. (2003)
Chen and Medioni, Description of Complex Objects from Muliple Range Images Using an Inflating Balloon Model. (1995)
Crossno and angel, Spiraling Edge: Fast Surface Reconstruction from Partially Organized Sample Points. (1999)
Curless and Levoy, A Volumetric Method for Building Complex Models from Range Images. (1996)
Davis et al., Filling Holes in Complex Surfaces using Volumetric Diffusion. (2002)
Dey and Goswami, Tight Cocone: A Water-tight Surface Reconstructor. (2003)
Dey and Goswami, Provable Surface Reconstruction from Noisy Samples. (2004)
Dey and Sun, An Adaptive MLS Surface for Reconstruction with Guarantees. (2005)
Dinh et al., Reconstructing Surfaces By Volumetric Regularization Using Radial Basis Functions. (2000)
Edelsbrunner and Mucke, Three-Dimensional Alpha Shapes. (1994)
Fang and Gossard, Multidimensional Curve Fitting to Unorganized Data Points by Nonlinear Minimization. (1995)
Fleishman et al., Progressive Point Set Surfaces. (2003)
Freedman, Efficient Simplicial Reconstruction of Manifolds from Their Samples. (2002)
Gopi et al., Surface Reconstruction Base on Lower Dimensional Delaunay Triangulation. (2000)
Gopi and Krishnan, A Fast and Efficient Projection-Based Approach for Surface Reconstruction. (2002)
Guy and Medioni, Inference of Surfaces, 3D Curves, and Junctions from Sparse, Noisy, 3D Data. (1997)
Hoppe et al., Surface Reconstruction from Unorganized Points. (1992)
Kazhdan, Reconstruction of Solid Models from Oriented Point Sets. (2005)
Keren and Gotsman, Fitting Curves and Surfaces with Constrained Implicit Polynomials. (1999)
Kolluri et al., Spectral Surface Reconstruction from Noisy point Clouds. (2004)
Levin, The Approximation Power of Moving Least Squares. (1998)
Levin, Mesh-Independent Surface Interpolation. (2003)
McLain, Drawing Contours from Arbitrary Data Points. (1974)
Mederos et al., Surface Reconstruction from Noisy Point Clouds. (2005)
Morse et al., Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions. (2001)
Muraki, Volumetric Shape Description of Range Data Using "Blobby Model". (1991)
Nehab et al., Efficiently Combining Positions and Normals for Precise 3D Geometry. (2005)
Ohtake et al., Multi-level Partition of Unity Implicits. (2003)
Ohtake et al., A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions. (2003)
Ohtake et al., 3D Scattered Data Approximation with Adaptive Compactly Supported Radial Basis Functions. (2004)
Podolak and Rusinkiewicz, Atomic Volumes for Mesh Completion. (2005)
Savchencko et al., Function Representation of Solids Reconstructed from Scattered Surface Points and Contours. (1995)
Scheidegger et al., Triangulating Point Set Surfaces with Bounded Error. (2005)
Shen et al., Interpolating and Approximating Implicit Surfaces from Polygon Soup. (2004)
Tang and Medioni, Inference of Integrated Surface, Curve, and Junction Descriptions. (1998)
Terzopoulos and Vasilescu, Sampling and Reconstruction with Adaptive Meshes. (1991)
Turk and Levoy, Zippered Polygon Meshes from Range Images. (1994)
Turk and O'Brien, Shape Transformation Using Variational Implicit Functions. (1999)
Turk and O'Brien, Modelling with Implicit Surfaces that Interpolate. (2004)
Whitaker, A Level-Set Approach to 3D Reconstruction from Range Data. (1998)
Xie et al., Piecewise C1 Continuous Surface Reconstruction of Noisy Point Clourds via Local Implicit Quadric Regression. (2003)
Yngve and Turk, Robust Creation of Implicit Surfaces from Polygonal Meshes. (2002)
Yoo et al., Anatomic Modeling from Unstructured Samples Using Variational Implicit Surfaces. (2001)
Zhao et al., Fast Surface Reconstruction Using the Level Set Method. (2001)