Algorytm pakowania tekstur

Co to jest dobry algorytm pakowania tekstur? Technicznie rzecz biorąc, pakowanie pojemników jest trudne NP , więc heurystyka jest tym, czego naprawdę chcę.

Spędziłem kilka miesięcy przy jednym zadaniu, opracowując lepszy algorytm pakowania tekstur.

Algorytm, od którego zaczęliśmy, był prosty. Zbierz wszystkie elementy wejściowe. Sortuj je według całkowitej liczby zużytych pikseli, od dużych do małych. Ułóż je w teksturze w kolejności skanowania, po prostu testując rzeczy od piksela od lewej do prawej, przesuwając w dół linii i powtarzając, resetując do piksela po każdym udanym umieszczeniu.

Musisz albo zakodować szerokość, albo wymyślić inną heurystykę. Próbując zachować kwadratowość, nasz algorytm zaczynałby się od 128, a następnie zwiększał się o 128s, aż do uzyskania wyniku, który nie był głębszy niż szeroki.

Więc mieliśmy ten algorytm i postanowiłem go ulepszyć. Wypróbowałem kilka zwariowanych heurystyk - próbując znaleźć obiekty, które pasują do siebie, dokonując pewnej oceny szeregu pożądanych właściwości upakowania przestrzeni, obracając i odwracając. Po całej mojej pracy, dosłownie trzech miesiącach pracy, udało mi się zaoszczędzić 3% miejsca.

Tak. 3%

Po przejściu przez to naszej procedury kompresji okazało się, że jest ona większa (czego wciąż nie umiem wyjaśnić), więc wyrzuciliśmy całość i wróciliśmy do starego algorytmu.

Sortuj elementy, blokuj teksturę w kolejności skanowania. Oto twój algorytm. Łatwo go kodować, szybko uruchamiać, a nie będziesz dużo lepszy bez niesamowitej pracy. Ta praca jest po prostu nieopłacalna, chyba że Twoja firma ma co najmniej 50 osób i prawdopodobnie więcej.

I na marginesie, właśnie zaimplementowałem ten algorytm (stała szerokość 512 pikseli) dla dosłownie tej samej aplikacji, którą robisz (bez ftgles, ale glify freetype renderowane w OpenGL). Oto wynik. Wygląda rozmazane, ponieważ mój wykorzystuje algorytm renderowania tekstu oparty na polu odległości Valve , który również uwzględnia dodatkową przestrzeń między glifami. Oczywiście nie pozostało wiele pustej przestrzeni i dobrze wpycha rzeczy w otwarte miejsca.

Cały kod tego jest na licencji BSD i jest dostępny na github .

Praca doktorska Andrei Lodi jest zatytułowana Algorytmy dla dwuwymiarowych problemów z pakowaniem pojemników i zadaniami .
Teza dotyczy niektórych trudniejszych form tych problemów. Na szczęście pakowanie tekstur jest najłatwiejszą wersją. Najlepszy algorytm, jaki znalazł, nazywał się Dotykanie obwodu .

Cytat ze strony 52:

