So I'm working on a terrain rendering engine...

[soylent]

A simple one, just as a pet project. Each square "patch" of vertices is rendered as a triangle strip using an index buffer which uses degenerate triangles for stitching togheter rows. What I'd like to be able to do is efficiently remove some polygons from the terrain. Have a hole through the world.

My first idea was to just make them degenerate. But then I'd need a seperate index buffer for each patch that's not to be fully used and generating the lower LOD patches might cause problems with popping. (Still, only a few patches will need the separate index buffers, so memory shouldn't be much of concern).

(The idea behind removing triangles is that you can do stuff like underground passages or caves etc. by just removing some triangles and slapping in a cave based on models or some other scheme that hides the hole and not have to make a silly portal/door that can't be seen through and teleports the player to the other side when they use it)

Is there an existing scheme for dealing with this that's fairly effective or do I have to come up with my own?

p.s. doesn't matter if it's an overly ambitious project to work on and will never amount to any kind of game or something, it's still fun, and far less useless than watching TV.

 

[Rodéric]

I'd go with this:
Chunk LOD, using Index Buffer LOD (keep the full data in VB, swap VB given pos on terrain), using alpha blending for transition between Level of Details to make it smooth.

The good thing is that it's geometry independant, doesn't involve expensive morphing (geomipmap), and works on everything (not just terrain, but models too).

 

[DeanoC]

I'd go with this:
Chunk LOD, using Index Buffer LOD (keep the full data in VB, swap VB given pos on terrain), using alpha blending for transition between Level of Details to make it smooth.

The good thing is that it's geometry independant, doesn't involve expensive morphing (geomipmap), and works on everything (not just terrain, but models too).

My vote as well, tho I'd go even simplier (ignore alpha blending most probably)

Really easy to implement, easy to page out from disk for really big levels, texture LOD is trivial to swap with VB LOD. Use Flanges for fake stitching and you can massive heightfields with tiny CPU cost and maximum GPU speed.

I really wouldn't consider anyother technique unless memory size/bandwidth is an issue...

 

[soylent]

I'd go with this:
Chunk LOD, using Index Buffer LOD (keep the full data in VB, swap VB given pos on terrain), using alpha blending for transition between Level of Details to make it smooth.

The good thing is that it's geometry independant, doesn't involve expensive morphing (geomipmap), and works on everything (not just terrain, but models too).

The little I've been able to find out about chunked LOD does not seem particularily relevant to this, but I might just be a bit thick. Can you clarify?

A clarification of what my 'terrain engine' currently does and what I want out of it:

The height map is split into tiles each consisting of a VB with size (x*2^m + 1) times (y*2^m + 1) vertices arranged in a rectangular grid. Currently I'm using 225x225 vertices(somewhat excessive probably) for the highest LOD, 113x133 for the next, 57x57 for the next and so on. I use just one VB for each tile to conserve space since I can easily just use vertices on every second row and second column in the second LOD, and every forth row and column in the third LOD and so on.

For occlusion culling I'm aiming for simple frustum culling and some kind of simple PVS based on these tiles.

I have an index buffer corresponding to a bunch of different lod levels of the tile one after another in the buffer. This IB can be reused for all VBs that represent a tile of height map without calling setIndices between each LOD change by just drawing a subsection of the IB corresponding to a lower LOD.

The big disadvantage of this scheme is that I need to load the full VB of the highest LOD into memory as soon as I am to display a tile comes into view(obviously you can prevent it from causing stutter and so on by precaching before you need to display arrises or only load the lowest LOD vertices into a vertex buffer and lock it and inserting the next LOD as needed). This may end up eating too much system RAM though.

The biggest problem seems to be being able to *not* draw parts of the terrain on a fine grained basis(i.e. being able to not display an arbitrary set of the triangles on a tile) to deal with pasages _under_ the height map gracefully, like caves and such. This means I can't reuse my index buffer for tiles that require missing height-mapped terrain.

You could probably device a scheme to use degenerate vertices in the VB to prevent some triangles from displaying, but that ties the VB to a specific LOD and breaks my IB reusal scheme.

It seems to mean I have to render these special tiles differently and most likely less efficiently, which is somewhat annoying, but if they're few that might not mean much for performance.

To save some memory I would also have liked to encode position information as a vertex constant defining the corner of the tile and a constant defining the scale of the terrain(stride between vertices of the grid) and then encode position as R and G 8-byte vertex colour components and encode normal as B and A vertex colour and then decode the normal and position information in a in a vertex shader. But I'm not sure if I am even allowed to define a FVF format without D3DFVF_XYZ. Now that I think about it I probably need tangent and binormal for normal mapping, but if the texture is axis aligned and oriented properly I can just generate that from the normal vector. Each may also need blend weigths for the different materials blended in the pixel shader but that might be better handled by a texture that can be finer than the grid of vertices when demanded(e.g. a road that you want to look extra nice or something) and low res when the tile has very slow variation between the blended materials. "materials" will be simple things like normal map and/or gloss map.

I think memory might be a serious concern but I have only done some back of the envelope guesses so far and I haven't seen if the view distance feels sufficient with the current approach and I may be assuming far too dense grids.(e.g. assuming you have say 20x20 VB's with 225x225 vertices each.

 

[soylent]

I've read some papers on it now and I think I have devised a scheme based on a paper about using square tiles tesselated with an isometric grids and alpha blending for LOD transitions. I don't need dynamic terrain so I will not implement it exactly as the paper suggest but it made a convincing case for isometric grids reducing shading errors and looking perceptually smoother for fewer tris.

Instead of using triangle strips I'll go for triangle lists. That way I can very easily punch holes in the grid if I need to and I can try to aggregate triangles where it does not make sense to have a highly tesselated surface(i.e. on nearly flat ground). I'll invent some error metric that seems to make sense(square sum of distances the removed vertices deviate from the plane of the triangle is less then some empirical value?) and check how big an error the lower LOD introduces (including the deviation of the adjacent T-junctions vertices that have to be moved up to the plane of the 4 triangles being aggregated to not leave cracks.).

I decided that I would probably like to not be too stingy about data per vertex because that decision could come back and bite me if I find some cool effect that I want to try and implement that suddenly triples data per vertex(like that spherical cap lighting hack presented by someone from ATi at GDC which would require an extra bent normal + spherical cap area per vertex to do cheap diffuse dynamic area lights for precompiled terrain).

It's fairly hard to put into words. But I hope my reasoning is somewhat understandable.

 

[Rodéric]

Instead of using triangle strips I'll go for a triangle lists.

AFAIR, they are the favored way to push geometry anyway, so don't bother with strips if they get in your way.

You shouldn't have T junctions, if you know before hand the tiles neighboors, you can build a list of 'fence' which will prevent T-Junctions for different LOD between the neighboors.

Your code should be vertex agnostic, in that it shouldn't care about the vertex attributes (Position, Normal, Tangent, TexCoord...), using Index Buffer LOD (ie index the same vertices in a different way) you avoid any trouble. (only the vertex index matter, as well as original connectivity)

 

[soylent]

Thanks. Just one more question before I start working on the LoD scheme.

Do t-junctions within a tile lead to slight visible cracks due to precision errors even if the 't-vertex' is moved vertically to be exactly on the edge of an adjacent triangle as closely as a 32-bit float will allow you?

(motivation for that question: At some point you'll have to asynchronously load tiles from disk and possibly do some quick decompression; and you'll have to cache a bunch of these in RAM, at least 4 times more than will be visible in a 90 degree FoV. In order to save on vertex buffer data I want to use lower LoD triangles in my higher LoD grid when the error of doing so is very small(think rolling hillsides or tarmack roads). I'll then move adjacent T-junction vertices onto the middle of the edge of the lower LoD triangle. (Only on triangles that don't share an edge with the edge of the tile). It's kind of an attempt to get some of the benefits you'd get with irregular tesselation without anywhere near the complexity of implementation, CPU usage and so on, and still have the advantage of using simple tile-based LoD with a single VB for each tile)

 

[Simon F]

Thanks. Just one more question before I start working on the LoD scheme.

Do t-junctions within a tile lead to slight visible cracks due to precision errors even if the 't-vertex' is moved vertically to be exactly on the edge of an adjacent triangle as closely as a 32-bit float will allow you?

Yes you will, because

• The vertex, when it gets to the rasterization stage, will often be represented with much less precision and
• The interpolated edge will be using yet another precision.
• Any geometry clipping will also adjust the positions

HW (and software) renderers will probably only guarantee that two edges will be "crack-free" (which will usually only show up as random 1-pixel holes) if the end points are exactly the same.

[edit: Added clipping comment]