# Geomipmapping tutorials

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

## Recommended Posts

do you know any tutorials on geomipmapping? i've searched for a day now, but i only find tutorials based on open gl, but none of them was for direct x. i have read many papers on that technqiue, but to fully understand it, i need to see the source code, but i'm simply to stupid to find any tutorial... -.- can you post me any links? i'm really out of options

##### Share on other sites
I might be mistaken but I think that the following technique is called geomipmapping:

You divide your terrain into CxC chunks.
High Detail is the default resolution (HxH vertices).

Medium detail (MxM vertices) has M=H/2. However, you would have holes around the Medium detail chunk like this (if it would neighbour chunk of other detail). Therefore, there must be one connecting row/column around all four sides that is of high detail on outer side and of half detail on inner side. The rest of the chunk is just of half resolution.
However, if all neighbouring quads are of same detail, its a bit ineffective (especially it there are several tens of those on-screen), so you could keep 2 versions of medium detail - one with connection between high/medium detail and the other without.

Low detail (LxL vertices), where L=M/2. Do the same thing as with medium detail.

Obviously, the least memory-intensive implementation under DirectX is to have all 3 LODs through Index Buffers (IB). You would have seperate IB for High,Medium and Low Detail. Consider using just 16-bit Indices and switching among several VBs (each with 65k vertices) because it enormously saves the memory.

To save memory even more, each chunk (of CxC resolution) would have separate VB.There would be just 3 IBs (High,Medium,Low) detail with indices for first chunk. Since the order of vertices can be same over all chunks (i.e. VBs), you dont need more IBs than those 3. Thus, the memory requirement is minimal.

As for performance, this technique raised fps for about 50%. Considering, it took just 1 day to implement (its a pain drawing all connecting borders on paper and deciding the correct order of Indices), its definitely a first thing you should implement after Frustum Culling.

##### Share on other sites
Link to the original article of Willem de Boer
EDIT: Oh wait, was toof ast, see you actually want source code. In that case: you might want to look at the Irrlicht-source. In CTerrainSceneNode.cpp they use Geomipmapping.

##### Share on other sites
thanks for the explanation, but i've already read some articles and i understand it ( theoreticly ) but i don't know how i should draw the triangle fan ( i thought this was mentioned in de boer's paper ) nor how not draw all the triangles on the side to a lower LOD patch. therefore i need the sourcecode to understand how it's done ( i won't str+c it all, but i can learn much better if i know the theory and its applied implementation )

but thanks for the tipp with the IB for all the chunks, i didn't do that, although i shoudl have noticed that the index buffer is the samer for each patch *rolleyes* i'll rewrite the source code ^^

i'll download the sourcecode and look through this file after that, thansk very much :D

##### Share on other sites
Quote:
 i don't know how i should draw the triangle fan ( i thought this was mentioned in de boer's paper )

I used a triangle list in my implementation. Ideally you would want to use triangle strips, since those are fastest on most cards. However, I have seen the question of how to order your vertices to acheive this posted here on gamedev, but sadly I have never come across or figured out a way to do this. I wouls assume you would use degenerate triangles somehow, but whenever I tried making a degenerate triangle my program would crash.. go figure. Trianlge fans are not possible for a square implementation since you have to share one common vertex for all the triangles (unless you do like a hex-based version of the techique, as opposed to a square patch).

##### Share on other sites
Quote:
 Original post by SiS-Shadowmanbut i don't know how i should draw the triangle fan ( i thought this was mentioned in de boer's paper )
Forget about Triangle Fans. Just use Triangle Lists right now. Later you can upgrade to Tri-Strips, if memory is an issue.
Quote:
 Original post by SiS-Shadowmannor how not draw all the triangles on the side to a lower LOD patch. therefore i need the sourcecode to understand how it's done ( i won't str+c it all, but i can learn much better if i know the theory and its applied implementation )
