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

Submitted by Henri, posted on July 17, 2001

Image Description, by Henri

Greetings - yep... its an ATR - Another Terrain Renderer.

- this is my claim to fame :) my post-graduate research focusses on developing a new continuous level-of-detail algorithm for terrain - the pictures above demonstrate the algorithm in action.

Ignore the abysmal frame-rates... my PC and graphic hardware was new back in 1996. On more up-to-date PCs the frame rates are on average in the range of 60 to 120. (The terrain data is a 1024x1024 heightfield, no far-clipping is performed.)

The algorithm utilizes split/merging (ala ROAM) - but ignores the idea of priority queues in favour of 4 constant-time LIFO queues; additionally the underlying mesh structure is completely different to ROAM's RTIN approach in favour of a form of ETRN (equilateral triangle regular network). This mesh structure tesselates faster and requires less work from top-most to bottom-most LOD compared to other approaches.

Additionally the mesh structure varies quicker from high to low detail. And it is extremely hardware friendly (in the sense that it can be used to generate long triangle strips).

Note from the screenshots: on average there are only about half as many vertices that require processing as there are tris in the scene.

The executable and (surprisingly short) source and a basic description of the algorithm are available here:

Press "v" a couple of times when executing to texture the terrain.

The official theoretical paper will only come in a couple of months... so don't wait up for that one. ;)

I'd love some (constructive) feedback... so go and gimme some.

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.
Sebastian Sylvan

July 18, 2001, 03:25 PM

You forget that some people with monster hardware get 50 fps. I think that your algorithm is CPU limited, so people with Geforce 3 cards don't really benifit from it unless they also have a 1.2Ghz CPU.

How many vertices do you have per vertex buffer? How many triangles do you have per strip?

As I've said before. There's virtually now difference in performance from changing 100 vertices and 1 vertex in the same vertex buffer. It's the first vertex that hurts. Not the rest.
What I mean is: It's THAT you update the vertex buffer that hurts, not by how much you update it.
And this is why a chunk-based LOD is way more effecient. You never ever change the vertex buffers, you only switch between different index buffers to represent various LOD-levels. So it's the best of two worlds. It pushes at least 4-8 times as many triangles as any CLOD algorithm, AND it has the ability to reduce detail for zoom-outs.
Now this detail reduction has to be conservative sure. You might not be able to reduce 50% of the polygons with maintained image quality but hey, you're pushing 8x the polygons to begin with so that doesn't matter does it? The important feature is that you can reduce LOD so that you have a "ceiling" of polycounts in the scene, no matter how much you zoom out you will never exceed this ceiling.

I maintain my oppinion on this: If you're target spec is Geforce1 or more than chunk-based LOD's are the way to go.

Mike Taylor

July 18, 2001, 04:20 PM

I have to agree to a point. If you change ANY data in your vertex buffers you will have to perform at least an AGP write, and potentially stall the pipeline. If you can get the memory however, you can work to precalc the collapse order into a VIPM structure and then you actually are just flipping around index buffers. This is a bit harder with view dependant LOD metrics, but can be done without touching your vertex data. This method has been done for Lindstrom and some of its variations (I have one myself), but I don't know of anyone who has made a static CLOD version for ROAM, and I dunno how it could be done for this algorithm. My point is, you shouldn't outright drop the idea of CLOD, as it can be represented exactly as you mention with blocks, but just have a VERY gradual change in index buffer data. Geomorphing is even possible if you have the memory for all possible points...

-Mike Taylor

Sebastian Sylvan

July 18, 2001, 06:07 PM

The following message is basically a direct transcript from a chain-of-thought. And may be completly moronic.

Am I correct in assuming that you are proposing an algorithm using VIPM on several chunks?

Can this be done with triangle strips?

Charles Bloom had something on his site about this. But it's basically pretty random (as I understand it). You choose the edges to collapse on random and then you imlement it as a sliding window, right?

What I'm saying is that it's still pretty limited (you can't choose which vertex to remove next depending on the current viewpoint, or am I wrong?).

How are you collapsing? Are you using the sliding window approach? Or are you mucking around with the index buffers (creating degenerate triangles).
As I see it, and bear with me I'm pretty tired right now. First of all you get around twice the index-buffer data. Also you can't collapse all of your triangles using this method.
However if you're mucking around in the index buffer you have two cons. Firstly you'll have a BUNCH of degenerate triangles after a while which defeats the purpose of LOD in respect to lowering the bandwidth. Also, you'll have to change your index buffers which, while faster than changing vertex buffers, causes a stall in DX8 (I think it needs to check for out of bound vertices or some crap).

Anyway, the biggest flaw in the chunk-based VIPM approach as I see it is that the triangles get popped at random, it might be very obvious from the current view point. So the worst case scenario is the same as for geomipmaps. The best case scenario is not nearly as good, geomipmaps can reduce detail to just two triangles per patch (which can't be done with the sliding window approach, unless you have several index buffers (like a lot of them))!
Another really important issue is vertex cache performance. You can easily rearrange your triangle strips to maximise the use of vertex cache. But since triangles need to be stored in collapse order with your method, and I assume that the collapse order needs to be somewhat random, the vertex cache performance is poor. Right?

Anyway I'm rambling. Catch you later. Have to get some sleep now.

Mike Taylor

July 18, 2001, 07:07 PM

You have run into what I consider the biggest flaw in this approach: striping. I have not found a reasonably useful methods of generating strips for this. I personally use trilists that are pretty optimized for cache coherency, and I definately get that. The other big plus of the method is that I only have one set of points for the patch, with size

This thread contains 34 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.