Quadtrees and Octrees
Quadtrees and Octrees
Written by Mike James   
Tuesday, 30 June 2015

If you do any advanced work in graphics, sooner or later you will meet the Quadtree or its 3D relation the Octree. For this reason alone they are worth knowing about, but they are also something you should have in your armory of data structures.

 

The Quadtree and its three-dimensional brother the Octree are two fundamental data types that are well worth knowing about.

They have lots of applications but the reason I am writing about them now is that I've been working on a number of implementations of graphics algorithms that need both data structures. In particular I've been working on custom color reduction.

However, the theory of these two data structures is well worth knowing even if color reduction isn’t something that interests you. Also, for reasons that I’m not at all sure of, both the quadtree and the octree are often ignored or forgotten when they could be really useful. 

The Quadtree

It makes sense to start with the quadtree because it is simpler to explain – and draw!

A quadtree derives from the idea of dividing a square area into smaller squares. This connection with squares and refinement also determines where it tends to be useful, i.e. in 2D search or optimisation algorithms.

Start with a unit square as the root of the tree. Now divide the square into four smaller squares.

Each of the new smaller squares is a child node of the root.

The next step is to repeat the process on the small squares generating four more sub-squares and hence four children at the next level of the tree for each of them.

 

Division

As you move down the quadtree each square is divided into four smaller squares.

 

At first it can be difficult to see the tree for the squares but the diagrams should help.

 

You can see how the tree idea fits into the picture a little better by drawing lines showing the children of each node. If you concentrate on the black lines you can see that they form a branching tree structure with four branches at each level.

 

Tree3D

 

We can make the view of the tree more abstract and closer to the data structure we use to represent it by flattening the tree part of the diagram into a 2D tree diagram.

 

Tree2DThe most abstract view emphasises the tree, but remember where the squares come from.

 

You can now see that a quadtree isn't really very special as a data structure - its just a tree where each node has four child nodes.

The key idea however is that each child node represents a subdivision of the square that its parent node represents. Most of the work in implementing a quadtree goes into representing and implementing the division of the geometry rather than in building a sophisticated data structure.

There are other potential complications that you can encounter in practice. For example, it is usually the case that a quadtree is built up dynamically as the data becomes available. In this case the division of a square at one level may become necessary before some or any of the others have been divided. The result is an unbalanced quadtree the covers some areas more finely than others.

This might seem like a complication but it has big advantages in that the 2D area is covered only as finely as is necessary.  

Fast sorting

OK so now you understand the quadtree – what use is it?

The answer is that the different levels of the tree provide different resolutions of detail and this can be useful in many different ways. 

For example, if you have a two-dimensional data point, x,y, then this will fall in exactly one node at each level of the tree.

You can use this fact to perform a fast search of a data set.

First sort the data into a quadtree and then when you want to see if a particular data value x,y is present you simply move down the tree via the correct node at each level until you reach the bottom and find the point or discover it isn’t present.

This is the two-dimensional equivalent of the binary search algorithm used to search a one-dimensional list.

Such algorithms have some surprising applications for example if you want to make Conway's Game of Life (The Meaning of Life ) go faster then use a quadtree.

You can also use the same technique as a method of data compression. For example if you divide  up a map using a quadtree then you can give every house a compressed location according to the right or left branches needed to reach it. For example, 2312 would mean the house that you find when you start at the root, got down branch 2, then 3 then 1 and finally 2.  

The Octree

Once you have understood the quadtree, the octree is almost obvious.

In three dimensions the square is replaced by a cube and the division into four is replaced by a division into eight sub-cubes – hence oct–tree, since oct = eight.

 

cubesAn octree division divides each cube into eight sub-cubes.

 

Thus the octree is just a generalisation of the quadtree to 3D.

Each node corresponds to a single cube and has exactly eight sub-nodes.

Notice that all of the sub-node cubes are contained within the parent cube. As in the case of the quadtree, the octree can be used to find a data point, but this time a three-dimensional point, very quickly.

As before you can flatten out the octree and draw it as a standard tree structure.

 

2DOct

 

The octree branches very rapidly and it doesn’t take very many levels to generate lots of nodes but apart from this implementing it as a data structure isn't difficult. What tends to be difficult is managing the geometry needed to divide the cubes and store the details at each node.

As in the case of the quadtree the octree is often built up dynamically as data become available. In this case dynamic construction often results in an unbalanced tree with areas of space being covered more finely than others.

As already mentioned octrees are useful when you have to search a 3D space. In particular they are often used in efficient collision detection but they also occur in algorithms that work in more abstract 3D space. For example the color space is generally considered to be 3D with dimensions Red, Green and Blue. Hence yo can use an octree to organise a the use of color by an image and perform color reduction or quantization.  

 

Related reading

The Meaning of Life       

An Algorithmic Challenge       

Donald Knuth's Christmas Tree Lecture      

Javascript data structures - the binary tree      

Data Structures Part I - From Data To Objects

Data Structures Part II - Stacks And Trees       

Data structures - Trees

 

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.

 

Banner


Amazon Web Services Adds API Gateway
17/07/2015

Amazon has announced new developer tools and services aimed at making it easier to develop APIs.



TypeScript 1.5 Released
24/07/2015

TypeScript 1.5 has been released and the developers say it’s a big one. 


More News

 

blog comments powered by Disqus

 

<ASIN:0521106974>

<ASIN:0201853922>

<ASIN:3838329201>

<ASIN:1420053361>

<ASIN:1558607323>

<ASIN:0262062178>

Last Updated ( Tuesday, 30 June 2015 )
 
 
Banner

   
RSS feed of all content
I Programmer - full contents
Copyright © 2015 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.