En gráficos de computadora 3D y modelado de sólidos , una malla poligonal es una colección devértices ,borde sycara sque define la forma de unobjetopoliédricoLas carassuelen estar formadas portriángulos(malla de triángulos),cuadriláteros(quads) u otrospolígonos convexos(n-gonos), ya que esto simplificala representación, pero también pueden estar compuestas de forma más general porpolígonos cóncavoso inclusopolí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 en las mallas puede incluir: lógica booleana ( geometría sólida constructiva ), suavizado , simplificación y muchas otras. También existen algoritmos para el trazado de rayos , la detección de colisiones y la 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 es implícito).
Existen varios métodos para la generación de mallas , incluido el algoritmo de cubos de marcha . [1]
Los objetos creados con mallas poligonales deben almacenar distintos tipos de elementos, como vértices, aristas, caras, polígonos y superficies. En muchas aplicaciones, solo se almacenan vértices, aristas y caras o polígonos. Un renderizador puede admitir solo caras de 3 lados, por lo que los polígonos deben construirse con muchas de ellas, como se muestra arriba. Sin embargo, muchos renderizadores admiten cuadriláteros y polígonos de más lados, 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 maneras, utilizando distintos métodos para almacenar los datos de vértices, aristas y caras. Entre ellos se incluyen:
VVmalla " " representa únicamente vértices que apuntan a otros vértices. Tanto la información de las aristas como de las caras 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 y desventajas particulares, que se analizan más a fondo en Smith (2006). [2] La elección de la estructura de datos está regida 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 tratar con triángulos que con polígonos generales, especialmente en geometría computacional . Para ciertas operaciones es necesario tener un acceso rápido a información topológica como bordes o caras vecinas; esto requiere estructuras más complejas como la representación de borde alado. Para la representación de hardware, se necesitan estructuras compactas y simples; por lo tanto, la tabla de esquinas (abanico de triángulos) se incorpora comúnmente en las API de representación 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 porque la información de las caras y los bordes está implícita. Por lo tanto, es necesario recorrer los datos para generar una lista de caras para la representación. Además, las operaciones sobre los bordes y las caras no son fáciles de realizar.
Sin embargo, las mallas VV se benefician de un espacio de almacenamiento pequeño y una transformación eficiente 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 la parte superior e inferior central del "cilindro-caja", tienen cuatro vértices conectados en lugar de cinco. Un sistema general debe poder manejar una cantidad arbitraria de vértices conectados a cualquier vértice dado.
Para una descripción completa de las mallas VV, consulte 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 y es la entrada que generalmente acepta el hardware gráfico moderno.
Las mallas de vértices de caras mejoran las mallas VV para el modelado, ya que permiten la búsqueda explícita de los vértices de una cara y las caras que rodean un vértice. La figura anterior muestra el ejemplo de "caja-cilindro" como una malla FV. El vértice 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 la misma cantidad de caras circundantes.
Para la representación, la lista de caras se transmite generalmente a la GPU como un conjunto de índices para los 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 en la forma, pero no en la geometría, se pueden actualizar dinámicamente simplemente reenviando los datos de los vértices sin 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 es un proceso de tiempo constante. Sin embargo, los bordes son implícitos, por lo que aún se necesita 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 son difíciles con las mallas de caras y vértices.
Introducidas por Baumgart en 1975, las mallas de aristas aladas representan explícitamente los vértices, las caras y las aristas de una malla. Esta representación se utiliza ampliamente en programas de modelado para proporcionar la mayor flexibilidad a la hora de cambiar dinámicamente 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 grandes requisitos de almacenamiento y la mayor complejidad debido al mantenimiento de muchos índices. Se puede encontrar un buen análisis de los problemas de implementación de las mallas de aristas aladas en el libro Graphics Gems II .
Las mallas de aristas con alas resuelven el problema de atravesar de arista a arista y proporcionar un conjunto ordenado de caras alrededor de una arista. Para cualquier arista dada, la cantidad de aristas salientes puede ser arbitraria. Para simplificar esto, las mallas de aristas con alas proporcionan solo cuatro, las aristas más cercanas en sentido horario y antihorario en cada extremo. Las otras aristas se pueden atravesar de manera incremental. Por lo tanto, la información para cada arista se asemeja a una mariposa, de ahí las mallas de "aristas con alas". La figura anterior muestra la "caja-cilindro" como una malla de aristas con alas. Los datos totales para una arista consisten en 2 vértices (puntos finales), 2 caras (en cada lado) y 4 aristas (arista con alas).
La representación de mallas de bordes con alas para hardware gráfico requiere la generación de una lista de índices de caras. Esto se hace generalmente solo cuando cambia la geometría. Las mallas de bordes con alas 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 realizar de manera eficiente.
Véase Baumgart (1975) para más detalles. [3]
Las mallas de aristas con alas no son la única representación que permite realizar cambios dinámicos en la geometría. Una nueva representación que combina mallas de aristas con alas y mallas de vértices de caras es la malla dinámica de renderizado , que almacena explícitamente tanto los vértices de una cara y las caras de un vértice (como las mallas FV) como las caras y los vértices de una arista (como las mallas de aristas con alas).
Las mallas dinámicas de renderizado requieren un poco menos de espacio de almacenamiento que las mallas de aristas con alas estándar 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 de cara a vértice. Las mallas RD no requieren las cuatro aristas salientes, ya que se pueden encontrar recorriendo desde la arista hasta la cara y luego desde la cara hasta la arista vecina.
Las mallas RD se benefician de las características de las mallas de bordes alados 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, explicit indica que la operación se puede realizar en tiempo constante, ya que los datos se almacenan directamente; list compare indica que se debe realizar una comparación de listas entre dos listas para realizar la operación; y pair search 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 dado V" utilizando la malla de cara-vértice, es necesario encontrar primero las caras alrededor del vértice dado V utilizando la lista de vértices. Luego, a partir de esas caras, utilizar la lista de caras para encontrar los vértices a su alrededor. Las mallas de aristas con alas 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-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 brinda un acceso más directo y constante en el tiempo al recorrido y la topología de varios elementos, pero a costa de un mayor espacio y sobrecarga para mantener los índices de manera adecuada.
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 las tablas de medio borde y de esquina. Todas ellas son variantes de cómo los vértices, las caras y los bordes se indexan entre sí.
Como regla general, las mallas de vértice-cara se utilizan siempre que se debe renderizar un objeto en hardware gráfico que no cambia la geometría (conectividad), pero puede deformar o transformar la forma (posiciones de vértice), como la renderización en tiempo real de objetos estáticos o que se transforman. Las mallas de borde alado o de renderizado dinámico se utilizan cuando cambia la geometría, como en paquetes de modelado interactivo o para calcular superficies de subdivisión. Las mallas de vértice-vértice son ideales para cambios complejos y eficientes en la geometría o la topología, siempre que la renderización del hardware no sea un problema.
Existen muchos formatos de archivo diferentes para almacenar datos de mallas poligonales. Cada formato es más eficaz cuando se utiliza para el propósito previsto por su creador. Los formatos más populares incluyen .fbx , .dae , .obj y .stl . A continuación, se presenta una tabla con algunos de estos formatos: