Triangulacja wielokątna z otworami

Question

Szukam algorytmu lub biblioteki (lepiej), aby rozbić wielokąt na trójkąty. Będę używał tych trójkątów w aplikacji Direct3D. Jakie są najlepsze dostępne opcje?

Oto co znalazłem do tej pory:

1. Ben Discoe's notes
2. FIST: Fast Industrial-Strength Triangulation of Polygons
3. wiem, że CGAL zapewnia triangulacji ale nie jestem pewien, czy obsługuje otwory.

Byłbym bardzo wdzięczny za opinie osób, które wcześniej miały doświadczenie w tej dziedzinie.

Edytuj: To jest wielobok 2D.

Answer 1

Jonathan Shewchuk's jest fenomenalny; Używałem go do automatyzacji triangulacji w przeszłości. Możesz poprosić o próbę uniknięcia małych/wąskich trójkątów itp., Więc wymyślisz "dobre" triangulacje, zamiast tylko triangulacji.

Answer 2

Możesz stosunkowo łatwo dodać otwory. Zasadniczo trianguluj do wypukłego kadłuba punktów wejściowych, zgodnie z CGAL, a następnie usuń dowolny trójkąt, którego motyw znajduje się wewnątrz dowolnego z wielokątów otworów (lub poza dowolnymi zewnętrznymi granicami). Gdy mamy do czynienia z dużą ilością dziur w dużym zbiorze danych, można zastosować techniki maskowania, aby znacznie przyspieszyć ten proces.

edycja: Powszechnym rozszerzeniem tej techniki jest słabe trójkąty chwastów na kadłubie, gdzie najdłuższa krawędź lub najmniejszy kąt wewnętrzny przekracza daną wartość. To utworzy lepszy wklęsły kadłub.

Answer 3

CGAL posiada narzędzia potrzebne: Constrained Triangulations

Możesz po prostu dostarczyć granice swojej wielokąta (incuding granice otworów) jako ograniczeń (najlepiej byłoby, aby wstawić wszystkie wierzchołki, a następnie określić ograniczenia jako pary Vertex_handles).

Następnie można oznaczyć trójkąty trójkąta za pomocą dowolnego algorytmu traversal: zacznij od trójkąta padającego na nieskończony wierzchołek i oznacz go jako znajdującego się na zewnątrz, a za każdym razem, gdy przekraczasz ograniczenie, przełącz na przeciwną etykietę (w środku, jeśli poprzednio oznaczałeś trójkąty jako outsider, na zewnątrz, jeśli wcześniej oznaczałeś trójkąty jako poufne).

Answer 4

podać kilka więcej możliwości bibliotek tam:

Polyboolean. Nigdy tego nie próbowałem, ale wygląda obiecująco: http://www.complex-a5.ru/polyboolean/index.html

Ogólny klips do wielokąta. Ta działa bardzo dobrze w praktyce i ma triangulację, a także wycinanie i dziurawienie otworów: http://www.cs.man.ac.uk/~toby/alan/software/

Moja osobista rekomendacja: Użyj tesselation z GLU (OpenGL Utility Library). Kod jest solidny, szybszy niż GPC i generuje mniej trójkątów. Nie potrzebujesz zainicjowanego uchwytu OpenGL lub czegoś podobnego, aby użyć biblioteki.

Jeśli nie podoba ci się pomysł włączenia biblioteki systemowej OpenGL do aplikacji DirectX, istnieje również rozwiązanie: wystarczy pobrać kod implementacyjny SGI OpenGL i podnieść z niego triangulator. Po prostu używa nazw OpenGL-Typedef i rozdania pełnego wyrażeń. to jest to! Możesz wyodrębnić kod i utworzyć samodzielną bibliotekę w ciągu godziny lub dwóch.

---

Generalnie moja rada byłaby taka, żeby używać czegoś, co działa, i nie zaczynam pisać własnej triangulacji.

Kusi, aby rzucić się na własną rękę, jeśli przeczytałeś o algorytmie przycinania uszu lub algorytmu liniowego, ale faktem jest, że algorytmy geometrii obliczeniowej są niewiarygodnie trudne do napisania w sposób, który działa stabilnie, nigdy się nie psuje i zawsze zwraca znaczący wynik. Numeryczne błędy zaokrąglania będą kumulować się i zabić cię w końcu.

Napisałem algorytm triangulacji w C dla firmy, w której pracuję. Sprawdzenie działania algorytmu trwało dwa dni. Praca z różnymi zdegenerowanymi danymi wejściowymi zajęła kolejne dwa lata (nie pracowałem na pełnym etacie, ale zaufaj mi - spędziłem na nim więcej czasu niż powinienem).

Answer 5

Jest to powszechny problem w analizie elementów skończonych. Nazywa się to "automatycznym generowaniem siatki". Wyszukiwarka Google znalazła this site z linkami do komercyjnego i oprogramowania open source. Zwykle zakładają jakiś rodzaj reprezentacji CAD geometrii, aby rozpocząć.

Answer 6

Innym rozwiązaniem (z bardzo elastycznej licencji) jest do portu algorytm z VTK:

vtkDelaunay2D

Algorytm ten działa dość dobrze. Korzystanie z niego bezpośrednio jest możliwe, ale wymaga linków do VTK, który może mieć więcej narzutów, niż chcesz (chociaż ma również wiele innych fajnych funkcji).

Obsługuje ograniczenia (otwory/granice/etc), jak również triangulację powierzchni niekoniecznie na płaszczyźnie XY. Obsługuje również niektóre funkcje, których nie widziałem gdzie indziej (patrz uwagi na temat wartości Alpha).

Answer 7

try libtess2

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

na podstawie oryginalnego SGI GLU tesselator (z liberalnej licencji). Rozwiązuje niektóre problemy z zarządzaniem pamięcią wokół wielu małych mallocs.

Answer 8

Znalazłem bibliotekę poly2tri jako dokładnie to, czego potrzebowałem do triangulacji. Tworzy znacznie czystszą siatkę niż inne biblioteki, które wypróbowałem (w tym libtess) i obsługuje również dziury. Został przekształcony w kilka języków. Licencja to New BSD, dzięki czemu można jej używać w dowolnym projekcie.

Poly2tri library on Google Code

Answer 9

I wprowadziły wielokąt 3D triangulator w C# za pomocą metody obcinania uszu. Jest łatwy w użyciu, obsługuje otwory, jest wytrzymały i obsługuje aramidowe (nie przecinające się) wypukłe/nie wypukłe wielokąty.