Самый быстрый доступный алгоритм триангуляции Delaunay для GPU

Ответ 1

Будьте осторожны с GPU: для триангуляции Delaunay требуются ориентировочные тесты. Они не работают надежно с арифметикой с плавающей запятой, и с этой проблемой может быть сложно справиться с использованием графического процессора. Также важно управление памятью.

Возможно, вы захотите попробовать http://www.geom.at/fade2d/html/, который является одним из самых быстрых однопоточных реализаций.

Ответ 2

2D триангуляция Делоне

GPU-DT - это самая быстрая реализация 2D Delaunay для GPU.

Он строит цифровую диаграмму Вороного в 2D с использованием алгоритма параллельного обхода GPU. Затем он исправляет и дуализирует это, чтобы получить двумерную триангуляцию. Наконец, он выполняет параллельное кроссирование на графическом процессоре для получения триангуляции 2D Delaunay.

Трехмерная треугольная треугольник

gStar4D - это быстрая и надежная реализация 3D Delaunay для графического процессора.

Подобно GPU-DT, этот алгоритм сначала создает трехмерную цифровую диаграмму Вороного. Однако в 3D это не может быть дуализировано на триангуляцию из-за топологических и геометрических задач. Вместо этого gStar4D использует информацию о соседстве с этой диаграммы, чтобы создать звезды, поднятые до 4D, и эффективно воспроизводит на них графики на GPU. Извлекая из этого нижнюю оболочку, получается триангуляция 3D Delaunay.

Более быстрой альтернативой является gDel3D, который является гибридным алгоритмом GPU-CPU.

Он выполняет параллельную установку и переключение на графический процессор. Результат близок к Делоне. Затем он фиксирует этот результат, используя консервативный метод отображения звезд на процессоре.

Все эти методы являются надежными, поэтому они могут обрабатывать любой вид вырожденного ввода.