Oktfa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2016. május 19-én felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

Az octree ( octant tree , octal tree , angolul  octree ) egy olyan fa adatstruktúra , amelyben minden belső csomópontnak pontosan nyolc "gyermeke" van. Az oktális fákat leggyakrabban a 3D tér felosztására használják nyolc cellára való rekurzív felosztással. Az oktrák a négyfák 3D-s analógjai . Az angol "octree" név az oct + tree-ből származik, és általában "octree"-nek írják, nem pedig "octtree"-nek.

Térábrázolás oktrával

Az  oktánsfa minden csomópontja nyolc új oktánsra osztja fel a teret . Az oktfa ponttartományában  (PR ) a csomópont egy explicit 3D pontot tárol, amely az adott csomópont térfelosztásának "középpontja". Ez a pont határozza meg mind a nyolc gyermek mező egyik sarkát. Egy MX oktrában a felosztási pont a csomópont által képviselt tér implicit középpontja. A PR-okfa gyökércsomópontja egy végtelen teret képviselhet. Egy MX oktfa gyökércsomópontjának egy korlátozott térrégiót kell képviselnie, hogy az implicit középpontok jól meghatározottak legyenek. Az oktrákat nem tekinthetjük k-dimenziós fáknak , mivel a k-dimenziós fák egy dimenzió mentén hasadnak, míg az oktrák egy pont körül. Ezenkívül a k-dimenziós fák mindig binárisak , ami nem igaz az oktrákra.

Az oktrák általános használata

• Térbeli indexelés
• Hatékony 3D ütközésészlelés
• Rejtett felületek meghatározása
• Gyors többpólusú módszer
• Strukturálatlan háló
• Végeselem módszer
• sugárkövetés

Alkalmazás színkvantáláshoz

Oktfa algoritmus színkvantáláshozGerwauz és Purgathofer 1988-ban találta fel, a kép színadatait kilenc szint mélységű oktfaként kódolja. Az octree használatát az magyarázza, hogy az RGB rendszerben három színösszetevő van. Ez az algoritmus nagyon memóriatakarékos, mivel a fa mérete korlátozható. Az oktra alsó (alap) szintje levélcsomópontokból áll , amelyek olyan színadatokat halmoznak fel, amelyek nem jelennek meg a fában; ezek a csomópontok kezdetben 1 bitet tartalmaznak. Ha a kívántnál jóval nagyobb mennyiségű színpaletta kerül az oktrába, akkor az oktfa mérete folyamatosan csökkenthető úgy, hogy az alsó (alap) szinten keresünk egy csomópontot, és annak bitadatait csomópontlevélre, zsugorító részre átlagoljuk. a fáról. A lekérés befejezése után a fa megvizsgálja az összes útvonalat a csomóponti levelekig, figyelembe véve a keresési útvonal bitjeit. Ez a folyamat hozzávetőleges számú színt eredményez.  

Oktrák használata meghatározott alkalmazásokban

• Az Urho3D egy ingyenes játékmotor .
• A Sauerbraten egy számítógépes játék , amely a Cube 2 játékmotort használja , amely oktrákat használ.
• Az OGRE egy ingyenes objektum-orientált grafikus motor , amelyben van egy oktrákat használó jelenetkezelő ( eng. Octree  Scene Manager )
• A Dendro egy párhuzamos többrácsos végeselem-könyvtár, amely octree-t használ (MPI/C++ implementáció)
• A FLASH egy kódcsomag az asztrofizikai folyamatok numerikus szimulációjához a Chicagói Egyetemen.

Külső linkek

Angol nyelvű források

• Octree kvantálás a Microsoft Systems Journalban
• Színkvantálás oktrákkal
• Színkvantálás az Octrees segítségével a Dr. Dobb forráskódja  (nem elérhető link)
• Az oktrák áttekintése
• Az oktfa generálási algoritmus párhuzamos megvalósítása, 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]  (hivatkozás nem érhető el)
• C++ implementáció (GPL licenc)
• Parallel Octrees for Finite Element Applications archiválva 2016. március 3-án a Wayback Machine -nél

Orosz nyelvű források

• Artem Merets "Scart". Octree Algorithm – Elmélet és gyakorlat a DirectX 2 -n. UralDev (2007. február 26.). Letöltve: 2009. június 3. Az eredetiből archiválva : 2012. április 2. (határozatlan)
• Artem Merets "Scart". Octree algoritmus (2. rész) 2. UralDev (2008. február 5.). Letöltve: 2009. június 3. Az eredetiből archiválva : 2012. április 2. (határozatlan)
• Joe. A jelenet objektumterének felosztása egy oktfa felépítésével . gamedev.com . Letöltve: 2009. június 3. (határozatlan)
• Octree (Oktáns fa) . gamedev.com . Letöltve: 2009. június 3. (határozatlan)
• Alekszej Ignatenko. Grafikus folyamat Geometriai modellezés 6. előadás (elérhetetlen link) . Letöltve: 2009. június 3. Az eredetiből archiválva : 2012. április 2. (határozatlan) 

Szótárak és enciklopédiák	nagy kínai

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll