Octree
Van Wikipedia
Een octree is een zoekboom voor het zoeken in een 3-dimensionale ruimte. Elke node in deze boom stelt een kubusvormig volume voor, die of objecten bevat die zich in die kubus bevinden, of weer acht kindernodes. Deze kindernodes samen bevatten dezelfde ruimte als de oudernode, dus als je weet dat het gebied dewelke 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 binary tree en een BSP-tree.
