Jump to content
  • Advertisement
Sign in to follow this  
s3mt3x

Goodbye Quadtrees for terrain rendering - new algorithm!

This topic is 4149 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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".

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
*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 ;)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!