Goodbye Quadtrees for terrain rendering - new algorithm!
Author
EVS Flood-Fill Algorithm for terrains
I’ve been trying to implement a terrain engine for a while now. One of the most frustrating parts of it was figuring out whether to dynamically generate triangles at the highest level of detail or not. I was torn between the two options of generating them on the fly, or just rendering the height map as is. I decided to go with the latter.
Rendering height maps (without generating higher levels of detail) is all well and good until you want a really large terrain with a decent triangle density. Using standard quad tree culling still requires you to test a large number of AABB against the frustum. In a test, I tried to render a 8192x8192 height map using standard techniques. The frame rate immediately dropped to below 15fps based purely on the VDS calculations I was performing (AABB vs. Frustum via a quad tree). This wasn’t good enough for what I wanted. My end goal was to be able to throw any resolution height map at my engine and have it maintain the frame rate.
Before I go into detail, I use the term ClipMap to define a finite section of the terrain – in my engine, this are represented by 64x64 squares.
After much deliberation I figured out that I needed to select which ClipMaps I rendered based on the position of the viewer as opposed to taking the whole terrain into consideration like a quadtree. The solution as it turned out was simple. I utilised a flood fill algorithm starting with the ClipMap the camera is currently in. Assuming that each ClipMap (or any predefined area of terrain) holds a reference to the ClipMap to the North, South, East and West, we can do the following:
Function TestVisibility(Frustum fru)
IsVisible = true
If (frustum.intersects(North.bounds))
North.TestVisibility(fru)
If (frustum.intersects(East.bounds))
East.TestVisibility(fru)
If (frustum.intersects(South.bounds))
South.TestVisibility(fru)
If (frustumIntersects(West.bounds))
West.TestVisibility(fru)
The above function means that we are only testing the necessary ClipMaps. Simple!
As it turned out the actual implementation was a bit harder as the above code would go on for infinity. To counter this I simply passed a list in to the function containing each ClipMap already tested and then only tested those that were not already in the list. As an optimization addition, I also passed in another list and added only visible ClipMaps to it. This then gives you a list of all ClipMaps that need to be rendered.
Anyway, if this algorithm already exists, then sorry for wasting your time, if not then please use it (just remember the name of it!)
As far as performance goes, I managed to get back up to 60 frames per second with a 8192x8192 height map!
Anyway, post your comments and let me know what you think.
Cheers,
Chris
I've used this technique before with ok results. The problem I experienced was with geometry that extended past the bounds of a cell. Do you store it in a global cell that always gets rendered? Do you store multiple references to the geometry in each cell it overlaps and flag the geometry as rendered? Just some things to think about.
ClipMaps == geo mipmaps?
the problem with geo mipmaps is the steady data transfer across the bus, early graphic cards had an extension which is not available anymore
the larger the terrain the more bandwidth you need to transfer them
I think some ati beta drivers allowed for allocation of memory on the card directly to abuse this data as vertex data when rendering
have a look here, its german but maybe you find some english references
http://wwwcg.in.tum.de/Theses/Results/holler2005
the problem with geo mipmaps is the steady data transfer across the bus, early graphic cards had an extension which is not available anymore
the larger the terrain the more bandwidth you need to transfer them
I think some ati beta drivers allowed for allocation of memory on the card directly to abuse this data as vertex data when rendering
have a look here, its german but maybe you find some english references
http://wwwcg.in.tum.de/Theses/Results/holler2005
Square sections of terrain (often sized for rendering in a single draw call) are usually called patches, chunks or sectors etc... Clipmaps refers to a specific algorithm that's different from what you're doing.
The camera-centered selection of sectors to render is clever, and as you might've guessed has been used before. In fact it goes far back to the pre-history of 3D games (e.g. the 1990 racing game Stunts, and most likely even earlier games like Midwinter). More recently, the Dungeon Siege engine uses a closely related system with arbitrary-shaped sectors.
The camera-centered selection of sectors to render is clever, and as you might've guessed has been used before. In fact it goes far back to the pre-history of 3D games (e.g. the 1990 racing game Stunts, and most likely even earlier games like Midwinter). More recently, the Dungeon Siege engine uses a closely related system with arbitrary-shaped sectors.
That's an interesting technique. Off the top of my head it seems to me that there is a break-even point where a smaller frustum favors your technique and a larger frustum favors a quadtree. It would be interesting to figure out where that break-even point is.
Assuming the area inside the frustum is convex and you aren't doing occlusion culling, then you can avoid checking for duplicates by relying less on recursion and flood fill, and simply spanning the 4 quadrants (NE, NW, SE, SW).
BTW, don't use "clipmap". That term is already used for something else -- "clipmap" for textures and "geoclipmap" for terrain. A more standard term is "patch", or perhaps "block" or "chunk".
Assuming the area inside the frustum is convex and you aren't doing occlusion culling, then you can avoid checking for duplicates by relying less on recursion and flood fill, and simply spanning the 4 quadrants (NE, NW, SE, SW).
BTW, don't use "clipmap". That term is already used for something else -- "clipmap" for textures and "geoclipmap" for terrain. A more standard term is "patch", or perhaps "block" or "chunk".
This seems similar to what I did many years ago (my one and only heightmap renderer).
I projected the frustum points (used 5) onto the XZ plane (i.e removed y).
Took the convex hull of the 5 points, this is a quad or a triangle.
Then used a good old software rasterizer, and "rendered" the polygon to determine the potentially visible patches.
This is VERY fast and rejects most of the unseen patches.
Then for every potentially visible patch I tested the AABB against the frustum planes (could probably remove some planes).
I projected the frustum points (used 5) onto the XZ plane (i.e removed y).
Took the convex hull of the 5 points, this is a quad or a triangle.
Then used a good old software rasterizer, and "rendered" the polygon to determine the potentially visible patches.
This is VERY fast and rejects most of the unseen patches.
Then for every potentially visible patch I tested the AABB against the frustum planes (could probably remove some planes).
*giggle*
Checkout MCP-Fly, here (with source):
http://rainmak3r.altervista.org/voxel/download/index.htm
It was x2ftp.oulu.fi over 10 years ago and was based initially on the Magic Carpet renderer which preceeded it. Back in the software rendering days it was a pretty obvious technique that was used in amateur and commercial engines alike for many, many years.
Nice work on the technique... better luck next time ;)
Checkout MCP-Fly, here (with source):
http://rainmak3r.altervista.org/voxel/download/index.htm
It was x2ftp.oulu.fi over 10 years ago and was based initially on the Magic Carpet renderer which preceeded it. Back in the software rendering days it was a pretty obvious technique that was used in amateur and commercial engines alike for many, many years.
Nice work on the technique... better luck next time ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
