No d'ordre:

Pierre Kraemer

Description

Niveau: Supérieur

• mémoire

No d'ordre: 5795 THÈSE présentée à l'Université Louis Pasteur, Département d'Informatique Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection, UMR CNRS-ULP 7005 par Pierre KRAEMER pour l'obtention du grade de Docteur de l'Université Louis Pasteur de Strasbourg Mention Sciences Spécialité Informatique Modèles topologiques pour la multirésolution Soutenue le 12 novembre 2008 devant la commission d'examen composée de : M. Bruno LÉVY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Rapporteur externe Directeur de recherches à l'INRIA Lorraine M. Pascal LIENHARDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Rapporteur externe Professeur à l'Université de Poitiers M. Leif KOBBELT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Examinateur Professeur à l'Université d'Aix-La-Chapelle, Allemagne M. Jean-François DUFOURD . . . . . . . . . . . . . . . . . . . . . .

• accès adaptatif


• mention sciences


• département d'informatique laboratoire des sciences de l'image, de l'informatique et de la télédétection


• multirésolution


• classiques des maillages progressifs


• extension multirésolution des cartes combinatoires


• spécialité informatique


• carte multirésolution


• surfaces de subdivision

Sujets

• Mémoire
• Krämer
• Université de Poitiers
• 5024 Bechmann
• Louis Pasteur University
• Allemagne

Informations

• Publié par: profil-nechor-2012
• Publié le: 01 novembre 2008
• Nombre de lectures: 28
• Langue: Français
• Poids de l'ouvrage: 13 Mo

Extrait

