stringtranslate.com

Malla poligonal

Ejemplo de una malla triangular de baja poli que representa un delfín

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 dela superficiede un objetopoliédrico. Simplificala representación, como en unmodelo de estructura alámbrica. Lascarassuelen constar detriángulos(malla de triángulos),cuadriláteros(cuadriláteros) u otrospolígonos convexos(n-gonos). Una malla poligonal también puede estar compuesta 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 .

Existen varios métodos para la generación de mallas , incluido el algoritmo de cubos de marcha . [1]

Las mallas volumétricas se diferencian de las mallas poligonales en que representan explícitamente tanto la superficie como la región interior de una estructura, mientras que las mallas poligonales solo representan explícitamente la superficie (el volumen es implícito).

Elementos

Elementos de modelado de malla poligonal.

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 .

vértice
Una posición (generalmente en el espacio 3D) junto con otra información como color, vector normal y coordenadas de textura.
borde
Una conexión entre dos vértices.
rostro
Un conjunto cerrado de aristas, en el que una cara triangular tiene tres aristas y una cara cuadrada tiene cuatro aristas. Un polígono es un conjunto coplanar de caras. En 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 de 3 o 4 lados, por lo que los polígonos se representan como múltiples caras. Matemáticamente, una malla poligonal puede considerarse una cuadrícula no estructurada o un gráfico no dirigido, con propiedades adicionales de geometría, forma y topología.
superficies
Los grupos de suavizado , más a menudo llamados grupos de suavizado , son útiles, pero no necesarios para agrupar regiones suaves. Considere un cilindro con tapas, como una lata de refresco. Para un sombreado suave de los lados, todas las normales de la superficie deben apuntar horizontalmente lejos del centro, mientras que las normales de las tapas deben apuntar directamente hacia arriba y hacia abajo. Representados como una única superficie sombreada con Phong , los vértices de los pliegues tendrían normales incorrectas. Por lo tanto, se necesita alguna forma de determinar dónde dejar de suavizar para agrupar partes suaves de una malla, al igual que los polígonos agrupan caras de 3 lados. Como alternativa a proporcionar superficies/grupos de suavizado, una malla puede contener otros datos para calcular los mismos datos, como un ángulo de división (los polígonos con normales por encima de este umbral se tratan automáticamente como grupos de suavizado separados o se aplica automáticamente alguna técnica como división o biselado al borde entre ellos). Además, las mallas de muy alta resolución están menos sujetas a problemas que requerirían grupos de suavizado, ya que sus polígonos son tan pequeños que hacen que la necesidad sea irrelevante. Además, existe otra alternativa: simplemente se pueden separar las superficies del resto de la malla. Los renderizadores no intentan suavizar los bordes de los polígonos no contiguos.
grupos
Algunos formatos de malla contienen grupos que definen elementos separados de la malla y son útiles para determinar subobjetos separados para la animación esquelética o actores separados para la animación no esquelética.
materiales
Generalmente se definirán los materiales , lo que permitirá que diferentes partes de la malla utilicen diferentes sombreadores al renderizarse.
Coordenadas UV
La mayoría de los formatos de malla también admiten algún tipo de coordenadas UV , que son una representación 2D independiente de la malla "desplegada" para mostrar qué parte de un mapa de textura bidimensional se debe aplicar a los diferentes polígonos de la malla. También es posible que las mallas contengan otra información de atributos de vértice como color, vectores tangentes, mapas de peso para controlar la animación , etc. (a veces también llamados canales ).

Representaciones

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:

Mallas de caras y vértices
Una lista simple de vértices y un conjunto de polígonos que apuntan a los vértices que utiliza.
De borde alado
en la que cada borde apunta a dos vértices, dos caras y los cuatro bordes (en sentido horario y antihorario) que los tocan. Las mallas de bordes alados permiten atravesar la superficie en tiempo constante, pero con mayores requisitos de almacenamiento.
Mallas de medio borde
Similar a las mallas de bordes alados, excepto que solo se utiliza la mitad de la información de recorrido de los bordes. (ver OpenMesh)
Mallas de cuatro bordes
que almacenan aristas, medias aristas y vértices sin ninguna referencia a polígonos. Los polígonos están implícitos en la representación y se pueden encontrar recorriendo la estructura. Los requisitos de memoria son similares a los de las mallas de media arista.
Mesas de esquina
que almacenan vértices en una tabla predefinida, de modo que al recorrer la tabla se definen implícitamente los polígonos. En esencia, se trata del abanico de triángulos que se utiliza en la representación de gráficos por hardware. La representación es más compacta y más eficiente para recuperar polígonos, pero las operaciones para cambiarlos son lentas. Además, las tablas de esquinas no representan mallas por completo. Se necesitan varias tablas de esquinas (abanicos de triángulos) para representar la mayoría de las mallas.
Mallas de vértice a vértice
Una 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 .

Mallas de vértice a vértice

Figura 2. Mallas vértice-vértice
Figura 2. Mallas vértice-vértice

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]

Mallas de caras y vértices

Figura 3. Mallas de caras y vértices
Figura 3. Mallas de caras y vértices

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.

Mallas con bordes alados

Figura 4. Mallas con bordes alados

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]

Renderizar mallas dinámicas

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]

Resumen de la representación de malla

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.

Otras representaciones

Mallas de transmisión
Almacena las caras de forma ordenada, pero independiente, para que la malla pueda transmitirse en fragmentos. El orden de las caras puede ser espacial, espectral o estar basado en otras propiedades de la malla. Las mallas de transmisión continua permiten renderizar una malla muy grande incluso mientras se está cargando.
Mallas progresivas
Transmite los datos de vértices y caras con niveles de detalle cada vez mayores. A diferencia de las mallas de transmisión , las mallas progresivas dan la forma general de todo el objeto, pero con un nivel de detalle bajo. Los datos adicionales, los nuevos bordes y caras, aumentan progresivamente el detalle de la malla.
Mallas normales
Transmiten cambios progresivos a una malla como un conjunto de desplazamientos normales a partir de una malla base. Con esta técnica, una serie de texturas representan las modificaciones incrementales deseadas. Las mallas normales son compactas, ya que solo se necesita un único valor escalar para expresar el desplazamiento. Sin embargo, la técnica requiere una serie compleja de transformaciones para crear las texturas de desplazamiento.

Formatos de archivos

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:

Véase también

Referencias

  1. ^ Lorensen, William E.; Cline, Harvey E. (1 de agosto de 1987). "Cubos de marcha: un algoritmo de construcción de superficies 3D de alta resolución". ACM SIGGRAPH Computer Graphics . 21 (4): 163–169. CiteSeerX  10.1.1.545.613 . doi :10.1145/37402.37422.
  2. ^ ab Colin Smith, Sobre las mallas vértice-vértice y su uso en el modelado geométrico y biológico, ( PDF )
  3. ^ Bruce Baumgart, Representación de poliedros con aristas aladas para visión artificial. Conferencia Nacional de Computación, mayo de 1975. "Uso de poliedros en visión artificial". baumgart.org . Mayo de 1975. Archivado desde el original el 29 de agosto de 2005. Consultado el 29 de agosto de 2005 .
  4. ^ Tobler & Maierhofer, Una estructura de datos en malla para renderización y subdivisión. 2006. ( PDF )

Enlaces externos