Una malla poligonal ( jar. mesh del inglés malla poligonal ) es una colección de vértices, aristas y caras que definen la forma de un objeto poliédrico en gráficos tridimensionales por computadora y modelado volumétrico. Las caras suelen ser triángulos , quads u otros polígonos convexos simples (polígonos) ya que esto simplifica el renderizado , pero las mallas también pueden estar compuestas por los polígonos cóncavos más comunes.[ aclarar ] , o polígonos con agujeros.
La doctrina de las cuadrículas poligonales es una gran subsección de los gráficos por computadora y el modelado geométrico. Las muchas operaciones realizadas en mallas pueden incluir álgebra booleana , suavizado, simplificación y muchas otras. Se utilizan diferentes representaciones de malla para diferentes propósitos y aplicaciones. Para transmitir mallas poligonales a través de la red, se utilizan representaciones de red como mallas de "transmisión" y "progresivas". Las mallas de volumen se diferencian de las mallas poligonales en que representan explícitamente tanto la superficie como el volumen de una estructura, mientras que las mallas poligonales representan explícitamente solo la superficie, no el volumen. Dado que las mallas poligonales se utilizan ampliamente en gráficos por computadora, se han desarrollado para ellas algoritmos de trazado de rayos , detección de colisiones y dinámica de cuerpos rígidos .
El equivalente matemático de las mallas poligonales (mallas no estructuradas ) se estudia mediante métodos de geometría combinatoria .
Los objetos creados con mallas poligonales deben almacenar diferentes tipos de elementos como vértices, aristas, caras, polígonos y superficies. En muchos casos, solo se almacenan los vértices, las aristas y las caras o los polígonos. El renderizador solo admite caras de tres lados, por lo que se deben construir polígonos a partir de muchas de ellas, como se muestra en la Fig. 1. Sin embargo, muchos renderizadores admiten polígonos con cuatro o más lados, o pueden triangular los polígonos en triángulos sobre la marcha, por lo que no es necesario almacenar la malla en forma de triángulo. También en algunos casos, como el modelado de una cabeza, es deseable poder crear polígonos de tres y cuatro lados.
Un vértice es una posición junto con otra información como color, vector normal y coordenadas de textura. Una arista es una conexión entre dos vértices. Una cara es un conjunto cerrado de aristas, en el que una cara triangular tiene tres aristas y una cara cuadrangular tiene cuatro. Un polígono es un conjunto de caras coplanares (que se encuentran en el mismo plano). En los sistemas que admiten caras de varios lados, los polígonos y las caras son equivalentes. Sin embargo, la mayoría del hardware de renderizado solo admite caras con tres o cuatro lados, por lo que los polígonos se representan como varias caras. Matemáticamente, una malla poligonal se puede representar como una malla no estructurada o un gráfico no dirigido, con la adición de propiedades de geometría, forma y topología.
Las superficies , más comúnmente conocidas como grupos de suavizado , son útiles pero no necesarias para agrupar áreas suavizadas. Imagine un cilindro con tapas, como una lata. Para un sombreado lateral uniforme, todas las normales deben apuntar horizontalmente desde el centro, mientras que las normales de los párpados deben apuntar en direcciones +/-(0,0,1). Si se renderiza como una sola superficie sombreada con Phong , los vértices del pliegue tendrían normales incorrectas. Por lo tanto, necesitamos una forma de determinar dónde dejar de suavizar para agrupar las partes suaves de la malla, de la misma manera que los polígonos agrupan caras de 3 lados. Como alternativa a proporcionar superficies/grupos suaves, la malla puede contener otra información para calcular los mismos datos, como un ángulo de separación (los polígonos con normales por encima de este límite se tratan automáticamente como grupos de fusión separados, o se aplica alguna técnica al borde entre ellos, como división o biselado). Además, las mallas de muy alta resolución son menos propensas a problemas que requieren grupos de suavizado para resolver, ya que sus polígonos son tan pequeños que no son necesarios. Además, existe una alternativa en la posibilidad de simplemente despegar las propias superficies del resto de la malla. Los renderizadores no intentan suavizar los bordes entre polígonos no contiguos.
El formato de malla también puede definir otros datos útiles. Se pueden definir grupos que definen elementos de malla individuales y son útiles para establecer subobjetos individuales para animación esquelética o sujetos individuales para animación no esquelética. Los materiales generalmente están definidos , lo que permite que diferentes partes de la malla usen diferentes sombreadores cuando se renderizan. La mayoría de los formatos de malla también asumen coordenadas UV , que son una representación 2D separada de la malla, "desenvuelta" para mostrar la cantidad de textura 2D que se aplica a diferentes polígonos de malla.
Las mallas de polígonos se pueden representar de muchas maneras, utilizando diferentes formas de almacenar vértices, aristas y caras. Incluyen:
Cada vista tiene sus propias ventajas y desventajas. [una]
La elección de la estructura de datos está determinada por la aplicación, el rendimiento requerido, el tamaño de los datos y las operaciones a realizar. Por ejemplo, es más fácil trabajar con triángulos que con polígonos generales, especialmente en geometría computacional . Para ciertas operaciones es necesario tener acceso rápido a información topológica como aristas o caras vecinas; esto requiere estructuras más complejas, como una representación "alada". La representación de hardware requiere estructuras compactas y simples; por lo tanto, las API de bajo nivel, como DirectX y OpenGL , suelen incluir una tabla de ángulos (ventiladores triangulares).
Una representación de vértice describe un objeto como un conjunto de vértices conectados a otros vértices. Esta es la representación más simple, pero no se usa mucho porque la información de la cara y el borde no se expresa explícitamente. Por lo tanto, es necesario revisar todos los datos para generar una lista de caras para renderizar. Además, las operaciones sobre aristas y caras no se realizan fácilmente.
Sin embargo, las mallas VI se benefician del bajo uso de memoria y la transformación eficiente. La Figura 2 muestra un ejemplo de una caja dibujada usando un VI de malla. Cada vértice indexa sus vértices vecinos. Tenga en cuenta que los dos últimos vértices, 8 y 9 en la parte superior e inferior de la caja, tienen cuatro vértices conectados, no cinco. El sistema principal debe manejar un número arbitrario de vértices asociados con cualquier vértice dado.
Para una descripción más detallada de las mallas VP, ver Smith (2006). [una]
Una malla que utiliza una lista de caras representa un objeto como un conjunto de caras y un conjunto de vértices. Esta es la representación más utilizada, siendo la entrada normalmente aceptada por el hardware de gráficos moderno.
Una lista de caras es mejor para el modelado que una representación de vértices, ya que permite una búsqueda explícita de los vértices de una cara y las caras que rodean un vértice. La Figura 3 muestra un ejemplo de una caja de malla usando una lista de caras. Vertex v5 se resalta para mostrar los bordes que lo rodean. Tenga en cuenta que en este ejemplo, cada cara debe tener 3 vértices. Sin embargo, esto no significa que cada vértice tenga el mismo número de caras circundantes.
Para el renderizado, la cara generalmente se envía a la GPU como un conjunto de índices de vértices, y los vértices se envían como estructuras de posición/color/normales (en la figura solo se proporciona la posición). Por lo tanto, los cambios de forma, pero no los cambios de geometría, pueden actualizarse dinámicamente simplemente retransmitiendo los datos del vértice sin actualizar la conectividad de la cara.
El modelado requiere un fácil recorrido de todas las estructuras. Con una malla usando una lista de caras, es muy fácil encontrar los vértices de una cara. Además, la lista de vértices contiene una lista de todas las caras asociadas con cada vértice. A diferencia de la representación de vértices, tanto las caras como los vértices se representan explícitamente, por lo que encontrar caras y vértices vecinos es constante en el tiempo. Sin embargo, los bordes no se especifican explícitamente, por lo que aún se necesita una búsqueda para encontrar todos los bordes que rodean un borde determinado. Otras operaciones dinámicas, como rasgar o fusionar una cara, también son complicadas con una lista de caras.
Introducido por Bruce Baumgart en 1975, Winged Representation representa explícitamente los vértices, caras y bordes de una malla. Esta representación se usa mucho en los 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 separación y combinación se pueden realizar rápidamente. Su principal desventaja son los altos requisitos de memoria y la mayor complejidad debido al contenido de muchos índices.
La representación alada resuelve el problema transversal de borde a borde y proporciona un conjunto ordenado de caras alrededor del borde. Para cualquier borde dado, el número de bordes salientes puede ser arbitrario. Para simplificar esto, la representación alada solo proporciona los cuatro bordes más cercanos en el sentido de las agujas del reloj y en el sentido contrario a las agujas del reloj en cada extremo del borde. Otros bordes se pueden pasar por alto gradualmente. Por lo tanto, la información sobre cada borde se parece a una mariposa, por lo que la representación se llama "alada". La Figura 4 muestra un ejemplo de una caja en una representación "alada". Los datos de borde completos consisten en dos vértices (puntos finales), dos caras (en cada lado) y cuatro bordes ("alas" del borde).
La representación de una representación alada por hardware de gráficos requiere la generación de una lista de índices de rostros. Esto generalmente se hace solo cuando cambia la geometría. La representación alada es ideal para la geometría dinámica, como la subdivisión de superficies y el modelado interactivo, porque los cambios de malla pueden ocurrir localmente. Caminar alrededor de la malla, que puede ser útil para la detección de colisiones, se puede hacer de manera eficiente.
Ver Baumgart (1975) para más detalles [2]
| Operación | Representación de vértice | Lista de caras | actuación "alada" | ||
|---|---|---|---|---|---|
| vv | Todos los vértices alrededor del vértice. | Claramente | V → f1, f2, f3, … → v1, v2, v3, … | V → e1, e2, e3, … → v1, v2, v3, … | |
| FE | Todos los bordes de una cara | F(a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Claramente | |
| FV | Todos los vértices de una cara. | F(a,b,c) → {a,b,c} | Claramente | F → e1, e2, e3 → a, b, c | |
| VF | Todos los bordes alrededor de la parte superior | Búsqueda de pareja | Claramente | V → e1, e2, e3 → f1, f2, f3, … | |
| VE | Todos los bordes alrededor del vértice. | V → {v, v1}, {v, v2}, {v, v3}, … | V → f1, f2, f3, … → v1, v2, v3, … | Claramente | |
| FE | Ambos bordes del borde | Comparación de listas | Comparación de listas | Claramente | |
| VE | Ambos vértices de la arista | E(a, b) → {a, b} | E(a, b) → {a, b} | Claramente | |
| Flook | Encuentra cara con vértices dados | F(a,b,c) → {a,b,c} | Intersección de conjuntos v1,v2,v3 | Intersección de conjuntos v1,v2,v3 | |
| Tamaño de la memoria | V*promedio(V,V) | 3F + V*promedio(F,V) | 3F + 8E + V*promedio(E,V) | ||
| Ejemplo con 10 vértices, 16 caras, 24 aristas: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | |||
| Figura 5: Resumen de las operaciones de vista de cuadrícula | |||||
En la tabla anterior, se indica explícitamente que la operación se puede realizar en tiempo constante, ya que los datos se almacenan directamente; comparación de listas indica que se deben comparar dos listas para realizar la operación; y la búsqueda por pares indica que se van a realizar dos búsquedas de índice. La notación avg(V,V) significa el número promedio de vértices conectados a un vértice dado; avg(E,V) es 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 designación “V → f1, f2, f3, … → v1, v2, v3, …” muestra que la operación requiere un recorrido alrededor de varios elementos. Por ejemplo, para obtener "todos los vértices alrededor de un vértice V dado" usando una lista de caras, primero se deben encontrar las caras alrededor de un vértice V dado usando una lista de vértices. Luego, a partir de estas caras, utilizando la lista de caras, encuentra los vértices que las rodean. Tenga en cuenta que la representación alada almacena casi toda la información explícitamente, y otras operaciones siempre atraviesan el borde primero para obtener más información. Una vista de vértice es la única vista que almacena explícitamente los vértices vecinos de un vértice dado.
A medida que aumenta la complejidad de las representaciones (de izquierda a derecha en el resumen), aumenta explícitamente la cantidad de información almacenada. Esto brinda un acceso más directo y constante en el tiempo al recorrido y la topología de los diversos elementos, pero a costa de más memoria para almacenar los índices correctamente.
Como regla general, las mallas de lista de caras se usan cuando un objeto necesita ser renderizado por hardware que no cambia la geometría (conexiones) pero que puede deformarse o transformarse (posiciones de vértice), como renderizar objetos estáticos o transformar objetos en tiempo real. La representación "alada" se utiliza cuando cambia la geometría, por ejemplo, en paquetes de modelado interactivo o para calcular superficies subdivididas. La vista de vértice es ideal para cambios complejos y eficientes en la geometría o la topología, siempre que la representación del hardware no sea importante.
Las mallas de transmisión almacenan las caras de forma ordenada pero independiente para que la malla se pueda enviar en fragmentos. El orden de las caras puede ser espacial, espectral o basado en otras propiedades de la malla. Las mallas de transmisión le permiten renderizar mallas muy grandes incluso mientras aún se están cargando.
Las mallas progresivas proporcionan datos de vértices y caras con niveles de detalle cada vez mayores. A diferencia de las mallas de flujo , las mallas progresivas dan la forma general de todo el objeto, pero con un bajo nivel de detalle. Datos adicionales, nuevos bordes y caras, aumentan progresivamente el detalle de la malla.
Las mallas normales transmiten cambios de malla graduales como un conjunto de desplazamientos normales desde la malla base. Con esta técnica, una serie de texturas muestra los cambios incrementales deseados. Las cuadrículas normales son compactas porque solo se necesita un valor escalar para expresar el desplazamiento. Sin embargo, la técnica requiere una serie de transformaciones complejas para crear texturas cortantes.
Las mallas poligonales se pueden almacenar en una variedad de formatos de archivo :