Thus, the rendering algorithm changes to something like:

idxCounter = 0
Index-Matrix = 0xFFFF

If vertex needs to be render
..If index-matrix[row][col] != 0xFFFF
....Add index to index array
..Else
....Morph the vertex
....Index-matrix[row][col]=idxCounter++;
....Add vertex to vertex buffer
....Add index to index array
..End
End

RenderVertexBuffer(index-array)

You have to be careful with these sort of algorithms. When I wrote an indoor engine a few years ago I tried to do the same thing. I had all my polygons index into a global vertex pool. Each vertex was flagged to make sure it's only transformed once. In the end, the whole thing ran very slowly because of the "if" statements checking the flag and because you're missing the cache with the random vertex pool reads. It may still be worth it if the per vertex operations are very expensive or helpful to your algorithm (i.e geomorphing).

Regarding the comment "if f falls into the range [.5, 1), the quadtree is not further refined" : One thing I've noticed by setting 'c' to 0.0 (meaning ignoring roughness values complete) is that if f = [.5, 1) then you WILL have to generate a fan at this node.. So there is always 1 child that did not split further.

Perhaps the idea is to use this value for the blending value of the 'leaf' vertices? Of couse I might be brain dead from staring at Figure 7 for too long.

I also wrote a simple console app that builds roughness values, triangulates etc, and then dumps out an ascii version of the different matrices. This seems to be pretty helpful in understanding just what is going on w/o dealing with GL / D3D..

First, I subdivide the world in 65x65 blocks (or smaller, if the user wants them to be smaller). There are three reasons for this:
(a) limits in texture size (i.e. Voodoo)
(b) to limit the size of a vertex buffer
(c) to decrease the number of levels in the tree.

For 65x65 blocks, the theoretical vertex buffer size if 4225 vertices. In practice, however, you'll only need the first 1000-1500 vertices. This is because of the simplification (i.e. NESW vertices are usually skipped). Well, it's probably *much* less than 1000 vertices, but I cannot tell for sure, without testing, first.
Assuming that each vertex is 24 byte, then we have a vertex buffer of 1,000*24 = 24,000 bytes.
In addition there's the index array. Assuming, that each vertex is used 4 times (average), we have an array size of 4*1,000*2 = 8,000 byte.
So all in all we are talking about 32,000 bytes, which doesn't seem to be too much.

As for if-statements... Those are only used to check the index-matrix. Of course, this can result in a cache miss from time to time, but I also significantly reduce the number of morphs. With fans, you morph each edge-vertex twice, whereas I'll only need to morph them once. I believe (but cannot proof, yet), that reducing the number of morphs is more important than having a cache miss every 100 vertices or so.

I think we don't have to argue about triangle lists. They are better suited than fans, because you triangles can be batched up. This is necessary to achieve high polygon throughput (see "fanning problem" thread on this message board).
Indexed triangle lists take this a step further, because not only do they avoid unnecessary transforms, but they should also reduce cache misses. That's simply because an indexed vertex buffer contains much less vertices than a non-indexed vertex buffer. Of course, a non-indexed vertex buffer is better sorted than an indexed one, and can thus be read sequentially. But an indexed vertex buffer also contains some order, because of the nature of the tree traversal.
Hence, I believe, that indexed triangle lists are the way to go for this particular problem (I may be wrong though).

As for vertex buffer handling, I intend to do the following:
(a) create vb with D3DVBCAPS_WRITEONLY
(b) lock vb with DDLOCK_NOOVERWRITE and DDLOCK_DISCARDCONTENTS
(c) add vertices to vb
(d) unlock vb
(e) DrawIndexPrimitiveVB
(f) jump to (b) and lock the same vertex buffer

Indexed triangle lists are the best thing to use. But you can gain even more speed by having the triangle indices in strip order. One card in particular (can't say for NDA reasons) only has a 3 value vertex cache and no strip support. So using these sorted triangle lists will allow the card to auto-generate strips for you and cut the bus traffic. The speed gain is VERY noticeable from my experience.

About the flag issue. From your first pseudo code example I thought you were using a frame number type flag. I used this in the past to keep track if a vertex has already been processed in the current frame. It ended up being slower to check the flag than to simply process all the vertices at the start of the frame.

I read you message, but still wanted to run a performance test between triangle fans and indexed triangle lists. The difference is gigantic.

Machine 1 (TNT-1, Windows 98):
fans: 101 fps
list: 124 fps

Machine 2 (GeForce, Windows 98):
fans: 155 fps
list: 271 fps

Machine 2 (GeForce, Windows 2000):
fans: 231 fps
list: 217 fps

Don't ask me what the problem with the Win2K machine is. But the Windows 98 numbers are reason enough to stay with the indexed lists.

BTW... these tests were not performed with Roettger's algorithm. I wrote a small test program, which displays 1024 quads (traversed like a tree). Each quad has 4 triangles (NESW vertices skipped).

Here you go: http://www.thecore.de/TheCore/QuadRender.zip

Thanks a lot Can't wait to examine the source.
Until now I was only able to have a quick look at it. Well, the code sure looks different. To be honest... it's looks over-complicated and cumbersome. But that's, of course, only my first impression. Time to have a closer look...

Thanks

Hmmm. It also appears that I am calculating the d2 values in the same manner as they are. The paper didn't clearly mention testing against the child nodes as well as newphews, but it makes sense.

Also their K value is different from the papers. I realized that a different K value is needed for children vs nephews, but I didn't come up with the same values that they did.. Guess I'll try theirs and see if I notice a difference.

Their K value is the same as in the paper. The point is that they are scaling their errors by DETAIL_VALUE_SCALE_FACTOR = 0.5.

For the L1-norm, their K is:

K = C / 2 * (C - 0.5)

Child errors are multiplied by K:

error' = K * error * 0.5

(0.5 is the DETAIL_VALUE_SCALE_FACTOR). Now you do the math:

K = (C / 2 * (C - 0.5)) * 0.5
==>
K = C / 4 * (C - 0.5)
==>
K = C / (4C - 2)
==>
K = C / 2 * (C - 1)

Their K value is the same as in the paper. The point is that they are scaling their errors by DETAIL_VALUE_SCALE_FACTOR = 0.5.

For the L1-norm, their K is:

K = C / 2 * (C - 0.5)

Child errors are multiplied by K:

error' = K * error * 0.5

(0.5 is the DETAIL_VALUE_SCALE_FACTOR). Now you do the math:

K = (C / 2 * (C - 0.5)) * 0.5
==>
K = C / 4 * (C - 0.5)
==>
K = C / (4C - 2)
==>
K = C / 2 * (C - 1)

I'm talking about the consts LOD_Terrain__Child_Detail_Scale and LOD_Terrain__Nephew_Detail_Scale which are found in LOD_Terrain.cpp. These are the K values that they use.
Kchild = C / (2*(C - .5*sqrt(2)))
Knephew = C / (2*(C - .5*sqrt(10)))
Both are mentioned in the .DOC and at the top of the .cpp file though I'm still working on understanding it better.

Those values are used in the constructor for Detail_Map() to build the detail/d2 values.

My code for d2 calcs was identical to theirs except my 'K' values were apparently wrong because of the paper. Their should definitely be 2 different K values (one for children and one for nephews). I need to reread the paper and see if I can prove that Westwoods values are correct.

Also, what were the problems with morphing? And what were you using for your bias calc?

I think some of the more knowledgable people
should get togethet and form a web page on the topic with tutorials, samples, optimizations...

I've looked at the paper and other documents and fairly understand the algorithm - but I'm sure other people who may wish to use it may be baffled.

Ye seem to have some good ideas bouncing around - it would be a shame not to have them all together on a web site.