Algorytm, zwany obwodem dotykowym (TPRF), rozpoczyna się od sortowania elementów według nie zwiększającego się obszaru (zrywanie więzi przez nie zwiększanie wartości min {wj, hj}) i orientowania ich w poziomie. Następnie obliczana jest dolna granica L optymalnej wartości rozwiązania i inicjowane są L puste pojemniki. (Ciągła dolna granica L0 zdefiniowana w poprzedniej sekcji jest oczywiście ważna również dla 2BP | R | F; lepsze granice są proponowane przez Dell'Amico, Martello i Vigo [56].) Algorytm pakuje jeden element na raz, albo w istniejącym koszu lub przez zainicjowanie nowego. Pierwszy przedmiot zapakowany do kosza jest zawsze umieszczany w lewym dolnym rogu. Każdy kolejny przedmiot jest zapakowany w tak zwaną normalną pozycję (patrz Christo fi des i Whitlock [41]), tj.
Wyboru pojemnika i pozycji pakowania dokonuje się poprzez ocenę wyniku, określonego jako procent obwodu przedmiotu, który dotyka pojemnika i innych już zapakowanych przedmiotów. Ta strategia preferuje wzory, w których zapakowane przedmioty nie „pułapkują” małych obszarów, co może być trudne do wykorzystania w dalszych miejscach. Dla każdej pozycji pakowania kandydata wynik jest oceniany dwukrotnie, dla dwóch orientacji przedmiotów (jeśli oba są możliwe) i wybierana jest najwyższa wartość. Więzy punktowe są zrywane przez wybranie kosza o maksymalnej powierzchni spakowanej. Ogólny algorytm jest następujący.

touching_perimeter:
  sort the items by nonincreaseing w,h values, and horizontally orient them;
  comment: Phase 1;
  compute a lower bound L on the optimal solution value, and open L empty bins;
  comment: Phase 2;
  for j := 1 to n do
     score := 0;
     for each normal packing position in an open bin do
        let score1 and score2 be scores with tow orientations;
        score := max{score,score1,score2};
     end for;
     if score > 0 then
        pack item j in the bin, position and orientation corresponding to score;
     else
        open a new bin and horizontally pack item j into i;
     end if;
  end for;
end;

Co ciekawe, w artykule opisano algorytm do określania rozmiaru optymalnie upakowanej mapy tekstur. Przydałoby się to ustalić, czy w ogóle można dopasować wszystkie tekstury do jednego atlasu 1024x1024.

Jeśli ktoś jest nadal zainteresowany, całkowicie przepisałem bibliotekę rectpack2D , aby była znacznie wydajniejsza.

Działa poprzez utrzymywanie std::vectorpustych przestrzeni w atlasie, zaczynając od pewnego początkowego maksymalnego rozmiaru (zazwyczaj maksymalnego dozwolonego rozmiaru tekstury na konkretnym GPU), dzieląc pierwszą żywotną pustą przestrzeń i zapisując podziały z powrotem do wektora.

Przełom w wydajności przyszedł po prostu za pomocą wektora, zamiast utrzymywania całego drzewa, tak jak wcześniej.

Procedura jest szczegółowo opisana w README .

Biblioteka jest pod MIT, więc cieszę się, jeśli okaże się przydatna!

Przykładowe wyniki:

Testy przeprowadzono na procesorze Intel® Core i7-4770K @ 3,50 GHz. Plik binarny został zbudowany z clang 6.0.0, przy użyciu przełącznika -03.

Arbitralne duszki z gry + japońskie glify: łącznie 3264 przedmioty.

Czas działania: 4 milisekundy
Zmarnowane piksele: 15538 (0,31% - odpowiednik kwadratu 125 x 125)

Wyjście (2116 x 2382):

W kolorze:
(czerń to zmarnowane miejsce)

Japońskie glify + niektóre duszki GUI: 3122 tematów.

Czas działania: 3,5 - 7 ms
Zmarnowane piksele: 9288 (1,23% - odpowiednik kwadratu 96 x 96)

Wyjście (866 x 871):

W kolorze:
(czerń to zmarnowane miejsce)

Dobry algorytm heurystyczny można znaleźć tutaj . Kiedy ostatnio próbowałem czegoś podobnego, znalazłem to odniesienie jako podstawowy punkt wyjścia dla większości implementacji, które widziałem.

Działa szczególnie dobrze z dużą ilością przedmiotów o regularnych kształtach, podobnych rozmiarach lub z dobrą mieszanką małych i mniejszych większych zdjęć. Najlepszą radą dla uzyskania dobrych rezultatów jest uporządkowanie danych wejściowych pod względem wielkości obrazu, a następnie spakowanie od największego do najmniejszego, ponieważ mniejsze obrazy zostaną umieszczone w przestrzeni wokół większych obrazów. Sposób, w jaki to robisz, zależy od twoich celów. Jako przybliżenie pierwszego rzędu zastosowałem obwód, a nie obszar, ponieważ uznałem, że wysokie + cienkie / krótkie + szerokie obrazy (które miałyby niski obszar) są w rzeczywistości bardzo trudne do umieszczenia później w paczce, więc używając obwodu naciskasz te dziwne kształty w kierunku przodu zamówienia.

Oto przykładowa wizualizacja danych wyjściowych mojego pakera na losowym zestawie obrazów z katalogu zrzutu obrazu mojej strony internetowej :).

Liczby w kwadratach są identyfikatorami bloków zawierających w drzewie, więc dają wyobrażenie o kolejności wstawiania. Pierwszy to identyfikator „3”, ponieważ jest to pierwszy węzeł liścia (tylko liście zawierają obrazy), a zatem ma 2 rodziców).

        Root[0]
       /      \
   Child[1]  Child[2]
      |
    Leaf[3]

Osobiście używam tylko chciwego największego bloku, który pasuje do pierwszego systemu. To nie jest optymalne, ale działa OK.

