Capturing the essence of shape of polygonal meshes [Elektronische Ressource] / von Tobias Isenberg

Tobias Isenberg

Sujets

• Informatik
• Mathematics

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2004
• Nombre de lectures: 46
• Langue: English
• Poids de l'ouvrage: 30 Mo

Extrait

Capturing the Essence of Shape
of Polygonal Meshes
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieur (Dr.-Ing.)
angenommen durch die Fakult¨at fu¨r Informatik
der Otto-von-Guericke-Universitat Magdeburg¨
von
Dipl.-Inf. Tobias Isenberg
geboren am 14.Dezember1974 in Gardelegen
Gutachter: Prof. Dr. Thomas Strothotte
Prof. Dr. Kees van Overveld
Prof. Dr. Hans Hagen
Ort und Datum des Promotionskolloquiums:
Magdeburg, 16.April2004c 2004 by Tobias Isenberg. All rights reserved.Fur Johanna Jellen.¨
In Erinnerung an
Kathe und Wilhelm Isenberg¨
und Herbert Jellen.Abstract/Zusammenfassung
Geometric models are the basis of computer graphics. Due to the growing computing
power and hardware support more and increasingly complex models are created. In
order to efficiently store, evaluate, manipulate, and match these, it is necessary to cap-
ture and extract the essence of shape. In particular for polygonal models, a concept
is developed that allows adaptation of the notion of importance to the specific appli-
cation without changing the extraction algorithm itself. For the use with this concept,
a variety of criteria are described and conceived that capture what commonly is con-
sidered to be important in a polygonal mesh. In addition, an algorithm is developed
within the concept that allows extraction of external skeletons as one aspect of essence
of shape. Moreover, it is demonstrated that the concept also covers different notions of
shape such as silhouettes. Since these have different application-specific requirements,
a different algorithm is presented for fulfilling them. Finally, the methods that were
presented are discussed with respect to potential application areas and a number of
examples are shown.
Geometrische Modelle bilden die Basis der Computergraphik. Aufgrund st¨andig wach-
sender Rechenkapazitat und steigender Hardwareunterstutzung werden immer mehr¨ ¨
und zunehmend komplexere Modelle erzeugt. Um diese effizient speichern, evaluieren,
manipulieren und miteinander vergleichen zu k¨onnen ist es notwendig, das Wesentliche
der Form von Objekten zu finden und zu extrahieren. Insbesondere fur polygonale¨
Modelle wird ein Konzept entwickelt, das es erlaubt, die Notation von Wichtigkeit
an die spezifische Anwendung anzupassen, ohne den Extraktionsalgorithmus selbst zu
ver¨andern. Es werden eine Reihe von Kriterien fu¨r die Verwendung innerhalb dieses
Konzeptes beschrieben und neu entworfen. Diese werden verwendet, um Strukturen
entsprechend der u¨blichen Auffassung von wichtigen Merkmalen in polygonalen Mod-
ellenzufinden. DesweiterenwirdentsprechenddesKonzepteseinAlgorithmusentwick-
elt, der externe Skelette als einen Aspekt von wesentlichen Formmerkmalen extrahiert.
Außerdemwirdgezeigt,daßdasKonzeptauchandereFormmerkmalewiebeispielsweise
Silhouetten beinhaltet. Da diese andere anwendungsbezogene Anforderungen haben,
wirdeinentsprechenderAlgorithmuspr¨asentiert,derdieseerfu¨llt. Abschließendwerden
dievorgestelltenMethodeninBezugaufihremoglichenAnwendungsgebieteuntersucht¨
und eine Anzahl von Beispielanwendungen vorgestellt.Preface
This dissertation is the result of my research work at the Department of Simulation
and Graphics at the Faculty of Computer Science of the Otto-von-Guericke University
of Magdeburg. I was advised by Prof. Strothotte to whom I am very grateful for giving
me this opportunity and from whom I learned a lot.
I also thank my external reviewers Prof. Hans Hagen and Prof. Kees van Overveld for
unhesitantly taking on the review as well as for their constructive criticism and helpful
comments.
I would like to thank my parents and my grandmother for the support and encourage-
ment they have always provided me. Without them this thesis would not have been
possible. I thank my girlfriend Petra first of all for being a great friend and support,
but also for the joint work on funny elephants, for her contribution to OpenNPAR,
and for the beautiful model of the pitcher of a Nepenthes alata plant.
I am very grateful to Stefan Schlechtweg for many discussions throughout the whole
time I was working on the dissertation and for giving a lot of valuable advice during
the writing process. In addition, I would like to thank Henry Konig for sharing the¨
++office with me and always offering his help and his tremendous knowledge of C
programming and debugging. Nick Halper, Roland Jesse, Henry Sonnet, Felix Ritter,
andMarcelG¨otzedeservemythanksforourjointworkonnon-photorealisticrendering
and the OpenNPAR system. In this context I must not forget to name my students
Angela Brennecke, Johannes Zander, and Bernd Nettelbeck and thank them for their
contributions toOpenNPAR.
Stefan Schirra helped me by answering many questions on theoretical concepts, com-
putational complexities, and notation as well as Michiel Smid with notation problems
and with proofreading the dissertation. I also thank Klaus Sachs-Hombach for the in-
teresting discussiononthe notionof theterm‘shape’. Fortakingthe timetoproofread
the whole or parts of the dissertation I am very thankful to Lissa Janoski, Andreas
Raab, Wallace Chigona, and Niklas R¨ober.
Last but certainly not least I am very grateful for the great environment provided
by the Department of Simulation and Graphics. In particular, thanks for the many
questionsansweredandthemanyproblemssolvedbyPetraJanka,PetraSpecht,Beate
Traor´e, and Sylvia Zabel in the department’s office.Preface
The work and parts of this thesis including the framework OpenNPAR were devel-
oped in collaboration with the following people: Angela Brennecke, Sheelagh Carpen-
dale, Marcel Gotze, Nick Halper, Roland Jesse, Bernd Nettelbeck, Petra Neumann,¨
Felix Ritter, Henry Sonnet, Thomas Strothotte, and Johannes Zander (for details see
Table A.1). Parts of this thesis have have been published or submitted for publication
+ +as [IHS02], [HIR 03], [IFH 03], [IHK03], [JI03], [SIDS03], [BI04], [GNIS04], [JINS04],
and [ZISS04].
ivTable of Contents
Abstract i
Preface iii
1 Introduction 1
1.1 Motivation and Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Structure of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Essence of Shape 7
2.1 Shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Motivation and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Requirements of an Essential Shape Representation . . . . . . . . . . . 10
2.4 Essential Shape Representations for Polygonal Models . . . . . . . . . . 12
2.5 ESR Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.1 Geometric vs. Non-Geometric Criteria . . . . . . . . . . . . . . 14
2.5.2 Geometric Criteria for Abstraction of Form. . . . . . . . . . . . 15
2.5.3 Geometric Criteria for Surface Details . . . . . . . . . . . . . . 15
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Approaches to Capturing Geometric Features of Shapes 17
3.1 Mathematical Concepts for Shape Abstraction . . . . . . . . . . . . . . 17
3.1.1 Voronoi Diagrams and Medial Axes . . . . . . . . . . . . . . . . 18
3.1.2 Reeb Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Feature Line Extraction from Discrete Data Representations . . . . . . 27
3.2.1 Skeletons from 2D Pixel Images . . . . . . . . . . . . . . . . . . 28
3.2.2 Skeletons from Volumetric Data . . . . . . . . . . . . . . . . . . 29
3.3 Extracting Internal Features from Boundary Representations . . . . . . 33
3.3.1 Medial Surface or Voronoi Diagram Based Algorithms . . . . . . 34
3.3.2 Edge Collapse Based Algorithms . . . . . . . . . . . . . . . . . 35
3.3.3 Radial Basis Function Approach . . . . . . . . . . . . . . . . . . 39
3.3.4 Skeletons From Point Clouds . . . . . . . . . . . . . . . . . . . 40
3.4 External Feature Extraction from Boundary Representations . . . . . . 42
3.4.1 Feature Lines Based on Approximated Curvature . . . . . . . . 42
3.4.2 External Feature Lines From Internal Skeletons . . . . . . . . . 45Preface
3.4.3 Approach Requiring User Interaction . . . . . . . . . . . . . . . 46
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Degree of Interest Functions 49
4.1 Concept and Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.1 Degree of Interest and Extreme Ridges . . . . . . . . . . . . . . 49
4.1.2 Discrete DoI Functions . . . . . . . . . . . . . . . . . . . . . . . 52
4.1.3 Determining the Discrete Curvature of Polygonal Meshes . . . . 53
4.1.4 Simple DoIs Based on Principal Curvature . . . . . . . . . . . . 55
4.2 Heuristic DoI Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Modified Shape Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3.1 Shape Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3.2 Modifications to Emphasize Ridges and Ruts . . . . . . . . . . . 58
4.4 Fold Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5 Singularity Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.6 DoI Functions for Adaptive Subdivision . . . .