Survey of Methods in Computer Graphics
(600.658)


Overview
The goal of this course is to survey the state-of-the-art methods for reconstructing surfaces in 3D from input 3D point sets, with a particular focus on methods using computational geometry, local function fitting, and global function fitting. Weekly readings will be assigned, and students will be expected to prepare and present to the rest of the class.
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 local implicit methods, focusing on providing locally-weighted estimations of the surface. Finally, we will consider the class of global implicit function fitting techniques, which generate an output by solving a global linear system to fit an implicit function to the input data.
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. In addition, all students will be expected to submit a short summary of the readings at the beginning of each class. (The review form can be found here.)
Finally, towards the end of the summer, the entire class will consolidate the semester's material by jointly writing a term paper summarizing the methods, analyzing their benefits, and identifying directions for future research in the area.
Formalities
Date Subject Presenter Reading Misc
9/11/13 Introduction / Alpha Shapes Kazhdan / Kazhdan (slides) Edelsbrunner and Mucke, 1994 Qhull
9/18/13 Ball-pivoting / Cocone Doverspike / Salume Bernardini et al., 1999 (slides, reviews) Dey and Goswami, 2003 (slides, reviews)
9/25/13 Spectral Reconstruction / Robust Reconstruction Prada / Sinha Kolluri et al., 2004 (slides, reviews) Hornung and Kobbelt, 2006 (slides, reviews)
10/02/13 Unorganized Points / Volumetric Models Prada / Fernandez Hoppe et al., 1992 (slides, reviews) Curless and Levoy, 1996 (slides, reviews)
10/09/13 Class Cancelled
10/16/13 Overivew of MLS / PSS Kazhdan / Sinha McLain, 1974 (slides) Alexa et al., 2001 (slides, reviews)
10/23/13 Robust MLS / MPU Prada / Salume Fleishman et al., 2005 (slides, reviews) Ohtake et al., 2003 (slides, reviews)
10/30/13 APSS / RIMLS Chuang / Chuang Guennebaud et al., 2007 (slides, reviews) Oztireli et al., 2009 (slides, reviews)
11/06/13 RBF / Interpolating polygon soups Fernandez / Doverspike Carr et al., 2001 (slides, reviews) Shen et al., 2004 (slides, reviews)
11/13/13 Poisson Reconstruction / Variational Voronoi Kazhdan / Sinha Kazhdan et al., 2006 (slides, reviews) Alliez et al., 2007 (slides, reviews)
11/20/13 Scattered Data Approximation / SSD Salume / Fernandez Ohtake et al., 2004 (slides, reviews) Calakli and Taubin, 2011 (slides, reviews)
12/04/13
Papers
Adamson and Alexa, Approximating and Intersecting Surfaces from Points. (2003)
Adamson and Alexa, Approximating Bounded, Non-orientable Surfaces from Points. (2004)
Ahmed et al., Robust Fusion of Dynamic Shape and Normal Capture for High-quality Reconstruction of Time-varying Geometry. (2008)
Alexa et al., Point Set Surfaces. (2001)
Alexa et al., Computing and Rendering Point Set Surfaces. (2003)
Alliez et al., Voronoi-based Variational Reconstruction of Unoriented Point Sets. (2007)
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)
Amenta and Kil, The Domain of a Point Set Surface. (2004)
Bajaj et al., Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans. (1995)
Bajaj et al., Arbitrary Topology Shape Reconstruction from Planar Cross Sections. (1996)
Barequet et al., Straight-Skeleton Based Contour Interpolation. (2004)
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, Geometric Structures for Three-Dimensional Shape Representation. (1984)
Boissonnat et al., Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions. (2000)
Boissonnat et al., Shape Reconstruction from Unorganized Cross-sections. (2007)
Boulch et al., Fast and Robust Normal Estimation for Point Clouds with Sharp Features. (2012)
Boyer and Petitjean, Curve and Surface Reconstruction from Regular and Non-Regular Point Sets. (2001)
Calakli and Taubin, SSD: Smooth Signed Distance Surface Reconstruction. (2011)
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)
Cazals and Giesen, Delaunay Triangulation Based Surface Reconstruction: Ideas and Algorithms. (2006)
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 et al., Shape Dimension and Approximation from Samples. (2003)
Dey and Goswami, Provable Surface Reconstruction from Noisy Samples. (2004)
Dey and Sun, An Adaptive MLS Surface for Reconstruction with Guarantees. (2005)
Dinge et al., Scale Space Meshing of Raw Data Point Sets. (2011)
Dinh et al., Reconstructing Surfaces By Volumetric Regularization Using Radial Basis Functions. (2000)
Edelsbrunner et al., On the Shape of Points in the Plane. (1993)
Edelsbrunner and Mucke, Three-Dimensional Alpha Shapes. (1994)
Fang and Gossard, Multidimensional Curve Fitting to Unorganized Data Points by Nonlinear Minimization. (1995)
Fleishman and Cohen-Or, Progressive Point Set Surfaces. (2003)
Fleishman et al., Robust Moving Least-squares Fitting with Sharp Features. (2005)
Freedman, Efficient Simplicial Reconstruction of Manifolds from Their Samples. (2002)
Fuchs et al., Optimal Surface Reconstruction from Planar Contours. (1977)
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)
Guennebaud and Gross, Algebraic Point Set Surfaces. (2007)
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)
Hoppe et al., Piecewise Smooth Surface Reconstruction. (1994)
Hornung and Kobbelt, Hierarchical Volumetric Multi-view Stereo Reconstruction of Manifold Surfaces based on Dual Graph Embedding. (2006)
Hornung and Kobbelt, Robust Reconstruction of Watertight 3D Models from Non-uniformly Sampled Point Clouds Without Normal Information. (2006)
Kazhdan, Reconstruction of Solid Models from Oriented Point Sets. (2005)
Kazhdan et al., Poisson Surface Reconstruction. (2006)
Kazhdan and Hoppe, Screened Poisson Surface Reconstruction. (2013)
Keren and Gotsman, Fitting Curves and Surfaces with Constrained Implicit Polynomials. (1999)
Kolluri et al., Spectral Surface Reconstruction from Noisy point Clouds. (2004)
Kolluri, Provably Good Moving Least Squares. (2005)
Krishnamurthy, Fitting Smooth Surfaces to Dense Polygon Meshes. (1996)
Lempitsky and Boykov, Global Optimization for Shape Fitting. (2007)
Levin, The Approximation Power of Moving Least Squares. (1998)
Levin, Mesh-Independent Surface Interpolation. (2003)
Li et al., Robust Single-View Geometry and Motion Reconstruction. (2009)
Li et al., Temporally Coherent Completion of Dynamic Shapes. (2011)
Masuda et al., Filling the Signed Distance Field by Fitting Local Quadrics. (2004)
McLain, Drawing Contours from Arbitrary Data Points. (1974)
Mederos et al., Surface Reconstruction from Noisy Point Clouds. (2005)
Mitra and Nguyen, Estimating Surface Normals in Noisy Point Cloud Data. (2003)
Morse et al., Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions. (2001)
Muecke et al., Surface reconstruction from multi-resolution sample points. (2011)
Mullen et al., Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets. (2010)
Muraki, Volumetric Shape Description of Range Data Using "Blobby Model". (1991)
Murali and Funkhouser, Consistent Solid and Boundary Representations from Arbitrary Polygonal Data. (1997)
Nehab et al., Efficiently Combining Positions and Normals for Precise 3D Geometry. (2005)
Newcombe et al., KinectFusion: Real-Time Dense Surface Mapping and Tracking. (2011)
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)
Oztireli et al., Feature Preserving Point Set Surfaces based on Non-Linear Kernel Regression. (2009)
Paris et al., A Surface Reconstruction Method Using Global Graph Cut Optimization. (2005)
Podolak and Rusinkiewicz, Atomic Volumes for Mesh Completion. (2005)
Pons et al., Multi-View Stereo Reconstruction and Scene Flow Estimation with a Global Image-Based Matching Score. (2007)
Pop et al., Globally Consistent Space-Time Reconstruction. (2010)
Rusinkiewicz et al., Real-Time 3D Model Acquisition. (2002)
Savchencko et al., Function Representation of Solids Reconstructed from Scattered Surface Points and Contours. (1995)
Schall and Samozino, Surface from Scattered Points: A Brief Survey of Recent Developments. (2005)
Scheidegger et al., Triangulating Point Set Surfaces with Bounded Error. (2005)
Sharf et al., Context-based Surface Completion. (2004)
Sharf et al., Space-time Surface Reconstruction Using Incompressible Flow. (2008)
Shen et al., Interpolating and Approximating Implicit Surfaces from Polygon Soup. (2004)
Sibson, A Vector Identity for the Dirichlet Tessellation. (1980)
Sussmuth et al., Reconstructing Animated Meshes from Time-Varying Point Clouds. (2008)
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)
Vogiatzis et al., Multi-view Stereo via Volumetric Graph-cuts. (2005)
Walder et al., Implicit Surface Modelling with a Globally Regularised Basis of Compact Support. (2006)
Wand et al., Reconstruction of Deforming Geometry from Time-Varying Point Clouds. (2007)
Wand et al., Efficient Reconstruction of Non-rigid Shape and Motion from Real-Time 3D Scanner Data. (2008)
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)
Yoon et al., Surface and normal ensembles for surface reconstruction. (2007)
Zhang et al., Spacetime Faces: High Resolution Capture for Modeling and Animation. (2004)
Zhao et al., Fast Surface Reconstruction Using the Level Set Method. (2001)