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

Question

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

Вот что я нашел на данный момент:

1. Заметки Бена Дискоу
2. КУЛАК:Быстрая промышленная триангуляция полигонов
3. я знаю это КГАЛ обеспечивает триангуляцию, но я не уверен, поддерживает ли она отверстия.

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

Редактировать:Это 2D-полигон.

Answer 1

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

Answer 2

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

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

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

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

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

---

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

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

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

Answer 3

У CGAL есть необходимый вам инструмент:Ограниченные триангуляции

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

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

Answer 4

Я обнаружил, что библиотека Poly2tri — это именно то, что мне нужно для триангуляции.Она создает гораздо более чистую сетку, чем другие библиотеки, которые я пробовал (включая libtess), а также поддерживает дыры.Он был преобразован в кучу языков.Лицензия Новый БСД, поэтому вы можете использовать его в любом проекте.

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

Answer 5

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

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

Answer 6

попробуй libtess2

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

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

Answer 7

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

Answer 8

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

вткДелоне2D

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

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

Answer 9

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