• Create Account

## A few questions about GPU based geo clip maps by Arul Asirvatham and Hugues Hoppe

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

18 replies to this topic

### #1fjholmstrom  Members

172
Like
0Likes
Like

Posted 24 September 2012 - 05:40 AM

I've been looking into creating an implementation of the GPU based Geo Clip Maps described in this paper http://research.micr...oppe/gpugcm.pdf by Arul Asirvatham and Hugues Hoppe. Now, I understand the general idea of the algorithm and how it uses vertex textures to achieve it's performance, etc. But, there is one thing I am not grasping about the section where they describe how the geometry is rendered, more precisely this section describing the vertex layout:

The two paragraphs under this image reads like this:

However, the union of the 12 blocks does not completely cover the ring. We fill the
small remaining gaps using a few additional 2D footprints, as explained next. Note that
in practice, these additional regions have a very small area compared to the regular m×m
blocks, as revealed in Figure 2-6. First, there is a gap of (n − 1) − ((m − 1) × 4) = 2
quads at the middle of each ring side. We patch these gaps using four m×3 fix-up regions
(shown in green in Figures 2-5 and 2-6). We encode these regions using one vertex
and index buffer, and we reuse these buffers across all levels. Second, there is a gap of one
quad on two sides of the interior ring perimeter, to accommodate the off-center finer
level. This L-shaped strip (shown in blue) can lie at any of four possible locations (topleft,
top-right, bottom-left, bottom-right), depending on the relative position of the fine
level inside the coarse level. We define four vertex and one index buffer for this interior
trim, and we reuse these across all levels.

Also, we render a string of degenerate triangles (shown in orange) on the outer perimeter.
These zero-area triangles are necessary to avoid mesh T-junctions.
Finally, for the finest
level, we fill the ring interior with four additional blocks and one more L-shaped region.

I understand how each "ring" is broken into 12 square sections of m x m vertices, and then the holes are patched using a m x 3 block, and since the size is uneven (example above uses 15 x 15 vertices), we also need to fill top or bottom and left or right with an additional strip of (2m + 1) x 2 blocks. But, what I don't understand is the first sentence of the second paragraph, more precisely what is marked as orange in the image and called "Outer Degenerate Triangles".

• What are these used for?
• How are they drawn, is each long section of a orange line a stretched out quad? Does it use the same vertex resolution as the grid itself? Are they drawn using the same shader as the main geometry?
• Are they drawn using 0 size? And if so why?

Basically I'm looking for an explanation for the outer degenerate triangles, why they are there, how they are drawn and how their vertex layout is?

Edited by fjholmstrom, 24 September 2012 - 05:45 AM.

### #2MegaPixel  Members

241
Like
2Likes
Like

Posted 24 September 2012 - 06:57 AM

I've been looking into creating an implementation of the GPU based Geo Clip Maps described in this paper http://research.micr...oppe/gpugcm.pdf by Arul Asirvatham and Hugues Hoppe. Now, I understand the general idea of the algorithm and how it uses vertex textures to achieve it's performance, etc. But, there is one thing I am not grasping about the section where they describe how the geometry is rendered, more precisely this section describing the vertex layout:

The two paragraphs under this image reads like this:

However, the union of the 12 blocks does not completely cover the ring. We fill the
small remaining gaps using a few additional 2D footprints, as explained next. Note that
in practice, these additional regions have a very small area compared to the regular m×m
blocks, as revealed in Figure 2-6. First, there is a gap of (n − 1) − ((m − 1) × 4) = 2
quads at the middle of each ring side. We patch these gaps using four m×3 fix-up regions
(shown in green in Figures 2-5 and 2-6). We encode these regions using one vertex
and index buffer, and we reuse these buffers across all levels. Second, there is a gap of one
quad on two sides of the interior ring perimeter, to accommodate the off-center finer
level. This L-shaped strip (shown in blue) can lie at any of four possible locations (topleft,
top-right, bottom-left, bottom-right), depending on the relative position of the fine
level inside the coarse level. We define four vertex and one index buffer for this interior
trim, and we reuse these across all levels.

Also, we render a string of degenerate triangles (shown in orange) on the outer perimeter.
These zero-area triangles are necessary to avoid mesh T-junctions.
Finally, for the finest
level, we fill the ring interior with four additional blocks and one more L-shaped region.

