LoD error metrics and headache

2,555

Author

July 06, 2004 11:52 AM

so, after figuring out a great way to introduce twice the number of lods for gmm terrain the frustrating part begins. subdivision is kind of alternating like so:


even lods:  odd lods:  next even:
xxxxxxxxx xxxxxxxxx xxxxxxxxx
xx      x xx     xx xx  x  xx
x x     x x x   x x x x x x x
x  x    x x  x x  x x  xxx  x
x   x   x x   x   x xxxxxxxxx
x    x  x x  x x  x x  xxx  x
x     x x x x   x x x x x x x
x      xx xx     xx xx  x  xx
xxxxxxxxx xxxxxxxxx xxxxxxxxx

calculating the errors i get results that make me doubt my sanity. not only would pairs like the first two examples end up with the same max error most of the time, i sometimes even get situations where the first has a SMALLER error than the second and everything inside me goes "thats not possible". it has more points (ok, just one in this case) and twice the triangles. so basically my error calculation must be completely whack (iterating over all levels and points, comparing the interpolated value to the real value with and without the central value and according to the triangle configuration). so: is there really a possibility for strange results like that? why does simple distance based selection give much better results and why did i do all the extra work to get error pairs that effectively skip every second level? just in case someone is feeling bored and feels to desire for a medium headache:


for (int lvl=1; lvl <= numLevels>>1; ++lvl) {
  int step=1<<lvl;
		
  for (int pat=0; pat<numPtch*numPtch; ++pat) {
	for (int iz=0; iz<PS; ++iz)
	for (int ix=0; ix<PS; ++ix) {
		float relx=(float)(ix%step)/step;
		float relz=(float)(iz%step)/step;

		int seg_x=ix/step, seg_z=iz/step;
		int seg_left=seg_x*step + Patches[pat].x;
		if (ix==PS-1) {seg_left-=step; relx=1;}
		int seg_right=seg_left+step;
		int seg_top=seg_z*step + Patches[pat].z;
		if (iz==PS-1) {seg_top-=step; relz=1;}
		int seg_bottom=seg_top+step;
				
		float y=Heightmap[(Patches[pat].z+iz)*MapSize + Patches[pat].x+ix];
	        float tl=Heightmap[seg_top*MapSize + seg_left];
		float tr=Heightmap[seg_top*MapSize + seg_right];
		float bl=Heightmap[seg_bottom*MapSize + seg_left];
		float br=Heightmap[seg_bottom*MapSize + seg_right];
		float mid=Heightmap[(seg_top+(step>>1))*MapSize + seg_left+(step>>1)];

		float height_odd=-1, height_even=-1;

		if (relx<=relz) {
			if (relz<=1-relx) height_odd=tl + relz*(bl-tl) + 2*relx*(mid - .5f*(tl+bl)); //left
			else height_odd=bl + relx*(br-bl) + 2*(1-relz)*(mid - .5f*(bl+br)); //bottom
		}
		else {
			if (relz<=1-relx) height_odd=tl + relx*(tr-tl) + 2*relz*(mid - .5f*(tr+tl)); //top
			else height_odd=tr + relz*(br-tr) + 2*(1-relx)*(mid - .5f*(tr+br)); //right
		}

		bool bl2tr=!((seg_x%2) ^ (seg_z%2));

		if (bl2tr) {
			if (relz<=1.0f-relx) height_even=tl + relx*(tr-tl) + relz*(bl-tl); //topleft
			else height_even=tr + (1-relx)*(bl-br) + (relz)*(br-tr); //botright
		}
		else {					
			if (relx<=relz) height_even=tl + relx*(br-bl) + relz*(bl-tl); //botleft
			else height_even=tl + relx*(tr-tl) + relz*(br-tr); //topright
		}

		float error=height_even-y;
		if (error<0) error=-error;
		if (error > Patches[pat].Error[2*lvl])
		        Patches[pat].Error[2*lvl]=error;
				
		error=height_odd-y;
		if (error<0) error=-error;
		if (error > Patches[pat].Error[2*lvl -1])
			Patches[pat].Error[2*lvl -1]=error;
	}
  }
}

for those with gf fx or newer radeon: http://festini.device-zero.de/Programming/Downloads/jstart.zip relevant console commands: terloddistance (toggle distance/error based lod) tersetthreshold (set threshold for error based) tersetlodstep (set stepwidth for distance based) terdrawwater (toggle the annoying water on/off) wireframe (toggle wireframe) page up/down scrolls the console or moves up/down cursor keys move, middle mouse frees cursor config.cfg contains a few settings autoexec.csf contains console commands to be run at start up other commands: terloadmap <file> <size> <patchsize> (loads a map, 16bit raw file of size+1 ^2 dimension, size and patchsize should be power of 2) tercreatemap (create random terrain, most likely broken by now) teruselod (toggle lod on/off, when off tersetlod sets global lod) camsetviewdistance (obvious) camsetfov (also obvious) i definitely need to add a help <command> command. the map used is from the far cry demo for better comparison. fake detail textures can be enabled by "inverting" the comments in terrain.psh

f@dzhttp://festini.device-zero.de

Buzzy

312

July 06, 2004 02:25 PM

I can't seem to make the console go away. In config.cfg it's bound to the ^ key (caret), but that doesn't work. Changing it to something else doesn't seem to work either (P, ~, `, -). And there are no console commands to make it go away. I'd love to look at this, but all I see is a buncha blue with a bit of moving stuff through it. :P

--Buzzy

Promit

13,404

July 06, 2004 03:07 PM

Quote:Original post by Trienco

even lods:  odd lods:  next even:xxxxxxxxx xxxxxxxxx xxxxxxxxxxx      x xx     xx xx  x  xxx x     x x x   x x x x x x xx  x    x x  x x  x x  xxx  xx   x   x x   x   x xxxxxxxxxx    x  x x  x x  x x  xxx  xx     x x x x   x x x x x x xx      xx xx     xx xx  x  xxxxxxxxxxx xxxxxxxxx xxxxxxxxx

Ok, now it's my turn to help you [wink] I used quad cutting LoD instead of half cutting LoD, so I'm sort of thinking out "loud" here. Bear with me. (I'm also ignoring your implementation, as it looks like an MFH (Mess From Hell)).

Let's look at the high detail sample.

      |      |  xxxxxxxxx  xx  x  xx  x x x x x  x  xxx  x--xxxxxxxxx--  x  xxx  x  x x x x x  xx  x  xx  xxxxxxxxx      |      |

I've used lines to mark the 4 "critical" vertices. These are the vertices that are removed when shifting down to the next LoD.

xxxxxxxxx xx     xxx x   x xx  x x  xx   x   xx  x x  xx x   x xxx     xxxxxxxxxxx

Right, so here we are, without the 4 critical vertices of the pervious LoD. We've introduced 4 errors at this point, one for each vertex removed. We need to calculate the 4 errors, take the maximum of those 4, and take that as the error of this "microblock". From all of the microblock errors in a patch, you will choose the highest one as your maximum patch error value for GMM.

Let's look at the errors.

xxxxxxxxxxx     xxx x   x xx  x x  xx   x   xx  x x  xx x   x xxx     xxxxxxxxxxx    |

Marked is a spot where there usd to be a critical vertex, and where we have now lost a vertex and gained an error. Where does this error manifest? Well, the bottom row of this ASCII art, or the bottom of the bottom triangle, is where our vertex's detail has been replaced by an interpolation. We need to calculate the difference between this interpolation and the actual vertex value.
The interpolation value is simple. The bottom line is a single straight line, so the height at the critical vertex's location is equal to the average height of the bottom left vertex and the bottom right vertex of this microblock. Compare that against the critical vertex's value, and you've got an error value. Do that x 4 for each side of our microblock, take a maximum, and BAM! We've got a net world space error for this microblock.

Let's slide down another LoD, just for practice.

xxxxxxxxxxx     xxx x   x xx  x|x  xx   x   xx  x x  xx x   x xxx     xxxxxxxxxxx

There is just 1 critical vertex here, dead center. The removal of this single vertex actually creates 2 errors, one for each diagonal of the microblock. We're going to do the exact same thing as before, except on the diagonals. So for this LoD change, we get two errors for this microblock. One is the error between the lower left and the upper right. Calculate the average height of the two, then get the difference from the actual vertex height. Same thing for the error created between the upper left and the lower right. Take the max of the two, and we've got our microblock error for this LoD.

I've given you the algorithm, but unfortunately for you, you get to code it, not me. Hope that helps [smile]

(Incidentally, I probably wouldn't have spent the good 30-45 mins it took me to reason through and type this had it not been for the help you gave me while trying to kick my engine into overdrive. Good deeds really do come back, don't they?)

SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.

Trienco

2,555

Author

July 07, 2004 02:06 AM

Quote:Original post by Buzzy
I can't seem to make the console go away. In config.cfg it's bound to the ^ key (caret), but that doesn't work. Changing it to something else doesn't seem to work either (P, ~, `, -). And there are no console commands to make it go away. I'd love to look at this, but all I see is a buncha blue with a bit of moving stuff through it. :P

