Geometry Clipmaps

I too am a bit unsure of the implementation of geometry clipmaps. The biggest issue I have with the paper is how to implement the toroidal access of the vertex buffers. I have done some research and come to a few conclusions.

First, you must either lock the vertex buffer of the clip region being update once for each row of vertices, or you must lock the entire thing. One side of the L-shaped region that needs to be updated has its rows going perpendicular to the rows of the actual vertex buffer.

For this reason you would need to lock every row seperately if you only wanted to lock the vertices that need to be updated. Would having only one lock call, but locking more vertices be faster than multiple lock calls but a lower overall amount of data being transferred?

The second thing that occurred to me is that the entire index buffer must be recalculated for every updated clip region. Through my searching, I have found no way to change indexing on the vertex buffer. Without this, the "mod operations on x and y" (which is all the paper says about the this) must be done on the CPU to achieve toroidal access. Am I correct in saying this or have I missed something?

Hopefully you can get something out of this Hybrid666, that is if any of my ideas here are right. Can anyone help to clarify them?

Edit: This post would probably get a better response in Graphics Programming and Theory.

[Edited by - Hexus on February 23, 2005 8:22:17 PM]

If you're using OpenGL, you're probably best using a mapped VBO to store the vertex data (sorry I don't know what the Direct3D equivalent is) and locking the whole lot and updating it in one go.



For the index buffers, I reckon if you are really sneaky you can use a static index buffer - and only need one for all you levels!



To make following easier to understand, imagine you render each sector of a region as long strips, one for each row, instead of vertex cache optimised way shown in figure 3 in the paper. The technique should work if you are doing that but this will make it easier to understand.



In your index buffer, if you duplicate the first half of each row you can allow your render calls to go past the normal end of the row. Using a render call like glDrawElements (again I don't know the Direct3D equivalent) you can specify the first index, and the number of them to render. (In reality, you'd specify them all at one using glMultiDrawElements.)



So if your vertex buffer was laid out as:

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

Your index buffer, for the first row, would be:

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

The first half of the row is duplicated at the end of the row. You need half the row to be duplicated because that's how wide the widest sector is.



When you make the render call, you specify the start index appropriately for the amount the vertex buffer should be 'scrolled'. e.g. If you want to draw the first row of the top middle section when the region is 'scrolled' by 6 verticies, specify 12 as the start index and 10 for the number of indicies.



It will run past the value 17 and the effect will be the same as wrapping to the start of the row.



For scrolling in the other axis you'd change which rows you draw - but that's a much easier problem.



Using this method, you will only need to calculate the start offset for each row in each sector.



I should point out that I've not implemented this yet - I'm still thinking about the best way to update the vertex buffers.



dave j

Edit: Added bit about the other axis.

[Edited by - dave j on February 24, 2005 2:53:48 PM]

That is a very ingenious solution to the indexing problem, but wouldn't the performance hit of having n calls to glDrawElements versus 4 be worse than updating the index buffer?

Does glMultiDrawElements group the seperate primitives together on the GPU to get rid of the overhead of multiple glDrawElements calls? If it does, then this trick should definitely work. However, I haven't heard of a Direct3d equivalent to that function.

I must have missed the part of the paper that said the indices have to be recomputed on the CPU. I guess if their implementation recomputes the index buffer, then it should be fine to do so.

Updating the vertex buffer should not be hard if you have easy access to the height data. Whenever the clip region needs to be updated, you would lock its corresponding vertex buffer and overwrite the vertices of the L-shaped region that is no longer in the clip region with the vertices of the new L-shaped region.

There is a diagram showing this update in the paper The Clipmap, A Virtual Mipmap. (page 4, although it is talking about textures and not vertex buffers.)

Quote:

Original post by Hexus That is a very ingenious solution to the indexing problem, but wouldn't the performance hit of having n calls to glDrawElements versus 4 be worse than updating the index buffer?

Yes. That's the reason to use glMultiDrawElements in practice. To do vertex cache friendly triangle strips like in figure 3 would need something like this to avoid the hit anyway.

Quote:

Does glMultiDrawElements group the seperate primitives together on the GPU to get rid of the overhead of multiple glDrawElements calls? If it does, then this trick should definitely work. However, I haven't heard of a Direct3d equivalent to that function.

Where glDrawElements takes a number of primitives and a pointer to an array of indices, glMultiDrawElements takes pointers to arrays of numbers and pointers to primitives and the size of the arrays. The effect is the same as calling glDrawElements many times with only one API call. I don't know how the driver writers have implemented it but we have to trust that they've optimised it - there wouldn't be much point in having the API otherwise.

Quote:

I must have missed the part of the paper that said the indices have to be recomputed on the CPU. I guess if their implementation recomputes the index buffer, then it should be fine to do so.

It's in the sentence just before figure 3. I haven't figured out what they mean by 'go away shortly' in that sentence, any ideas?



I'm trying to keep the option open of not insisting on vertex shaders to fix LOD change gaps, maybe by using skirts on hardware that doesn't support them, so I'll probably stick to this indexing scheme for now even if there is some neat solution to avoiding updating index buffers using vertex shaders.

Quote:

Updating the vertex buffer should not be hard if you have easy access to the height data. Whenever the clip region needs to be updated, you would lock its corresponding vertex buffer and overwrite the vertices of the L-shaped region that is no longer in the clip region with the vertices of the new L-shaped region.

That's the bit I'm working on now. It's not as hard a problem as the index buffer updates, just awkward.



dave j

Quote:

Original post by dave j It's in the sentence just before figure 3. I haven't figured out what they mean by 'go away shortly' in that sentence, any ideas?

I'm assuming that he means that it will eventually be possible to implement the toroidal access on the GPU, therefore the overhead of updating the indices will 'go away.'

Quote:

Original post by dave j The effect is the same as calling glDrawElements many times with only one API call. I don't know how the driver writers have implemented it but we have to trust that they've optimised it - there wouldn't be much point in having the API otherwise.

I'm still a bit skeptical of glMultiDrawElements. I can't find a whole lot of information on it other than the documentation, which does not mention performance, and a post here on GDNet that says it is no different than a for loop with glDrawElements. I would be interested to hear how this method works out for you.

Quote:

Original post by Hexus I'm assuming that he means that it will eventually be possible to implement the toroidal access on the GPU, therefore the overhead of updating the indices will 'go away.'

The 3rd paragraph in section 10 gives it away. Recent GPUs with recent drivers allow vertex shaders to read textures. You could store your heights in a texture and look them up when necessary. You could pass the viewer's position as a variable to the shader. Each vertex could either be passed in another variable or, more likely, just have a constant vertex buffer that contains coordinates for referencing the heights texture. Use the viewer's position to offset and wrap the vertex coordinates and there you have your toroidal access. If your landscape was entirely procedural you wouldn't even need the heights texture - although calculating the landscape everytime you draw it is unlikely to be the fastest way.

Quote:

Original post by Hexus I'm still a bit skeptical of glMultiDrawElements. I can't find a whole lot of information on it other than the documentation, which does not mention performance, and a post here on GDNet that says it is no different than a for loop with glDrawElements. I would be interested to hear how this method works out for you.

Posts in the forums on OpenGL.org seem to indicate that glMultiDrawElements only really helps if you are CPU bound. If you are focusing on newish hardware, you're probably better off using triangle lists or triangle strips joined with degenerate triangles.



You could still use the duplicate half the indices buffer technique to help though. Updating the proper index buffer could then be a series of memcpys instead of calculating it all the time.



I want to see if clipmaps, without the geomorphing, would help on low end hardware though so I'll presevere with it a bit longer. (Why I'm bothering I don't know - I've just got a GeForce 6600 GT, I should be going for the 'do it all in the vertex shader' solution.)



