Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Terrain Rendering Techinques Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
howbizarre

March 21, 2005, 05:08 AM

Hi !

I am doing research work on the various Terrain based techniques being used in the state of the art games. Apparently the two most widely used techniques are ROAM and QUADTree for Continuous LOD. But unfortunately I have not come across a single comparsion of the two techniques. So I was wondering if some one can specify the pros and cons of the two technqiues or point some other better technique.

Regards,
Hussain

 
Gerald Knizia (cgk)

March 21, 2005, 06:42 AM

...various Terrain based techniques being used in the state of the art games. Apparently the two most widely used techniques are ROAM and QUADTree for Continuous LOD.

Do you know _any_ game that uses ROAM? I don't...
To the quadtrees: are you sure that this has anything to do with LOD? I know quadtrees only as a (simple) spacial subdivision scheme used for example to do view frustum culling. Or is "QUAD" some kind of acronym in your notion?

 
howbizarre

March 21, 2005, 07:19 AM

By Quadtree I meant Quadtree based terrain triangulation. For further information on the technique try following paper by Renato Pajarola:

www.ics.uci.edu/~pajarola/pub/UCI-ICS-02-01.pdf

Regards,
Hussain

 
Dark_Nebula

March 21, 2005, 09:17 AM

From what I have read, I conclude that the two most common method used in games are Chunked lod and GeoMipMapping. Personaly, I have only implemented the latter so I can't really comment on how they compare against each other, or to ROAM. But it seems to me that these two are better suited for implementations where you make good use of the hardware. With ROAM you put a lot of work on the CPU.

Also, there is a lot of buzz right now about Hugues Hoppe's Gemoetry Climpmaps. Defenetly worth to take a look at!

 
Wernaeh

March 21, 2005, 09:41 AM

Seumas McNally's Treadmarks used it ;) Feel free to google it up if you like ;o)

Cheers,
- Wernaeh

 
Wernaeh

March 21, 2005, 09:54 AM

Hi there ;)

I guess which algorithm is better suited also depends on the desired scale of your terrain.

For example, for just smaller viewing distances (think small case fps, like the Unreal 2 engine titles), it is often sufficient to just brute force the terrain (and fog and cull a little bit), and rather use the remaining throughput to make the detail around the viewer as great as possible (texture splatting, adding lots of grass, etc).

In contrary, larger viewing distances (MMPORG games, RPGs), where you need the increased view for orientation and still want much detail close up, need a fast lod which still provides as much detail as possible. Yet, the algorithm does in most cases not need to adapt to a camera high above the terrain. This is where geomipmapping and others come in handy (see all AquaNox titles).

Roam finally is mostly used in games where you need both great viewing distances, and not so much detail close up (and probably anyways have spare CPU time). This is mostly flight simulator terrain. In most cases you'll probably have the player high up in the air, where you need enormous viewing distances to stay realistic. However, you also need at least some detail up close (say your going in low to stay below enemy radar), which gives you a really big range of numbers to cope with. AFAIK, geomipmapping does not deal with such situations too well, I haven't tried it though ;).

Geometry Clipmaps finally seem to solve all these problems by just using sheer vertex and pixel throughput. I am currently experimenting with them a little bit and they look really promising. The only problem I see with these up to now is that they're more CPU intensive than just brute forcing, especially for a "fast" camera, because more of the clipmaps has to be rebuilt each frame.

Cheers,
- Wernaeh

 
howbizarre

March 22, 2005, 12:48 AM

Wow Wernaeh
That was awesome description. Thank you so much. I will definitely look into the details of GeoMipMapping, Geometry Clipmaps and Roam2.
Regards,
Hussain

 
theAntiELVIS

March 22, 2005, 02:53 AM

Yeah, if you're viewpoint is down on the ground (first person shooter style) definitely check into geomipmapping - it can even be done in vertex shaders (check-out ShaderX books).

Combined with geomorphing the technique can be very subtle - almost unnoticeable. And if you place it within a "quadtree/octree" type structure, you can really pack-on details like trees, grass, rocks, whatever.

ROAM seems to be losing favor out there now that hardware and shader technology has upped the performance level available for terrain rendering.

You also might want to Google on "adaptive quadtrees" for info on this form of continuous LOD - a variant to geomipmapping.

 
knackered

March 22, 2005, 07:29 AM

about geoclipmaps:
Have you come to terms with the fact that, even though you update only the L region of the vertex buffer you have to upload the entire vertex buffer each update time...because a vertex buffer is 1 dimensional?

 
sylvan

