Rozkład wklęsłej siatki na zestaw wypukłych siatek

Chciałbym móc rozłożyć siatkę wklęsłą na zestaw siatek wypukłych z dwóch powodów:

1. Przejrzysty rendering
2. Kształty fizyki

Czy istnieje algorytm, który przyjmuje zestaw trójkątów (wklęsły) jako dane wejściowe i wyprowadza pewną liczbę zestawów trójkątów (wypukłych)? Chciałbym, aby nie wypełniał otworów między częściami oryginalnej siatki.

Natknąłem się już na mały pomysł: znajdź wszystkie wklęsłe krawędzie i podziel siatki wzdłuż pętli krawędzi. Czy jestem na dobrej drodze? Jak mogę to zaimplementować?

Powiedziałbym, że jesteś na dobrej drodze, ale wymyślenie optymalnego i / lub wydajnego algorytmu to inna sprawa: to trudny problem. Jednak, jeśli twoje zainteresowania nie są akademickie, wystarczające może być wystarczające rozwiązanie.

Po pierwsze, jeśli nie jesteś zainteresowany wymyśleniem własnego rozwiązania, CGAL zawiera już algorytm rozkładu wypukłych wielościanów: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Teraz metoda; podobnie jak wiele problemów w 3D, często pomocne jest rozważenie problemu 2D, który jest łatwiejszy do zrozumienia. W przypadku 2D zadaniem jest zidentyfikowanie wierzchołków odruchu i podzielenie wielokąta na dwa, tworząc nową krawędź (i ewentualnie nowe wierzchołki) z tego wierzchołka odruchu, i kontynuuj, dopóki nie pozostaniesz bez wierzchołków odruchu (a zatem wielokątów wypukłych) ).

Dekompozycja wielokąta J. Mark Keil zawiera następujący algorytm (w niezoptymalizowanej formie):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Zasadniczo porównuje wyczerpująco wszystkie możliwe partycje i zwraca tę z najmniejszą liczbą przekątnych. W tym sensie jest też nieco brutalna i optymalna.

Jeśli chcesz „ładniej wyglądających” rozkładów, czyli takich, które wytwarzają bardziej zwarte kształty niż wydłużone, możesz również rozważyć ten wyprodukowany przez Marka Bayazita , który jest zachłanny (stąd znacznie szybszy) i wygląda ładniej, ale ma kilka wad. Zasadniczo działa, próbując połączyć wierzchołki odruchowe z najlepszym przeciwległym do niego, zwykle z innym wierzchołkiem odruchowym:

Jednym z niedociągnięć jest to, że ignoruje „lepszy” rozkład poprzez tworzenie punktów Steiner'a (punktów, które nie istnieją na istniejącej krawędzi):

Problem w 3D może być podobny; zamiast wierzchołków odruchowych identyfikujesz „krawędzie wycięcia”. Naiwnym wdrożeniem byłoby identyfikowanie krawędzi wycięcia i wielokrotne wykonywanie płaskich cięć na wielościanie, aż wszystkie wielościany będą wypukłe. Sprawdź „Wypukłe partycje wielościanów: algorytm optymalny dolnej granicy i najgorszego przypadku” Bernarda Chazelle, aby uzyskać więcej informacji.

Zauważ, że takie podejście może spowodować w najgorszym przypadku wykładniczą liczbę sub-wielościanów. Wynika to z możliwości zdegenerowania takich przypadków:

Ale jeśli masz nietrywialną siatkę (pomyśl nierówną powierzchnię), i tak otrzymasz słabe wyniki. Jest bardzo prawdopodobne, że zechcesz wcześniej uprościć wiele czynności, jeśli będziesz musiał użyć tego w przypadku skomplikowanych siatek.

Obliczenie dokładnego wypukłego rozkładu powierzchni S jest trudnym zadaniem NP i zwykle powoduje powstanie dużej liczby skupień. Aby przezwyciężyć te ograniczenia, dokładne ograniczenie wypukłości może zostać złagodzone i zamiast tego obliczane jest przybliżone wypukłe rozkład S. Tutaj celem jest określenie podziału trójkątów siatki z minimalną liczbą klastrów, przy jednoczesnym zapewnieniu, że każdy klaster ma wklęsłość niższą niż próg zdefiniowany przez użytkownika.

Sprawdź następujące przybliżone wypukłe biblioteki dekompozycji: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

Oto kod, który może ci pomóc. Jest w Javie, więc będziesz musiał przekonwertować go do c ++.

Oto także kolejny artykuł, który może ci pomóc