Malla triangular

Una forma de compartir datos de vértices entre triángulos es mediante tiras de triángulos. En estas tiras, cada triángulo comparte una arista completa con un vecino y otra con el siguiente. Otra forma es mediante abanicos de triángulos , que consisten en un conjunto de triángulos conectados que comparten un vértice central. Con estos métodos, los vértices se gestionan de forma eficiente, lo que reduce la necesidad de procesar solo N+2 vértices para dibujar N triángulos. ^{[ 3 ]}

Las tiras triangulares son eficientes, pero traducir una malla triangular a un conjunto mínimo de tiras triangulares es un problema NP-completo . ^{[ 4 ]}

La estructura de datos que representa la malla admite dos operaciones básicas: insertar y eliminar triángulos. También admite una operación de colapso de aristas, útil en esquemas de decimación de triángulos. La estructura no admite las posiciones de los vértices, pero asume que a cada vértice se le asigna un identificador entero único, generalmente el índice de ese vértice en una matriz de posiciones de vértices contiguas. Un vértice de la malla se define mediante un único entero y se denota por hvi. Una arista de la malla se define mediante un par de enteros hv0,v1i, donde cada entero corresponde a un extremo de la arista. Para admitir mapas de aristas, estas se almacenan de forma que v0 = min(v0,v1). Un componente triangular se define mediante una tripleta de enteros hv0,v1,v2i, donde cada entero corresponde a un vértice del triángulo. Para admitir mapas de triángulos, estos se almacenan de forma que v0 = min(v0,v1,v2). Cabe destacar 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 tríos en la estructura de datos. Para evitar recordatorios constantes sobre el orden de los índices, en el resto del documento la información de pares/tríos no implica que los vértices estén ordenados de ninguna manera (aunque la implementación sí maneja el orden).

La conectividad entre los componentes está completamente determinada por el conjunto de ternas 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. Las conexiones inversas también son conocidas. 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 información que almacena una estructura de datos depende de las necesidades de la aplicación. Además, la aplicación podría requerir información adicional almacenada en los componentes. La información almacenada en un vértice, arista o triángulo se denomina atributo de vértice, atributo de arista o atributo de triángulo. Las representaciones abstractas de estos para la estructura de datos simple descrita aquí son:

Vértice = <entero>; // v Edge = <entero, entero>; // v0, v1 Triángulo <entero,entero,entero>; // v0, v1, v2 VData = <datos de vértice específicos de la aplicación>; EData = <datos de borde específicos de la aplicación>; TData = <datos triangulares específicos de la aplicación>; VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset EAttribute = <EData, set<Triangle>>; // datos, tset TAttribute = <TData>; // datos VPair = pair<Vertex,VAttribute>; EPair = pair<Edge,EAttribute>; TPair = pair<Triangle,TAttribute>; VMap = map<VPair>; EMap = map<EPair>; TMap = map<TPair>; Malla = <VMap,EMap,TMap>; // 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 no existe. La eliminación se produce solo si el elemento ya existe.

Esta operación consiste en identificar una arista hvk, vti, donde vk se denomina vértice de conservación y vt, vértice de eliminación. Los triángulos que comparten esta arista se eliminan de la malla. El vértice vt también se elimina de la malla. Cualquier triángulo que compartiera vt ve su vértice reemplazado por vk. La figura 1 muestra una malla triangular y una secuencia de tres colapsos de aristas aplicados a la malla.

Con los arrays de índices, una malla se representa mediante dos arrays separados: uno que contiene los vértices y otro que contiene conjuntos de tres índices dentro de ese array, los cuales definen un triángulo. El sistema gráfico procesa primero los vértices y luego renderiza los triángulos, utilizando los conjuntos de índices que trabajan con los datos transformados. En OpenGL, esto es compatible con la primitiva glDrawElements() cuando se utiliza un objeto de búfer de vértices (VBO).

Con este método, cualquier conjunto arbitrario de triángulos que compartan un número arbitrario de vértices puede almacenarse, manipularse y pasarse a la API gráfica, sin ningún procesamiento intermedio.