Triangulación de polígono con orificios

Question

Estoy buscando un algoritmo o 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?

Aquí es lo que he encontrado hasta ahora:

1. Ben Discoe's notes
2. FIST: Fast Industrial-Strength Triangulation of Polygons
3. sé que CGAL proporciona triangulación, pero no estoy seguro de si es compatible con agujeros.

Realmente agradecería algunas opiniones de personas con experiencia previa en esta área.

Editar: Este es un polígono 2D.

Answer 1

Jonathan Shewchuk's Triangle library 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.

Answer 2

Puede agregar los orificios 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.

Answer 3

CGAL tiene la herramienta que necesita: Constrained Triangulations

Simplemente puede proporcionar límites de su polígono (incuding los límites de los agujeros) como restricciones (lo mejor sería que se inserta todos los vértices, y luego especificar el restricciones como pares de Vertex_handles).

Puede etiquetar los triángulos de la triangulación mediante 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 anteriormente etiquetó los triángulos como externos, afuera si estaba etiquetando triángulos como información privilegiada anteriormente).

Answer 4

para darle un poco más opciones de bibliotecas por ahí:

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 la 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 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 utilizar algo que ya funciona y no comenzar a escribir su propia triangulación.

Es tentador rodar el suyo si ha leído sobre el algoritmo de corte de oreja o línea de barrido, pero el hecho es que los algoritmos de geometría computacional son increíblemente difíciles de escribir de manera que funcionen estable, nunca se cuelguen y siempre devolver 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).

Answer 5

Este es un problema común en el análisis de elementos finitos. Se llama "generación automática de malla". Google encontró this site 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.

Answer 6

Otra opción (con una licencia muy flexible) es el algoritmo puerto de VTK:

vtkDelaunay2D

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).

Answer 7

intento libtess2

https://code.google.com/p/libtess2/downloads/list

basado en el original de la SGI tesselator GLU (con licencias liberal). Resuelve algunos problemas de administración de memoria en muchos pequeños mallocs.

Answer 8

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.

Poly2tri library on Google Code

Answer 9

he implementado un polígono 3D triangulator 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).