En gráficos por computadora en 3D y modelado de sólidos , una malla poligonal es una colección devértices ,borde syface sque define la forma de unobjetopoliédrico. Las caras generalmente consisten entriángulos(malla triangular),cuadriláteros(quads) u otrospolígonos convexossimples(n-gons), ya que esto simplifica elrenderizado, pero también puede estar compuesto más generalmente porpolígonos cóncavos, o incluso polígonos con agujeros.
El estudio de mallas poligonales es un gran subcampo de gráficos por computadora (específicamente gráficos por computadora en 3D) y modelado geométrico . Se utilizan diferentes representaciones de mallas poligonales para diferentes aplicaciones y objetivos. La variedad de operaciones realizadas en mallas puede incluir: lógica booleana , 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 renderizan los bordes de la malla en lugar de las caras, el modelo se convierte en un modelo de estructura alámbrica .
Las mallas volumétricas son distintas 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]
Elementos
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, 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 muchos de estos, 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, por lo que no es necesario almacenar una malla en forma triangulada .
Representaciones
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:
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 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 aristas o caras vecinas; esto requiere estructuras más complejas como la representación del borde alado. Para la renderización de hardware, se necesitan estructuras compactas y simples; por lo tanto, la mesa de esquina (ventilador triangular) se incorpora comúnmente en API de renderizado de bajo nivel como DirectX y OpenGL .
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, 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 bordes y caras no se realizan fácilmente.
Sin embargo, las mallas VV se benefician de un espacio de almacenamiento pequeño y de una transformació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. Observe que los dos últimos vértices, 8 y 9 en el centro superior e inferior del "cilindro-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 dado.
Para obtener una descripción completa de las mallas VV, consulte Smith (2006). [2]
Mallas cara-vértice
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, siendo la entrada generalmente aceptada por el hardware de gráficos moderno.
Las mallas cara-vértice mejoran la malla VV para el modelado, ya que permiten una 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 "cilindro de caja" como una malla FV. Vertex v5 se resalta 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 todos los vértices tengan el mismo número de caras circundantes.
Para el renderizado, la lista de caras generalmente se transmite a la GPU como un conjunto de índices a vértices, y los vértices se envían como posición / color / estructuras normales (en la figura, solo se da 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 un recorrido sencillo de todas las estructuras. Con las 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 la localización de caras y vértices vecinos es un tiempo constante. Sin embargo, los bordes están 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 cara-vértice.
Mallas de borde alado
Introducidas por Baumgart en 1975, las mallas de bordes alados representan explícitamente los vértices, caras y bordes 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 con alas en el libro Graphics Gems II .
Las mallas de borde con alas abordan el problema de atravesar de borde a borde y proporcionan un conjunto ordenado de caras alrededor de un borde. Para cualquier borde dado, el número de bordes salientes puede ser arbitrario. Para simplificar esto, las mallas de borde alados proporcionan solo cuatro, los bordes más cercanos en sentido horario y antihorario en cada extremo. Los otros bordes se pueden atravesar de forma incremental. Por lo tanto, la información de cada borde se asemeja a una mariposa, por lo tanto, mallas de "borde alado". La figura anterior muestra el "cilindro de caja" como una malla de borde alado. Los datos totales de un borde constan de 2 vértices (puntos finales), 2 caras (en cada lado) y 4 bordes (borde alado).
La representación de mallas de 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 borde 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 cruce a través de la malla, como podría ser necesario para la detección de colisiones, se puede lograr de manera eficiente.
Ver Baumgart (1975) para más detalles. [3]
Renderizar mallas dinámicas
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 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 mallas FV) y las caras y vértices de un borde ( como borde alado).
Renderizar mallas dinámicas requiere un poco menos de espacio de almacenamiento que las mallas de borde de ala estándar, y se puede renderizar 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 un borde a otro y luego de un lado a otro.
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.
Consulte Tobler & Maierhofer ( WSCG 2006) para obtener más detalles. [4]
Resumen de la representación de la malla
Operación | Vértice-vértice | Vértice de la cara | Borde alado | Renderizar dinámico | |
---|---|---|---|---|---|
VV | Todos los vértices alrededor del vértice | Explícito | V → f1, f2, f3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... | V → e1, e2, e3, ... → v1, v2, v3, ... |
EF | Todos los bordes de una cara | F (a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Explícito | Explícito |
VF | Todos los vértices de una cara | F (a, b, c) → {a, b, c} | Explícito | F → e1, e2, e3 → a, b, c | Explícito |
FV | Todas las caras alrededor de un vértice | Búsqueda de pares | Explícito | V → e1, e2, e3 → f1, f2, f3, ... | Explícito |
EV | Todos los bordes alrededor de un vértice | V → {v, v1}, {v, v2}, {v, v3}, ... | V → f1, f2, f3, ... → v1, v2, v3, ... | Explícito | Explícito |
FE | Ambas caras de un borde | Lista comparar | Lista comparar | Explícito | Explícito |
VE | Ambos vértices de una arista | E (a, b) → {a, b} | E (a, b) → {a, b} | Explícito | Explícito |
Flook | Encuentra cara con vértices dados | F (a, b, c) → {a, b, c} | Establecer la intersección de v1, v2, v3 | Establecer la intersección de v1, v2, v3 | Establecer la intersección de v1, v2, v3 |
Tamaño de almacenamiento | V * promedio (V, V) | 3F + V * promedio (F, V) | 3F + 8E + V * promedio (E, V) | 6F + 4E + 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 | 6 * 16 + 4 * 24 + 10 * 5 = 242 | ||
Figura 6: resumen de las operaciones de representación de la malla |
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 lista indica que se debe realizar una comparación de lista 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 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 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, use la lista de caras para encontrar los vértices a su alrededor. Tenga en cuenta que las mallas de borde alado almacenan explícitamente casi toda la información, y otras operaciones siempre atraviesan el borde primero 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 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 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 tablas de medio borde y de esquina. Todas estas son variantes de cómo los vértices, caras y aristas se indexan entre sí.
Como regla general, las mallas cara-vértice se utilizan siempre que un objeto debe renderizarse en hardware de gráficos que no cambia la geometría (conectividad), pero que puede deformarse o transformarse en forma (posiciones de vértice), como la renderización en tiempo real de objetos estáticos o cambiantes. . Las mallas dinámicas de renderizado o de borde con alas se utilizan cuando cambia la geometría, como en paquetes de modelado interactivo o para calcular superficies de subdivisión. Las mallas vértice-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 una preocupación.
Otras representaciones
Formatos de archivo
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. Algunos de estos formatos se presentan a continuación:
Sufijo de archivo | Nombre de formato | Organización (es) | Programa (s) | Descripción |
---|---|---|---|---|
.crudo | Malla cruda | Desconocido | Varios | Formato abierto, solo ASCII. Cada línea contiene 3 vértices, separados por espacios, para formar un triángulo, así: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 |
.mezcla | Formato de archivo de Blender | Fundación Blender | Licuadora 3D | Código abierto, formato solo binario |
.fbx | Formato de Autodesk FBX | Autodesk | Varios | Propiedad. Existen especificaciones binarias y ASCII. |
.3ds | Archivo 3ds Max | Autodesk | 3ds máximo | Un formato común pero desactualizado con límites estrictos de 16 bits en el número de vértices y caras. Ni estandarizado ni bien documentado, pero solía ser un "estándar de facto" para el intercambio de datos. |
.dae | Bolsa de Activos Digitales (COLLADA) | Sony Computer Entertainment , Khronos Group | N / A | Soportes para " COLLA borative D esign A ctividad". Un formato universal diseñado para evitar incompatibilidades. |
.dgn | Archivo de MicroStation | Bentley Systems | MicroStation | Hay dos formatos de archivo dgn: pre-versión 8 y versión 8 (V8) |
.3dm | Archivo Rhino | Robert McNeel y asociados | Rinoceronte 3D | |
.dxf , .dwg | Formato de intercambio de dibujos | Autodesk | AutoCAD | |
.obj | OBJ de frente de onda | Tecnologías Wavefront | Varios | Formato ASCII que describe la geometría 3D. Los vértices de todas las caras se ordenan en sentido antihorario, lo que hace implícitas las normales de faceta. Las normales suaves se especifican por vértice. |
.capa | Formato de archivo de polígono | Universidad Stanford | Varios | Binario y ASCII |
.pmd | Datos de Polygon Movie Maker | Yu Higuchi | MikuMikuDance | Formato de archivo binario patentado para almacenar la geometría del modelo humanoide con información de rigging, material y física. |
.stl | Formato de estereolitografía | Sistemas 3D | Muchos | Formato binario y ASCII diseñado originalmente para ayudar en CNC . |
.amf | Formato de archivo de fabricación aditiva | ASTM Internacional | N / A | Como el formato STL, pero con color nativo, material y compatibilidad con constelaciones. |
.wrl | Lenguaje de modelado de realidad virtual | Consorcio Web3D | Navegadores web | Norma ISO 14772-1: 1997 |
.wrz | VRML comprimido | Consorcio Web3D | Navegadores web | |
.x3d, .x3db, .x3dv | 3D extensible | Consorcio Web3D | Navegadores web | Basado en XML, de código abierto, libre de regalías, extensible e interoperable; también admite información de color, textura y escena. Norma ISO 19775/19776/19777 |
.x3dz, .x3dbz, .x3dvz | Binario comprimido X3D | Consorcio Web3D | Navegadores web | |
.c4d | Archivo Cinema 4D | MAXON | CINE 4D | |
.lwo | Archivo de objeto LightWave 3D | NewTek | LightWave 3D | |
.smb | SCOREC apf | RPI SCOREC | PUMI | Mallas 3D no estructuradas adaptativas paralelas de código abierto para flujos de trabajo de simulación basados en PDE. |
.msh | Malla Gmsh | Desarrolladores de GMsh | Proyecto GMsh | Código abierto, que proporciona una descripción de malla ASCII para elementos interpolados lineales y polinomiales en 1 a 3 dimensiones. |
.malla | XML OGRE | Equipo de desarrollo de OGRE | OGRE, puro básico | Fuente abierta. Disponible en formato binario (.mesh) y ASCII (.mesh.xml). Incluye datos para la animación de vértices y la animación de destino Morph (blendshape). Datos de animación esquelética en un archivo separado (.skeleton). |
.veg | Malla tetraédrica Vega FEM | Jernej Barbič | Vega FEM | Fuente abierta. Almacena una malla tetraédrica y sus propiedades de material para la simulación FEM. Formatos ASCII (.veg) y binarios (.vegb) disponibles. |
. z3d | Z3d | Oleg Melashenko | Modelador Zanoza | - |
.vtk | Malla VTK | VTK , Kitware | VTK , Paraview | Formato abierto, ASCII o binario que contiene muchos campos de datos diferentes, incluidos datos de puntos, datos de celda y datos de campo. |
.l4d | Dibujo LAI4D | Laboratorio de Inteligencia Artificial para el Diseño | LAI4D | Formato de datos ASCII que describe un árbol jerárquico de entidades. |
Ver también
- B-rep
- Operador de Euler
- Hypergraph
- Múltiple (una malla puede ser múltiple o no múltiple)
- Subdivisión de malla (una técnica para agregar detalles a una malla poligonal)
- Modelado de polígonos
- Poligonizador
- Simplex
- T-spline
- Triangulación (geometría)
- Modelo de estructura de alambre
Referencias
- ^ Lorensen, William E .; Cline, Harvey E. (1 de agosto de 1987). "Marchando cubos: un algoritmo de construcción de superficie 3D de alta resolución". Gráficos por computadora ACM SIGGRAPH . 21 (4): 163-169. CiteSeerX 10.1.1.545.613 . doi : 10.1145 / 37402.37422 .
- ^ a b Colin Smith, sobre mallas vértice-vértice y su uso en modelado geométrico y biológico , ( PDF )
- ^ Bruce Baumgart, Representación de poliedro de borde alado para visión por computadora. 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 .
- ^ Tobler & Maierhofer, una estructura de datos de malla para renderizado y subdivisión. 2006 . ( PDF )
enlaces externos
- Weisstein, Eric W. "Simplicial complex" . MathWorld .
- Weisstein, Eric W. "Triangulación" . MathWorld .
- Representación de malla de medio borde de código abierto OpenMesh .
- Biblioteca de procesamiento de malla poligonal