graphics - Triangulación de polígono con agujeros
geometry direct3d (9)
CGAL tiene la herramienta que necesita: Triangulaciones restringidas
Simplemente puede proporcionar límites de su polígono (incluyendo los límites de los agujeros) como restricciones (lo mejor sería insertar todos los vértices y luego especificar las restricciones como pares de Vertex_handles).
A continuación, puede etiquetar los triángulos de la triangulación con cualquier algoritmo transversal: comience con un triángulo incidente al vértice infinito y márquelo como fuera, y cada vez que cruce una restricción, cambie a la etiqueta opuesta (dentro si estuvo etiquetando anteriormente los triángulos como externos, afuera si estuvieras etiquetando triángulos como información privilegiada antes).
Estoy buscando un algoritmo o una biblioteca (mejor) para descomponer un polígono en triángulos. Usaré estos triángulos en una aplicación Direct3D. ¿Cuáles son las mejores opciones disponibles?
Esto es lo que he encontrado hasta ahora:
- Notas de Ben Discoe
- FIST: Triangulación rápida de fuerza industrial de polígonos
- Sé que CGAL proporciona triangulación, pero no estoy seguro si admite agujeros.
Realmente agradecería algunas opiniones de personas con experiencia previa en esta área.
Editar: este es un polígono 2D.
Este es un problema común en el análisis de elementos finitos. Se llama "generación automática de malla". Google encontró este sitio con enlaces a software comercial y de código abierto. Suelen presuponer algún tipo de representación CAD de la geometría para comenzar.
Para darle más opciones de bibliotecas:
Polyboolean. Nunca intenté este, pero parece prometedor: http://www.complex-a5.ru/polyboolean/index.html
General Polygon Clipper. Este funciona muy bien en la práctica y hace triangulación, así como los agujeros de recorte y agujeros: http://www.cs.man.ac.uk/~toby/alan/software/
Mi recomendación personal: utilice la tesselación de GLU (OpenGL Utility Library). El código es sólido como una roca, más rápido que GPC y genera menos triángulos. No necesita un OpenGL-Handle inicializado ni nada de esto para usar la lib.
Si no le gusta la idea de incluir las librerías del sistema OpenGL en una aplicación DirectX, también existe una solución: simplemente descargue el código de implementación de referencia SGGL de OpenGL y levante el triangulador. Solo usa los nombres OpenGL-Typedef y una mano llena de enumeraciones. Eso es. Puede extraer el código y crear una lib propia en una o dos horas.
En general, mi consejo sería usar algo que ya funciona y no comenzar a escribir tu propia triangulación.
Si ha leído sobre el algoritmo de corte de orejas o barrido, es tentador hacer rodar el suyo, pero el hecho es que los algoritmos de geometría computacional son increíblemente difíciles de escribir de manera que funcionen de manera estable, nunca se cuelguen y siempre devuelvan un resultado significativo . Los errores numéricos de redondeo se acumularán y te matarán al final.
Escribí un algoritmo de triangulación en C para la empresa con la que trabajo. Lograr que el algoritmo central funcionara tomó dos días. Conseguir que funcionara con todo tipo de entradas degeneradas tomó otros dos años (no trabajaba a tiempo completo, pero créanme, pasé más tiempo de lo que debería).
Puede agregar los agujeros con relativa facilidad usted mismo. Básicamente triangular al casco convexo de los puntos de entrada, según CGAL, y luego eliminar cualquier triángulo cuyo incentivo se encuentre dentro de cualquiera de los polígonos de agujero (o fuera de cualquiera de los límites externos). Al tratar con muchos agujeros en un gran conjunto de datos, las técnicas de enmascaramiento se pueden utilizar para acelerar significativamente este proceso.
editar: una extensión común de esta técnica es eliminar los triángulos débiles en el casco, donde el borde más largo o el ángulo interno más pequeño excede un valor dado. Esto formará un mejor casco cóncavo.
La biblioteca Triangle de Jonathan Shewchuk es fenomenal; Lo he usado para automatizar la triangulación en el pasado. Puedes pedirle que intente evitar triángulos pequeños / estrechos, etc., así que obtienes triangulaciones "buenas" en lugar de cualquier triangulación.
Otra opción (con una licencia muy flexible) es portar el algoritmo de VTK:
Este algoritmo funciona bastante bien. Usarlo directamente es posible, pero requiere enlaces a VTK, que pueden tener más sobrecarga de lo que usted desea (aunque también tiene muchas otras características interesantes).
Admite restricciones (agujeros / límites / etc.), así como la triangulación de una superficie que no está necesariamente en el plano XY. También es compatible con algunas características que no he visto en otros lugares (ver las notas sobre los valores Alpha).
prueba libtess2
https://code.google.com/p/libtess2/downloads/list
basado en el teselador original SGI GLU (con licencia liberal). Resuelve algunos problemas de administración de memoria en muchos pequeños mallocs.
He encontrado que la biblioteca poly2tri es exactamente lo que necesitaba para la triangulación. Produce una malla mucho más limpia que otras bibliotecas que he probado (incluida libtess), y admite orificios también. Se ha convertido a varios idiomas. La licencia es New BSD , por lo que puede usarla en cualquier proyecto.
Implementé un triangulador de polígono 3D en C # usando el método de recorte de oreja. Es fácil de usar, admite orificios, es numéricamente robusto y admite polígonos convexos / no convexos aribtrary (no autointersecables).