GPU Pro 5

3. Quadtrees on the GPU 449

3.5 Conclusion

We have presented a novel implementation for quadtrees running completely on

the GPU. It takes advantage of linear trees to alleviate the recursive nature of

common tree implementations, offering a simple and efficient data structure for

parallel processors. While this work focuses on quadtrees, this representation

can also be used for higher dimensional trees, such as octrees. Using the same

distance-based criterion, the Tr a n s vo x e l algorithm [Lengyel 10] could be employed

to produce a crack-free volume extractor, running entirely on the GPU. We expect

such an implementation to be extremely fast as well. ...