Pamiętaj, że jeśli masz rozsądną liczbę bloków tekstur, możesz wyczerpująco wyszukać najlepsze uporządkowanie, nawet jeśli sam problem to NP.

Coś, czego użyłem, co działa dobrze nawet w przypadku nieregularnych map UV, polega na przekształceniu łatki UV w maskę bitmapową i utrzymaniu maski dla samej tekstury, szukając pierwszej pozycji, w którą zmieści się łatka UV. Układam bloki według prostej heurystyki (wysokość, szerokość, rozmiar, cokolwiek) i pozwalam na rotację bloków, aby zminimalizować lub zmaksymalizować wybraną heurystykę. To daje łatwą do przeszukania przestrzeń dla brutalnej siły.

Jeśli możesz następnie powtórzyć tę próbę kilku heurystyk i / lub zastosować losowy czynnik przy wyborze kolejności i iteracji, aż skończy się pewien limit czasu.

Dzięki temu schematowi upakujesz małe wyspy UV w szczeliny wykonane przez duże, a nawet w dziurach pozostawionych w obrębie pojedynczych łat UV.

Niedawno wydaliśmy skrypt w języku Python, który spakuje tekstury do wielu plików obrazów o danym rozmiarze.

Cytat z naszego bloga:

„Chociaż istnieje wiele programów pakujących, które można znaleźć w Internecie, naszym problemem było znalezienie takiego, który mógłby obsłużyć dużą liczbę obrazów w wielu katalogach. W ten sposób narodził się nasz własny program pakujący atlasy!

W tej chwili nasz mały skrypt uruchomi się w katalogu podstawowym i załaduje wszystkie pliki .PNG do atlasu. Jeśli ten atlas jest wypełniony, tworzy nowy. Następnie spróbuje dopasować pozostałe obrazy we wszystkich poprzednich atlasach, zanim znajdzie miejsce w nowym. W ten sposób każdy atlas jest zapakowany tak ciasno, jak to możliwe. Atlasy są nazywane na podstawie folderu, z którego pochodzą ich obrazy.

Możesz łatwo zmienić rozmiar atlasu (wiersz 65), format obrazów, które chcesz spakować (wiersz 67), katalog ładowania (wiersz 10) i katalog zapisu (wiersz 13) dość łatwo, bez doświadczenia w Pythonie. Jako małe zastrzeżenie zostało to zebrane w ciągu kilku dni, aby pracować konkretnie z naszym silnikiem. Zachęcam do żądania funkcji, komentowania własnych odmian i zgłaszania wszelkich błędów, ale wszelkie zmiany w skrypcie pojawią się w wolnym czasie ”.

Zapoznaj się z pełnym kodem źródłowym tutaj: http://www.retroaffect.com/blog/159/Image_Atlas_Packer/#b

Łatwo jest spakować czcionki, ponieważ wszystkie (lub zdecydowana większość) tekstur glifów mają prawie taki sam rozmiar. Zrób najprostszą rzecz, która Ci się przydarzy, a będzie ona bardzo zbliżona do optymalnej.

Spryt staje się ważniejszy, gdy pakujesz obrazy o bardzo różnych rozmiarach. Wtedy chcesz być w stanie spakować się w luki itp. Nawet wtedy prosty algorytm, taki jak omówione wcześniej wyszukiwanie kolejności skanowania, da bardzo rozsądne wyniki.

Żaden z zaawansowanych alg nie jest magiczny. Nie będą one o 50% bardziej efektywne niż zwykły algo i nie uzyskasz z nich spójnych korzyści, jeśli nie będziesz miał oszałamiającej liczby arkuszy tekstur. to dlatego, że drobne ulepszenia wprowadzone przez lepsze algorytmy będą widoczne tylko łącznie.

Przejdź prosto i przejdź do czegoś, w którym twoje wysiłki będą lepiej nagradzane

Jeśli jest to specjalnie dla tekstur czcionek, prawdopodobnie robisz coś nieoptymalnego, ale przyjemnego i prostego:

Sortuj postacie według wysokości, najpierw najwyższej

Zacznij od 0,0 Umieść pierwszy znak przy bieżących liniach, przesuń X, umieść następny, powtarzaj, aż nie będziemy mogli dopasować innego

Zresetuj X do 0, przesuń Y w dół o wysokość najwyższego znaku w rzędzie i wypełnij kolejny rząd

Powtarzaj, aż skończą się postacie lub nie zmieścimy się w innym rzędzie.