Jak mogę wdrożyć oświetlenie oparte na wokselach z okluzją w grze w stylu Minecraft?


13

Używam C # i XNA. Mój obecny algorytm oświetlenia to metoda rekurencyjna. Jest jednak drogi , do tego stopnia, że ​​jeden fragment 8 x 128 x 8 obliczany co 5 sekund.

  • Czy istnieją inne metody oświetlenia, które będą tworzyć cienie o zmiennej ciemności?
  • A może metoda rekurencyjna jest dobra i może po prostu robię to źle?

Wydaje się, że rekurencyjne rzeczy są zasadniczo drogie (zmuszone przejść przez około 25 000 bloków na porcję). Myślałem o użyciu metody podobnej do ray tracingu, ale nie mam pojęcia, jak to zadziała. Inną rzeczą, którą próbowałem, było przechowywanie źródeł światła na liście, a dla każdego bloku uzyskanie odległości do każdego źródła światła i użycie go do oświetlenia go na odpowiednim poziomie, ale wtedy światło przechodziło przez ściany.

Mój aktualny kod rekurencyjny znajduje się poniżej. Jest to wywoływane z dowolnego miejsca w kawałku, które nie ma poziomu światła zerowego, po wyczyszczeniu i ponownym dodaniu światła słonecznego i pochodni.

world.get___atjest funkcją, która może przenosić bloki poza tę porcję (jest to wewnątrz klasy porcji). Locationto moja własna struktura, która jest jak a Vector3, ale używa liczb całkowitych zamiast wartości zmiennoprzecinkowych. light[,,]jest lightmapą dla fragmentu.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }

1
Coś jest bardzo źle, jeśli robisz 2 miliony bloków na fragmencie - zwłaszcza, że istnieje tylko 8192 bloki rzeczywiście w 8-* 128 * 8 kawałku. Co możesz zrobić, że przechodzisz przez każdy blok ~ 244 razy? (czy to może być 255?)
doppelgreener 30.10.11

1
Źle zrobiłem moją matematykę. Przepraszam: P. Wymiana pieniędzy. Ale powodem, dla którego musisz przejść tak wiele, jest to, że musisz „wypuszczać” z każdego bloku, aż osiągniesz poziom światła większy niż ustawiony. Oznacza to, że każdy blok może zostać zastąpiony 5-10 razy, zanim osiągnie rzeczywisty poziom oświetlenia. 8x8x128x5 = dużo

2
Jak przechowujesz woksele? Jest to ważne, aby skrócić czas przejścia.
Samaursa

1
Czy możesz opublikować swój algorytm oświetlenia? (pytasz, czy robisz to źle, nie mamy pojęcia)
doppelgreener

Przechowuję je w szeregu „bloków”, a blok składa się z wyliczenia materiału oraz bajtu metadanych do wykorzystania w przyszłości.

Odpowiedzi:


6
  1. Każde światło ma precyzyjne (zmiennoprzecinkowych) Pozycja i obwiedni sferę zdefiniowany przez skalarne wartości promienia światła, LR.
  2. Każdy woksel ma precyzyjną (zmiennoprzecinkową) pozycję w środku, którą można łatwo obliczyć na podstawie jego pozycji w siatce.
  3. Przeprowadź przez każdy z 8192 wokseli tylko raz i dla każdego sprawdź, czy mieści się w sferycznej objętości granicznej N świateł |VP - LP| < LR, sprawdzając , gdzie VP jest wektorem pozycji woksela względem źródła i LPjest wektorem pozycji światła względem źródła. Dla każdego światła, którego promień prąd woksel znajduje się w, przyrost jest lekki czynnik według odległości od centrum światła |VP - LP|. Jeśli znormalizujesz ten wektor, a następnie uzyskasz jego wielkość, będzie on w zakresie 0,0-> 1,0. Maksymalny poziom światła, który woksel może osiągnąć, wynosi 1,0.

Środowisko wykonawcze to O(s^3 * n), gdzie sjest długość boku (128) regionu wokseli i nliczba źródeł światła. Jeśli twoje źródła światła są statyczne, nie stanowi to problemu. Jeśli Twoje źródła światła poruszają się w czasie rzeczywistym, możesz pracować wyłącznie nad deltami, zamiast przeliczać cały shebang przy każdej aktualizacji.

Możesz nawet przechowywać woksele, na które wpływa każde światło, jako odniesienia w tym świetle. W ten sposób, gdy światło porusza się lub jest niszczone, możesz przejść tylko przez tę listę, odpowiednio dostosowując wartości światła, zamiast ponownie przechodzić przez całą siatkę sześcienną.


