Oktree

Et oktret (fra latin octo 'otte' og engelsk træ 'træ' ) er en datastruktur inden for datalogi . Et okter er et rodfæstet træ, hvis noder hver især har otte direkte efterkommere eller slet ingen efterkommere.

Oktre bruges hovedsageligt i computergrafik til hierarkisk at opdele tredimensionelle datasæt. Roden repræsenterer alle data, hver anden knude repræsenterer en oktant af dataene fra dens direkte forgænger. Dette gør dem velegnede til implementering af opdelings- og erobringsstrategien .

Octrees kan ses som udvidelser af binære træer og quadtrees : binære træer opdeler endimensionale data, quadtrees todimensionale og octrees tredimensionale; Lejlighedsvis kaldes en generalisering til enhver-dimensionelle data et N-træ . En anden mere generaliseret version, hvor dimensionerne ikke er faste, er B-træet .

brug

Ordning af et okter. Til venstre underinddelingen af ​​det kubeformede volumen, til højre den resulterende oktre.

Følgende eksempel illustrerer den mest almindelige anvendelse af et oktret, nemlig for den ensartede struktur af et terningformet datarum: Roden står for hele terningen. Terningen er opdelt i otte mindre terninger - oktanterne - og hver efterfølger til roden står for en af ​​dem. Hver af disse mindre terninger skæres til gengæld i otte endnu mindre terninger og så videre. Underinddelingen af ​​en delvis terning slutter, når ingen yderligere opdeling er mulig eller ikke nødvendig.

Det originale volumen behøver ikke at være terningformet, men kan også generelt være kubisk. Det er også muligt at opdele mængderne i ulige dele. Som regel gemmes yderligere oplysninger om de underordnede noder i noderne. Så indeholder z. For eksempel har hver node i den specielle min-max-oktree-form minimum og maksimum for følgende undertræ, hvilket muliggør effektive søgninger.

Yderligere anvendelsesområder

Generelle anvendelsesområder for okter er:

• Billedrepræsentation
• Rumlig indeksering (f.eks. I geografiske informationssystemer )
• Gruppering af partikler i molekylær dynamik / DEM -simuleringer
• Fjernelse af skjult overflade af terrændata
• Kollisionsdetektering i 3D computerspil
• Hierarkisk splatting
• Adaptiv løsning af differentialligninger, f.eks. B. deformerbare kroppe
• Statens skøn

Særlige former

Empty-Non-Empty-Octree

Enten gemmes værdien tom eller ikke-tom i hver knude i et tomt, ikke-tomt oktret . Tom angiver, at datavolumen, der repræsenteres af noden, ikke indeholder nogen data, der er værd at behandle; ikke-tom indikerer derfor, at den tilhørende datavolumen skal behandles. Normalt er tom også opsigelseskriteriet for underafdelingen; Da den tilhørende datavolumen ikke længere indeholder interessante oplysninger, er det heller ikke værd at opdele den yderligere.

Min-Max-Oktree

Ordning med et min-max-oktret. Hver node indeholder minimum (top) og maksimum (bund) af dens undertræ. Når man søger efter værdien 3, skal der kun søges i datavolumener for noder markeret med gult.

Minimumet og maksimumet for nodens subtræ lagres i et min-max-oktret i hver knude. Min-Max-Octrees er derfor velegnede til effektive søgninger baseret på eksemplet på binære træer. Subtræet i en knude søges kun, hvis den søgte værdi ligger mellem minimum og maksimum for noden. På denne måde kan dele af træet udelades, og søgningen kan fremskyndes.

I det særlige tilfælde, hvor minimum og maksimum er det samme i en knude, kan søgningen i undertræet også udelades, fordi hele undertræet i noden indeholder den værdi, du leder efter. Normalt er tilfældet med minimum lig med maksimum også afslutningskriteriet for underopdelingen, dvs. den tilhørende datavolumen er ikke yderligere opdelt.

For eksempel bruges min-max oktre i volumengrafik til at accelerere algoritmen for marcherende terninger . Her søges alle sub-terninger i oktret, der indeholder en given tærskelværdi. Denne tærskelværdi er en materialetæthed, for hvilken en isosurface skal ekstraheres fra voxeldataene.

Tensor felter

Fra et matematisk synspunkt er oktre særligt velegnede til strukturering af tensorfelter . Et voxel-gitter med grå værdier er for eksempel et nulordens tensorfelt som et skalarfelt , og et voxel-gitter med tre farveværdier i henhold til RGB-skemaet og en alfakomponent som et vektorfelt er en førsteordens tensorfelt.

Weblinks

Individuelle beviser

1. ↑ Martin Seiler et al., En tredobbelt repræsentation for den adaptive simulering af indlejrede deformerbare objekter i kontakt , Journal of WSCG, Pilsen, Tjekkiet, februar, 2010.
2. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13. International Conference on Information Fusion, Edinburgh, Storbritannien, juli, 2010. (PDF; 3,2 MB)