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.
 |
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
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.
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
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
Octree Buit-no-buit
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
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.
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Octree
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
