Надежная, сложная полигональная (с дырками) триангуляция c/С++ библиотека с разрешительной лицензией

Я разработчик игры с открытым исходным кодом, Bitfighter. В соответствии со следующим сообщением SO мы использовали отличную библиотеку "Triangle" для генерации сетчатой зоны для использования с нашими игровыми AI (роботами):

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

Однако мы столкнулись с небольшой проблемой, когда хотим упаковать нашу игру для Debian - использование библиотеки "Треугольник" сделает нашу игру считающейся "несвободной".

Мы были очень довольны работой библиотеки "Треугольник" и не хотим отказываться от нее; однако нам также не нравится заниматься вопросами лицензии. Поэтому мы приступили к поиску подходящей, разрешительно-лицензированной замены, которая может соответствовать "Треугольнику" в его надежности и скорости.

Мы ищем библиотеку C или С++ для разделения больших, сложных областей на треугольники, которые могут обрабатывать любые нерегулярные многоугольники, размещенные вместе каким-либо образом, а также дыры. Надежность - наша основная потребность, скорость почти такая же важная.

Я нашел poly2tri, но он страдает от ошибки, в которой он не может обрабатывать многоугольники с совпадающими ребрами.

Мы нашли несколько библиотек, но все, похоже, страдают от того или иного: либо слишком медленного, либо не обрабатывают дыры, либо страдают от некоторой ошибки. В настоящее время мы тестируем polypartition, и у нас есть большие надежды.

Каковы наилучшие альтернативы большой библиотеке "Треугольник" , но имеют разрешительную лицензию?

Ответ 1

Я нашел решение. Это было poly2tri в конце концов, с использованием отличного Clipper, а также некоторые незначительные алгоритмические дополнения к входам.

Наш процесс выглядит следующим образом:

Запустите все наши отверстия через Clipper, используя соединение с обмоткой NonZero (это означает, что внутренние отверстия намотаны в противоположном направлении, как внешние). Clipper также гарантирует хорошие чистые входные точки без повторов внутри epsilon.
Отфильтруйте наши отверстия в ранах против часовой стрелки и по часовой стрелке. Отверстия по часовой стрелке означали, что отверстие было обходным и что внутри была еще одна концентрическая область, которая должна быть триангулирована.
Используя poly2tri, триангулируем внешние границы и каждый найденный полигон по часовой стрелке, используя остальную часть дырок в качестве входов в poly2tri, если они были найдены в пределах одной из границ.

Результат: poly2tri, кажется, триангулирует примерно так же быстро, как Triangle, и до сих пор был очень прочным со всем, что мы бросили на него.

Для тех, кого интересует, вот наши изменения кода.

Обновление

Я попытался вытащить наш код clipper-to-poly2tri с нашими дополнениями к надежности в отдельную библиотеку, которую я начал здесь: clip2tri

Ответ 2

Вы можете взглянуть на пакет 2D триангуляции CGAL. Пример триангуляции многоугольника с отверстиями дается здесь. Лицензия пакета - GPLv3 +.

Обратите внимание, что не нужно слишком сложно извлекать только этот пакет, если это необходимо.

Ответ 3

В качестве небольшого примечания:

Недавно мне пришлось внедрить сложный полигон-клипер и триангулятор для резки оконных рам в стены дома.

В то время как я был доволен результатами клипса Vatti, триангуляция Деланея, используемая в poly2tri, была слишком тяжелой, чтобы обеспечить плавное перетаскивание оконной рамы вдоль барицентрических координат поверхности стены. Немного поцарапав голову, я в конечном итоге обманул это гораздо проще треугольника, чтобы работать с отверстиями:

http://wiki.unity3d.com/index.php?title=Triangulator

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

Вот несколько скриншотов, показывающих, что он работает:

https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak

Надеюсь, что это поможет.