This is impossible to understand from some source code. If you understand the concept of the border between two different LODs, all you need to program is to find out the relevant Indices of the Terrain Chunk.
And for this, you must draw it on paper and see it on your own eyes. It takes 10 minutes to draw on paper the grid with enhanced border (around the lower detail). Just do it on paper, and youll immediatelly see it.

Quote:
 Original post by SiS-Shadowmanbut thanks for the tipp with the IB for all the chunks, i didn't do that, although i shoudl have noticed that the index buffer is the samer for each patch *rolleyes* i'll rewrite the source code ^^
Definitely rewrite the code so that it uses IBs. Not only shall your memory requirements drop enormously (Indexed VB shall have just about 16% of nonindexed version), but your performance will skyrocket too.

Quote:
 Original post by SiS-Shadowmani'll download the sourcecode and look through this file after that, thansk very much :D
Such a thing should be written from scratch by you into your own codebase, instead of using some alien code which you dont understand. Its a road to hell of bugs/crashes/weird behaviour with the alien code. Especially, if it takes just few hours to write this code. But you must first understand it fully, theres no way around it.

Quote:
 Original post by APIdeally you would want to use triangle strips, since those are fastest on most cards.
Leaving smaller memory footprint for Strips aside, Tri-Lists can be as fast as Tri-Strips IF your order of Vertices is ideal. That means that you should have your Vertices inside VB sorted by rows (and each row sorted by column). Thus, whether youll use Tri-Lists or Tri-Strips, Vertex Cache (16 entries on all shader HW) shall take care for all last 16 transformed vertices, and thus Vertex Shader wont have to be called for them.

On the other hand, if you use NonIndexed Tri-Lists, Vertex Shader shall be called for each vertex. If you consider, that you have heightmap of say, 1024x1024, the Non-Indexed Tri-List shall call the Vertex Shader 6.291.456 times (1024x1024x2x3). But, with Indexed Tri-List (and ideal order of vertices), where vertex cache shall search the current vertex within last 16 transformed vertices, your Vertex Shader shall be called just 1.048.576 times (i.e. just once per each vertex). Thats a ratio of 6:1 !
The reason, why Tri-Strips can be a little bit faster than Tri-Lists (even with ideally sorted Vertices) is bandwidth. With Tri-Strips, your IB is 3 times smaller, thus less data gets moved around the bus. However, the difference with small VBs/IBs is negligible and isnt worth the trouble of calculating the correct degenerate vertices - especially at the border between High and Low detail. Dont get me wrong though - degenerate vertices are fast and easy to calculate on regular heightmap. However, doing that for border between High and Low Detail is a bit messy and requires huge drawing (A4 at least) and few hrs of your time. Lowered Memory requirements might be worth it, though.

##### Share on other sites
Quote:
Quote:
 Original post by SiS-Shadowmannor how not draw all the triangles on the side to a lower LOD patch. therefore i need the sourcecode to understand how it's done ( i won't str+c it all, but i can learn much better if i know the theory and its applied implementation )
This is impossible to understand from some source code. If you understand the concept of the border between two different LODs, all you need to program is to find out the relevant Indices of the Terrain Chunk.
And for this, you must draw it on paper and see it on your own eyes. It takes 10 minutes to draw on paper the grid with enhanced border (around the lower detail). Just do it on paper, and youll immediatelly see it.

well, i saw some screens where they showed, how triangles are removed at the border between a lower LOD patch and a higher LOD patch, but do i need to update the IB every time, a neighbouring patch changes it's LOD? or would it be better to pre create an index buffer for every situation ( less cpu power, more memory usage )
i don't like any option. i thought altering an IB at runtime costs very much cpu time.

[Edited by - SiS-Shadowman on April 25, 2006 7:32:39 AM]

##### Share on other sites
Since were talking about geomipmapping here, Im assuming were doing brute-force rendering. Therefore, your terrain is pre-divided into chunks of same dimensions.

Option A: 32-bit Indices (Tri-List), 1 VB, 1 IB
So, for one LOD you need just one Index Buffer (32-bit IB Tri-List).
If your heightmap has a resolution of, say, 1024x1024, thats 24MB for IB. Second LOD should have ~16,5 MB and third LOD ~11,7 MB.
If you have 3 LODs, thats 52 MB (quite a lot, and most probably unacceptable).

Of course, nothing stops you here from occasional update of these Indices provided not whole terrain is visible at any time. I.e. you may know that any time, only 25% of the terrain is visible (say, some 3x3 chunks around your current chunk are visible). So, you have precomputed Indices for terrain chunks around you and if you move further the boundary, new Indices are created for the chunks of terrain that just came into your view and those behind you can be safely deleted. If this is spread over several frames (i.e. not all 3 new chunks are created during iven frame), no major slowdowns should be noticed.

Option B: 16-bit Indices, 1 IB, several VB
Here, each VB chunk shall have dimension 256x256, so we need 16 VBs in total. However, well need indices just for this chunk of 256x256.
So, heighest LOD shall occupy 0.75 MB (256x256*2*3*2), medium 0.5 MB and low 0.38 MB. In total, thats around 1.7 MB which is totally acceptable.
Since you wouldnt see whole terrain at any one time anyway, you wouldnt need to switch among all 16 VBs. Maybe about 6 DIP calls could be enough (depending on the size of the terrain and relevant chunks), which isnt that bad.

Put all indices into one IB, and youre done.

And definitely stay out of dynamically updating IBs every frame. That would be horribly inefficient considering needed memory for indices in Option B.

##### Share on other sites
if i'm getting you right, you suggest for option A), that i just update the IB for a patch, when one of it's neighbouring patches changes the lod ( well, thats logical ). for further performance, just one IB is created per frame ( at maximum ), that means that the other patches have to wait, until it's their turn.

the 'only' thing i have to do is inventing an algorithm, wich creates this IB, based on the LOD lvl of the other patches. thats gonna be a lot of work ^^

##### Share on other sites
Well, acutally Id propose Option B, which is what I implemented recently. Even with little VB switching, the performance was perfect. With about 50k tris on screen (on average), fog and texture splatting (2 textures of resolution 1024x1024) I had over 1000 fps on my pretty old GF6800. So theres plenty room for other things to render/process.

##### Share on other sites
i think you don't know where my problem is.
i've already divided my terrain into different patches, why should i need extra chunks for each patch??

all i want to do is render the patches in several LODs ( depending on the distance from the camera ) and i have problems updating the index buffer for the patches, because it would result in gaps, when i render two patches with different LODS ( just half of the resolution between each lod.. ). so i need to remove triangles ( actually rewrite the IB, that there are only half of the vertices at the border to the lower LOD used for the tris )

i need 1 IB and 1 VB for each patch, i can't do it anything else, can i?

##### Share on other sites
You can use 1IB and 1VB for each patch.

All you do, is when you are updating a given patch and after having figured out that one or multiple neighbors are of LOWER LOD, meaning less vertices, then you simply run back through the patches indices and change only the border indices.

So for instance, lets say the neighbor to the left has one Lod level lower than the current patch. Then all you would do is change every odd indexed indice on the left border to point to the previous vertex.

So if your border indices were

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Then now they would be

0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 17

And if the neighbor's Lod was 2 minus the current patch's lod then the indices would be:

0 4 4 4 4 8 8 8 8 12 12 12 12 16 16 16 16 17

You get the idea now?

##### Share on other sites
ahh, yeah, i got it now :D

i drawed it all on the paper, but i could not find a suitable algorithm to do this. i'll try it right now. thanks very much :D

##### Share on other sites
Quote:
 Original post by VladROption B: 16-bit Indices, 1 IB, several VB...

Trying to figure out your math, but all I get is a headache. Let's divide a 1024x1024 heightmap (and I consider that to be pretty much on the small side) into 32x32 patches. That's 1024 patches of 1024 vertices (yes, technically it's 33x33, but who cares).

LoDs use 32, 16, 8, 4, 2, 1... so you need 6x16 IBs (including all the "cut outs" for connecting pieces to lower lod). Thats 32x32x2x2x16 byte + 16x16x... ie 64kb+16kb+4kb+1kb+.25kb+<so small nobody cares> = less than 86kb. A bunch of connectors, unless you use a quick and dirty method like skirts anyway. Even if you use 128x128 patches (I'd advice that for 4096x4096 and up) you won't have more than 1.5MB.

The patches themselves absolutely don't need to have x,z coordinates over and over again. Just store the height, use a seperate buffer for x,z (each 0-32) and store ONE offset per patch (send them as program/shader parameter, doing a translation for each patch is a performance killer).

So you get 33x33x4 vertices per patch and have 1024 of them for height, ie. 4.2MB plus 33x33x4x2 = 8.5kb for x,z and 1024x2x4 = 8kb for offsets. You can also use a height offset, but with floats that's rather pointless and more modern cards hate their vertex data as anything else anyway.

The terrain uses a total of about 4.3MB at 1024x1024, roughly 16MB for 2048 and 64MB for 4096. Or, to make it simpler: width*height*4byte + not too interesting overhead for offsets, index buffers, quadtree, etc.

Playing around and squeezing the exported Oblivion terrain into it with 128 patch size (around 4096x4096 if you remove all the pointless areas with no height) it's running at around 500fps on a 7900gt.

And source that won't help anybody, because it's an uncommented mess with index buffer generation I don't understand myself a week later.

Forgot some people want to see an actual app of it or at least some screens (1024x1024 FarCry demo map or more screens (4096x4096 Oblivion map).

[Edited by - Trienco on April 26, 2006 12:31:23 PM]

##### Share on other sites
See if this post helps.

##### Share on other sites
i have now divided the terrain into different patches and the IB is updatet everytime a patch changes its LOD. i'll implement now that the IB also changes when a neighbouring patch changes its LOD ( to avoid those nasty gaps, haven't come so far yet ). i'll then compare the speed with the speed when using fixed IB's ( well about 3 or 4 ) and also the memory usage and then decide wich techniques suits my need better :)

##### Share on other sites
You can also greatly improve the speed of dynamic IB's by only updating them of the camera has moved a certain amount. So let's say a patch is 33x33 units, then if the camera moves about 16 units from its previous position, THEN go through updating each patch's lod and indices.

##### Share on other sites
Quote:
 Original post by SiS-Shadowmani have now divided the terrain into different patches and the IB is updatet everytime a patch changes its LOD.

Are you saying you're using one huge IB to draw everything in one call? Because if you update and change the IB all the time anyway you could just as well implement geoclipmapping and essentially don't have any limit on terrain size anymore. Geomipmapping isn't all that great for anything but smallish level like terrains anyway.

##### Share on other sites
no.
i meant that i update the IB for one patch, IF it has to change it's LOD, because it's too far / near from the camera. i'm not shure how big my terrain needs to be. i think i'm satisfied when it can read out a 256 or even 512 sized heighmap and draw it speedy ;)

##### Share on other sites
Quote:
 Original post by TriencoTrying to figure out your math, but all I get is a headache.
Well, it seems that you got confused by number 16, which in my case was number of separate VBs (max.terrain chunk size that can be indexed with 16-bit IB). In your case, its the number of different LODs per chunk. In my calculations, I used just 3 LODs per chunk, because any distance beyond this threshold and its already fogged out of frustum anyway.

Quote:
 Original post by SiS-Shadowmani meant that i update the IB for one patch, IF it has to change it's LOD, because it's too far / near from the camera.
Im not sure if I get you right. So, if you have, say, some 32 patches (chunks) on-screen, and about 20 of them require different LOD, youre updating those 20 IBs each frame ? Or only once when the LOD is being changed ?

Quote:
 Original post by SiS-Shadowmani'm not shure how big my terrain needs to be. i think i'm satisfied when it can read out a 256 or even 512 sized heighmap and draw it speedy ;)

You dont mean 256x256 for whole heightmap, do you ? Probably 256x256 just for one chunk of the terrain, right ? Such a small heightmap would be too blocky for regular use. Even 1024x1024 can be too small (depending on total area that you want it to cover).

##### Share on other sites
checkout this book:

http://www.amazon.de/exec/obidos/ASIN/1592000282/qid=1146209561/sr=8-3/ref=sr_8_xs_ap_i3_xgl/028-6211522-3945319

##### Share on other sites
Quote:
Original post by Trienco
Quote:
 Original post by SiS-Shadowmani meant that i update the IB for one patch, IF it has to change it's LOD, because it's too far / near from the camera.
Im not sure if I get you right. So, if you have, say, some 32 patches (chunks) on-screen, and about 20 of them require different LOD, youre updating those 20 IBs each frame ? Or only once when the LOD is being changed ?

i'm only updating them, when they need to change ;)
i know it would be a waste of time to update them every frame. but i'll write a different terrain class, wich pre calculates the IB's for the different LODs and then just use the propriate: i haven't decided what i want to use.

Quote:
Original post by Trienco
Quote:
 Original post by SiS-Shadowmani'm not shure how big my terrain needs to be. i think i'm satisfied when it can read out a 256 or even 512 sized heighmap and draw it speedy ;)

You dont mean 256x256 for whole heightmap, do you ? Probably 256x256 just for one chunk of the terrain, right ? Such a small heightmap would be too blocky for regular use. Even 1024x1024 can be too small (depending on total area that you want it to cover).

well, actually i meant this, but i haven't spend much time thinking of it. i'm not shure how big my actual game can be ( i'm just one person ;) )
apart from that, am i able to use such big heightmaps with a 16bit indexed buffer?
if i'm getting it right, 16 bit integers are just able to display values up to 32.767, and so i could just use up to 32.767 vertices for one IB ( and propably patch/chunk ( 181*181 )
or am i misunderstanding something?

##### Share on other sites
http://www.gamedev.net/reference/articles/article1936.asp

And I picked the url of the source code from it:
http://www.gamedev.net/columns/hardcore/geomorph/Terrain_Src.zip

##### Share on other sites
Quote:
 Original post by SiS-Shadowmani'm only updating them, when they need to change ;)i know it would be a waste of time to update them every frame. but i'll write a different terrain class, wich pre calculates the IB's for the different LODs and then just use the propriate: i haven't decided what i want to use.
Thats good. I just wonder, wouldnt it be easier to write precalculated LODs than updating each during runtime ? But since youll write it anyway, youll be at least able to measure the performance differences.

Quote:
 Original post by SiS-Shadowmanwell, actually i meant this, but i haven't spend much time thinking of it. i'm not shure how big my actual game can be ( i'm just one person ;) )

This has nothing to do with how "big" the level is going to be. It all just depends on your scale. If you scale it 10 times the distance between clipping planes, its gonna be quite huge. But itll be very sharp and low-detail. So it depends just on you.

Quote:
 Original post by SiS-Shadowmanapart from that, am i able to use such big heightmaps with a 16bit indexed buffer?if i'm getting it right, 16 bit integers are just able to display values up to 32.767, and so i could just use up to 32.767 vertices for one IB ( and propably patch/chunk ( 181*181 )or am i misunderstanding something?
You can index 65536 vertices with 16-bit IB. So, if you want to use larger terrain, you should either switch to 32-bit Indices (double the memory usage for IBs) or stick with 16-bit Indices and switch between several VBs (each containing max 65k vertices). Of course, using 32-bit Indices is easier, since you dont have to change anything except few flags and IB creation details. So, if memory isn`t an issue, just go for 32-bit Indices.

##### Share on other sites
i don't agree with you at the second point.
the level also needs to be filled with everything ( buildings, trees, plants, rocks and all the other stuff ) and i don't want to spent months in building the whole level, thats why i don't need a huge terrain. i know i can scale it. but 512x512 should be sufficent enough for my needs