PDA

View Full Version : Terrain



Rodrix
08-27-2006, 05:04 PM
Hi! :D

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 (http://www.gamedev.net/columns/hardcore/geomorph/)

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

Fitz
08-27-2006, 07:51 PM
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.

zeoverlord
08-28-2006, 07:27 AM
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.

Adrian
08-28-2006, 11:51 AM
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

holdeWaldfee
08-28-2006, 12:12 PM
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.

dorbie
08-28-2006, 02:34 PM
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.

ZbuffeR
08-28-2006, 04:06 PM
Carmack is spectacularly wrong on this one for a whole range of problemsno, 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 embellishmentsFractal detail, ruling terrain rendering since 1983 :)
http://accad.osu.edu/~waynec/history/tree/images/pages/genesis1_jpeg.htm
http://www.complang.tuwien.ac.at/alex/Pics/Fractal-Mountain-3.jpeg

zeoverlord
08-28-2006, 04:51 PM
Originally posted by Adrian:
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.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.

Adrian
08-28-2006, 06:20 PM
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.

ZbuffeR
08-29-2006, 01:37 AM
the map is much smaller but the performance characteristics and benefit from lod are the sameNot 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.

Zulfiqar Malik
08-29-2006, 02:29 AM
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 :( and lack of texturing algorithm.
I have since then made modifications to the texturing algorithm and am targetting SIGGRAPH/Eurographics next year :) .

Zulfiqar Malik
08-29-2006, 03:54 AM
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 :) ).

knackered
08-29-2006, 05:06 AM
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.

Jan
08-29-2006, 07:07 AM
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.

knackered
08-29-2006, 10:13 AM
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.

Zulfiqar Malik
08-29-2006, 01:02 PM
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 :) .

Adrian
08-29-2006, 01:58 PM
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.

Jan
08-29-2006, 02:58 PM
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.

Zulfiqar Malik
08-29-2006, 09:06 PM
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 :) . 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.

Adrian
08-29-2006, 10:55 PM
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?

Zulfiqar Malik
08-29-2006, 11:17 PM
@Adrian: There is no demo right now but will be soon. Yes the LOD is not very noticable i know, but still, of the little popping artifacts, geomorphing would get rid of those too and it'll only cost a couple of instructions in the vertex shader.

@Jan: I finally found what you were talking about. The algorithm that uses a stitching scheme similar to this is "Real-time Terrain Rendering using Smooth Hardware Optimized Level of Detail" By "Bent Dalgaard Larsen and Niels Jørgen Christensen" of "Technical University of Denmark" (i think its available at http://www.vterrain.org/LOD/Papers/).
In simple words, no my stiching scheme is different. Their stiching scheme although greatly resembling the one that i use, is different in every sense. They change LOD and handle stitching specially at runtime, and the way they do it is different as well. So essentially they are not the same techniques although the final result resembles a lot but its not at all the same algorithm. Please read the paper in detail. In comparison you can read this paper as well and find things out for yourself.
A few other algorithms that use a similar approach (with a similar end result) BUT ARE NOT THE SAME are listed below:

1. http://www.gamasutra.com/features/20000228/ulrich_01.htm
2. http://www.flipcode.com/tutorials/tut_geomipmaps.shtml
3. http://www.ics.uci.edu/~pajarola/publications.html#vis98
4. http://www.imm.dtu.dk/pubdb/personal/sho...html&order=year (http://www.imm.dtu.dk/pubdb/personal/showbasket.php?cmd=full_view&id=53&title=Publications&header=&footer=&css=&f=1&b=1&e=1&year=&fmt=html&order=year)
5. http://stereofx.org/#Papers

The bottom line being that there is a certain desired output in such rendering algorithms and just because the output is the same doesn't mean that the path chosen is the same.

zed
08-29-2006, 11:58 PM
http://i24.photobucket.com/albums/c26/zzeek/landscape_LOD_wire.jpg

:)

