Curve and Surface Reconstruction

Tamal K. Dey0521863708, 9780521863704, 9780511261336

Many applications in science and engineering require a digital model of a real physical object. Advanced scanning technology has made it possible to scan such objects and generate point samples on their boundaries. This book shows how to compute a digital model from this point sample. After developing the basics of sampling theory and its connections to various geometric and topological properties, the author describes a suite of algorithms that have been designed for the reconstruction problem, including algorithms for surface reconstruction from dense samples, from samples that are not adequately dense and from noisy samples. Voronoi and Delaunay based techniques, implicit surface based methods and Morse theory based methods are covered. Scientists and engineers working in drug design, medical imaging, CAD, GIS, and many other areas will benefit from this first book on the subject.Provides fundamentals of point cloud data processing Algorithms with correctness proofs are presented Many figures, a set of exercises, and a brief history for each chapter.

---

Table of contents :
Half-title……Page 3
Series-title……Page 4
Title……Page 5
Copyright……Page 6
Dedication……Page 7
Contents……Page 9
Preface……Page 13
1 Basics……Page 17
1.1 Shapes……Page 18
1.1.1 Spaces and Maps……Page 19
Homotopy……Page 20
Isotopy……Page 21
Boundary……Page 22
1.1.3 Complexes……Page 23
1.2 Feature Size and Sampling……Page 24
1.2.1 Medial Axis……Page 26
1.2.2 Local Feature Size……Page 30
1.2.3 Sampling……Page 32
Uniform Sampling……Page 33
1.3 Voronoi Diagram and Delaunay Triangulation……Page 34
Voronoi Diagrams……Page 35
Delaunay Triangulations……Page 36
Restricted Voronoi Diagrams……Page 37
1.3.2 Three Dimensions……Page 38
1.4 Notes and Exercises……Page 39
Exercises……Page 40
2 Curve Reconstruction……Page 42
2.1 Consequences of Epsilon-Sampling……Page 43
2.2.1 Algorithm……Page 46
2.2.2 Correctness……Page 48
2.3.1 Algorithm……Page 51
2.3.2 Correctness……Page 52
2.4 Notes and Exercises……Page 54
Exercises……Page 55
3 Surface Samples……Page 57
3.1.1 Approximation of Normals……Page 59
3.1.2 Normal Variation……Page 61
3.1.3 Edge and Triangle Normals……Page 63
3.2.1 Topological Ball Property……Page 66
3.2.2 Voronoi Faces……Page 69
Exercises……Page 73
4.1.1 Poles and Cocones……Page 75
4.1.2 Cocone Triangles……Page 78
4.1.3 Pruning……Page 80
4.1.4 Manifold Extraction……Page 82
4.2 Geometric Guarantees……Page 86
4.2.1 Additional Properties……Page 88
4.3.1 The Map Nu……Page 89
4.3.2 Homeomorphism Proof……Page 91
4.4 Notes and Exercises……Page 92
Exercises……Page 94
5.1 Samples and Boundaries……Page 96
5.1.1 Boundary Sample Points……Page 97
5.1.2 Flat Sample Points……Page 98
5.2 Flatness Analysis……Page 99
5.3 Boundary Detection……Page 103
5.3.1 Justification……Page 104
5.3.2 Reconstruction……Page 105
5.4 Notes and Exercises……Page 106
Exercises……Page 107
6.1 Power Crust……Page 109
Power Diagrams……Page 110
Geometric Proximity……Page 113
Normal Proximity……Page 114
6.1.3 Homeomorphism and Isotopy……Page 115
6.1.4 Algorithm……Page 117
6.2 Tight Cocone……Page 120
6.2.1 Marking……Page 121
6.2.2 Peeling……Page 123
6.3 Experimental Results……Page 125
Exercises……Page 127
7.1 Noise Model……Page 129
7.2 Empty Balls……Page 131
7.3.1 Analysis……Page 135
7.3.2 Algorithm……Page 138
7.4 Feature Approximation……Page 140
7.4.1 Analysis……Page 142
7.4.2 Algorithm……Page 146
7.5 Notes and Exercises……Page 147
Exercises……Page 148
8.1 Preliminaries……Page 149
8.2 Union of Balls……Page 152
8.3 Proximity……Page 158
8.4 Topological Equivalence……Page 160
8.4.1 Labeling……Page 161
8.4.2 Algorithm……Page 163
8.5 Notes and Exercises……Page 165
Exercises……Page 166
9.1 Generic Approach……Page 168
9.1.1 Implicit Function Properties……Page 169
9.1.2 Homeomorphism Proof……Page 170
9.2 MLS Surfaces……Page 171
Weighting Functions……Page 172
AMLS Function……Page 174
9.3 Sampling Assumptions and Consequences……Page 175
9.3.1 Influence of Samples……Page 178
9.4 Surface Properties……Page 182
9.4.1 Hausdorff Property……Page 183
9.4.2 Gradient Property……Page 186
9.5.1 Normal and Feature Approximation……Page 188
9.5.2 Projection……Page 189
9.6.1 Projection MLS……Page 191
9.6.3 Computational Issues……Page 192
Advantages of Newton Projections……Page 193
Zero-Level Sets……Page 194
9.7 Voronoi-Based Implicit Surface……Page 195
9.8 Notes and Exercises……Page 196
Exercises……Page 197
10.1 Morse Functions and Flows……Page 198
10.2.1 Vector Field……Page 201
10.2.2 Discrete Flow……Page 203
10.2.3 Relations to Voronoi/Delaunay Diagrams……Page 206
Index 3 Critical Points……Page 207
10.3.1 Flow Complex Construction……Page 208
10.3.2 Merging……Page 209
10.3.3 Critical Point Separation……Page 210
10.4.1 Distance from Delaunay Balls……Page 212
Flow Relation……Page 214
Centered Simplices……Page 215
Equivocal Simplices……Page 216
10.4.3 Reconstruction……Page 217
10.4.4 Algorithm……Page 218
Exercises……Page 221
Bibliography……Page 223
Index……Page 229