Octree

Un octree (del llatí oct "vuit", i l'anglès tree "arbre") es una estructura de dades de la informàtica. Un octree es 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 es 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 es possible, però no s'usa en la pràctica. Una versió generalitzada, on les dimensions no son determinades, son els arbres B.

Aplicació

Esquema d'un Octree. A l'esquerra la subdivisió dels volums en forma de cub, a la dreta l'Octree resultant

El següent exemple il·lustra l'aplicació més comú 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

Formes especials

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 te 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. Son per tant adequats per cerques eficients seguint el model dels arbres binaris. El subarbre de 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 de 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 es la densitat del material.

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Octree