Jeśli dobrze zrozumiałem jego algorytm, próbuje on dokonać pewnego rodzaju pseudo-radiosity, pozwalając światłu dotrzeć do odległych miejsc, nawet jeśli oznacza to, że musi ominąć niektóre zakręty. Lub, innymi słowy, algorytm wypełniania „pustych” (niestałych) przestrzeni z ograniczoną maksymalną odległością od źródła (źródła światła) i odległości (i od niego tłumienia światła) obliczanej zgodnie z najkrótsza ścieżka do źródła. A więc - nie do końca to, co obecnie proponujesz.
Martin Sojka

Dzięki za szczegół @MartinSojka. Tak, brzmi bardziej jak inteligentne wypełnienie zalewowe. Przy każdej próbie globalnego oświetlenia koszty wydają się być wysokie nawet przy sprytnych optymalizacjach. Dlatego dobrze jest najpierw spróbować rozwiązać te problemy w 2D, a jeśli są nawet trochę drogie, wiedz, że w 3D będziesz mieć konkretne wyzwanie.
Inżynier

4

Sam Minecraft nie robi światła słonecznego w ten sposób.

Po prostu wypełniasz światło słoneczne od góry do dołu, każda warstwa zbiera światło z sąsiednich wokseli w poprzedniej warstwie z tłumieniem. Bardzo szybko - pojedynczy przebieg, brak list, brak struktur danych, brak rekurencji.

W późniejszym przebiegu musisz dodać pochodnie i inne nie zalane światła.

Jest tak wiele innych sposobów, aby to zrobić, w tym fantazyjne kierunkowe rozchodzenie się światła itp., Ale są one oczywiście wolniejsze i musisz dowiedzieć się, czy chcesz zainwestować w dodatkowy realizm, biorąc pod uwagę te kary.


Zaczekaj, więc jak dokładnie to robi Minecraft? Nie mogłem zrozumieć dokładnie tego, co mówiłeś ... Co oznacza „każda warstwa zbiera światło z sąsiednich wokseli w poprzedniej warstwie z tłumieniem”?

2
Zacznij od najwyższej warstwy (plasterek o stałej wysokości). Wypełnij go światłem słonecznym. Następnie przejdź do warstwy poniżej, a każdy woksel otrzyma podświetlenie od najbliższych wokseli w poprzedniej warstwie (powyżej). Umieść zero światła w stałych wokselach. Masz kilka sposobów na określenie „jądra”, wagi wkładów z wokseli powyżej, Minecraft używa maksymalnej znalezionej wartości, ale zmniejsza ją o 1, jeśli propagacja nie jest prosta. Jest to tłumienie boczne, więc odblokowane pionowe kolumny wokseli uzyskają pełną propagację światła słonecznego i zakręty świetlne wokół rogów.
Bjorn Wesen

1
Pamiętaj, że ta metoda nie jest w żaden sposób oparta na żadnej prawdziwej fizyce :) Główny problem polega na tym, że w istocie próbujesz przybliżyć światło bezkierunkowe (rozproszenie atmosferyczne) ORAZ odbijając radość prostą heurystą. Wygląda całkiem nieźle.
Bjorn Wesen

3
A co z „wargą”, która zwisa, jak tam dociera światło? Jak światło porusza się w górę? Gdy wchodzisz tylko z góry na dół, nie możesz cofać się w górę, aby wypełnić nawisy. Również pochodnie / inne źródła światła. Jak byś to zrobił? (mogli tylko zejść na dół!)

1
@ Felheart: minęło trochę czasu, kiedy na to spojrzałem, ale w gruncie rzeczy istnieje minimalny poziom światła w otoczeniu, który zwykle wystarcza na zwisanie, więc nie są całkowicie czarne. Kiedy sam to zaimplementowałem, dodałem drugie przejście od dołu do góry, ale tak naprawdę nie zauważyłem żadnej dużej poprawy estetycznej w porównaniu do metody ambientowej. Z pochodniami / lampami punktowymi trzeba się obchodzić osobno - myślę, że możesz zobaczyć wzór propagacji używany w MC, jeśli umieścisz pochodnię na środku ściany i poeksperymentujesz. W moich testach propaguję je na osobnym polu świetlnym, a następnie dodaje.
Bjorn Wesen

3

Ktoś powiedział, żeby odpowiedzieć na twoje pytanie, jeśli to rozgryzłeś, więc tak. Wymyślił metodę.

To, co robię, to: Najpierw utwórz trójwymiarową tablicę boolowską „już zmienionych bloków” nałożoną na porcję. Następnie wypełnij światło słoneczne, światło pochodni itp. (Wystarczy zapalić blok, który jest włączony, jeszcze nie wypełnienie powodzi). Jeśli coś zmieniłeś, wciśnij „zmienione bloki” w tej lokalizacji na true. Idź też i zmień każdy solidny blok (a zatem nie musisz obliczać oświetlenia) na „już zmieniony”.

