High qualitiy simplification and repair of polygonal models [Elektronische Ressource] / vorgelegt von Pavel Borodin

Pavel Borodin

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2009
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

High-Quality Simplification
and Repair
of Polygonal Models
Dissertation
zur Erlangung des Doktorgrades (Dr. rer. nat.)
der Mathematisch-Naturwissenschaftlichen Fakultat¨
der Rheinischen Friedrich-Wilhelms-Universitat¨ Bonn
vorgelegt von
Dipl.-Math. Pavel Borodin
aus Moskau
Bonn, Mai 2009Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen
Fakultat¨ der Rheinischen Friedrich-Wilhelms-Universitat¨ Bonn.
1. Gutachter: Prof. Dr. Reinhard Klein
2. Prof. Dr. Andreas Weber
Tag der mundlichen¨ Prufung:¨ 24. August 2009
Diese Dissertation ist auf dem Hochschulschriftenserver der Universitats-¨ und
Landesbibliothek Bonn (http://hss.ulb.uni-bonn.de/diss online) elektronisch
publiziert.
Erscheinungsjahr: 2009Acknowledgements
The work presented in this thesis has been produced within the scope of the
Computer Graphics group at the Institute of Computer Science II of the Uni-
versity of Bonn.
I wish to thank all the people who were directly or indirectly involved in
the creation of this work. First of all, I want to express my deepest gratitude
to Professor Reinhard Klein, the leader of the Computer Graphics group and
my scientific adviser, without whose patience and support this thesis would not
have been possible.
Furthermore, I thank all members of the Computer Graphics group, espe-
cially those with whom I had a pleasure of joint research and writing papers:
Marcin Novotni, Michael Guthe, Gabriel Zachmann and Alexander Greß. For
the same reason my thanks belong to Stefan Gumhold.
Our secretaries Simone von Neffe and Regina Haverkamp play an impor-
tant role in the life of our group, always ready to help and to sort out any
administrative issues, for what I am very grateful to both of them.
Finally, I want to thank DaimlerChrysler AG, the Stanford 3D Scanning
Repository, the Digital Michelangelo Project, the Virtual Try-On project and
Michael Beals, who created and/or provided many of the polygonal models
used in my research and, consequently, in this thesis.
iiiivAbstract
Because of the rapid evolution of 3D acquisition and modelling methods, highly
complex and detailed polygonal models with constantly increasing polygon
count are used as three-dimensional geometric representations of objects in
computer graphics and engineering applications. The fact that this particular
representation is arguably the most widespread one is due to its simplicity,
flexibility and rendering support by 3D graphics hardware. Polygonal models
are used for of objects in a broad range of disciplines like medical
imaging, scientific visualization, computer aided design, film industry, etc.
The handling of huge scenes composed of these high-resolution models
rapidly approaches the computational capabilities of any graphics accelerator.
In order to be able to cope with the complexity and to build level-of-detail
representations, concentrated efforts were dedicated in the recent years to the
development of new mesh simplification methods that produce high-quality ap-
proximations of complex models by reducing the number of polygons used in
the surface while keeping the overall shape, volume and boundaries preserved
as much as possible.
Many well-established methods and applications require “well-behaved”
models as input. Degenerate or incorectly oriented faces, T-joints, cracks and
holes are just a few of the possible degenaracies that are often disallowed by
various algorithms. Unfortunately, it is all too common to find polygonal mod-
els that contain, due to incorrect modelling or acquisition, such artefacts. Ap-
plications that may require “clean” models include finite element analysis, sur-
face smoothing, model simplification, stereo lithography. Mesh repair is the
task of removing artefacts from a polygonal model in order to produce an out-
put model that is suitable for further processing by methods and applications
that have certain quality requirements on their input.
This thesis introduces a set of new algorithms that address several partic-
ular aspects of mesh repair and mesh simplification. One of the two mesh re-
pair methods is dealing with the inconsistency of normal orientation, while an-
other one, removes the inconsistency of vertex connectivity. Of the three mesh
simplification approaches presented here, the first one attempts to simplify
polygonal models with the highest possible quality, the second, applies the
developed technique to out-of-core simplification, and the third, prevents self-
intersections of the model surface that can occur during mesh simplification.
vviContents
I Introduction and basics 1
1 Introduction 3
1.1 Motivation and problem statement . . . . . . . . . . . . . . . 3
1.2 Contributions and thesis structure . . . . . . . . . . . . . . . 4
1.2.1 Mesh repair . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Mesh simplification . . . . . . . . . . . . . . . . . . . 6
1.2.3 Thesis structure . . . . . . . . . . . . . . . . . . . . . 7
2 Basics on meshes and data structures 9
2.1 Polygonal meshes . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Mesh definition . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Mesh relations and operations . . . . . . . . . . . . . 14
2.1.3 Triangular meshes . . . . . . . . . . . . . . . . . . . 17
2.1.4 Application areas for meshes . . . . . . . . . . . . . . 18
2.2 Data structures and file formats for meshes . . . . . . . . . . . 18
2.2.1 Manifold mesh data structures . . . . . . . . . . . . . 20
2.2.2 Non-manifold mesh data structures . . . . . . . . . . 26
2.2.3 Our data structure . . . . . . . . . . . . . . . . . . . . 31
2.2.4 File formats . . . . . . . . . . . . . . . . . . . . . . . 33
II Mesh repair 39
3 Consistent orientation of normals 43
3.1 Description of the algorithm . . . . . . . . . . . . . . . . . . 45
3.1.1 Detection of patches . . . . . . . . . . . . . . . . . . 45
3.1.2 Calculation of boundary coherence . . . . . . . . . . 46
3.1.3 of visibility . . . . . . . . . . . . . . . . 47
3.1.4 Consistent orientation of patches . . . . . . . . . . . . 50
3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . 56
viiviii Contents
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Progressive gap closing 59
4.1 Vertex-edge contraction . . . . . . . . . . . . . . . . . . . . . 62
4.2 Description of the algorithm . . . . . . . . . . . . . . . . . . 65
4.2.1 Preprocessing phase . . . . . . . . . . . . . . . . . . 65
4.2.2 Decimation step . . . . . . . . . . . . . . . . . . . . 67
4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
III Mesh simplification 73
5 High-quality 77
5.1 Generalized pair contractions . . . . . . . . . . . . . . . . . . 78
5.1.1 Vertex-edge contraction . . . . . . . . . . . . . . . . 78
5.1.2 Vertex-triangle . . . . . . . . . . . . . . . 79
5.1.3 Edge-edge contraction . . . . . . . . . . . . . . . . . 80
5.2 Order of operations . . . . . . . . . . . . . . . . . . . . . . . 81
5.2.1 Non-accumulating error quadrics . . . . . . . . . . . 81
5.2.2 Handling of boundaries and sharp features . . . . . . . 83
5.3 Spatial search data structure . . . . . . . . . . . . . . . . . . 83
5.3.1 Simplex insertion and removal . . . . . . . . . . . . . 85
5.3.2 Distance-sorted nearest neighbour queries . . . . . . . 85
5.4 Description of the algorithm . . . . . . . . . . . . . . . . . . 86
5.4.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . 87
5.4.2 Decimation loop . . . . . . . . . . . . . . . . . . . . 88
5.4.3 Double queue strategy . . . . . . . . . . . . . . . . . 89
5.5 Preservation of normals and other surface properties . . . . . . 89
5.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.7 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6 Out-of-core simplification 97
6.1 Description of the algorithm . . . . . . . . . . . . . . . . . . 99
6.1.1 Cutting . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.1.2 Hierarchical simplification . . . . . . . . . . . . . . . 101
6.1.3 Stochastic . . . . . . . . . . . . . . . . 102
6.1.4 Stitching . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.3 Related-work . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110Contents ix
7 Intersection-free simplification 111
7.1 Dynamic spatial search data structure . . . . . . . . . . . . . 114
7.1.1 Simplex insertion and removal . . . . . . . . . . . . . 114
7.1.2 Spatial queries . . . . . . . . . . . . . . . . . . . . . 115
7.2 Initial clean-up of self-intersections . . . . . . . . . . . . . . 115
7.3 Detection and prevention of self-intersections . . . . . . . . . 116
7.3.1 Classification of collisions . . . . . . . . . . . . . . . 117
7.3.2 Efficient computation of collisions . . . . . . . . . . . 118
7.4 Avoidance of self-intersections . . . . . . . . .