Sign in to follow this  

LOD Terrain - Indices management

Recommended Posts

retroip    415
Hello Community !,
I'v spent many hours regarding terrain, tested many approaches from my side,but [b]I stopped on one and last thing - Indices/Vertices optimization.[/b]
So, currently I'm using BiLOD XNA 4.0 LOD Terrain sample by [url=""]Rene7705[/url].
In my approach, I'v successfully reached stiching, and other required things, but I did not understand or I did not find proper material for Indices/Vertices optimization. [b]Let me explain:[/b]
[b]I need to remove duplicated Vertices and prepare indices for buffer.[/b]

Can you advice me some methods how can I remove duplicated vertices and use proper order for indices ? This proces is important for me, because when I'm transfering Vertices and indices into the Vertex/Index buffer, it saves me a lot (Yes, I'm using background thread to redetail terrain according current camera position).

Maybe picture will explain it better:
I have vertices from part 1 of the terrain, and vertices from part 2.
It is no problem to build Vertex and Index buffer for part 1 and Part 2 separately.
When I want to merge this parts into the one buffer to final buffer which is drawed, I can see...not seems, but I can see that I have 2 vertices on same place it is side effect of my DUPLICATED VERTICES.

[u][b]So question:[/b][/u]
How can I remove, well, remove is easy [img][/img], but how can I then properly calculate Indices for this Vertices for Part 1 and part 2 ?

[i]So, for example Vertices ABCD will be discarded because I already have E,G,I,K on that position.[/i]
[i]Vertices F H J are correctly stitched (height is interpolated between both sides vertices)[/i]

I hope, I'm clear.

Many thanks for your responses.

Share this post

Link to post
Share on other sites
Martin Perry    1553
I tried to do stitching once... but i figured out, that skirts are better, faster and easier... thats for start :)
Now...why you need to remove duplicated vertices ? I would just send all vertices in one VB and not to bother change this VB... he will be sitting on GPU all the time unchanged. Than you will be changing only IB, which is faster and more elegant.
I have created 1 IB for every block and every LOD of this block ... gives me lot of IB... when rendering, i simply switching IB and render parts of terrain with different LOD.

Set VB
Render block 1 (IB_Lod0)
Render block 2 (IB_Lod1)

If you wan to spare switching buffers, you can generate new one and send new one every time when LOD displacement changes. Depends on your terrain size, but due to my tests and results for terrain above 512x512 it starts to be rendering brake.

Share this post

Link to post
Share on other sites
retroip    415
Thank's Martin for hint, it makes sense, to precalculate all vertices and indices. I'll give it a try.

Well I have Primary V&i Buffer for rendering, on background thread I'm recalculating terrain detail according camera movement. Determining LOD level for each "chunk", building vertices and IB's for each chunk. Then all chunk buffers are merged into one VBuffer & IBuffer, and then quickly swapped.
[u]Then I was in circle:[/u]
1.that i can't compute Indices for chunk 1 if i dont know how will look like chunk 2, if I want to eliminate duplicated vertices
2.I can't compute Indices on merged vertices buffer, because I dont know the order of them (if I'll delete duplicated vertices)

Thats the advantage of BiLod I mentioned up, because there is no duplicated vertices, as I'm using this sample, and I spent a lot of time for analyse of this code. I cant see anything, that is maintaining duplicated vertices. But in wireframe it is not about squares, but 8 vertex shapes.

Share this post

Link to post
Share on other sites
Martin Perry    1553
I dont know BiLod exactly... but if it doesn´t move vertices among [x,y] (asume Z as height), than you dont have to do anthing with vertices at all during runtime.... they all remain the same and intact. LOD is created only with ordering indices. Your IB doesn´t need to use all vertices... you can use only some of them, that are stored in VB.
There are no duplicate vertices (or at least shouldn´t be) in VB... all duplicate are created on index level.

Share this post

Link to post
Share on other sites
In your image, A and E, B and G, C and I, and D and K are the same. They should be, at least.