I understand how each "ring" is broken into 12 square sections of m x m vertices, and then the holes are patched using a m x 3 block, and since the size is uneven (example above uses 15 x 15 vertices), we also need to fill top or bottom and left or right with an additional strip of (2m + 1) x 2 blocks. But, what I don't understand is the first sentence of the second paragraph, more precisely what is marked as orange in the image and called "Outer Degenerate Triangles".
• What are these used for?
• How are they drawn, is each long section of a orange line a stretched out quad? Does it use the same vertex resolution as the grid itself? Are they drawn using the same shader as the main geometry?
• Are they drawn using 0 size? And if so why?

Basically I'm looking for an explanation for the outer degenerate triangles, why they are there, how they are drawn and how their vertex layout is?

They are degenerates triangles used to stich togeter the inner ring boundaries with the outher ring ones. Another more elegant solution would be to just eliminate the T-junctions adding proper tessellation.

### #3fjholmstrom  Members

172
Like
0Likes
Like

Posted 24 September 2012 - 07:15 AM

They are degenerates triangles used to stich togeter the inner ring boundaries with the outher ring ones. Another more elegant solution would be to just eliminate the T-junctions adding proper tessellation.

Okey, so they have the resolution of the inner grid mapped to the outer grid? What I'm saying is that I get *what* they are used for now (stitching), but not how they are constructed. They are squashed on width or depth, depending on which side they're on of the ring. But is it a triangle strip like the blue strip, but just squashed to zero on one axis?

Also, it's drawn as separate strips I assume?

Edited by fjholmstrom, 24 September 2012 - 07:15 AM.

### #4fjholmstrom  Members

172
Like
4Likes
Like

Posted 24 September 2012 - 07:31 AM

Ok, so I did some more googling and also talked to a few friends on IRC, so this is what my conclusion is, if someone could confirm/deny it:

• The degenerate triangles are created by using the same positions as the outer and inner grids depth, and stitches them together
• They are drawn as separate draw calls, and their size ends up being zero as the vertices from the different grids are supposed to align, but it helps to smooth out any interpolation errors.
• If done correctly, this removes errors due to texture interpolation

I drew a simple picture to illustrate, which the grids pulled apart to show the actual degenerate triangles, and I hope this is correct:

### #5turch  Members

590
Like
4Likes
Like

Posted 24 September 2012 - 07:37 AM

Aww I just spent all this time drawing up an explanation and you go and post it yourself

But yes.

The first bit of jargon is "t-junction", which is when you have the situation in the left picture, but with no space between any of the triangles. You "stitch" those together using the black strip on the right.

The other bit of jargon is "degenerate triangle", which is any triangle with an area of 0 (i.e. one that is never drawn). This can be achieved by making any two of the triangle's vertices be at the same location. You can use degenerate triangles to do stuff like render multiple bits of unconnected geometry with one draw call.

Edited by turch, 24 September 2012 - 07:46 AM.

### #6fjholmstrom  Members

172
Like
0Likes
Like

Posted 24 September 2012 - 07:51 AM

@turch:Thanks for confirming my understanding of this, and for explaining the terms.

### #7fjholmstrom  Members

172
Like
0Likes
Like

Posted 25 September 2012 - 06:57 AM

So, I've gotten a bit further into my own implementation and a couple of new questions have popped up in relation to the updating of the elevation map for each level in the clipmap, my understanding of the algorithm explained in the paper is this:

If your clipmap size is 255, you will render the inner most elevation map as a 256x256 pixel texture, which is as the finest level of detail. The second level elevation map is also rendered as a 256x256 texture, but this uses every other elevation point (effectively giving a down-sampled version of a 512x512 sample from the elevation data), and this continues until you have a 256x256 elevation map for each clip map level at different sample rate (1, 2, 4, 8, etc.)

So, my question is then: Why not just render an elevation map which is as large as your view-distance, say 1024x1024 which contains all the data you need at the finest level and then just sample this texture in the vertex shader? I realize this might not work for things like flight-sims, etc. where you need very large view-distances (> 4096), but for everything else, why not? While it might not be as fast, it is far easier to implement.

### #8turch  Members

590
Like
0Likes
Like

Posted 25 September 2012 - 07:30 AM

