Terrain LOD

Game Play & Game Design
#1

Hi all,
Ive got no where else to post this, so might as well be here. I kinda thought of a terrain level of detail algorithm that might just spank the living daylights out of any other algorithm (emphasis on might ::slight_smile: ). Imagine the camera is looking down onto the xz plane like in an RTS game…

The outlines of the “simple” algorithm are:
-Create a n*m grid that is orthogonal to the near plane of the camera (i.e. in post perspective space)
-Project this grid onto a plane in world space (probably xz plane)
-Displace the vertices’s by a heightmap
-Render the grid

If you can predict the outcome for this algorithm, you’ll see that the vertices of the grid before step 3 are no longer evenly spaced, they are more compacted towards the camera’s location on that plane.

The algorithm gives you these advantages:

  • Vertex poping no longer is a problem as the frame to frame coherency is good, the features are introduces slowly from the horizon towards the viewer and geomorphing is done implicitly.
  • No polys/vertices exist outside the camera’s frustum, as opposed to SOAR where frustum culling of each DAG node is needed to do frustum culling and reduce the stress on the GPU. I dont know much details about ROAM, but it seems that polys do exist outside the frustum but are just big polys, like in SOAR.
  • Indices are preserved, one less thing to calculate per frame, all other implementations need to recaculate based on the new tesselation
  • You can restrict the number of poly’s the mesh is to the exact poly, i believe that is impossible to do directly in SOAR or ROAM. In soar, you can do it indirectly by specificing a higher screen space tau value, but no direct control is given.
  • No data paging issues at all since the only data that needs to be stored is the actual height map, not any other queued data (in SOAR, this will be the DAG stored in a special way to avoid the need to do manual paging and memory control) and thus, your terrain height field data can be as big as you want it to be as long as it fits into RAM.

As you can imagine, doing the calculations needed for step 2 per vertex per frame is alot of work on the CPU (you can offload the work to a vertex shader, but you need to be able to do a texture lookup on the vertex shader, which is an NV only operation at the moment). Im pretty sure I can work out a way to do this using a heuristic based on the dot product between the camera and each of the x and z axis. That is then used along with the distance between the camera and the vertex to calculate its x/z position. To avoid the projection stage, the mesh can be made every frame in world space coordinates as a uniform grid and then the heuristic is used to create the mesh into a non-uniform grid, this method will also avoid the nastiness of the projection “back firing” if the camera isn’t pointing at the xz plane ( if you dont know what why back firing appears, google for “projective textures”)

I really wish I could throw everything down and just work on this, unfortunetly, its only getting my free time at the moment, which isnt alot. I’ll try and implement something in the next few weeks, and then possibly write a paper about it, we’ll see. If anyone implements something before, let me know, im very interested :slight_smile:

DP

#2

For the geometry this is a pretty good solution, although the GPU doesn’t like dynamic data. Texture-lookups on NV cards using at least 16 bit heightvalues could take care of that as long as the camera is rotated along the Y axis. Rotating along the X or Z axis will require additional math for the cpu (if I understand your plan correctly).

The main problem for this kind of renderer is how to texture it probably. You’ll have UVs that are far from usable. How to make a rock-face on a steep slope if your vertices and polygon-dimensions are always changing. You can’t really “apply that texture” to the rockface anymore. You’re either bound to 1 surface-texture, or procedural textures in the fragment-shader. Both don’t give a lot of artistic freedom.

A little problem will be that you’ll need a fairly high-resolution screenspace ‘grid’, like a ‘node’ every (4 to 8)^2 pixels, with larger spaces between the nodes you’ll notice the terrain ‘slides’ over the grid.

Last remark: I’ve already seen implementations of this idea for the rendering of water. The advantage here was that it would all be procedural (textured / geometry) anyway, and due to the dynamic surface the ‘sliding’ wasn’t noticable.

#3