oN d’ordre: 5795
THÈSE
présentée à
l’Université Louis Pasteur, Département d’Informatique
Laboratoire des Sciences de l’Image, de l’Informatique et de la Télédétection,
UMR CNRS-ULP 7005
par
Pierre KRAEMER
pour l’obtention du grade de
Docteur de l’Université Louis Pasteur de Strasbourg
Mention Sciences
Spécialité Informatique
Modèles topologiques pour la multirésolution
Soutenue le 12 novembre 2008 devant la commission d’examen composée de :
M. Bruno LÉVY ......................................Rapporteur externe
Directeur de recherches à l’INRIA Lorraine
M. Pascal LIENHARDT .............................Rapporteur externe
Professeur à l’Université de Poitiers
M. Leif KOBBELT .........................................Examinateur
Professeur à l’Université d’Aix-La-Chapelle, Allemagne
M. Jean-François DUFOURD .......................Rapporteur interne
Professeur à l’Université Louis Pasteur de Strasbourg
Mme Dominique BECHMANN ..................... Directrice de thèse
Professeure à l’Université Louis Pasteur de Strasbourg
M. David CAZIER .........................................Examinateur
Maître de conférences à l’Université Louis Pasteur de StrasbourgTable des matières
Introduction 1
1 Contexte et objectif . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Surfaces de subdivision . . . . . . . . . . . . . . . . . . . 4
2.2 Maillages progressifs . . . . . . . . . . . . . . . . . . . . 5
3 Plan du mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . 5
I Modèle topologique multirésolution 7
1 Modèles de représentation multirésolution 9
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Modèles topologiques standards . . . . . . . . . . . . . . . . . . 10
1.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Cartes combinatoires . . . . . . . . . . . . . . . . . . . . 17
1.3 Modèles multirésolution . . . . . . . . . . . . . . . . . . . . . . 32
1.3.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.3.2 Maillages progressifs . . . . . . . . . . . . . . . . . . . . 33
1.3.3 Multi-Triangulation . . . . . . . . . . . . . . . . . . . . . 37
1.3.4 Quadtrees . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.3.5 Pyramides de cartes . . . . . . . . . . . . . . . . . . . . 42
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2 Extension multirésolution des cartes combinatoires 47
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47iv Table des matières
2.2 Extension multirésolution . . . . . . . . . . . . . . . . . . . . . 48
2.2.1 Ensembles de brins . . . . . . . . . . . . . . . . . . . . . 48
2.2.2 Relations indexées . . . . . . . . . . . . . . . . . . . . . 49
2.2.3 Hypercarte multirésolution . . . . . . . . . . . . . . . . . 51
2.2.4 2-carte multirésolution . . . . . . . . . . . . . . . . . . . 52
2.3 Opérateurs de manipulation . . . . . . . . . . . . . . . . . . . . 53
2.3.1 Opérateurs de base . . . . . . . . . . . . . . . . . . . . . 53
2.3.2 Opérateurs de haut niveau . . . . . . . . . . . . . . . . . 55
2.4 Mise-en-œuvre pratique . . . . . . . . . . . . . . . . . . . . . . . 62
2.4.1 Implantation des 2-cartes. . . . . . . . . . . . . . . . . . 63
2.4.2 Implantation des 2-cartes multirésolution . . . . . . . . . 66
II Applications géométriques 71
3 Surfaces de subdivision multirésolution 73
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.1.1 Surfaces de subdivision . . . . . . . . . . . . . . . . . . . 74
3.1.2 L’édition multirésolution . . . . . . . . . . . . . . . . . . 78
3.1.3 Obtention d’une surface de subdivision multirésolution . 82
3.1.4 Support du maillage multirésolution . . . . . . . . . . . . 84
3.2 Génération des niveaux . . . . . . . . . . . . . . . . . . . . . . . 85
3.2.1 Génération régulière . . . . . . . . . . . . . . . . . . . . 85
3.2.2 Génération adaptative . . . . . . . . . . . . . . . . . . . 99
3.2.3 Simplification . . . . . . . . . . . . . . . . . . . . . . . . 106
3.2.4 Critère de subdivision . . . . . . . . . . . . . . . . . . . 108
3.2.5 Mise à jour du maillage. . . . . . . . . . . . . . . . . . . 111
3.2.6 Niveaux de subdivision des cellules . . . . . . . . . . . . 114
3.3 Accès aux niveaux . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.3.1 Accès régulier . . . . . . . . . . . . . . . . . . . . . . . . 120
3.3.2 Accès adaptatif . . . . . . . . . . . . . . . . . . . . . . . 121
3.3.3 Affichage d’une 2-carte adaptative . . . . . . . . . . . . . 125
3.4 Schémas de subdivision originaux . . . . . . . . . . . . . . . . . 129
3.4.1 Le schéma Quad/Triangle . . . . . . . . . . . . . . . . . 129√
3.4.2 Le schéma 3 . . . . . . . . . . . . . . . . . . . . . . . . 132
3.5 Comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.5.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.5.2 Complexité en temps . . . . . . . . . . . . . . . . . . . . 144
3.5.3 Complexité en espace . . . . . . . . . . . . . . . . . . . . 147
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4 Maillages progressifs 153
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153Table des matières v
4.2 Applications des maillages progressifs multirésolution . . . . . . 155
4.2.1 Filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.2.2 Compression . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.3 Supports topologiques classiques des maillages progressifs . . . . 161
4.4 Utilisation des cartes multirésolution . . . . . . . . . . . . . . . 162
4.4.1 Gestion des ensembles de brins . . . . . . . . . . . . . . 162
4.4.2 Gestion des coutures . . . . . . . . . . . . . . . . . . . . 165
4.4.3 Vérification des contraintes topologiques . . . . . . . . . 167
4.4.4 Contractions groupées . . . . . . . . . . . . . . . . . . . 171
4.4.5 Economies de mémoire . . . . . . . . . . . . . . . . . . . 173
4.4.6 Application aux algorithmes de traitement de la géométrie175
4.4.7 Accès au maillage . . . . . . . . . . . . . . . . . . . . . . 180
4.4.8 Comparaison du coût mémoire . . . . . . . . . . . . . . . 182
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Conclusion 189
1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Liste des figures 195
Bibliographie 200Introduction
1 Contexte et objectif
En modélisation géométrique, l’amélioration de la représentation et de la ma-
nipulation des objets géométriques est un enjeu dont l’objectif est de met-
tre en avant différentes propriétés de ces objets, et de rendre possibles dif-
férentes méthodes d’interaction et d’édition de ces objets. L’un des modes de
représentation usuels consiste à décomposer les objets en cellules de différentes
dimensions (sommets, arêtes, faces, ...) partageant entre elles des relations
d’adjacence et d’incidence.
Dans le cadre d’applications de modélisation ou de traitement de la géométrie
surdetelsobjets,oùlasouplesseetl’efficacitédelareprésentationsous-jacente
sont primordiales, le modèle des cartes combinatoires [Edm60, Vin83, Lie89,
Lie91] constitue une référence. Le choix de ce modèle, dit à base topologique,
est d’autant plus pertinent face aux structures ad hoc qui existent dans la lit-
tératurequesonsoclemathématiquepermetaussibienlagarantiedecertaines
propriétéssurlesobjetsreprésentésqu’unedéfinitionconsistanteendimension
arbitraire.
Danslecadredelamodélisationmultirésolution[FIQ02,DFS04],ladécomposi-
tiondesobjetsencellulesesteffectuéeàdesniveauxdedétailouderaffinement2 Introduction
Figure 1 - Exemple d’application d’une représentation multirésolution
surfacique : plus l’objet est distant, plus le maillage utilisé pour l’affichage
est grossier
différents. Cette représentation multi-échelles a de nombreuses applications en
informatique graphique. Suivant les cas, elle sert à accélérer des traitements
existants tels que l’affichage, comme illustré dans la figure 1 où plus l’objet
à afficher est éloigné du point de vue de l’utilisateur, plus le maillage utilisé
pour l’affichage est simplifié, accélérant d’autant l’exécution de la procédure
d’affichage.
Dans d’autres applications, cette représentation constitue le support d’outils
puissants de traitement et de manipulation de la géométrie, tels que l’édition
multirésolution de surfaces de subdivision [Zor05] qui perm