I'm a bit confused now. I take the average height, and the detail increases as I get closer to the ground. The LOD works just as I would expect.

It was just a suggestion... It depends on what your game is like. Let's take an example:

Thanks. I understand now. I sort of like your idea, because it will also be faster than computing the average height for each block.

Anyway, I plan to rewrite my engine tonight so that I can make it publicly available (hopefully with correct geomorphing, and this time it'll use Direct3D). I'll support your idea in this version.

Thank you so much for this. I really appreciate it, and of course I'll provide feedback.

Have a look at your old post (Feb 03, 2000 - 02:47 PM).
If your propagation code really works as you explain in your post, then you ran into a trap (I almost ran into it myself). The problem is that you cannot propagate the errors in a recursive process. The reason is as follows. You need to compute K times the neighbors' d2 values. However, if these neighbors have another parent than the current block, then chances are that the neighbors' children didn't propagate the d2 values to the corners (just because they are in a different branch of the recursive process and are therefore visited later). Thus you read wrong d2 values from the edges.

Guys -- I'd like to discuss this error propagation again. The point is this. If I really implemented the propagation as it is presented in the paper, then my this part of my code would be completely different. I'm now going to copy the important parts of the paper, and then comment on them. (Always keep in mind that the authors are mathematicians with Ph.D.s).

I'm going to do this, because I think there's a chance, that none of us got the error propagation right. Let's start:

(1) "Thus, if d21/d22 <= K, then we have to modify the d2-values in the following fashion:"

The above contains an "if". Does this perhaps mean "if and only if"?

(2) "Starting with the smallest existing block, we calculate the local d2-values of all blocks and propagate them up the tree."

The important words here are "local" and "all". If I take this sentence as it stands, then I would first compute the *local* d2-values of *all* blocks in the tree, before I do anything else (like multiplying by K and comparing with existing values).

(3) "The d2-value of each block is the maximum of the local value and K times the previously calculated values of adjacent blocks at the next lower level."

Now this one is a beauty. First off, have a look at the end of the second paragraph in the geomorphing section. Here the authors use the terms "lower level" and "higher level". One might think that they accidentally confused "lower" with "higher", but... If you were assigning numbers to each level in the tree, then you would choose 0 for the root, and 1 for the level below. Thus, the root is at a lower level, than the level below. Therefore, the authors didn't confuse "lower" with "higher".

Now back to the propagation. The important part here is "...K times the previously calculated values of adjacent blocks at the next lower level."
If we use the same convention as in the geomorphing section, then the "next lower level" is the level above, and the "previously calculated values" are the values we calculated in (2).

Well, my description above is not really complete, because it would have taken too much time. But please consider this "Why do we have children, if 0.5 <= f < 1 ?". One possible explanation of this could be, that our error propagation is completely wrong.

In my opinion, the error propagation is definitely open to interpretation. If you read some of my earlier posts in this forum, I was doing it completely different at the start. When I read the term "adjacent blocks at a lower level" I thought it meant the 2 child nodes of your neighbor that border the current block. I wasn't doing the propagation to the corners at all. The algorithm still seemed to work without any cracks, etc. Since then I fixed it to propagate to the corners but this illustrates that just because it looks like it's working does not mean you're doing it correctly.

I really hope you have success. The more I look at the paper the more confused I get. I guess I've been staring at it for too long.

Sometimes I wished that Siggraph papers were allowed to be longer than 8 pages. Peter Lindstrom's paper with 10 pages was a real exception.

I was thinking again... In one of your mails you wrote:

"I think I understand now why the author of the paper insisted that nodes with 0.5< f < 1 should not have any children. Those f values would correspond to a blend value of 0 < b < 1. The reason this is important is that it gives you a way to test if a node is really subdivided (b==1). Without this condition, you have no way of knowing if nodes with 0 < b < 1 really have children."

This is either not correct or I misunderstood your point. You know that a node is subdivided, if b > 0 (f < 1), because b <= 0 corresponds to f >= 1.

But there's still a reason, why it is important that nodes with 0.5 <= f < 1 are not further refined. Let's talk about this "further refined", first. In the paper it reads "A close examination reveals that, if f falls into the range [0.5,1), the quadtree is not further refined, and a single fan is generated for the complete node". If I understand this correctly, then this means that the node has exactly 4 children, and they are all leaf nodes. Thus you can draw their parent node with a single fan.

Now for the reason why this is important. My geomorphing does exactly what the paper says, but popping still occurs, if a new child is born. The reason why there is popping is, that the parent node of the new child has not yet finished its morphing process, because the blending factor was still in range (0; 1]. This must never happen, if you don't want to morph corner vertices. Have a look at the paper... they don't morph corner vertices. Hence, you need to finish morphing a node, before you subdivide it.

MarkW, I don't check the value already stored, just the local d2 and the neighbors. But since the values that could already be stored have already been propagated to every possible neighbor, I don't think you need to or are supposed to.

Klaus, I'll be the first to agree that the paper is not clear. And the authors wouldn't help me much either. But my best guess is that when talking about propagation, they're definitely saying K times the values at higher resolution (i.e. toward the leaf nodes). I think that because the d2-propagation definitely moves up toward the root, not down to the leaves, and theoretically it doesn't make sense to be multiplying the effects of K down towards the leaves. So I think starting at the height field data and 3x3 blocks, and working up towards the root, is the only conceivable way to do this. When geomorphing, I think "higher level" means "closer to the leaf nodes."

Re the 0.5<=f<1 thing, I just don't know.

Anyway, I promised to reveal the family jewels, at least as they relate to walking the completed tree and rendering. So here it is. In light of what's gone before I have less confidence that this is the way it was intended, but it works. RenderBVertex is a call that multiplies by b before doing a glVert, and RenderVertex omits the multiply (for corner verts, which aren't morphed). At the moment I can't remember what's up with that last, largely-empty switch.

void rLOD::RenderTree(w16 x,w16 y,w16 dim)
{
int d2=dim>>1,d4=dim>>2;
float b;
int xy=y*map_dim+x,yd4=d4*map_dim,ydd=dim*map_dim;
int firstVert=0;

bool clipRight=(map_dim-x)<dim;
bool clipLeft=x<dim;
bool clipTop=(map_dim-y)<dim;
bool clipBottom=y<dim;

bool didLast; //so we don't repeat verts

b=blends[xy];
if(blends[xy+yd4+d4]!=0) //ne needs subdivision
{
if(inFan)
EndFan();
RenderTree(x+d4,y+d4,d2);
}
else{
StartFan();
RenderBVertex(x,y,0,0,b);
if(clipRight | | blends[xy+dim]!=0){
RenderBVertex(x+d2,y, 0,d2, min(b,blends[xy+dim]));
firstVert=1;
}
else firstVert=2;
RenderVertex(x+d2,y+d2);
if(clipTop | | blends[xy+ydd]){
RenderBVertex(x,y+d2, d2,0, min(b,blends[xy+ydd]));
didLast=true;
}
else didLast=false;
inFan=true;
}

if(blends[xy+yd4-d4]!=0) //nw
{
if(inFan)
EndFan();
RenderTree(x-d4,y+d4,d2);
inFan=false;
}
else{
if(!inFan){
StartFan();
RenderBVertex(x,y,0,0,b);
}
if((clipTop | | blends[xy+ydd]!=0) && !didLast){
RenderBVertex(x,y+d2, d2,0, min(b,blends[xy+ydd]));
if(!firstVert)firstVert=3;
}
else if(!firstVert)
firstVert=4;
RenderVertex(x-d2,y+d2);
if(clipLeft | | blends[xy-dim]){
RenderBVertex(x-d2,y, 0,d2, min(b,blends[xy-dim]));
didLast=true;
}
else didLast=false;
inFan=true;
}

if(blends[xy-yd4-d4]!=0) //sw
{
if(inFan)
EndFan();
RenderTree(x-d4,y-d4,d2);
inFan=false;
}
else{
if(!inFan){
StartFan();
RenderBVertex(x,y, 0,0, b);
}
if((clipLeft | | blends[xy-dim]!=0) && !didLast){
RenderBVertex(x-d2,y, 0,d2, min(b,blends[xy-dim]));
if(!firstVert)firstVert=5;
}
else if(!firstVert)firstVert=6;
RenderVertex(x-d2,y-d2);
if(clipBottom | | blends[xy-ydd]){
didLast=true;
RenderBVertex(x,y-d2, d2,0, min(b,blends[xy-ydd]));
}
else didLast=false;
inFan=true;
}

f=l/(d * C * max(c*d2,1))

Now let's say f > 0.5 for the parent node.

Thanks for the explanation. It wasn't quite what I was looking for, but it still helped. I was more looking for an explanation about how exactly those formulas are derived, and why they are as they are... a proof for those formulas. But your explanation still helped a lot. Thanks.

As for "we are all three doing the propagation properly.". I think you are right. When I first implemented the propagation I didn't even think about it. I implemented it intuitively. And so did others, like C. J. Cookson, Mike Cocker, Mark Batten, and Mark Wilczynski. Mike Cocker, however, made the same mistake than Mark Batten did (recursion).
Anyway, we all implemented this part of the algorithm independently, and we all chose the same approach. Now there are two options:

(a) we did it correctly

(b) we all implemented Lindstrom's algorithm before, and are blinded by Lindstrom's "error propagation". (which was: take the maximum of the children's delta values -- this was possible with recursion, btw.).

I for myself believe in (a) now.

I am curious if any of you are planning on attending GDC this year? There is a talk on Friday 12:00-1:00pm on the algorithm in this paper. There are 3 people giving the presentation, so maybe one of them will have some insight. One of the guys (Louis Castle)is from Westwood, the other two I have no idea. Well if you guys go, maybe I will see you there.

I'd love to work more on this, but studying takes up far too much time! Anyhow, this might give you all some food for thought.