Oktreen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. toukokuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 13 muokkausta .

Oktree ( oktanttipuu , oktaalipuu , englanniksi  octree ) on eräänlainen puutietorakenne , jossa jokaisessa sisäisessä solmussa on täsmälleen kahdeksan "lasta". Oktaalipuita käytetään yleisimmin 3D-avaruuden jakamiseen jakamalla se rekursiivisesti kahdeksaan soluun. Octrees ovat nelipuiden 3D- analogi . Englanninkielinen nimi "octree" muodostuu sanasta oct + tree ja kirjoitetaan yleensä "octree" eikä "octtree".

Avaruuden esitys oktreilla

Jokainen oktanttipuun solmu jakaa tilan kahdeksaan uuteen oktanttiin .  Oktren pistealueelle (PR ) solmu tallentaa eksplisiittisen 3D-pisteen, joka on kyseisen solmun avaruusjaon "keskus". Tämä piste määrittää yhden kulmista jokaisessa kahdeksasta lapsivälistä. MX-oktressa jakopiste on solmun edustaman tilan implisiittinen keskipiste. PR-oktrin juurisolmu voi edustaa ääretöntä avaruutta. MX-oktrin juurisolmun tulee edustaa rajattua avaruuden aluetta, jotta implisiittiset keskukset ovat hyvin määriteltyjä. Oktreja ei voida pitää k-ulotteisina puina , koska k-ulotteiset puut halkeavat ulottuvuutta pitkin, kun taas oktreet jakautuvat pisteen ympärille. Myös k-ulotteiset puut ovat aina binaarisia , mikä ei pidä paikkaansa oktreille.  

Oktreiden yleinen käyttö

• Spatiaalinen indeksointi
• Tehokas 3D -törmäystunnistus
• Piilopintojen määritys
• Nopea moninapamenetelmä
• Strukturoimaton verkko
• Elementtimenetelmä
• säteen jäljitys

Värin kvantisointisovellus

Oktree-algoritmi värien kvantisoimiseksiGerwauzin ja Purgathoferin vuonna 1988 keksimä kuva koodaa kuvan väritiedot oktreiksi yhdeksän tason syvyyteen. Oktreen käyttö selittyy sillä, että RGB- järjestelmässä on kolme värikomponenttia. Tämä algoritmi on erittäin muistitehokas, koska puun kokoa voidaan rajoittaa. Oktren alempi (perus)taso koostuu lehtisolmuista , jotka keräävät väritietoja, joita ei ole esitetty puussa; nämä solmut sisältävät aluksi 1 bitin. Jos oktriin syötetään paljon haluttua suurempi määrä väripalettia, niin oktron kokoa voidaan jatkuvasti pienentää etsimällä solmu alemmalta (perus)tasolta ja keskiarvottamalla sen bittidata solmulehteksi, kutistuva osa. puusta. Kun nouto on valmis, puu tutkii kaikkia polkuja alas solmulehtiin ottaen huomioon hakupolun bitit. Tämä prosessi tuottaa likimääräisen tarvittavan määrän värejä.  

Oktreiden käyttö tietyissä sovelluksissa

• Urho3D on ilmainen pelimoottori .
• Sauerbraten on tietokonepeli, joka käyttää Cube 2 -pelimoottoria , joka käyttää oktreja.
• OGRE on ilmainen olio- grafiikkamoottori , jossa on oktreja käyttävä näkymänhallinta ( eng.  Octree Scene Manager )
• Dendro on rinnakkainen moniruudukkoelementtikirjasto, joka käyttää octreea (MPI/C++-toteutus)
• FLASH on Chicagon yliopiston koodipaketti astrofysikaalisten prosessien numeeriseen simulointiin.

Ulkoiset linkit

Englanninkieliset lähteet

• Octree-kvantisointi Microsoft Systems Journalissa
• Värien kvantisointi oktreilla
• Värien kvantisointi käyttämällä Octreesia julkaisussa Dr. Dobbin lähdekoodi  (linkki ei saatavilla)
• Yleiskatsaus oktreista
• Octtree Generation Algorithm -algoritmin rinnakkaistoteutus, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library
• Generation of Octrees from Raster Scan with Reduced Information Loss, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, IASTED International Conference VIIP 2001 [1]  (linkki ei ole käytettävissä)
• C++-toteutus (GPL-lisenssi)
• Parallel Octrees for Finite Element Applications Arkistoitu 3. maaliskuuta 2016 Wayback Machinessa

Venäjänkieliset lähteet

• Artem Merets "Scart". Octree Algorithm – teoria ja käytäntö DirectX 2 :ssa. UralDev (26. helmikuuta 2007). Haettu 3. kesäkuuta 2009. Arkistoitu alkuperäisestä 2. huhtikuuta 2012. (määrätön)
• Artem Merets "Scart". Octree-algoritmi (osa 2) 2. UralDev (5. helmikuuta 2008). Haettu 3. kesäkuuta 2009. Arkistoitu alkuperäisestä 2. huhtikuuta 2012. (määrätön)
• Joe. Kohtausobjektitilan osiointi rakentamalla oktreen . gamedev.com . Haettu: 3.6.2009. (määrätön)
• Octree (Octant tree) . gamedev.com . Haettu: 3.6.2009. (määrätön)
• Aleksei Ignatenko. Graafinen prosessi Geometrinen mallinnus Luento 6 (pääsemätön linkki) . Haettu 3. kesäkuuta 2009. Arkistoitu alkuperäisestä 2. huhtikuuta 2012. (määrätön) 

Sanakirjat ja tietosanakirjat	iso kiinalainen

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla