Ray casting - Ray casting
Odlévání paprsků je metodickým základem pro 3D modelování CAD/CAM těles a vykreslování obrázků. Je to v podstatě stejné jako sledování paprsků pro počítačovou grafiku, kde jsou virtuální světelné paprsky „vrhány“ nebo „sledovány“ na jejich cestě od ohniska kamery přes každý pixel v senzoru kamery, aby se určilo, co je viditelné podél paprsku v 3-D scéna. Termín „Ray Casting“ zavedl Scott Roth ve výzkumných laboratořích General Motors v letech 1978–1980. Jeho příspěvek „Ray Casting for Modeling Solids“ popisuje modelované objemové objekty kombinací primitivních těles, jako jsou bloky a válce, pomocí svazku operátorů množiny (+), průsečíku (&) a rozdílu (-). Obecná myšlenka využití těchto binárních operátorů pro modelování těles je do značné míry dána skupinou geometrického modelování Voelckera a Requichy na univerzitě v Rochesteru. Viz Solid modelování pro široký přehled pevných modelovacích metod. Tento obrázek vpravo ukazuje U-kloub modelovaný z válců a bloků v binárním stromu pomocí Rothova systému odlévání paprsků, kolem roku 1979.
Před odléváním paprsků (a sledováním paprsků) promítají algoritmy počítačové grafiky povrchy nebo hrany (např. Čáry) ze 3-D světa do obrazové roviny, kde bylo nutné použít logiku viditelnosti. Projekce roviny svět-obraz je 3-D homogenní transformace souřadnicového systému (aka: 3D projekce , afinní transformace nebo projektivní transformace ( homografie )). Vykreslení obrazu tímto způsobem je obtížné dosáhnout odstraněním skrytého povrchu/hran. Siluety zakřivených povrchů navíc musí být výslovně vyřešeny, zatímco se jedná o implicitní vedlejší produkt odlévání paprsků, takže není nutné je výslovně řešit vždy, když se změní pohled.
Odlévání paprsků výrazně zjednodušilo vykreslování obrazu 3-D objektů a scén, protože čára se transformuje na čáru. Takže místo promítání zakřivených hran a ploch ve 3-D scéně do 2-D obrazové roviny se transformované čáry (paprsky) protnou s objekty ve scéně. Homogenní transformace souřadnic je reprezentována maticí 4x4. Matematická technika je společná počítačové grafice a geometrickému modelování. Transformace zahrnuje rotace kolem tří os, nezávislé škálování podél os, překlady ve 3-D a dokonce zkosení. Transformace jsou snadno spojeny pomocí maticové aritmetiky. Pro použití s maticí 4x4 je bod reprezentován [X, Y, Z, 1] a směrový vektor je reprezentován [D x , D y , D z , 0]. (Čtvrtý termín je pro překlad a to neplatí pro směrové vektory.)
Algoritmus odlévání paprsků je při zjednodušení matematiky velmi náročný na počítačové zpracování. Pixar má velké renderovací farmy, budovy s 1000 CPU, aby jejich animace využívaly ray tracing [aka "ray casting"] jako základní techniku.
Pojem
Ray casting je nejzákladnější z mnoha algoritmů vykreslování počítačové grafiky , které používají geometrický algoritmus sledování paprsku . Algoritmy vykreslování založené na sledování paprsků pracují v pořadí obrázků k vykreslení trojrozměrných scén do dvojrozměrných obrazů. Geometrické paprsky jsou sledovány z oka pozorovatele, aby se vzorkovalo světlo ( záření ) cestující směrem k pozorovateli ze směru paprsku. Rychlost a jednoduchost vrhání paprsků pochází z výpočtu barvy světla bez rekurzivního sledování dalších paprsků, které odebírají vzorky záření dopadajícího na místo, kde paprsek dopadl. To eliminuje možnost přesného vykreslení odrazů , lomů nebo přirozeného spadu stínů ; všechny tyto prvky však lze do určité míry zfalšovat, a to kreativním využitím map textur nebo jinými metodami. Vysoká rychlost výpočtu udělala z ray castingu praktickou metodu vykreslování v raných 3D videohrách v reálném čase .
Myšlenkou odlévání paprsků je vysledovat paprsky z oka, jeden na pixel, a najít nejbližší objekt blokující cestu tohoto paprsku-představte si obrázek jako dveře obrazovky, přičemž každý čtverec na obrazovce je pixel. To je pak předmět, který oko vidí přes tento pixel. Pomocí vlastností materiálu a vlivu světel ve scéně může tento algoritmus určit stínování tohoto objektu. Zjednodušujícím předpokladem je, že pokud je povrch obrácen ke světlu, světlo dosáhne tohoto povrchu a nebude blokováno nebo ve stínu. Stínování povrchu je počítáno pomocí tradičních 3D stínovacích modelů počítačové grafiky. Jednou z důležitých výhod odlévání paprsků nabízených oproti starším algoritmům scanline byla jeho schopnost snadno si poradit s nerovinnými povrchy a tělesy, jako jsou kužele a koule . Pokud lze matematický povrch protnout paprskem, lze jej vykreslit pomocí odlévání paprsků. Vypracované objekty lze vytvářet pomocí technik modelování těles a snadno je vykreslovat.
Z abstraktu příspěvku „Odlévání paprsků pro modelování těles“: Pro vizualizaci a analýzu modelovaných kompozitních těles jsou virtuální světelné paprsky vrhány jako sondy. Díky své jednoduchosti je ray casting spolehlivý a rozšiřitelný. Nejtěžším matematickým problémem je nalezení průsečíků čáry a povrchu. Plochy jako roviny, kvadriky, tori a pravděpodobně dokonce parametrické plošné plochy mohou tedy primitivní pevné látky svázat. Zde jsou řešeny otázky adekvátnosti a účinnosti odlévání paprsků. Největší výzvou je schopnost rychlého generování obrázků pro interaktivní modelování.
Světelné paprsky a geometrie kamery zde tvoří základ pro všechny geometrické úvahy. Tento obrázek ukazuje model dírkové komory pro perspektivní efekt při zpracování obrazu a model paralelní kamery pro hromadnou analýzu. Jednoduchý model dírkové komory se skládá z ohniska (nebo bodu oka) a čtvercového pixelového pole (nebo obrazovky). Přímé světelné paprsky procházejí pixelovým polem a spojují ohnisko se scénou, jeden paprsek na pixel. Pro zastínění obrázků se intenzity paprsků měří a ukládají jako pixely. Odrazný povrch zodpovědný za hodnotu pixelu protíná paprsek pixelu.
Když je ohnisková vzdálenost, vzdálenost mezi ohniskovým bodem a obrazovkou, nekonečná, pak se zobrazení nazývá „paralelní“, protože všechny světelné paprsky jsou navzájem rovnoběžné, kolmé na obrazovku. Ačkoli je perspektivní pohled pro vytváření obrázků přirozený, některé aplikace vyžadují paprsky, které mohou být v prostoru rovnoměrně rozloženy.
Pro usnadnění modelování má typický standardní souřadnicový systém pro kameru obrazovku v rovině XY, scénu v polovičním prostoru +Z a ohnisko na ose -Z.
Paprsek je jednoduše přímka v trojrozměrném prostoru modelu kamery. Nejlépe je definován jako směrový vektor v parametrizované formě jako bod (X 0 , Y 0 , Z 0 ) a směrový vektor (D x , D y , D z ). V tomto formuláři jsou body na lince uspořádány a je k nim přístup prostřednictvím jediného parametru t. Pro každou hodnotu t je definován odpovídající bod (X, Y, Z) na přímce:
X = X0 + t · Dx Y = Y0 + t · Dy Z = Z0 + t · Dz
Pokud je vektor normalizován, pak parametr t je vzdálenost podél čáry. Vektor lze snadno normalizovat pomocí následujícího výpočtu:
Dist = √(Dx2 + Dy2 + Dz2) Dx = Dx / Dist Dy = Dy / Dist Dz = Dz / Dist
Vzhledem k geometrickým definicím objektů, z nichž každý je ohraničen jedním nebo více povrchy, je výsledek výpočtu průniku jednoho paprsku se všemi ohraničenými povrchy na obrazovce definován dvěma poli,
Ray parameters: t[1], t[2], ..., t[n] Surface pointers: S[1], S[2], ..., S[n]
kde n je počet průniků paprsku a povrchu. Uspořádaný seznam parametrů paprsku t [i] označuje vstupně-výstupní body. Paprsek vstupuje do tělesa v bodě t [1], vystupuje v t [2], vstupuje do tělesa v t [3] atd. Bod t [1] je nejblíže kameře a t [n] je nejvzdálenější. Ve spojení s parametry paprsku obsahují ukazatele povrchu jedinečnou adresu pro informace o protínaném povrchu. Povrch může mít různé vlastnosti, jako je barva, zrcadlovost, průhlednost s/bez lomu, průsvitnost atd. Pevná látka spojená s povrchem může mít své vlastní fyzikální vlastnosti, jako je hustota. To by mohlo být užitečné například tehdy, když se předmět skládá ze sestavy různých materiálů a zajímá celkový těžiště a momenty setrvačnosti.
Aplikace informací
Tři algoritmy využívající ray casting mají vytvářet perokresby, vytvářet stínované obrázky a počítat objemy a další fyzikální vlastnosti. Každý algoritmus, daný model kamery, vrhá jeden paprsek na pixel na obrazovce. Pro výpočet objemu závisí rozlišení pixelové obrazovky na požadované přesnosti řešení. U čárových kreseb a stínování obrázku určuje rozlišení kvalitu obrazu.
ŘADOVÉ VÝKRESY . Chcete-li nakreslit viditelné okraje tělesa, generujte jeden paprsek na pixel pohybující se na obrazovce shora dolů, zleva doprava. Vyhodnoťte každý paprsek, abyste identifikovali viditelný povrch S [1], první ukazatel povrchu v seřazeném seznamu průsečíků paprsku a povrchu. Pokud je viditelný povrch v místě pixelu (X, Y) odlišný od viditelného povrchu v pixelu (X-1, Y), zobrazte svislou čáru dlouhou jeden pixel se středem na (X-½, Y). Podobně, pokud je viditelný povrch na (X, Y) odlišný od viditelného povrchu na pixelu (X, Y-1), pak zobrazte vodorovnou čáru o délce jednoho pixelu se středem na (X, Y-½). Výsledný výkres bude sestávat pouze z vodorovných a svislých okrajů, které budou vypadat zubatě v rozlišeních kurzu.
Rothův systém odlévání paprsků generoval obrazy pevných předmětů vpravo. K optimalizaci byly použity krabicové skříně, dynamické ohraničení a soudržnost. U každého obrázku byly na obrazovce odebrány vzorky s hustotou asi 100 x 100 (např. 10 000) paprsků a nové okraje byly lokalizovány pomocí binárních vyhledávání. Poté všechny okraje následovaly vrháním dalších paprsků v krocích po jednom pixelu na dvě strany okrajů. Každý obrázek byl nakreslen na tubu Tektronix v rozlišení 780 x 780.
STÍNENÉ OBRÁZKY . Chcete -li vytvořit stínovaný obrázek, znovu vrhněte jeden paprsek na pixel na obrazovce. Tentokrát však pro přístup k popisu povrchu použijte ukazatel viditelné plochy S [1] na každém pixelu. Z toho vypočítejte normálu povrchu ve viditelném bodě t [1]. Hodnota pixelu, zobrazitelná intenzita světla, je úměrná kosinu úhlu, který svírají normály povrchu a vektor světelného zdroje od povrchu. Zpracováním všech pixelů tímto způsobem vznikne obraz scény rastrového typu.
VÝPOČETNÍ OBJEM A MOMENTY ZASMĚRU . Objem (a podobné vlastnosti) tělesa ohraničeného zakřivenými plochami lze snadno vypočítat integrační metodou „aproximace součtů“, aproximací tělesa pomocí sady obdélníkových rovnoběžnostěnů. Toho je docíleno „hloubkovým“ obrazem tělesa v paralelním pohledu. Lití paprsků skrz obrazovku do tělesa rozdělí těleso na prvky objemu. Dva rozměry rovnoběžnostěnu jsou konstantní, definované 2-D roztečí paprsků na obrazovce. Třetí dimenze je proměnná, definovaná vypočítaným bodem vstupu a výstupu. Konkrétně, pokud je horizontální a vertikální vzdálenost mezi paprsky na obrazovce S, pak objem „detekovaný“ každým paprskem je
S × S × (t[2]-t[1] + t[4]-t[3] + ∙∙∙ + t[n]-t[n-1]) / L
kde L je definována jako délka směrového vektoru. (Pokud je již normalizován, je roven 1.)
L = √(Dx2 + Dy2 + Dz2)
Každý ( t [ i ] - t [ i -1])/L je délka paprskového segmentu, který je uvnitř tělesa.
Tento obrázek ukazuje rovnoběžnostěny pro modelovanou hmotu pomocí paprskového lití. Toto je použití modelu kamery s paralelní projekcí.
Klasifikace paprsků In-Out
Tento obrázek ukazuje příklad binárních operátorů ve stromu kompozice pomocí + a -, kde je vyhodnocen jeden paprsek.
Procedura odlévání paprsků začíná v horní části stromu kompozice pevných látek, rekurzivně klesá ke dnu, klasifikuje paprsek s ohledem na primitivní pevné látky a poté vrací strom, který kombinuje klasifikaci levého a pravého podstromu.
Tento obrázek ilustruje kombinaci levé a pravé klasifikace pro všechny tři binární operátory.
Realistické stínované obrázky
Ray casting je přirozený modelovací nástroj pro vytváření stínovaných obrázků. Systém lití ve stupních šedi vyvinutý Scottem Rothem a Danielem Bassem v GM Research Labs produkoval obrázky na barevném rastrovém displeji Ramtek kolem roku 1979. Pro komponování obrázků poskytl systém uživateli následující ovládací prvky:
View
• Viewing direction and position
• Focal length: width-angle perspective to parallel
• Zoom factor
Illumination
• Number of light sources
• Locations and intensities of lights
• Optionally shadow
• Intensities of ambient light and background
Surface Reflectance
• % reflected diffusely
• % reflected specularly
• % transmitted
Tento obrázek ukazuje scénu tabulky se stíny ze dvou bodových světelných zdrojů.
Algoritmy stínování, které implementují všechny realistické efekty, jsou výpočetně nákladné, ale relativně jednoduché. Následující obrázek například ukazuje další paprsky, které by mohly být vrhány na jeden světelný zdroj.
Pro jeden pixel v obrázku, který má být vykreslen, algoritmus vrhá paprsek začínající v ohnisku a určuje, že protíná poloprůhledný obdélník a lesklý kruh. Aby bylo možné určit, co je v zrcadleném odrazu viditelné, musí být poté vrhán další paprsek začínající v tomto bodě ve směru symetrickém proti normálu povrchu v místě průniku paprsku. Ten paprsek protíná trojúhelník, který je neprůhledný. Nakonec je každý průsečík paprskového povrchu testován, aby se zjistilo, zda je ve stínu. Paprsek „Shadow feeler“ je vrhán z průsečíku paprsku s povrchem ke zdroji světla, aby se určilo, zda tuto dráhu blokuje nějaký jiný povrch.
Turner Whitted nazývá sekundární a další paprsky „Rekurzivní sledování paprsků“. [Zrcadlení místnosti by bylo nákladné, takže omezení počtu rekurzí je rozumné.] Bělý modelovaný lom pro průhledné fólie generováním sekundárního paprsku z bodu viditelného povrchu v úhlu určeném indexem lomu tělesa. Sekundární paprsek je poté zpracován jako zrcadlový paprsek. Refrakční vzorec a obrázkové příklady najdete v Whittedově papíru.
Skříně a účinnost
Lití paprskem se kvalifikuje jako metoda hrubé síly pro řešení problémů. Minimální algoritmus je jednoduchý, zejména s ohledem na jeho mnoho aplikací a snadné použití, ale aplikace obvykle vrhají mnoho paprsků. Milióny paprsků mohou být vrhány k vykreslení jednoho snímku animovaného filmu. Doba počítačového zpracování se zvyšuje s rozlišením obrazovky a počtem primitivních pevných látek/povrchů v kompozici.
Použitím minimálních ohraničovacích rámečků kolem těles ve stromu kompozice se vyčerpávající hledání průniku paprsků a pevných látek podobá efektivnímu binárnímu vyhledávání. Algoritmus hrubé síly provádí vyčerpávající vyhledávání, protože vždy navštíví všechny uzly ve stromu-transformuje paprsek na lokální souřadnicové systémy primitivů, testuje průsečíky paprskového povrchu a kombinuje klasifikace-i když paprsek jasně postrádá těleso. Aby bylo možné detekovat „jasnou chybu“, používá rychlejší algoritmus strom binárních kompozic jako hierarchickou reprezentaci prostoru, který pevná kompozice zaujímá. Ale všechny informace o poloze, tvaru a velikosti jsou uloženy na listech stromu, kde sídlí primitivní pevné látky. Horní a mezilehlé uzly ve stromu určují pouze operátory kombinací.
Charakterizace příloh prostorem, který vyplňují všechna tělesa, dává všem uzlům ve stromu abstraktní souhrn informací o poloze a velikosti. Hledání v hierarchii pak vedou rychlé testy „paprsek protíná kryt“. Když test selže v mezilehlém uzlu ve stromu, paprsek je zaručeně klasifikován jako mimo kompozitní, takže opakování jeho podstromů pro další zkoumání není nutné.
Přesné posouzení úspor nákladů na používání krytů je obtížné, protože závisí na prostorovém rozložení primitiv (rozdělení složitosti) a na organizaci stromu kompozic. Optimální podmínky jsou:
- Ve vesmíru se nepřekrývají žádná primitivní ohrazení
- Kompoziční strom je vyvážený a uspořádaný tak, aby se ve stromu nacházely také sub-pevné látky v blízkosti vesmíru
Naopak nejhorší podmínka je:
- Všechny primitivní přílohy se vzájemně překrývají
Následují různá vylepšení výkonu provedená v Rothově článku o lití paprsků, ale došlo k značnému vylepšení, které následně provedli ostatní.
- Early Outs . Pokud je operátor na složeném uzlu ve stromu-nebo & a paprsek je klasifikován jako z levého dílčího tělesa kompozitu, pak paprsek bude klasifikován jako mimo kompozit bez ohledu na klasifikaci paprsku s ohledem na pravý sub- pevný. Klasifikace paprsku s ohledem na správnou subtuhou látku je tedy zbytečná a pro účinnost by se jí mělo vyhnout.
- Proměny . Počáteční kombinací transformace obrazovky na scénu s transformací scény na lokální prostředí primitiva a uložením výsledných transformací obrazovky na lokální data do datových struktur primitiva je eliminována jedna transformace paprsku na průnik paprsku a povrchu.
- Rekurze . Vzhledem k hlubokému stromu kompozice může být rekurze drahá v kombinaci s přidělením a uvolněním paměti. Rekurzi lze simulovat pomocí statických polí jako zásobníků.
- Dynamické ohraničení . Pokud mají být zobrazeny pouze viditelné hrany tělesa, algoritmus odlévání paprsků může paprsek dynamicky svázat a přerušit vyhledávání. To znamená, že po zjištění, že paprsek protíná dílčí těleso, může algoritmus použít průsečík, který je nejblíže obrazovce, k utažení hranice hloubky pro test „pole průniků paprsků“. To funguje pouze pro + část stromu, počínaje od vrcholu. Pomocí - a & mohou být blízké „in“ části paprsku později „out“.
- Soudržnost . Princip koherence spočívá v tom, že povrchy viditelné na dvou sousedních pixelech jsou častěji stejné než různé. Vývojáři počítačové grafiky a systémů pro vidění použili tuto empirickou pravdu pro účinnost a výkon. U čárových kreseb je oblast obrazu obsahující hrany obvykle mnohem menší než celková plocha obrazu, takže vrhání paprsků by mělo být soustředěno kolem okrajů, a ne do otevřených oblastí. To lze účinně realizovat řídkým vzorkováním obrazovky paprsky a následným vyhledáním hran, když sousední paprsky identifikují různé viditelné povrchy, hrany pomocí binárních vyhledávání.
Anti aliasing
Zubaté hrany způsobené aliasingem jsou nežádoucím efektem technik bodového vzorkování a jsou klasickým problémem algoritmů rastrového zobrazení. Lineární nebo hladce zakřivené hrany budou působit zubatě a jsou zvláště nevhodné v animacích, protože pohyb obrazu způsobí, že okraje budou vypadat rozmazané nebo budou vypadat jako malé pohyblivé eskalátory. Rovněž mohou být ztraceny detaily ve scéně menší než mezery mezi paprsky. Zubaté hrany v perokresbě lze vyhladit následováním hran. Účelem takového algoritmu je minimalizovat počet řádků potřebných k vykreslení obrázku s přesností jednoho pixelu. Výsledkem jsou hladké hrany. Čárové kresby výše byly nakresleny tímto způsobem.
Chcete -li vyhladit zubaté okraje ve stínovaném obrázku s přesností subpixelů, je třeba vrhat další paprsky pro informace o okrajích. ( Obecný přístup viz Supersampling .) Hrany jsou tvořeny průsečíkem ploch nebo profilem zakřivené plochy. Pokud použijeme „Soudržnost“, jak je popsáno výše, pomocí binárního vyhledávání, pokud je viditelný povrch v pixelu (X, Y) odlišný od viditelného povrchu v pixelu (X+1, Y), pak je možné v jejich středu (X+) vygenerovat paprsek ½, Y) a tam je viditelný povrch. Vzdálenost mezi body vzorků lze dále rozdělit, ale hledání nemusí být hluboké. Primární hloubka hledání hladkých zubatých okrajů je funkcí gradientu intenzity přes hranu. Protože (1) oblast obrazu, která obsahuje hrany, je obvykle malým procentem z celkové plochy a (2) další paprsky vrhané při binárním vyhledávání mohou být ohraničeny hloubkou - viditelnými primitivy tvořícími okraje - náklady na vyhlazení zubatých okrajů je cenově dostupné.
Historie lití paprsků
Historii ray castingu najdete v ray tracingu (grafika), protože oba jsou v zásadě totéž. Scott Roth vynalezl termín „ray casting“, než slyšel o „ray tracing“. Vývoj Scotta Rotha v odlévání paprsků v GM Research Labs probíhal souběžně s prací na sledování paprsku Turnera Whitteda v Bell Labs.
Ray casting v raných počítačových hrách
V raných hrách první osoby bylo raycasting použito k efektivnímu vykreslení 3D světa z 2D hracího pole pomocí jednoduchého jednorozměrného skenování přes horizontální šířku obrazovky. Rané střílečky z pohledu první osoby používaly ray casting jako techniku k vytváření 3D efektu z 2D světa. Zatímco se svět jeví jako 3D, hráč se nemůže dívat nahoru nebo dolů nebo pouze v omezených úhlech se smykovým zkreslením, protože to umožňuje rychlejší vykreslování 2D hracího pole.
Wolfenstein 3D
Světoznámá videohra Wolfenstein 3D byla postavena ze čtvercové mřížky stěn s jednotnou výškou, které splňují jednobarevné podlahy a stropy. Aby bylo možné nakreslit svět, byl pro každý sloupec obrazovkových pixelů vysledován jeden paprsek a byl vybrán svislý řez textury stěny a škálován podle toho, kde ve světě paprsek narazí na zeď a jak daleko putuje, než tak učiní.
Účel úrovní založených na mřížce byl dvojí-kolize paprsků se stěnou lze nalézt rychleji, protože potenciální zásahy se stávají předvídatelnějšími a snižuje se režie paměti. Kódování široce otevřených oblastí však vyžaduje více místa.
ShadowCaster
Raven Software Hra ShadowCaster používá vylepšený Wolfenstein na bázi motoru s přidanými podlah a stropů texturování a variabilní výškou stěn.
Série Comanche
Motor Voxel Space vyvinutý společností NovaLogic pro hry Comanche sledoval paprsek v každém sloupci pixelů obrazovky a testoval každý paprsek proti bodům na výškové mapě . Poté transformoval každý prvek mapy výšky na sloupec pixelů, které byly určeny jako viditelné (to znamená, že nebyly uzavřeny pixely, které byly nakresleny vpředu), a nakreslil je odpovídající barvou z mapy textur.
Mimo raycasting
Pozdější hry pro DOS, jako DOOM od id Software, si ponechaly mnoho omezení rychlosti raycastingu 2.5D, ale přešly na alternativní vykreslovací techniky (jako BSP ), což z nich již neudělalo raycastingové motory.
Nastavení výpočetní geometrie
Ve výpočetní geometrii je problém odlévání paprsků známý také jako problém snímání paprsku a může být uveden jako následující problém dotazu: vzhledem k sadě objektů v d -dimenzionálním prostoru je předzpracujte do datové struktury tak, aby pro každý paprsek dotazu počáteční objekt zasažený paprskem lze rychle najít. Problém byl zkoumán pro různá nastavení: prostorová dimenze, typy objektů, omezení paprsků dotazu atd. Jednou z technik je použít řídký oktar voxel .