Myślałem o tym problemie. Czy przy obecnej technologii można stworzyć replikę ziemi 1: 1 w grze opartej na wokselach? Jaka jest najlepsza struktura danych do przechowywania tej gigantycznej mapy? Którego algorytmu należy użyć do renderowania tej struktury danych w czasie rzeczywistym?
Poniższe pytania opierają się na następujących założeniach:
Każdy woksel ma rozdzielczość 1 metra sześciennego.
Dla uproszczenia każdy woksel wymaga tylko 1 bajtu informacji o metadanych. Informacje te zostaną wykorzystane do przechowywania identyfikatora „typu” woksela (ziemia, woda, skała itp.).
Objętość ziemi wynosi 1 * 10ˆ21 metrów sześciennych.
Przez „obecną technologię” uwzględniam wszystko, co jest dostępne w handlu, ale nie superkomputery.
Do wygenerowania mapy zostanie użyta tylko topografia Ziemi i batymetria. Budynki ludzkie, rośliny lub jaskinie są wykluczone. Podziemne bloki zostaną wybrane na podstawie badań geologicznych, np .: jeśli głębokość jest większa niż 3000 km, render woksel „magmy”.
Podobnie jak w Minecraft, mapa nie jest statyczna, można ją modyfikować w grze.
„Nieskończony” zasięg rysowania to duży plus, jaki jest sens posiadania całej ziemi na mapie, jeśli nie możesz latać i obserwować całej planety?
Pierwszy wniosek, do którego doszedłem, gdy pomyślałem o tym problemie, jest taki, że przechowywanie danych Ziemi w sposób liniowy jest niemożliwe, przy założeniu, że każdy woksel zajmuje tylko 1 bajt pamięci, to nadal wymagałoby 1 zettabajta do przechowywania mapy. Wymagany jest więc pewien rodzaj kompresji.
Myślę, że oktok wokseli może skompresować mapę, ale nie jestem pewien, o ile. Entropia tej mapy wokseli jest prawdopodobnie bardzo niska, więc myślę, że można osiągnąć bardzo wysoki poziom kompresji.
Zrzeczenie się
To pytanie teoretyczne, nie mam zamiaru pisać wokselowej ziemi
EDYTOWAĆ
ESA GOCE odwzorował już geoidę Ziemi z dokładnością 1–2 cm. Wierzę, że ta informacja mogłaby zostać wykorzystana do wygenerowania bardzo dokładnej mapy wysokości Ziemi. Wykluczałoby to potrzebę stosowania algorytmu do wypełniania luk w topografii Ziemi.
źródło
Odpowiedzi:
Zależy to od zastosowanej metody podziału przestrzennego, chociaż wszystkie metody podziału (jak każda metoda kompresji) ostatecznie określają, gdzie nie może nastąpić dalsza kompresja, ze względu na narzuty struktury danych i inne czynniki logiczne / matematyczne. Przykład można znaleźć w oktatach. Dla każdego węzła w oktcie wskaźnik musi być zachowany dla jego rodzica i / lub dzieci (w zależności od tego, jak postępujesz w architekturze struktury danych), aby umożliwić znaczące przejście. Każda struktura drzewa może zawierać n dzieci. Im niższy stosunek 1: n, tym bardziej efektywne wykorzystanie przestrzeni zyskujesz, a tym samym większe koszty ogólne w przechodzeniu przez drzewo, ponieważ musisz mieć więcej węzłów przodków, aby zawierać tę samą liczbę wokseli liści (w twoim przypadku około 510 bilionów dolarów z nich reprezentujących powierzchnię).
Biorąc pod uwagę, że w twoim przypadku podstawowymi kwestiami są koszty przechowywania i renderowanie całej planety (lub jej części) z dużej odległości, nie ma struktury danych, którą poleciłbym ponad oktok. Mapowanie jest koniecznością: średnica 12,8 miliona metrów przy najbliższej wyższej mocy 2 wynosi 2 ^ 24 = 16,8 miliona. 24 poziomy oktawy do przejścia oznaczałyby gigantyczną ilość rozgałęzień - bardzo kosztowne zarówno dla procesorów graficznych, jak i procesorów. Ale pod warunkiem, że postępujesz właściwie, będziesz musiał przejść tylko kilka poziomów jednocześnie. Biorąc jednak pod uwagę wymaganą ilość miejsca, alternatywy są nieliczne i dalekie (patrz poniżej).
Możliwości mapowania w oktatach sprawiają, że jest to niezwykle potężne narzędzie do dużych woluminów, takich jak te, które opisujesz. W przeciwieństwie do wszystkich innych znanych metod podziału (z wyjątkiem drzew KD), oktree utrzymuje podział na poziomie minimalnym, co oznacza, że wizualne i fizyczne różnice między poziomami mipmap są również utrzymywane na minimalnym poziomie, co oznacza znacznie drobniejsze delty w ziarnistości, gdy wchodzisz i w dół drzewa.
Z drugiej strony, jeśli chcesz stworzyć świat, w którym hierarchiczne przechodzenie przez siatkę jest ograniczone do minimum, musisz wymienić miejsce na zwiększenie prędkości.
Mówiąc o idealnym stosunku 1: n, nie ma pod tym względem drobniejszej struktury niż drzewo kd. Tam, gdzie liczba oktetów dzieli się na 2 dla każdej osi, co daje 2 ^ 3 = 8 pojedynczych komórek potomnych, drzewo kd dzieli się dokładnie raz na poziom podziału. Problem polega na tym, że musisz wybrać hiperpłaszczyznę do podziału, a ta hiperpłaszczyzna może być wybrana wokół dowolnej z 3 osi. Chociaż jest optymalny pod względem przestrzeni, sprawia, że przechodzenie przez 3D (takie jak podczas rymowań, podstawowa operacja przy użyciu oktetów do fizyki lub renderowania) jest znacznie trudniejsze niż w oktawie, ponieważ dynamiczna struktura typu portalu musi być zachowana, aby nagrywać interfejsy między poszczególnymi węzłami drzewa kd.
RLE jest innym podejściem do kompresji, ale pod wieloma względami trudniej jest zastosować do takiego problemu (gdzie podstawa operacji jest sferyczna), ponieważ kompresja RLE jest jednowymiarowa i musisz wybrać oś, w której działa. planetę, można wybrać oś biegunową, ale każdy wybór jednej osi wprowadziłby pewne problemy z przechodniami do renderowania i fizyki, gdy działałby pod pewnymi nieoptymalnymi kątami. Oczywiście można również uruchomić RLE w 3 osiach jednocześnie, trzykrotnie zwiększając koszt przechowywania lub w 6 osiach (-x, + x, -y, + y, -z, + z) jako dalszą optymalizację.
Aby odpowiedzieć na twoje pytanie (lub nie!)
Nie zamierzam bezpośrednio odpowiadać na pytanie, jaki rodzaj sprzętu, ale myślę, że patrząc na to z perspektywy oktetu, zaczynam dać ci wyobrażenie o tym, co w rzeczywistości jest możliwe na jakim sprzęcie. Zachęcam do zejścia tą drogą, jeśli naprawdę chcesz wiedzieć, może być najłatwiej wdrożyć prostą rzadką oktodę(patrz artykuł Laine'a w odnośnikach) i umieść w nim kulistą skorupę wokseli powierzchniowych i zobacz, jakie jest wynikowe wykorzystanie przestrzeni. Podejdź stamtąd. Zobacz, jak daleko możesz się posunąć, zanim pamięć systemowa zacznie się rozdawać. Nie wymaga to napisania renderera, chyba że chcesz wizualizacji. Należy również pamiętać, że najlepiej to zrobić na procesorze - procesory graficzne na ogół nie mają wystarczającej pojemności pamięci, aby poradzić sobie z problemami na taką skalę. Jest to jeden z powodów, dla których Intel dąży do przejścia na masowo równoległe procesory: korzyści GPGPU, które są lepsze w tego rodzaju sprawach, można zastosować w znacznie większej przestrzeni pamięci bez wąskich gardeł magistrali systemowej. Prawdopodobnie są tu inni lub na mathematics.stackexchange.com,
Jeśli chodzi o wymagania dotyczące nieskończonej odległości widzenia, jasne, ale pytanie zawsze sprowadza się do: „ile szczegółów w jakiej odległości”. Renderowanie nieskończonych szczegółów wymagałoby nieskończonych zasobów. Właśnie tutaj zaczyna się mipmapowanie zmiennej sceny. Należy również pamiętać, że wszystkie struktury danych zawierają pewien kompromis prędkości dla przestrzeni kosmicznej i odwrotnie. Oznacza to mniej / wolniejsze renderowanie, jeśli chcesz mieć większy świat przy takim samym nakładzie pracy inżynieryjnej.
źródło
Ponieważ najprawdopodobniej nigdy nie dowiesz się o właściwościach każdego metra sześciennego świata rzeczywistego, będziesz potrzebować sposobu na wygenerowanie tych danych, które są niepewne na podstawie założeń. Więc jeśli masz to ustalone, nie musisz obliczać i przechowywać wszystkich tych danych, ale możesz raczej wygenerować je w locie.
Przede wszystkim możesz odrzucić wszystkie woksele w ziemi, ponieważ trzeba je obliczyć tylko wtedy, gdy ktoś faktycznie wykopie dziurę, np. woksele stają się widoczne.
Na powierzchni ziemi prawdopodobnie zrobiłbym zdjęcie jako punkt wyjścia do moich obliczeń. Może jakaś mapa temperatury i wilgotności pozwoli Ci obliczyć rodzaj bloków, które chcesz zastosować. Na przykład. Woda, piasek (pustynia), trawa, śnieg itp. Ponieważ obraz prawdopodobnie nie będzie zawierał jednego piksela informacji na każdy metr kwadratowy powierzchni ziemi, musiałbyś to zmieszać z pewnym hałasem, aby wygenerować trochę zmienności na powierzchnia. Jeśli zawsze używasz tych samych losowych nasion, wynik powinien być jednak deterministyczny.
Ponadto przydatna byłaby mapa wysokości, aby można było określić wysokość elementów powierzchni. W ten sposób możesz dodawać góry itp.
Sprowadza się to do objętości danych niektórych obrazów 2D, które zawierają informacje o powierzchni ziemi. W przypadku wszystkiego w środku powróciłbyś do czysto proceduralnego podejścia, w którym renderujesz różne rodzaje bloków, w zależności od odległości od centrum ziemi. Ale jak powiedziano powyżej, należy je obliczać tylko wtedy, gdy ktoś wykopie dziurę.
Aby zmiany były trwałe, zapisywałbym tylko modyfikacje na świecie. Więc jeśli ktoś wykopie dziurę, zapisałbym informacje o tym, które woksele zostały usunięte, ponieważ powinienem być w stanie renderować otaczające woksele proceduralnie.
Jeśli chodzi o rendering: do wykonania tej czynności potrzebne będą wyrafinowane algorytmy określania poziomu szczegółowości i wygładzania. Głupio jest renderować wszystkie woksele powierzchniowe, gdy kamera jest na poziomie powiększenia pokazującym cały świat. Na tym poziomie woksele powinny być znacznie większe, może wystarczyłaby nawet zwykła teksturowana kula.
Myślę, że najtrudniejszą rzeczą byłoby posiadanie solidnego generatora, który pozwala obliczyć właściwości woksela, nawet dla różnych „rozdzielczości”, dzięki czemu można go używać do generowania różnych poziomów szczegółowości.
źródło
Możesz w zasadzie zrobić to samo, co robi Minecraft. Zamiast tworzyć taką ilość danych, możesz zdefiniować świat jako formułę matematyczną, ilekroć do wyświetlenia potrzebny jest kawałek danych, generujesz go za pomocą tej formuły.
Taka formuła jest zwykle budowana przy użyciu koncepcji hałasu Perlina , pozwala to na szczegóły na wszystkich poziomach, możesz mieć pasma górskie tak duże jak te w prawdziwym świecie, a jednak wybrać generowanie tylko niewielkiej ich części. Możesz wygenerować tyle szczegółów, ile ci się podoba, dzięki czemu możliwe jest tworzenie bardzo drobnych szczegółów dla bliskich rzeczy, a także generowanie odległych scen na wymaganym poziomie szczegółowości.
Minecraft zapisuje wszystkie bloki, które odwiedziłeś, wraz z wszelkimi dokonanymi zmianami, można po prostu zapisać tylko różnicę między światem generowanym a światem zaktualizowanym, ale myślę, że zapisywanie dużych bloków było łatwiejsze i stosunkowo dobrze kompresują.
Nie sądzę, aby istniała jakaś gra, która tak naprawdę ogranicza to, ale bardzo często stosuje się formułowanie generowania wszystkich „nieistotnych” szczegółów dużych światów gier. Nie jestem jednak pewien, jak powszechne jest podejście generowania w razie potrzeby, w przeciwieństwie do zwykłego generowania partii i umieszczania jej na dysku.
źródło
Możesz szukać danych wektorowych z lądów Ziemi, ponieważ dane wektorowe mają tę zaletę, że skalują się do dowolnej skali, którą chcesz. Połącz go z mapą wysokości Ziemi, aby wygenerować wysokość terenu. Ostatnim krokiem są szczegółowe zdjęcia satelitarne, z których możesz wybrać rodzaj górnego bloku na podstawie obrazu, aby uzyskać kamień tam, gdzie jest skała, piasek tam, gdzie jest piasek itp. Prawdopodobnie powinny zostać wygenerowane rzeczywiste wnętrza planety tak jak robi to Minecraft, chyba że możesz znaleźć szczegółowe dane geograficzne do pracy. Zasadniczo to, co chcesz zrobić, to znaleźć dane geograficzne i ekstrapolować je, biorąc pod uwagę tylko dane wejściowe współrzędnych XYZ. Oznacza to, że masz ograniczone dane, a resztę ekstrapolujesz tak precyzyjnie, jak tylko możesz.
źródło