Algoritmos para las operaciones booleanas en 2d y 3d, bajo un sistema de representación formal

Abstract

Se ha presentado una formalización matemática para la representación y manipulación de sólidos con caras planas variedad y no variedad, con o sin agujeros, basada en el concepto de cadena simplicial y susceptible de ser utilizada en espacios n-dimensionales, La nueva representación es una representación híbrida entre un sistema B-rep y un esquema constructivo; pues los símplices de la cadena simplicial se obtienen directamente de la representación de la frontera sin procesamientos previos, y aplicando sobre ellos las operaciones de suma y producto de las cadenas se obtiene la cadena simplicial asociada al sólido. Además, la nueva representación es inambigua y única para un punto de referencia elegido. El modelo ha sido presentado de forma detallada para dos y tres dimensiones, describiéndose las estructuras de datos a seguir en cada una de ellas; ambas estructuras son sencillas y concisas pues ocupan una cantidad mínima de memoria. En 3D se ha asumido que se trabaja con sólidos con caras triangulares, fundamental por las ventajas que ello aporta en cuanto a facilidad de representación respecto a otras estructuras, y por la sencillez de los algoritmos que manejan sólidos con caras tan simples, mejorando la eficiencia de los mismos. También se han formalizado las operaciones booleanas entre sólidos en dos y tres dimensiones, presentando teoremas que prueban la correctitud de las operaciones booleanas regularizadas obtendias a partir de las cadenas simpliciales y de sus operaciones algebraicas, de modo que se pueden obtener las operaciones booleanas a través de las operaciones de suma y productor entre símplices. Para conseguir una eficiente implementación de los operadores booleanos regularizados, se ha propuesto una simplificación del operador intersección basada en los conceptos de subordinación, nivel y capa definidos para los símpleces de una cadena, que permite el cálculo de la intersección, unión