Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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{...};
class Quadtree: public SpacePartition{...};

Share this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!