Solidna, szybka, złożona wielobok (z dziurami) triangulacja c/C++ biblioteka z permisywną licencją

Question

Jestem twórcą gry open-source, Bitfighter. Zgodnie z poniższym SO post, użyliśmy doskonałą bibliotekę „trójkąt” do generowania siatki strefy do użytku z naszej w grze AI (roboty):

Polygon Triangulation with Holes

jednak wpadliśmy do małego Suszka kiedy chcemy spakować naszą grę dla Debiana - użycie biblioteki "Trójkąt" sprawi, że nasza gra będzie uważana za "niewolną".

Jesteśmy niezmiernie zadowoleni z działania biblioteki "Trójkąt" i naprawdę nie chcemy tego rezygnować; jednak nie lubimy też zajmować się kwestiami licencji. Dlatego podjęliśmy próbę znalezienia odpowiedniego, dopuszczalnie licencjonowanego zamiennika, który pasowałby do "Trójkąta" w jego solidności i szybkości.

Poszukujemy biblioteki C lub C++ do dzielenia dużych, złożonych obszarów na trójkąty, które mogą obsługiwać dowolny rodzaj nieregularnych wielokątów złożonych razem w dowolny sposób, a także dziury. Solidność jest naszą podstawową potrzebą, z prędkością niemal równie ważną.

Znalazłem poly2tri, ale cierpi na błąd, w którym nie może obsłużyć wielokątów o zbieżnych krawędziach.

Znaleźliśmy kilka bibliotek, ale wszystkie zdają się cierpieć z jednego lub drugiego powodu: albo zbyt wolno, albo nie radzą sobie z dziurami lub cierpią z powodu jakiegoś błędu. Obecnie testujemy obecnie polypartition i mamy duże nadzieje.

Jakie są najlepsze alternatywy dla wspaniałej biblioteki "Trójkąt", ale mają zezwolenie?

Answer 1

Znalazłem rozwiązanie. W końcu była to poly2tri, z wykorzystaniem znakomitej biblioteki Clipper i pewnych drobnych algorytmicznych dodatków do danych wejściowych.

Sposób według wynalazku jest następujący:

1. Run Wszystkie otwory poprzez Clipperze stosując związek z niezerowych uzwojenie (oznacza to, że otwory wewnętrzne są nawinięte w przeciwnym kierunku, jak te zewnętrzne). Clipper gwarantuje również czyste, czyste punkty wejściowe bez powtórzeń w epsilon.
2. Przefiltruj dziury w te, które są nawijane przeciwnie do ruchu wskazówek zegara i zgodnie z ruchem wskazówek zegara. Otwory zgodne z ruchem wskazówek zegara oznaczały, że otwór był obwodowy i że w środku znajdował się inny koncentryczny obszar, który wymagałby triangulacji
3. Stosując poly2tri, trianguluj zewnętrzne granice i każdy wielokąt zgodny z ruchem wskazówek zegara, wykorzystując resztę otworów jako wejścia do poli2tri, jeśli zostały znalezione w jednym z granic.

Wynik: poly2tri wydaje triangulacji prawie tak samo szybko jak trójkąt i jak dotąd bardzo wytrzymałe ze wszystkim mamy rzucony na niego.

Dla zainteresowanych, here are our code changes.

Aktualizacja

starałem się wyciągnąć nasze maszynki-do-poly2tri kodu z naszymi dodatkami solidności, do osobnej biblioteki, które zacząłem tutaj: clip2tri

Answer 2

Możesz rzucić okiem na pakiet 2D Triangulations CGAL. Przykład triangulacji wielokąta z otworami jest podany jako here. Licencja pakietu to GPLv3 +.

Należy pamiętać, że w razie potrzeby nie powinno być zbyt trudno wyodrębnić tylko ten pakiet.

Answer 3

jako mały marginesie :

Niedawno musiałem zaimplementować wielokanałowy klips do obciskania & triangulator do cięcia ram okiennych w ścianach domu.

Podczas gdy byłem zadowolony z rezultatów maszynki Vatti, triangulacja Delaunay stosowana w poli2tri była zbyt ciężka, aby umożliwić płynne przeciąganie ramy okna wzdłuż barycentrycznych współrzędnych powierzchni ściany. Po zarysowania moja głowa trochę, skończyło się to znacznie prostsze oszukiwanie trójkątny pracować z otworami:

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

Co zrobiłem było podzielić poziomo twarz ściany od wysokości najkrótszym obcinania poli. W moim przypadku są to zawsze prostokąty, ale nie muszą. W każdym razie zmusza maszynkę do pracy tylko do zwykłych lub wklęsłych polys, dzięki czemu można uciec z tańszą metodą triangulacji.

Oto screeny pokazujące to działa:

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

Nadzieja to pomaga.