GeoMipMap Implementation

Recommended Posts

Share on other sites
Splitting the terrain up into patches is the right thing to do, but one of the drawbacks to geomipmapping is that each patch requires a draw call, even if it is only two triangles. Try a patch size of 65x65 or 129x129. Those would cut the number of draw calls by a factor of 4 or 16.

I don't understand what you mean by, "create the strokes next to terrain chunks to smooth the transition to another MipMap level". Are you talking about geomorphing? That is fairly easy to do with geomipmapping.

Share on other sites
I wrote some stuff up, but that was a long time ago, and the implementation has since been redone and refined.

Skimming over what I wrote back then, these are the changes that come to mind:
* Vertex buffers are allocated 4 MB at a time, rather than assigning one to each patch. I feed in as many patches as possible to each buffer.
* The indices for each patch are cached after being crack-patched. This consumes a fair bit of memory, but saves a lot of computation. the exact figures depend on details, but you're looking at about 12M total for a 1025 square terrain using tri-lists. That's system memory, not video.
* Index generation incorporates cache priming now.
* I believe the quadtree generation is less stupid now.
* Patches are 65x65 and arranged in memory in super-squares of 2x2. A super square constitutes one draw call, no matter how many of its patches are visible. The number of super squares visible on screen sets your draw call count per pass, and that figure will depend on view distance, FoV, and scaling size.

Share on other sites

I'm not sure what you mean by "patch", can a patch consist out of multiple chunks of terrain that have different MipMap Levels?

If it can not then wouldn't it be inefficient to increase the size of the patch since the chance of being able to choose a high MipMap level would decrease?

If it can then wouldn't this mean the index or vertex buffer needs to be dynamicly changed at run time?

I was not talking about geomorphing. I was talkingn about making the transitions between two chunks of heightmap that have a different GeoMipMapLevel. De Boers paper solves this problem by using triangle fans, are these fans supposed to be created using a seperate index buffer and rendered with a seperate DrawIndexedPrimitive?

Share on other sites
One patch is one LoD unit. So a 65x65 patch can be rendered as 65x65, 33x33, 17x17, or 9x9. There's a delicate balance involved in terms of LoD resolution versus work load. A larger patch size is more friendly to the graphics hardware, but detrimental to the effectiveness of the LoD. 129x129 is the largest you can fit in unsigned short indices.

My experimentation showed that 129 was too big, and 65 was slightly preferable to 33. Anything smaller than 33 is just silly. It's a compile time constant in any case, so it can be tweaked without too much trouble.

And the indices are completely dynamic. This isn't really a big deal, because graphics cards don't generally store index buffers in their video memory at all. Static or dynamic, it doesn't matter. Read the crack patching part of the implementation details (linked in previous) for the fans answer. To cut a long story short, they're patched dynamically into the per-patch index buffer and cached.

Share on other sites
I was just reading the topic you posted and It's just what I was looking for. Thanks for explaining the patch definition you really helped me out.

Kind Regards,

Quinnie

Share on other sites
Hey,

After carefully studying your code in the thread you linked earlier, and making a ton of sketches in paint I came up with the following result. Note that I'm using an index triangle strip instead of the index triangle list that was used in your code.

One of my sketches showing a 9x9 patch with all sides up one MipMap Level.

The corresponding index buffer that came out of my algorithm, the numbers relate to the vertices starting from the bottom left to the upper right.
0, 0, 18, 2, 10, 2, 11, 4, 12, 4, 13, 6, 14, 6, 15, 8, 16, 8, 26, 26,
18, 18, 18, 10, 19, 11, 20, 12, 21, 13, 22, 14, 23, 15, 24, 16, 25, 26, 26, 26,
18, 18, 36, 19, 28, 20, 29, 21, 30, 22, 31, 23, 32, 24, 33, 25, 34, 26, 44, 44,
36, 36, 36, 28, 37, 29, 38, 30, 39, 31, 40, 32, 41, 33, 42, 34, 43, 44, 44, 44,
36, 36, 54, 37, 46, 38, 47, 39, 48, 40, 49, 41, 50, 42, 51, 43, 52, 44, 62, 62,
54, 54, 54, 46, 55, 47, 56, 48, 57, 49, 58, 50, 59, 51, 60, 52, 61, 62, 62, 62,
54, 54, 72, 55, 64, 56, 65, 57, 66, 58, 67, 59, 68, 60, 69, 61, 70, 62, 80, 80,
72, 72, 72, 64, 74, 65, 74, 66, 76, 67, 76, 68, 78, 69, 78, 70, 80, 80, 80, 80,

Now everything seems to working fine however I'm worried that there are problems because not all triangles are CW and CCW correctly. Is there some way to get around this?

Thanks in advance and Kind Regards,

Quinnie

Share on other sites
Tell me how you figured out these indices, and I shall be your sex slave :) I can't figure it out

Share on other sites
Quote:
 Original post by QuinnieNow everything seems to working fine however I'm worried that there are problems because not all triangles are CW and CCW correctly. Is there some way to get around this?
Hmm. You know, I'm not sure. The way I modified the trilists, the winding was never changed. For a triangle strip, the winding naturally alternates, and the hardware is aware of this. So if you look at a triangle strip's winding, all the even triangles will be CW and the odd ones will be CCW (or vice versa). I believe that this alternation is applied regardless of degenerates as well, so you want to generate windings as CW, degen, CW or CCW, degen, CCW. If the original winding order is preserved after patching, then you're fine. If it's not, you're probably going to have problems with backface culling.

By the way, I really like that sketch.

Share on other sites

The backface culling might indeed become a problem. Some minutes ago in another topic on gamedev I read that someone added aditional vertices to solve this problem. Frankly I'm to tired now to recheck my code but I'll do so tomorrow. Again thanks alot for your advise and help, I hope I can show you some screenshots soon!

Quote:
 Original post by i_luv_cplusplusTell me how you figured out these indices, and I shall be your sex slave :) I can't figure it out

It didn't take me that as long as I expected it, but I can advise you to make a lot of sketches. Also check out the topic Promit linked earlier it's a great help. As I said earlier I'm planning to make this project open source so I'll post some snippits of my code here. Note that there may still be some issues regarding the CW and CCW thing and other problems that might occur, since I only just started coding it and I had no chance to test it yet. Also this code can probably be optimised a lot better but I didn't had a chance to do so just yet.

Some macro defenitions I use throughout the code (Note you'll have to include math.h)
#define ROWOFFSET1 (Row + 0) * Dimensions * pow(2, GeoMipMapLevel)#define ROWOFFSET2 (Row + 1) * Dimensions * pow(2, GeoMipMapLevel)#define COLOFFSET1 ((Col - 0) / 2) * pow(2, GeoMipMapLevel)#define COLOFFSET2 ((Col - 1) / 2) * pow(2, GeoMipMapLevel)#define NUMROWS ((Dimensions - 1) / pow(2, GeoMipMapLevel))#define NUMCOLS ((2 + 2 * Dimensions) - (2 * Dimensions - 2) * (1 - pow(2.0f, GeoMipMapLevel * -1)))#define YVERTEX(i) (int)(i / Dimensions)#define XVERTEX(i) (i - (int)(i / Dimensions) * Dimensions)#define ADJUSTEDINDEX1 (int)(YVERTEX(Buffer[i]) / pow(2.0f, AdjustingMipMapLevel) + 1) * pow(2.0f, AdjustingMipMapLevel) * Dimensions#define ADJUSTEDINDEX2 (int)(XVERTEX(Buffer[i]) / pow(2.0f, AdjustingMipMapLevel) + 1) * pow(2.0f, AdjustingMipMapLevel)typedef unsigned int USINT;

The function used to create the plain patch without any stiching on the sides.
VOID CreateTerrainIndexBuffer(INT Dimensions, INT GeoMipMapLevel, USINT* Buffer){	// Variable For Looping Through The Buffer	int i = NULL;	// Algorithm For Calculating Indices 	for (int Row = 0; Row < NUMROWS; Row++)	{		Buffer[i] = ROWOFFSET1; i++;		for (int Col = 0; Col < NUMCOLS - 2; Col++)		{			if (Col % 2 == 0) {Buffer[i] = ROWOFFSET1 + COLOFFSET1; i++;}			else {Buffer[i] = ROWOFFSET2 + COLOFFSET2; i++;}		}		Buffer[i] = ROWOFFSET2 + Dimensions - 1; i++;	}	return;}

The functions used to apply a MipMapLevel to the sides of a previously created index buffer to apply the stiching
VOID AdjustLeftMipMapLevel(INT Dimensions, INT GeoMipMapLevel, INT AdjustingMipMapLevel, USINT* Buffer){	// Algorithm For Adjusting The Left Stroke Of An Index Buffer For A Lower MipMap Level	for (int i = 0; i < NUMROWS * NUMCOLS; i++)	{		if (YVERTEX(Buffer[i]) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && XVERTEX(Buffer[i]) == 0)			Buffer[i] = ADJUSTEDINDEX1;	}	return;}VOID AdjustRightMipMapLevel(INT Dimensions, INT GeoMipMapLevel, INT AdjustingMipMapLevel, USINT* Buffer){	// Algorithm For Adjusting The Right Stroke Of And Index Buffer For A Lower MipMap Level	for (int i = 0; i < NUMROWS * NUMCOLS; i++)	{		if (YVERTEX(Buffer[i]) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && XVERTEX(Buffer[i]) == Dimensions - 1)			Buffer[i] = ADJUSTEDINDEX1 + Dimensions - 1;	}	return;}VOID AdjustLowerMipMapLevel(INT Dimensions, INT GeoMipMapLevel, INT AdjustingMipMapLevel, USINT* Buffer){	// Algorithm For Adjusting The Lower Stroke Of And Index Buffer For A Lower MipMap Level	for (int i = 0; i < NUMROWS * NUMCOLS; i++)	{		if (XVERTEX(Buffer[i]) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && YVERTEX(Buffer[i]) == 0)			Buffer[i] = ADJUSTEDINDEX2;	}	return;}VOID AdjustUpperMipMapLevel(INT Dimensions, INT GeoMipMapLevel, INT AdjustingMipMapLevel, USINT* Buffer){	// Algorithm For Adjusting The Upper Stroke Of And Index Buffer For A Lower MipMap Level	for (int i = 0; i < NUMROWS * NUMCOLS; i++)	{		if (XVERTEX(Buffer[i]) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && YVERTEX(Buffer[i]) == Dimensions - 1)			Buffer[i] = ADJUSTEDINDEX2 + Dimensions * (Dimensions - 1);	}	return;}

A sample using the above functions to create the index buffer I posted earlier
        // Constant Values        const int Dimensions = 9;        const int GeoMipMapLevel = 0;        // Create A Buffer For The Indices        unsigned int* Buffer = new unsigned int [NUMROWS * NUMCOLS];        // Fill The Buffer With The Basic Patch        CreateTerrainIndexBuffer(Dimensions, GeoMipMapLevel, Buffer);        // Adjust All Strokes To MipMapLevel 1        AdjustUpperMipMapLevel(Dimensions, GeoMipMapLevel, 1, Buffer);        AdjustLeftMipMapLevel (Dimensions, GeoMipMapLevel, 1, Buffer);        AdjustRightMipMapLevel(Dimensions, GeoMipMapLevel, 1, Buffer);        AdjustLowerMipMapLevel(Dimensions, GeoMipMapLevel, 1, Buffer);        // The Buffer Is Finished Now And Can Be Used With Either The DirectX Or OpenGL Functions        // Delete The Buffer        delete Buffer;

Share on other sites
Quote:
Original post by Quinnie
Quote:
 Original post by i_luv_cplusplusTell me how you figured out these indices, and I shall be your sex slave :) I can't figure it out

... Note that there may still be some issues regarding the CW and CCW thing

It may not be the most elegant solution, but here is a simple algorithm for generating the indexes while maintaining CW/CCW.

Using you example grid above...

First, generate the indexes as if you are stripping a standard grid:
         0,  9,  1, 10,  2, 11,  3, 12,  4, 13,  5, 14,  6, 15,  7, 16,  8, 17, 17,     9,  9, 18, 10, 19, 11, 20, 12, 21, 13, 22, 14, 23, 15, 24, 16, 25, 17, 26, 26,    18, 18, 27, 19, 28, ...
Next, instead of removing vertexes, you move them. According to the diagram, the following vertexes are moved like this:
    From    To      1      2      3      4      5      6      7      8      9     18     17     26     27     36
Finally, replace the indexes of the moved vertexes with the indexes of the vertexes they are moved to:
         0, 18,  2, 10,  2, 11,  4, 12,  4, 13,  6, 14,  6, 15,  8, 16,  8, 26, 26,    18, 18, 18, 10, 19, 11, 20, 12, 21, 13, 22, 14, 23, 15, 24, 16, 25, 26, 26, 26,    18, 18, 36, 19, 28, ...
The removed triangles are still in the strip, but are not drawn because they are now degenerate. It results in the same number of triangles, but that is not an issue.

Share on other sites
Hey,

thanks for the reply JohnBolton that is actually the same way I implemented my algorithms above and your right that it does indeed not cause any problems with the CW and CCW thing. :D

I implemented my code in my engine and got some screenshots for you guys to look at. I did not yet create a system to calculate the correct mipmaplevel but I'll do so as quickly as possible.

The terrain patches all got the same heightmap data, the heightmap itself is just a plane with a cricle in the middle thats a bit bumpy, its a bit ugly because a friend of mine had to create in a couple of seconds.

The screenshots shows the entire terrain in LOD level 2 and one patch in LOD level 0. You can see the stitching in progress and it seems to work nicely.

I did not yet implement any splatting so its plain white and black :P

Thanks for all the help again :D

Share on other sites
I would like to point out something here.

See the problem? I'm still trying to figure out what causes this. I noticed it in my own code at one point, but I'm not sure it's there after later tweaks. I haven't really looked.

[Edited by - Promit on May 11, 2007 5:40:13 PM]

Share on other sites
Quote:
 Original post by JohnBoltonIt may not be the most elegant solution, but here is a simple algorithm for generating the indexes while maintaining CW/CCW.

Does your solution work with triangle strips or normal triangles only?

+rated

Share on other sites
Quote:
 Original post by PromitI would like to point out something here.See the problem? I'm still trying to figure out what causes this. I noticed it in my own code at one point, but I'm not sure it's there after later tweaks. I haven't really looked.

Hmm I didn't noticed that, however when I enable splatting it still covers the entire area so I'm not sure if it'll be a problem?

Besides that I'm having some difficulties calculating the errors for each patch. I'm trying to follow de Boers equations but I'm having some difficulties implementing them, I would be very greatfull if anyone could help me with the following questions.

First of all the equations as give my de Boer:
Quote:
 Dn = |d| · CEquation 1: Use this equation to calculate Dn for d. C isa constant which can be calculated using theequation found in Equation 1a)C = A / TEquation 1a), used to calculate C. A and T are constantswhich can be calculated using the equations found in 1b)and 1c) respectively.A = n / |t|Equation 1b), used to calculate A. n is the near clippingplane,and t is the top coordinate of the near clippingplane,as in (l, r, b, t, n, f).T = (2 * Treshold) / VresEquation 1c), used to calculate T. vres is the verticalscreen resolution in pixels.

And these are the settings I'm using:
Quote:
 FoV = PI / 4Aspect Ratio = 1.0fNear Clipping Plane = 0.1fFar Clipping Plane = 2000.0fVertical Resolution = 1280.0fTreshold = 5

First I assumed Vres is the screen resolution and not the backbuffers width, in my test case this would be 1280.

For the Treshold I'm using 5 px so T results in (2 * 5) / 1280 = 0,0078125

Calculating A gives me more trouble, especially because I'm not sure what the variables represent. is n the distance from the camera to the near clipping plane or is it a vector describing the near clipping plane?

Also I'm not sure how to calculate the top coordinate of the near clippingplane. I assume you need the FOV for that?

Should the resulting Dn be a float or some sort of an integer? In promit's code it's typecasted to a short but I'm not sure why that is neccesary.

Thanks in advance and Kind Regards,

Quinnie

p.s.
i_luv_cplusplus: The algorithm I posted above is using triangle strips, JohnBolton's explanation is also using triangle strips since it's actually the same thing I was doing in my code.

Share on other sites
Quinnie
Just small hint.
It's much faster.

Share on other sites
Thanks for the tip,

I was actually planning to make some sort of look up table kind of thing for the pow() functions but this bit shifting seems to be a better solution. I'll adjust my code right away.

Quinnie

Share on other sites
With regards to your C, A and T calculations, this is the way I have always interpreted them.

Vres is the height of my backbuffer. So if I was using an 800x600 backbuffer, it would be 600.

n is the zNear, so in your case 0.01f

I calculate |t| as the tan of half the camera's fov ... e.g. tan(fov / 2.0)

If those are wrong then I have some problems with my own error metrics [smile]

As for the problem Promit has pointed out, I had seen this myself in my own implementation and it arose from the way I was shifting indices.

Basically what you are doing is when a vertex is deemed invalid (the blue dots) you modify the index so that it indexes the last valid vertex (the black dot being the last valid index and the blue arrows showing the direction you shift your indices). What this actually results in is an overhang. It is hard to describe, but that arrowhead shaped concave polygon is not rendered as a concave polygon, but instead like taking a square piece of paper and folding it along the diagonal (you could see it for yourself by freezing your lod updates and navigating your camera down to where that corner is) [smile]

Anyway, the solution is to not always index the last valid vertex, but instead index the nearest valid vertex. So in the case of at least one of those blue dots, you would actually index the red dot instead of the black one.

All the best,
ViLiO

Share on other sites
Quote:
 Original post by QuinnieFirst I assumed Vres is the screen resolution and not the backbuffers width, in my test case this would be 1280.
1280's an odd value. It's vertical resolution, whereas 1280 is typically a horizontal resolution. (a typical LCD would be 1280 x 1024, so the Vres would be 1024.)
Quote:
 Also I'm not sure how to calculate the top coordinate of the near clippingplane. I assume you need the FOV for that?
It's determined by using a right triangle with the hypotenuse going from the eye to the top center of the near plane. The base of that triangle is the near plane distance, and the angle contained by those two sides is half the FoV. It's straightforward trig to figure out the height of the last side, which is the value you need.
Quote:
 Should the resulting Dn be a float or some sort of an integer? In promit's code it's typecasted to a short but I'm not sure why that is neccesary.
I may have been messing with compressing the data involved at the time. Use whatever seems appropriate. (IIRC, the most recent implementation simply stores the world space errors, rather than the distance. This allows dynamic tweaking of the error value and camera parameters.)

Share on other sites
Hey,

thanks a whole lot for your valuable reply's. Sorry for the obvious mistake with the Vres thing. I did indeed use the horizontal instead of the vertical resolution. However I'm still not sure wheter to use 1024 or 600, 1024 seems to most logical to me.

Also thanks for enlightening the meaning of the other variables used in the equations I'll try to implement it tomorrow morning.

I took a second look at that problem with the corner and I beleive I understand the problem and the solution. Thanks for pointing it out.

Kind regards,

Quinnie

Share on other sites
This is my updated code to calculate the C constant:

// Calculate Cfloat T = (2.0f * TRESHOLD) / VRES;float A = 1.0f / (float)tan(FOV / 2.0f);float C = A / T;

The only thing I'm unsure about is wether the FoV needs to be converted into radians as Promit's implementation does.

Another problem I'm facing is how to calculate the distance between de camera and the patch. Should I use the patch center or use the closest of the 4 edges of the patch? And should I consider the diference between the camera's height and the patch's height or is it sufficient if I only use the 2d coördinates?

Kind regards,

Quinnie

Share on other sites
Quote:
 Original post by QuinnieThe only thing I'm unsure about is wether the FoV needs to be converted into radians as Promit's implementation does.
Quote:
 Another problem I'm facing is how to calculate the distance between de camera and the patch. Should I use the patch center or use the closest of the 4 edges of the patch?
Trust me, you don't want to use the patch center. What happens if you do is that for many patches, some of the distances for the LoD changes will be crossed while you're standing on that patch. Geomipmap changes aren't supposed to be significant visually, but they certainly will be if they happen right in front of you and under your feet.

Share on other sites
Hey,

I just made some screenshots of my terrain engine in it's current stage. Its using a 1024x1024 16 Bit heightmap, somehow my error calculations aren't working probably. I had to set my Teshold to 40 px before getting some decent results. The screenshots also show some glitches with the texturing I'm not sure why that happens but I'll try to look into that later. Additionally a quadtree culling system is not yet implemented.

My FPS is really low, it might be becuase I'm making 256 DrawIndexedPrimtive per frame (On a Geforce 7600 GS) but I suspect it's my CPU. My algorithm computes the index buffer again for each frame. Should I create some sort of a cache system for that?

I'm real sorry about the very poor splatting done on this screenshots it's kind of confusing but I'm working on a system using blendmaps.

Share on other sites
Quote:
 Original post by QuinnieMy FPS is really low, it might be becuase I'm making 256 DrawIndexedPrimtive per frame (On a Geforce 7600 GS) but I suspect it's my CPU. My algorithm computes the index buffer again for each frame. Should I create some sort of a cache system for that?
You should, yes. The index patching is a fairly brutal amount to run for 6 million indices or whatever it comes out to for strips.

After implementing caching and setting a restriction on how fast the level of detail can change (ie if a patch changed detail less than .25 seconds ago, it can't change again yet), I was running the index patching stuff for maybe 10-16 patches per second. Compare to 256 * 60 = 15360 at full frame rate.

Share on other sites
Quote:
 Original post by QuinnieMy FPS is really low, it might be becuase I'm making 256 DrawIndexedPrimtive per frame (On a Geforce 7600 GS) but I suspect it's my CPU. My algorithm computes the index buffer again for each frame. Should I create some sort of a cache system for that?

If your patches are 65x65, then you have 6 LODs. There are 2275 possible index buffers. If you precomputed every possible one, they would take up 65x65x2x2275 = 18 MB. That's not a lot of memory on a PC. If you restrict LODs so that adjacent patches never differ by more than 1 LOD, then there are only 16 possible index buffers. Those would only take up only 65x65x2x16 = 132 kB.

The space requirements for 33x33 patches would be 2 MB and 34 kB respectively.

Edit: These values are incorrect. See the corrected values below.

[Edited by - JohnBolton on May 16, 2007 5:00:16 PM]

Create an account

Register a new account

• Forum Statistics

• Total Topics
627744
• Total Posts
2978902

• 10
• 10
• 21
• 14
• 14