Jak mogę zoptymalizować świat wokseli w stylu Minecraft?

Odkryłem, że cudowne duże światy Minecrafta poruszają się bardzo wolno, nawet z czterordzeniowym rdzeniem i mięsną kartą graficzną.

Zakładam, że powolność gry Minecraft wynika z:

• Java, ponieważ partycjonowanie przestrzenne i zarządzanie pamięcią są szybsze w natywnym C ++.
• Słaby podział świata.

Mogę się mylić przy obu założeniach. Jednak to sprawiło, że pomyślałem o najlepszym sposobie zarządzania dużymi światami wokseli. Jak to jest prawdziwy świat 3D, gdzie blok mogą występować w dowolnej części świata, to jest po prostu wielka tablica 3D [x][y][z], gdzie każdy blok na świecie ma typ (tj BlockType.Empty = 0, BlockType.Dirt = 1itp)

Zakładam, że aby ten świat działał dobrze, musisz:

• Użyj drzewa jakiejś odmiany ( oct / kd / bsp ), aby podzielić wszystkie kostki; wygląda na to, że lepszym rozwiązaniem byłby oct / kd, ponieważ możesz po prostu podzielić partycję na poziomie kostki, a nie na poziomie trójkąta.
• Użyj jakiegoś algorytmu, aby ustalić, które bloki można obecnie zobaczyć, ponieważ bloki bliżej użytkownika mogą zaciemnić bloki z tyłu, co sprawia, że ​​ich renderowanie jest bezcelowe.
• Utrzymuj sam obiekt bloku jako lekki, aby szybko dodawać i usuwać je z drzew.

Wydaje mi się, że nie ma na to właściwej odpowiedzi, ale chciałbym zobaczyć opinie ludzi na ten temat. Jak poprawiłbyś wydajność w dużym świecie opartym na wokselach?

Jeśli chodzi o Javę vs C ++, napisałem silnik wokseli w obu (pokazana powyżej wersja C ++). Piszę też silniki wokselowe od 2004 roku (kiedy nie były modne). :) Mogę bez wahania powiedzieć, że wydajność C ++ jest znacznie lepsza (ale trudniej jest też kodować). To mniej o szybkości obliczeniowej, a więcej o zarządzaniu pamięcią. Jeśli przydzielasz / zwalniasz tyle danych, ile jest w świecie wokseli, C (++) jest językiem do pokonania. jednakpowinieneś pomyśleć o swoim celu. Jeśli wydajność jest twoim najwyższym priorytetem, skorzystaj z C ++. Jeśli chcesz po prostu napisać grę bez najnowszej wydajności, Java jest zdecydowanie akceptowalna (o czym świadczy Minecraft). Istnieje wiele trywialnych przypadków / krawędzi, ale ogólnie można oczekiwać, że Java będzie działać około 1,75-2,0 razy wolniej niż (dobrze napisany) C ++. Widać słabo zoptymalizowane, starszą wersję mojego silnika w akcji tutaj (edycja: nowszą wersję tutaj ). Podczas gdy generowanie fragmentów może wydawać się wolne, należy pamiętać, że generuje ono objętościowo diagramy voronoi 3D, obliczając wartości normalne powierzchni, oświetlenie, AO i cienie na procesorze za pomocą metod brutalnej siły. Wypróbowałem różne techniki i mogę uzyskać około 100 razy szybsze generowanie porcji przy użyciu różnych technik buforowania i instancji.

Aby odpowiedzieć na resztę pytania, możesz zrobić wiele, aby poprawić wydajność.

1. Buforowanie W miarę możliwości należy raz obliczyć dane. Na przykład piekę oświetlenie na scenie. Może używać dynamicznego oświetlenia (w przestrzeni ekranu, jako post-process), ale pieczenie w oświetleniu oznacza, że ​​nie muszę przekazywać normalnych dla trójkątów, co oznacza ...

2. Prześlij jak najmniej danych na kartę graficzną. Jedną rzeczą, o której ludzie często zapominają, jest to, że im więcej danych przesyłasz do GPU, tym więcej czasu to zajmuje. Przechodzę w jednym kolorze i pozycji wierzchołka. Jeśli chcę wykonywać cykle dzienne / nocne, mogę po prostu przeprowadzić gradację kolorów lub ponownie obliczyć scenę, gdy słońce stopniowo się zmienia.

3. Ponieważ przesyłanie danych do GPU jest tak drogie, można napisać silnik w oprogramowaniu, który pod pewnymi względami jest szybszy. Zaletą oprogramowania jest to, że może on wykonywać wszelkiego rodzaju operacje na danych / dostęp do pamięci, które po prostu nie są możliwe na GPU.

4. Graj z rozmiarem partii. Jeśli używasz procesora graficznego, wydajność może się znacznie różnić w zależności od wielkości każdej przekazywanej tablicy wierzchołków. W związku z tym baw się wielkością kawałków (jeśli używasz kawałków). Przekonałem się, że kawałki 64x64x64 działają całkiem dobrze. Bez względu na to, trzymaj swoje kawałki sześcienne (bez prostokątnych pryzmatów). Ułatwi to kodowanie i różne operacje (takie jak transformacje), aw niektórych przypadkach bardziej wydajne. Jeśli przechowujesz tylko jedną wartość dla długości każdego wymiaru, pamiętaj, że to dwa mniej rejestrów, które są zamieniane podczas obliczeń.

5. Rozważ listę wyświetlania (dla OpenGL). Mimo że są „stare”, mogą być szybsze. Musisz upiec listę wyświetlania w zmiennej ... jeśli wywołasz operacje tworzenia listy wyświetlania w czasie rzeczywistym, będzie ona beznadziejnie powolna. W jaki sposób lista wyświetlania jest szybsza? Aktualizuje tylko stan w stosunku do atrybutów na wierzchołek. Oznacza to, że mogę przekazać maksymalnie sześć twarzy, a następnie jeden kolor (w porównaniu z kolorem dla każdego wierzchołka woksela). Jeśli używasz GL_QUADS i wokseli sześciennych, może to zaoszczędzić do 20 bajtów (160 bitów) na woksel! (15 bajtów bez alfy, chociaż zwykle chcesz zachować wyrównanie 4 bajtów).

6. Używam metody brutalnej siły do ​​renderowania „fragmentów” lub stron danych, co jest powszechną techniką. W przeciwieństwie do oktetów, odczyt / przetwarzanie danych jest znacznie łatwiejsze / szybsze, choć znacznie mniej przyjazne dla pamięci (obecnie można uzyskać 64 gigabajty pamięci za 200-300 USD) ... nie to, że przeciętny użytkownik to ma. Oczywiście nie można przydzielić jednej ogromnej tablicy dla całego świata (zestaw wokseli 1024x1024x1024 to 4 gigabajty pamięci, przy założeniu, że na woksel użyto 32-bitowej liczby int). Przydzielasz / zwalniasz wiele małych tablic w oparciu o ich bliskość do przeglądarki. Możesz także przydzielić dane, uzyskać niezbędną listę wyświetlania, a następnie zrzucić dane, aby zaoszczędzić pamięć. Myślę, że idealną kombinacją może być zastosowanie hybrydowego podejścia w postaci oktetów i tablic - przechowuj dane w tablicy podczas proceduralnego generowania świata, oświetlenia itp.

7. Renderuj blisko daleko ... obcięty piksel to oszczędność czasu. GPU wyrzuci piksel, jeśli nie przejdzie testu bufora głębokości.

8. Renderuj tylko fragmenty / strony w rzutni (oczywiste). Nawet jeśli GPU wie, jak przycinać poligony poza oknem ekranu, przekazywanie tych danych nadal wymaga czasu. Nie wiem, jaka byłaby najbardziej wydajna struktura („haniebnie”, nigdy nie napisałem drzewa BSP), ale nawet zwykły raycast na porcję może poprawić wydajność, a oczywiście testowanie w porównaniu z frustum oglądania Oszczędzaj czas.

9. Oczywiste informacje, ale dla początkujących: usuń każdy wielokąt, który nie jest na powierzchni - tj. Jeśli woksel składa się z sześciu twarzy, usuń twarze, które nigdy nie są renderowane (dotykają innego woksela).

10. Zasadą ogólną wszystkiego, co robisz w programowaniu: CACHE LOCALITY! Jeśli możesz zachować lokalną pamięć podręczną (nawet przez krótki czas, to zrobi to ogromną różnicę. Oznacza to utrzymanie spójności danych (w tym samym regionie pamięci) i nie przełączanie obszarów pamięci na zbyt częste przetwarzanie. , najlepiej pracować z jednym kawałkiem na wątek i zachować tę pamięć wyłącznie dla wątku. Nie dotyczy to tylko pamięci podręcznej procesora. Pomyśl o takiej hierarchii pamięci podręcznej (od najwolniejszej do najszybszej): sieć (chmura / baza danych / itp.) -> dysk twardy (uzyskaj dysk SSD, jeśli jeszcze go nie masz), ram (uzyskaj potrójny kanał lub większą pamięć RAM, jeśli jeszcze go nie masz), pamięć podręczną procesora, rejestry. Staraj się zachować dane na ten drugi koniec i nie zamieniaj go bardziej niż musisz.

11. Gwintowanie. Zrób to. Światy Voxel dobrze nadają się do tworzenia wątków, ponieważ każdą część można obliczyć (głównie) niezależnie od innych ... Widziałem dosłownie prawie 4x poprawę (na 4 rdzeniach, 8 wątkach Core i7) w proceduralnym generowaniu świata, kiedy napisałem procedury wątków.

12. Nie używaj typów danych char / bajt. Lub szorty. Przeciętny konsument będzie miał nowoczesny procesor AMD lub Intel (prawdopodobnie również). Te procesory nie mają rejestrów 8-bitowych. Obliczają bajty, umieszczając je w 32-bitowym gnieździe, a następnie przekształcając je (może) z powrotem do pamięci. Twój kompilator może wykonywać wszelkiego rodzaju voodoo, ale użycie 32- lub 64-bitowej liczby da najbardziej przewidywalne (i najszybsze) wyniki. Podobnie wartość „bool” nie zajmuje 1 bitu; kompilator często używa pełnych 32 bitów na bool. Może być kuszące, aby wykonać pewne typy kompresji danych. Na przykład można zapisać 8 wokseli jako pojedynczą liczbę (2 ^ 8 = 256 kombinacji), jeśli wszystkie są tego samego typu / koloru. Musisz jednak pomyśleć o konsekwencjach tego - może zaoszczędzić sporo pamięci, ale może również utrudniać działanie, nawet przy krótkim czasie dekompresji, ponieważ nawet ta niewielka ilość dodatkowego czasu skaluje się sześciennie do wielkości twojego świata. Wyobraź sobie obliczanie raycast; dla każdego kroku raycasta musiałbyś uruchomić algorytm dekompresyjny (chyba że wpadniesz na sprytny sposób uogólnienia obliczeń dla 8 wokseli w jednym promieniu).

13. Jak wspomina Jose Chavez, wzór na wagę lataną może być przydatny. Tak jak przy użyciu mapy bitowej do reprezentowania kafelka w grze 2D, możesz budować swój świat z kilku rodzajów kafelków (lub bloków 3D). Wadą tego jest powtarzanie tekstur, ale można to poprawić, stosując dopasowane warianty tekstur. Zasadniczo chcesz korzystać z instancji w dowolnym miejscu.

14. Unikaj przetwarzania wierzchołków i pikseli w module cieniującym podczas wysyłania geometrii. W silniku wokselowym nieuchronnie będziesz mieć wiele trójkątów, więc nawet prosty moduł cieniujący piksele może znacznie skrócić czas renderowania. Lepiej jest renderować do bufora, a następnie cieniować piksele jako post-proces. Jeśli nie możesz tego zrobić, spróbuj wykonać obliczenia w module cieniującym wierzchołki. Tam gdzie to możliwe, inne obliczenia należy zapisać w danych wierzchołków. Dodatkowe przejścia stają się bardzo drogie, jeśli musisz ponownie renderować całą geometrię (np. Mapowanie cieni lub mapowanie środowiska). Czasami lepiej jest zrezygnować z dynamicznej sceny na rzecz bogatszych szczegółów. Jeśli twoja gra ma modyfikowalne sceny (tj. Zniszczalny teren), zawsze możesz ponownie obliczyć scenę, gdy rzeczy zostaną zniszczone. Ponowna kompilacja nie jest droga i powinna zająć mniej niż sekundę.

15. Rozwiń pętle i utrzymuj tablice płasko! Nie rób tego:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }

    EDYCJA: Dzięki bardziej szczegółowym testom odkryłem, że to może być źle. Użyj skrzynki, która najlepiej pasuje do Twojego scenariusza. Ogólnie rzecz biorąc, tablice powinny być płaskie, ale stosowanie pętli o wielu indeksach może często być szybsze w zależności od przypadku