You want to do stitching because even after geomorphing, F, H, and J may not be exactly (A+B)/2, (B+C)/2, and (C+D)/2, respectively -- resulting in visible gaps.

One very easy thing to do would be to add the triangles AFB, BHC, and CJD. This is as easy as it gets, cheap, and it works.

If everything matches perfectly, the triangle has zero area. If everything does not match perfectly, the triangle has a non-zero area and hides the holes.

Share this post

Link to post
Share on other sites
retroip    415
[u][b]Samoth[/b][/u]:[b]Yes, they are same,[/b] I just wanted to illustrate same vertice position for Chunk 1 and Chunk2 , I also wrote:
[quote][i]So, for example Vertices ABCD will be discarded because I already have E,G,I,K on that position.[/i][/quote]
[u]Thank you[/u], this looks better than my approach of handling stitches (Edge grid was created in every Chunk to adapt to [url=""]neighbour[/url]'s Chunk . You are right, interpolation was not enough to "hide" very small gaps. OK but this is not main point now.

[u][b]Martin[/b][/u]: I think I got it what do you want to say. For me is important "ordering indices" as you wrote, how is this done.

I'm trying to know simple thing, I understand that my explanations are not clear.
OK, another pic:

So what was made by me:
We have Chunk1 and Chunk 2 with it's own VB and IB. When I was preparing main VB and IB, which will be swapped later on with VB and IB for drawing, was:

Fill VB with Chunk's 1 VB and fill IB with Chunk's 1 IB.
[b][u]Results:[/u][/b] VB: A,B,C,D IB: [color=#0000ff]0,3,2,0,1,3[/color] ([color=#0000ff]ADC,ABD[/color])

Fill VB with Chunk's 2 VB
[u][b]Results:[/b][/u] VB: [color=#0000ff]A,B,C,D[/color],[color=#ff0000]C,D,F,G,H,I,J,K[/color] IB: [color=#0000ff]0,3,2,0,1,3[/color]

Fill IB with Chunk's 2 IB + SHIFT INDEX (starting number will be Count of current VB vertices), so:
[u][b]Results:[/b][/u] VB: [color=#0000ff]A0,B1,C2,D3[/color],[color=#ff0000]C4,D5,F6,G7,H8,I9,J10,K11[/color] IB: [color=#0000ff]0,3,2 (ADC) ,0,1,3 (ABD)[/color] , [color=#b22222]0[/color]+4=[color=#ff0000][u][b]4[/b][/u][/color];[color=#b22222]3[/color]+4,=[color=#ff0000][u][b]7[/b][/u][/color][color=#FF0000];[/color][color=#b22222]2[/color]+4=[color=#ff0000][u][b]6[/b][/u][/color] ([color=#ff0000]CGF[/color]) [color=#ff0000]0[/color]+4,[color=#ff0000]1[/color]+4,[color=#ff0000]3[/color]+4 ==[color=#ff0000]4,5,7[/color] ([color=#ff0000]CDG[/color]) [color=#ff0000]1[/color]+4,[color=#ff0000]4[/color]+4,[color=#ff0000]3[/color]+4==[color=#ff0000]5,8,7[/color] ([color=#ff0000]DHG[/color])

Yes I can draw this, but in LOD level 4-5 I can have >20 same vertices per chunk. In overall I had around 8x more vertices then current Terrain renderer.

[size=5][u][b]And NOW:[/b][/u][/size]
I hope you can see what I'm pointing at.
I have vertice [b][u][color=#0000ff]C[/color][/u][/b] twice in VB. If I want to remove doubled vertice [color=#ff0000]C on index position 4 (C4) in VB[/color], I need to edit Indice [color=#ff0000]4[/color] at index position 6 of IB, and set it [color=#FF0000]to 2 (from [/color][color=#ff0000]ib[6]=4 to [/color][color=#ff0000]ib[6]=2)[/color], and [u]SHIFT all other indices[/u]. This is too complicated process when currently in average I'm rendering 66000 Vertices with 130000 Indices with not my terrain engine (as I linked on my first post).
My approach is not good and I think [u]it is too complicated[/u]. There are not so many really working LOD terrains, with available source codes.

[u]Martin:[/u] If I keep all Vertices for deepest level, I think it will be too much.

So question,
What is optimal approach to fight with this issue, how it is done in your terrain renderers ? [img][/img]
I think I can't compute all indices if I have VB because, there is some order which I dont know (different, LOD per Chunk, different count of primitives)

My data:
Terrain is sized to 8192x8192 units, visibility is to aprox. 3000 units, LOD level max 12

Screens shows my requirements but not my renderer:
This is maximum terrain detail, you can compare it to character.

Or I'm missing some knowledge regarding VB,IB, ordering, drawing.

[b]Many thanks for your attention[/b] Edited by RetroIP

Share this post

Link to post
Share on other sites
TeaTreeTim    467
How many chunks are there? In your explaination your chunks are only a few vertices each. Merging all VB's and IB's into one is not something I would do. The processing of that would outweigh rendering multiple chunks unless the chunks are actually as small as in your explaination. How do you store 12 levels of LOD physically (eg a single file per chunk)? Your terrain is so hilly you might gain from chunk occlusion unless you want to fly. The hills are so small you might contemplate some kind of parallaxing for distant terrain. I would put that on the backburner until you are happy though.

Share this post

Link to post
Share on other sites
retroip    415
32x32 chunks, All picures all illustrations, Chunk 1 LOD 1, Chunk2 LOD 2, maximum lod is 12, so much more vertices.
Terrain size 8192x8192. Approx 3m between 2 vertices.
Heightmap is 2048*2048, so I have array of height. if there are more vertices per one pixel of height, IInterpolation is used - later details with additional noise
Occlusion is another part, which I want to implement, but current BiLOD sample which I'm using, is made a little bit in different way-this is the reason why I want to use my own terrain system.

I have opinion that I can reder terrain with one DRAW, (yes, limitations of vertices/indices), what I want ,is to collect all VB and IB from chunks, put it these into one VB and IB a simply DRAW.
Problem for me is how I remove duplicated vertices and SORT indices in IB properly according removed vertices.

I red many WhitePapers for terrains (LOD,Roam, different approaches), this process whas not mentioned.

Rendering each chunk separately will force to gaps, solution for this maybe skirts, but at the edge of chunk you will still see this.

I think I want to do it in wrong way.But then how it is done in globally ?
2 options:
1. Large terrain rendering is builded in way that it does not generates duplicated vertices (my currently terrain renderer NOTmade by me)

2.Or vertices are somehow handled - this I want to know, how

I want to achieve Quad based LOD, when I can easily cull quads which are far away. With current chunked LOD I cant't, because implementation is not possible in this algorithm. Edited by RetroIP

Share this post

Link to post
Share on other sites
Martin Perry    1553
I am using Quad based LOD... Drawing every block independently....merging it into one VB / IB is waste of time and it will be probably slower than multiple draw-calls.
I have had stitching done, so it looks like this

All is done by only working with IB. Can stitch any LOD quality on any other. Stitsching is computed every time scene changed, for discarding invisible (or out of frustrum blocks) is used quad-tree. Works fine, but for large terrain its not quite good in performance and calculating stitsching in real-time slow thing down... precalculation could be solution, but than it wouldn´t be so universal (conect every LOD on any other... and fro your 12 qualities even impossible).
So I switch to skirts, which are far better. I even have geo-morphing with that and everything looks fine. Basicly speaking.. stitching really disapoint me [img][/img] in way of "quality vs. spend time and performance" Edited by Martin Perry

Share this post

Link to post
Share on other sites
retroip    415
Fine Martin,
Thanks for this, I'll try to use skirts again, then I'm finally free and I can enable/disable whole terrain chunks.
I'm not having FPS drops during current terrain rendering, but I wanted to have my engine, because someone other's engine is sometimes hard to understand.

I thought that drawing terrain in one draw is the best solution, but background indice management is time expensive in that way.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this