• 14
• 12
• 9
• 10
• 13

# GeoMipMap Implementation

This topic is 3959 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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) / pow(2.0f, AdjustingMipMapLevel) + 1) * pow(2.0f, AdjustingMipMapLevel) * Dimensions#define ADJUSTEDINDEX2 (int)(XVERTEX(Buffer) / 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 = ROWOFFSET1; i++;		for (int Col = 0; Col < NUMCOLS - 2; Col++)		{			if (Col % 2 == 0) {Buffer = ROWOFFSET1 + COLOFFSET1; i++;}			else {Buffer = ROWOFFSET2 + COLOFFSET2; i++;}		}		Buffer = 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) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && XVERTEX(Buffer) == 0)			Buffer = 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) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && XVERTEX(Buffer) == Dimensions - 1)			Buffer = 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) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && YVERTEX(Buffer) == 0)			Buffer = 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) % (int)(pow(2, AdjustingMipMapLevel)) != 0 && YVERTEX(Buffer) == Dimensions - 1)			Buffer = 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;