Jaką strukturę danych należy zastosować do przedstawienia terenu wokselowego?


18

Według strony Wikipedii o wokselach „[...] pozycja woksela jest wywnioskowana na podstawie jego pozycji względem innych wokseli (tj. Jego pozycji w strukturze danych, która tworzy pojedynczy obraz wolumetryczny)”.

Jak wdrożyć taką strukturę danych? Myślałem o oktawie, ale zastanawiam się, czy jest coś jeszcze, o czym nigdy nie słyszałem.


1
Jest to nieco trudne pytanie, ponieważ jest bardzo zależne od tego, jakie dane będą potrzebne twoje dane wokselowe. Rzeczy, takie jak pełny woksel, jak to wygląda, itp. Będą dość zależne od tego, co robisz. Po drugie, struktura danych musi nadawać się do szybkiego dostępu do manipulacji danymi w czasie rzeczywistym, a następnie ich aktualizacji. Jak utrzymać niską strukturę pamięci na woksel i szybki dostęp do danych / szybką manipulację są właściwie głównymi wyzwaniami technicznymi, które są dość celowe specyficzne podczas pracy z silnikami wokselowymi. Brak odpowiedzi, więc komentarz.
James

Odpowiedzi:


14

Pierwszy. Napiszmy, co wiemy o każdym wokselu:

voxel = (x, y, z, color) // or some other information

Ogólne miejsce do przechowywania

Ogólny sposób jest po prostu następujący:

set of voxels = set of (x,y,z, color)

Zauważ, że tryplet (x, y, z) jednoznacznie identyfikuje każdy woksel, ponieważ woksel jest punktem w przestrzeni i nie ma możliwości, aby dwa punkty zajmowały jedno miejsce (myślę, że mówimy o statycznych danych wokseli).

Proste dane powinny wystarczyć. Ale w żadnym wypadku nie jest to szybka struktura danych.

Renderowanie jest AFAIK wykonywane przez algorytm scanline. Artykuł Tom's Hardware na temat wokseli zawiera obraz algorytmu scanline .

Szybkie wyszukiwanie

Jeśli potrzebne jest szybkie wyszukiwanie, najszybszą strukturą danych dla wyszukiwania jest skrót (inaczej tablica, mapa ...). Musisz więc zrobić z niego skrót. Naiwnie chcemy po prostu najszybszego sposobu na uzyskanie dowolnego elementu:

array [x][y][z] of (color)
  • Ma O (1) do wyszukiwania wokseli za pomocą współrzędnych x, y, z.

  • Problem polega na tym, że jego wymagania przestrzenne to O (D ^ 3), gdzie D jest zakresem każdej liczby x, y i z (zapomnij liczbę rzeczywistą, ponieważ gdyby były znakami, które mają zakres 256 wartości, byłoby 256 ^ 3 = 2 ^ 24 == 16 777 216 elementów w tablicy).

Ale to zależy od tego, co chcesz zrobić z wokselami. Jeśli renderowanie jest tym, czego chcesz, to prawdopodobnie ta tablica jest tym, czego chcesz. Ale problem z magazynowaniem wciąż pozostaje ...

Jeśli problemem jest przechowywanie

Jedną z metod jest użycie kompresji RLE w tablicy. Wyobraź sobie kawałek wokseli (zbiór wokseli, w których woksele mają stałą wartość jednej współrzędnej ... jak płaszczyzna, na przykład z = 13). Taki kawałek wokseli wyglądałby jak prosty rysunek w MSPaint . Powiedziałbym, że model wokselowy zajmuje zwykle ułamek wszystkich możliwych miejsc (przestrzeń D ^ 3 wszystkich możliwych wokseli). Wierzę, że „weź parę z tripletu współrzędnych i ściśnij pozostałą oś” załatwi sprawę (na przykład weź [x] [y] i dla każdego elementu ściśnij wszystkie woksele na osi z przy danym x, y .. . powinno być 0 do kilku elementów, RLE dobrze by się tu spisało):

array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color 

Inną metodą rozwiązania problemu z pamięcią byłoby użycie tablicy zamiast struktury danych drzewa:

tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
  • Octree, jak wspomniał Nick. Powinien kompresować woksele. Octree ma nawet przyzwoitą prędkość wyszukiwania, myślę, że to trochę O (log N), gdzie N to liczba wokseli.
  • Octree powinien mieć możliwość przechowywania przyzwoicie dowolnych danych wokseli.

Jeśli woksele są uproszczoną mapą wysokości, możesz przechowywać właśnie to. Lub Możesz przechowywać parametry do funkcji, która generuje mapę wysokości, czyli procedury generuje ją ...

I oczywiście możesz połączyć wszystkie możliwe podejścia. Ale nie przesadzaj, chyba że sprawdzisz, czy Twój kod działa i zmierzysz, że jest NAPRAWDĘ szybszy (więc warto go zoptymalizować).

TL; DR

Oprócz Octrees jest kompresja RLE z wokselami, Google „Voxlap”, „Ken Silverman” ...

Zasoby

Istnieje lista zasobów i dyskusja na temat sposobu szybkiego renderowania wokseli, w tym dokumenty i kod źródłowy .


1
„Jeśli problemem jest przechowywanie”: możesz także użyć kompresji VTC ( oss.sgi.com/projects/ogl-sample/registry/NV/… ) lub kompresji DXT
KindDragon

@KindDragon dziękuję za te informacje. :) To bardzo dobry pomysł.
user712092,

Link do zasobu nie działa.
Ezequiel

4

Istnieją dwa różne aspekty struktury danych, o których mogą mówić.

Struktury tablicowe

Gdy odwołujesz się do elementu tablicy o dowolnej liczbie wymiarów, weź pod uwagę, że sama tablica po przejściu wskaźników (np. myArray[4][6][15]) Wie, co jest w tej lokalizacji. Jeśli to, co znajduje się w tym miejscu, to woksel, woksel nie musi dodatkowo rejestrować własnych współrzędnych x, y i z - tablica zawierająca woksel określa domyślnie swoją lokalizację na świecie na podstawie lokalizacji indeksowanej przez tablicę.

Powodem tego jest to, że arytmetyka wskaźnika używana do tego rodzaju dostępu do tablicy jest z natury szybka i ogólnie mówiąc, stanowi podstawę dla większości szybkich (często nazywanych „natywnymi”) tablic występujących w różnych językach. Minusem tych tablic jest to, że muszą mieć elementy o równej wielkości w bajtach, aby wspomniana arytmetyka wskaźnika mogła być zastosowana.

Octrees

(Zwracam uwagę na tę sekundę, ponieważ jest to mniej prawdopodobne, do czego odnosi się wikipedia, a implementacje wokseli nie wymagają użycia oktetów, chociaż prawie wszystkie współczesne używają oktetów).

Węzeł główny oktetu jest pojedynczą, niepodzielną kostką. Ustawmy przykład. Powiedzmy, że korzeń waszego oktetu, sam środek sześcianu, znajduje się {0, 0, 0}w przestrzeni 3D. Gdy zaczniesz umieszczać obiekty w tej przestrzeni (czytaj: więcej niż jeden obiekt), nadszedł czas, aby dalej podzielić oktodę. W tym miejscu dzieli się na 8 ( okt ), dzieląc go na 3 płaszczyzny, przy czym płaszczyzny te to płaszczyzny xy, xz i yz. Twoja oryginalna kostka zawiera teraz dokładnie 8 mniejszych kostek. Każdy z tych podwęzłów jest ustawiony jako odsunięcie od centralnej kostki nadrzędnej . To znaczy, że na przykład sześcian leżący w dodatniej oktanie xyz miałby przesunięcie od środka rodzica / zawierającego środek dokładnie{root.width / 4, root.height / 4, root.depth / 4}. Zamiast określać pozycję bezwzględną dla każdego podwęzła, bardziej logiczne jest rozważenie węzła nadrzędnego jako źródła jego przestrzeni potomnej. W ten sam sposób działają wykresy scen.

