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

Submitted by Ben Woodhouse, posted on May 15, 2001

Image Description, by Ben Woodhouse

This shot was taken from the landscape renderer I'm working on. It demonstrates the use of LODs for landscape rendering.

The landscape is rendered as a 16x16 grid of tiles, with each tile drawing one of 5 pre-calculated LOD meshes (depending on distance from the viewer). The gaps between the tiles have not yet been filled in. The LOD reduction routine I'm using preserves detail with a bias towards higher points, so distant peaks are preserved.

With LOD turned off (each tile being just a grid of 16x16 quads), I get 14 fps in polygon mode, or 4 fps in wireframe mode, drawing 115200 triangles (on a GeForce2 Pro with FSAA 2x). With LOD turned on, the triangle count depends on the complexity of the landscape mesh. This one is nice and flat and so reduces to about 12000 triangles per frame, which displays at about 80fps in polygon mode or 20fps wireframe. Despite the fact that this landscape, including all the LODs, is made up of 90059 vertices and 145374 triangles, it manages to fit into about 1.45MB of memory (by the cunning use of BYTES instead of floats wherever possible).

The landscape renderer uses OpenGL. Eventually I hope to use it in a racing game I'm designing.

Ben Woodhouse

Image of the Day Gallery


Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
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.
John van der Burg

May 16, 2001, 05:39 AM

Ofcourse he is not.
But look. His current 'terrain' in the screenshots is really small.
If he precalcs all the vertexbuffers etc, that eats up a lot of memory if you have a big terrain.
That's the problem. So you have to stream through the terrains, and only
calculate visible parts of the terrain, and cache these for a while, until they haven't been visible for
a couple of seconds. On that way you keep your memory load down.
But that also means you have to re-construct the vertexbuffer for that terrain part if it becomes visible
and isn't in the cache yet. But constructing this with applying lod like this to it, might be
pretty slow. Not on 1 new visible part, but what if there are 20 new parts for example.
That might result in a big choking effect (the framerate drops down for a while) when you fly around
in your terrains. That might be anoying.

- John

Joachim Hofer

May 16, 2001, 08:36 AM

I am rather sure that there is no real reason to only use 8 tris per tile. For the grapics card it really doesnt matter that much whether you render 10000 or 12000 polygons, but if you write this in 8 tri bunches, this will be really slow. Why do you not simply put more tris in one tile and make the tile larger in space, resulting in the same polygon count for your lendscape? OK, you will render more unneccessary tris, but even though I suppose it will be much faster if you use around 100 tris or per tile something.

Christian Schüler

May 16, 2001, 11:11 AM

Numero27 wrote:

The reasoning behind not just flanging your tiles would be you wanted to vertex light them, but a bugger of a thing I've noticed about terrain engines that use arbitary meshes to represent the landscape (ROAM, QuadTrees or LOD tiles, as opposed to brute forcing it..) is that you will have a really hard time generating acceptable normals to vertex light the scene with. It will look okay while the scene isn't "moving", but as soon as an LOD switches the actual geomety sihloutte may not have changed all that much, but the shading changes will be very visually jarring. It's probably the biggest "for" for baking your lighting into your underlying textures.

A very big EXACTAMENTO from me on this point. When I implemented ROAM i realized that triangles where popping more between dark and bright than change in geometry. I tried to change the error metric to make triangles high priority which would change most in brightness when splitted. But it sucked also. The best solution is as you say to conserve all lighting in the underlying texture and render the landscape unlit. You'll have much more freedom about your lighting anyway and can precalculate it.

Alex J. Champandard

May 16, 2001, 11:41 AM

> Strips and fans aren't so good anymore

Never!! Strips are still right up there, fans never were (except flipcode fans of course ;) You can combine fans and indexed/vertex buffers, and that's the beauty of it all!



May 16, 2001, 02:49 PM

True, I might as well do that. Thanks!

Ben Woodhouse

May 16, 2001, 03:51 PM

