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 .

La diversité des besoins en C.A.O. a fait progressivement apparaître trois types d’objets :
– les objets à facettes planes ou polyèdres,
– les objets comportant des surfaces gauches,
– les objets possédant des parties sans volume appelés objets non-Eulériens.

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ès application 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.

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 ».

Pour étudier les algorithmes d’évaluation d’opérations booléennes sur les objets polyédriques, on peut classer les différentes méthodes  en deux grandes familles :
– les méthodes utilisant un modèle intermédiaire spécifique (essentiellement les arbres octaux),
– les méthodes travaillant directement sur le modèle par les frontières.

Cette méthode [BRA 751, fait partie des premières méthodes publiées sur les algorithmes d’opérations booléennes. Elle ne concerne qu’une classe d’objets restreints. Ces derniers ne peuvent être composés que de faces planes et de surfaces cylindriques. Un objet est dit négatif s’il n’est considéré comme n’étant constitué que d’antimatière sinon il est dit positif. Les objets négatifs servent notamment à supprimer de la matière dans un objet positif. Les points de l’espace euclidien 3D sont classés suivant leur appartenance aux objets.