• 9
• 9
• 11
• 13
• 9

# What is the general name for types like Quadtrees and Octrees etc

This topic is 553 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What is the canonical name for these types of geometrical types?

I mean what are they called in general?

Because I want to make a superclass that encapsulates some of the attributes

They are in common sometimes.

Thanks

Jack

##### Share on other sites

Quadtrees, Octrees, BSP Trees, etc. are commonly known as 'Spatial Partitioning' or 'Spatial Subdivision' methods.

##### Share on other sites

Yes, is there a technical name for these types?

Or they are just called BSP in general?

Or SPT - for spatial partitioning tree whatever

class Quadtree : public SPT
{
};

class Octree : public SPT
{
};

Edited by lucky6969b

##### Share on other sites

Or they are just called BSP in general?

BSP is a special kind, just like Octree and Quadtree are. Liguria already said what they're called in general. BSP (Binary Space Partioning Tree) is a special variety that uses two  child-nodes per subdivision, while Quadtrees splits each node into four (usually equally sized) subquadrants.

##### Share on other sites

Quadtrees and octrees are not BSP. BSP stands for Binary Space Partitioning. Quadtrees and octrees are not binaries.

They all are spatial partitioning structures as said by another poster.

What you might do is something like this:

class SpacePartition{...};
class BSP: public SpacePartition{...};


Thanks all.

##### Share on other sites

Know that there is also Kd-trees. It's like BSP, but you don't store a vector-per-split; you just store a magnitude. Each split's axis is determined from its depth in the tree, modulo the number of dimensions, e.g. the root node splits on the X axis, the next level splits on the Y axes of the two X parts, the next level splits on the Z axes of the four Y parts, and the next level splits on X again. Ideally you want to split an equal number of elements to either side of each split.

The main advantages over BSP as a spatial search structure (as opposed to BSP's main uses in the 90s as a spatial *traversal* structure) is that the tree is easier to build, and there's no vector math involved to test which side of a split a point or object is on, only axis-aligned-bounds checks.

##### Share on other sites

class Quadtree : public SPT
{
};

class Octree : public SPT
{
};


Why does that need to happen?

##### Share on other sites

Know that there is also Kd-trees. It's like BSP, but you don't store a vector-per-split; you just store a magnitude. Each split's axis is determined from its depth in the tree, modulo the number of dimensions, e.g. the root node splits on the X axis, the next level splits on the Y axes of the two X parts, the next level splits on the Z axes of the four Y parts, and the next level splits on X again. Ideally you want to split an equal number of elements to either side of each split.

The main advantages over BSP as a spatial search structure (as opposed to BSP's main uses in the 90s as a spatial *traversal* structure) is that the tree is easier to build, and there's no vector math involved to test which side of a split a point or object is on, only axis-aligned-bounds checks.

BSPs and KDtrees are very different entities with different uses.

They are like comparing Tomatoes and Oranges, while both are edible fruits, one would be used for salad and other for desert.

BSP: Very hard to create, Even harder to modify, but many unperformant edge cases of KD trees are avoided. A BSP's nodes are partitioned more efficently because they do not have to be aligined to anything. Costly creation times mean that BSPs are usually pre-calculated and not so good for moving objects like physics. But they are very efficient for things that don't move like scenery and such.

KDTrees - Are very easy to create and modify. As such they are excellent for physics.

It is worth mentioning that KD trees can be a little bit slower than octrees and quadtrees, but on the other hand they have the shortest and simplest code.