Surfaces polyédriques et surfaces paramétriques : une reconstruction par approximation via les surfaces de subdivision, Polyhedral surfaces and parametric surfaces : a reconstruction by an approximation through subdivision surfaces

Khoi Nguyen Tan

Description

Sous la direction de Marc Daniel
Thèse soutenue le 08 juillet 2010: Aix Marseille 2
La Conception Assistée par Ordinateur (C.A.O) qui permet de concevoir des objets physiques à partir de modèles mathématiques est utilisée dans de nombreux secteurs de l’industrie.On constate actuellement une volonté généralisée de tirer parti de deux approches jusqu’à présent plutôt antagonistes : la modélisation géométrique continue qui crée des objets continus représentant par la modélisation à partir de surfaces B-splines ou NURBS) et la modélisation géométrique discrète qui qu’il s’agisse de maillages ou de surfaces de subdivision.Cette dualité d’approche a de nombreuses applications industrielles potentielles et présente donc un intérêt scientifique important. Les surfaces polyédriques et en particulier les surfaces de subdivision offrent intrinsèquement la discrétisation, sont d’une manipulation très simple, mais elles ne remplacent pas les surfaces B-splines ou NURBS. Les travaux présentés dans la thèse et qui ont abouti au passage réciproque d’une surface paramétrique à une surface polyédrique. Nous nous intéressons plus particulière aux surfaces de subdivision considérant comme une liaison entre la surface polyédriquee et la surface paramétrique parce qu’après quelques étapes de subdivision, le polyèdre caractéristique converge à une surface paramétrique correspondant. Nous y proposons des schémas de la subdivision inverse permettent de récréer les surface polyédrique grossier de subdivision précédent. Nous avons donc développé deux méthodes pour la reconstruction d’une courbe/surface paramétrique en utilisant le schéma de subdivision inverse uniforme et le schéma de subdivision inverse non-uniforme. Pour améliorer les résultats de reconstruction par la subdivision inverse, nous associons à ces méthodes une possibilité d’ajustement d’approximation qui permet de diminuer grandement l’erreur de reconstruction. Les résultats obtenus ont été comparés à une méthode bien connu de reconstruction sens au sens des moindres carrés. Nos méthodes sont très prometteuses en termes d’approximation et de compression
-B-spline
-Nurbs
-Maillage
-Subdivision inverse
-Reconstruction
-Approximation
-Modélisation
-Compression
Computer Aided Geometric Design (CAGD) which allows us to design the physical objects from mathematical models is used in many sectors of industry. It is currently a general wish to take advantage of the two these approaches rather than the antagonists : The goal that the continuous geometric model creates the continuous objects represented by the modelof the surfaces B-splines or NURBS) and the discreet geometric model made by eitherthe meshes or the subdivision surfaces. This duality of the approach has many potential industrial applications and therefore submits interesting significant science. The polyhedral surfaces and the subdivision surfaces in particular which offer the intrinsically discretization,are a very simple manipulation, but they do not replace the surfaces B-splines or NURBS.The works presented in this thesis aim to the reciprocal passage from a parametric surfaceto a polyhedral surface. We are more specialy interested to subdivisions surfaces considering as a liaison between the polyhedral surface and the parametric surface, because after a few steps of subdivision, the polyhedron characteristic converges to a parametric surface corresponding.We have proposed the schemas of the inverse subdivision allowing recreating the polyhedral surface coarse of subdivision precedent. We thus presented two methods for there construction of a parametric curve/surface : one for using the schema of uniform inverse subdivision and the other for non-uniform inverse subdivision. To improve the results of reconstruction by the inverse subdivision methods, we associate these methods with the process of adjustment the approximation which allows reducing the error of reconstruction.The results obtained have been compared with a well-known least squares method. Our methods are very promising in terms of approximation and compression.
-Modelling
-B-spline
-Nurbs
-Subdivision
-Inverse subdivision
-Reconstruction
Source: http://www.theses.fr/2010AIX22055/document

Sujets

• NURBS
• Maillage
• Reconstruction
• Modélisation

Informations

• Publié par: Thesee
• Nombre de lectures: 83
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