You could do glTextureSubImage on the texture data and use texgen to create texture coordinates for projective textures and project the texture from the camera’s perspective, the texture data can then be whatever you want it to be. Althought i dont know how significant the speed drop would be in using glTextureSubImage every frame. Giving you the artistic freedom you wanted. Another solution would be to figure out what this vertex position is relative to the terrain data and use that as the UV while looping through the vertices adjusting their height. Im pretty sure this is an easily solved problem and im not too concerned about it at the moment…

I think this can be overcome by using the normals calculated using the previous frame’s vertices, or even better, by using normal mapping on the GPU.

Have you got the relevant paper for this? I would be really interested in seeing this…

DP

#4

About texture-projection and glTextureSubImage… keep in mind that the polys you’re ‘painting’ with textures are not rectangular (world-space nor texture-space nor screen-space). Anything you’ll try to get certain (subsets of) textures rendered at a certain part of the terrain, will result in massive math and lots of calls to update the texture, with bad performance.

But somehow I get the feeling we have other interpretations of what we’re talking about.
-> are you talking about texture-projection in EYE or WORLD coordinates?

Not really papers - I coudn’t find them, but here is the demo:
http://www.cs.utah.edu/~felsted/cs5610/final/references/packmk2/

#5

Ahhh, the papers

http://www.cs.utah.edu/~felsted/cs5610/final/description/projectWriteup.pdf
http://www.cs.utah.edu/~felsted/cs5610/final/references/papers/simulatingOceanWater.pdf

#6

I skimmed over those two papers and both of them didn’t remotely reference to anything like this.

Yeah, i thought more about it after I posted this, but the second idea of getting UV coordinates is still valid.

Typically, to obtain a sub-pixel height for a point, you LERP between the 4 pixels that surround this, giving you the typical height, its a simple matter of dividing the vertex position by the dimension of the height map in order to obtain UV coordinates in the range of [0,1].

In both :wink:

The optimised version that im still working on will be exclusively in world coordinates, the above “simple” algorithm is in both, initially in post-perspective coordinates which is then put back through the mathmatical pipeline to world coordinates. (I.e. a division of each vertex by the camera’s projection matrix)…

Also, if the camera’s angle between the x and z axis never change, the grid never changes either, so you can avoid the whole business of projecting the mesh from post perspective coordinates to world coordinates, saving you some computation…

DP

DP

#7

Unfortunately, this isn’t a new idea (and one I’ve had myself too). The problem is that as the camera moves the terrain is going to ripple in disturbing ways - and unlike geomorphing the rippling is going to be worse the closer to the camera the terrain is. To counter this rippling you’d need a ridiculously high resolution terrain grid, ideally high enough that each pixel actually maps to a single vertex (you can probably calculate the exact nyquist frequency/resolution for a given view but thats a little beyond me).

If you poke around the opengl.org forums someone posted a demo which used this method a while back. It was fairly simplistic in its texturing, but even this showed how distracting the rippling effect is. :frowning:

#8

Yes, that was what I meant with the terrain ‘sliding’ over the grid. That’s why it’s only (?) usable for water/liquids with minimal height-differences.

You might have a increase in detail the lower on the screen you get, but by looking up->down that makes no sense.

I think a node every 8 pixels would be good enough to get rid of the artifacts. I’ll see where I can find that demo…

[quote]I skimmed over those two papers and both of them didn’t remotely reference to anything like this.
[/quote]
Launch the demo (for either nvidia or ati) and go through the options until you find the ‘point-view’. You’ll see the points are distributed in a screen-space grid. I’m sure I read about it in a paper on their side, I didn’t have the time to read the papers, but it must be in one of those directories. Might be worth the effort to manually find it yourself there.

#9

The reason for the “sliding” over is due to, like you said, insuffecient number of vertices, to stop that, one solution, like you said again, is to increase the number of vertices. Another solution (i think) is to use cubic interpolation to obtain the sub-pixel height values instead of linear interpolation. What this effectively creates is that each pixel in the height map data as a control point and the mesh produces is a bezier mesh based on the control points. Which is sweeeeeeet for smooth terrain, but that still requires some mesh tesselation. Even with the increased number of vertices, you can still push the number of triangles you would normally use for the entire terrain in the scene into this one mesh, which results in better looking terrain anyway…

DP

#10

I’m a bit worried about this whole thing.

If I understand the idea correctly, the grid in screenspace is “projected” into worldspace on the XZ (flat terrain) plane, to retreive the Y (height) value of the terrain.

But by finding the Y and pushing the terrain geometry straight up the nearest ‘node’ it might very well be far from the camera. So you’d need the grid to go outside the screen-dimension, down the screenspace Y-axis.

So either I missed something obvious, or I misinterpretated the whole story.

#11

After projection, the Y value is simply a obtained from a get height method that LERPs the 4 nearest pixels in the heightmap. My point is that if you use LERP, you get this sliding business. But if you cubically interpolated the 4 pixels instead of linearly interpolating them, then that might solve the problem…

The getting of the y value of the vertex happens in world coordinates.

DP

#12

A ray projected forward in 3d space from a certain camera-height, will point to the XZ plane at height 0.0 quite far from the camera. Especially if the terrain is very high (>5m). So you’ll need the grid to continue below the screen (in screenspace).

> image describing the problem

The higher the camera is from 0.0 and the closer the terrain is to the camera (high terrain), the more you’ll need to go “down” in screenspace, resulting in extreme dense meshes, if you keep the grid linear (so don’t ;))

#13

It won’t. No matter how you interpolate your heightmap data the end result is still a continuous surface. Now you’re going to sample that at various points (the vertices) and linearly interpolate between them for the final image (because the triangles are basically a lerp between the vertices). On it’s own this isn’t really a problem, because if your sampling frequency is high enough then you can get a pretty good approximation of the original surface.

But as the camera moves, your sample points shift and change. Each camera position will still be a reasonable approximation, but it isn’t going to be the same as the frame before it. In fact unless you’ve got a perfectly flat world it’s unlikely to ever be the same.

#14

Realising that this “sliding” problem wont go away, ive had to think about a new way of doing it, what do you think about this one ?

-Make a highly tesselated plane and upload the vertices to VBO, same with normals, texture coordinates and colours if you want…
-For each vertex, have a “block” which has the vertex position and bound to the neighbour vertices (sphere is preferable, see below)
-During rendertime, frustum cull the blocks (thats where sphere is faster), then your left with the blocks that are visible.
-Use a distance based heuristic for calculating the indices so that the blocks nearer to the camera have a higher tesselation than the ones fruther away.
-Because you know which blocks coorespond to which vertices, you can geomorph the vertices to make it look better and still be fast as you only upload the newly moved vertices to the VBO…

Its basically as fast as the one above, keeps most of the data static in VRAM and is fully dynamic in terms of LOD…

What do you think?
DP

#15

Chunked LOD will beat the crap out of that algorithm.

Uploading the new indices to the GPU might be fairly fast, but recalculating those very same indices will be a real bottleneck for the CPU.

Chunked LOD has the advantage of being completely static at both the CPU and GPU side. Terrain has the advantage of not being really dynamic, so why not take advantage of that? And to prevent geo-popping when changing LODs, you can easily interpolate between the LODs (using a high-resolution low-precision intermediate LOD) with a vertex shader, using a technique that you recently poked fun at.

So no, there are better algorithms out there.

#16

I asked for clarification on your technique and pointed out some limitations of it, poking fun is a different matter. And besides, the maximum textures size is 4096x4096 and vertex texture fetches are only on the highest end cards, so you are really limiting your options.

I never asked whether my algorithm was better than static terrain because i doubt anything can be faster at the moment, i merely asked if its an improvement over the projected grid approach, read the question carefully next time, and if you have nothing constructive to say, dont say it.

DP

#17

Texture sizes have nothing to do with it, really, nothing. I’m not sampling textures in the vertex-shader, that would make it quite slow.

Indeed it’s a vast improvement over the projected-grid approach, for obvious reasons.

[quote]read the question carefully next time, and if you have nothing constructive to say, dont say it.
[/quote]
Little hostile there mate, relax.