Approximation et intersection des surfaces procédurales utilisées en C.A.O. Stéphane Chau To cite this version: Stéphane Chau. Approximation et intersection des surfaces procédurales utilisées en C.A.O.. Mathé- matiques [math]. Université Nice Sophia Antipolis, 2008. Français. ￿NNT: ￿. ￿tel-00560289￿ HAL Id: tel-00560289 https://theses.hal.science/tel-00560289 Submitted on 27 Jan 2011 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. ´ UNIVERSITE DE NICE-SOPHIA ANTIPOLIS - UFR Sciences E´cole Doctorale Sciences Fondamentales et Appliqu´ees ` THESE pour obtenir le titre de Docteur en Sciences de l’UNIVERSITE´ de Nice-Sophia Antipolis Sp´ecialit´e : Mathe´matiques pr´esent´ee et soutenue par St´ephane Chau Approximation et intersection des surfaces proc´edurales utilis´ees en C.A.O. Th`ese dirig´ee par Andr´e Galligo et Mohamed Elkadi soutenue au laboratoire J.A. Dieudonn´e le 10 Juin 2008 Membres du jury : Mme. Gema Maria Diaz-Toca Professeur `a l’Universit´e de Murcia Examinateur M. Mohamed Elkadi Maˆıtre de conf´erence `a l’Universit´e de Nice Directeur M. Andr´e Galligo Professeur `a l’Universit´e de Nice Directeur M. Laureano Gonzalez-Vega Professeur a` l’Universit´e de Cantabria Rapporteur M. Bert Ju¨ttler Professeur `a l’Universit´e Johannes Kepler Rapporteur M. Bernard Mourrain Directeur de recherche `a l’INRIA Pr´esident M. Jean-Claude Yakoubsohn Professeur `a l’Universit´e de Toulouse Rapporteur Approximation et intersection des surfaces proc´edurales utilis´ees en C.A.O. St´ephane Chau Remerciements Il est de coutume de consacrer quelques pages de remerciements dans une th`ese et la mienne ne fera pas exception `a la r`egle. Bien entendu, et ce n’est pas par conformit´e, je voudrais sinc`erement remercier mes directeurs de th`ese Andr´e Galligo et Mohamed Elkadi qui m’ont consacr´e beaucoup detempsetm’ont´enorm´ementapport´equecesoitsurleplanscientifiqueou humain.Monexp´eriencedanslemilieuuniversitairem’afaitcomprendreque les relations doctorant-directeur(s) peuvent parfois ˆetre difficiles en raison d’incompatibilit´e de caract`eres. Ce constat me permet de r´ealiser que je fais partie d’une minorit´e qui a eu la chance de cˆotoyer des encadrants avec lesquelsjemesuisparticuli`erementbienentendu.Celaafortementcontribu´e `a mon ´epanouissement tout au long du projet de th`ese dont le manuscrit pr´esent ne refl`ete qu’une infime partie. Cettederni`ereremarquemeparaˆıtimportantedanslamesureou` ilfautbien r´ealiser qu’une multitude de facteurs contribue au bon d´eroulement d’une th`ese et que l’auteur ne fait pas tout. Parmi eux, il y a ´evidemment les per- sonnes qui sont autour du projet et qui permettent d’enrichir son contenu. Je pense tout d’abord aux membres du projet GALAAD de l’INRIA qui m’ont beaucoup apport´e graˆce `a leurs comp´etences sp´ecifiques. En parti- culier je voudrais remercier Bernard Mourrain pour son regard expert `a tous les niveaux, Julien pour tous les conseils qu’il m’a apport´e sur le plan informatique et Jean-Pascal qui m’a fait d´ecouvrir, avec son sens de la communication absolument unique, les probl`emes de la CAO. Il y a ´egalement Laurent, Marc, Lionel et Jean-Pierre avec qui j’ai eu souvent des discussions fructueuses. Je remercie aussi les personnes qui ont accept´e de faire partie de mon jury de th`ese et en particuliers les rapporteurs qui ont eu la lourde taˆche de me relire. De mˆeme que la technologie avanc´ee d’une Formule 1 ne serait rien sans des pneus de qualit´e pour exploiter son potentiel, une th`ese doit son existence aussi en partie `a l’entourage proche de son auteur. Cette m´etaphore doit en faire sourire plus d’un et je saisis cette opportunit´e pour citer toutes les personnes du laboratoire Dieudonn´e avec lesquelles j’ai beaucoup ri. Je veux remercier Pierre, qui a partag´e mon bureau et mes amphis il y a quelques ann´ees en arri`ere, pour son look inimitable, Mig pour ses formules depolitessequirimentavecbus,Fabienpoursabonnehumeurpermanente et bien suˆr tous les autres : Delphine, Mimi, Thi Ha, Marcello, Olivier, La maman de Josu´e et Lucie, You, Nico, Thomas, Joan, Xavier... Lesmomentsded´etenteneser´esumantpasqu’aubureau,jemedoisausside nommerlescopainsquinefontpaspartiedulabomaisavecquij’aipass´ede tr`es bons moments : Laura qui m’a beaucoup soutenu et fait d´ecouvrir des perles musicales, Marie qui me fait toujours beaucoup rire avec ses anec- dotes, Elise chez qui on a pass´e des soir´ees m´emorables, Claire, Vincent, Julie, Pascale,... J’ai aussi une pens´ee toute particuli`ere pour Coralie et Kiwi qui partagent ma vie et qui ont bien du m´erite `a supporter un ´energum`ene comme moi surtout apr`es certaines journ´ees de travail ou` je n’ai eu comme seul interlo- cuteur que mon ´ecran d’ordinateur. Enfin, je terminerai en remerciant ma famille et ma belle famille. Table des mati`eres Introduction 1 1 Outils alg´ebriques et num´eriques 7 1.1 Base de Bernstein . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Base de Bernstein univari´ee . . . . . . . . . . . . . . . 8 1.1.2 Base de Bernstein multivari´ee . . . . . . . . . . . . . . 10 1.2 Solveurs polynomiaux . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Solveur univari´e . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Solveur multivari´e . . . . . . . . . . . . . . . . . . . . 12 1.3 D´ecomposition en valeurs singuli`eres . . . . . . . . . . . . . . 15 2 Approximation et localisation d’intersections 17 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Notations et repr´esentations . . . . . . . . . . . . . . . . . . . 20 2.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 Polynˆome de bidegr´e (2,2) dans la base de Bernstein . 21 2.3 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Boˆıtes englobantes et raffinement . . . . . . . . . . . . . . . . 24 2.4.1 Algorithme de De Casteljau . . . . . . . . . . . . . . . 25 2.4.1.1 Cas d’une courbe de B´ezier de degr´e 2 . . . . 25 2.4.1.2 Cas d’une surface de B´ezier de bidegr´e (2,2) 25 2.4.2 Boˆıtes englobantes orient´ees et intersections . . . . . . 27 2.4.2.1 Cas du plan . . . . . . . . . . . . . . . . . . 27 2.4.2.2 Cas de l’espace . . . . . . . . . . . . . . . . . 29 v vi Table des mati`eres 2.4.3 Crit`ere de discrimination . . . . . . . . . . . . . . . . 29 2.4.3.1 Choix des directions . . . . . . . . . . . . . . 30 2.4.3.2 D´ecoupage r´ecursif de boˆıtes . . . . . . . . . 32 2.5 Intersection de deux grilles de boˆıtes englobantes . . . . . . . 34 2.5.1 Structure de donn´ees . . . . . . . . . . . . . . . . . . . 35 2.5.2 Intersection . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Intersection des surfaces polynomiales 39 3.1 M´ethode bas´ee sur les r´esultants . . . . . . . . . . . . . . . . 40 3.1.1 G´en´eralit´es sur les r´esultants bivari´es . . . . . . . . . . 40 3.1.2 Application au probl`eme d’intersection . . . . . . . . . 41 3.1.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 Implicitisation approch´ee et intersection . . . . . . . . . . . . 45 3.2.1 Implicitisation . . . . . . . . . . . . . . . . . . . . . . 46 3.2.2 Implicitisation approch´ee . . . . . . . . . . . . . . . . 46 3.2.3 Implicitisation d’une surface biquadratique . . . . . . 47 3.2.4 Application au probl`eme d’intersection . . . . . . . . . 49 3.2.5 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 Approche semi-implicite . . . . . . . . . . . . . . . . . . . . . 52 3.3.1 Intersection d’une courbe coordonn´ee . . . . . . . . . 52 3.3.2 Structure globale de la courbe d’intersection . . . . . . 57 3.3.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 Auto-intersection des surfaces biquadratiques . . . . . . . . . 59 3.4.1 Auto-intersection par r´esultants . . . . . . . . . . . . . 60 3.4.2 Auto-intersection par semi-implicitisation . . . . . . . 62 3.5 Topologie d’une courbe implicite . . . . . . . . . . . . . . . . 63 3.5.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . 63 3.5.2 Courbe implicite plane . . . . . . . . . . . . . . . . . . 64 3.5.3 Courbe implicite 3D . . . . . . . . . . . . . . . . . . . 66 3.5.4 Courbe implicite 4D . . . . . . . . . . . . . . . . . . . 70 3.6 Aspects algorithmiques du calcul de topologie . . . . . . . . . 79 3.6.1 Structure de donn´ees hexatree . . . . . . . . . . . . . 80 3.6.2 Algorithme de subdivision . . . . . . . . . . . . . . . . 81 3.6.3 Composantes connexes et boucles . . . . . . . . . . . . 83 3.7 Remont´ee d’une topologie dans l’espace . . . . . . . . . . . . 84 3.7.1 Isolation des branches par des boˆıtes . . . . . . . . . . 87 Table des mati`eres vii 3.7.2 Noeuds et discr´etisation . . . . . . . . . . . . . . . . . 89 3.8 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4 Axel : modeleur alg´ebrique g´eom´etrique 95 4.1 Point de vue utilisateur . . . . . . . . . . . . . . . . . . . . . 97 4.1.1 Objets . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.1.1.1 Courbes . . . . . . . . . . . . . . . . . . . . . 97 4.1.1.2 Surfaces . . . . . . . . . . . . . . . . . . . . . 100 4.1.2 Outils . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.1.2.1 Topologie . . . . . . . . . . . . . . . . . . . . 102 4.1.2.2 Intersection . . . . . . . . . . . . . . . . . . . 102 4.1.2.3 Auto-intersection. . . . . . . . . . . . . . . . 103 4.1.2.4 Arrangement . . . . . . . . . . . . . . . . . . 104 4.1.2.5 Calcul diff´erentiel et approximation . . . . . 106 4.1.3 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.1.3.1 Interface graphique . . . . . . . . . . . . . . 106 4.1.3.2 Interface de fichier . . . . . . . . . . . . . . . 107 4.1.3.3 Interface de script . . . . . . . . . . . . . . . 108 4.2 Point de vue d´eveloppeur . . . . . . . . . . . . . . . . . . . . 109 4.2.1 Framework . . . . . . . . . . . . . . . . . . . . . . . . 110 4.2.1.1 Hi´erarchie virtuelle d’objets . . . . . . . . . . 111 4.2.1.2 Hi´erarchie virtuelle d’outils . . . . . . . . . . 112 4.2.2 Syst`eme de plugin . . . . . . . . . . . . . . . . . . . . 113 4.2.3 Syst`eme de noyaux . . . . . . . . . . . . . . . . . . . . 115 4.2.3.1 Noyau g´eom´etrique . . . . . . . . . . . . . . 115 4.2.3.2 Noyau alg´ebrique . . . . . . . . . . . . . . . 116 Conclusion et perspectives 117 Bibliographie 119