Author

Topic: Rottger/Quadtree Algorithm

MarkW Member

posted February 01, 2000 01:49 PM
Has anyone else here (besides C.J. Cookson) implemented this algorithm? I got everything in the paper to work except for geomorphing. No matter what I try, I get cracks in the terrain with any type of geomorphing. The paper doesn't go into enough detail and the author is unwilling to help.IP: 
MarkBatten Member

posted February 02, 2000 08:58 AM
Yes, I've got it working (on a Mac, but the code is identical). If you can be more specific about the problem and your implementation, I'd be glad to try to help.IP: 
MarkW Member

posted February 02, 2000 11:37 AM
Okay.. first let me review what I have so far in case I made an error somewhere. When I first read the paper, I became stuck on the part of propagating d2 values up the tree. I think I finally figured it out by doing it like this:1) Calcularte local d2 values for all the smallest nodes (edge length 2 = 3 verts). 2) On the next highest level (edge length 4 = 5 verts) I take the maximum of the local d2 value and neighboring nodes at the lower level (calculated in step 1). When working on a 9x9 height field like the example in the paper I would let d2_0 = max(local d2_0,d2_1,d2_3,d2_5,d2_6) +++++++++     + + 1 + 2 +     + 0 +8     + + 3 + 4 +     +++++++++      + 5  6 + + +      +7++      +  + + +      ++++++ 3) Repeat step 2 until you reach the top node (edge length 8). Now let me go over the geomorphing problem. In the geomorphing section, the author states that nodes with an f value of >= 1/2 do not have children. This is not true in my version. In my case any node who's f < 1 can have children. This was how it was presented at the start of the paper. Maybe this is related to my problem? The real problem is that I don't understand which vertices can be safely morphed. Are you supposed to be morphing the edge centers which you were required to skip to avoid cracks in the first place? If I morph the vertex on the edge between nodes 0 and 7 above I will get cracks in the child nodes of 7 that also share this edge. This thing is really hard to explain... If possible, maybe you can be reach me by ICQ:593988158 to get a better response/code sample. Thanks for any advice you can give. IP: 
MarkW Member

posted February 02, 2000 11:46 AM
I see my ASCII artwork got messed up. You can see what it was supposed to look like at: http://voodoo.cyberwar.com/terrain/grid.jpg IP: 
MarkBatten Member

posted February 03, 2000 10:04 AM
OK, let's start at the beginning. I had great trouble with the propagation thing as well. One thing I see that you're doing wrong is that in propagating the values up the tree, you don't simply take the max; you compare the local value against each neighbor value multiplied by K (var described in the article). Then you store that maximum value, and propagate it to the corners (per the arrows in the diagrams in the article). So as values climb up the tree, they'll be multiplied by K several times. I also had trouble with the statement re "f>1/2 means no children," but it's just a theoretical point that you can safely ignore, IIRC. As perhaps a more direct answer, the process of calculating the blend values once you've built the quad tree is a very short recursive routine. If "matrix" is the array that stores the d2's, and "blends" is the array of morphing factors, the calculation of the f values (and therefore the geomorphs) goes like this: EvaluateTree(int x, int y, int dim) { float l,c1,f; int d2=dim>>1,d4=dim>>1; int ix=y*dim+x; l=Dist(x,y); //calculate distance from eye //to center of block c1=c*matrix[ix]; //c is from article if(c1<1)c1=1; f=l/(dim*C*c1); //formula from article if(f<1){ blends[ix]=(1x)*2; if(blends[ix]>1.0) blends[ix]=1.0; EvaluateTree(x+d4,y+d4,d2); EvaluateTree(xd4,y+d4,d2); EvaluateTree(xd4,yd4,d2); EvaluateTree(x+d4,yd4,d2); } else blends[ix]=0; } Then in rendering the tree you start with the center vertex and build the fan, examining the blend values of each of the four "child" vertices (x + or  dim/4, y+ or  dim/4) to determine whether those children need further subdivision. If they don't, you include the corner vertex in the fan, multiplying its z delta by the blend value of the central vertex. Yikes, that's not very clear. Let me know if this makes any sense or not. IP: 
MarkW Member

