Octree
 |
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
Un octree (del llatí oct "vuit", i l'anglès tree "arbre") és una estructura de dades de la informàtica. Un octree és un arbre arrelat, els nodes del qual o bé tenen com a màxim vuit successors, o bé no en tenen cap. Els octrees s'empren principalment als gràfics per computador, per subdividir jeràrquicament conjunts de dades tridimensionals. L'arrel representa el conjunt de totes les dates, i cada un dels altres nodes representa un octau de les dades del seu predecessor. Per tant, aquest és adequat per a aplicar estratègies de dividir i vèncer.
Octrees pot considerar com una extensió d'arbres binaris i quadtree: els arbres binaris divideixen dades unidimensionals, els quadtrees bidimensionals, i els octrees tridimensionals; una ampliació a dades N-Dimensionals és possible, però no s'usa en la pràctica. Una versió generalitzada, on les dimensions no són determinades, són els arbres B.
Aplicació
[modifica]
El següent exemple il·lustra l'aplicació més comuna d'un octrees, això és, la subdivisió uniforme d'un conjunt de dades amb forma de cub: l'arrel representa tot el cub. El cub està dividit en vuit cubs més petits - els octants - i qualsevol successor de l'arrel és d'un d'ells. Cada un d'aquests cubs més petits és al seu torn dividit en vuit cubs més petits i així successivament. El desglossament d'un sub-cub acaba quan un divisió major no és possible o necessària.
El volum original no ha de ser un cub, però generalment pot ser rectangulars. També és possible una subdivisió del volum en peces de mida diferent. Com a regla general, s'emmagatzemen en els nodes d'informació addicional sobre els nodes secundaris. Així, per exemple, al Min-Max-Octree cada node de l'expressió específica el mínim i el màxim dels següents sub-arbres, que permet cerques eficaces.
Altres aplicacions
[modifica]Les aplicacions generals per octrees són:
- Representació d'imatges
- Indexació espacial (per exemple, Sistemes d'Informació Geogràfica)
- Agrupació de partícules en la dinàmica molecular / simulacions de marcs alemanys
- Eliminació de cares ocultes de les dades del terreny
- Detecció de col·lisions en els jocs 3D
- Splatting Jeràrquic
Formes especials
[modifica]Octree Buit-no-buit
[modifica]En un Octree Buit-no-buit, s'emmagatzema a cada node el valor buit o no-buit. Buit significa que el node no conté dades de valor que hagin de ser processades, mentre que no-buit especifica que les dades que conté s'han de processar. Buit sol ser, al mateix temps, el criteri per a la terminació de les subdivisions, ja que si el corresponent tros de dades no té informació interessant, no val la pena seguir amb la subdivisió.
Min-Max-Octree
[modifica]En un Min-Max-Octree, a cada node s'emmagatzema el mínim i el màxim dels sub-arbres. Són, per tant, adequats per a cerques eficients seguint el model dels arbres binaris. El subarbre d'un node serà cercat, quan el valor cercat estigui entre en mínim i el màxim del node. Així es pot estalviar cercar a determinats nodes de l'arbre, accelerant la cerca.
En casos especials, on el mínim i el màxim d'un node siguin iguals, la cerca en sub-arbres pot esser estalviada de la mateixa manera, ja que als sub-arbres només es troba el valor que especifiquen el mínim i màxim. Aquest cas sol ser també el criteri d'aturada del procés de subdivisió.
Els Min-Max-Octrees s'empren per exemple en l'acceleració de l'algorisme dels "Marching cubes" als gràfics amb volum. Es cerquen tots els sub-cubs de l'Octree, als que s'inclou un valor límit. Aquest llindar és la densitat del material.