March 22, 2005, 08:59 AM

I haven't implemented this, but how about you upload all the vertices at the highest LOD and then have an index buffer with the various LOD indices. You'd need a five dimensional array to find the correct IB, where the first index is the LOD of the current patch, and the four following is the LOD of the neighbours.
So you precompute all the LODs and stitching.

Then each frame you wouldn't have to upload any vertices assuming all the visible vertex buffers fit in memory. And you won't even have to update the IBs.

 
theAntiELVIS

March 22, 2005, 06:10 PM

There are ways to use LOW LOD meshes and then generate intermediate vertices to get higher LOD - saving a lot of bandwidth and allowing very large terrains.

Here's an example:


http://www.gamasutra.com/features/20000228/ulrich_03.htm

I think he is pre-calculating here - but with current hardware it should be feasable to calculate new vertices to create smaller quads on-the-fly.

 
Max

March 22, 2005, 06:44 PM

Wouldn't you just write the vertices directly into AGP memory?

Max

 
knackered

March 24, 2005, 04:53 PM

I always assumed that the card dma's the 'dirty' region of the vertex buffer (specified in the 'lock') from agp to video memory when you are about to render with the buffer bound. Don't think it would be very efficient for it to dma a vertex at a time. So, dynamic vertex buffers reside in agp memory until you render with them, at which point they are copied into a temporary area of video memory before being transformed, lit and used.
The dirty region for an L region in clipmaps would effectively be the entire vertex buffer if you think about it.
Maybe I'm wrong.

 
theAntiELVIS

March 26, 2005, 06:49 AM

It would. The link I presented isn't a clipmap solution, though. But the presented algo relies on the LOD areas being fairly small squares of quads. So you are effectively batching whole squares, each in its own buffer. The technique would not allow a single large vertex buffer for the entire in-scene terrain. So like clipmaps, the "dirty region" would be an entire buffer, as you say. But it isn't being "dirtied" every frame.

The way to go would be to use data stored outside the vbuffer and use a set of vbuffers for the currently visible scene. Whenever the viewpoint crosses a square boundary from one square to another we then recalc and fill the scene buffers. So the lock/unlock cycle only happens then. As long as the viewpoint is inside a square we would be working with "static" LOD, and then doing geomorphing in the standard way (and through a vertex shader).

So the idea is you "precalc" the LOD levels up on crossing a boundary, and have all the levels for the scene area. As boundaries are crossed you only need calc LOD up for the new squares that enter the scene, and discard them for the squares that go "out" (down to low LOD). For the vast majority of the world you only have low LOD squares in memory, and offline in mass storage. This requires additional data in flags for each low LOD vertex, but not nearly as much compared with keeping full high LOD data around all the time.

If transformations could be used on the squares you wouldn't even have to do any copying of existing squares when a boundary is crossed, and instead just keep a "map array" of which square is where in the scene. This might introduce some accuracy errors with positioning, though. Depends on how big the visible scene area is.

Another approach would be to store a medium LOD dataset, and calc both higher and lower LOD squares - but then you must maintain more data, most of which is not being used at any given time.

 
knackered

April 13, 2005, 06:29 AM

Sorry, posted this in as a reply to the wrong post.
Here it is again in the correct place!
"
I always assumed that the card dma's the 'dirty' region of the vertex buffer (specified in the 'lock') from agp to video memory when you are about to render with the buffer bound. Don't think it would be very efficient for it to dma a vertex at a time. So, dynamic vertex buffers reside in agp memory until you render with them, at which point they are copied into a temporary area of video memory before being transformed, lit and used.
The dirty region for an L region in clipmaps would effectively be the entire vertex buffer if you think about it.
Maybe I'm wrong.
"

 
raissel

April 14, 2005, 03:43 PM

hello, if you are researching about terrain rendering, we have the same purpose:, I have a good book for that, "Premier - Focus On 3D Terrain Programming - fly", if you don't have it, look in http://free.gameres.com, you can download it free. If you find or have the sorce code of the books examples, please tell me, I need it, or tell me about well books.
Thanksfully
Raissel

 
arex

April 17, 2005, 07:08 AM

If you'r doing LOD and you really want fast one, here is one suggestion:

- Terrain is based on blocks, for example 32x32 (quads)
- You create n versions of block (where the n is amount of lods)
- Then you just switch the buffers to change lod

And basicly this doesn't even need stitching. :)

Check my terrain rendering (block based):
www.DawnBringer.cjb.net

 
Wernaeh

April 17, 2005, 08:41 AM

How comes it does not need stitching ?

Do you always keep the vertices on the block borders for all lod levels ?

Cheers,
- Wernaeh

 
publicENEMY

April 19, 2005, 01:25 AM

just my 2 cents

terrain technique
1. rendering pipeline acceleration - where you simplified the terrain for limiting polygon thoughout(geometric LOD based method) - where you load all terrain data into memory, then simplified it for rendering

2. data driven - where you manage terrain data to load/process before rendering - usually with extremely large datasets where loading terrain data into memory would be impossible - real world implementation usually coupled this with geometric LOD

1. rendering pipeline acceleration - geometric LOD
1.1 ROAM
1.2 stefan roetger
1.3 peter lindstorm
1.4 diamond based roam
1.5 clipmaps
1.6 geomipmaps(author implementation)

good
minimal coherence between real data (best method - roam, see derek bradley analytical comparison)
nice for small terrain
some of the technique implement geomorph for unnoticeable terrain lod transition

bad
eats lots of cpu resources
loads all data into memory

2. data driven
2.1 tree - octree, uniform grid
2.2 chunklod
2.3 PVS(potentially visibility sets)
2.4 visibility culling
2.4.1 frustum
2.4.2 occlusion
2.4.3 backface
2.5 geomipmaps(possible implementation)

good
for extremely large datasets(out of core)
non cpu intensive
possible paralell processing(chunklod already implements threading)

bad
stiching problem
hard to geomorph

i know there is a lots of mistakes here. correct me if im wrong.

 
Greg Hermann

April 21, 2005, 04:05 PM

What's interesting to me is that Lindstrom's 'SOAR' is never mentioned. Has great throughput, code is available and is extraordinarily simple (requires no complicated mesh management like with roam), has several research papers associated with it. It even has a lot of guarantees which cover the stitching issues. Best of all, it doesn't just throw a lot of geometry at the card in the hopes that it can handle it.

Throwing static geometry demos well, but I'm just not sure it scales as well. Average PC someone buys - Really fast CPU, crap-all graphics card. Probably a built-in intel graphics card or something similar -- Using some small CPU percentage for terrain calculations isn't a bad thing. If you feel your graphics card is being underutilized, use a more complicated shader (I kind of like the steep parallax mapping for grass and whatnot). But you can have multiple paths for shaders which scale with the graphics card.

 
Greg Hermann

April 21, 2005, 05:10 PM

Apologies to publicENEMY, he did mention soar in 1.3.

As far as texturing goes, this is what I'm currently considering:
32 x 32 patches.

Terrain textures A, B, C. Tile U and V for A, B, and C.
Normal maps for A, B, C (optional for bumpmapping / parallax bumps / specular)

Blend and shadow map for the patch. (16 or 32 bit) I may need to break these up for optional fixed-function pipeline.

Use the blend map to know how much of A, B and C to mix together. Use the Alpha component of the blend map as the shadow component for the patch. (darken, and provide no specular).

As far as creating holes in terrain, I'm currently planning on a separate quadtree-like 'split' for each patch, and artifically inflating the error metrics of the verts at the edges of the 32 x 32 patch so it can match up with a 16 x 16 patch (or smaller) until I can just reach the point where patches can just be left out of the mesh.

This looks like more or less what WoW is using, and I'm in-progress on an editing tool which lets me create these blend maps. Ideally, everything will be done in photoshop or paint shop pro with real-time visualization of edits.

 
theAntiELVIS

April 22, 2005, 04:36 PM

Lately I've been testing different LOD implementations (ROAM, chunks, stitched sectors, etc.) and to my surprise simple brute force (NO LOD) gives me the best performance. Admittedly my system is relatively powerful (3.2 GHz Intel, ATI 9800 PRO), but I see approx. 3 to 10 times the raw rendering speed of the fastest LOD system.

I imagined this would change using using lower spec hardware - but on my 1.7 GHz/ATI 9200 I see the same thing. And on my laptop with an old NVIDIA card.

Go figure....

 
AdrianL

April 23, 2005, 02:19 AM

When you say performance, do you mean tris/sec or frames/sec. With simple tiled LOD I get lower tris/sec but much higher frames/sec than without LOD.

 
theAntiELVIS

April 23, 2005, 03:19 AM

Yeah - it's raw FPS. When you are measuring your tris/sec are you just timing the throughput per-tile? What's your tile size in quads? Mine is 1:1 - a single quad. I was amazed to get nearly 1000 FPS treating each quad as a unique material surface (although I am batching by texture to minimize setting texture stages).

