Geometric processing of CAD data and meshes as input of integral equation solvers [Elektronische Ressource] / by Maharavo Randrianarivony
217 Pages
English

Geometric processing of CAD data and meshes as input of integral equation solvers [Elektronische Ressource] / by Maharavo Randrianarivony

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

GEOMETRIC PROCESSING OF CADDATA AND MESHES AS INPUT OFINTEGRAL EQUATION SOLVERSbyMaharavo RandrianarivonyJune 25, 2006Supervisor: Prof. Dr. Guido BrunnettCOMPUTER SCIENCE FACULTY¨TECHNISCHE UNIVERSITAT CHEMNITZiiiiiAcknowledgmentI would like to express my sincere appreciation to my advisor Prof.Guido Brunnett for his guidance during the preparation of this thesis. The fre-quent discussions with him have tangibly improved my knowledge in CAGD.He has helped me a lot during the conception of most geometric approaches es-pecially about decomposition of CAD surfaces into four-sided subsurfaces andtreatment of diffeomorphisms by means of transfinite interpolations using Coonsand Gordon patches. Special acknowledgment is granted to him for taking thetime to correct my ideas as well as my misspellings in several former drafts ofsome chapters. The financial assistance that he offered me is also very muchappreciated.IamalsogratefultoProf. ReinholdSchneiderwhohasdeveloppedhisexplanations of the required surface representations for his mesh-free numericalmethods of integral equations. Thanks are equally due to Dr. Helmut Harbrechtwith whom I have had several discussions which greatly helped me to have adeeper insight about the wavelet Galerkin scheme.Special thanks go to the Computer Graphic Group which has pro-vided me with computing equipments that helped me implement the proposedapproaches.

Subjects

Informations

Published by
Published 01 January 2006
Reads 12
Language English
Document size 4 MB

GEOMETRIC PROCESSING OF CAD
DATA AND MESHES AS INPUT OF
INTEGRAL EQUATION SOLVERS
by
Maharavo Randrianarivony
June 25, 2006
Supervisor: Prof. Dr. Guido Brunnett
COMPUTER SCIENCE FACULTY
¨TECHNISCHE UNIVERSITAT CHEMNITZiiiii
Acknowledgment
I would like to express my sincere appreciation to my advisor Prof.
Guido Brunnett for his guidance during the preparation of this thesis. The
frequent discussions with him have tangibly improved my knowledge in CAGD.
He has helped me a lot during the conception of most geometric approaches
especially about decomposition of CAD surfaces into four-sided subsurfaces and
treatment of diffeomorphisms by means of transfinite interpolations using Coons
and Gordon patches. Special acknowledgment is granted to him for taking the
time to correct my ideas as well as my misspellings in several former drafts of
some chapters. The financial assistance that he offered me is also very much
appreciated.
IamalsogratefultoProf. ReinholdSchneiderwhohasdeveloppedhis
explanations of the required surface representations for his mesh-free numerical
methods of integral equations. Thanks are equally due to Dr. Helmut Harbrecht
with whom I have had several discussions which greatly helped me to have a
deeper insight about the wavelet Galerkin scheme.
Special thanks go to the Computer Graphic Group which has
provided me with computing equipments that helped me implement the proposed
approaches. Additional thanks are due to the Computer Science Faculty of the
Technische Universita¨t Chemnitz for giving me an environment where I could
pursue my research.
Last but not the least, I thank my sister Lova who has given me
moral supports during the frustrating period of working on this thesis.ivv
Abstract
Among the presently known numerical solvers of integral equations, two main
categories of approaches can be traced:
• Mesh-free approaches
• Mesh-based approaches.
We will propose some techniques to process geometric data so that they can
be efficiently used in subsequent numerical treatments of integral equations. In
order to prepare geometric information so that the above two approaches can be
automatically applied, we need the following items.
• Splitting a given surface Γ into several four-sided patches Γ .i
• Generating a diffeomorphismγ from the unit square to Γ .i i
• Generating a meshM on a given surface.
• Patching of a given triangulation.
NIn order to have a splitting Γ = ∪ Γ , we need to approximate the surfacesii=1
first by polygonal regions. We use afterwards quadrangulation techniques by
removing quadrilaterals repeatedly. We will generate the diffeomorphisms by
means of transfinite interpolations of Coons and Gordon types.
The generation of a meshM from a piecewise Riemannian surface will use some
generalized Delaunay techniques in which the mesh size will be determined with
the help of the Laplace-Beltrami operator.
We will describe our experiences with the IGES format because of two reasons.
First, most of our implementations have been done with it. Next, some of the
proposed methodologies assume that the curve and surface representations are
similar to those of IGES.
Patching ameshconsistsinapproximatingorinterpolatingitbyasetofpractical
surfaces such as B-spline patches. That approach proves useful when we want to
utilize a mesh-free integral equation solver but the input geometry is represented
as a mesh.viContents
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
List of figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
1 INTRODUCTION 1
1.1 Brief reminder about integral equations . . . . . . . . . . . . . . . 1
1.1.1 Wavelet Galerkin method . . . . . . . . . . . . . . . . . . . 3
1.1.2 Mesh-based method . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Challenges of geometric processing . . . . . . . . . . . . . . . . . . 5
1.3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Chapter 2: Building an adjacency model from an IGES
format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Chapter 3: Decomposing a surface into four-sided patches . 8
1.3.3 Chapter 4: Constructing diffeomorphic reparametrization . 9
1.3.4 Chapter 5: Mesh generation . . . . . . . . . . . . . . . . . . 10
1.3.5 Chapter 6: Paving of meshes by four-sided patches . . . . . 12
2 IGES FORMAT AND SURFACE STRUCTURES 13
2.1 Geometric storage and transmission . . . . . . . . . . . . . . . . . 13
2.1.1 CAD interface usage . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 IGES as a CAD neutral format . . . . . . . . . . . . . . . . 14
2.2 IGES file structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Entity classification and data types . . . . . . . . . . . . . . 15
2.2.2 IGES file organization . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Shortcomings and proposed remedies . . . . . . . . . . . . . 18
2.3 Segment separators . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Features of the implementation . . . . . . . . . . . . . . . . . . . . 21
2.5 Practical experiences and CAD flaws . . . . . . . . . . . . . . . . . 22
2.6 Surface structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.1 Topological structure . . . . . . . . . . . . . . . . . . . . . . 24
2.6.2 Metric structure . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7 Other CAD interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 27
viiviii CONTENTS
3 FOURSIDED SPLITTING 29
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Problem setting and general approach . . . . . . . . . . . . . . . . 31
3.3 Polygonal regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Removing a quadrilateral from a simple polygon . . . . . . . . . . 35
3.5 Toward multiply connected polygons . . . . . . . . . . . . . . . . . 38
3.6 Quadrilating multiply connected polygons . . . . . . . . . . . . . . 46
3.7 Cut search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.1 Cuts having extreme vertices . . . . . . . . . . . . . . . . . 50
3.7.2 Cuts having nonextreme vertices . . . . . . . . . . . . . . . 50
3.7.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.8 Conversion into convex quadrangulation . . . . . . . . . . . . . . . 54
3.9 Cleanup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.9.1 Quality control . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.9.2 Cleanup operations . . . . . . . . . . . . . . . . . . . . . . . 57
3.10 Converting a triangulation into a quadrangulation . . . . . . . . . 58
3.11 Regions having curved boundaries . . . . . . . . . . . . . . . . . . 61
3.12 Structure of the polygonal model . . . . . . . . . . . . . . . . . . . 61
3.12.1 Discretization of curved boundaries . . . . . . . . . . . . . . 62
3.12.2 Edge splitting . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.3 Even polygonal approximation . . . . . . . . . . . . . . . . 63
3.13 Metric aspect of the polygonal model . . . . . . . . . . . . . . . . . 65
3.13.1 Discretization artifact . . . . . . . . . . . . . . . . . . . . . 65
3.13.2 Edge quality . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.13.3 Polygonal approximation . . . . . . . . . . . . . . . . . . . 67
3.14 Postprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.14.1 Boundary replacement . . . . . . . . . . . . . . . . . . . . . 68
3.14.2 Boundary interference . . . . . . . . . . . . . . . . . . . . . 69
13.14.3 Treating G vertices . . . . . . . . . . . . . . . . . . . . . . 72
3.14.4 Subdivision for diffeomorphisms . . . . . . . . . . . . . . . 74
3.15 Summarizing algorithm . . . . . . . . . . . . . . . . . . . . . . . . 75
3.16 Special splittings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
13.16.1 All G vertices . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.16.2 Simple polygons . . . . . . . . . . . . . . . . . . . . . . . . 76
3.17 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4 MAPPING REGULARITY 91
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2 Transfinite interpolation and problem setting . . . . . . . . . . . . 92
4.3 First sufficient condition . . . . . . . . . . . . . . . . . . . . . . . . 95
4.4 Second sufficient condition . . . . . . . . . . . . . . . . . . . . . . . 99
4.5 Sufficient and necessary condition . . . . . . . . . . . . . . . . . . . 100
4.5.1 Subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5.2 Adaptivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 103CONTENTS ix
4.6 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.7 Mapping search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.7.1 Overspill phenomenon . . . . . . . . . . . . . . . . . . . . . 109
4.7.2 Gordon patch . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.8 Generation of internal curves . . . . . . . . . . . . . . . . . . . . . 110
4.8.1 Finding the internal points x . . . . . . . . . . . . . . . . 111ij
4.8.2 Generating the interpolating curves . . . . . . . . . . . . . 113
4.9 Diffeomorphic Gordon and termination guarantee . . . . . . . . . . 114
4.10 Practical results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 MESH GENERATION 121
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.2 Definitions and problem setting . . . . . . . . . . . . . . . . . . . . 122
5.3 Motivation for the planar case . . . . . . . . . . . . . . . . . . . . . 124
5.4 Meshing using the first fundamental form . . . . . . . . . . . . . . 127
5.4.1 Splitting according to first fundamental form . . . . . . . . 127
5.4.2 Flipping according to first fundamental form . . . . . . . . 128
5.5 Initial coarse mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.6 Nonsmooth boundary approximation . . . . . . . . . . . . . . . . . 129
5.7 Determination of the edge size function . . . . . . . . . . . . . . . 131
5.8 Meshing of a surface with multiple patches . . . . . . . . . . . . . 133
5.9 Discretization of the curved boundaries . . . . . . . . . . . . . . . 133
5.10 Theoretical discussion . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.11 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
06 C -PAVING OF MESHES BY
QUADRILATERAL PATCHES 147
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.3 Handle decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.4 Preliminary search for canonical curves. . . . . . . . . . . . . . . . 151
6.4.1 Normalized canonical form . . . . . . . . . . . . . . . . . . 151
6.4.2 Numerical realization . . . . . . . . . . . . . . . . . . . . . 154
6.4.3 Bases of the fundamental group . . . . . . . . . . . . . . . . 155
6.4.4 Homotopic transformation . . . . . . . . . . . . . . . . . . . 156
6.5 Improvements of the canonical curves . . . . . . . . . . . . . . . . 158
6.5.1 Weighted split graph . . . . . . . . . . . . . . . . . . . . . . 159
6.5.2 Improvement algorithm . . . . . . . . . . . . . . . . . . . . 159
6.6 Paving into quadrilateral patches . . . . . . . . . . . . . . . . . . . 160
6.6.1 Mesh parametrization . . . . . . . . . . . . . . . . . . . . . 161
6.6.2 Splitting into four-sided submeshes . . . . . . . . . . . . . . 163
06.7 Surface fitting withC -joint . . . . . . . . . . . . . . . . . . . . . . 164
6.8 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167x CONTENTS
A NUMERICAL TOPOLOGY 173
A.1 Simplicial complexes . . . . . . . . . . . . . . . . . . . . . . . . . . 173
A.2 Boundary operator and incidence matrix . . . . . . . . . . . . . . . 174
A.3 Homology group . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
B CURVES ON SURFACES 177
B.1 Topological surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . 177
B.2 Classification of surfaces . . . . . . . . . . . . . . . . . . . . . . . . 179
B.3 Fundamental group . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
B.4 Reidemeister moves . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
BIBLIOGRAPHY i