I'm not sure I understand what you are saying in the last paragraph. The original height map texture is probably going to be thousands of pixels in size - the whole point is rendering massive terrains. You can just use one mega texture while you're developing it, since mip levels will be auto generated for you. Eventually, you'll want to manually create the mip levels because most of the automatic methods don't work as well for height data. (for example you don't want to average a block of pixels, because if one of them has a peak and the rest are lower, the peak height will be averaged on the lower resolution mip, what you want is for the the lower resolution to be as high as the highest point on the original texture)

I started by using one giant 16,384x16,384 texture (1px = 1m). The view distances I had were in the 100+ km range, so the heightmap ended up being tiled. The texture barely fit into my vram and was still just a tiny fraction of what I was able to render. So if I wanted to draw 100 km's worth of (unique) terrain, there is no way it could all fit into one texture. The distance you can have the highest resolution LOD ends up dependending more on how much terrain data you can fit into memory than how many tris you're drawing.

Edited by turch, 25 September 2012 - 07:33 AM.

### #9jmakitalo  Members

668
Like
0Likes
Like

Posted 25 September 2012 - 07:36 AM

I also considered another terrain renderer to replace my geomipmapping implementation. The implementation of geometry clipmaps appeared a bit too messy for me. Then I discovered the CDLOD scheme and I'm very pleased with the results so far. You only need a single small vertex grid and then instance it over the field of view. Of cource, if you specifically want to implement clipmaps and are already aware of CDLOD, then just ignore my message.

### #10kauna  Members

2918
Like
0Likes
Like

Posted 25 September 2012 - 07:47 AM

I made a slightly similar implementation of geoclipmaps and I was pleased with the results until I realized that implementing decals with geoclipmaps is rather difficult since the geometry changes so often. A simple quadtree terrain as used in Frostbyte engine works well for me.

However, the toroidal texture update which is used with geoclipmaps is usable with quad tree terrain too.

Cheers!

### #11fjholmstrom  Members

172
Like
0Likes
Like

Posted 25 September 2012 - 07:55 AM

I'm not sure I understand what you are saying in the last paragraph.

Maybe I was unclear, I'm saying that no matter how large the original terrain data is, if you don't need a very large view distance could you just not only use a single slice of the original data, at say 1024x1024 and then sample this? (this would give ~1km of view distance assuming 1:1 texel:meters) ? Instead of having to mess around with dynamically creating mip-maps for the terrain during runtime, just render the current "viewable" area to a 1024x1024 texture and use that for all levels.

### #12fjholmstrom  Members

172
Like
0Likes
Like

Posted 25 September 2012 - 07:59 AM

I made a slightly similar implementation of geoclipmaps and I was pleased with the results until I realized that implementing decals with geoclipmaps is rather difficult since the geometry changes so often. A simple quadtree terrain as used in Frostbyte engine works well for me.
However, the toroidal texture update which is used with geoclipmaps is usable with quad tree terrain too.
Cheers!

Sorry for the double answers here in a row, forgot about multi-quote. Anyways, I was worried about this also, but then decals will most likely be needed at only the finest (or possibly two finest) levels, the way I see doing this is having two splat maps for the terrain, one for detail textures and one for decals, which are also updated as the elevation map is updated.

also considered another terrain renderer to replace my geomipmapping implementation. The implementation of geometry clipmaps appeared a bit too messy for me. Then I discovered the CDLOD scheme and I'm very pleased with the results so far. You only need a single small vertex grid and then instance it over the field of view. Of cource, if you specifically want to implement clipmaps and are already aware of CDLOD, then just ignore my message.

Thanks, I will look into CDLOD

Edited by fjholmstrom, 25 September 2012 - 08:04 AM.

### #13turch  Members

590
Like
0Likes
Like

Posted 25 September 2012 - 08:10 AM

I'm not sure I understand what you are saying in the last paragraph.

Maybe I was unclear, I'm saying that no matter how large the original terrain data is, if you don't need a very large view distance could you just not only use a single slice of the original data, at say 1024x1024 and then sample this? (this would give ~1km of view distance assuming 1:1 texel:meters) ? Instead of having to mess around with dynamically creating mip-maps for the terrain during runtime, just render the current "viewable" area to a 1024x1024 texture and use that for all levels.

Ah, well yes, if you can fit the entire texture in memory then you can certainly get away without implementing any kind of texture streaming. But if that's the case then I'd say that geoclipmapping is overkill and you might as well just render a 1024x1024 terrain as a regular mesh.

### #14fjholmstrom  Members

172
Like
0Likes
Like

Posted 25 September 2012 - 08:21 AM

Ah, well yes, if you can fit the entire texture in memory then you can certainly get away without implementing any kind of texture streaming. But if that's the case then I'd say that geoclipmapping is overkill and you might as well just render a 1024x1024 terrain as a regular mesh.

Well, not the entire height map texture, but the entire texture of the viable area. I mean, rendering a 1024x1024 terrain as a mesh is still ~1mil verts, which is a bit high.

### #15kauna  Members

2918
Like
0Likes
Like

Posted 25 September 2012 - 09:21 AM

Anyways, I was worried about this also, but then decals will most likely be needed at only the finest (or possibly two finest) levels, the way I see doing this is having two splat maps for the terrain, one for detail textures and one for decals, which are also updated as the elevation map is updated.

In my terrain project roads are/will be visible at some kilometers range so few nearest rings wasn't enough for me.

Otherwise, if you are using some sort of splatting for the decals, then you should be fine.

Cheers!

### #16gjaegy  Members

122
Like
0Likes
Like

Posted 26 September 2012 - 01:34 AM

I would second CDLOD as well, this is what I implemented. It's much easier to understand, and performance are great - TBH I never really understood why geo clipmap would achieve better results than a chunk based method (but I might be dumb )

Also, CDLOD will give you geomorphing without any further effort, which is a very nice-to-have feature.
Gregory Jaegy[Homepage]

### #17fjholmstrom  Members

172
Like
0Likes
Like

Posted 26 September 2012 - 07:28 AM

I would second CDLOD as well, this is what I implemented. It's much easier to understand, and performance are great - TBH I never really understood why geo clipmap would achieve better results than a chunk based method (but I might be dumb )

Also, CDLOD will give you geomorphing without any further effort, which is a very nice-to-have feature.

I've been looking into CDLOD, I read the paper published, but I felt it was missing a few very important details, like how the height map is updated, how to deal with *really large* terrains, etc.

Edit: Also, I'm not a super fan of relying the fact that the GPU has bilinear filtering of vertex textures, even though it's common now.

Edited by fjholmstrom, 26 September 2012 - 08:04 AM.

### #18fjholmstrom  Members

172
Like
0Likes
Like

Posted 26 September 2012 - 09:51 AM

So, I've re-read the CDLOD paper two times now, and I think I got the hang of the general algorithm, it does indeed seem way simpler to implement then geoclipmaps, but in the end there's a section called "granularity issues" that read like this:

One limitation of the algorithm is that a single quadtree node can only support transition
between two LOD layers. This limits the minimum possible viewing range, or the minimum
quadtree depth, because only one smooth transition can be performed between two LOD layers
over the area of the same node. Increasing the viewing range will move LOD transition areas
further away from each other and solve the problem at the expense of having more render data to
process. The other options are to reduce the number of LOD levels, which reduces the benefits of
the LOD system, or to increase the quadtree depth to increase the granularity, which increases
quadtree memory and CPU use. The size of the morph area can also be decreased to mitigate this
problem, but that can make the transition between levels noticeable.

Since the LOD works in three dimensions, this problem will be enhanced when using extremely
rough terrain with large height differences: thus, different settings might be required for each
dataset.

In the provided data examples, LOD settings are tuned so that the ranges are always
acceptable. In the case where different datasets and settings are used, these LOD transition
problems can appear in the form of seams between LOD levels. Debug builds of the demo code
will always detect a possibility of such a situation and display a warning so that settings can be
corrected (detection code is overzealous, so a warning does not guarantee that the seam will be
observable - just that it is theoretically possible).

And I just wanted to ask those people that have implemented CDLOD if this effected any real world implementations? And if so, how much? And what considerations did you have to take for your type of environment/game? The section is very vague on the details, exactly when this issue shows up, et

### #19jmakitalo  Members

668
Like
0Likes
Like

Posted 27 September 2012 - 12:36 AM

And I just wanted to ask those people that have implemented CDLOD if this effected any real world implementations? And if so, how much? And what considerations did you have to take for your type of environment/game? The section is very vague on the details, exactly when this issue shows up, et

Well, I have had only little time to play with CDLOD, but I have found settings that work nicely for me, although they still might be sub-optimal in some sense. I found that too coarse meshing can make the lod transitions quite visible if the camera moves very fast. On the otherhand, with mesh detail that I was planning on having, I cannot notice any LOD artifacts nor transitions. I could also double the currently sufficient mesh detail without too much performance hit. I can't give any precise figures on this issue, I think you just need to experiment with it to see if it will work out for you.

I also recently implemented reflective water, and CDLOD is just perfect for that, because I can just use lower detail grid version for rendering, so it's quite efficient and still easy to implement.

I think that some sort of mipmapping for the height data should be used if there is very high frequency content included. I'm not sure how to do this in vertex shaders.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.