Three-dimensional surface meshes are the most common discrete representation of the exterior of a virtual shape. Extracting relevant geometric or topological features from them can simplify the way objects are looked at, help with their recognition, and facilitate description and categorization according to specific criteria. This book adopts the point of view of discrete mathematics, the aim of which is to propose discrete counterparts to concepts mathematically defined in continuous terms. It explains how standard geometric and topological notions of surfaces can be calculated and computed on a 3D surface mesh, as well as their use for shape analysis. Several applications are also detailed, demonstrating that each of them requires specific adjustments to fit with generic approaches. The book is intended not only for students, researchers and engineers in computer science and shape analysis, but also numerical geologists, anthropologists, biologists and other scientists looking for practical solutions to their shape analysis, understanding or recognition problems.

Table of Contents:
Preface ix Introduction xi Chapter 1. Geometric Features based on Curvatures 1 1.1. Introduction 1 1.2. Some mathematical reminders of the differential geometry of surfaces 2 1.2.1. Fundamental forms and normal curvature 2 1.2.2. Principal curvatures and shape index 5 1.2.3. Principal directions and lines of curvature 6 1.2.4. Weingarten equations and shape operator 9 1.2.5. Practical computation of differential parameters 12 1.2.6. Euler’s theorem 13 1.2.7. Meusnier’s theorem 15 1.2.8. Local approximation of the surface 16 1.2.9. Focal surfaces 17 1.3. Computation of differential parameters on a discrete 3D mesh 19 1.3.1. Introduction 19 1.3.2. Some notations 19 1.3.3. Computing normal vectors 20 1.3.4. Locally fitting a parametric surface 22 1.3.5. Discrete differential geometry operators 22 1.3.6. Integrating 2D curvatures 28 1.3.7. Tensor of curvature: Taubin’s formula 28 1.3.8. Tensor of curvature based on the normal cycle theory 30 1.3.9. Integral estimators 34 1.3.10. Processing unstructured 3D point clouds 38 1.3.11. Discussion of the methods 38 1.4. Feature line extraction 46 1.4.1. Introduction 46 1.4.2. Lines of curvature 47 1.4.3. Crest/ridge lines 55 1.4.4. Feature lines based on homotopic thinning 79 1.5. Region-based approaches 84 1.5.1. Mesh segmentation 84 1.5.2. Shape description based on graphs 87 1.6. Conclusion 98 Chapter 2. Topological Features 99 2.1. Mathematical background 99 2.1.1. A topological view on surfaces 100 2.1.2. Algebraic topology 103 2.2. Computation of global topological features 106 2.2.1. Connected components and genus 106 2.2.2. Homology groups 107 2.3. Combining geometric and topological features 111 2.3.1. Persistent homology 112 2.3.2. Reeb graph and Morse–Smale complex 115 2.3.3. Homology generators 118 2.3.4. Measuring holes 121 2.4. Conclusion 128 Chapter 3. Applications 131 3.1. Introduction 131 3.2. Medicine: lines of curvature for polyp detection in virtual colonoscopy 131 3.3. Paleo-anthropology: crest/ridge lines for shape analysis of human fossils 133 3.4. Geology: extraction of fracture lines on virtual outcrops 137 3.5. Planetary science: detection of feature lines for the extraction of impact craters on asteroids and rocky planets 140 3.6. Botany: persistent homology to recover the branching structure of plants 143 Conclusion 145 References 149 Index 169