We just enhanced our terrain system and the results were so good I thought I would share the technique with the list. With this technique you can dynamically increase or decrease terrain quality to match hardware capability and you can render textured seamless meshes representing miles of terrain. This actually improved our framerates while increasing the quality of the rendered terrain. I have not tested this yet on lower end hardware, but I had a test case last night showing 32kilometers of terrain, 5 km of trees, sky, etc at 110 fps on a Geforce 4.
I have been corresponding with Thatcher Ulrich, who published an article on adaptive quad trees in Gamasutra (http://www.gamasutra.com/features/20000228/ulrich_01.htm). The idea which I had was to combine our scenegraph optimized terrain paging system with the adaptive nature of his algorithm. As with most OpenGL algorithms, his code was built to recalculate the terrain on every single frame, and there is no capability to intelligently texture the terrain (short of draping some huge big texture over the whole thing). Our previous system was described to the java3d list in the e-mail entitled "RE: ROAM and GPU Usage". So to recap our static system, we keep a quad tree in memory. Leaf nodes in the quad tree have a corresponding BranchGroup which hold the shape of a patch (texture and geometry). Up to now we have been building the patches offline and then pages them in as needed. With this new technique we build the geometry for the patches dynamically, but still load the textures from an offline source. The technique has three pieces: Heightfield management, geometry construction and rendering. 1. Heightfield management. Thatcher's adaptive trees have the ability to hold both sparse and detailed heightmap infomation within the same tree. So it is possible to store data at 128m resolution for the whole map, and then lay down 16m data for another portion of the map. His algorithm can also bilinearly interpolate between heightnodes to produce nice data on demand. To change an arbitrary terrain dataset into something usable by Thatcher's algorithms we needed to have a sample size which is a power of 2. So we wrote a converter which takes heightmaps and builds bezier splines to represent the terrain. We then query the splines for any x,z value and get a fairly accurate resampling which preserves terrain details which we would have lost had we linearly interpolated. We can then cull static data from the tree. Thatcher can scan the tree and remove "irrelevent" height samples to reduce memory usage. We have been seeing about 40 percent reduction of memory using this. 2. Thatcher's algorithm works in two passes. The first pass adjusts the quadtree according to a detail parameter and the location of the view. This will enable and disable quads and vertices throughout the tree very rapidly. It is then possible to query the tree for the triangles which are needed to render. It does this by starting at the top and examining the quad. Each quad has up to 9 vertices. Each quad is divided up into a maximum of 4 quadrants, but if the quadrant is disabled then it is rendered using 2 triangles, otherwise that quad is rendered with up to 8 triangles. His article explains this in detail, so I will not explain that more. The nice thing about the algorithm is that it is possible to render a part of the tree as long as it is power-of-two aligned. 3. You could of course render the terrain by building one big geometry array with all the triangles generated by Thatcher's algorithm, but that has two problems. You would have to cull FoV by triangles or else you would be sending lots of terrain to the card every frame that could not even see. You could not use display lists because the terrain would change on every frame. The next problem is texturing. At a minimum you want a 2:1 texel-meter texture ratio + multi texturing for a nice look. That would require something like a 16k x 16k texture to place over a 32k x 32k terrain. We texture Magicosm at 1:1 texel-meter ratio + detail multi-texturing. So in our system the LodTree has a quad tree of LodNodes. The construction of this tree mirrors the scenegraph. We start out with LodNode representing the top of the tree, and then there are 4 children representing quadrants. We have rules determining how close you can be to a certain lod level before it is forced to subdivide. After you move a few meters we re-check these bounding spheres against the bouning boxes of the patches. If they intersect then we sub-divide. After it is determined that it should not divide any more it loads in the texture for that patch/level from a paging file. Now in the past we would also load the geometry from the file, attach the texture and then put it into a shape3d and add to the scene (in transactions of course to maintain integrity). So we made a small change to incorporate adaptive quadtrees. We created a QuadNode class which extends branchgroup. We extended Thatcher's system by creating something called a QuadRenderer, which are targets for rendering triangles into. Each QuadRenderer holds the bounds that should be rendered for and some data buffers. It also has a single public method called render(). When you ask the adaptive quad tree to render you pass it a QuadRenderer class. It uses the bounds as it traverses the tree until it finds the parent quad which exactly matches the bounds in the QuadRenderer class. When each quad is rendered it is costructed in a maximum of 8 triangles using 9 vertices. So the vertices are "rendered" into a vertex array in the QuadRenderer and then the triangles are defined using indexes into the vertices. Once each quad has "rendered" its triangles the render() method of the QuadRenderer is called to process them. In our QuadNode we created an inner class extending QuadRenderer and overrode the render() method. The QuadNode uses a GeomContainer to hold the geometry for the patch. GeomContainers are our standard dynamic geometry containers which can render using by-reference, NIO buffers, Interlaced, etc. It has a standard interface and it contains a GeometryArray. When you construct it you have to give it a class implementing GeomUpdateInterface. So we have the QuadNode implement this interface and create a GeomContainer inside the node to hold the geometry. When the QuadNode.update() is called, it calls the GeomContainer.update() which in-turn calls the updateData() method on the geometry array, which in turn calls the updateGeom method of the class implementing the GeomUpdateInterface, which in this case is the QuadNode. This method can now saftly update the geometry. It does this by calling passing the QuadRenderer into Thatcher's quadtree. As each render() call is made against the innerclass QuadRenderer, it examines the triangles in the buffers and transfers them into GeomContainer. It also calculates texture coordinates and vertex colors if needed. 4. So each LodNode patch becomes a dynamically updatable mesh with no gaps or seams. If the tree is rebuilt to change the larger Lod levels then the new patches are re-rendered into new QuadNodes to perfectly match their sibling and cousin quads. In addition, we are recalculting the QuadNodes every few steps by calling QuadTree.update(view,detail) and then updating each active QuadNode. This update uses the same texture since it is not a rebalancing of the tree, just a tweaking of the mesh. So since Thatcher's algorithm uses a view dependent reduction mechanism, as we move around the detail right around us is improved. It is even possible to add procedural mesh detail at the local level so that you have transient geometry showing cracks or bumps, but with no overhead to the heightmap. The advantages of this technique are manyfold. By placing each patch into shape3d nodes you get FoV culling for free on patches. In addition with isFrequent(false) for geometry updates you can even get your quads to be pushed to display lists. Each patch can get its own texture which means you can have effectively LOD texturing across all the levels. With just a few improvements you could even recycle QuadNode's so that we never have to remove them from the scene, just update them or make them invisible... a more efficient operation than removing a branchgroup. David Yazel =========================================================================== To unsubscribe, send email to [EMAIL PROTECTED] and include in the body of the message "signoff JAVA3D-INTEREST". For general help, send email to [EMAIL PROTECTED] and include in the body of the message "help".
