Malla poligonal

En términos de gráficos por computadora, un vértice es una estructura de datos que describe la posición de un punto en un espacio de 2, 3 o 4 dimensiones sobre una superficie , junto con atributos opcionales (otros valores utilizados para renderizar el objeto correctamente). La mayoría de los atributos de un vértice representan vectores en el espacio que se va a renderizar . Estos vectores suelen ser de 2 ( x, y ) o 3 ( x, y, z ) dimensiones y pueden incluir una cuarta coordenada homogénea ( w ). En la renderización en tiempo real, estas propiedades son utilizadas por un sombreador de vértices o una canalización de vértices .

Los atributos pueden incluir posición, color, reflectancia, especularidad , coordenadas de mapeo de textura , vectores normales y mapeo de desplazamiento .

Las mallas vértice-vértice representan un objeto como un conjunto de vértices conectados entre sí. Esta es la representación más simple, pero no se usa ampliamente, ya que la información de caras y aristas es implícita. Por lo tanto, es necesario recorrer los datos para generar una lista de caras para la renderización. Además, las operaciones sobre aristas y caras no son fáciles de realizar.

Sin embargo, las mallas VV se benefician de un espacio de almacenamiento reducido y una deformación de forma eficiente. La figura anterior muestra una caja de cuatro lados representada por una malla VV. Cada vértice indexa sus vértices vecinos. Los dos últimos vértices, el 8 y el 9, situados en la parte superior e inferior del centro del "cilindro-caja", tienen cuatro vértices conectados en lugar de cinco. Un sistema general debe ser capaz de gestionar un número arbitrario de vértices conectados a cualquier vértice dado.

Para una descripción completa de las mallas VV, véase Smith (2006). ^{[ 2 ]}

Las mallas de caras y vértices representan un objeto como un conjunto de caras y un conjunto de vértices. Esta es la representación de malla más utilizada, ya que es la entrada que suelen aceptar los equipos gráficos modernos.

Las mallas de caras y vértices mejoran las mallas VV para el modelado, ya que permiten la búsqueda explícita de los vértices de una cara y de las caras que la rodean. La figura anterior muestra el ejemplo de "cilindro-caja" como una malla FV. El vértice v5 está resaltado para mostrar las caras que lo rodean. Nótese que, en este ejemplo, cada cara debe tener exactamente 3 vértices. Sin embargo, esto no significa que cada vértice tenga el mismo número de caras circundantes.

Para la renderización, la lista de caras se suele transmitir a la GPU como un conjunto de índices de vértices, y estos últimos se envían como estructuras de posición, color y normal (en la figura, solo se indica la posición). Esto permite actualizar dinámicamente la forma, pero no la geometría, simplemente reenviando los datos de los vértices sin necesidad de actualizar la conectividad de las caras.

El modelado requiere un recorrido sencillo de todas las estructuras. Con las mallas de caras y vértices, es fácil encontrar los vértices de una cara. Además, la lista de vértices contiene una lista de caras conectadas a cada vértice. A diferencia de las mallas VV, tanto las caras como los vértices son explícitos, por lo que la localización de caras y vértices vecinos se realiza en tiempo constante. Sin embargo, las aristas son implícitas, por lo que aún se requiere una búsqueda para encontrar todas las caras que rodean una cara dada. Otras operaciones dinámicas, como dividir o fusionar una cara, también resultan difíciles con las mallas de caras y vértices.

Introducidas por Baumgart en 1975 ^{[ 3 ]} , las mallas de aristas aladas representan explícitamente los vértices, caras y aristas de una malla. Esta representación se utiliza ampliamente en programas de modelado para proporcionar la mayor flexibilidad en la modificación dinámica de la geometría de la malla, ya que las operaciones de división y fusión se pueden realizar rápidamente. Su principal inconveniente son los elevados requisitos de almacenamiento y la mayor complejidad derivada del mantenimiento de numerosos índices. Un buen análisis de los problemas de implementación de las mallas de aristas aladas se puede encontrar en el libro Graphics Gems II ^{[ 4 ]} .

