Here are some pictures from my landscaping engine. It uses Adaptive Subdivision to create a landscape approximation from ~2 million triangles. My Algorithm: I had 2 requirements for my landscape. It needed to have a structure that would support rendering via the "bleeding" method, and it needed to only provide detail where detail was necessary. Of course this all has to work in a limited resource environment. The result is that I need a quadtree, neighbor aware data structure. Each node of the quad tree is capable of being split into 4 children aranged in a grid. Each child is the same size, and placed together, occupy the same space as the parent. I start with a X by Y grid. My tree starts with one root node of size X-1 by Y-1. X and Y should each be a power of 2 + 1. For each step, I find the node with the greatest error. Error is the RMS difference between the plane a node occupies and the high resolution grid under it. That node is subsequently split. Very simple to implement. But there are problems with this method. Keeping track of neighbors needs to be done very carefully. There is also the issue of "tearing." Tearing occurs when 2 adjacent nodes aren't the same size. One node could be a better approximation of the underlying grid. This would mean that the 2 edges that the 2 nodes share won't be the same, creating a tear in your mesh. I use an algorithm that I call "stitching" to fix tears in a mesh. It works very well, and allows you to have a much greater freedom in your subdivision, rather than limiting the types of nodes that can abut.

Last updated on October 1st, 1998