PDA

View Full Version : Terrain Optimization...



zix99
08-12-2003, 06:52 AM
Hi all

I was wondering what some different methods of optimaztion could be used in drawing terrain. All i have heard of is Tesselation, and a method where the farther out the poly is, the bigger it gets, thus reducing the poly count. The second methos i said works very nicly, but when i do per-vertex lighting it starts looking very bad.

Thank you for any ideas and suggestions
Zix

p.s. i am using very large terrain (2000x2000) to (4000x4000) units

Machiavelli
08-12-2003, 08:21 AM
Visit Google.com with the search phrase 'ROAM'

Good luck.

JustHanging
08-12-2003, 08:35 AM
Don't use per-vertex lighting...

-Ilkka

Ostsol
08-12-2003, 08:49 AM
I agree on the per vertex lighting, thingy. Set all the vertex normals to face straight up and use a normal map, just like if you were doing bump-mapping on a flat surface.

EDIT: In my own terrain renderer it was even worse since I was using per-vertex colouring instead of using a colour map. http://www.opengl.org/discussion_boards/ubb/smile.gif Hehehe. . .

[This message has been edited by Ostsol (edited 08-12-2003).]

bunny
08-12-2003, 08:49 AM
Geomipmapping is better suited to current hardware than ROAM. Google will reveal more.

JanHH
08-12-2003, 09:03 AM
what's wrong with per-vertex lighting?

Ostsol
08-12-2003, 09:20 AM
Originally posted by JanHH:
what's wrong with per-vertex lighting?
When you bring the terrain down to a lower polygon count you have less vertices to work with. As a result, you lose alot of the finer detail in the shading (in addition to the loss of polygon detail). By using a normal map, the only detail you really lose in in the terrain's sillouette -- and a good tesselation algorithm can minimize that, anyway.

Obli
08-12-2003, 09:52 AM
Originally posted by bunny:
Geomipmapping is better suited to current hardware than ROAM. Google will reveal more.

I am not really sure of that (reading about Geomipmapping right now). I agree that there are algorithms avaiable which works nicely when "small enough" terrains are getting rendered but here zix is using a 4000x4000. I am also doing a large terrain renderer and most algorithms around the net does not feel attractive (my crash test is 12000x8000).
Now, the terrain map itself is, for zix 4000x4000 = 15.2MB if he's using 8bit samples. Expand that to a 16bit only and 30MB are gone away (for height only). Add eventual GeoMipMaps and stuff like that. I feel there is the need to manage memory very effectively here.

I must thank you anyway for the hint provided about geomipmapping. I am very interested on that topic. I'll keep an eye on it (reading a paper right now).

Adrian
08-12-2003, 10:44 AM
I would recommend what I think is being called,'chunked LOD'. I presume it's not the same as geomipmapping or is it?

Basically break your terrain up into chunks e.g. 128x128, then calculate the LOD based on distance from the viewer.

You can use a cacheing system to only store the vertex array data for visible chunks of vertices. You only need to regenerate the vertex data when a chunk becomes visible or changes LOD. This keeps memory/cpu usage low.

This is imo the fastest,most memory effecient way of rendering terrain on modern hardware.

This screenshot shows a wireframe view of chunked LOD terrain with a 4kx4k dataset. http://www.adrian.lark.btinternet.co.uk/MarsExWF.JPG

Edit: Image updated to show newer version of the software running at 51MPolys/sec. With fog off it runs at 82MPolys/sec on a GF5900u)

[This message has been edited by Adrian (edited 08-12-2003).]

bunny
08-12-2003, 11:16 AM
Originally posted by Adrian:
I would recommend what I think is being called,'chunked LOD'. I presume it's not the same as geomipmapping or is it?

Basically break your terrain up into chunks e.g. 128x128, then calculate the LOD based on distance from the viewer.

You can use a cacheing system to only store the vertex array data for visible chunks of vertices. You only need to regenerate the vertex data when a chunk becomes visible or changes LOD. This keeps memory/cpu usage low.

This is imo the fastest,most memory effecient way of rendering terrain on modern hardware.

This screenshot shows a wireframe view of chunked LOD terrain with a 4kx4k dataset. http://www.adrian.lark.btinternet.co.uk/MarsExWF.JPG
Exactly the same idea.

I'm currently working on a variation of this, where the patches are stored in quad-tree nodes, and all are the same fixed resolution. The advantage of this is that the fixed chunk size is the optimal amount of vertex data to send to the graphics card in a single burst. Although it's not as flexible as the standard approach.

zix99
08-12-2003, 12:12 PM
Thank you all for your suggestions. Right now i am using something similiar to 'Chunked LOD', but with texture maps. I will go look at Geomipmapping and see what it does, it might be perfect for what i am doing.

