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 = <integer, integer>; // v0, v1 Triangle <integer,integer,integer>; // v0, v1, v2 VData = <application-specific vertex data>; EData = <application-specific edge data>; TData = <application-specific triangle data>; VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset EAttribute = <EData, set<Triangle>>; // data, tset TAttribute = <TData>; // data VPair = pair<Vertex,VAttribute>; EPair = pair<Edge,EAttribute>; TPair = pair<Triangle,TAttribute>; VMap = map<VPair>; EMap = map<EPair>; TMap = map<TPair>; Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap 

The maps support the standard insertion and removal functions for a hash table. Insertion occurs only if the item does not already exist. Removal occurs only if the item does exist.

This operation involves identifying an edge hvk, vti where vk is called the keep vertex and vt is called the throw vertex. The triangles that share this edge are removed from the mesh. The vertex vt is also removed from the mesh. Any triangles that shared vt have that vertex replaced by vk. Figure 1 shows a triangle mesh and a sequence of three edge collapses applied to the mesh.

With index arrays, a mesh is represented by two separate arrays, one array holding the vertices, and another holding sets of three indices into that array which define a triangle. The graphics system processes the vertices first and renders the triangles afterwards, using the index sets working on the transformed data. In OpenGL, this is supported by the glDrawElements() primitive when using Vertex Buffer Object (VBO).

With this method, any arbitrary set of triangles sharing any arbitrary number of vertices can be stored, manipulated, and passed to the graphics API, without any intermediary processing.