Opérations sur les ensembles de polyèdres utilisant des arbres de partitionnement d'espace binaire

Nous introduisons une nouvelle représentation pour les polyèdres en montrant comment les Arbres de Partitionnement d'Espace Binaire (arbres BSP) peuvent être utilisés pour représenter des ensembles réguliers. Nous montrons ensuite comment ils peuvent être utilisés pour évaluer des opérations sur les ensembles de polyèdres. L'arbre BSP est un arbre binaire représentant un partitionnement récursif d'un espace d par des (sous-)hyperplans, pour toute dimension d. Leur application précédente à la graphiste informatique a été d'organiser un ensemble arbitraire de polygones afin qu'une solution rapide au problème de surface visible puisse être obtenue. Nous conservons cette propriété (en 3D) et montrons comment les arbres BSP peuvent également fournir une représentation exacte de polyèdres arbitraires de toute dimension. La conversion d'une représentation de frontière (B-reps) de polyèdres en une représentation d'arbre BSP est décrite. Cette technique conduit à une nouvelle méthode pour évaluer des expressions théoriques des ensembles (booléennes) sur des B-reps, représentées sous forme d'un arbre CSG, produisant un arbre BSP comme résultat. Les résultats de notre implémentation pilotée par le langage de cet évaluateur CSG sont discutés. Enfin, nous montrons comment modifier un arbre BSP pour représenter le résultat d'une opération sur les ensembles entre l'arbre BSP et un B-rep. Nous décrivons l'incarnation de cette approche dans un programme de conception d'objets 3D interactif qui permet la modification incrémentielle d'un objet avec un outil. Le placement de l'outil, la sélection des vues et l'exécution de l'opération sur les ensembles se font toutes à des vitesses interactives pour des objets modestement complexes.