Contents  Introduction  Quadtrees  Additional  considerations  Printable version  Discuss this article  in the forums

Introduction

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