PART II: Terrain Rendering with a Scene Graph

In the previous post we discussed some of the issues of Terrain rendering and started to improve and evolve our Terrain rendering system. Part II kicks off right from where Part I left off and it might actually cover some scene graph stuff this time.

So we discovered that a constant number of visibility checks can still be a limiting factor. It's Quad tree to the rescue. Instead of just cutting the grid up into 256 even bits by going across and down 33 verticies we could actually be clever in the way we build the patches.

Starting from the highest level we could divide it into 4 equal child parts which would result in 4 patches that are 257 X 257 vertices. Four patches is not enough so lets divide each of these patches into four more child patches. Now we have 16 patches, still not enough but if we continue to divide down a few more levels eventually we reach 256 patches that we add as leaves to the quad tree. If we keep this dividing information in a tree (Quad Tree to be exact) we can make assumptions that can help us with our visibility issues. Note none of the higher level nodes contain any Terrain information, only the leaves of the Quad tree.

For example because each level of children exists completely inside the bounding volume of the parent by definition we then know that if the parent node fails the visibility test then so will all the children. So no need to bother testing their visibility. Worst case all 256 patches would be visible and we'd still do 341 visibility tests but on average we should achieve about 64 tests instead of original 256. A great improvement on the efficiency of our algorithm for no change in the visual experience of the user.

In the previous version of my Brainstorm game engine this was the complete extent of my Terrain rendering code and it has done the job quite well, however there are still a number of issues with this implementation that I think I can improve on. Specifically there is no handling of level of detail, there is still wasted effort when parent nodes are completely visible inside the viewing frustrum and Tree and Grass rendering don't take any advantage of the terrains Quad Tree, each of the systems uses their own quad tree visibility checking.

Keep an eye out for Part III of this series that will try and cover these issues in more detail.