Las mallas de aristas aladas abordan el problema del recorrido de arista en arista, proporcionando un conjunto ordenado de caras alrededor de una arista. Para cualquier arista dada, el número de aristas salientes puede ser arbitrario. Para simplificar esto, las mallas de aristas aladas proporcionan solo cuatro: las aristas más cercanas en sentido horario y antihorario en cada extremo. Las demás aristas se pueden recorrer de forma incremental. La información de cada arista se asemeja, por lo tanto, a una mariposa, de ahí el nombre de mallas de "aristas aladas". La figura anterior muestra el "cilindro-caja" como una malla de aristas aladas. Los datos totales de una arista constan de 2 vértices (puntos extremos), 2 caras (en cada lado) y 4 aristas (aristas aladas).

La renderización de mallas con bordes alados para hardware gráfico requiere generar una lista de índices de caras, lo que generalmente solo se realiza cuando cambia la geometría. Las mallas con bordes alados son ideales para geometría dinámica, como superficies de subdivisión y modelado interactivo, ya que los cambios en la malla pueden ocurrir localmente. El recorrido a través de la malla, como el que se requiere para la detección de colisiones, se puede realizar de manera eficiente.

Las mallas de borde alado no son la única representación que permite cambios dinámicos en la geometría. Una representación que combina mallas de borde alado y mallas de cara-vértice es la malla dinámica de renderizado (RDM), que almacena explícitamente tanto los vértices de una cara como las caras de un vértice (como las mallas FV), y las caras y los vértices de una arista (como el borde alado).

Las mallas RDM requieren menos espacio de almacenamiento que las mallas estándar de aristas aladas y pueden renderizarse directamente mediante hardware gráfico, ya que la lista de caras contiene un índice de vértices. Además, el recorrido de vértice a cara es explícito (tiempo constante), al igual que el de cara a vértice. Las mallas RDM no requieren las cuatro aristas salientes, ya que estas se pueden encontrar recorriendo de arista a cara y luego de cara a arista vecina. Las mallas RDM se benefician de las características de las mallas de aristas aladas al permitir la actualización dinámica de la geometría.

Para más detalles, véase Tobler y Maierhofer ( WSCG 2006). ^{[ 5 ]}

En la siguiente tabla, "explícito" indica que la operación se puede realizar en tiempo constante, ya que los datos se almacenan directamente; " comparación de listas" indica que se debe realizar una comparación entre dos listas para completar la operación; y "búsqueda de pares " indica que se debe realizar una búsqueda en dos índices. La notación avg(V,V) significa el número promedio de vértices conectados a un vértice dado; avg(E,V) significa el número promedio de aristas conectadas a un vértice dado, y avg(F,V) es el número promedio de caras conectadas a un vértice dado.

La notación "V → f1, f2, f3, ... → v1, v2, v3, ..." describe que se requiere un recorrido a través de múltiples elementos para realizar la operación. Por ejemplo, para obtener "todos los vértices alrededor de un vértice V dado" usando la malla de caras y vértices, es necesario primero encontrar las caras alrededor del vértice V dado usando la lista de vértices. Luego, a partir de esas caras, usar la lista de caras para encontrar los vértices alrededor de ellas. Las mallas de aristas aladas almacenan explícitamente casi toda la información, y otras operaciones siempre recorren primero la arista para obtener información adicional. Las mallas de vértice a vértice son la única representación que almacena explícitamente los vértices vecinos de un vértice dado.

A medida que las representaciones de la malla se vuelven más complejas (de izquierda a derecha en el resumen), aumenta la cantidad de información almacenada explícitamente. Esto proporciona un acceso más directo y constante al recorrido y la topología de los distintos elementos, pero a costa de un mayor gasto de recursos y espacio para mantener los índices correctamente.

Por regla general, las mallas de vértices de caras se utilizan cuando un objeto debe renderizarse en hardware gráfico que no modifica su geometría (conectividad), pero sí su forma (posiciones de vértices), como en la renderización en tiempo real de objetos estáticos o en movimiento. Las mallas de aristas aladas o de renderizado dinámico se utilizan cuando la geometría cambia, como en programas de modelado interactivo o para el cálculo de superficies de subdivisión. Las mallas de vértice a vértice son ideales para cambios complejos y eficientes en la geometría o la topología, siempre que la renderización por hardware no sea un factor determinante.