dave j

well... i've been playing around with VBO's and reading through what you've all said and read that paper again..

just wondering if its a bit beyond me to be honest! :(

sorry haven't replied sooner - been away :)

im still unsure about how id set out my data, in a way that lends itself to updating the vertex buffers....

"Each level contains an n×n array of verti-ces, stored as a vertex buffer in video memory. To permit efficient incremental updates, the array is accessed toroidally, i.e. with 2D wraparound addressing using mod operations on x and y."

ok, obviously 2x2 array of vertices isnt rocket science.. vert[n][n] which is then put into the vertex buffer.. toroidial access however..? this is to do with the rings around the viewer yes? and each level is each 'ring' around the viewer from what i understand. each 2d vertex buffer would need to be updated incrementally too, to handle position/lod changes..

im mainly confused tho in how id set out my vertex and index data in memory! (i know.. not even got as far as the updating of them!) :(

thanks for all your comments so far tho, and apologies for my uselessness! :)

Hybrid

Since vertex arrays, VBOs etc only accept 1 dimensional arrays, I generally use them for my data structures and just work out the offsets in them by hand when I want 2D arrays. You then only have to remember one simple thing rather than worrying if your 2D array maps to the OpenGL data structure in the way you expect.



Doing

or

causes the compiler to generate the same thing anyway (or did last time I looked).

Here's a C++ class that will calculate offsets for a 2D array held in a 1D buffer with toroidal access.


dave j

It is important to note that the modulus operator may not give you correct results with a negative offset. For example, if the x offset from the origin is -5, the width is 30, and the input x is 0, then it will be (0 - 5) % 30. The desired result is actually 25, but in most cases modulus will give you -5. The current solution I have devised for this problem is:

#define mod(a,b) (((a % b) + b) % b)

This gives you the desired positive output value. You could also check if the modulus results in a negative number and add the right hand operand on if it is, but the above solution seems like it would be more efficient.

Edit: I just saw the offsetX = newX % width; In that case all you would have to do is ((x + offsetX + width) % width) as there is no chance of offsetX being below -width.

[Edited by - Hexus on March 1, 2005 5:38:28 PM]

Texture splatting would be implemented in a very similar way to other terrain algorithms. The entire terrain would share the splat textures, such as snow and dirt. The individual clip regions would have their own alpha maps for the texture splatting. The alpha maps would be done with the spatially based texture LOD scheme mentioned in the paper, while the splats could be rendered with normal mipmapping. Atleast this is how I believe you would implement it.

The advantage geometry clipmaps have over something like chunked LOD is that the transitions between levels are very simplified and are also more hardware friendly. There is no pre-computation required which contributes to another one of geometry clipmaps' advantages: streaming. With geometry clipmaps, terrain data can be brought in as it is needed. With chunked LOD the entire chunk must be loaded in before it can be used. Clipmaps only need to update around the edges of each region.

As for applying this algorithm when the data is spread across multiple vertex buffers, I am really unsure as to what part of the algorithm is giving you problems. Basically each clip region has its own vertex buffer. This vertex buffer overlaps that of the finer levels, but, when rendering, the finer level's active region is cut out of the coarser one so that coarser region has a rectangular hole in the middle.

Quote:

Original post by Anonymous Poster The problem is like you said "the entire terrain would share splat textures". So, how many splat textures can be used? 4,8? With a chunk-based approach those textures could be different for every chunk, however with geoclipmaps it's only possible to assign one set of textures for whole terrain(e.g like the one Hoppe used, 16kx16k).Imho, that's a serious limitation for any real application(read: game), using large terrains.

The theory behind texture splatting for terrains is that you can use a few common textures to produce varied terrain. If you supply a different texture for each chunk then you are not really using texture splatting, but just the normal method of having one texture to represent the terrain's surface.

I have thought about the texture splatting for a while and I think there is an easy way to do it without having a limit on the number of textures. Basically what is happening is that the individual splat textures are being baked into a single texture.

First the alpha maps are decompressed or synthesized, just as in the paper. Now, instead of uploading the alpha maps directly to their own textures, we use them to bake their corresponding splats onto a single texture. This would decrease bandwidth. I am unsure as to how much it would affect performance on the CPU side however. Becaused the textures are updated toroidally like the vertex buffer, you would only have to do this on the edges.

For things like scorches on the terrain, I imagine you could do them just like you would if you did not have support for multitexturing. Geometry clipmaps would not prevent you from cropping another pass down to the area that is required.

Any further ideas on this? Would it work efficiently?

Quote:

Original post by Hexus I have thought about the texture splatting for a while and I think there is an easy way to do it without having a limit on the number of textures. Basically what is happening is that the individual splat textures are being baked into a single texture.

I think that is what they envisage happening - they are doing that for the normal maps. In section 4 of the paper, in the paragraph below the equation, they talk about triangles being 3 pixels wide and normal maps with 1.5 pixels per texture sample. You might want to go a bit higher resolution than half the triangle size for colour textures because they only use a 640 pixel wide window.

Quote:

Any further ideas on this? Would it work efficiently?

Did you see the GScape program that was doing the rounds a couple of years ago? Link to thread. That generated unique terrain textures and looked like it used geometry clipmapping. It was at www.gscape.com but that site went down some time ago.



dave j

Quote:

Original post by Anonymous Poster If you're doing typical splatting, you're generating UVs on the fly in the VS (via the XZ coord), aren't you? And if you're doing that, you're depending on the texture lookup to loop within the texture... and the only way you get that is if each splat texture is separate.

Yes, that is how texture splatting typically works, but what I was suggesting was for the splats to be baked into a single texture. The texture wrapping with the splats would be done while baking them onto the texture, so you would just use normal texture mapping when rendering. I still doubt how efficient it would be to do this however. It requires more CPU processing, and geometry clipmaps aim at trying to move as much to the GPU as possible.

Quote:

Original post by Anonymous Poster It would still seem to be a viable alternative to just build your index buffers such that you draw subsets of each clip level at a time, though, wouldn't it? It wouldn't be as efficient as drawing it all at once, but of course not, breaking things up is never efficient - it's just what you do when you run out of texture stages.

The algorithm actually calls for each clip level to be split up into four regions. Frustum culling further reduces the size of each region. This may help with breaking the terrain up into chunks, but the regions can still extend across the entire width of the screen.

Unless i misunderstood the algorithm completely, the clipmaps are like scrolling "windows". They represent terrain around view point which moves(and the terrain "scrolls" within it). So the data in the clipmaps is dynamic, and a given section of the clipmap does not represent a concrete chunk of terrain at all. So you'd need to map somehow, that let's say chunk[1][1] of a given clip level corresponds to to let's say chunk[12][53] in the terrain. However, even this will not help, as a given terrain chunk can be only halfway in a certain clip level region, and it does not have to be aligned in any way. So this comes down to having to map terrain chunks to a kind of irregular grid of rectangles of different sizes possibly, that represent regions within each clip level that need to be rendered in a separate call with a certain texture. However, this of course makes batching worse. So, is it at all worth the effort?

Quote:

Original post by rejussSo this comes down to having to map terrain chunks to a kind of irregular grid of rectangles of different sizes possibly, that represent regions within each clip level that need to be rendered in a separate call with a certain texture. However, this of course makes batching worse. So, is it at all worth the effort?

Even though each clip region is divided into four render regions, these regions are still larger than most terrain chunks you would see in other algorithms for the same LOD level. So the batching is at worst equal to that of algorithms which use a regular grid of chunks. The only problem I really see is determining which textures a specific region needs when texture splatting. I guess it is not too much different from doing it in other algorithms, but it just needs to be done more often.

hi guys, thanks for all the feedback.. seems i've started quite a discussion!

i've got my head around what "toroidal" means anyway.. but not got much further .. got a bit distracted by my X model loader ;)

right.. so "each level contains an n×n array of verti-ces, stored as a vertex buffer in video memory"

i'm still confused as to how i set out my data.. mainly becuase im not totally clear on regions and levels..

finding it hard to visualise it all :(