EDYCJA 2: gdy używasz pętli z wieloma indeksami, najlepiej zapętlić w kolejności z, y, x zamiast na odwrót. Twój kompilator może to zoptymalizować, ale byłbym zaskoczony, gdyby to zrobił. Maksymalizuje to wydajność dostępu do pamięci i lokalizacji.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}

16. Czasami trzeba dokonywać założeń, uogólnień i poświęceń. Najlepsze, co możesz zrobić, to założyć, że większość twojego świata jest całkowicie statyczna i zmienia się co kilka tysięcy klatek. W przypadku animowanych części świata można to zrobić w osobnym przebiegu. Załóż również, że większość twojego świata jest całkowicie nieprzejrzysta. Przezroczyste obiekty można renderować w osobnym przejściu. Załóżmy, że tekstury różnią się tylko co x jednostek lub że obiekty można umieszczać tylko w przyrostach x. Załóżmy, że świat ma ustalony rozmiar ... kuszący, jak świat nieskończony, może prowadzić do nieprzewidzianych wymagań systemowych. Na przykład, aby uprościć generowanie wzoru voronoi w skałach powyżej, założyłem, że każdy punkt środkowy voronoi leżał w jednolitej siatce, z niewielkim przesunięciem (innymi słowy, implikowany haszowanie geometryczne). Załóżmy, że świat się nie zawija (ma krawędzie). Może to uprościć wiele zawiłości wprowadzonych przez układ współrzędnych zawijania, przy minimalnym koszcie dla wygody użytkownika.

Możesz przeczytać więcej o moich implementacjach na mojej stronie

Istnieje wiele rzeczy, które Minecraft może robić bardziej wydajnie. Na przykład Minecraft ładuje całe pionowe filary o wymiarach około 16 x 16 płytek i renderuje je. Uważam, że wysyłanie i renderowanie niepotrzebnej liczby płytek jest bardzo nieefektywne. Ale nie wydaje mi się, żeby wybór języka był ważny.

Java może być dość szybka, ale w przypadku czegoś zorientowanego na dane C ++ ma dużą zaletę ze znacznie mniejszym nakładem na dostęp do tablic i pracę w bajtach. Z drugiej strony znacznie łatwiej jest wykonywać wątki na wszystkich platformach Java. O ile nie planujesz używać OpenMP lub OpenCL, nie znajdziesz takiej wygody w C ++.

Mój idealny system byłby nieco bardziej złożoną hierarchią.

Kafelek to pojedyncza jednostka, prawdopodobnie około 4 bajtów, która przechowuje takie informacje, jak rodzaj materiału i oświetlenie.

Segment byłby blokiem płytek o wymiarach 32 x 32 x 32.

1. Flagi byłyby ustawione dla każdej z sześciu stron, jeśli cała strona jest solidnymi blokami. Umożliwiłoby to rendererowi zamykanie segmentów za tym segmentem. Obecnie wydaje się, że Minecraft nie wykonuje testów okluzji. Wspomniano jednak o możliwości sprzętowego eliminowania okluzji, które może być kosztowne, ale lepsze niż renderowanie ogromnych ilości wielokątów na kartach niższej klasy.
2. Segmenty były ładowane do pamięci tylko podczas aktywności (gracze, postacie niezależne, fizyka wody, wzrost drzew itp.). W przeciwnym razie byłyby wysyłane bezpośrednio skompresowane z dysku do klientów.

Sektory byłyby blokiem segmentów 16 x 16 x 8.

