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

Additional considerations

A few points should be mentioned regarding the presented code and the algorithm in general

• The quadtree version of this algorithm as it was presented only culls the quadtree for left/right evaluation of FOV, no near, far, top or bottom planes are considered. Additionally only flat-(2D)-projection of the FOV is considered. Thus the algorithm (as it is presented in the code) only covers quadtree culling at quadtree height and viewing along the quadtree plane.

  Extending the code to traverse a 3D-quadtree (corner points form a cube, rather then a square) and applying the algorithm to process octrees removes these limitations - any viewing position and direction will be correctly processed.

• Several additional point / FOV considerations can be implemented, for example: if two corner points are infront of the FOV origin and on opposing sides of the FOV, then the quad is partially inside the FOV. For most scenarios the algorithm described yields very satisfactory results.

• The primary concern with the proposed algorithm is its memory requirement, though certainly not steep the memoization requires an additional byte (at most) for each possible quad corner point. Thus if a square region with n intervals per side is memoized, the memoization requires n² bytes. Though typically only a fraction of this memory is accessed for a given traversal, and the part that is accessed is likely to be accessed several times.

This concludes the presentation of the algorithm. I have found it a useful and effective approach - if you have any queries regarding the algorithm feel free to mail me and ask.

Bibliography