Una malla triangular es un tipo de malla poligonal en gráficos por computadora . Comprende un conjunto de triángulos (típicamente en tres dimensiones ) que están conectados por sus bordes o esquinas comunes.
Muchos paquetes de software de gráficos y dispositivos de hardware pueden operar de manera más eficiente en triángulos que están agrupados en mallas que en un número similar de triángulos que se presentan individualmente. Esto se debe típicamente a que los gráficos por computadora realizan operaciones en los vértices de las esquinas de los triángulos. Con triángulos individuales, el sistema tiene que operar en tres vértices por cada triángulo. En una malla grande, podría haber ocho o más triángulos reunidos en un solo vértice; procesando esos vértices solo una vez, es posible hacer una fracción del trabajo y lograr un efecto idéntico. En muchas aplicaciones de gráficos por computadora es necesario administrar una malla de triángulos. Los componentes de la malla son vértices, aristas y triángulos. Una aplicación puede requerir el conocimiento de las diversas conexiones entre los componentes de la malla. Estas conexiones se pueden gestionar independientemente de las posiciones reales de los vértices. Este documento describe una estructura de datos simple que es conveniente para administrar las conexiones. Ésta no es la única estructura de datos posible. Existen muchos otros tipos y admiten diversas consultas sobre mallas.
Representación
Son posibles varios métodos para almacenar y trabajar con una malla en la memoria de la computadora. Con los OpenGL y DirectX API hay dos formas principales de pasar una malla de triángulos con el hardware gráfico, tiras de triángulos y matrices de índice.
Tira triangular
Una forma de compartir datos de vértices entre triángulos es la tira de triángulos. Con tiras de triángulos, cada triángulo comparte un borde completo con un vecino y otro con el siguiente. Otra forma es el abanico triangular , que es un conjunto de triángulos conectados que comparten un vértice central. Con estos métodos, los vértices se tratan de manera eficiente, lo que resulta en la necesidad de procesar solo N + 2 vértices para dibujar N triángulos.
Las tiras triangulares son eficientes, sin embargo, el inconveniente es que puede no ser obvio o conveniente traducir una malla triangular arbitraria en tiras.
La estructura de datos
La estructura de datos que representa la malla proporciona soporte para dos operaciones básicas: insertar triángulos y eliminar triángulos. También admite una operación de colapso de bordes que es útil en esquemas de diezmado de triángulos. La estructura no proporciona soporte para las posiciones de los vértices, pero asume que a cada vértice se le asigna un identificador entero único, típicamente el índice de ese vértice en una matriz de posiciones de vértice contiguas. Un vértice de malla se define por un solo entero y se denota por hvi. Un borde de malla está definido por un par de números enteros hv0, v1i, cada número entero correspondiente a un punto final del borde. Para admitir mapas de bordes, los bordes se almacenan de modo que v0 = min (v0, v1). Un componente de triángulo se define por un triple de números enteros hv0, v1, v2i, cada número entero corresponde a un vértice del triángulo. Para admitir mapas de triángulos, los triángulos se almacenan de modo que v0 = min (v0, v1, v2). Observe que hv0, v1, v2i y hv0, v2, v1i se tratan como triángulos diferentes. Una aplicación que requiera triángulos de doble cara debe insertar ambos triples en la estructura de datos. Con el fin de evitar recordatorios constantes sobre el orden de los índices, en el resto del documento la información de pares / triples no implica que los vértices se estén ordenando de ninguna manera (aunque la implementación sí maneja el orden). La conectividad entre los componentes está completamente determinada por el conjunto de triples que representan los triángulos. Un triángulo t = hv0, v1, v2i tiene vértices v0, v1 y v2. Tiene aristas e0 = hv0, v1i, e1 = hv1, v2i y e2 = hv2, v0i. También se conocen las conexiones inversas. El vértice v0 es adyacente a las aristas e0 y e2 y al triángulo t. El vértice v1 es adyacente a las aristas e0 y e1 y al triángulo t. El vértice v2 es adyacente a las aristas e1 y e2 y al triángulo t. Las tres aristas e0, e1 y e2 son adyacentes a t. La cantidad de esta información que almacena una estructura de datos depende de las necesidades de una aplicación. Además, es posible que la aplicación desee tener información adicional almacenada en los componentes. La información almacenada en un vértice, borde o triángulo se denomina atributo de vértice, atributo de borde o atributo de triángulo. Las representaciones abstractas de estos para la estructura de datos simple descrita aquí son
Vértice =; // vEdge =; ,>// v0, v1Triángulo; ,>// v0, v1, v2VData =; EData =; TData =; VAttribute =, establecer ,>// datos, eset, tsetEAttribute =>; ángulo>>; ,>// datos, tsetTAttribute =; // datosVPair = par; értice,>EPair = par; ,>TPair = par; ángulo,>VMap = mapa; EMap = mapa; TMap = mapa; Malla =; ,>// vmap, emap, tmap
Los mapas admiten las funciones estándar de inserción y eliminación de una tabla hash. La inserción se produce solo si el elemento aún no existe. La eliminación ocurre solo si el artículo existe.
Colapso de borde
Esta operación implica identificar una arista hvk, vti donde vk se llama vértice de conservación y vt se llama vértice de lanzamiento. Los triángulos que comparten este borde se eliminan de la malla. El vértice vt también se elimina de la malla. Cualquier triángulo que comparta vt tiene ese vértice reemplazado por vk. La Figura 1 muestra una malla triangular y una secuencia de tres colapsos de bordes aplicados a la malla.
Matriz de índice
Con las matrices de índice, una malla está representada por dos matrices separadas, una matriz que contiene los vértices y otra que contiene conjuntos de tres índices en esa matriz que define un triángulo. El sistema de gráficos procesa los vértices primero y luego renderiza los triángulos, usando los conjuntos de índices que trabajan en los datos transformados. En OpenGL, esto es compatible con la primitiva glDrawElements () cuando se usa Vertex Buffer Object (VBO).
Con este método, cualquier conjunto arbitrario de triángulos que compartan cualquier número arbitrario de vértices puede almacenarse, manipularse y pasarse a la API de gráficos, sin ningún procesamiento intermedio.
Ver también
- Hypergraph
- Algoritmo de Möller-Trumbore para la intersección de rayos y triángulos
- Malla Nonobtuse
- B-spline racional no uniforme
- Punto de nube
- Malla poligonal
- Triangulación (geometría)