1. Sektory śledzą najwyższy segment dla każdej kolumny pionowej, dzięki czemu segmenty wyższe niż ten można szybko określić jako puste.
2. Śledziłby również dolny segment okludowany, dzięki czemu każdy segment, który należy wyrenderować z powierzchni, mógł zostać szybko złapany.
3. Sektory śledzą także, kiedy następnym razem każdy segment będzie wymagał aktualizacji (fizyka wody, wzrost drzew, itp.). W ten sposób ładowanie w każdym sektorze wystarczyłoby, aby utrzymać świat przy życiu, i ładowanie tylko w segmentach wystarczająco długich, aby wykonać swoje zadania.
4. Wszystkie pozycje bytu byłyby śledzone względem sektora. Pozwoliłoby to uniknąć błędów zmiennoprzecinkowych obecnych w Minecraft, gdy podróżujesz bardzo daleko od centrum mapy.

Świat byłby nieskończoną mapą sektorów.

1. Świat byłby odpowiedzialny za zarządzanie sektorami i ich kolejne aktualizacje.
2. Świat zapobiegawczo wysyłałby segmenty graczom na ich potencjalnych ścieżkach. Minecraft reaktywnie wysyła segmenty, o które prosi klient, powodując opóźnienie.

Minecraft jest dość szybki, nawet na moim 2-rdzeniowym. Wydaje się, że Java nie jest tutaj czynnikiem ograniczającym, chociaż występuje niewielkie opóźnienie serwera. Lokalne gry wydają się radzić sobie lepiej, więc zamierzam założyć pewne nieefektywności.

Jeśli chodzi o twoje pytanie, Notch (autor gry Minecraft) długo pisał na blogu o tej technologii. W szczególności świat jest przechowywany w „kawałkach” (czasami je widzisz, zwłaszcza gdy brakuje, ponieważ świat się jeszcze nie wypełnił.), Więc pierwszą optymalizacją jest decyzja, czy fragment może być widoczny, czy nie .

Jak już zgadłeś, w obrębie fragmentu aplikacja musi zdecydować, czy blok może być widoczny, czy nie, na podstawie tego, czy inne bloki są zasłonięte.

Należy również zauważyć, że istnieją blok TWARZE, które można założyć, że nie są widoczne, z powodu albo zasłonięcia (tj. Inny blok zakrywa twarz) lub kierunku, w którym kamera wskazuje (jeśli kamera skierowana jest na północ, możesz nie zobaczy północnej powierzchni JAKICHKOLWIEK bloków!)

Typowe techniki obejmowałyby również nie trzymanie oddzielnych obiektów bloków, ale raczej „blok” typów bloków, z pojedynczym blokiem prototypowym dla każdego z nich, wraz z pewnym minimalnym zestawem danych opisujących, jak ten blok może być niestandardowy. Na przykład, nie ma żadnych niestandardowych bloków granitowych (które znam), ale woda ma dane, które określają, jak głęboko jest ona wzdłuż każdej powierzchni bocznej, z której można obliczyć jej kierunek przepływu.

Twoje pytanie nie jest jasne, czy chcesz zoptymalizować szybkość renderowania, rozmiar danych lub co. Pomocne byłoby wyjaśnienie.

Oto kilka słów ogólnych informacji i porad, które mogę przekazać jako, hm, nadmiernie doświadczony modder Minecraft (który może przynajmniej częściowo dać ci trochę wskazówek).

Powód, dla którego Minecraft jest wolny, ma wiele wspólnego z niektórymi wątpliwymi decyzjami projektowymi na niskim poziomie - na przykład za każdym razem, gdy odniesienie do bloku polega na pozycjonowaniu, gra sprawdza współrzędne za pomocą około 7, jeśli oświadczenia zapewniają, że nie wykracza poza granice . Co więcej, nie ma sposobu na złapanie „fragmentu” (jednostki 16 x 16 x 256 bloków, z którymi gra współpracuje), a następnie bezpośredniego odniesienia do niej bloków, aby ominąć wyszukiwania w pamięci podręcznej i, hmm, głupie problemy z weryfikacją (na przykład, każde odniesienie do bloku obejmuje również wyszukiwanie fragmentów, między innymi.) W moim modzie stworzyłem sposób na bezpośrednie chwytanie i zmianę tablicy bloków, co przyspieszyło generowanie ogromnych lochów z niemożliwych do gry lagów na niezauważalnie szybkie.