Thanks again, and if anyone has a better idea i would be happy to hear it
ZIX

zix99
08-12-2003, 12:30 PM
I just want to know if i'm geting the idea about geomipmapping...

I found this site here (http://216.239.37.104/search?q=cache:3oMYI9SoYTwJ:www.flipcode.com/tutorials/geomipmaps.pdf+Geomipmapping&hl=en&ie=UTF-8) and read a little about it. It sounds like i'm already doing. Here are two images...

normal image (http://members.cox.net/zix99/images/sc1.jpg)
In mesh (http://members.cox.net/zix99/images/sc2.jpg)

it looks fine (excluding the texture map is pretty bad when it comes to shadows, i found a free one on the internet)

Thanks for advide, ZIX


EDIT: darn UBB code...

EDIT: darn UBB code TIMES 2...

[This message has been edited by zix99 (edited 08-12-2003).]

[This message has been edited by zix99 (edited 08-12-2003).]

Korval
08-12-2003, 01:21 PM
Basically break your terrain up into chunks e.g. 128x128, then calculate the LOD based on distance from the viewer.

Fundamental problem: how do you guarentee that the edge cases work correctly? Since they can't be using the same vertices, how do you handle the possibility of possibility of seeing small gaps between edges?

Also, how do you deal with visible LOD popping?

Adrian
08-12-2003, 02:12 PM
Fundamental problem: how do you guarentee that the edge cases work correctly? Since they can't be using the same vertices, how do you handle the possibility of possibility of seeing small gaps between edges?

Yes, a thorny problem. Edge strips and corners have to be tesselated so that there are no T-junctions. The solution is outlined here. http://www.flipcode.com/cgi-bin/msg.cgi?...um=askmid&id=-1 (http://www.flipcode.com/cgi-bin/msg.cgi?showThread=09January2002-N-PatchesforTerrainLOD&forum=askmid&id=-1)
Solving this for the corners was even worse and by far the hardest part of the engine.


Also, how do you deal with visible LOD popping?

With 250,000 polygons per frame popping is virtually unnoticeable. These days popping/geomorphing should be avoidable.

In case you downloaded my demo and noticed seaming, IIRC the seaming was only fixed in the second demo(Melas). http://www.adrian.lark.btinternet.co.uk/PWMarsExplorer3.htm

[This message has been edited by Adrian (edited 08-12-2003).]

bunny
08-12-2003, 02:13 PM
Originally posted by Korval:
Fundamental problem: how do you guarentee that the edge cases work correctly? Since they can't be using the same vertices, how do you handle the possibility of possibility of seeing small gaps between edges?

Also, how do you deal with visible LOD popping?

Where the neighbouring patches levels are different, you render the higher resolution mipmap edge to match the lower resolution edge using triangle fans.

See the method (and diagram) here (http://www.flipcode.com/tutorials/geomipmaps.pdf)

You can deal with popping by setting the error metric to be very low, so that only small errors are allowed when changing levels. If that's not good enough, you can do vertex blending between two detail levels. This is dealt with in the paper I linked to above (they refer to it as trilinear geomipmapping).

Adrian
08-12-2003, 02:26 PM
Originally posted by zix99:
I just want to know if i'm geting the idea about geomipmapping...


A few things I noticed from your mesh:

1) You jump from a low LOD to a high LOD which was 4x more detailed in each direction. It would be better to get your LOD algorithm to do a more smooth transition between the LOD levels.

2) You will get seeming issues because you have T-junctions in your mesh, refer to flipcode link I posted higher up.

3) Your not using many polys you will likely have severe popping issues, how many polys are you rendering per frame?

[This message has been edited by Adrian (edited 08-12-2003).]

Assassin
08-12-2003, 03:30 PM
Having implemented geomipmapping in my engine, I can say that if you use a pixel error metric of 3.0 then popping is almost unnoticeable. Getting a 3.0 pixel error required rendering on average 150,000 polys per frame for my test terrain, which is quite attainable at decent speeds on even a radeon 7500 when you use large batches, as GMM forces you to. I used "skirts" to make the T-junctions and seaming disappear, and used the same texture across the entire mesh to avoid texture seams. For calculating pixel error, I used the same formula as discussed in the chunked LOD paper, but you can specify a fixed screen width if you don't want your LOD selection to be resolution-dependent.

And for some eye candy, here's a pic (http://www.andyc.org/destiny3d/images/terrain-lod-6.jpg) of my terrain running, with a 1024^2 puget sound heightmap and a custom 2048^2 texture made by Devon Zachary. 112 is the framerate, and 216910 is the polycount. Running on a Radeon 9500 pro, 1GHz duron. And it uh... uses a direct3d driver, but the same stuff should apply to an opengl backend.

[edit] I should point out that GMM doesn't scale very effectively. I can load a 2048^2 heightmap, but with my current implementation it takes about 30 seconds to load and chews up 1.5GB of memory. Chunked LOD addresses this problem by only loading the vertices needed by a [soon to be] visible LOD mesh, and storing distinct vertices for each LOD level - this also allows for optimization of the meshes such as using VIPM. Chunked LOD takes quite a bit more preprocessing than GMM though, especially if you go for unique texturing (not splatted) - GMM can be loaded directly from a heightmap, but Chunked LOD requires some custom-formatted data structures that are all ready to stream into memory off disk.

[This message has been edited by Assassin (edited 08-12-2003).]

Stack Overflow
08-12-2003, 03:33 PM
One of very few topics I see Assassin around so just wanted to say hi.

- BlueDev



[This message has been edited by VC6-OGL (edited 08-12-2003).]

Adrian
08-12-2003, 05:51 PM
Originally posted by Assassin:
[edit] Chunked LOD takes quite a bit more preprocessing than GMM though, .. GMM can be loaded directly from a heightmap, but Chunked LOD requires some custom-formatted data structures that are all ready to stream into memory off disk.

Why do you have to preprocess for chunked LOD? I calculate vertices from the heightmap at runtime and store them in a cache just keeping those that are part of visible tiles, no preprocessing is necessary. (apart from indice arrays for the different LODs)

[This message has been edited by Adrian (edited 08-12-2003).]

JanHH
08-12-2003, 08:32 PM
how would you guys render a very large terrain? at least 1000 x 1000 km in real, and probaly larger? I think a normal map with a lot of details for such a size is rather inappropriate, isn't it? we have a standard triangle mesh with per vertex lighting and no tricks at all and it looks very bad, compared to the screenshot above, and it's already about 1.000.000 poly in the whole terrain, and a large amount of texture data.. any hints?

thanks
Jan

dbugger
08-12-2003, 10:43 PM
Split all data in chunks. Apply paged LOD. Paged LOD == Streaming data when needed from disk.

Korval
08-12-2003, 10:56 PM
how would you guys render a very large terrain?

Do you mean render, or generate? If you want rendering advice for a heightmap of a particular size, you have some in the previous posts.

If you mean generate, then you should look into fractals and perlin noise. Fractals can be used to generate terrain and normal maps. Also, they can get to pretty arbiturary resolution.

Assassin
08-12-2003, 11:13 PM
Originally posted by Adrian:
Why do you have to preprocess for chunked LOD? I calculate vertices from the heightmap at runtime and store them in a cache just keeping those that are part of visible tiles, no preprocessing is necessary. (apart from indice arrays for the different LODs)


I was referring mainly to the implementation offered in Thatcher Ulrich's Chunked LOD paper, which I believe is the origination of the algorithm. He uses a quadtree structure of distinct LOD levels that use VIPM to achieve mesh simplification (using a unit error threshold 2x that of the next-more-detailed level and 1/2 the next-less-detailed levels), and does a fairly memory-intensive quadtree splitting of the (very large) unique texture so as to match a unique texture to a unique mesh, make the texture for a mesh small enough to actually work on a current 3D card, and page it all at once off disk. If you can load and process a 16K^2 texture (128MB when stored as DXT1, 768MB when stored as BMP) on current 3D hardware, then please share your secrets.

You might have a variation on Chunked LOD that doesn't do it all the same way as Ulrich's paper and demo do, but when I refer to Chunked LOD, I mean the "official" version.

[edit] whoops, my original quoted texture size was too small - it's 32K^2, which makes for 512MB in DXT1. And the heightfield is 16K^2, which makes for a pretty sizeable chunk of memory too, especially if it's in 16-bit (another 512MB of memory). So you want to load and process a gigabyte of heightfield and texture data at program load time? I'd rather do some preprocessing.

Oh, and here's Thatcher Ulrich's chunked LOD page: http://www.tulrich.com/geekstuff/chunklod.html


[This message has been edited by Assassin (edited 08-13-2003).]

Adrian
08-13-2003, 12:13 AM
Originally posted by Assassin:
You might have a variation on Chunked LOD that doesn't do it all the same way as Ulrich's paper and demo do, but when I refer to Chunked LOD, I mean the "official" version.

Yes my 'chunked lod' seems different to his. Perhaps I should use a different name for my algorithm to avoid confusion, say 'tiled lod'. With tiled lod you only need to store the height values and texture data for every visible tile. This will only be an issue for very large datasets where you need to be able to view the whole datatset at once. There is no pre process step and no issues regarding height/collision queries. Tiles can be streamed off disk allowing infinite sized datasets. It seems more of a brute force approach then chunked lod.

Edit: On closer inspection it looks like the main difference is that I don't use a quad tree, the LOD is the same across a whole tile for me, his algo is more refined, mine simpler and more brute force.

[This message has been edited by Adrian (edited 08-13-2003).]

coelurus
08-13-2003, 01:44 AM
Another technique: Bunched LOD http://www.opengl.org/discussion_boards/ubb/smile.gif

This was my approach for my first terrain engine (66x66km2 with per-meter detail), using an adaptive quadtree for all patches. It's built upon Geomipmapping with 64x64 patches. Switching streams all the time was pretty slow, so I moved the low-LOD data in the leaves, far away from the view, up in the quadtree, "bunching" up the patches. I could then render big fields of GMM patches with one call and I gained atleast like 6x in performance... Not sure if this is what Chunked LOD does.

Using a rough heightmap along with some fractal details, the entire map takes 6.1 MBs on the HDD, about 10 MBs in run-time (excluding textures). My goal was not quality, but speed and little memory usage. We'll cover the thingy with vegetation and some structures anyway.

mfugl
08-13-2003, 04:46 AM
The real problem is limited AGP bandwidth. How are we going to reach 350M transformed tris/sek from new cards?

/mfugl

Adrian
08-13-2003, 04:56 AM
Originally posted by mfugl:
The real problem is limited AGP bandwidth. How are we going to reach 350M transformed tris/sek from new cards?

/mfugl

If the vertices are stored on the card by using VBO/VAR etc. then surely that isn't a problem? Having said that even benmark 'only' gives me 130Million vertices/sec on my 5900u which should be capable of 300+ million vertices/sec. Anyone know why that would be? maybe benmark doesn't use video memory....Also NVidias VAR demo only gives me 30Million polys/sec with lighting switch off.(same when switched on)

okapota
08-13-2003, 07:44 AM
Hey bunny, how do you generate your terrain? it doesnt look oike noise or a fractal approch.

zix99
08-13-2003, 07:49 AM
Originally posted by Adrian:
A few things I noticed from your mesh:

1) You jump from a low LOD to a high LOD which was 4x more detailed in each direction. It would be better to get your LOD algorithm to do a more smooth transition between the LOD levels.

