Indeksowanie twarzy Voxel (uproszczenie siatki, możliwe, że przy użyciu chciwości)

Edycja: To tylko dla mojego własnego doświadczenia uczenia się, to NIE z powodu wydajności zadaję to pytanie.

Dotyczy to silnika terenowego podobnego do Minecrafta. Bloki przechowuję w porcjach (bloki 16 x 256 x 16 w porcji). Podczas generowania fragmentu używam wielu technik proceduralnych do ustawiania terenu i umieszczania obiektów. Podczas generowania zachowuję jedną tablicę 1D dla pełnego fragmentu (bryłę lub nie) i osobną tablicę 1D brył.

Po wygenerowaniu iteruję przez pełne bloki sprawdzając ich sąsiadów, więc generuję tylko ściany bloków, które nie mają stałych sąsiadów. Przechowuję, które twarze mają zostać wygenerowane na ich własnej liście (to 6 list, jedna na każdą możliwą twarz / normalna). Podczas renderowania fragmentu renderuję wszystkie listy w bieżącym fragmencie kamery i tylko listy skierowane w stronę kamery we wszystkich innych fragmentach. Robię to, przechowując wszystkie 6 list w jednym buforze, a następnie zmieniam tylko rysowane zakresy.

Korzystając z atlasu 2D z tą małą sztuczką cieniującą, sugerowaną przez Andrew Russella, chcę całkowicie połączyć podobne twarze razem. Oznacza to, że jeśli znajdują się na tej samej liście (tej samej normalnej), sąsiadują ze sobą, mają ten sam poziom światła itp. Wiem, że nadal będę mieć prostokąty, ale powinno to łatwo zmniejszyć liczbę moich wierzchołków o 50% lub lepiej, jeśli moje szacunki są prawidłowe.

Moim założeniem byłoby posortowanie każdej z 6 list według osi, na której spoczywają, a następnie według pozostałych dwóch osi (lista na górze bloku byłaby posortowana według wartości Y, następnie X, a następnie Z).

Dzięki temu samemu z łatwością mogłem scalić paski twarzy, ale w miarę możliwości chcę połączyć więcej niż tylko paski razem. Przeczytałem o tym chciwym algorytmie tworzenia siatki, ale mam problem z jego zrozumieniem.

Więc moje pytanie: aby wykonać scalanie twarzy zgodnie z opisem (ignorując, czy to zły pomysł na dynamiczny teren / oświetlenie), czy może jest jakiś algorytm, który jest łatwiejszy do wdrożenia? Z radością przyjąłbym również odpowiedź, która prowadzi mnie przez chciwy algorytm w znacznie prostszy sposób (link lub wyjaśnienie).

Nie przeszkadza mi niewielki spadek wydajności, jeśli jest łatwiejszy do wdrożenia, a nawet jeśli jest tylko trochę lepszy niż zwykłe tworzenie pasków. Martwię się, że większość algorytmów skupia się raczej na trójkątach niż na quadach i używając atlasu 2D takim, jakim jestem, nie wiem, czy mogłabym zaimplementować coś trójkąta na podstawie moich obecnych umiejętności.

PS: Już frustum wybijam na porcję i zgodnie z opisem, również wybijam twarze między solidnymi blokami. Nie jestem jeszcze okluzyjny i może nigdy.

* Edycja: Wdrożyłem własną małą technikę, która prawdopodobnie ma nazwę, ale po prostu przeglądam 6 list, które są posortowane według osi, na których spoczywają, następnie według typu bloku, a następnie według poziomu oświetlenia. Idę przez nie, tworząc nowe prostokąty, gdy idę i rozwijam je jednocześnie (z dużym odchyleniem w kierunku pewnej osi). To zdecydowanie nie jest optymalne, ale rzeczywiście jest dość szybkie i obniża moją liczbę wierzchołków średnio o prawie 50%. Komentarz Byte56 jest, jak sądzę, prawdziwą odpowiedzią, ale nie mogę jej wybrać dla odpowiedzi / nagrody.

Oto mój szybki i uproszczony sposób radzenia sobie z tym problemem PO wygenerowaniu pełnego terenu początkowego bez większej optymalizacji. Zakładając, że wszystkie podane kwadraty to ten sam obraz, poziom światła, normalny itp. .. każdy kolor jest innym kwadratem, który renderowałbym. Z posortowanymi listami takimi, jakie są, jest to bardzo łatwe / szybkie podejście.

Chcesz tylko robić paski, a najlepiej - prostokąty. Nie ma innych kształtów, które byłyby dla ciebie do rozwiązania lub przydatne.

Chciałbym również zauważyć, że utrzymując 6 list na porcję, w dowolnym momencie będziesz używać 5 list z porcji w głównych kierunkach i co najmniej 3 w każdym innym. Marnujesz tutaj czas, gdy karta graficzna nie tylko może wykonać tę optymalizację dla Ciebie, ale nawet jeśli zrobiłbyś to sam, lepiej byłoby trzymać wszystkie twarze w jednym miejscu i porównywać normalną z kierunkiem do kamera (badanie produktu DOT wektorów).

Linki CaptainRedMuff na temat Chciwej siatki, którą już widziałeś, są odpowiedzią na Twój problem. Powinno być również oczywiste, że skończysz z „pasiastymi” siatkami, ale są one doskonale skuteczne, a uzyskanie czegoś bardziej optymalnego będzie bardziej skomplikowane, a wyraziłeś, że chciwa siatka jest już zbyt skomplikowana.

Jeśli masz problemy z wydajnością z jednym kawałkiem, to sprawia, że ​​myślę, że coś innego jest bardzo nie tak.

Po pierwsze sądzę, że zbyt często wywołujesz operację losowania. Możesz tylko powiedzieć karcie graficznej, aby rysowała od 50 do 400 ~ razy na sekundę, w zależności od sprzętu. Ile wykonujesz połączeń do .setData lub .draw ____ Prymitywów?

Artykuł, do którego prowadzi łącze, nie zawiera algorytmu generowania siatki; określa sposób oceny możliwych rozwiązań.

Ogólnie rzecz biorąc, artykuł zawiera dobre podsumowanie: 1) naiwne rozwiązanie jest złe, 2) istnieje optymalne rozwiązanie, ale zarówno pisanie, jak i uruchamianie będzie czasochłonne, 3) szybkie wyrównywanie daje znacznie lepsze wyniki ( i to wszystko robi sam Minecraft), a na koniec 4) może istnieć mądrzejsze rozwiązanie (chciwy algorytm).

„Rozwiązaniem”, które sugerujesz na obrazie w swoim pytaniu, jest chciwy algorytm. Wygląda na to, że twoje pytanie brzmi „czy poprawnie wdrożyłem jego rozwiązanie?” na co muszę odpowiedzieć „nie dał rozwiązania; sam to rozwiązałeś”.

Czy twoje rozwiązanie może być lepsze? Meh Pewnie. Prawdopodobnie nie warto. Wydaje mi się, że lepszym rozwiązaniem byłoby wyeliminowanie okluzji lub LOD. Minecraft marnuje dużą liczbę cykli rysowania powierzchni, nawet gdy jesteś pod ziemią, a także rysowania rozległych sieci systemów jaskiń i kopalni, gdy jesteś na powierzchni. Gdy masz dobry podział siatki, tak, pozbycie się zaciemnionych powierzchni może być dobrą rzeczą - ale (np.) Generalnie szybciej jest pozwolić, aby twoja karta graficzna zrobiła culling backface niż zrobić to na CPU.