Diseño Asistido por Ordenador TEMA 3 PDF

Diseño Asistido por Ordenador Juan Manuel Sanz Arranz Área de Expresión Gráfica en la Ingeniería Escuela de Ingenierías Industriales Universidad de Valladolid TEMA 3 Modelad...

Diseño Asistido por Ordenador Juan Manuel Sanz Arranz Área de Expresión Gráfica en la Ingeniería Escuela de Ingenierías Industriales Universidad de Valladolid TEMA 3 Modelado de sólidos En muchas aplicaciones los elementos que se diseñan representan objetos físicos tridimensionales, de los que es necesario calcular propiedades tales como su peso, su volumen o su momento de inercia. Estos objetos deben modelarse con las técnicas de modelado sólido. Este tema aborda el estudio del modelado de sólidos, que es el conjunto de métodos y técnicas utilizadas para representar sólidos. En el se aborda la problemática planteada en la representación de sólidos y se ahonda en los tres métodos de modelado más utilizados en aplicaciones comerciales: la representación de fronteras, la geometría constructiva de sólidos y los octrees.  Diseño Asistido por Ordenador Índice 3.1 Introducción III-3 3.1.1 Modelo topológico III-3 3.1.2 Modelo de superficies III-4 3.1.3 Propiedades volumétricas III-5 3.1.4 Propiedades de los métodos de representación III-5 3.1.5 Operaciones regularizadas III-6 3.1.6 Métodos de representación III-6 3.2 Representación por fronteras (B-rep) III-9 3.2.1 Representación III-10 3.2.2 Cálculo de propiedades III-13 3.2.3 Edición III-15 3.2.4 Propiedades de la representación III-17 3.3 Métodos de descomposición III-20 3.3.1 Enumeración espacial III-20 3.3.2 Octrees III-20 3.3.3 Almacenamiento III-21 3.3.4 Búsqueda III-21 3.3.5 Operaciones booleanas III-22 3.3.6 Propiedades III-23 3.4 Geometría constructiva de sólidos (CSG) III-23 3.4.1 Primitivas sólidas simples III-23 3.4.2 Representación basada en árboles binarios III-25 3.4.3 Representación basada en grafos III-27 3.4.4 Visualización III-28 3.4.5 Propiedades III-29 3.5 Representación por barrido (Sweep) III-29 3.5.1 Conversión de barridos III-31 3.6 Organización de modeladores sólidos III-31 3.7 Referencias III-34 III-2  Diseño Asistido por Ordenador 3.1 Introducción Muchas aplicaciones (CAD/CAM) necesitan trabajar con elementos volumétricos con los que se puedan calcular propiedades, como por ejemplo el volumen, peso, centro de gravedad, momentos de inercia, tensiones, temperaturas y realizar operaciones, como unir objetos, calcular su intersección, ver colisiones de elementos (robot, objeto), etc. En otros casos, el objeto que se diseña se debe fabricar mediante algún proceso automático, siendo esencial garantizar que representa realmente a un sólido. El modelado de sólidos es el conjunto de teorías, técnicas y sistemas orientados a la representación “completa en cuanto a información” de sólidos. Dicha representación debe permitir (al menos en principio) calcular automáticamente cualquier propiedad bien conocida de todo sólido almacenado [Requi83]. Así, sobre los sólidos representados podremos, además de visualizarlos y editarlos, calcular sus propiedades físicas y simular procesos físicos (como la transmisión de calor en su interior). Antes de plantearnos como realizar la representación, es necesario concretar cuales son los objetos a representar. Es decir, formalizar lo que entenderemos por sólido [Mäntyla 88]. Hay dos aproximaciones diferentes al problema, una que caracteriza al sólido como un conjunto de puntos 3D, conocida como modelo topológico o de conjunto de puntos, y otra que caracteriza matemáticamente al sólido a partir de la superficie que lo delimita, esto es, su piel o frontera. De este modo estableceremos un sistema de representación con tres niveles: sólidos físicos, modelos matemáticos de sólidos y representaciones [Mant88, pp.32]. Sólidos físicos Modelos matemáticos Representaciones Figura 3.1 Niveles de representación 3.1.1 Modelo topológico Los sólidos están definidos en el espacio Euclídeo, E3, ocupando una determinada porción del espacio. Podemos por tanto considerar un sólido como un conjunto de E3. Obviamente no todos los subconjuntos del espacio Euclídeo son sólidos (por ejemplo un punto aislado no es un sólido). Para que un conjunto de puntos represente, a nivel abstracto, un sólido deberá satisfacer, las siguientes condiciones: III-3  Diseño Asistido por Ordenador Ser cerrado y acotado. Esto es, contiene a su frontera y ocupa una porción finita del espacio. Ser rígido. Los sólidos no se modifican al trasladarlos o rotarlos. O lo que es lo mismo, dos sólidos que se diferencian tan solo en una transformación rígida son el mismo sólido. Homogeneidad tridimensional. El sólido debe ser tridimensional en todos sus puntos, es decir, cualquier punto de él debe ser posible en tres direcciones ortogonales. Esta última propiedad se suele caracterizar mediante el concepto topológico de regularización. La regularización de un conjunto se define como la clausura de su interior: r(S) = c(i(S)) Figura 3.2 El objeto no es regular por tener elementos 2D y 1D El interior de un conjunto es el subconjunto de sus puntos que no están en su frontera. La clausura de un conjunto es el conjunto formado por todos sus puntos y todos sus puntos adherentes (los que están es su frontera). Un conjunto es regular si es igual a su regularización S = r(S) Es fácil comprobar que cualquier punto o plano aislado no estará en la regularización del conjunto, es decir ser regular es equivalente a ser tridimensional en todos sus puntos. Un conjunto regular acotado se denomina un r-set (ver figura 3.2). 3.1.2 Modelo de superficies El modelo algebraico describe un sólido a partir de su frontera (conjunto de superficies que separa el sólido de la parte del espacio no ocupada por él). La frontera se puede ver como la piel del sólido. Obviamente cualquier superficie no determina un sólido. Para que un conjunto de superficies describan un sólido deben satisfacer la siguiente propiedad. Encierra un volumen. La piel es cerrada, orientada y completa. Que la piel sea cerrada y este orientada permite determinar si un punto está dentro del sólido, y por tanto obtener el modelo topológico. Los dos modelos, topológico y de superficies, son equivalentes, con determinadas restricciones. Para que el sólido sea representable se suele imponer una condición adicional de suavidad en su frontera, más concretamente se suele exigir que la frontera sea algebraica (o al menos analítica). Esto es, debe ser representable por un polinomio de grado finito. Este modelo permite utilizar representaciones de los sólidos basadas en el almacenamiento de la frontera, que es una entidad bidimensional. III-4  Diseño Asistido por Ordenador Para facilitar la representación se suele exigir además que la frontera sea 2-variedad, esto es, cada punto de la frontera es homeomorfo a un disco en E2. No todos los sólidos satisfacen esta propiedad, por ejemplo, dos pirámides unidas por un vértice no son 2-variedad (2-manifold). 3.1.3 Propiedades volumétricas La mayor parte de las propiedades de un sólido se pueden expresar como integrales de volumen de la forma: Pr opiedad ( Sólido) = ∫∫∫ G Vol ( Sólido ) p ( x, y, z )dV La función a integrar, Gp, cambia dependiendo de la propiedad a calcular. La siguiente tabla recoge algunas de las propiedades más usuales. Propiedad Gp Volumen 1 Masa ρ Centro de gravedad P/Masa Momento de inercia (eje z) X2 + Y 2 3.1.4 Propiedades de los métodos de representación Un método de representación de sólidos establece una relación entre sólidos y descripciones de éstos. Las representaciones de sólidos tienen los siguientes atributos y propiedades formales [Requi80]: Dominio. El dominio del método de representación es el conjunto de objetos representables por él. Idealmente será el conjunto de sólidos. Validez. Una representación es inválida si no se corresponde con ningún sólido real. Es importante que el método de representación asegure de por sí la validez de todas las representaciones que se pueden crear o que existan procedimientos automáticos para comprobar la validez de las representaciones. No ambigüedad. Un método es no-ambiguo si Figura 3.3 Ambigüedad del modelo cada representación se corresponde con un de alambres único objeto real. Es deseable que el método no sea ambiguo. Unicidad. Se dice que existe unicidad en el método de representación si cada objeto real tiene, a lo sumo, una posible representación. Si el método no asegura la unicidad no es posible comprobar la igualdad de objetos. III-5  Diseño Asistido por Ordenador Otras propiedades de las representaciones a tener en consideración son: Ocupación de memoria. Facilidad de creación y edición Facilidad de visualización y cálculo 3.1.5 Operaciones regularizadas Una de las formas más usuales, y naturales, de editar sólidos es combinarlos usando operaciones booleanas, unión, intersección y diferencia (se usa la diferencia en lugar del complemento dado que el complemento produciría un objeto no acotado). No obstante, las operaciones booleanas, tal como se definen habitualmente, no son internas al conjunto de sólidos. Es decir, pueden producir como resultado objetos que no sean sólidos [Fole90; pp.535]. Para resolver este problema se utilizan operaciones booleanas regularizadas. Las operaciones regularizadas se definen como la regularización del resultado de la operación, y se denotan con un asterisco. Figura 3.4 Intersección regularizada A ∩* B = r (A ∩ B) = c(i(A ∩ B)) A U* B = r (A U B) = c(i(A U B)) A -* B = r (A - B) = c(i(A - B)) El conjunto de sólidos con las operaciones regularizadas constituye un álgebra de Boole. 3.1.6 Métodos de representación Se han propuesto un gran número de esquemas de representación para sólidos. En esta sección se hace una breve introducción a algunos de estos métodos. En el resto del tema se analizan con más detalle cuatro de estos métodos. Instanciación de primitivas. El modelo se representa como un conjunto de primitivas que se instancian en el espacio. Para pode realizar cálculos es necesario que las diferentes instancias no se solapen en el espacio. El dominio depende del repertorio de primitivas. III-6  Diseño Asistido por Ordenador Figura 3.5 Instanciación de primitivas Descomposición. El sólido se describe en base a una descomposición del espacio en una colección de elementos simples disjuntos, celdas (por ejemplo tetraedros o cubos). La representación de un sólido es el conjunto de celdas que ocupa. Figura 3.6 Enumeración espacial Fronteras. El sólido se representa mediante un conjunto de caras que describen su frontera. La mayor parte de los sistemas utilizan representaciones de fronteras, con caras poligonales. Figura 3.7Representación de fronteras III-7  Diseño Asistido por Ordenador CSG. Se almacena una expresión booleana que construye el sólido a partir de primitivas simples. Figura 4.8 Construcción de un sólido CSG Barrido (sweep). Se puede ver como una generalización de los métodos de generación de superficies a partir de curvas. El elemento a desplazar es ahora una superficie, que describe un volumen al desplazarse a lo largo de una trayectoria o al rotarse. Figura 3.9 Construcción de sólido por barrido ASM. El modelado analítico de sólidos describe los sólidos a partir de mallas 3D de puntos de control, combinados usando funciones mezcla, generalizando los métodos de diseño de superficies. Figura 3.10 Modelado analítico de sólidos III-8  Diseño Asistido por Ordenador 3.2 Representación por fronteras (B-rep) El método de representación por fronteras (B-rep, de “boundary representation”) se basa en la descripción algebraica de los sólidos, asumiendo que están delimitados por un conjunto de caras, que pertenecen a superficies orientables, continuas y cerradas. La orientación implica que es posible distinguir la cara exterior de la interior al sólido. La orientación suele estar indicada por el vector normal a la superficie. El método surge a partir de los modelos poliédricos usados para la representación de objetos con eliminación de líneas y caras ocultas. Se puede ver como una mejora del modelo para poder describir sólidos incluyendo toda la información de la superficie. En él los sólidos se describen dando la geometría de su superficie (frontera), normalmente formada por un conjunto de caras planas, y las relaciones topológicas existentes. Para ello se distingue entre entidades geométricas (puntos, curvas, superficies) y topológicas (vértices, aristas y caras): Vértice (Vertex): punto único en el espacio. Arista (Edge): curva finita, orientada, delimitada por dos vértices (puede ser el mismo), que no se autointersecta. Anillos (Loop): secuencia ordenada alternante de vértices y aristas no autointersectante y cerrado. Cara (Face): región finita, no autointersectante de una superficie orientable, limitada por uno o más loops. Agujero que no atraviesa (Not through hole): depresión en un objeto. Agujero que atraviesa (Through hole o handle): el número de agujeros de este tipo se llama genus. Cuerpo (Body o Shell): conjunto de caras que delimitan un volumen cerrado continuo. Las relaciones topológicas incluyen relaciones de vecindad y de pertenencia, como por ejemplo: - Cada arista es compartida por dos caras. - En cada vértice confluyen varias aristas (al menos tres) - Vecindad entre caras. Cuando las caras permitidas por el sistema son polígonos el conjunto de objetos representable es el conjunto de poliedros. En este caso, las caras deben ser polígonos cualesquiera, incluyendo polígonos cóncavos y con agujeros (de otro modo el conjunto de presentaciones sería cerrado bajo operaciones booleanas). III-9  Diseño Asistido por Ordenador Figura 3.11 Poliedros simples Figura 3.12 Poliedros con caras con varios anillos o fronteras Figura 3.13 Poliedros con agujeros que no atraviesan el objeto Figura 3.14 Poliedros con agujeros que atraviesan el objeto III-10  Diseño Asistido por Ordenador Aristas Vi Vf Cizq Cder 3.2.1 Representación 0 0 1 1 3 1 1 2 1 2 Existen diversas representaciones que permiten almacenar modelos de fronteras. Su 2 2 3 1 4 complejidad varía en función de las relaciones 3 3 0 1 5 topológicas almacenadas. La opción más simple es 4 1 5 2 3 no almacenar ningún tipo de relación, con lo que la 5 5 4 2 6 representación puede ser una simple lista de caras. 6 4 2 2 4 No obstante, esta aparente simplicidad en la estructura de datos da lugar a procesos complejos para realizar cualquier operación con el modelo, desde la comprobación de validez hasta la edición o cálculo. A modo de ejemplo, supongamos que se desea comprobar que la frontera es cerrada (condición indispensable para que la representación sea válida). Se tendrá que comprobar que en cada arista confluyen dos caras con la misma orientación. Para ello se tendrá que comparar cada par de puntos consecutivos de cada cara con los pares de puntos consecutivos del resto de las caras. Este proceso es complejo (depende del cuadrado del número de caras) e impreciso, la comparación de puntos puede generar errores numéricos. Obsérvese que esta es la estructura habitualmente usada en los sistemas que dibujan poliedros, cuando no interesa editar el objeto como un sólido, ni que represente un sólido válido, ni calcularle propiedades. Por otra parte, esta estructura es muy redundante, los puntos asociados a cada vértice se almacenan en la lista de puntos de cada cara que comparte el vértice. La existencia de información redundante conlleva la utilización de un mayor espacio, y puede ser origen de inconsistencias. La siguiente tabla muestra la representación de las dos caras visibles del poliedro de la figura 3.15. Cara Vértices 1 (0,0,0) (0,2,-1) (0,3,2) (0,1,2) NULL 2 (0,2,-1) (2,3,-1) (2,4,1) (0,3,2) NULL 3 Una alternativa simple es almacenar el modelo en una estructura jerárquica heterogénea, en la que la información asociada a cada cara sea una lista de aristas, y la normal a la cara. De cada arista se almacenan los dos vértices que la delimitan, y para cada vértice el punto en el que se encuentra. La estructura se puede completar con relaciones hacia arriba (de vértices a aristas, y de estas a caras). De este modo se eliminan las Figura 3.15 Poliedro mostrando redundancias y se almacenan parte de las relaciones topológicas. dos caras visibles Cara Aristas Las superficies de las caras y 1 0 1 2 3 NULL las líneas de las aristas se 2 4 5 6 1 NULL pueden calcular cuando sea 3 necesario a partir de los puntos que las delimitan. III-11  Diseño Asistido por Ordenador Vértice X Y Z 0 0 0 0 1 0 2 -1 2 0 3 2 3 0 1 2 4 2 4 1 5 2 3 -1 Para poder utilizar caras con agujeros es necesario complicar la estructura, almacenando para cada cara una secuencia de ciclos de aristas, de los que el primero es el perímetro exterior, y el resto agujeros practicados en él. Otra alternativa es utilizar falsas aristas, o aristas puente, para unir los perímetros interiores al exterior. Aristas con alas La estructura de datos más popular para almacenar un modelo de fronteras es la de aristas aladas (“winged-edge”) [Manty88, Baumgart72]. Esta estructura incorpora más relaciones topológicas y organiza la jerarquía partiendo de las aristas, lo que simplifica el tratamiento de caras con agujeros (cuando se utilizan aristas puente es necesario marcarlas para evitar dibujarlas, con la estructura de aristas aladas esto no es necesario ya que se detectan por tener la misma cara a derecha e izquierda). El elemento central de la estructura es la arista, en lugar de la cara. Cada arista almacena información de sus relaciones de vecindad con aristas y caras. Concretamente, cada arista contiene, además de su identificador: Sus dos vértices Las dos caras que comparten arista Las cuatro aristas que parten de ella, en las caras que la comparten. Las dos caras de la arista se etiquetan en función de como se recorra la cara cuando se va del vértice inicial al final de la arista, en clockwise (sentido de las agujas del reloj) y counterclockwise. La figura 3.16 muestra la información asociada a cada arista. El recorrido de los vértices se realiza en sentido anti-horario. Las tablas siguientes muestran parte de la información almacenada para el sólido de la figura 3.16. Aristas Vi Vf fcw fccw pccw nccw pcw ncw 0 0 1 1 3 1 1 1 2 1 2 0 2 6 4 2 2 3 1 1 3 3 3 0 1 2 0 4 5 1 2 1 5 5 4 5 2 4 6 6 2 4 2 5 1 III-12  Diseño Asistido por Ordenador Vértice X Y Z Cara Arista Normal 0 0 0 0 1 0 (1,0,0) 1 0 2 -1 2 4 (0,1,0) 2 0 3 2 3 0 1 2 4 2 4 1 5 2 3 -1 Figura 3.16 Sólido ejemplo Obsérvese que esta estructura no se puede utilizar para poliedros no variedad, ya que en ellos una arista podría tener más de dos caras vecinas. La alternativa para tratar este tipo de sólidos con estas representaciones es modificar el sólido para eliminar la singularidad, bien convirtiendo la arista en una unión sólida o desdoblándola (ver figura 3.17). Figura 3.17 El sólido no variedad de la izquierda se puede convertir para obtener un sólido 2-variedad 3.2.2 Cálculo de propiedades Aunque se almacenan las superficies, las propiedades volumétricas se pueden calcular de forma exacta a partir del teorema de la divergencia (o de Gauss, que es una generalización del de Stokes [Apost80]) que establece una relación entre la integral en volumen cerrado de la divergencia de un campo vectorial y la integral de superficie de la componente normal del campo en la superficie del volumen. Concretamente, el enunciado del teorema es: III-13  Diseño Asistido por Ordenador Teorema de la divergencia. Sea V un volumen en el espacio Euclídeo limitado por una superficie cerrada y orientable, S, y sea n la normal a S, orientada hacia el exterior. Para cualquier campo vectorial F, definido en V, se cumple: ∫∫∫ (div F )dV = ∫ F ⋅ ndS V S siendo S la superficie que encierra a V, n el vector normal a dicha superficie, (obsérvese que los vectores están notados usando negrita), y div el operador divergencia. Para una función vectorial F, dada por F(x,y,z) = (Fx ,Fy ,Fz) la divergencia se calcula como: dFx dFy dFz divF = ( , , ) x y z Calcular la propiedad volumétrica se reduce a una función F cuya divergencia sea igual a Gp, e integrar dicha función en la superficie del sólido. div( F ) = g Figura 3.18 Cilindro Ejemplo. Cálculo del peso de un cilindro. Supongamos un cilindro, cuyo eje sea paralelo al eje y, con altura h y radio de base r. Para calcular el peso se debe integrar la función constante r. Hay infinidad de funciones que cumplen esta condición, por ejemplo: Fa(x,y,z) = ρ (x/3, y/3, z/3) y Fb(x,y,z) = ρ (0, y, 0) En general, no es posible adaptar la función usada a la forma del sólido. En este caso es evidente que es más fácil integrar la segunda función. III-14  Diseño Asistido por Ordenador Podemos pues calcular el peso de un objeto integrando F· n en su superficie. Si el objeto es un cilindro vertical, bastara con integrar en las dos caras horizontales, ya que el producto escalar es cero en el resto. Por tanto el volumen será: ∫∫∫ (divF )dV = ∫ F ⋅ n dS = ∫ y r dS = p r hr 2 V S tapa 3.2.3 Edición La edición directa, moviendo puntos de control, aunque es factible cuando se restringe el método para utilizar caras triangulares, no es aconsejable, pues es demasiado laborioso. Los métodos de edición usuales en modeladores que trabajan con modelos de fronteras son: La combinación de instanciación de primitivas prediseñadas con operaciones de barrido sobre las caras. Las operaciones booleanas La modificación local del modelo por biselado de las aristas o vértices. Hablaremos brevemente de cada una de estas opciones. Las operaciones booleanas usadas son la unión, la intersección y la diferencia. No se usa el complemento, ya que produce sólidos no válidos. Para realizar una operación booleana entre dos sólidos se sigue el siguiente proceso: a) Clasificación de caras I. Calcular todas las líneas de intersección de las caras de A con las caras del sólido B y viceversa. II. Dividir las caras que están partidas por estas líneas. Para ello se unen las aristas consecutivas entre si para formar nuevas caras. III. Clasificar las caras de cada sólido respecto al otro sólido en externas e internas. b) Selección de caras IV. En función de la operación a realizar se clasifican las caras eligiendo las que forman parte del sólido resultado. Operación Caras AUB Caras de A externas a B y caras de B externas a A A∩B Caras de A internas a B y caras de B internas a A A-B Caras de A externas a B y caras de B internas a A c) Crear representación V. Reconstruir las relaciones entre elementos III-15  Diseño Asistido por Ordenador Se debe tener un cuidado especial al tratar las caras coplanarias, realizando la clasificación de las caras teniendo en cuenta la orientación de las dos caras. La figura 3.19 muestra el resultado que se obtendría con dos sólidos a los que coincide una cara si esto no se tiene en consideración, y como se deben clasificar dos caras coplanarias con la misma y distinta orientación en cada uno de las operaciones. Figura 3.19 Tratamiento de caras coplanarias al realizar operaciones booleanas El biselado consiste en sustituir una arista o un vértice por una cara. Aplicando reiteradas veces se puede obtener un sólido con perfil redondeado. El sistema modifica la representación del sólido creando las nuevas caras y modificando las relaciones de vecindad. Figura 3.20 Biselado de un cubo Una operación de barrido define un sólido por el volumen del espacio ocupado por una superficie cuando se desplaza a lo largo de una trayectoria, de un modo análogo a la construcción de una superficie por desplazamiento de una curva. La construcción más simple es realizar traslaciones o revoluciones, pero se pueden igualmente construir sólidos realizando un barrido generalizado, escalando y rotando la superficie mientras se desplaza a lo largo de una trayectoria arbitraria. Aún en este último caso, el conjunto de sólidos que se pueden generar es muy reducido. Por este motivo su utilización como método de representación en si mismo está muy limitado. III-16  Diseño Asistido por Ordenador Figura 3.21 Edición por barrido No obstante, es muy útil como método de modificación local de un modelo de fronteras, permitiendo su edición. De este modo se puede añadir materia a una cara del modelo realizando una extrusión a partir de la cara, o realizar una perforación haciendo una intrusión en la cara. En cualquier caso, el usuario dibuja la superficie a desplazar sobre la cara del sólido e indica el vector de desplazamiento. A partir de esta información el sistema puede generar automáticamente la información de las caras creadas. 3.2.4 Propiedades de la representación El modelo de fronteras es no ambiguo y su dominio es, cuando se usan caras planas, el conjunto de objetos formados por poliedros. Si se permiten caras no planas el dominio es mayor, ampliándose a los objetos curvos. En esta caso permite representar supericicies generales a costa de un mayor tiempo de proceso. La representación de cada sólido es única, salvo permutaciones de la información en las listas, si no se permiten caras coplanarias adyacentes, ya que de otro modo las caras podrían estar partidas en la estructura de datos de diversas formas. La principal debilidad del modelo es la validez, ya que cualquier conjunto de caras, vértices y aristas no define un sólido valido. Para asegurar la validez de la representación se imponen una serie de condiciones a ésta, que pueden verse como una restricción del conjunto imagen del método. Una representación de fronteras, para representar un sólido 2-variedad válido debe cumplir: i) Cada arista está delimitada por dos vértices. ii) Cada arista separa dos caras. iii) Las caras que coinciden en una arista tienen orientación conforme. iv) Las aristas solo se intersectan en los vértices. v) Las caras solo se intersectan en los vértices y las aristas. Las dos primeras condiciones se comprueban fácilmente cuando se utiliza una estructura de aristas aladas. Las tres últimas requieren la realización de comprobaciones geométricas que son costosas. Una forma rápida de detectar modelos no validos es comprobar la formula de Euler, que establece una relación invariente entre caras, aristas y vértices de cualquier poliedro: caras + vértices-aristas = anillos interiores + 2 * (cuerpos – perforaciones) F + V - E = R + 2( B- H) III-17  Diseño Asistido por Ordenador Donde un anillo es un perforación entrante en una cara, una perforación es un agujero que cruza el sólido y un cuerpo es un fragmento separado del sólido. La formula de Euler es una condición necesaria pero no suficiente para que la representación se corresponda con un sólido válido. Figura 3.22 Fórmula de Euler En el caso de objetos curvos, las aristas y superficies también son curvas. Se cumplen las mismas leyes que en los cuerspos poliédricos. Figura 3.23 Modelos curvos La representación puede ser exacta, si se trabaja con las correspondientes ecuaciones de las curvas y las superficies, o aproximada si se realizan representaciones faceteadas de las mismas. Figura 3.24 Representación faceteada de un cilindro y una esfera III-18  Diseño Asistido por Ordenador Estructura de datos: Figura 3.25 Estructura de datos B-rep La representación de fronteras presenta las siguientes características: Es un método popular, muy estendido por estar relacionado con el dibujo tradicional. Su principal ventaja reside en permitir constuir sólidos difíciles de modelar con primitivas básicas. Resulta fácil convertir una representación B-rep a alámbrico. Esta representación requiere mucho espacio de almacenamiento. Si no tiene interfaz CSG resulta lento, al tener que trabajar con operadores de Euler. III-19  Diseño Asistido por Ordenador 3.3 Métodos de descomposición Representan objetos sólidos mediante la unión de un conjunto de celdas disjuntas sin agujeros. S = U Ci La representación del sólido es la lista de celdas que ocupa, que se puede codificar como un bit de ocupación por cada celda (Ci), si la geometría de las celdas es fija, o como la lista de parámetros de las celdas ocupadas. Los métodos que utilizan celdas de geométrica fija suelen utilizarse para realizar representaciones aproximadas. Estos métodos se pueden utilizar para representar sólidos heterogéneos, añadiendo simplemente el valor de propiedad de cada celda. Los métodos de descomposición pueden estructurar las celdas en una estructura jerárquica, lo que ayuda a localizar información y a compactar la representación del modelo, este es el caso de los árboles octales (o de octantes, octrees), y de los árboles de partición binaria del espacio (BSP). Cuando la representación no es jerárquica se dice que el método de representación es una enumeración de celdas. En la siguiente sección se estudia la enumeración espacial y en la sección 3.3.2 los octrees. 3.3.1 Enumeración espacial El espacio donde reside el sólido se divide en cubos de igual tamaño que conforman una rejilla 3D. Por cada cubo (voxel), se almacena la información de ocupación del sólido, esto es, si el voxel pertenece o no al sólido. En la mayor parte de los casos es necesario realizar una aproximación, ya que el voxel no estará ni totalmente dentro ni totalmente fuera del sólido. La estructura de almacenamiento es simplemente un array 3D de booleanos. En cierto modo, la representación es semejante a una imagen 3D del sólido. El principal inconveniente de la representación, además de ser aproximada, es que no es concisa (ocupa mucho espacio). 3.3.2 Octrees Un octree describe, dentro de un cubo inicial y recursivamente los octantes ocupados por el sólido. Dado un cubo que encierra al sólido, se divide en ocho octantes, que podrán estar totalmente ocupados por el sólido, vacíos o parcialmente ocupados. Para los octantes que están parcialmente ocupados se repite el mismo proceso. Así hasta alcanzar un nivel de precisión prefijado. La representación puede verse como una compactación de una enumeración espacial. III-20  Diseño Asistido por Ordenador 3.3.3 Almacenamiento De forma natural la representación se puede almacenar como un árbol octal, en el que cada nodo interno representa un cubo parcialmente ocupado, y los nodos terminales puede estar ocupados o vacíos. Los ocho hijos de cada nodo interno representan los ocho subcubos en que se divide el cubo. Esta representación permite localizar de forma rápida la información de un nodo, pero requiere un espacio adicional para alojar los punteros a los hijos. Cuando no se va a operar con el sólido, por ejemplo para almacenarlo en un fichero, suele ser preferible una codificación lineal, obtenida mediante un recorrido del árbol (por ejemplo en orden central). Figura 3.26 Almacenamiento como árbol octal Figura 3.27 Codificación lineal 3.3.4 Búsqueda La localización de un punto del espacio en el árbol, que es necesaria para la mayor parte de las operaciones, y en concreto para saber si el punto está dentro del sólido, se puede realizar de forma rápida si se ha realizado el etiquetado de los nodos de forma adecuada. Concretamente se puede hacer que el índice del nodo hijo se obtenga por yuxtaposición de su posición relativa en las tres direcciones (ver figura). Asumiendo una resolución máxima conocida, esto es un tamaño conocido, d, del voxel más pequeño a usar, podemos calcular los índices de un voxel dado en coordenadas enteras, en el rango 0 a 2n, siendo n la máxima profundidad del árbol. III-21  Diseño Asistido por Ordenador Y Z X Figura 3.28 Etiquetado de los nodos 3.3.5 Operaciones booleanas La forma más simple de editar un octree es realizando operaciones booleanas. Dados dos octrees con la misma caja englobante, las operaciones booleanas se pueden calcular nodo a nodo, realizando un descenso sincronizado en los dos operandos. Las siguientes tablas muestran el procesamiento de las operaciones booleanas, representando por □ un nodo vacío, por uno lleno, y por un nodo interno. III-22  Diseño Asistido por Ordenador 3.3.6 Propiedades Los principales inconvenientes de la representación son su carácter aproximado y el espacio ocupado. Por otra parte, no es trivial realizar transformaciones geométricas, salvo rotaciones de múltiplos de 90 grados, escalados por múltiplos de dos o traslaciones en múltiplos del tamaño de un voxel. Como ventajas destacan la facilidad para realizar operaciones booleanas y calcular propiedades. Las propiedades volumétricas se pueden calcular realizando una simple sumatoria sobre el conjunto de nodos terminales ocupados: Pr opiedad ( Sólido) = ∫∫∫ G p ( x, y, z , )dV = ∑G p nodos llenos (voxel ) ⋅ V (voxel ) Vol ( Sólido ) Se han realizado varias extensiones del método de representación para permitir una representación exacta de sólidos poliédricos. Entre estas cabe destacar los octrees extendidos, que incluyen información de la geometría de la frontera en los nodos terminales. 3.4 Geometria constructiva de solidos (CSG) Este método esta basado en la noción topología de que un objeto puede dividirse en un conjunto de primitivas combinadas de cierta forma por un conjunto de reglas para formar el objeto. La geometría constructiva de sólidos (CSG) no representa explícitamente la geométrica del sólido, si no que lo describe como una expresión booleana, en la que intervienen primitivas (sólidos básicos predefinidos). Más formalmente, un modelo CSG se puede expresar como Sólido = Tg1 (Sólido1) OpB Tg2 (Sólido2) l Tg3 (primitiva) donde las Tg son transformaciones geométricas y OpB es una operación booleana: U ó + → Unión ∩ ó ‫ → ׀‬Intersección - → Diferencia Obviamente la representación es muy concisa, pero a costa de no almacenar explícitamente la geometría, lo que hace que la visualización no sea trivial. Del objeto se obtienen las caras, aristas y vértices. 3.4.1 Primitivas sólidas simples Como ya se ha indicado, los sólidos se pueden construir partiendo de un conjunto de primitivas adecuadamente combinadas por medio de las correspondientes operaciones booleanas. Exiten dos tipos de primitivas: Primitivas con fronteras (r-sets) Primitivas sin fronteras (non r-sets), estas definen semiespacios III-23  Diseño Asistido por Ordenador Las primitivas r-sets (conjunto regular acotado) son más concisas, las non r-sets puede ser practicas en ocasiones, por ejemplo en el cálculo de intersecciones. Sólido Figura 3.29 Primitivas con fronteras y sin fronteras Las primitivas con fronteras, que puede estar parametrizadas, se representan como intersección de semiespacios, lo que permite un tratamiento homogéneo de todo el árbol. Para definirlas completamente se precisan dos conjuntos de datos geométricos: Parámetros de configuración, que definen sus dimensiones geométricas Parámetros de posicionamiento, que definen su orientación y localización en el espacio Entre las primitivas más usuales en los sistemas de modelado sólido se encuentran las siguientes: 1. Bloque: Origen, altura, anchura y profundidad. 2. Cilindro: Origen, radio y longitud. 3. Cono: Origen, radio base, radio superior y altura. 4. Esfera: Centro, y radio (diámetro). 5. Cuña: Origen, altura, anchura y profundidad de la base. 6. Toro: Centro, radio mayor, radio menor (o radio interno y radio externo). Bloque Cilindro Cono Toro 0