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

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

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

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

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

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

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

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

Каковы лучшие альтернативы великой библиотеке «Треугольник», но у них есть разрешающая лицензия?


c c++ open-source triangulation
person raptor    schedule 16.04.2013    source источник
comment
Не могли бы вы уточнить, что именно вам нужно от такой библиотеки, как Triangle, пожалуйста? Возможно, вы сможете сами написать некоторые алгоритмы и опубликовать свой код так, как вам это нужно.   -  person Mare Infinitus    schedule 16.04.2013
comment
Что такое лицензия Triangle? Вы пытались написать Джонатану Шевчуку по электронной почте, чтобы спросить, перелицензировал бы он его для вас?   -  person rob mayoff    schedule 16.04.2013
comment
@MareInfinitus У нас есть уровни со стенами. Вся игровая область уровня должна быть триангулирована для навигации по сетке, чтобы наши роботы могли двигаться.   -  person raptor    schedule 16.04.2013
comment
@raptor действительно сложно сказать, возможно, лучше всего, как уже рекомендовал Роб Майофф, написать автору Triangle   -  person Mare Infinitus    schedule 16.04.2013
comment
Забавно, что это было закрыто как не по теме с инструкциями по описанию проблемы и того, что было сделано на данный момент для ее решения.   -  person raptor    schedule 05.04.2015

Ответы (3)


arrow_upward
18
arrow_downward

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

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

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

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

Для тех, кто интересуется, .

Обновить

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

person raptor    schedule 20.04.2013
comment
Я просто хотел бы продолжить и сказать, что poly2tri, хотя и быстрый, действительно иногда страдает от проблем с устойчивостью, обычно связанных с точками, которые действительно близки друг к другу в эпсилоне. - person raptor; 23.10.2013
comment
Я использовал описанные вами методы, а также обнаружил несколько случаев, когда poly2tri дает сбой. Я смог решить все случаи с помощью этой комбинации: установить Clipper :: StrictlySimple (true) перед Execute (); после этого я использую CleanPolygon (), а затем ваш edgeShrink () как для полигонов, так и для дыр; и, наконец, проверьте наличие смежных вершин с равными координатами и удалите одну из них (отбрасывая весь полигон / отверстие, когда он достигает менее 3 вершин). - person Fabio Ceconello; 25.02.2015

arrow_upward
1
arrow_downward

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

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

person sloriot    schedule 17.04.2013

arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

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

person Rob Bantin    schedule 01.05.2014
comment
Как вы заставили его принять дыры? - person Aaron Azhari; 24.09.2014