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

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

## Recommended Posts

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.
[/quote]

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".

1. What are these used for?
2. 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?
3. 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

##### Share on other sites

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".

1. What are these used for?
2. 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?
3. 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?
[/quote]

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.

##### Share on other sites
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

##### Share on other sites
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:

1. The degenerate triangles are created by using the same positions as the outer and inner grids depth, and stitches them together
2. 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.
3. 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:

##### Share on other sites
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

##### Share on other sites
@turch:Thanks for confirming my understanding of this, and for explaining the terms.

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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!

1. 1
Rutin
49
2. 2
3. 3
4. 4
5. 5

• 11
• 16
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009849
• ### Who's Online (See full list)

There are no registered users currently online

×