No d'ordre:

De
Publié par

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


Publié le : samedi 1 novembre 2008
Lecture(s) : 27
Source : scd-theses.u-strasbg.fr
Nombre de pages : 214
Voir plus Voir moins

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 permet de déformer une
surface à des échelles différentes et ce de manière naturelle et cohérente rel-
ativement aux détails de l’objet. La compression de maillages ou encore la
suppression de bruit [GSS99] sont d’autres applications qui s’appuient sur une
tellereprésentation.Afindepouvoirs’exécuterdemanièreoptimaleetpourun
large éventail de types d’objets différents, tous ces algorithmes de traitement
de la géométrie ont besoin d’un support topologique efficace et général pour
la représentation des maillages sous-jacents.Contributions 3
Nous nous intéressons dans cette thèse aux modèles et structures de données
utilisées pour la représentation de maillages multirésolution. Comme nous le
verrons, les modèles existants, généralement basés sur la représentation con-
jointe d’un maillage courant encodé dans une structure standard et d’un en-
semble de nœuds de modification, présentent de nombreux défauts. Ceux-ci
sont principalement dus à l’absence de représentation de l’ensemble des cel-
lules de la subdivision de l’objet modélisé au sein d’une structure topologique
complète.
2 Contributions
Compte tenu des avantages que présente le modèle des cartes combinatoires,
ce dernier nous est apparu comme un point de départ de choix pour l’élabora-
tion d’un nouveau modèle de représentation multirésolution capable de répon-
dre aux contraintes imposées par les applications prenant appui sur de telles
représentations et de proposer des solutions aux défauts que présentent les
structures existantes.
Nousproposonsdanscettethèseuneextensionmultirésolutiondescartescom-
binatoires permettant la représentation multi-échelles d’objets géométriques.
Une carte multirésolution peut être vue comme une hiérarchie de cartes com-
binatoires imbriquées les unes dans les autres. Chaque niveau de résolution
de l’objet représenté est ainsi défini par une carte combinatoire. On bénéfi-
cie donc ici à chaque niveau de toutes les propriétés intéressantes des cartes, à
savoirlagénéralitédelareprésentation,l’efficacitédesalgorithmesdeparcours
des maillages représentés et la légèreté des structures de données dérivées du
modèle. En effet, le modèle est défini en dimension arbitraire et peut représen-
ter des partitions cellulaires quelconque, quel que soit le niveau de résolution
considéré. A tout niveau, les requêtes de voisinage sont exécutées de manière
optimale. Enfin, le coût mémoire de la structure de données dérivée du modèle
est comparable à celui des structures multirésolution classiquement utilisées.
Cettestructurededonnéesaétéimplantéeaucœurd’unmodeleurgéométrique
fondésuruneimplantationgénériquedescartescombinatoiresdéveloppéedans
notreéquipe.Endimension2,c’est-à-diredanslecadredelareprésentationde
maillages surfaciques, nous avons choisi deux cadres applicatifs différents afin
d’illustrer les avantages de notre modèle par rapport à l’existant : les surfaces
de subdivision multirésolution, et les maillages progressifs.4 Introduction
2.1 Surfaces de subdivision
Les surfaces de subdivision multirésolution ont été notre sujet d’étude princi-
pal. Une surface de subdivision est définie comme la limite d’une séquence de
maillages raffinés successivement. Un schéma de subdivision définit les règles
selon lesquelles ce raffinement est appliqué à partir d’un maillage de départ
donné. On peut distinguer ici deux étapes : d’abord, la topologie du mail-
lage est raffinée, puis de nouvelles informations géométriques sont associées au
maillage obtenu. Celles-ci sont calculées en appliquant des masques locaux sur
le maillage d’origine. Il existe un certain nombre de schémas qui, opérant sur
des maillages constitués de types de cellules différents, génèrent des surfaces
aux propriétés géométriques différentes.
Danslecadredel’éditionmultirésolutiondesurfacesdesubdivision,descoeffi-
cients de détail sont introduits entre les différents maillages correspondant aux
étapes de la subdivision, que l’on appelle alors niveaux de résolution. En édi-
tantlemaillageàunniveaudonné,onappliqueunedéformationplusoumoins
globale à la surface, en conservant les détails de l’objet de manière cohérente.
Par rapport aux structures basées sur des arbres de faces habituellement util-
isées dans ce cadre, les cartes multirésolution apportent ici de nombreux avan-
tages. Là où les structures classiques doivent être déclinées en plusieurs ver-
sionsspécifiques,lagénéralitédenotremodèleautorisel’utilisationd’unmême
noyau avec des algorithmes de subdivision travaillant sur des cellules de types
différents. Ainsi, nous avons implanté efficacement les algorithmes de Loop
[Loo87] (quadrisection de triangles), Catmull-Clark [CC78] (quadrisection de√
quadrilatères), Doo-Sabin [DS78] (subdivision duale) et le schéma 3 [Kob00]
qui opère une trisection de triangles suivie de basculements d’arêtes. Plusieurs
types de subdivision peuvent même être utilisés simultanément au sein d’un
même objet, tel qu’illustré avec l’implantation du schéma quad-triangle [SL03]
qui conserve à la fois des triangles et des quadrilatères dans le maillage.
Dans une carte multirésolution, la subdivision adaptative, c’est-à-dire le raf-
finement à une profondeur variable suivant les zones d’intérêt de l’objet, ne
compromet pas la consistance topologique du maillage. Dans les structures à
base d’arbres, une telle subdivision engendre des trous topologiques au niveau
des frontières entre les zones ayant des profondeurs différentes. Cela résulte du
faitquenotremodèlenemanipulepasdirectementuneseuleentitétopologique
(enl’occurrencelafaceencequiconcernelesmodèlesarborescents),maisopère
la subdivision de manière cohérente avec toutes les cellules de la subdivision
(sommets, arêtes, faces). Enfin, l’efficacité des algorithmes de calcul de l’infor-
mation géométrique est améliorée, les informations d’adjacence et d’incidence

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi