Octree

Links: Recursieve opdeling van een kubus in achtsten. Rechts: De bijbehorende zoekboom.

Een octree is een zoekboom voor het zoeken in een driedimensionale ruimte. Elke knoop (Engels: node) in deze boom stelt een kubusvormig volume voor, die ofwel objecten bevat die zich in die kubus bevinden, ofwel weer acht kindernodes. Deze kindernodes samen bevatten dezelfde ruimte als de oudernode, dus als je weet dat het gebied dat de oudernode beslaat niet interessant is kan je vervolgens concluderen dat de kindernodes ook niet interessant zijn. Op deze manier kan je heel snel bepalen welke delen van een ruimte interessant zijn voor een bepaalde bewerking. Delen waar de bewerking toch geen invloed op heeft, kunnen buiten beschouwing worden gelaten.

De 2-dimensionale versie van een octree is een quadtree. Er is ook een binaire boom en een BSP-tree.