--Buzzy

ok, the way im handling that is pretty crappy and dependend on your keyboard layout. ^ should be the key left of the 1 (might be a ~ in your case.. i think those two are switched). also no keys usable for console input can be used (letters, numbers, enter, etc.)

try setting LEFT_STRING

or others:

if (key=="KEY_A") return 'A';	if (key=="KEY_B") return 'B';	if (key=="KEY_C") return 'C';	if (key=="KEY_D") return 'D';	if (key=="KEY_E") return 'E';	if (key=="KEY_F") return 'F';	if (key=="KEY_G") return 'G';	if (key=="KEY_H") return 'H';	if (key=="KEY_I") return 'I';	if (key=="KEY_J") return 'J';	if (key=="KEY_K") return 'K';	if (key=="KEY_L") return 'L';	if (key=="KEY_M") return 'M';	if (key=="KEY_N") return 'N';	if (key=="NUM_O") return 'O';	if (key=="KEY_P") return 'P';	if (key=="KEY_Q") return 'Q';	if (key=="KEY_R") return 'R';	if (key=="KEY_S") return 'S';	if (key=="KEY_T") return 'T';	if (key=="KEY_U") return 'U';	if (key=="KEY_V") return 'V';	if (key=="NUM_W") return 'W';	if (key=="KEY_X") return 'X';	if (key=="KEY_Y") return 'Y';	if (key=="KEY_Z") return 'Z';	if (key=="KEY_^") return '^';	if (key=="KEY_~") return '~';	if (key=="KEY_0") return '0';	if (key=="KEY_1") return '1';	if (key=="KEY_2") return '2';	if (key=="KEY_3") return '3';	if (key=="KEY_4") return '4';	if (key=="KEY_5") return '5';	if (key=="KEY_6") return '6';	if (key=="KEY_7") return '7';	if (key=="KEY_8") return '8';	if (key=="KEY_9") return '9';	if (key=="KEY_.") return '.';	if (key=="KEY_,") return ',';	if (key=="KEY_-") return '-';	if (key=="NUM_0") return GLFW_KEY_KP_0;	if (key=="NUM_1") return GLFW_KEY_KP_1;	if (key=="NUM_2") return GLFW_KEY_KP_2;	if (key=="NUM_3") return GLFW_KEY_KP_3;	if (key=="NUM_4") return GLFW_KEY_KP_4;	if (key=="NUM_5") return GLFW_KEY_KP_5;	if (key=="NUM_6") return GLFW_KEY_KP_6;	if (key=="NUM_7") return GLFW_KEY_KP_7;	if (key=="NUM_8") return GLFW_KEY_KP_8;	if (key=="NUM_9") return GLFW_KEY_KP_9;	if (key=="NUM_/") return GLFW_KEY_KP_DIVIDE;	if (key=="NUM_*") return GLFW_KEY_KP_MULTIPLY;	if (key=="NUM_-") return GLFW_KEY_KP_SUBTRACT;	if (key=="NUM_+") return GLFW_KEY_KP_ADD;	if (key=="NUM_.") return GLFW_KEY_KP_DECIMAL;	if (key=="NUM_=") return GLFW_KEY_KP_EQUAL;	if (key=="NUM_ENTER") return GLFW_KEY_KP_ENTER;	if (key=="LEFT_SHIFT") return GLFW_KEY_LSHIFT;	if (key=="RIGHT_SHIFT") return GLFW_KEY_RSHIFT;	if (key=="LEFT_CTRL") return GLFW_KEY_LCTRL;	if (key=="RIGHT_CTRL") return GLFW_KEY_RCTRL;	if (key=="LEFT_ALT") return GLFW_KEY_LALT;	if (key=="RIGHT_ALT") return GLFW_KEY_RALT;	if (key=="TAB") return GLFW_KEY_TAB;	if (key=="ENTER") return GLFW_KEY_ENTER;	if (key=="CURSOR_UP") return GLFW_KEY_UP;	if (key=="CURSOR_DOWN") return GLFW_KEY_DOWN;	if (key=="CURSOR_LEFT") return GLFW_KEY_LEFT;	if (key=="CURSOR_RIGHT") return GLFW_KEY_RIGHT;	if (key=="BACKSPACE") return GLFW_KEY_BACKSPACE;	if (key=="DELETE") return GLFW_KEY_DEL;	if (key=="INSERT") return GLFW_KEY_INSERT;	if (key=="HOME") return GLFW_KEY_HOME;	if (key=="END") return GLFW_KEY_END;	if (key=="PAGEUP") return GLFW_KEY_PAGEUP;	if (key=="PAGEDOWN") return GLFW_KEY_PAGEDOWN;	if (key=="ESCAPE") return GLFW_KEY_ESC;	if (key=="SPACE") return GLFW_KEY_SPACE;	if (key=="MOUSE_LEFT") return 350;	if (key=="MOUSE_RIGHT") return 351;	if (key=="MOUSE_MIDDLE") return 352;	if (key=="MOUSE_X") return 0;	if (key=="MOUSE_Y") return 1;	if (key=="MOUSE_Z") return 2;