posted February 03, 2000 12:07 PM
I was multiplying by K. That was a mistake in the message I posted. Hmm... I just ignored that diagram with the progagated d2 values since it didn't make sense to me. The way it was described it the paper I thought you only propagate up the quadtree, not across nodes on the same level.What would be the point in progagating to the corners? When should I read those corner values back again since d2 values are per node (i.e center  not corner). Can you walk me through the first 2 levels of this process? So let's say I'm on the lowest level (nodes are 3x3 verts). I'm supposed to copy the local d2 value to the corners or take some max? What happens on the next level (5x5 verts). Hmm...looking back at the diagram I think I may be doing things totally wrong. When the paper states: "d2= max (local d2, K*d2 of adjacent blocks at the next lower level)" Does that really mean adjacent vertices? The diagram looks like he's taking values from the center vertex on each edge of the node. I was taking values from node centers of adjacent smaller blocks. See me original message/diagram for example. By the way, I really appreciate the time you're putting into helping me. IP: 
MarkW Member

posted February 03, 2000 01:42 PM
Another thing I noticed about your version. The author states "the blending value for a shared edge is obtained by taking the minimum of the blending values of the two involved blocks". You seem to just take the blending value of the node center vertex and ignore the neighboring nodes on the same level. I have a feeling both our implementations are not exactly what the author had in mind. But yours definitely looks closer than mine.IP: 
MarkBatten Member

posted February 03, 2000 02:47 PM
OK, let's see. First, you *do* propagate to the corners, as in the article, because vertices that are the corners for one block will be center vertices at the next (i.e. coarser) level up the tree.So the process goes like this. You start at the finest level of detail, as you're doing; I get there with another recursive routine that starts with the center vertex of the map, and then recurses to look at each child quadrant, etc. When you get to the "bottom," the 3x3 block, you don't have to calculate a d2 because it's zero by definition  there's no error when you're dealing with height field values. For a given x,y (center of the 3x3 vertices), you set that entry in your d2 matrix (matrix[x][y]=localval), and then propagate that value to the corners  which literally means, if the value stored in the corner array entry (e.g., matrix[x+dim/2][y+dim/2]) is less than the current local value, change the entry. OK. Now returning from your recursive routine up to the next higher level, having done all of the four child quadrants, you compare the locally calculated d2 with K times the d2 values stored in the matrix to the north, south, east, and west of the current center vertex (e.g., matrix[xdim/2][y]). Store the maximum at matrix[x][y], and propagate this value to the corners of this larger block, as described above. Re your second post, you *do* use the minimum blend of the two involved blocks when you're considering a vertex that is N,S,E, or W of the center vertex. So the rendering of a given block, in pseudocode and simplifying away edge cases and complications that come from building triangle fans, is something like b=blend[x][y] RenderVertex(x,y,b) RenderVertex(x+dim/2,y,min(b,blends[x+dim][y])) RenderVertex(x+dim/2,y+dim/2,no blending) etc., on around the fan. Hope this helps. I love this algorithm because despite its apparent complexity, it's actually tremendously simpler than a full ROAM implementation, runs as fast as any algorithm I've yet come across, and avoids a lot of the oddities that crop up in using the Lindstrom algorithm. The paper just isn't as clear as it should be (as is always the case; my hat is off to anyone who can create a competent dualqueue ROAM implementation based just on that paper). IP: 
MarkW Member

posted February 03, 2000 03:35 PM
Okay. I think I got it now. It will take me a while to digest/implement those changes. I'll get back to you if things don't work.One thing about your last message that may just be a misunderstaning  You say there is no d2 value for a 3x3 block? If I have 3 vertices on an edge, obviously I can drop the middle one and thus need a d2 value to measure the error. Maybe you really mean the 2x2 blocks (edge length 1) don't need d2 values? IP: 
MarkW Member

