Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Guide to Computational Geometry Processing

Foundations, Algorithms, and Methods

verfasst von: Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs

Verlag: Springer London

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book reviews the algorithms for processing geometric data, with a practical focus on important techniques not covered by traditional courses on computer vision and computer graphics. Features: presents an overview of the underlying mathematical theory, covering vector spaces, metric space, affine spaces, differential geometry, and finite difference methods for derivatives and differential equations; reviews geometry representations, including polygonal meshes, splines, and subdivision surfaces; examines techniques for computing curvature from polygonal meshes; describes algorithms for mesh smoothing, mesh parametrization, and mesh optimization and simplification; discusses point location databases and convex hulls of point sets; investigates the reconstruction of triangle meshes from point clouds, including methods for registration of point clouds and surface reconstruction; provides additional material at a supplementary website; includes self-study exercises throughout the text.

Inhaltsverzeichnis

Frontmatter

Introduction

1. Introduction
Abstract
This introductory chapter motivates the book through a discussion of the many sources and applications of geometric data.
Small to medium sized objects can be captured with a variety of optical acquisition techniques, such as laser scanning, structured light scanning, and time of flight cameras. There are many uses of optical acquisition, and number of these are medical in nature: for instance, laser scanning has emerged as an important part of in-the-ear hearing aid manufacturing.
At the other end of the scale spectrum, airborne laser scanning allows us to build digital terrain models and ultimately city models. Finally, a lot of geometric data are still produced manually through the use of CAD software.
Going through each topic, we discuss what geometry processing algorithms are pertinent and refer the reader to the chapters where these algorithms are discussed in greater detail.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs

Mathematical Preliminaries

Frontmatter
2. Vector Spaces, Affine Spaces, and Metric Spaces
Abstract
The chapter gives a short overview of the most important concepts in linear algebra, affine spaces, and metric spaces. It is not intended as a course, but as a point of reference and a brush up.
First, we present the basic concepts of linear algebra: vector space, subspace, basis, dimension, linear map, matrix, determinant, eigenvalue, eigenvector, inner product. This should all be familiar concepts, but what might be less familiar is the abstract view where the basic concepts are vector spaces and linear maps while coordinates and matrices become derived concepts. The last subject is the singular value decomposition which is used for mesh simplification and in the ICP algorithm for registration.
The next area is affine spaces where we only give the basic definitions: affine space, affine combination, convex combination, and convex hull.
Finally we introduce metric spaces which makes the concepts of open sets, neighborhoods, and continuity precise.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
3. Differential Geometry
Abstract
The chapter gives a short overview of the concepts from differetial geometry that are used in geometry processing: normal, area, first and second fundamental form, the Gauß and Weingarten map, normal and geodesic curvature, principal curvatures and directions, the Gaußian and mean curvature, the Gauß–Bonnet theorem and the Laplace–Beltrami operator. We end by a brief study of implicitly defined surfaces.
It is not meant as a course in differential geometry, but as a brush up and a handy point of reference. For the reader who wishes to know more there is a vast literature to which we refer.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
4. Finite Difference Methods for Partial Differential Equations
Abstract
In this chapter, we initially give an introduction to methods for computing derivatives and partial derivatives using discrete differential operators and discuss the connection to Taylor series.
The chapter moves on to the topic of solving PDEs using finite difference methods. We discuss implicit and explicit methods and boundary conditions. The chapter also covers the categories of PDEs: elliptic, hyperbolic and parabolic as well as the important notions of consistence, convergence and stability. Finally, there is a discussion of 2D and 3D problems and problems on irregular grids.
At the end of the chapter, linear interpolation is discussed. We discuss both linear interpolation on a regular 2D or 3D grid and linear interpolation in a simplicial complex using barycentric coordinates.
As in the previous two chapters, this chapter is intended as a brush up and a point of reference. The reader who wishes to know more is referred to the literature.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs

Computational Geometry Processing

