En gráficos por computadora 3D y modelado sólido , una malla poligonal es una colección devértices ,borde sycara sque define la forma de unpoliédrico. Las carassuelen consistir entriángulos(malla triangular),cuadriláteros(quads) u otrospolígonos convexos(n-gons), ya que esto simplificala representación, pero también pueden estar compuestas más generalmente porpolígonos cóncavoso incluso polígonos con agujeros.
El estudio de las mallas poligonales es un gran subcampo de los gráficos por computadora (específicamente los gráficos por computadora en 3D) y el modelado geométrico . Se utilizan diferentes representaciones de mallas poligonales para diferentes aplicaciones y objetivos. La variedad de operaciones realizadas sobre mallas puede incluir: lógica booleana ( geometría sólida constructiva ), suavizado , simplificación y muchas otras. También existen algoritmos para trazado de rayos , detección de colisiones y dinámica de cuerpos rígidos con mallas poligonales. Si se representan los bordes de la malla en lugar de las caras, entonces el modelo se convierte en un modelo de estructura alámbrica .
Las mallas volumétricas 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 solo representan explícitamente la superficie (el volumen está implícito).
Existen varios métodos para la generación de mallas , incluido el algoritmo de cubos en marcha . [1]
Los objetos creados con mallas poligonales deben almacenar diferentes tipos de elementos. Estos incluyen vértices, aristas, caras, polígonos y superficies. En muchas aplicaciones, sólo se almacenan los vértices, aristas y caras o polígonos. Un renderizador puede admitir solo caras de 3 lados, por lo que se deben construir polígonos con muchas de ellas, como se muestra arriba. Sin embargo, muchos renderizadores admiten quads y polígonos de lados superiores, o pueden convertir polígonos en triángulos sobre la marcha, lo que hace innecesario almacenar una malla en forma triangulada .
Las mallas poligonales se pueden representar de diversas formas, utilizando diferentes métodos para almacenar los datos de vértices, aristas y caras. Éstas incluyen:
VV" malla representa sólo vértices, que apuntan a otros vértices. Tanto la información del borde como de la cara está implícita en la representación. Sin embargo, la simplicidad de la representación no permite realizar muchas operaciones eficientes en las mallas.Cada una de las representaciones anteriores tiene ventajas e inconvenientes particulares, que se analizan con más detalle en Smith (2006). [2] La elección de la estructura de datos se rige 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 determinadas operaciones es necesario tener un acceso rápido a información topológica como aristas o caras vecinas; esto requiere estructuras más complejas, como la representación del borde alado. Para el renderizado de hardware, se necesitan estructuras compactas y simples; por lo tanto, la tabla de esquina (ventilador triangular) se incorpora comúnmente en API de renderizado de bajo nivel como DirectX y OpenGL .
.png/1280px-Vertex-Vertex_Meshes_(VV).png)
Las mallas vértice-vértice representan 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 ya que la información de cara y borde está implícita. Por lo tanto, es necesario recorrer los datos para generar una lista de caras para renderizar. Además, las operaciones en aristas y caras no se realizan fácilmente.
Sin embargo, las mallas VV se benefician del pequeño espacio de almacenamiento y de una eficiente transformación de la forma. 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, 8 y 9 en el centro superior e inferior del "cilindro de caja", tienen cuatro vértices conectados en lugar de cinco. Un sistema general debe poder manejar un número arbitrario de vértices conectados a cualquier vértice determinado.
Para obtener una descripción completa de las mallas VV, consulte Smith (2006). [2]
Las mallas cara-vértice representan un objeto como un conjunto de caras y un conjunto de vértices. Esta es la representación de malla más utilizada y es la entrada que suele aceptar el hardware de gráficos moderno.
Las mallas cara-vértice mejoran las mallas VV para modelado porque permiten la búsqueda explícita de los vértices de una cara y de las caras que rodean un vértice. La figura anterior muestra el ejemplo de "cilindro de caja" como una malla FV. Vertex v5 está resaltado para mostrar las caras que lo rodean. Observe que, en este ejemplo, se requiere que cada cara tenga 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 generalmente se transmite a la GPU como un conjunto de índices de vértices, y los vértices se envían como estructuras de posición/color/normal (en la figura, solo se proporciona la posición). Esto tiene la ventaja de que los cambios de forma, pero no de geometría, se pueden actualizar dinámicamente simplemente reenviando los datos del vértice sin actualizar la conectividad de la cara.
El modelado requiere atravesar fácilmente todas las estructuras. Con mallas cara-vértice 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 localizar caras y vértices vecinos es un tiempo constante. Sin embargo, las aristas están implícitas, por lo que aún es necesaria una búsqueda para encontrar todas las caras que rodean una cara determinada. Otras operaciones dinámicas, como dividir o fusionar una cara, también resultan difíciles con las mallas de cara-vértice.
Introducidas por Baumgart en 1975, las mallas de bordes alados representan explícitamente los vértices, caras y aristas de una malla. Esta representación se usa ampliamente en programas de modelado para proporcionar la mayor flexibilidad al cambiar dinámicamente la geometría de la malla, porque las operaciones de división y fusión se pueden realizar rápidamente. Su principal inconveniente son los grandes requisitos de almacenamiento y la mayor complejidad debido al mantenimiento de muchos índices. Se puede encontrar una buena discusión sobre los problemas de implementación de las mallas de borde alado en el libro Graphics Gems II .
Las mallas de bordes alados abordan la cuestión de atravesar de un borde a otro y proporcionar un conjunto ordenado de caras alrededor de un borde. Para cualquier arista dada, el número de aristas salientes puede ser arbitrario. Para simplificar esto, las mallas con bordes alados proporcionan solo cuatro, los 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. Los otros bordes se pueden recorrer de forma incremental. Por lo tanto, la información de cada borde se asemeja a una mariposa, de ahí que se trate de mallas de "borde alado". La figura de arriba muestra el "cilindro de caja" como una malla con bordes alados. Los datos totales de una arista constan de 2 vértices (puntos finales), 2 caras (en cada lado) y 4 aristas (arista alada).
La representación de mallas con bordes alados para hardware de gráficos requiere generar una lista de índice de caras. Por lo general, esto se hace solo cuando cambia la geometría. Las mallas de 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 podría ser necesario para la detección de colisiones, se puede lograr de manera eficiente.
Véase Baumgart (1975) para más detalles. [3]
Las mallas de bordes alados no son la única representación que permite cambios dinámicos en la geometría. Una nueva representación que combina mallas de bordes alados y mallas de cara-vértice es la malla dinámica de renderizado , 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 vértices de un borde ( como borde alado).
Las mallas dinámicas de renderizado requieren un poco menos de espacio de almacenamiento que las mallas de borde alado estándar y pueden renderizarse directamente mediante hardware de gráficos, 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 de cara a vértice. Las mallas RD no requieren los cuatro bordes salientes, ya que estos se pueden encontrar atravesando de borde a cara y luego de cara a borde vecino.
Las mallas RD se benefician de las características de las mallas de borde alado al permitir que la geometría se actualice dinámicamente.
Véase Tobler y Maierhofer (WSCG 2006) para más detalles. [4]
En la tabla anterior, 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 de listas entre dos listas para realizar la operación; y la búsqueda por pares indica que se debe realizar una búsqueda en dos índices. La notación promedio(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 cara-vértice, primero es necesario encontrar las caras alrededor del vértice V dado usando la lista de vértices. Luego, a partir de esas caras, usa la lista de caras para encontrar los vértices a su alrededor. Las mallas de borde alado almacenan explícitamente casi toda la información, y otras operaciones siempre atraviesan primero el borde para obtener información adicional. Las mallas vértice-vértice son la única representación que almacena explícitamente los vértices vecinos de un vértice determinado.
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 en tiempo al recorrido y la topología de varios elementos, pero a costa de una mayor sobrecarga y espacio para mantener los índices correctamente.
La Figura 7 muestra la información de conectividad para cada una de las cuatro técnicas descritas en este artículo. También existen otras representaciones, como mesas de medio borde y de esquina. Todas estas son variantes de cómo los vértices, las caras y las aristas se indexan entre sí.
Como regla general, las mallas de cara-vértice se utilizan siempre que un objeto debe representarse en hardware de gráficos que no cambia la geometría (conectividad), pero puede deformarse o transformarse (posiciones de los vértices), como la representación en tiempo real de objetos estáticos o transformables. . Las mallas dinámicas de renderizado o de borde alado se utilizan cuando la geometría cambia, como en paquetes de modelado interactivos o para calcular superficies de subdivisión. Las mallas vértice-vértice son ideales para cambios complejos y eficientes en geometría o topología, siempre que la representación del hardware no sea un problema.
Existen muchos formatos de archivo diferentes para almacenar datos de malla poligonal. Cada formato es más eficaz cuando se utiliza para el propósito previsto por su creador. Los formatos populares incluyen .fbx , .dae , .obj y .stl . A continuación se presenta una tabla con algunos de estos formatos: