GeoMipMap Implementation
Author
Hey,
a while ago I created my own terrain engine using the brute force rendering technique, I was however not pleased with the line of sight that I could achieve using this method. I've looked at techniques such as ROAM but found that GeoMipMapping suited my purpouses better.
I've read Willem de Boer's paper on GeoMipMapping and I beleive I understand the basics about this technique. I've made a whole lot of sketches with pen and paper about the vertex and index buffers and created the algorithm's.
I am however confused how I should store the vertex buffers. My first thought would be to split the entire terrain into chunks of say 33x33 vertices and create index buffers for every existing MipMapLevel. After that I could render the seperate vertex buffers using the index buffer to apply the MipMap level. This would however mean that I would need to use a DrawIndexedPrimitive call for each terrain chunk and that could slow down the performance.
I also thought of combining multiple chunks of terrain into one vertex buffer but that would result into dynamicly updating the vertex or index buffers. This also slows down the performance.
I've also heard of an implementation in wich there are actually two vertex streams that are combined in a vertex shader. However I could not find any more information on such a technique and I was wondering if this would be possible using shader model 2.0 or below.
Another problem I'm facing is how I should create the strokes next to terrain chunks to smooth the transition to another MipMap level. Should this be done using a seperate vertexbuffer and a seperate DrawIndexedPrimitive call?
If someone could show me a working and easy to follow GeoMipMap implementation I would be very happy. It seems that there's not a lot of open source code on GeoMipMapping available on the internet. I myself am planning to make this project open source when finished or atleast progressed a bit further.
Kind Regards,
Quinnie
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.
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.
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.
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.
Author
Thanks for your reply,
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?
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?
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.
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.
Author
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
Kind Regards,
Quinnie
Author
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
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
Tell me how you figured out these indices, and I shall be your sex slave :) I can't figure it out
Quote:Original post by QuinnieHmm. 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.
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?
By the way, I really like that sketch.
Author
Thanks for your reply,
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!
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)
The function used to create the plain patch without any stiching on the sides.
The functions used to apply a MipMapLevel to the sides of a previously created index buffer to apply the stiching
A sample using the above functions to create the index buffer I posted earlier
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_cplusplus
Tell 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;This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
