Title: Reconstruction and Feature Extraction from Point Cloud Data with Mathematical Reasoning

Course Organizer:
Tamal K. Dey
Dept. of Computer Science & Engineering
The Ohio State University
Columbus, OH 43210
e-mail: [email protected]

Rationale: Geometric computations with point cloud data are becoming increasingly important in the application areas dealing with geometric shapes. The point clouds provide a light-weight, simple input mechanism to automate the conversion of a real-world object into a computer model. Naturally, the research on how to reconstruct the sampled shape and how to extract their geometric features from the given point samples has come to the fore. Among the many proposed methods, there are some that come with mathematical guarantees. The purpose of this course is to expose the audience to these algorithms and their mathematical reasoning. The course will be designed keeping the mathematical understanding of the algorithms and their practical effectiveness in focus.

Instructor: Prof. Tamal K. Dey
Dept. of Computer Science & Engineering
The Ohio State University

Tamal Krishna Dey is currently a professor in the computer science & engineering department of the
Ohio State University. He nished his Phd from Purdue University in 1991. Before joining Ohio State
he has held faculty and research positions at various other institutes, including Indiana University-Purdue
University at Indianapolis, Indian Institute of Technology, Kharagpur, University of Illinois at Urbana-
Champaign and Max-Planck Institute, Germany. His work mainly concentrate on computational geometry
and computational topology spanning different application areas such as geometric modeling, mesh generation, computer graphics and visualization. More information can be obtained from http://www.cse.ohiostate.edu/�� tamaldey.

Course description: There will be three parts to the course.

In the first part, we will develop the necessary concepts for curve and surface reconstruction. We will
touch upon some basic tools from computational geometry (Delaunay and Voronoi diagrams) and topology
(homeomorphism, simplicial complex). Then we explain the notion of feature size,
-sampling theory.
Based on this theory we develop two algorithms CRUST and NEAREST NEIGHBOR for curve reconstruction
and one algorithm COCONE for surface reconstruction. The proofs of correctness involve analyzing
differential properties of curves and surfaces in the discrete setting using the Delaunay/Voronoi structures.
In the second part, we focus on reconstructing surfaces from point cloud data that are not perfect. We
present two algorithms POWER CRUST and TIGHT COCONE that can handle undersampling. For noisy point clouds we present two algorithms ROBUST COCONE that interpolates the data and ADAPTIVE MLS that 1 projects point on an implicit smooth surface. Necessary concepts for proving the correctness of the methods are discussed.

In the third part, we concentrate on algorithms to extract features from point cloud data. Namely, we
present one algorithm MEDIAL to extract the medial axis of the shapes from its point samples and another
algorithm SEGMENT for segmenting a shape into its salient features. The rst one derives its correctness
from the
-sampling theory while the second one is motivated by critical point theory.

Level of the Material: The course material will be developed assuming a very basic background in algorithms and mathematics. We will assume that the participant is familiar with the algorithmic concepts
in computer science at the undergraduate level and have basic mathematical skills in linear algebra and
geometry.

The distribution of the level of material in the course will be:
1. 30% beginner (material accessible to any attendee who has the recommended background)
2. 60% intermediate (material accessible to an attendee with the background provided by the course)
3. 10% advanced (material that requires further study by an attendee outside the course)

Target audience: People in academia, industry or research institutions working on geometric modeling,
CAD designs, mesh generation, computer graphics, computer vision, GIS, molecular modeling, scientic
simulations.

Recommended background: Familiarity of algorithms, specically geometric algorithms at a level of
undergraduates in computer science. Basic knowledge in linear algebra, geometry and topology.

Course outline:
First hour.
1. Shape topology (manifolds, complexes, maps): 5 min.
2. Feature size and sampling (medial axis, local feature size,
-sampling): 5 min.
3. Voronoi and Delaunay diagrams: 5 min.
4. Crust and NN-crust (algorithms, correctness): 15 min.
5. Surface normal approximations (normal variations, edge-, triangle-normals): 5 min
6. Surface topology recovery (closed ball property, Voronoi properties): 5 min.
7. Surface reconstruction (Algorithm, guarantees): 15 min.
Second hour.
1. Undersampling : 5 min.
2. Power crust (denitions, algorithm, correctness): 10 min.
3. Tight Cocone (denitions, algorithm, experiments): 10 min.
4. Noisy point clouds: 5 min.
5. Robust Cocone (sampling conditions, normal estimations, reconstructions) : 15 min.
6. Moving Least Squares (MLS) methods: 5 min.
7. Adaptive MLS (denition, algorithm, correctness): 10 min.
Third hour.
1. Medial axis approximation : 5 min.
2. Algorithm : 10 min.
3. Convergence : 5 min.
4. Experimental results : 5 min.
5. Feature segmentation : 5 min.
6. Distance functions : 5 min.
7. Relations to Delaunay/Voronoi : 5 min.
8. Algorithm : 10 min.
9. Shape matching : 5 min.
10. Experimental results : 5 min.