Jump to content
  • Advertisement
Sign in to follow this  

Terrain algorithms

This topic is 3827 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

Hi everybody, I have a question about Terrain rendering, more specifically LOD algorithms. I've been inspired by the Infinity Engine (featured in the Dev Journals) by Ysaneya to create a better terrain engine than the one I currently have. However, I've read his forums and he mentions Quadtrees, Geomipmapping and Clip mapping. So I googled these in turn and I found several SIGGRAPH papers, but they are all dated around 1999, give or take a few years. I even read a paper on gamasutra about ROAM (which I realise is old) which had references to the Elite game (from roughly 15 years ago). Do people still use these references? Should I be reading and trying to implement these methods from these papers? Could you please give me some views and opinions about the different LOD methods? At the minute I have no particular goals, although the only thing I don't want to do is have to pre-compile terrain information is seperate files ( I read this on some Chunked LOD sites), so procedurally generated terrain would be good, and I'd like large view distances :) Thanks for your help. -Lintford

Share this post

Link to post
Share on other sites
People do still use quadtrees, ROAM and the like but that doesn't mean they should [wink]

Y'see, back the '99 timeframe we were just seeing the first generation T&L hardware and the pipeline was still fairly stacked in the CPU's favour. Over the last 8 years the pipeline has got deeper and moved more and more towards the GPU hardware.

A basic concept is that you want as little CPU intervention as possible - treat the GPU as a parallel co-processor and don't try to micromanage it. It reaches its peak when you give it nice big chunks of work to do.

Algorithms like quadtrees and ROAM tend to increase the draw call count (typically with lots of small, or increasingly small, batches that perfectly fit the view frustum) which breaks the aforementioned micromanagement rule. ROAM and the like go one step further and rely on regularly manipulating and changing the raw data being rendered, which is A Bad Thing™ with the current architectures.

So whilst these algorithms do still reduce the amount of genuine work the GPU has to do they typically increase the synchronization and stalling involved - so the net result is actually no faster as you're just wasting valuable cycles doing nothing useful [headshake].

All that said, you can still use aspects of these algorithms. I personally like quadtrees just clamped to the N=3 to N=6 depths (or thereabouts) and not a full tree.

If you can get hold of a copy of Game Programming Gems 2 then Greg Snooks Interlocked terrain tiles article is worth a read. I've found that to be a very good trade-off for performance and LOD.


Share this post

Link to post
Share on other sites
Thanks for your help Mr. J. Jeffers.

OK, I thinking I'm leaning in the Geo-mip mapping direction, however this leads me to a couple more questions, as was inevitable.

I've currently got a quadtree terrain, with no LOD. Would you recommend trying to incorporate Geo-mip mapping directly into my quadtree (is this even possible)? or would it be better doing it again from scratch?

Also, I have found a paper on Geo-mip mapping by willem de boar, should / could I use this as a reference, or is there a better paper/implementation - or would this be a waste of time?

[Edit] - I have something else to add :( - Could somebody describe the relationship between the quadtree and the geomipmapped mesh. My current implementation (quadtree) analyses the heightmap at the start, then creates nodes - starting from the entire terrain, and creating children, until each node is of a certain, small size - and then all calculations are performed on these 'child nodes' (culling etc.)

But I undersand geomipmmaping to be almost the opposite - you create a mesh for the highest level (global) level of terrain, then when the camera gets closer to the terrain, you create 4 more meshes as children etc. etc.

How can you have both a quadtree and use geomip mapping ?

Thanks again for the help :)

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!