Oktanové stromy

Je jedna z metod objemového modelování. Těleso je definováno objemovými elemnty (angl. voxel), což je něco 3D pixel. Jde o malé krychličky, na které je rozdělen prostor a které buď jsou v tělese nebo nejsou. 

Na obrázku vpravo je zobrazen tento způsob pro 2D. Zápis takového 2D tělesa by mohl vypadat takto: [0,0,false], [0,1,true], [0,2,true], ...

Čím jemnější detaily potřebujeme modelovat, tím jemněji potřebujeme plochu rozdělit. Jenže tím se nám taky zvedají nároky na paměť. Proto zavádíme oktanové stromy, které tento problém eliminují.

Oktanové stromy zmenšují paměťovou náročnost detailních modelů, tak že zjemní pouze elementy, kterých se detail týká. Začíná se tedy na velkých voxelech, ale ty nyní mohou nabývat třech stavů:

  1. voxel je obsažen v tělese
  2. voxel není obsažen v tělese
  3. voxel je částečně obsažen v tělese.

V dalším kroku se řeší ty voxely, které jsou nerozhodné, tedy částečně obsaženy v tělese. Takovýto voxel ležíci na hranici tělesa rozdělím na osm menších voxelů. Na obrázku níže je tento postup znázorněn v 2D prostoru, proto se voxely dělí jen na čtyři části. V prostoru se však krychle rozdělí na osm menších krychliček.

Výsledná struktura je pak zapsána do oktanových stromů (stromy s max. osmi větvemi). Vpravo máme oktanový (respektive kvartálový, protože jsme jen v 2D prostoru) strom popisující oblast, která je vyznačená červeně na obrázku výše.