# Geomipmapping tutorials

This topic is 4404 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 there`s plenty room for other things to render/process.

• 10
• 16
• 9
• 13
• 41