EDYCJA: Usunięto twierdzenie, że zadeklarowanie zmiennych w innym zakresie spowodowało wzrost wydajności, w rzeczywistości tak nie jest. Wydaje mi się, że w tamtym czasie połączyłem ten wynik z czymś innym, z czym eksperymentowałem (konkretnie, usuwając obsady między liczbami podwójnymi i zmiennoprzecinkowymi w kodzie związanym z eksplozją poprzez konsolidację do liczb podwójnych ... co zrozumiałe, miało to ogromny wpływ!)

Ponadto, chociaż nie jest to obszar, w którym spędzam dużo czasu, większość dławików wydajności w Minecraft stanowi problem z renderowaniem (około 75% czasu gry jest poświęcone temu w moim systemie). Oczywiście nie przejmujesz się tak bardzo, czy problemem jest obsługa większej liczby graczy w trybie dla wielu graczy (serwer nic nie renderuje), ale ma to znaczenie, ponieważ każdy komputer może nawet grać.

Więc niezależnie od wybranego języka, postaraj się bardzo zbliżyć do szczegółów implementacji / niskiego poziomu, ponieważ nawet jeden mały szczegół w projekcie takim jak ten może mieć znaczenie (jeden przykład dla mnie w C ++ brzmiał: „Czy kompilator może statycznie wstawiać funkcję wskaźniki? „Tak, może! Zrobiłem niesamowitą różnicę w jednym z projektów, nad którymi pracowałem, ponieważ miałem mniej kodu i przewagę wbudowanego.)

Naprawdę nie lubię tej odpowiedzi, ponieważ utrudnia to projektowanie na wysokim poziomie, ale to bolesna prawda, jeśli wydajność jest problemem. Mam nadzieję, że okazało się to pomocne!

Ponadto odpowiedź Gavina obejmuje pewne szczegóły, których nie chciałem powtarzać (i wiele więcej! Jest wyraźnie bardziej kompetentny w tym temacie niż ja) i w większości się z nim zgadzam. Będę musiał poeksperymentować z jego komentarzem dotyczącym procesorów i krótszych rozmiarów zmiennych, nigdy o tym nie słyszałem - chciałbym udowodnić sobie, że to prawda!

Chodzi o to, aby pomyśleć o tym, jak najpierw załadujesz dane. Jeśli w razie potrzeby przesyłasz strumieniowo dane mapy do pamięci, istnieje naturalna granica tego, co możesz renderować, jest to już ulepszenie wydajności renderowania.

To, co zrobisz z tymi danymi, zależy od Ciebie. Aby uzyskać wydajność GFX, możesz następnie użyć funkcji Przycinanie do przycinania ukrytych obiektów, obiektów, które są zbyt małe, aby były widoczne itp.

Jeśli szukasz technik grafiki, jestem pewien, że w sieci można znaleźć góry.

Wzorem do obejrzenia jest wzór Flyweight . Wierzę, że większość odpowiedzi tutaj odnosi się do tego wzoru w taki czy inny sposób.

Chociaż nie znam dokładnej metody, którą stosuje Minecraft, aby zminimalizować pamięć dla każdego typu bloku, jest to możliwa droga do wykorzystania w twojej grze. Chodzi o to, aby mieć tylko jeden obiekt, taki jak obiekt prototypowy, który przechowuje informacje o wszystkich blokach. Jedyną różnicą byłaby lokalizacja każdego bloku.

Ale nawet lokalizację można zminimalizować: jeśli wiesz, że blok terenu jest jednego typu, dlaczego nie przechowywać jego wymiarów jako jednego gigantycznego bloku z jednym zestawem danych o lokalizacji?

Oczywiście jedynym sposobem, aby się dowiedzieć, jest rozpoczęcie wdrażania własnego i wykonanie testów pamięci pod kątem wydajności. Poinformuj nas jak to idzie!