Триангуляция полигонов с отверстиями

Question

Я ищу алгоритм или библиотеку (лучше), чтобы разбить многоугольник на треугольники. Я буду использовать эти треугольники в приложении Direct3D. Каковы лучшие доступные варианты?

Вот что я нашел до сих пор:

1. Заметки Бена Диско
2. FIST: быстрая промышленно-прочная триангуляция полигонов
3. Я знаю, что CGAL обеспечивает триангуляцию, но не уверен, поддерживает ли она отверстия.

Я был бы очень признателен за мнения людей, имеющих опыт работы в этой области.

Редактировать: это 2D многоугольник.

Answer 1

Библиотека Джонатана Шевчука Треугольник феноменальна; Я использовал его для автоматизации триангуляции в прошлом. Вы можете попросить его попытаться избежать маленьких / узких треугольников и т. Д., Так что вы придумаете «хорошие» триангуляции вместо какой-либо триангуляции.

Answer 2

Чтобы дать вам еще несколько вариантов библиотек:

Polyboolean. Я никогда не пробовал этот, но выглядит многообещающе: http://www.complex -a5.ru / polyboolean / index.html

General Polygon Clipper. Это очень хорошо работает на практике и выполняет триангуляцию, а также отсечение и отверстия: http://www.cs.man.ac.uk/~toby/alan/software/

Моя личная рекомендация: используйте тесселяцию из GLU (OpenGL Utility Library). Код надежен, быстрее чем GPC и генерирует меньше треугольников. Вам не нужен инициализированный OpenGL-дескриптор или что-то подобное, чтобы использовать библиотеку.

Если вам не нравится идея включения системных библиотек OpenGL в приложение DirectX, есть и решение: просто скачайте эталонный код реализации SGI OpenGL и снимите с него триангулятор. Он просто использует имена OpenGL-Typedef и полный набор перечислений. Вот и все. Вы можете извлечь код и создать автономную библиотеку за час или два.

---

В общем, мой совет - использовать то, что уже работает, и не начинать писать свою собственную триангуляцию.

Соблазнительно катиться самостоятельно, если вы читали об алгоритме срезания ушей или стреловидности, но факт в том, что алгоритмы вычислительной геометрии невероятно сложно написать так, чтобы они работали стабильно, никогда не падали и всегда возвращались значимый результат. Числовые ошибки округления накапливаются и убивают вас в конце.

Я написал алгоритм триангуляции на C для компании, с которой я работаю. Работа над основным алгоритмом заняла два дня. На то, чтобы заставить его работать со всеми типами вырожденных входов, потребовалось еще два года (я не работал над ним полный рабочий день, но поверьте мне - я потратил на это больше времени, чем следовало бы).

Answer 3

CGAL имеет инструмент, который вам нужен: Ограниченные триангуляции

Вы можете просто предоставить границы вашего многоугольника (включая границы отверстий) как ограничения (лучше всего, чтобы вы вставили все вершины, а затем задали ограничения как пары Vertex_handles).

Затем вы можете пометить треугольники триангуляции любым алгоритмом обхода: начните с треугольника, падающего на бесконечную вершину, и пометьте его как находящегося снаружи, и каждый раз, когда вы пересекаете ограничение, переключайтесь на противоположный тег (внутри, если вы ранее отмечали треугольники как аутсайдеров, если вы ранее отмечали треугольники как инсайдеров).

Answer 4

Я обнаружил, что библиотека poly2tri - это именно то, что мне нужно для триангуляции. Он производит намного более чистую сетку, чем другие библиотеки, которые я пробовал (включая libtess), и он также поддерживает дыры. Это было преобразовано в кучу языков. Лицензия Новая BSD , поэтому вы можете использовать ее в любом проекте.

Библиотека Poly2tri в Google Code

Answer 5

попробуйте libtess2

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

на основе оригинального тесселятора SGI GLU (с либеральным лицензированием). Решает некоторые проблемы с управлением памятью вокруг множества маленьких mallocs.

Answer 6

Вы можете добавить отверстия относительно легко самостоятельно. По существу, триангулируйте выпуклую оболочку входных точек согласно CGAL, а затем удаляйте любой треугольник, центр которого лежит внутри любого из многоугольников отверстия (или вне любой из внешних границ). При работе с большим количеством дырок в большом наборе данных можно использовать методы маскировки, чтобы значительно ускорить этот процесс.

edit: Распространенным расширением этой техники является прополка слабых треугольников на корпусе, где самый длинный край или наименьший внутренний угол превышает заданное значение. Это сформирует лучший вогнутый корпус.

Answer 7

Это распространенная проблема в анализе методом конечных элементов. Это называется "автоматическая генерация сетки". Google нашел этот сайт со ссылками на коммерческое и открытое программное обеспечение. Они обычно предполагают какое-то представление геометрии в САПР для начала.

Answer 8

Я реализовал 3D-многоугольник триангулятор в C #, используя метод обрезания ушей. Он прост в использовании, поддерживает отверстия, численно устойчив и поддерживает произвольные (не самопересекающиеся) выпуклые / невыпуклые многоугольники.

Answer 9

Другой вариант (с очень гибкой лицензией) - портировать алгоритм от VTK:

vtkDelaunay2D

Этот алгоритм работает довольно хорошо. Прямое его использование возможно, но для этого требуются ссылки на VTK, которые могут иметь больше служебных данных, чем вы хотите (хотя он также имеет много других полезных функций).

Он поддерживает ограничения (отверстия / границы / и т. Д.), А также триангуляцию поверхности, которая не обязательно находится в плоскости XY. Он также поддерживает некоторые функции, которые я не видел в других местах (см. Примечания по значениям Alpha).