Frontmatter
5. Polygonal Meshes
Abstract
The polygonal mesh representation is one of the most general and most used representations of geometric data. A large part of the success of meshes is the simplicity of the representation combined with the fact that computers are increasingly able to deal with the large amounts of data needed in order to represent a smooth surface using polygons.
In this chapter, we cover the basic notions of a polygonal meshes: faces, edges, vertices. We move on to data sources for polygonal meshes and common issues when meshes are considered to be sampled representations of smooth surfaces. Also, we discuss the common basic operations for manipulation of meshes, e.g., edge collapse, edge flipping, splitting of edges and faces, etc.
Finally, we discuss concrete data structures for polygonal meshes. In particular, the indexed face set representation, the halfedge representation, and the quad edge representation are covered. These are some of the most useful and generic representations for polygonal meshes.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
6. Splines
Abstract
The chapter describes the type of curves and surfaces often used in modern CAD systems. The de facto industry standard here are NURBS which stands for Non Uniform Rational B-Splines. Even though the animation industry has largely switched to subdivision surfaces NURBS are still relevant: They are a very flexible tool for the representation of smooth surfaces, allow for exact representation of conic surfaces, and the CAD business has a lot of software and know-how pertaining to B-Splines. For further reading and proofs we refer to the vast literature on the subject.
Splines are piecewise polynomial or rational functions and B-splines or NURBS is a particular nice basis for a spline space. We describe knot insertions and the de Boor algorithm to evaluate a spline curve, we give formulas for the differentiation of spline curves, and describe how conic sections can be given as rational spline curves.
We then describe tensor product spline surfaces and how a quadratic surface can be given as a rational tensor product spline surface.
We end by illustrating how splines can be used to interpolate or approximate discrete data and few words on tessellation and trimming of spline surfaces.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
7. Subdivision
Abstract
Subdivision curves and surfaces are defined as the limit of a sequence of successive refinements of a control polygon or mesh. There are in many cases a close connection to spline curves with a uniform knot vector and uniform tensor product surfaces. However, subdivision surfaces are useful in slightly different scenarios. Put briefly, subdivision is generally more useful for animation, and splines are more useful for geometric design.
First we study subdivision curves. Curve subdivision is simple to express using matrix multiplication, and we discuss the relation to spline curves and how an eigenanalysis can be used to find points on the limit curve (after infinitely many subdivision steps). Then we present a similar discussion but now for subdivision surfaces. Here the matrix representation is somewhat more difficult but still highly useful for analysis of the schemes. The most advanced theory we present is the characteristic map. It is a tool for analysis of whether subdivision schemes are tangent plane continuous in the limit.
Finally we turn to concrete subdivision schemes and discuss the Loop, Catmull–Clark, modified butterfly, \(\sqrt{3}\), and Doo–Sabin schemes. We end with a brief discussion of some advanced techniques and recent methods: parametrization, factorization, and polar subdivision.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
8. Curvature in Triangle Meshes
Abstract
In many cases notions from differential geometry can be usefully extended to piecewise planar surfaces, and this chapter covers curvature measures on triangle meshes. A frequently used principle is to obtain a smooth surface approximation and to estimate the curvature from this approximation. Alternatively, the integral of some curvature measures can be computed from a small region of the mesh and then normalized by dividing by the area of that region.
Following these principles, we first discuss how to extend the definition of a surface normal to the edges and vertices of a triangle mesh. Next, we cover the estimation of Gaußian and mean curvature on a triangle mesh. Finally, techniques for computing the shape operator are discussed—followed by a discussion on how to obtain the principal curvatures from the shape operator.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
9. Mesh Smoothing and Variational Subdivision
Abstract
In this chapter, we cover how meshes are smoothed. This is an important topic in geometry processing since acquired meshes are always subject to noise. The basic principles of signal processing are discussed. Then we present the principles behind Laplacian smoothing and Taubin smoothing, which is based on Laplacian smoothing but suffers less from shrinkage. However, Taubin smoothing causes distortion if the mesh is not highly regular in its structure. Mean curvature flow is much better in this regard.
Using spectral smoothing, it is possible to create filters that more accurately manipulate features of a certain scale. Spectral smoothing works by observing that the Laplace–Beltrami operator, which is central to many smoothing schemes, can be written as a linear operator whose eigenvectors form a function space upon which the vertex positions can be projected—very much like the Fourier basis on a regular grid.
Smoothing generally smooths sharp edges and corners. Fortunately, there are several schemes which remove noise while preserving features such as corners and edges.
Finally, we can see smoothing as an energy minimization and the chapter concludes with a discussion of variational subdivision which is based on repeated refinement and smoothing of meshes.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
10. Parametrization of Meshes
Abstract
Many algorithms rely on mesh parametrization. In particular, the mapping from a mesh to a 2D domain (and vice versa) is essential to rendering 3D models and an essential component of e.g. remeshing. In this chapter, we study several algorithms for such flattening of a patch of disk topology. The basic algorithm—quite similar to mesh smoothing—is introduced, and various vertex weights are covered, ranging from simple uniform weights to mean value and harmonic weights which result in less distortion. Finally, we discuss the so called natural boundary conditions which allow us to flatten the mesh with minimum angle distortion in the least squares sense.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
11. Simplifying and Optimizing Triangle Meshes
Abstract
Smoothing is only one of the processes we generally have to apply to acquired geometry. This chapter discusses several other important algorithms connected by virtue of being simple greedy processes where we improve the mesh by local changes to the mesh connectivity.
First, we discuss the popular scheme for mesh simplification due to Garland and Heckbert where edges are iteratively contracted according to a cost function stored in a priority queue. Next, we discuss various algorithms for improvement of meshes based on flipping an edge separating two triangles to the other diagonal of the quadrilateral formed by the two triangles. Greedy schemes may again be applied for mesh flip optimization, but we also consider the method of simulated annealing.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
12. Spatial Data Indexing and Point Location
Abstract
This chapter is concerned with spatial databases. Anyone designing algorithms for geometry processing will invariably need to store data in spatial databases. The chapter begins with an introduction to spatial databases and moves on to discuss particular data structures.
The kD tree for instance is a simple and very popular data structure for storing points in space. Essentially, a kD tree is a binary tree that recursively divides space into smaller regions. The same is true of a binary space partitioning tree, but the planes that divide space can be arbitrarily oriented, and a BSP tree is often used for triangles. Quadtrees and octrees divide space into four and eight sub-regions at each node and thus have a higher branching factor.
The chapter closes with a discussion of object-driven spatial access methods. The distinguishing characteristic of these is that objects are grouped as opposed to space being divided.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
13. Convex Hulls
Abstract
An object is convex if any two points inside it can be connected via a straight line that is entirely inside the object. This chapter opens with a discussion of convexity and then defines the convex hull: The tightest fitting convex region of space that covers a given object.
Initially, several algorithms for computing 2D convex hulls are considered and then methods for 3D convex hulls. In particular, we discuss an incremental algorithm where one adds a triangle at a time and the divide and conquer approach where the object is recursively divided until the computations are trivial. The essential part of the divide and conquer approach is to recursively merge the convex hulls of the parts.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
14. Triangle Mesh Generation: Delaunay Triangulation
Abstract
In this chapter, the generation of triangle meshes from points is illustrated via the Delaunay triangulation. Apart from Delaunay triangulation being the most common triangulation method, the aim is also to give an overview of the typical issues of point triangulation in general. As such the aspects of numerical accuracy and constraint triangulation are also covered. Central constructive proofs of Delaunay triangulation are covered along with the connection to Voronoi diagrams and convex hulls. The aim is that the student should be able to complete an exercise in performing Delaunay triangulation after this chapter; as such the flip algorithm is covered in some detail, as well as the geometric primitives in circle and left of. These primitives are the foundation of many triangulation algorithms. The arguably most efficient algorithm for 2D Delaunay triangulation, the divide and conquer algorithm, is also presented.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
15. 3D Surface Registration via Iterative Closest Point (ICP)
Abstract
The central theme of this chapter is surface registration, i.e. how to compute the correspondence between two surfaces, which are known to be overlapping or partially overlapping, w.r.t. the same underlying geometry. The algorithm presented to do this is the iterative closest point (ICP) algorithm, aimed at registering two individual 3D point sets. The ICP algorithm is covered in enough detail for the students to construct the algorithm as an exercise. The standard ICP algorithm is extended with an adapted version aimed at partially overlapping point sets. The chapter takes its outset in the merging of several partial surfaces, e.g. lasers scans, of a surface, and how to merge these into one. A methods for doing this is outlined, where registration is a central part, and references to the other tools are given, all covered elsewhere in this book.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
16. Surface Reconstruction using Radial Basis Functions
Abstract
Interpolation is a big topic in its own right. In this chapter, we discuss how interpolation can be applied to surface reconstruction. The simplest case is when we have a set of points in 2D with associated height values. Assuming these points are scattered (i.e. not aligned with a grid) a good way of interpolating the height values is using radial basis functions (RBF). Using the RBF method, we can obtain a smooth surface from points plus height. The RBF method has the attractive property that it is simple to implement, since it reduces to solving a single (albeit dense) linear system.
Reconstructing 3D surfaces is more challenging, but again the RBF method can be applied if we have points which are known to be both inside and outside as well as on the surface. The result is an implicit representation of the reconstructed object where the object is the set of points that have value zero with respect to the function produced by the RBF method.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
17. Volumetric Methods for Surface Reconstruction and Manipulation
Abstract
The RBF method (introduced in the previous chapter) involves solving a dense linear system. For huge numbers of points, this becomes too computationally demanding. Like the RBF method, volumetric methods for reconstruction produce an implicit representation of the reconstructed surface, but instead of solving a linear system, these methods proceed by solving a partial differential equation discretized on a 3D grid. Volumetric reconstruction algorithms become rather simple: essentially it boils down to repeatedly smoothing data on a 3D grid while keeping the values at some grid points constant. Having discussed the basic approach, we also explain how normals for point data can be estimated, since point normal estimates are generally required for volumetric reconstruction.
This chapter also covers the Level Set Method which, again, is based on the implicit representation of 3D surface using discrete 3D grids. However the LSM allows us to deform a surface. Distance fields are typically used as the input to the LSM and they have numerous other uses, so this chapter also covers the construction of 3D distance fields from triangle meshes.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
18. Isosurface Polygonization
Abstract
In the final chapter, we cover how to go from an implicit representation back to a triangle mesh. Since the methods in Chaps. 16 and 17 produce implicit surface representations, isosurface polygonization is essential to complete the reconstruction pipeline. We focus on the popular cell-based approaches where the volume is split into (typically cubical) regions and a polygonal approximation to the surface is computed for each cubical cell. The most famous of these algorithms is the table driven Marching Cubes algorithm. However, we also discuss the more recent dual contouring methods which arguably produce nicer meshes because they have more flexibility with regard to vertex placement.
Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs
Backmatter
Metadaten
Titel
Guide to Computational Geometry Processing
verfasst von
Jakob Andreas Bærentzen
Jens Gravesen
François Anton
Henrik Aanæs
Copyright-Jahr
2012
Verlag
Springer London
Electronic ISBN
978-1-4471-4075-7
Print ISBN
978-1-4471-4074-0
DOI
https://doi.org/10.1007/978-1-4471-4075-7

Premium Partner

    Bildnachweise