Wystarczy to zobaczyć na rysunku 2D, gdzie narysujesz kwadrat i podzielisz go na 4 równe regiony. Gdyby, podobnie jak nasz główny węzeł oktowy, środek kwadratu nadrzędnego został uznany za {0, 0}, wówczas 4 środki kwadratów podrzędnych byłyby

{root.width / 4, root.height / 4}, {-root.width / 4, root.height / 4}, {root.width / 4, -root.height / 4}, {-root.width / 4, -root.height / 4}

... W stosunku do ich rodzica - ta sama zasada jak w 3D.


Dziękuję za Twoją odpowiedź. W moim przypadku niektóre duże części terenu byłyby zbudowane z tego samego typu woksela i dlatego myślałem o oktetach (duża część nie musiałaby być dzielona). Daję jednak szansę matrycy 3D, ponieważ wygląda ona na prostszą w implementacji. Jestem pewien, że uda mi się na tyle wyodrębnić szczegóły implementacji mojej klasy terenu, że zmiana implementacji nie byłaby tak trudna, gdyby zaszła taka potrzeba.
pwny

Nie ma za co. Zdecydowanie proponuję zajrzeć do oktetów, naprawdę nie są trudne do uchwycenia. Ale tak, twoje podejście ma na razie sens, na pewno warto wykonać wstępne prototypowanie przy użyciu tablicy 3D.
Inżynier

W ramach dalszej lektury, dobrą dyskusję na temat implementacji oktetów, w tym kilka przydatnych odniesień, można znaleźć w artykule Intela dotyczącym rozszerzenia STL dla gier .
Martin Foot

1

Możesz użyć RLE. Ale możesz użyć SVO (Sparse Voxel Octree), id Tech 6 używa SVO. SVO jest techniką renderowania grafiki komputerowej 3D z wykorzystaniem metody raycasting lub czasami ray tracingu do reprezentacji danych w postaci oktetów.

Technika ta jest nieco inna, ale ogólnie polega na generowaniu i przetwarzaniu kadłuba punktów (rzadkich wokseli), które są widoczne lub mogą być widoczne, biorąc pod uwagę rozdzielczość i rozmiar ekranu.

Użyj raycastingu, ponieważ jest szybszy.


0

Zasadniczo można uniknąć struktury danych 3D dla terenu. Zamiast tego możesz użyć mapy wysokości . Może to być bardzo tanio i skutecznie weryfikowane w środowisku uruchomieniowym. Z mojego doświadczenia wynika, że ​​śledzenie minimalnej wysokości, którą musisz wyrenderować w każdej kolumnie, a także czasami kąty start-stop-top, opłaca się, abyś mógł również wyrównać kolumny tła.

Oto jeden, który zrobiłem dawno temu: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

Jeśli w terenie znajduje się niewielka liczba nawisów, jaskiń lub innych elementów, których nie można przedstawić za pomocą mapy wysokości, możesz mieć otwory w mapie wysokości i mieć alternatywną reprezentację, np. Prawdziwe obiekty wokselowe 3D, które wypełniają tylko te zlokalizowane miejsca, w których kosztują środowisko wykonawcze jest uzasadnione.

Rzadkie reprezentacje wokselowe są tego warte, gdy masz duże prawdziwe światy wokselowe. John Carmack rozmawia o nich od kilku lat ...


Myślałem też o mapach wysokości, ale kilka rzeczy odciągnęło mnie od nich. Chodzi o to, że w moim przypadku teren nie jest naprawdę duży ani bardzo skomplikowany (pomyśl teren typu labirynt, bardzo kartezjański). Chciałbym również, aby część terenu była zniszczalna lub aby użytkownik mógł wpływać na teren poprzez konstrukcję. Może to spowodować, że gracz utworzy „tunele” w terenie, które wydają się bardziej skomplikowane do przedstawienia za pomocą mapy wysokości.
pwny
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.