Самый быстрый доступный алгоритм триангуляции Делоне для графического процессора

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

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

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

GPU-DT — самый быстрый 2D Реализация Делоне для GPU.

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

Трехмерная триангуляция Делоне

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

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

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

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

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