2) You will get seeming issues because you have T-junctions in your mesh, refer to flipcode link I posted higher up.

3) Your not using many polys you will likely have severe popping issues, how many polys are you rendering per frame?

[This message has been edited by Adrian (edited 08-12-2003).]

to your 1). I fixed that problem right after i posted that message. I have new screenshots and new details below.

2)I'll try to fix that, many people posted the same thing.

3)about 1500 quads (now i use tris), of 15876, on a 128x128 heightmap. (Standing in the middle of the terrain)

---------------------------------------

Originally posted by Adrian:
With 250,000 polygons per frame popping is virtually unnoticeable. These days popping/geomorphing should be avoidable.

In case you downloaded my demo and noticed seaming, IIRC the seaming was only fixed in the second demo(Melas). http://www.adrian.lark.btinternet.co.uk/PWMarsExplorer3.htm


I'll check out that website, it is a method i HAVE to implement, i hate when there are pockets in the terrain.

--------------------------------------
Assasin, nice terrain http://www.opengl.org/discussion_boards/ubb/smile.gif

-------------------------------------
This terrain is to small to do this but I will aventually use chunked LOD, because my terrain are getting bigger, but height maps only go so big.

-------------------------------------
Program update:
Here are updated screenshots of the program
Mesh (http://members.cox.net/zix99/images/sc3.jpg)
Normal triangles (http://members.cox.net/zix99/images/sc4.jpg)

To who-ever said this, yes i do get a little terrain popping, but not extremly bad.



[This message has been edited by zix99 (edited 08-13-2003).]

Korval
08-13-2003, 11:30 AM
The real problem is limited AGP bandwidth. How are we going to reach 350M transformed tris/sek from new cards?

There's a new form of AGP-esque transfer protocol in development, if I understand correctly. Supposedly, it'll be released around the end of this year. It should allow for greater access to main memory bandwidth.

Adrian
08-13-2003, 11:54 AM
You're referring to PCI express I presume? http://www.anandtech.com/systems/showdoc.html?i=1830&p=1

V-man
08-14-2003, 10:43 AM
That`s not very AGP-esque.

"Serial interface"
"hot swappable"
"sequence number"
etc
etc

According to one chart they have, it is way faster than AGP but I`m not sure if it will replace it.

The paper has a mistake. It`s says that AGP is not technically a bus since it only supports one device. AGP v3.0 supports multiple devices now.

Yes, I already checked and there are no mothrboards with multiple AGP ports.