Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
64 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:


 Printable version
 Discuss this article
 in the forums


Traditionally computer graphic applications - particularly applications requiring real-time, interactive display - have approached graphic problems by determining a best possible subset of graphic data that needs to be send through the graphics pipeline, rather then processing an entire data set. Quadtrees, octrees, BSP-trees, back-face culling, potential visibility sets and many other methods were developed for this purpose.

Modern computer graphic hardware has in recent years grown exponentially in processing power and functionality. The current state of affairs indicates that it is in many cases preferable and faster to find a good data set quickly and send it to the graphics pipeline, rather then finding a best data set elaborately. Such a good data set is an approximation to a best data set and can often be found with more efficient and elegant (if less accurate) algorithms. The task at hand is thus to review existing techniques and algorithms in an attempt to find faster alternatives that are not burdened with finding the best solution possible.

In this article a heuristic approach to quadtree and octree culling is described, that is both easy to understand and easy to implement, yet still delivers very satisfactory results. I will focus on quadtrees for the remainder of the article, but the technique applies equally well to octrees.

Next : Quadtrees