Using the various LOD methods and rendering just the terrain (always the same number of quads at highest LOD) I saw FPS as low as 90-100.

 
AdrianL

April 23, 2005, 03:31 AM

I'm measuring tris/sec for the whole terrain. My tile size is 128x128 quads.

I get something like 60MTris/sec @ 85fps with LOD and 95MTris/sec @ 7fps without. I'm just using one texture for the whole terrain at the moment.

 
Wernaeh

April 23, 2005, 05:06 AM

I am not sure whether comparing MTris/Sec or Fps really is a good way to compare terrain rendering techniques.

This is mainly due to the fact that these measurements do not take representation quality into account.

F.e. 1000 tris in a terrain still may "look" much better than 10000 tris if they are placed right - that is, shiluettes facing the viewer are highly tesselated and surfaces facing the viewer are not.

I guess this is one of the points where LOD algos outperform brute force for large terrains.

Brute force terrain rendering is O(n ^ 2) triangles, where n is the viewing distance. Additionally, if you push the viewing distance out far enough, many of these tris will be very small, and consequently add less to overall detail than more tris right in front of the viewer.

LOD on the other hand usually cuts down to around O(n) triangles, but both O(n) on the GPU and the CPU. Also the tris are distributed more equally - smaller tris in front, where detail is required, larger tris far outside, where the distance anyways makes them appear smaller.

Just remember the time when everybody still was writing roam algorithms. Some implementations even took the screen space distortion of triangle shilouettes into account, so that they used up a couple more cpu cycles, but had their few tris just where it counts. This probably looked better than simply having all the few tris spread about the terrain.

Today, one can fill the entire screen with pixel sized tris without any fps problems. Yet, rendering the same pixel over and over again, because far out tris are subpixel sized, still might prove to be a problem with brute force rendering. I guess that's why the clipmap LOD might be useful these days - since it guarantees pixel sized tris over the entire terrain.

That's of course only given enough time to implement one. Brute forcing still is much easier to do - especially on a tight schedule.

Cheers,
- Wernaeh

 
Dr. Necessiter

April 23, 2005, 07:37 AM

FWIW: I use a "chunked" style system with a few modifications. I have very large, paged terrains so in my application, most of the terrain is drawn at the lowest LOD. This is good for flight sims, really large worlds, etc.

- I keep lowest-res LOD of the entire terrain mesh on the board all the time. Most chunks are drawn at the lowest res, so this is always available - and it doesn't take up too much memory.

- For everything but the lowest res, I upload the highest res of a chunk and use pre computed index buffers to draw/stitch it at the desired LOD. That's lots of permutations of index buffers, but it's really not much memory.

- I cache the high res vertex buffers so if you spin your view around, they will be available and won't need to be uploaded again. This can do wonders depending on the application.

- Right now, I draw all the lowest-res chunks using individual calls, but I think I'm going to try creating a lowest-res LOD index buffer as needed when the LODs change. This way, all the lowest-res chunks can be drawn with a single call. This will probably cut the draw calls by 70%, I'm guessing. I really don't want to spend more than 100 draw calls on the terrain.

As you can see by reading, this is all designed to cut down on bus traffic as much as possible, which tends to be the bottleneck with terrain systems. This is also why people see such good performance with brute-force. However, it is impractical to brute-force large terrains... too much memory.

 
theAntiELVIS

April 23, 2005, 08:00 PM

My goal is to move as much to the GPU as possible. Except for sorting by texture (which only has to be done when/if new textures are introduced) the no-LOD brute force method is just about as close as 100% GPU as I can get.

So it's fill-rate we're after here. There are no objects on my terrain, and I am blending a maximum of three textures per-quad (which actually looks very good treating each quad as an independent surface). My terrain isn't all that big: 512x512 vertices (so 511x511 quads).

At the moment I'm not even using a shader - just pushing lit vertices through the fixed pipeline. So the performance is very good (FPS-wise, which is of course a somewhat bogus measurement being non-linear). I'm using no occlusion culling, but am using frustum culling.

Really the point is that fill-rate on an up-to-date card is so immense that LOD becomes irrelevant as far as rendering quads goes. When things like transparent textures, impostors/models, and especially water and sky effects get added, raw fill-rate will become less of a factor. But it seems viable to only consider LOD as it relates to model objects ON the terrain, and ignore it for the terrain itself (perhaps only using occlusion culling).

 
theAntiELVIS

April 23, 2005, 08:03 PM

>>it is impractical to brute-force large terrains

 
This thread contains 29 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.