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

Started by
11 comments, last by _Silence_ 7 years, 6 months ago

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

Advertisement

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

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
{
};
usually: spatial partition / spatial hierarchy

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.

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{...};

Thanks all.

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.

RIP GameDev.net: launched 2 unusably-broken forum engines in as many years, and now has ceased operating as a forum at all, happy to remain naught but an advertising platform with an attached social media presense, headed by a staff who by their own admission have no idea what their userbase wants or expects.Here's to the good times; shame they exist in the past.

a couple possibilities:

https://en.wikipedia.org/wiki/R-tree

https://en.wikipedia.org/wiki/Directed_graph

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php



class Quadtree : public SPT
{
};
 
class Octree : public SPT
{
};

Why does that need to happen?

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

This topic is closed to new replies.

Advertisement