Algoritmo de triangulación de Delaunay más rápido disponible para GPU

Question

¿Cuál es en su opinión el algoritmo de triangulación de Delaunay más rápido disponible para GPU? O más general, en paralelo

Answer 1

Tenga cuidado con las GPU: las triangulaciones de Delaunay requieren pruebas de orientación. Estos no funcionan de manera confiable con la aritmética de punto flotante, y podría ser difícil hacer frente a ese problema usando una GPU. Además, la gestión de la memoria es crucial.

Es posible que desee probar http://www.geom.at/fade2d/html/ que se encuentra entre las implementaciones de subproceso único más robustas .

Answer 2

2D triangulación de Delaunay

GPU-DT es la implementación más rápida 2D Delaunay para la GPU.

Construye un diagrama digital de Voronoi en 2D utilizando el algoritmo de bandas paralelas . A continuación, corrige y dualiza esto para obtener una triangulación 2D. Finalmente, realiza un volteo de borde en paralelo en la GPU para obtener la triangulación Delaunay 2D.

3D triangulación Delaunay

gStar4D es una aplicación rápida y robusta de Delaunay 3D para la GPU.

Similar a la GPU-DT, este algoritmo construye primero el diagrama 3D digital de Voronoi. Sin embargo, en 3D esto no se puede dualizar a una triangulación debido a problemas topológicos y geométricos. En cambio, gStar4D usa la información del vecindario de este diagrama para crear estrellas levantadas a 4D y realiza una proyección de estrellas de manera eficiente en la GPU. Al extraer el casco inferior de este, se obtiene la triangulación 3D de Delaunay.

Una alternativa más rápida es gDel3D, que es un algoritmo híbrido de GPU-CPU.

Realiza inserción paralela y voltea en la GPU. El resultado está cerca de Delaunay. Luego corrige este resultado utilizando un método conservador de proyección de estrellas en la CPU.

Todos estos métodos son robustos, por lo que pueden manejar cualquier tipo de entrada degenerada.