Soutenance mémoire
Un système de C.F.A.O. (Conception et Fabrication Assistées par Ordinateur) s’appuie principalement sur un modèle qui sert de description virtuelle d’un objet que I’on veut concevoir puis fabriquer. Les évolutions de la modélisation ont permis d’effectuer de réels progrès pour prévoir le comportement des pièces que ce soit pour étudier une déformation possible, pour préparer de façon automatique leur fabrication ou même pour déterminer leur forme à partir de leurs fonctions. Il apparaît clairement qu’il est essentiel pour mener à bien ces opérations, de pouvoir stocker la forme de I’objet. Historiquement, deux modèles solides ont été utilisés à cette fin : le modèle B-Rep (Boundary Representation) qui est une représentation de la frontière de I’objet et le modèle CSG (Constructive Solid Geometry) qui est un arbre de construction. De plus en plus, ces deux modèles sont maintenus conjointement dans le système, le modèle B-Rep étant généralement calculé automatiquement à partir de I’arbre de construction. Les possibilités offertes par ce dernier en matière de paramétage et de remise en cause de I’historique de construction sont alors associées aux avantages amenés par le fait que la représentation par les limites est évaluée (visualisation rapide, cotations, …). L’outil permettant de convertir une description CSG d’un objet en une suite de faces est communément appelé évaluation booléenne. Ce mémoire est consacré à cet opérateur. Le travail présenté dans ce mémoire, s’inscrit dans le projet SACADO (Système Adaptatif de Conception et d’Aide au Développement par Ordinateur) développé au Laboratoire de Recherche en Informatique de Metz. Notre objectif à terme est de foumir au système SACADO un modèle hybride s’appuyant sur un arbre CSG étendu et évolué.
Formellement, les opérateurs booléens sur deux solides A et B peuvent être définis par :
– UNION : ensemble des points appartenant à I’un ou à I’autre solide (notée At-rB),
– DIFFÉRENCE : ensemble des points appartenant au premier solide et n’appartenant pas au second (notée A-B),
– INTERSECTION : ensemble des points appartenant aux deux solides (notée AnB).
La validité d’un modèle de solides est assurée par les conditions suivantes l rigidité : le solide décrit dans le modèle a une forme invariante, quelles que soient sa position et son orientation,
– finitude : le volume du solide décrit dans le modèle doit être fini,
– homogénéité : tout point à I’intérieur du solide ne peut appartenir à aucun autre objet.
Ces conditions très générales ont indépendantes de la famille de modèles utilisée. Elles doivent être converties en conditions vérifiables du point de we informatique, qui dépendront du modèle utilisé. Dans un modèle Eulérien, la vérification de validité peut être faite soit par le traitement de chaque fonction appliquée sur un objet, soit par vérification sur les données géométriques et topologiques de I’objet aprèsapplication de la fonction. Cette seconde solution reste diffrcile à mettre en æuvre (il est plus aisé de contrôler une modification d’une partie d’un objet que I’objet après modifrcation) et seule la vérification de la validité topologique est relativement aisée .
Dans les algorithmes mettant en æuvre les opérations booléennes, la première solution est choisie. Toute opération construisant ou modifiant un solide se charge de la validité’ Les opérations booléennes régularisées, qui permettent de composer des objets, sont supposées ainsi assurer la validité du résultat. Cette propriété est extrêmement importante, dans la mesure où certaines opérations deviendraient impossibles. Prenons par exemple, la fonction « appartenance d’un point au solide », qui est I’un des traitements de base utilisé dans de nombreux algorithmes ; cette fonction ne pourra être implantée en utilisant la méthode de la demi-droite et en comptant le nombre d’intersectionsignificatives que si I’on est certain que I’objet est un solide. Il n’est cependant pas obligatoirement judicieux d’assuter la validité en pennanence pendant le déroulement de la fonction. En particulier dans le cas des opérations booléennes, on peut accepter des états intermédiaires non valides, à condition que l’état final le soit.
Ainsi I’utilisation d’opérateurs d’Euler peut ne pas être la panacée, même si ces derniers sont à la base de certains algorithmes. On peut utiliser des primitives qui ne vérifient pas la validité topologique, laissant cette responsabilité àla fonction de construction qui les utilise. Les modèles par les frontières s’appuient sur un graphe FAS (Faces, Arêtes, Sommets). Les conditions topologiques utilisées sur ce graphe sont les suivantes :
– a. une arête est partagée par deux faces exactement,
– b. une arête est parcourue une fois dans un sens, et une fois dans I’autre pour les deux faces la partageant,
– c. deux arêtes ne se coupent qu’en un sommet.
Les conditions géométriques se réduisent à :
– a. deux faces ne peuvent se couper qu’en une arête partagée,
– b. la surface définie par le contour de la face ne peut avoir de recoupement (sans importance pour des modèles à facettes planes)
Les opérations ensemblistes sont I’un des moyens très utilisés pour construire des solides. Leur mise en æuwe sur des modèles par des facettes planes est relativement diffrcile. Pourtant leur définition mathématiquest très simple.
Les opérations booléennesont utilisées dans deux types d’algorithmes [BRO 88] :
– ceux effectuant une opération booléenne sur deux objets B-Rep et dont le résultat est un objet B-Rep. Ils sont recensés sous le nom de « fitsion des frontières » (« boundary merging »),
– cetu( évaluant un arbre de construction CSG et réunis sous le terme « calcul des frontières » (« boundary evaluation »).
L’idée sous-jacente de ces deux types d’algorithmes est cependant la même. Elle consiste à évaluer le résultat d’une opération booléenne sur deux objets B-Rep. L’évaluation d’un arbre de construction devient alors triviale : il suffit de transformer les primitives en objets B-Rep puis d’évaluer I’arbre de construction du modèle CSG. C’est pourquoi notre étude va essentiellement porter sur les algorithmes « fusion des frontières ».
Les calculs d’intersection arêtes /faces impliquent le traitement de tous les cas particuliers pouvant se présenter (ce qui était également le cas pour la méthode d’intersection arêtes-faces [BRA 75]).Ladiffrculté essentielle de cette approche réside dans la détermination de la ligne de section. La ligne de section est formée par les points d’intersection entre arêtes et faces qui doivent être correctement reliés.
L’idée générale est que I’on peut relier deux points d’intersection si ils appartiennent àune même face sur A et sur B pour des faces convexes MAN 82]. Dans le cas de faces non convexes [MMP 87a] [MMP 87b], on ordonne les points d’intersections communs à deux faces ce qui donne un certain nombre de segments candidats. Un segment candidat constitue une arête si le milieu du segment appartient à chaque face.
On insère les éléments de la ligne de section dans chaque objet en deux étapes :
– insertion des points d’intersection dans les contours de faces auxquelles ils appartiennent,
– pour une telle face, on la parcourt jusqu’à un point d’intersection, puis on parcourt la ligne de section tant que I’on est sur la même face. Le parcours se pousuit sur le contour de la face jusqu’à un nouveau point d’intersection ou jusqu’à ce que le parcours donne un contour fermé.
La partition en intérieur et en extérieur est assez simple puisqu’une face d’un ensemble (extérieur et intérieur) ne peut pas traverser I’autre solide. Par adjacence d’arêtes initiales et test de classification d’un point, on détermine facilement l’état des sous-ensembles de faces.
Les opérateurs d’Euler sont en général utilisés [HIG 93], car ils permettent de traiter facilement des opérations consistant à couper des arêtes, créer des arêtes nulles… Cette famille d’algorithmes fonctionne sur des faces planes et impose un traitement particulier pour les faces coplanaires.
|
Table des matières
Introduction
Chapitre l. État de I’art
1. Introduction
2. Les modèles de solides par les frontières.
3. Mise en æuwe des opérations booléennes sur des objets polyédriques
3.1. Méthodes d’évaluation directe sur des B-Rep
3.1.1. Méthode d’intersection arêtes-faces
3.1.2. Méthode du polygone de section.
3.1.3. Méthode de découpage de faces.
3.1.4. Méthode du pan.
3.1.5. Méthode des domaines.
3.1.6. Méthodes par faces.
3.1.7. Conclusion
3.2. Méthodes utilisant un modèle intermédiaire.
4. Méthodes sur des objets contenant des surfaces gauches
4.1. Intersection de surfaces.
4.2.Éivaluation d’opérations booléennes.
5. Opérations booléennes sur des objets non-eulériens.
5.1. Définition
5.2. Opérations booléennes.
6. Conclusion
Chapitre 2. Opérations booléennesur des objets polyédriques : la méthode des sections.
l. Introduction.
2.ldée principale et bases théoriques.
3. Recherche de la section.
4. Opérations booléennes en deux dimensions
4.1. Calcul de I’union.
4.2. Calcul de I’intersection.
4.3. Calcul de la différence
4.4. Conclusion
5. Traitement des faces coplanaires
5.1. Résolution théorique
5.2. Exemples de faces coplanaires
6. Reconstruction de I’objet résultat suivant la définition du modèle B-Rep.
6.1. Notations mathématiques, définitions et propriétés.
6.2. Propriétés topologiques.
6.3. Démonstrations
7. Comparaison avec la méthode des faces.
8. Implémentation
9. Exemples.
10. Conclusion
Chapitre 3. Opérations booléennesur des objets à surfaces quelconques : extension de méthode des sections.
l. Introduction.
2. Choix d’une so1ution
2.1. Formulation du problème
2.2.Méthode sans modèle intermédiaire
2.3. Méthode avec un modèle intermédiaire
2.4. Conclusion
3. Méthode proposée.
3.1. Le modèle.
3.2. Approximation d’une surface par des facettes et suppression des facettes
3.3. Exemples
3.4. Incohérences géométriques
4. Conclusion
Sommaire.
Chapitre 4. Réalisation, mise en Guvre et complexité.
1. Introduction
2. Opérations booléennes sur des polyèdres
2.l.Le modèle de SACADO
2.2. Structures de données avec justification du choix
2.3. Algorithmes de la méthode
2.4. Complexité et résultats
2.5. Problèmes rencontrés
3. Opérations booléennes sur les quadriques
3.1. Modèle pour objets à surfaces quelconques.
3.2. Algorithmes de la méthode
3.3. Résultats.
3.4. Problèmes de visualisation du modèle.
3.5. Apports de C+ par rapport à C
4. Conclusion
Conclusion
Télécharger le rapport complet
