• Advertisement

Archived

This topic is now archived and is closed to further replies.

Terrain LOD question.

This topic is 6053 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, I'm writing a landscape/terrain engine/demo. It's already looking really nice (screenshot here - http://www.sbdev.pwp.blueyonder.co.uk/Terrain2.jpg ) but of course it's too slow. Has anyone got any recommendations for a way of implementing LOD/distrance abstraction? Currently the 'map' is made up of 10*10 sectors of 30*30 nodes. I could have a sector based LOD value based on distance from player, and update only when the player leaves a sector. The problem with this is that building the new sectors is too slow because I need to work out face normals, and then average the face normals to get vertex normals. Averaging face normals to get vertex normals is very time consuming, but without vertex normals, D3D is using the face normal for all three vertices, and we got no shading. I've been looking at one of the best terrain engines, Project IGI, and I can't figure out how they can keep the frame rates up when they are rebuilding a section of their map every frame. Can anyone enlighten me? TIA, Simon. Edited by - simon_brown75 on July 19, 2001 7:18:29 PM

Share this post


Link to post
Share on other sites
Advertisement
Make sure that you cull any un-necessary triangles from the terrain mesh, and also make sure that you aren''t populating flat areas with more triangles that barely needed...

www.vterrain.org

That may help you out a little, if you haven''t been there already.

------------------------------
Trent (ShiningKnight)
E-mail me
OpenGL Game Programming Tutorials

Share this post


Link to post
Share on other sites
Well, at the moment, the triangle distribution is the same everywhere, on flat and hilly bits, 2 triangles per node.

I''ve managed to speed it up by implmenting a crude form of level-of-detail, where each sector has an LOD value, which determins how many nodes to skip for each pair of triangles. Either it skips 0, 1, 2, 4 or 5 nodes at a time. This means each sector can have 1800, 450, 200, 72, or 50 triangles. This has brought the number of drawn triangles down from 180,000 to about 25,000 per frame.

However it''s left gaps where distant sectors join each other (as I knew it would).

I think I should be trying to do something like the ROAM algorithm instead.

Share this post


Link to post
Share on other sites
Hey, Recently I have been reading up on quite a few interesting algorithms such as, LOD using ROAM && binary triangle trees, QuadTrees, and a few other things. There is tons of information covering these topics if you do a search on gamasutra or google. And find yourself a nice texturing algorithm. Heres a pic of my terrain demo/thingy from last week http://www.geocities.com/tryforfulluse/water_lil_jpg.jpg
Read up on frustrum culling too. good luck.

Share this post


Link to post
Share on other sites
Thanks for the info Just been reading the ROAM white paper last night, interesting stuff, although hard to follow at times.

That''s looking really nice. Are you making a demo or are you hoping to make a game with it?

Share this post


Link to post
Share on other sites
Im currently rewriting my entire demo to support ROAM with frustrum culling. A paper that provides source code located at http://www.gamasutra.com/features/20000403/turner_pfv.htm provides a nice read with source code.

Share this post


Link to post
Share on other sites
Now that I''ve spend the day reading and such about ROAM, LOD, and quadtrees, I have to say quadtrees seem a bit better than ROAM (in my own opinion), because ROAM constantly has popping meshes, which become''s very irritating. I read through a great article on quad trees, which dont seem to hard to implement, located at www.gamasutra.com/features/20000228/ulrich_pfv.htm

the author of that article presents some great idea''s for LOD calcuation''s. try out both ROAM & QuadTrees to see which algorithm you''d rather work with. good luck

Share this post


Link to post
Share on other sites
Simon_Brown,

You seem to have a good idea on this terrain stuff I''ve seen you post some sample code on another forum which is rare these days. Is there anyway you could tell me or post some code on how the Vertex buffer part of the ROAM terrain works. Like where to lock and unlock the buffer and how to code in the triangle list ? Thanks for any and everything.

Scoot

Share this post


Link to post
Share on other sites
Scooter/

I think you''ve over-estimated my talents with terrain engines I only started writing my first ever terrain demo two days ago, and only started implementing LOD yesterday. The version of LOD i''ve implemented is very amateurish as well, which is why i''ve been reading about ROAM and other LOD techniques.

masterg/
I also read Thatcher Ulrich''s piece yesterday, and I also find qudtrees more appealing than bintrees. It seems a cleaner solution to me, and easier to get up and running.

Share this post


Link to post
Share on other sites
heh, after reading some more, octrees seem like another nice alternative. and once again, good luck.

Share this post


Link to post
Share on other sites
Octrees are nice alternative, however they are rather fitted for 3D rendering ( I mean worlds with several levels: ground, underground and so on, or a town with buildings ).

The complexity added in building the octree don't worth the benefits for a "flat" landscape render. Building an octree from an heightmap ( I suppose you use an heightmap ) require some computations, and you have to make choices to define where to put the sectors that will cut your 3D world. Some divisions will be better than others,and finding a good one could be an hard job.

I am convinced that quadtrees ( and adaptative quadtrees ) is the best and simplest solution.

Edited by - Cedric Perthuis on July 22, 2001 1:43:51 PM

Share this post


Link to post
Share on other sites
Yep, i''ve decided to go with the quadtrees, a least for this particular engine. Although the vertex buffer management is dragging down the performance, the technique is working pretty well. There''s a wireframe screenshot of what i''ve managed so far here-

http://www.sbdev.pwp.blueyonder.co.uk/wireframe.jpg

Share this post


Link to post
Share on other sites
I have a follow up question. Is it possible to get decent performance if you are building the entire terrain mesh on the fly every frame?

Share this post


Link to post
Share on other sites
In my opinion no, unless you are rendering a small world. You mush have some type of LOD implementation if you are to render a somewhat large world.

Share this post


Link to post
Share on other sites
I think my question may have been a little ambiguous

LOD (level-of-detail) simply means you have an algorithm controlling polygon density across your mesh. I have that in place, using adaptive quadtrees, as can be seen in that wireframe image.

Whether you reconstruct your entire mesh every frame, or just modify a small section is a sperate question though. So, using LOD, but rebuilding the entire map every frame, is it possible to achieve decent performance?

Thanks.

Edited by - simon_brown75 on July 22, 2001 4:13:03 PM

Share this post


Link to post
Share on other sites
Oh sorry, from what I''ve seen and from what I''ve done, you can rebuild the entire scene every frame and still get decent frame rates. But, you should have some sort of frustum culling so you dont have to render everything. From a quadtree demo I worked a bit with, I was rendering a very large landscape every frame, and got ''decent'' frame rates.

Share this post


Link to post
Share on other sites
So much for 'straight forward', it took ages to get it working, but I now have frustum culling in place and it's made a huge difference. Frame rates have gone from <20 to around 50 fps

Just a note - it's not perfect though. I noticed it's possible for all 8 points of a patch bounding box to be outside the frustum, but yet the patch should still be partially visible, and of course it gets culled. I think using spheres may be more accurate than a bounding box in this circumstance.

Cheers for all the help

Edited by - simon_brown75 on July 23, 2001 12:56:36 PM

Share this post


Link to post
Share on other sites
Regarding the patch visibility. I had tons of problems with this (I used the ROAM algorithm however, but the ideas are the same). Instead of using 8 test points, I used 5 test points. The 4 surrounding the patch (2D square), with the 5th in the middle of the square. All of the height values (Y coordinates) were taken from the actual height field, such that the 5 test points were not all in a single plane. I then expanded them outwards by 25% (this is a fudge to help fix the problem of undrawn patches that should be drawn, but the test points fail to detect this situation). So your 4 outer points are 25% farther out. This is like a safety margin. The extra performance from having to transform just 5 instead of 8 points for each patch helps offset the fact that once and a while an unwanted patch will get drawn with this method.

I''ll be posting screen shots of my new ROAM engine shortly.

By the way, I''m getting "good" framerates rebuilding the entire tree each frame. I could do better if I coded some frame-coherance (regenerating only the necessary bits of terrain each frame), but that''s quire complex, and will come later.

By the way, it''s BS that ROAM has more popping than quadtrees. The concept between the two algorithms is almost the same.

The bit thing to reduce popping is to use a VARIANCE structure, like the one talked about in the ROAM article on gamasutra.com. This is th emetric used to determine where more detail is required. It''s your screen-error metric.

By the way, don''t forget to "adjust" your screen error metric by camera-vertex distance, such that the metric is considered less and less the farther it gets from the camera. But don''t ignore it totally or you will get popping as objects come at you from the distance.

Greg.

Share this post


Link to post
Share on other sites
Oh by the way, drop lighting altogether. It''s a waste of processor. (it''s also nearly impossible to code using ROAM so far as I''ve figured out. If anybody can show me wrong, please go ahead!).

Use a lightmap. Use some other application to generate a lightmap for your terrain (try WILBUR, it''s free). Then using multi-texturing, texture both your terrain texture, and your lightmap (a darkmap is the easiest way).

The negative to this is that game lighting changes will not affect your landscape''s lighting. I''m thinking of using dot-product bump mapping to light the landscape in a third texture operation to overcome this, but honestly, I don''t think this is a large problem.

With lightmaps you have one other huge advantage (other than the performance of not having to code your normal averaging). You can (at any point in time) generate a RAY-TRACED lightmap texture using another application, or coding this yourself. That way your mountains can actually CAST SHADOWS on terrain. This makes for a VERY cool effect when walking around your landscape.

Share this post


Link to post
Share on other sites
Cheers, more great advice

I''ll give the 5-point clipping method a try and see how it works out.

Since this was my first terrain engine, I''ve basically took all the simplest ideas from all the articles I''ve read. I calculate the variance just by taking the actual height difference between the node and the mid-point of the edge the node is on (so 6 errors to calculate per quadrant). Then I do-

if ( error * threshold > distance ) -> split the quad

I know from the results I''m getting that this isn''t a good method, so I''m going to read the articles again and see what I should be doing. I have 4 levels of detail and only the first and last are used heavily. I''m also getting polygons wasted on entirely flat sections.

Still, that''s all totally fixable given a week or two more work.

Share this post


Link to post
Share on other sites
Acutally the algorithm-

if ( error * threshold > distance ) -> split the quad

is ok afterall, it was just a dumb bug. I have much better polygon distribution and far less popping with the bug fixed.

Share this post


Link to post
Share on other sites
A word of warning. If you want to reduce popping, then you should not simply check your top level polygons for accuracy, and failing that, recurse into more detail.

What happens with your algorithm if there are 2 small mountains in each triangle of your quad, but the middle point lies on the same plane as the 3 surrounding points? You won''t recurse to get those mountains, right?

That''s why you need to build a variance tree. It''s a tree (quad tree if you''re using quad trees, bintree if you''re using roam) that mirrors your normal subdivision. It contains a variance value (difference between real and interpolated height) for each stage of your normal subdivision. With quad trees, it should be a quad tree, with roam it should be a bin tree. Generate the whole tree in advance. So your first level (top level node) should contain the variance without any subdivision. Just the top level difference at the middle. Then you subdivide into 4 quads right? Well, then add the variance for all those 4 quads (their midpoint variance) into the tree. Keep going until a vertain point (usually until a resolution of 8x8 point samples).

The catch is that what you should really do is store the MAXIMUM variance at each level. So at the top level, don''t store just the variance based on the difference of the top point. As you keep recursing down, and checking variance down lower, bubble the LARGEST variance found all the way up to the caller. So if you had that twin mountain situation I described earlier, you would get that large variance (perhaps after 2 subdivisions) bubbled up to the top level. So your top level would store the variance from a few levels down in fact!

Of course, the next level deeper would most likely store the SAME variance figure as the top one, because ALL nodes should keep the largest value they find. It''s either going to be the one they calculate from themselves, or the one that is bubbled up from a deeper recursion, which you know is the biggest value found deeper down, since you keeped bubbling up the MAX value found.

Did I make sense? It''s a little hard to explain.

You only need to store this stuff as a BYTE to save storage because it will be a large tree.

So you''ll typically have values like 17, 6, 4, 23 in your tree. This represents how badly off your approximation is at any given point (considering also deeper nodes because of the bubbling). Now you need to factor in distance. A value like 4 might NOT be ignored if close to the camera. But it would be in the distance. However a value of 23 should never be ignored even in the distance, because mount everest might vanish.

Normally you would (by some factor that you will have to tweak yourself) divide the variance by the distance. So 23 would be reduce to 2.3 if it was 10 units in the distance (well, 2 since we are talking integer division of course). You may have coded to ignore variances of 1, but keep all those >1. If you did this, this moutain would only vanish at 20 units distance.

You get the idea?

When implimented like this, popping should nearly vanish, because distant objects that deform the terrain significantly should be retained even in the distance.

Best of luck,

Greg.

(still working hard on my terrain engine acutally, I''m not an expert, but I''m getting there after hours of toil. Geez what a pain these things can be).

Don''t even THINK about texturing yet (well, not advanced texturing).

Are you using gouraud shading? It can be done in quadtrees without much trouble, but it''s expensive. ROAM it''s almost impossible. I like lightmaps myself. You should give them some thought.

Share this post


Link to post
Share on other sites
Terrain programmers seem especially generous, thanks again

I had already noticed that problem, but hadn't come up with a solution to it. Just testing accuracy against 3 nodes per triangle at the top level (out of 64 nodes per quadrant of a patch) means quite significant features can be completely missed. I definitely need to fix this, plus there's the time I'll save by not calculating the variance on the fly. Preumably it would have to be an implicit quad-tree to keep the size down.

..and the explanation did make sense, cheers

Simon.

Edited by - simon_brown75 on July 24, 2001 3:08:52 PM

Share this post


Link to post
Share on other sites

  • Advertisement