posted February 03, 2000 07:33 PM
Got more questions already.. ;)As I understand it, the blend value for a node comes from 5 possible sources (please correct anything that's wrong): 1)Center vertex of the node. 2)Minimum(Center vertex,Center vertex of Neighboring nodes on same level) for N,E,W,S. When there are no child nodes, I interpolate the center vertex of each edge using the value from 2) skipping the vertex if blend is 0. I interpolate the node center vertex with the value from 1). I don't interpolate the corner vertices of the node and use actual height field values. But what happens when there are child nodes? Do I draw all vertices that touch the child nodes at full resolution or still do some blending? IP: 
MarkBatten Member

posted February 04, 2000 08:20 AM
I'm not sure I understand this question, but here's a crack at it. When there are no child nodes, I agree with your description. When there are child nodes  which I check as I go around the fan by asking whether the blend value of each corner vertex is nonzero  I recurse: my noderendering algorithm calls itself with the corner vertex in question as the center. Does that answer the question?Also, re the 3x3 d2s, you may be right, although the visual effect is negligible unless you've got some wild heightfield data. IP: 
MarkW Member

posted February 04, 2000 12:30 PM
When you say corner vertex do you mean for example: x+dim/2,y+dim/2 or x+dim/4,y+dim/4. Assuming x,y is the parent's center and dim is the parent's edge length.In my system the child node center is at the dim/4 offset but the corner vertex of the parent (on the triangle fan edge) is on the dim/2 offset. For a concrete example, let's say I'm looking at the topleft node in the tree of edge length 4. (5x5 verts). It's center is at 2,2; corners are at 0,0 : 4,0 : 4,4 : 0,4. Child nodes are at 1,1 : 3,1 : 3,3 : 1,3. This is right out of figure 1 of the paper with x,y==0,0 in top left corner. Now let's say blend matrix value (3,1) is set to 1.0 so the top right child needs subdivision. When I render the parent fan (L shaped) would I render verts that touch the child (2,0)(2,2)(4,2) with actual height map values or still do some blend? If you blend (2,0) as the paper suggests ((b)*(actual height value) + (1b)(average height on edge)) you will get a different verex than the nonblended vertex of the child node. To fix this you would need to force the child's top left vertex (2,0) to the same value. I hope you're not getting tired on this discussion yet... It really feels like I'm pulling teeth here.. hehehe.. :) IP: 
MarkBatten Member

posted February 04, 2000 01:52 PM
I don't have my code in front of me (other computer), but I think you're right, i.e. x + or  d/4, y+ or  d/4 are the blend entries you check to see if further subdivision is needed.Sorry you feel like you're pulling teeth. I'm trying to be helpful... and I don't mind trying to help  I sure could have used it when I was putting this algorithm together. IP: 
MarkW Member

posted February 04, 2000 02:11 PM
By that comment I meant it must feel painful for you having to answer all these questions. I'll have more time to mess around with the code this weekend so hopefully I'll get it running with all the advice you've given me this week.IP: 
MarkW Member

posted February 06, 2000 11:36 AM
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.Now look at figure 2 of the paper: http://voodoo.cyberwar.com/terrain/fig2.gif When you are rendering the top right quadrant (6,2) and come to vertex (6,4) you need some way to know whether you should render it at the full height field value, skip it, or interpolate it with b. If the adjacent node's b==1 then you know it has children and therefore the vertex must be rendered at full detail. If the neighbor's b==0 you know to skip the vertex. Only when 0 < 0 < 1 can you safely interpolate the vertex with the minimum b of the 2 nodes. If you interpolate in any other case, you will get a crack because the child at (7,5) will use a noninterpolated value for vertex (6,4). Is this example clear? If so, there are a few issues I have no figured out yet: 1) Why do I get nodes with 0.5< f < 1 that have children. 2) How do you make the geomorphing fast. In the method described above I would need a lot of "if" statements when making the fan. I Need to test for b==1, b==0, etc. IP: 
Klaus Hartmann Member

posted February 06, 2000 09:43 PM
Mark Batten,I just had a look at your EvaluateTree code. This function looks like it has been taken from actual code. In this case... there's a bug in your code. The blend factor is "b = 2 * (1  f)" and not "b = 2 * (1  x)". If this is really a bug, then you must have had the most funny geomorphing  depending on the blocks xposition in the matrix IP: 
Klaus Hartmann Member

posted February 06, 2000 10:26 PM
Mark W.,I can answer about 80% of your geomorphing question. Maybe Mark Batten can then help to fix the other 20%. Before I start. The following does result in correct geomorphing without any cracks. The only problem with it is, that there's a situation in which popping still occurs. More precisely, this is the case, when a new child is born. However... if the minimum global resolution is relatively low, and the desired resolution is relatively high, then this popping effect is virtually invisible. IMO, this is by far good enough for a highquality game, because you would use similar resolution settings to achieve a real LOD effect (where large flat planes are represented by only a handful of fans). But then again, you gotta see yourself. In my implementation I work with something I dubbed a "fan mask". This fan mask tells me, which children of a parent node need to be rendered. A parent can have up to four children, and the following flags are used for the children of a parent node: 0x1: NW child needs to be rendered 0x2: NE child needs to be rendered 0x4: SE child needs to be rendered 0x8: SW child needs to be rendered Hence, if all 4 children need to be rendered, then the mask is 0xF. If only the southern children need to be rendered, then the mask is 0xC. You get the picture... Now about the morphing. For simplicity let's start with the center vertex. The center vertex may only be morphed, if the fan mask is 0xF (all children need to be rendered). For the center vertices on the edges I do the following. Let's take the northern vertex for example. The northern vertex may only be morphed, if the "fan mask & 0xC" of the northern block is equal to the "fan mask & 0x3" of the current block. In other words this means, that the southern part of the northern neighbor has the exact same subdivision as the northern part of the current block. After you've implemented this, you've got geomorphing without cracks. In order to fix the other problem (help please) we would need to morph corner vertices. This is against the rules in the paper, because it states "... there are up to five vertices where morphing might have to be performed". From that point of view, I believe that my geomorphing code is 100% complete, but it doesn't change the fact, that I'd like to remove this last cause for popping. I don't think that this is too difficult, but unfortunately I didn't have much time to think about it. BTW... I'm willing to share source, if you are also willing to do so. IP: 
Klaus Hartmann Member

posted February 06, 2000 10:41 PM
In my last post I made a mistake. I wrote this "fan mask & 0x3" and "fan mask & 0xC" stuff. This is, of course wrong... The northern vertex may only be morphed, if the southern part of the northern neighbor is not subdivided. I hope I got it right this time... it's kinda difficult to reproduce this from my code.IP: 
MarkBatten Member

posted February 07, 2000 09:07 AM
Klaus  Yes, it's 2*(1f). I just typed it wrong here. So the bug is the typing, not the code. Also, in my experience I agree with you that the remaining popping, if there is any, is very hard to detect, particularly in the heat of battle. MarkW  I don't know why nodes inside the range have children, but as it doesn't affect the implementation, I decided not to worry about it. Re question 2, checking for those cases doesn't slow things down that much. Klaus's method is interesting; I ought to go experiment with it. But I don't do it that way and I don't have cracks. The five vertices he refers to are the center and the noncorner vertices of each block. What I do to create the fan is start with the center vertex; then check the east vertex and render it with blend if necessary; then render the NE corner vertex (with no blending); then N; and so on around the node. If a child needs rendering as I go around, I end the fan, call the rendering routine recursively, and pick up with a new fan on return. IP: 
Klaus Hartmann Member

posted February 07, 2000 09:35 AM
Mark Batten,if you use a fan mask as I described above, then you don't need to "pick up with a new fan on return". The following should be faster, because it results in fewer fans: static ulong g_vertexOrder[] = { /* 0x0 */ 0, 0, /* 0x1 */ 3, 0, /* 0x2 */ 3, 2, /* 0x3 */ 5, 0, /* 0x4 */ 3, 4, /* 0x5 */ 0, 0, /* 0x6 */ 5, 2, /* 0x7 */ 7, 0, /* 0x8 */ 3, 6, /* 0x9 */ 5, 6, /* 0xA */ 0, 0, /* 0xB */ 7, 6, /* 0xC */ 5, 4, /* 0xD */ 7, 4, /* 0xE */ 7, 2, /* 0xF */ 9, 1, } The above table is indexed with the "fan mask << 1". The first value tells you the number of vertices you need to render, and the second is the first vertex (after the center). In order to render the vertices: vertexCount = g_vertexOrder[fanMask << 1]; vertex = g_vertexOrder[(fanMask << 1) + 1]; renderVertex(centerVertex); for (i = 0; i < vertexCount; i++) { renderVertex(vertex); vertex = (vertex + 1) & 7; } The vertex enumeration is as follows: Vertex #0 is the west vertex, vertex #1 is the northwest vertex, and so on (clockwise around the block). The only case where you need to "split" the fan is, if the fan mask is 0x5 or 0xA (two diagonally opposing patches). In this case you would call RenderFan twice: if (fanMask != 0) { if (fanMask == 0x5   fanMask == 0xA) { RenderFan(fanMask & 0x3); fanMask &= 0xC; } RenderFan(fanMask); } IP: 
Klaus Hartmann Member

posted February 07, 2000 10:46 AM
I uploaded a source file of my terrain renderer. It's only a single .CPP file that makes use of other files. But even without those other files it should be good enough to compare implementations. http://www.thecore.de/TheCore/TrArea.cpp The code is sometimes a bit messy, and the geomorphing is not optimized. It just doesn't make sense to optimize things that are not yet fully functional. IP: 
MarkW Member

posted February 08, 2000 12:44 AM
Mark Batten,From your last message: "then check the east vertex and render it with blend if necessary" How do you determine if it's necessary? I think Klaus and I are both looking at the neighbor node to the east and checking it's 2 west subchildren to see if they are subdivided. If they are subdivided, we don't morph the east vertex since it's shared with those 2 subchildren in the neighboring node. If you're doing the same thing, then I think we're all missing something from the paper. The paper hints at the fact that geomorphing should be free and can be derived just from the blend factors of your neighbors. Nowhere does it suggest you look at child nodes of your neighbors. This doubles the number of "if" statements for each potentially morphing vertex. Hmm... There's going to be a lot of terrain lectures at this year's Game Developer Conference in March. I think even the moderator of this forum will be presenting something. There will also be 3 guys from Westwood Studios who will demo their version of Rottger's algorithm. Hopefully I'll be able to ask them what the proper/fastest way is. I'll post anything I find out here. IP: 
MarkBatten Member

posted February 08, 2000 08:55 AM
Klaus  Interesting approach. I'll have to think about that in more detail. Thanks for the description.MarkW  I don't check the "two west subchildren." IIRC (again, code not in front of me) all I do is check the blend value of the east neighbor (in your example). So geomorphing is essentially free for me. I'm not sure more is required. IP: 
Klaus Hartmann Member

posted February 08, 2000 10:35 AM
Mark Batten,I hate asking this, but this whole geomorphing problem is beginning to be very frustrating. Please excuse if I ask the following question. Is there any way, that you could share your source code? I'm not talking about the complete implementation, but about the following: "Given a blend matrix, render and morph the vertices." This is basically the first time that I asked for source code. From that you can imagine how frustrated I am. IP: 
MarkW Member

posted February 08, 2000 11:27 AM
Klaus,I looked at your source and it looks almost the same as mine. The only difference is that I put a large switch statement into my rendering function which generates optimal fan(s) for each of the 16 possible childsubdivision combinations. The input to the switch is a code made of the 4 child nodes where each bit is set if the child is subdivided. It's similar to your "fan mask". I think most good compilers will convert the switch to a hash/lookup table. I noticed you're using the average terrain height in your distance calculations. If your game is ground based, it may be better to use the terrain height directly below your camera. That way you'll always get more detail as you get closer to the ground. The average height (as used in the paper) works better for flight sims.
IP:  