Надежная, быстрая сложная многоугольная (с дырками) библиотека триангуляции c / c ++ с разрешающей лицензией
Я разработчик игры с открытым исходным кодом, Bitfighter. Согласно следующему сообщению SO, мы использовали превосходную библиотеку «Треугольник» для генерации меш-зоны для использования с нашим внутриигровым ИИ (роботами):
Триангуляция полигонов с отверстиями
Однако, когда мы решили упаковать нашу игру для Debian, мы столкнулись с небольшим затруднением — использование библиотеки «Треугольник» сделает нашу игру «несвободной».
Мы были чрезвычайно довольны производительностью библиотеки «Треугольник» и не хотим от нее отказываться; однако, нам также не нравится иметь дело с лицензионными проблемами. Поэтому мы приступили к поиску подходящей заменительной лицензии, которая может соответствовать «Треугольнику» по прочности и скорости.
Мы ищем библиотеку C или C ++ для разделения больших, сложных областей на треугольники, которые могут обрабатывать любые типы неправильных многоугольников, размещенных вместе любым способом, а также отверстия. Надежность — наша основная потребность, а скорость почти так же важна.
я нашел poly2tri, но он страдает от ошибки, из-за которой он не может обрабатывать полигоны с совпадающими ребрами.
Мы нашли несколько библиотек, но все, похоже, страдают от одного или другого: либо слишком медленно, либо не обрабатывают дыры, либо страдают от какой-то ошибки. В настоящее время мы тестируем polypartition и у нас большие надежды.
Каковы лучшие альтернативы великой библиотеке «Треугольник», но есть разрешительная лицензия?
Решение
Я нашел решение. это было poly2tri в конце концов, с использованием отличного клипер библиотека и некоторые незначительные алгоритмические дополнения к входам.
Наш процесс выглядит следующим образом:
- Пропустите все наши отверстия через Clipper, используя штуцер с обмоткой NonZero (это означает, что внутренние отверстия намотаны в противоположном направлении, как внешние). Clipper также гарантирует хорошие чистые точки ввода без повторов в эпсилоне.
- Отфильтруйте наши отверстия в отверстия, намотанные против часовой стрелки и по часовой стрелке. Отверстия по часовой стрелке означали, что отверстие было округлым и что внутри была еще одна концентрическая область, которую нужно было триангулировать
- Используя poly2tri, триангулируйте внешние границы и каждый найденный многоугольник по часовой стрелке, используя оставшиеся отверстия в качестве входных данных для poly2tri, если они были найдены в одной из границ.
Результат: Кажется, что poly2tri триангулирует почти так же быстро, как Triangle, и до сих пор был очень устойчив ко всему, что мы на него бросили.
Для тех, кто заинтересован, вот наши изменения кода.
Обновить
Я попытался вытащить наш код clipper-to-poly2tri с нашими добавлениями надежности в отдельную библиотеку, которую я начал здесь: clip2tri
Другие решения
Вы можете взглянуть на пакет 2D триангуляции CGAL. Приведен пример триангуляции многоугольника с отверстиями. Вот.
Лицензия пакета — GPLv3 +.
Обратите внимание, что не должно быть слишком сложно извлечь только этот пакет, если это необходимо.
В качестве небольшого примечания:
Мне недавно пришлось реализовать сложную полигональную машинку & триангулятор для резки оконных рам в стены дома.
В то время как я был доволен результатами клипсатора Vatti, триангуляция Делоне, используемая в poly2tri, была слишком тяжелой, чтобы позволить плавное перетаскивание оконной рамы вдоль барицентрических координат грани стены. Немного поцарапав голову, я в итоге обманул этот гораздо более простой треугольник для работы с отверстиями:
http://wiki.unity3d.com/index.php?title=Triangulator
То, что я сделал, это поделил горизонтальную поверхность стены на высоту кратчайшего отрезка. В моем случае они всегда прямоугольники, но они не должны быть. В любом случае, это заставляет машинку работать только с обычными или вогнутыми полисами, и, следовательно, позволяет вам обходиться дешевле с помощью метода триангуляции.
Вот несколько скриншотов, демонстрирующих его работу:
https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak
Надеюсь это поможет.