Université de la Méditerranée
Aix-Marseille II
Faculté des Sciences de Luminy
163, Avenue de Luminy 13288 Marseille cedex 9
THÈSE DE DOCTORAT
en Informatique
Surfaces polyédriques et surfaces
paramétriques : une reconstruction par
approximation via les surfaces de
subdivision
présentée par :
Khoi NGUYEN TAN
en vue d’obtenir le grade de docteur de l’Université de la Méditerranée
soutenue le 8 juillet 2010 devant le jury composé de :
Marc Daniel Professeur, Directeur de thèse
Jean-Pierre Jessel Rapporteur
Marc Neveu Rapporteur
André Crosnier Examinateur
Cung Le Docteur, Co-Directeur de thèse
Romain Raffin Maître de Conférence, Co-Directeur de thèse
oN attribué par la bibliothèque
Année 2010À mes parents,
`À ma femme Bach Hông.Remerciements
Je voudrais remercier chaleureusement les membres de mon jury de thèse de m’avoir fait
l’honneur d’évaluer mon travail :
– Monsieur Jean-Pierre Jessel, chair de l’AFIG (the French Association for Computer
Graphics) qui a rapporté mon mémoire;
– Monsieur Marc Neveu, professeur à l’Université de Bourgogne, qui a également été
rapporteur de mon mémoire;
– Monsieur André CROSNIER, professeur à l’Université de Montpellier qui a fait partie
de mon jury;
Je tiens à exprimer ma profonde gratitude à mes directeurs de thèse qui ont grandement
contribué à faire de ce travail ce qu’il est :
– Monsieur Marc Daniel, professeur à l’Université de la Méditerranée, pour avoir dirigé
mes travaux. Qu’il trouve ici toute ma gratitude pour son orientation scientifique, son
soutien, sa direction attentive, sa rigueur; pour ses encouragement de chaque instant
et sa patience qui m’ont permis d’achever mon doctorat.
– Monsieur Romain Raffin, enseignant-chercheur à l’Iut de Provence, co-directeur de
ma thèse. Son suivi régulier, son attention, sa disponibilité, et sa gentillesse m’ont été
précieux pour l’élaboration et la rédaction de mon travail. Je le remercie du temps
qu’il m’a consacré pour mon travail.
– Monsieur Cung Le, chef de la Faculté de Pédagogie Technique-Science de l’Ingénieur,
1assistant du PFIEV de l’Université de Danang, co-directeur de ma thèse, pour ses
encouragements, sa disponibilité, ses remarques et ses conseils avisés.
Je remercie tous les thésards anciens et actuels de l’équipe I&M du LSIS qui ont contri-
bué à une ambiance à l’équipe : Grégory, Guillaume, Agung, Alaa, Van, Hung, Axel, Ma-
riette,.... Je remercie également Raphaël et Jean-Christophe pour les aides qu’ils m’ont
apportés au début de ma thèse.
Je tiens également à remercier tous les autres membres de l’équipe I&M de leur accueil,
avec qui j’ai été heureux de passer mes temps de thésard.
Je souhaite de remercie Hélène de son enthousiasme, de sa sympathie et avec qui j’ai
partagé beaucoup de moments mémorables.
Je n’oublie pas les aides chaleureuses que les familles de Romain, Gilles et Axel m’ont
donnés quand j’étais à Arles.
2J’adressetousmesremerciementsàmesamis,mescollègues pourleursencouragements,
leurs soutiens sur mon travail.
Enfin, je remercie du fond de cœur mes parents pour leurs encouragements et plus
particulièrement ma femme qui se donne beaucoup de peines pour moi dans ma vie de
doctorant.
1. Programme de Formation d’Ingénieurs d’Excellence
2. Faculté d’Informatique, Ecole Polytechnique - Université de Danang.À tous, encore merci ...
iiiTable des matières
Table des matières i
Table des figures viii
Liste des tableaux xiii
Introduction générale 1
1. Cadre et orientation de l’étude 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Modélisation géométrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Modèles polyédriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Modèles paramétriques . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2.1 Les courbes paramétriques . . . . . . . . . . . . . . . . . . 7
1.2.2.1.1 Courbe de Bézier . . . . . . . . . . . . . . . . . . . 7
1.2.2.1.2 Courbe B-spline . . . . . . . . . . . . . . . . . . . 8
1.2.2.1.3 Courbe NURBS . . . . . . . . . . . . . . . . . . . 9
1.2.2.2 Les surfaces paramétriques . . . . . . . . . . . . . . . . . . 10
1.2.2.2.1 Surface B-spline . . . . . . . . . . . . . . . . . . . 11
1.2.2.2.2 NURBS . . . . . . . . . . . . . . . . . . . 11
1.2.2.3 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Modèles de subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Problématique et objectif de ce travail . . . . . . . . . . . . . . . . . . . . . 15
1.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2. Discrétisation d’objet continu 18
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Etat de l’art sur la discrétisation d’objets continus . . . . . . . . . . . . . . 18
2.2.1 Maillage polyédrique . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1.1 Définition du maillage . . . . . . . . . . . . . . . . . . . . . 19
2.2.1.2 Qualité d’un maillage . . . . . . . . . . . . . . . . . . . . . 19
2.2.1.3 Méthodes de génération de maillage . . . . . . . . . . . . . 19
2.2.2 Conversion de modèles paramétriques en modèles polyédriques . . . 20
2.2.2.1 Génération de maillage . . . . . . . . . . . . . . . . . . . . 20
2.2.2.2 Mise en maillage cohérent . . . . . . . . . . . . . . . . . . . 20
iTable des matières
2.2.2.3 Optimisation du maillage . . . . . . . . . . . . . . . . . . . 21
2.2.3 Méthodes de discrétisation existantes . . . . . . . . . . . . . . . . . . 21
2.2.4 Approche de l’échantillonnage uniforme du domaine paramétrique . 21
2.2.5 Approche par les surfaces triangulaires . . . . . . . . . . . . . . . . . 22
2.2.6 Approche par la méthode de discrétisation . . . . . . . . . . . . . . . 23
2.2.7 Approche par l’évaluation et le raffinement . . . . . . . . . . . . . . 23
2.2.8 Discussion sur les approches et orientation de notre méthode . . . . 24
2.3 Algorithmes d’évaluation et de raffinement . . . . . . . . . . . . . . . . . . . 24
2.3.1 Algorithme de De Casteljau . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 de De Boor . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.3 Algorithme de De Boor-Cox . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.4 d’insertion de nœuds de Boehm . . . . . . . . . . . . . . 28
2.3.4.1 Insertion d’un nœud de multiplicité 1 . . . . . . . . . . . . 28
2.3.4.2 Insertion d’un nœud de multiplicité m supérieure à 1 . . . 28
2.3.5 Algorithmes d’Oslo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.5.1 Algorithme Oslo1 . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.5.2hme Oslo2 . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.7 Raffinement d’une surface paramétrique . . . . . . . . . . . . . . . . 32
2.4 Méthodes de discrétisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.1 Discrétisation d’une courbe paramétrique . . . . . . . . . . . . . . . 34
2.4.1.1 Construction de la fonction nodale E(s) . . . . . . . . . . . 34
2.4.1.2 Détermination de la répartition de l’abscisse curviligne de
courbe C(s) . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.2 Discrétisation d’une surface paramétrique . . . . . . . . . . . . . . . 38
2.4.2.1 Discrétisation des arêtes frontières de la surface . . . . . . . 38
2.4.2.2 Maillage de la surface paramétrique par la méthode frontale 40
2.4.2.3 Evaluation de la méthode de discrétisation . . . . . . . . . 40
2.4.2.4 Le cas d’une courbe bien paramétrée . . . . . . . . . . . . . 41
2.4.2.5 Le cas d’une courbe mal . . . . . . . . . . . . . 41
2.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3. Subdivision d’objets polyédriques 44
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Notation et terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Etat de l’art sur la subdivision . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 Schémas de sub uniforme . . . . . . . . . . . . . . . . . . . . 46
3.3.2 Schémas de subdivision non-uniforme. . . . . . . . . . . . . . . . . . 48
3.3.3 Continuité de la surface de subdivision . . . . . . . . . . . . . . . . . 49
3.3.4 Profondeur de la subdivision . . . . . . . . . . . . . . . . . . . . . . 49
iiTable des matières
3.3.5 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Subdi