Arbres Octals (Octrees)

És un model de sòlids del tipus enumeració espacial. Cal partir d'un cub "univers" que conté tot l'objecte, i anar dividint l'espai en octants recursivament. El resultat és un arbre octal amb nodes interiors o exteriors en funció de si contenen una part prou "simple" de l'objecte.

• Nodes interiors: Grisos.
• Nodes terminals (fulles): Blancs, Negres, Cara, Aresta, Vèrtex, Grisos Terminals.

Un octtree clàssic només té nodes G,N,B (els nodes grisos G són nodes corresponents a cubs que cal subdividir mentre que els nodes blancs B són nodes totalment exteriors a l'objecte i els nodes negres N són totalment interiors a l'objecte). Els octtrees extesos d'altres de més complicats. Habitualment es necessita un límit que determina el nivell màxim de divisió (el dels grisos terminals) i  la precisió amb què quedaran representats els objectes. L'objecte es representa com un arbre que codifica el procés de subdivisió de l'espai, de forma que cada node de l'arbre es correspon univocament amb un cub de la subdivisió espaial. A partir de la posició d'un node a l'arbre podem inferir el tamany del cub associat i la seva posició a l'espai.
Exemple d'octree extès:

	Partim del cub univers  El subdividim en 8 nodes (octants)      .     .     . recursivament fins que dins del node hi ha una part prou senzilla de l'objecte original

El mateix concepte és vàlid per a dues dimensions, és a dir per a quadtrees que modelitzen polígons:

Quadtree Extès	Quadtree Clàssic

Característiques del model:

• No ambigu (fixats uns eixos i un cub univers)
• Hi ha octrees extesos als quals no correspon cap objecte vàlid.
• Unicitat, fixats uns eixos de referencia i un cub univers. Cal mantenir l'octtree compactat (un node gris no pot tenir tots els fills blancs, per exemple).
• Domini de representació: Permet representar qualsevol objecte de forma aproximada. En el cas dels octtrees extesos, el domini són els poliedres. També permet modelitzar l'interior dels sòlids (serveix com a model de volum).
• Considerable espai de memòria, depenent del tipus de nodes terminals que s'admetin, però pot ser bo per a representar objectes de forma molt complexa. En tot cas, si es considera com a model de volum, segur que ocupa menys espai que una voxelització.

Operacions i interrogacions sobre el model:

• Transformacions geomètriques: molt costoses!
• Classificació punt-sòlid: senzilla i molt ràpida (aprofitant la divisió espacial).
• Classificació recta-sòlid: tampoc gens costosa i ràpida.
• Càlculs de volums, etc: senzills, però aproximats en els octrees clàssics. Permeten fer aproximacions ràpidament.
• Operacions booleanes: bastant senzilles i ràpides (aprofitant la divisió espacial); tant sols cal saber operar dos tipus de nodes fulla qualssevol.
• Edició (construcció): algorísmicament, partint d'una representació en algun altre model.
• Visualització: es pot utilitzar un mètode ad hoc que aprofiti l'ordenació espacial que proporciona (algorisme del pintor) o fer ray-casting aprofitant la rapidesa del test d'intersecció amb una recta, però visualitzar-los aprofitant un z-buffer és senzill perquè només cal saber visualitzar els diferents tipus de node fulla. Admeten la gran majoria de tècniques de visualització pròpies dels models de volum (mètodes projectius i mètodes de traçat de raig) i n'acceleren alguns d'ells.

Habitualment s'utilitza com a model auxiliar per aprofitar la localització espacial. Per exemple, per accelerar les operacions booleanes entre B-Reps. En aquest cas, cada node terminal podria contenir informació de les cares i arestes contingudes dins del seu cub associat, per tal de poder accelerar els tests cara-aresta.