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

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_chemnitz
• Publié le: 01 janvier 2006
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

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 . . . . . . . . . . . . . . . . 1