Teraz ciężkie rzeczy: Przejdź przez cały kawałek z 16 przejściami (dla każdego poziomu światła), a jeśli jego „już zmieniono”, kontynuuj. Następnie uzyskaj poziom światła dla bloków wokół siebie. Zdobądź ich najwyższy poziom światła. Jeśli ten poziom światła jest równy poziomowi światła przejścia, ustaw blok, na którym jesteś, i ustaw „już zmieniony”, aby ta lokalizacja była prawdziwa. Kontyntynuj.

Wiem, że to trochę skomplikowane, starałem się wyjaśnić wszystko, co w mojej mocy. Ale ważne jest to, że działa i jest szybki.


2

Sugerowałbym algorytm, który łączy rozwiązanie wieloprzebiegowe z oryginalną metodą rekurencyjną i najprawdopodobniej jest nieco szybszy niż którykolwiek z nich.

Będziesz potrzebował 16 list (lub dowolnego rodzaju kolekcji) bloków, po jednej na każdy poziom światła. (W rzeczywistości istnieją sposoby optymalizacji tego algorytmu w celu wykorzystania mniejszej liczby list, ale ten sposób jest najłatwiejszy do opisania.)

Najpierw wyczyść listy i ustaw poziom światła wszystkich bloków na zero, a następnie zainicjuj źródła światła, tak jak w obecnym rozwiązaniu. Po tym (lub w trakcie) dodaj dowolne bloki o niezerowym poziomie światła do odpowiedniej listy.

Teraz przejrzyj listę bloków o poziomie światła 16. Jeśli którykolwiek z sąsiednich bloków ma poziom światła mniejszy niż 15, ustaw ich poziom światła na 15 i dodaj je do odpowiedniej listy. (Jeśli były już na innej liście, możesz je usunąć, ale nie wyrządzi to żadnej szkody, nawet jeśli tego nie zrobisz).

Następnie powtórz to samo dla wszystkich pozostałych list, w malejącej kolejności jasności. Jeśli stwierdzisz, że blok na liście ma już wyższy poziom jasności niż powinien być na tej liście, możesz założyć, że został już przetworzony i nawet nie zawracał sobie głowy sprawdzaniem swoich sąsiadów. (Z drugiej strony sprawdzanie sąsiadów może być szybsze - zależy to od tego, jak często to się zdarza. Prawdopodobnie powinieneś spróbować obu sposobów i sprawdzić, która z nich jest szybsza.)

Możesz zauważyć, że nie określiłem, jak listy powinny być przechowywane; tak naprawdę powinna to robić każda rozsądna implementacja, pod warunkiem że wstawienie danego bloku i wyodrębnienie dowolnego bloku są szybkimi operacjami. Połączona lista powinna działać, ale tak samo będzie w przypadku przyzwoitej implementacji tablic o zmiennej długości. Po prostu użyj tego, co najbardziej Ci odpowiada.


Dodatek: Jeśli większość twoich świateł nie porusza się zbyt często (podobnie jak ściany), może być nawet szybsze przechowywanie, dla każdego oświetlonego bloku, wskaźnika do źródła światła, które określa jego poziom światła (lub jednego z nich je, jeśli kilka jest powiązanych). W ten sposób można prawie całkowicie uniknąć globalnych aktualizacji oświetlenia: jeśli zostanie dodane nowe źródło światła (lub istniejące zostanie rozjaśnione), wystarczy wykonać tylko jedną rekurencyjną przepustkę dla bloków wokół niego, a jeśli zostanie ono usunięte (lub przyciemniony), wystarczy zaktualizować tylko te bloki, które do niego wskazują.

Możesz nawet obsługiwać zmiany ścian w ten sposób: kiedy ściana zostanie usunięta, po prostu rozpocznij nową rekurencyjną przepustkę świetlną w tym bloku; gdy jeden zostanie dodany, wykonaj przeliczenie oświetlenia dla wszystkich bloków wskazujących to samo źródło światła, co blok o nowych ścianach.

(Jeśli kilka zmian oświetlenia nastąpi jednocześnie - np. Jeśli światło zostanie przesunięte, co jest liczone jako usunięcie i dodatek - należy połączyć aktualizacje w jedną, używając powyższego algorytmu. Zasadniczo zerujesz poziom światła wszystkich bloki wskazujące na usunięte źródła światła, dodaj do odpowiednich list wszelkie oświetlone bloki wokół nich, a także wszelkie nowe źródła światła (lub istniejące źródła światła w wyzerowanych obszarach) i uruchom aktualizacje jak wyżej).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.