Category Archives: Spatial Data Structure

Uniform Grid

This is maybe the easiest way to manage the objects in a scene and is also often a very good choice. It’s a simple uniform grid with equally sized cells/buckets/patches (or whatever you want to call it). When rendering, all that is needed for culling is to check the view frustum against these cells to determine which ones are visible. This grid can most of the time be in only 2D but can of course in special cases be 3D if necessary. This spatial data structure works well with both static and dynamic objects.

A Uniform Grid
Some information of traversing a grid structure

Quadtree

Nearly the same as a Octree but instead of dividing the space in cuboids in 3D it’s rectangles in 2D space. This is useful for rendering terrain and you want to cull a lot of the terrain fast.

Example of the creation of a quadtree

A visual demonstration of a quadtree used for fast collision detection:
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

Introduction to quadtrees and sample code:
http://www.gamedev.net/reference/programming/features/quadtrees/

More info about quadtrees, including source:
http://www.kyleschouviller.com/wsuxna/quadtree-source-included/

Octree

Octrees are one of many ways to divide the space into smaller volumes structured in a tree. This is useful for culling objects while rendering or for finding collisions between objects. First cover the entire space that is of important into one big cuboid. Then the dividing algorithm for the tree goes as follows:

- First select the maximum number of objects in each cuboid. This determines how deep the tree will go.

- For each cuboid that contains more objects than the maximum allowed, split it into eight (oct = eight) new cuboids with the same volume and dimensions. Repeat this step until all cuboids fulfill the requirement.

The procedure looks like the following:

Octree creation process

More information about octrees.
http://www.gamasutra.com/features/19970801/octree.htm

Source of the image:
http://en.wikipedia.org/wiki/Octree

A little description of octrees.
http://www.flipcode.com/archives/Introduction_To_Octrees.shtml