f@dzhttp://festini.device-zero.de

Trienco

2,555

Author

July 07, 2004 02:31 AM

Quote:Original post by Promit
Ok, now it's my turn to help you [wink] I used quad cutting LoD instead of half cutting LoD, so I'm sort of thinking out "loud" here. Bear with me. (I'm also ignoring your implementation, as it looks like an MFH (Mess From Hell)).

you should see the function to create the index buffers with its tons of special cases and variations (the "direction" for even lods must alternate, odd lods are handles differently and depending on cutout combinations single corner triangles are needed)

Quote:
Let's look at the high detail sample.
      |      |  xxxxxxxxx  xx  x  xx  x x x x x  x  xxx  x--xxxxxxxxx--  x  xxx  x  x x x x x  xx  x  xx  xxxxxxxxx      |      |
I've used lines to mark the 4 "critical" vertices. These are the vertices that are removed when shifting down to the next LoD.
xxxxxxxxx xx     xxx x   x xx  x x  xx   x   xx  x x  xx x   x xxx     xxxxxxxxxxx

for a moment i went "duh, of course, im forgetting these 4. but then i noticed these two are different step sizes.

in fact the above example would use a smaller step size, reducing one "segment" to case 1 (or just horz flipped to make it alternate).

so all segments are either looking like the lowest lod for a patch (two triangles) or the second lowest (adding one point in the center, four triangles). yet, it seems this center point isnt making a difference to the max error in most cases.

i think i should explain some of the terms im using (as they are all made up).

PS is the patchsize, here 33. inconsistent i notice, as patchsize is 32 and mapsize is 1025 instead of 1024.

step is the distance between two points for an even lod (or and odd one ignoring the one in the middle). a segment is a square with size step (ie the "quad" you get when ignoring all skipped points). seg_left, etc. are the global coordinates in the heightmap (ie seg_left is the global x coord for the left side).

relx is the relative distance into a segment (ie for x=4 with a step size of 8 it is .5).
when reaching the right or bottom side of the map i need to set it to 1 (1 is usually never reached as its treated as 0 for the next segment.. at these two edges they need to be set to 1 to prevent being out of bounds with the right or bottom side of a segment.. so its forcing the exception of using the left or top segment when reaching the edge).

tl=topleft, br=bottomright, etc. are the height values at the corners of a segment. mid is the height in the center.

the loop is only going over half the levels, starting with 1 (level 0 never has errors) and handles 2 consecutive levels at once (ie. 1 and 2 use the same step size, 1 simple adds the center point and needs to interpolate differently).

all the ugly if's..
for odd levels, its four triangles meeting in the center, so the left,top,right,bottom triangle are interpolated depending on where the real coordinate is. you get that by adding the patch internal ix, iz to the patch offset x,z.

bl2tr is just used to decide in which direction the quad is divided.
where you are is decided by the relative positions, as you can say if the diagonal is going from topleft to bottom right and relx<relz then youre in the bottom left triangle, else youre past the diagonal and in the top right.

the rest is just getting the difference between two corners and interpolating. height at corner you start + interpolated height difference in x direction + interpolated height difference in z direction.

hm, need to check that the start is consistent with the rest..

what i hate about error calculation is that its a pain to debug and always works great for the small test cases where you can afford to track each step.

errors for patch 512 end up like this:
0, 8, 8, 12, 12, (annoying but right order so far)
16, 14, 16, 15, (wtf?)
32, 32

f@dzhttp://festini.device-zero.de

Buzzy

312

July 07, 2004 03:19 AM

Okay, I did some thinking on this and what you say makes sense to me. It would be possible, and probably quite common for a higher LOD to have a higher error metric than its children, so to speak. Consider my little picture.

On the left is the highest LOD. When taking a step down, the vertices circled with red are going to disappear, to make the middle picture. Then the blue vertex disappears to make the right one. But if you do your error metric calculations based on
how much change each vertex has to move to get to the next LOD, then look at what happens when the red vertices have a very high distance to move compared to the blue in the middle.

If you're picking your LOD based on all the error metrics, then yes, have levels 1 to 2 higher than levels 2 to 3 seems odd, and it would screw things up. I'd recommend having each chunk know its level (obviously) but only compare itself to neighboring levels. So when your at level 1, you're only waiting until you are within range to switch to 2, and not even look at the metric between 2 and 3 until you're at two.

BTW, I didn't thoroughly read through your last post so I'm not sure if your problem changed, or if this post'll even help, but here's hoping!

--Buzzy

Trienco

2,555

Author

July 07, 2004 04:29 AM

Quote:Original post by Buzzy
BTW, I didn't thoroughly read through your last post so I'm not sure if your problem changed, or if this post'll even help, but here's hoping!

--Buzzy

dont worry, i just tried a rough explanation of the source.

i found a few suspicious places and could figure how single points have a bigger error in a higher lod. i somehow though that this is limited to single samples and made up for by other samples where the lower lod has even bigger errors (correcting the max).

after trying to average the errors for a single segment and still having "flipped" values (but for a weird reason a little less popping) i changed to a metric that should be worthless, yet works best so far in combination with your suggestion of changing only in one level steps. i average all errors over the whole patch. the few samples then had continous errors for different levels (yet, your idea prevents iterating over all levels when just checking if going one up/down is enough.. ill do the same for distance once i can figure out how to calculate the distances for a given lod with my weird scheme).

i uploaded the new exe and updated the archive

if you just get the exe, the error threshold must be changed to .45 in the autoexec.csf or console.

still a little popping in some places, but i guess with reduced view distance, a little fog and hopefully some vegetation to hide it that should work well. and maybe i should keep telling myself "far cry popped like crazy and i should expect to easily get it much better".

f@dzhttp://festini.device-zero.de

Promit

13,404

July 07, 2004 02:06 PM

Quote:Original post by Trienco
errors for patch 512 end up like this:
0, 8, 8, 12, 12, (annoying but right order so far)
16, 14, 16, 15, (wtf?)
32, 32

Uh...why are those integers?

SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.

Trienco

2,555

Author

July 08, 2004 12:59 AM

Quote:Original post by Promit
Quote:Original post by Trienco
errors for patch 512 end up like this:
0, 8, 8, 12, 12, (annoying but right order so far)
16, 14, 16, 15, (wtf?)
32, 32

Uh...why are those integers?

because my maps use 16bit height values and i dont divide the values until the end (not to mention that these values are much nicer than 0.0032425 and such. the variables are floats, but the errors in this case dont have fractions.

f@dzhttp://festini.device-zero.de

LoD error metrics and headache

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

LoD error metrics and headache

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines