Budowanie Octree do generowania terenu

Wcześniej zaimplementowałem marszowe kostki / czworościany do renderowania IsoSurface. Działało ( YouTube ), ale wydajność była tragiczna, ponieważ nigdy nie wdrożyłem do wdrażania zmiennej Poziomu Szczegółowości na podstawie odległości widzenia (lub nawet usuwania starych, odległych fragmentów).

Tym razem postanowiłem zrobić kolejny krok i zrobić to poprawnie. Zacząłem od utworzenia OctreeNode, który działa w następujący sposób po Build()wywołaniu.

• Jeśli fragment jest zbyt mały, aby go zbudować, natychmiast wróć.
• Sprawdź, czy powierzchnia przechodzi przez objętość tego fragmentu.
• Jeśli tak, to zdecyduj, czy chcemy podnieść LOD (ponieważ kamera jest blisko)
• Jeśli tak, to spawnuj 8 dzieci i wywołaj na nich ten sam proces
• Jeśli nie, zbuduj siatkę, używając wymiarów bieżącego węzła

Niektóre PseudoCode:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds)² > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ Oprócz gęstości zwracanej w punkcie, źródło gęstości może określać możliwy zakres gęstości dla danej objętości.

² Dostawca LoD przyjmuje ramkę ograniczającą i zwraca maksymalną pożądaną wartość LoD na podstawie położenia kamery / frustum, ustawień użytkownika itp.

Więc ... To wszystko działa całkiem dobrze. Używając prostej kuli jako źródła gęstości i pokazując wszystkie węzły:

I tylko liście:

Istnieje jednak kilka problemów:

• Muszę zdefiniować początkowy wolumin ograniczający (im większy, tym więcej przetwarzania muszę wykonać)
• U korzenia drzewa nie mam pojęcia, jak głębokie będą liście, więc moja numeracja LoD zaczyna się od najniższej jakości (korzenia) i rośnie wraz ze zmniejszaniem się kawałków. Ponieważ LoD jest teraz w stosunku do początkowej objętości, nie ma większego zastosowania, gdy chcę robić rzeczy w określonych rozmiarach / jakościach.

Myślałem o kilku opcjach, ale obie wydają się wadliwe:

• Zachowaj kolekcję oktetów i dodawaj / usuwaj w zależności od odległości. Nie widzę, jak ładnie się zestawiłbym w siatkę¹, a ponadto potrzebowałbym listy znanych pustych węzłów, szczególnie jeśli chcę dowolnych powierzchni 3D (aby uniknąć wielokrotnego ponownego obliczania pustych objętości)
• Dodaj węzeł nadrzędny do bieżącego katalogu głównego, a następnie dodaj siedem rodzeństwa dla oryginalnego węzła. To działałoby i byłoby dostępne na żądanie, ale wydaje się, że rozsądne zmniejszenie się rozsądnie, gdy gracz porusza się po krajobrazie. Sprawiłoby to, że liczby LoD byłyby jeszcze mniej znaczące.

¹ [W wyjaśnieniu do Q poniżej] Obecnie, jeśli 2 fizycznie sąsiadujące węzły w drzewie znajdują się w różnych LOD, mam trochę kodu, aby zmusić wierzchołki tak, aby nie było szwu podczas generowania siatek. Jestem w stanie to zrobić, znając gęstość wielu otaczających węzłów. W scenariuszu, w którym mam 2 niezależne oktawy obok siebie, nie miałbym łatwego sposobu na odzyskanie tych informacji, co spowodowałoby szwy.

Jaki jest optymalny sposób na to?

Nie jestem pewien, czy odpowiadam na dokładne pytanie, więc idę odpowiadać w segmentach i mogę odpowiedzieć w komentarzach, jeśli istnieje nieporozumienie na temat konkretnego pytania.

Muszę zdefiniować początkowy wolumin ograniczający (im większy, tym więcej przetwarzania muszę wykonać)

Nie wydaje się, że tak powinno być. Ponieważ liczba oktetów zwiększa ziarnistość wykładniczo, dodanie kilku poziomów u góry powinno być bardzo małym wzrostem wydajności netto.

U korzenia drzewa nie mam pojęcia, jak głębokie będą liście, więc moja numeracja LoD zaczyna się od najniższej jakości (korzenia) i rośnie wraz ze zmniejszaniem się kawałków. Ponieważ LoD jest teraz w stosunku do początkowej objętości, nie ma większego zastosowania, gdy chcę robić rzeczy w określonych rozmiarach / jakościach.

Jeśli ustawisz oktawę główną na jakąś „wystarczająco dużą wartość”, wówczas „LoD względem początkowej objętości” nie powinno stanowić problemu. I jak wspomniano powyżej, nie sądzę, aby dodatkowy poziom u góry wpływał na ogólną wydajność.

Zachowaj kolekcję oktetów i dodawaj / usuwaj w zależności od odległości. Nie widzę, jak ładnie się przekreślę, a ponadto potrzebowałbym listy znanych pustych węzłów, szczególnie jeśli chcę dowolnych powierzchni 3D (aby uniknąć wielokrotnego ponownego obliczania pustych objętości)

Jak rozumiem, to proponowane rozwiązanie polega na obniżeniu LoD podczas odchodzenia od poprzednio szczegółowego obszaru. Myślę, że powinien wyglądać bardzo podobnie do ścieżki kodu „rosnącego LoD”:

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Następnie nie spędzasz zbyt wiele czasu na sprawdzaniu odległych węzłów, ponieważ możesz polegać na tym, że chociaż daleko, nie ma zbyt wielu „aktywnych” węzłów, ponieważ wszystkie węzły o wyższej rozdzielczości zostaną usunięte.

Zakładając, że małe węzły mają skalę skalną, oznaczałoby to potencjalnie dziesiątki, jeśli nie setki poziomów podczas podróży przez kontynent

Myślę, że logarytmiczna skala oktetu sprawia, że ​​jest to nadal wykonalne. Jeśli twój najwyższy poziom ma szerokość 1 000 00 000 000 m (byłby 25 razy szerszy niż rzeczywista Ziemia i przy 625x powierzchni), a twoje bity najniższego poziomu mają 10 cm średnicy, to jest 32 poziomy w oktawie, czyli prawdopodobnie wystarczająco zarządzalny. Jeśli chcesz mieć planetę 100 razy szerszą niż Ziemia (i 10000 razy większą powierzchnię), to tylko dodatkowe 3-4 poziomy w twojej oktawie. W tym momencie graczowi zajęłoby setki lat przejście przez świat, a jeśli użyjesz naiwnej matematyki zmiennoprzecinkowej, świat będzie kumulował błędy precyzji.

Zachowaj kolekcję oktetów i dodawaj / usuwaj w zależności od odległości. Nie widzę, jak ładnie się zestawiłbym w siatkę¹, a ponadto potrzebowałbym listy znanych pustych węzłów, szczególnie jeśli chcę dowolnych powierzchni 3D (aby uniknąć wielokrotnego ponownego obliczania pustych objętości)

Czy nie jest to zasadniczo równoważne z posiadaniem oktawy o szerokości miliarda km, ale utrzymywaniem listy wskaźników do każdego, powiedzmy, 1 km bloku? Wtedy „zazębianie się” polegałoby po prostu na węzłach wielkości 2 km. Zachowanie lokalnego odniesienia do każdego „dużego bloku” na średnim poziomie zapobiega również iteracji przez węzły najwyższego poziomu, jeśli martwisz się o „możliwe dziesiątki dodatkowych poziomów oktawy”