Terrain

Hi! :smiley:

I googled the whole internet for the latest terrain rendering and LOD terrain technicsā€¦
The latest I found was from 2003, Terrain Geo-Morphing:
GeoMorphing Terrain

I also found a very similar technique released in 2000 called ā€œMipmapped Terrainā€, making an analogy of their LOD with the functioning of OpenGl Mipmap textures.

What is the last trend -today-?

I am looking for a realistic terrain with high performanceā€¦

Thanks so much in advance,
Cheers,
Rod

From what I understand Chunked LOD and geometry clipmaps seem popular.

Chunked LOD website(http://tulrich.com/geekstuff/chunklod.html), you can find hard to read source code and demos if you search this page.

Clipmaps website(http://research.microsoft.com/~hoppe/), if you scroll down to demos there is a GPU clipmap demo which requires an Nvidia.

Geometry clipmaps can be done on the GPU, unfortunatly vertex textures are still quite slow and not supported by ATIā€“I tried this and found using VTF dropped the fps by almost 50%.
There is also geometry clipmaps on the cpu, although they require recalculating the index buffer each frame unless you can figure out some trick to avoid it.

ChunkedLOD as originally implemented uses a quadtree structure on pre-processed independent meshes paging them in from disk. It seems to perform pretty good.

John Carmack said in his 2005 keynote speetch that the brute force ( = no lod ) method combined with good culling is probably equally as fast as any other lod method, not to mention simpler and have less problems.
I do agree with him on that, everything i have seen in games like WoW suggest that is the case.

Originally posted by zeoverlord:
John Carmack said in his 2005 keynote speetch that the brute force ( = no lod ) method combined with good culling is probably equally as fast as any other lod method, not to mention simpler and have less problems.
I do agree with him on that, everything i have seen in games like WoW suggest that is the case.

I strongly disagree with him on that.

In my engine with LOD on the frame rate is 45 fps and the rendered triangle count is 1.3 Million. With LOD off the triangle count is 10 Million and the fps is 7.

You can try if for yourself here.
http://www.mars3d.com/EarthExplorer/PWEarthExplorer.htm

It totally depends on what kind of application you create.
Most games (low range of view, low freedom of movement) have scenes where you donā€™t need any terrain LODs at all and can do simple portal/occluder culling.

It really depends on what you have in mind, sometimes these differences in opinion arise from people considering problems of differing scope.

Carmack is spectacularly wrong on this one for a whole range of problems if youā€™re representing his views accurately. But heā€™s a smart guy and probably had something else in mind, for example a viewpoint very low, lots of dynamic self shadowing and maybe texture & shader based detail (he has some uber virtual texture paging stuff heā€™s working on) and perhaps other limits in mind like constraints on size.

Instead of googling this run Google Earth, a picture speaks a thousand words. Tell me you can make that work using brute force and culling.

At some point weā€™ll see texture based terrain displacement with the basis for this being a multi-resolution image map & then you have a hybrid between the Tanner SGI CLIP map and Hoppe Microsoft clip terrain. Then with subdivision shaders you can perhaps start to do smarter things in the tesselation stage (with preprocessed cues?).

In there somewhere is augmenting the available terrain information with detailed but unmodelled embellishments.

Carmack is spectacularly wrong on this one for a whole range of problems
no, he specifically excluded whole-planet-like terrains, and said brute-force was possible because in their case the game maps have a limited total surface.

augmenting the available terrain information with detailed but unmodelled embellishments
Fractal detail, ruling terrain rendering since 1983 :slight_smile:
http://accad.osu.edu/~waynec/history/tree/images/pages/genesis1_jpeg.htm
http://www.complang.tuwien.ac.at/alex/Pics/Fractal-Mountain-3.jpeg

Originally posted by Adrian:
[b] I strongly disagree with him on that.

In my engine with LOD on the frame rate is 45 fps and the rendered triangle count is 1.3 Million. With LOD off the triangle count is 10 Million and the fps is 7.[/b]
True at that polycount lod is better, however, i do think itā€™s possible to use a low poly mesh and just blend between the two, at a certain distance.

However the raw poly pushing speed increases way faster than CPU speed does, so in 2-3 years brute force will be way faster at those polycounts.

Originally posted by ZbuffeR:
no, he specifically excluded whole-planet-like terrains, and said brute-force was possible because in their case the game maps have a limited total surface.
Map size isnt important with regards to LOD. I could reduce the scale so the terrain resolution would go from 10 meters to 1 meter and view distance would go from 20km to 2km. So the map is much smaller but the performance characteristics and benefit from lod are the same as before.

the map is much smaller but the performance characteristics and benefit from lod are the same
Not quite. Going from 100ms to 10ms is not the same as going from 10ms to 1ms, unless you only do terrain. The gain is hidden by other bottlenecks where it is better to optimize. And there is lod on moving entities.

Well, i developed a terrain rendering algorithm named GIST (Indexed Geometry Sets for Terrains). I have written a formal paper on the mesh rendering part and am working on writing a texturing part as well (for huge textures). I will be uploading the paper on our website soon. The paper was originally aimed for Eurographics 2006 but narrowly got rejected because of ā€¦ ahem ā€¦ errr ā€¦ inappropriate English :frowning: and lack of texturing algorithm.
I have since then made modifications to the texturing algorithm and am targetting SIGGRAPH/Eurographics next year :slight_smile: .

Well the paper that was originally posted to Eurographics 2006, is available at:

http://www.itrango.com/downloads/GIST.zip

Screenshots at:

http://www.itrango.com/downloads/GIST_Screenshots.zip

A public implementation will be made available soon. Please read the license.txt file in GIST.zip (it just says you cannot mis-represent the origins of the algorithm, you can use it for anything u want :slight_smile: ).

quickly skimming the pdf leaves me thinking thereā€™s nothing new in there. Itā€™s just a standard chunked lod scheme.
But obviously I must be missing something, so please clarify the differences between your approach and geomipmapping/chunkedlod.

Ha! I implemented just that half a year ago!

Itā€™s nearly 1:1 the same, except that you use 5 Triangles to stitch nearby LODs together, i only used 3 (the two long triangles are not necessary, i think).

The rest is absolutely identical: patches, precalculated LOD index-buffers, etc. etc.

But sorry, man, thatā€™s all not new:
The stitching-pattern is called ā€œinterlocking tilesā€ or so, and was presented in one of the Game Programming Gems Books (1 or 2 i think).

Using a precalculated index-buffer is IMO a straight-forward addition.

Also, take a look at the Far Cry Editor, you will see, that they use this technique for their terrain-rendering.

And another straight-forward addition: Use Occlusion Queries to cull occluded patches. I implemented that too, after i noticed, that Far Cry does it also.

Anyway, this is, IMO the best solution for terrain-rendering in real-time games. It is certainly not the best thing for scientific stuff, but because it has such a low overhad, it is really great for games.

Jan.

thereā€™s no need to be so enthusiastic in your destruction of zulfigarā€™s work, jan.
If thereā€™s something more to it zulfigar, please tell us.

Well its definitely no where near TUrlichā€™s chunked LOD which selectively refines the mesh. Just because it uses patches does mean its the same thing. Boerā€™s geomipmapping is a very different technique and i do not know how it can be confused with a patched scheme.

There are a few new things in it:

  1. The way the vertex buffer is organized i.e. each successive LOD level just has the new vertices appended with the previous levels. No vertices are repeated. That means dropping or adding a level is very fast and easy. That also means lesser memory requirements. Read the introductory section on calculating vertex and index buffers. This is something not even clipmap does. Although this is not particularly useful with 1 big vertex buffer it is when there is patch specific (per-vertex unique) data that needs to be sent to the pipeline. In my paper i send normals but in my future work section i mention that normals can be calculated entirely within the vertex shader (along with smooth geomorphing) but even then you have to send height map specific data per-vertex where the unique vertex buffer arragement helps in minimizing changes.

  2. One of the biggest problems with patch based approch is that there is a lot of overdraw. In almost all fixed patch sized algorithms this was a problem and no proper solution was given to address the issue. The unique way in which the vertex buffer is arranged in this algorithm makes each LOD level a complete ā€œrecursiveā€ quad-tree which gives room for quad-sub-trees which are used for minimizing overdraw. Quad-sub-trees are rendered in one draw call and their size is dynamically adjustable. I have also noticed that different hardwares have different optimal batch size. Apart from minimizing draw calls, quad-sub-trees can be used to optimally select the proper draw call size no matter what the actual patch size is.

  3. The stitching algorithm. I did not know that this had been done before and i do not even know whether what jan says is the same as my approach. Is there a link jan? (None of the Eurographics reviewers mentioned it to me as well. I am sure they must be aware of the technique. They were generally optimistic about the mesh renderer but were not pleased with the absence of a texturing algorithm to go with it). One thing that i can clarify is that like patches, edge LODs are calculated at load time and are very very fast.

  4. The unique way in which vertex buffer is organized has opened up avenue new texturing algorithm for me as well. I am currently in the process of implementing it and initial results are very positive. Infact the texturing algorithm is EXACTLY the same as the mesh rendering algorithm. Something, that gives a good edge to other algorithms like clipmaps.

  5. Hierarchical occlusion culling. This is not something even an advanced algorithm such as clipmaps can do.

  6. Its very very easy to implement in comparison to other algorithms. When i implemented the algorithm a year or so ago, from the point of conception to a fully optimized implementation took 8 working days!!! In comparison i initallly implemented the ROAM2 algorithm and it took me more than 3 weeks for a decently optimized implementation. And btw, it gives better fill-rate than any algorithm that i know of and i know there is still room for improvement. Although i do agree that an apples to apples comparison is not possible but the results are very positive.

Basically its based on existing approaches (and thatā€™s probably all the similarilty) but adds quite a few optimizations and refinements to existing techniques. Just like the billion quad tree based algorithms out there does not make them similar to the original quad tree algorithm :slight_smile: .

Originally posted by ZbuffeR:
Going from 100ms to 10ms is not the same as going from 10ms to 1ms, unless you only do terrain.
The example I gave wouldnā€™t reduce render time at all, I think you misread my post or perhaps Iā€™m misunderstanding yours.

Originally posted by Jan:
It is certainly not the best thing for scientific stuff, but because it has such a low overhad, it is really great for games.
Why is it not great for scientifc stuff?

Zulfiqar, why do you want to implement geomorphing. When youā€™re pushing more than half a million triangles per frame popping is barely visible. As triangle rates go up it will become even less of an issue. I dont see any need for geomorphing these days.

Originally posted by knackered:
thereā€™s no need to be so enthusiastic in your destruction of zulfigarā€™s work, jan.

Sorry, it wasnā€™t meant to sound that way.

About the stitching: I donā€™t know of any link. As i said, itā€™s in Game Programming Gems 1, 2 or 4 thatā€™s for sure. However, i donā€™t have access to my books right now, so i canā€™t be more specific.

After i started working on it, i bought Far Cry and downloaded the SDK. With it comes their editor, and in wireframe you can clearly see, that they use the exact same method as described in the book, with a patch-size depending on the maps size (on a typical map, the patch size is 64*64 vertices).

I think that it is not a good approach for ā€œscientificā€ cases (depending on your definition of ā€œscientificā€), because it is meant to be a low-overhead, realtime-capable LOD approach. To actually make it realtime and reduce calculation overhead to a minimum you need to live with one disadvantage: heavy popping.

No matter how you tweak your parameters to make it less obvious, your terrain will still pop when the LOD changes on a patch, and it WILL be visible and noticable. Though, for a game it might be acceptable.

However, in a ā€œscientificā€ scenario, you will most certainly want to have a LOD method, that also minimizes the differences between LOD levels.
And there are plenty of other methods, that do just that and are therefore better in such cases.

But as i said, for games, i have not been able to find any other method that comes even close to this one. And as a prove of concept, take a look at Far Cry.

Jan.

I donā€™t think FarCry uses a patched scheme. When i did some research on FarCry i noticed that their algorithm to be a selective refinement approach like ROAM/ROAM2. However i cannot say anything with certainty as i do not have access to code.
As for geomorphing, well there are popping artifacts on LOD change because there is a limit to the number of vertices you can use (dependent on heightmap resolution) without having geometry aliasing artifacts. Geomorphing will be simple and effective in minimizing those and there will be very little overhead in the vertex shader.
@Jan: You see with GIST your quad-trees can be of fixed size but you can change your batch size by changing quad-sub-trees (defined in the paper). So in essense you can say that the ā€œrendered patch sizeā€ is dynamic in GIST. 64x64 sized patch is definitely not the most optimal.
I will have a look at the interlocking tiles algorithm that you suggested. In the meantime you can have a detailed read.

In my post above i confused geomipmapping with geomorphing :slight_smile: . Sorry.
So basically its a mix of things with the partitioning being a quad-tree style approach with some elements of geomipmapping. But it builds a lot on them.

Originally posted by Jan:
No matter how you tweak your parameters to make it less obvious, your terrain will still pop when the LOD changes on a patch, and it WILL be visible and noticable. Though, for a game it might be acceptable.
Neither of you can have tried the demo I posted above. I am using a very similar method to you and Zulfiqar in terms of stitched patches with varying LOD. Iā€™ve been using the same method for the last 6 years. The popping is barely noticeable.

Do you have a demo to download Zulfiqar?