might as well throw my implentation into the works as well, iirc i was creating an infinite landscape, where u could walk in any direction for ever. all terrain was generated on the fly, no slowdowns, since each frame a small piece is generated

now who else?

btw ive starting to get my game together see zedzeek.com

knackered
08-30-2006, 02:09 AM
believe me I've tried everything.

game's looking really good zed. Pity it's linux only, really limits your audience unnecessarily.

zed
08-30-2006, 02:16 AM
"Pity it's linux only,"

check the readme

knackered
08-30-2006, 03:01 AM
right, windows now, great.
so why don't you have a download link on your page?
I will never email you, you can be sure of that.

Rodrix
08-31-2006, 11:04 PM
Thanks guys for all the feedback! :D

The best one I was able to -try- yet, was the link I first posted on GeoMorphing with the Vertex Shader.
Terrain looks great and perfomance is 10 points. However it's in DirectX. :confused:
Geomorphing in Vertex Shader (http://www.gamedev.net/columns/hardcore/geomorph/) It dates 2003. Fairly new compared to most articles on this topic.

Anyone has a link to a complete tutorial (with source code) on GeoMorphing with Shader on OpenGL? Or any other LOD you mentioned? :)

Thanks so much!!!

Fitz
09-01-2006, 01:21 AM
One thing about that GeoMorphing article I noticed is it seems to lack dynamic lighting, at least in the article you posted. You could probably just add this by storing the normals in the texture instead of the lightmap they mentioned.

Rodrix
09-01-2006, 10:22 AM
That's a great idea!
But when the terrain changes shape because of the terrain 'mipmapping' or 'geomorphing', won't normals change too? So you won't be able to store the normals unless you have a static terrain???

CrazyButcher
09-02-2006, 03:44 AM
the point is to keep "normals" consistent, so that lighting is consistent even when the mipmapping kicks in, hence use of texture data which is not so much distorted on lower tessalation is recommended

Rodrix
09-02-2006, 10:11 AM
OH great! So you mean keep only a texture data of normals for only the highest levels of details (more detailed ones), and then just use the same normals for the low level of detail patches, right?

So maintaining the same normals even though you have you have less vertexes on less levels of details makes the mipmapping more unnoticiable?

THanks so much

Rodrix
09-12-2006, 09:22 PM
I am just reading John Carmacks' Interview
http://www.gamerwithin.com/?view=article&article=1319&cat=2

He says:

Level of detail wise, the terrain does not render with any sophisticated geometry morphing situation. That’s one of those things that for years I think most of the research that’s gone into has been wasted. Geometry level of detail on terrain…there have been thousands of papers written about it, and I honestly don’t think it’s all that important. The way the hardware works, you’re so much better off setting down a static mesh that’s all in vertex and index buffers, and just letting the hardware plow through it, rather than going through and having the CPU attempt to do some really clever cross blended interpolation of vertices.As Adrian shortly mentioned too.

He says that he used that for Doom 3. :eek:

Also he mentions about MegaTexturing. He uses a 32000x32000 texture for the static terrain (no geometry LOD he says).

Does he load the 32000x32000 texture by chunks, using some kind of texture LOD? That would mean a 50mb texture with a decent quality 20:1 compression (JPEG) if I my calculator didn't fail this time... :)
which is possible...

He mentioned he uses Index Buffers...
Any ideas?

Filip Strugar
09-14-2006, 09:25 AM
You can check out my terrain_middleware_under_development (shameless advertisment ;) ).
It prebuilds adaptive tesselated mesh LOD layers, and just streams them at run-time. It's got smooth LOD, streaming, collision detection, low CPU and moderate memory usage and - excellent framerate.
Heightmaps up to 32k x 32k are supported in current beta. Overlay texture can be of any (reasonable) size.
SDK can be downloaded, tried and used for free for non-commercial purposes.
Also, there are demo binaries, screenshots and few videos.

It can at least give you an idea or benchmark for the techniques used!

oh, yes, the link is: www.advantageterrain.com (http://www.advantageterrain.com) :)