Well, I just represent each landscape tile as a cube divided into a 256x256x256 grid, meaning I can specify vertex positions as single bytes (as someone pointed out, they're a quarter of the size of floats). I don't lose much precision like this. After all, the original height map was only 8-bit anyway.

Ben Woodhouse

May 16, 2001, 04:16 PM

I already had a way devised to generate the gap triangles in real-time based on an ordered list of tile edge vertices. Your suggestion looks neater though. Thanks for the idea; I'll look into it.

Ben Woodhouse

May 16, 2001, 04:34 PM

I've got a method for filling the gaps, but only on paper. In this method, each tile has two border strips: one above and one to the right. Each vertex on the edge of a tile is put into a list ordered by the vertex's position, then in real-time, triangles are generated to connect those vertices. In the case of a vertical border strip, the thing would work as follows (I pasted this from my notes, as I have no memory) :

To generate a triangle:
1. Find the topmost unused point in the strip. This is point A. Mark this point as used.
2. Find the topmost unused point in the strip from each side.
3. Point B is the point on the same side as point A, below. Point C is the point on the other side. This ensures the points are in anticlockwise order.
4. Draw (or store) a triangle going from point A to point B to point C.

Repeat the above procedure all triangles until the bottom two points of the strip are rendered (or stored) in a triangle. Then the strip is complete.

I think this method will work, however it may be slow (in the case of a real-time calculation), or eat too much memory (in the case of pre-stored meshes).

Ben Woodhouse

May 16, 2001, 04:43 PM

The problem is that when the tile edges have vertices in different positions, even if they are very similar, there will be small gaps where they don't quite line up.

If the landscape were static I could render the tiles with no gaps, however, each tile has 5 different meshes (depending on its distance from the viewer), so it's more complicated.

Ben Woodhouse

May 16, 2001, 04:48 PM

>>Still if you do some vertex lighting it'll look like crap if you don't join the vertex.

Good point. Also, with vertex rendering, when a tile is completely flat and reduces to 2 triangles, it would look very poor. Fortunately, I'm doing lightmap rendering, so these aren't issues.

>>you could implement a distance based LOD also it would help reduce a lot of triangles.

My LOD is distance-based.

Ben Woodhouse

May 16, 2001, 04:54 PM

My technique works like that anyway. I reduce the number of vertices based on how much each change affects the normals of the surrounding triangles, and stop at a certain threshold. In this way, flat triangles reduce to a smaller number of tris. In fact, a completely flat tile will reduce to 2 triangles.

Ben Woodhouse

May 16, 2001, 07:16 PM

Well, as you can see from my description, the frame rate is 14fps when drawing all the unreduced tiles*. Reduced, it manages 80fps. Quite an improvement, don't you agree?

As for popping, it's actually not noticable unless you're looking for it. The LOD algo I devised does a good enough job of preserving detail that two different levels of detail are hardly noticable. When it gets a bit more finished I'll put a demo on my site so you can see for yourself.

*Admittedly, this doesn't use triangle fans/strips, vertex buffers or display lists to achieve that, but in my experience such things rarely increase the frame rate by more than 10 to 30% (and you try fitting 115200 tris in a display list ;) ), so this still wouldn't produce an acceptable frame rate. BTW, the use of FSAA wouldn't affect this much as it isn't fill-limited. Without FSAA, I get 14.5 fps instead of 14. Ah, but enough waffle...

I'll look into that thing on evaluators, as the method I'm working on for filling gaps is far from pretty. I don't know that I'd want to use a nVIDIA specific extension, though, cos I'm planning on selling this thing someday.

Ben Woodhouse

May 16, 2001, 07:21 PM

It only slows things down noticably where fill rate is the bottleneck. For instance, it only makes about .5 of an fps difference on my landscape thing drawing 115200 tris, where the bottleneck is in transforming all those vertices. But yes, a geforce3 would be nice.

Ben Woodhouse

May 16, 2001, 07:31 PM

I was just wondering. If this little terrain (piece of a terrrain) already eats up 1.45MB of memory, wouldn't it be a bit of a problem when you need to store a HUUUGE terrain?
Yes, it would be a problem. I could get away with a terrain possibly 16 times as big stored in memory, and then I'd have to start loading terrain from the disk, which would probably slow things down quite a bit. Fortunately, I only need little terrains (maybe 4x the size above) for what I plan to do.

In other words, is the algorithm fast enough to stream through the terrain data. So while flying around, generating the terrain sector data on the fly (you should cache it ofcourse).
But I just have a feeling it will start choking a lot. [/i]

The algo would get about 0.00001 fps (if that) if it did the LOD on-the-fly. However, the meshes are pre-stored, meaning the only algorithm used at render-time is the one which gets the distance to the center of the tile from the viewer and selects the appropriate pre-stored mesh.

[another problem might be generating strips with this algo]

There's no reason why the pre-stored meshes can't be optimised into strips or fans.

Ben Woodhouse

May 16, 2001, 07:36 PM

Yes. That and scaling them.

Ben Woodhouse

May 16, 2001, 07:44 PM

Well, just doing some quick mental arithmatic, that's only a 256x256 heightfield you've got there. Memory useage shouldn't be that extreme, even if you were using floats to store all of that. *cough* try a 4096x4096 field. *cough* ;)

Well, it wouldn't be that extreme, except when LOD is applied, it goes from being an array of 256x256 bytes to 16x16x5 meshes (the x5 is because each tile contains 5 pre-stored LOD meshes). The method could be tweaked considerably to reduce memory consumption, at the expense of detail, if I wanted to do much bigger landscapes, but I just don't need big landscapes for the applications I plan to write.

Ben Woodhouse

May 16, 2001, 07:52 PM

Those s are supposed to be italics tags. This is what I wanted to do. That'll teach me not to use the preview button.

Moby Disk

May 18, 2001, 08:54 AM

I would have to see the exact use of bytes to say for certain, but you may be trading memory for speed. The video board, the CPU, and the FPU take hits for using non-aligned structures. Typically, you are better off to use the 4-byte structures and just walk memory efficiently rather than compact the memory and take the efficiency hit.

Ben Woodhouse

May 18, 2001, 09:18 AM

In this case it doesn't seem to have affected the fps, and I really can't get away with _not_ doing it. Speed is very important, but more important is the ability to run the program on low-end, low memory machines, as this will be a shareware game eventually.

This thread contains 49 messages.
First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.