Jump to content
  • Advertisement
Sign in to follow this  
RobMaddison

Terrain LOD stitching on the GPU

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Further to my previous post on the subject, this has saved me so much development time and terrain engine complexity, not to mention the large amount of index buffers and memory usually associated with LOD stitching, so I thought I'd share it with everyone. I've done a fair amount of research on the internet to see if it's been done before and, as yet, I haven't found anything. I have only tried this with my terrain engine where one regular grid vertex buffer is used for all sizes of terrain chunk (by scaling and translating). The one and only index buffer should include all vertices as normal in the standard quad format shown in the first diagram below - you may be able to manipulate the algorithm to suit your own terrain. Here's how it works: 1) Pre-render stage In the pre-render stage, traverse the quadtree picking out chunks for rendering and add them to the render queue. During this stage, fill in a matrix of LOD levels - for a 4096x4096 terrain with a 32x32 high-LOD patch size, this involves filling a matrix of [128][128] - but only those elements that fall within the viewing frustum and only the outer edges of each of those elements need to be set. I believe this is standard practise for pre-determining the LODs of neighbouring patches. 2) Render stage Process the front-to-back-sorted terrain render queue and, for each chunk, pass to the shader: a) a true flag if the tile needs any stitching at all (from the LOD matrix created in pre-render stage, check each neighbour of the current patch) b) the 4 neighbouring LOD changes in powers of 2 (e.g. float4(n=0, s=0, e=4, w=2) = 2 LOD changes east (4), one to the south (2) - zero means no change). The reason for the power of two value will be explained next but the sequence is (0 - no LOD difference, 2 - one LOD difference, 4 - two LOD differences, 8 - three LOD differences, 16 - four LOD differences, etc) In the vertex shader, if any stitching is required, check if the vertex position is on any of the relevant edges of the patch and use a simple modulo algorithm using the LOD difference value passed in to move the vertex along x or z if it doesn't share a vertex position with the neighbour at that point. This is the reason for the power of two value - the shader can automatically select which vertices need moving and also their distance simply by using the modulo of the value passed in - if the modulo result is zero, the vertex will be shared between patches (regardless of LOD difference) and is not moved. So if the patch being rendered is level 6 (highest detail) and its neighbour to the north is level 5 (i.e. half the detail), the first vertex in the x direction (e.g. x=0, z=32) would remain in place, the second vertex (x=1, z=32) would be moved to (x=2, z=32). In the next quad, the first vertex (x=1, z=32) would also be moved to (x=2, z=32). This will create a degenerate triangle (visually) because the first triangle in the second quad will have two vertices the same (i.e. x=2, z=32). This algorithm doesn't change for higher differences in LOD due to the nature of the modulo, so if the northern neighbour is 2 LOD jumps, the higher modulo causes more vertices to move across to the next shared vertex. The amount to move each vertex is the LOD difference value passed in minus the modulo of the x (or z) position and the difference value passed in. NB. All 'position' values are local to the patch - e.g. 0-32, 0-64, 0-128, etc. Once the vertex is moved (or not, in the case of vertices in the middle of the patch), the height is retrieved from that point in the vertex texture - as it is for normal vertices. As an example, consider the following diagrams. The first one shows the normal quad structure (showing local xz values). The second one shows the top quad row of a patch which is stitched against a lower LOD (less detail) to the north. The arrows demonstrate the direction of the vertex movement and the lettering shows the new positions of the triangles. Note that C and G have essentially collapsed onto themselves and so are not shown in the second diagram (although they will, of course, be processed).
  0   1   2   3   4
32*---*---*---*---*
  | A/| C/| E/| G/|
  | / | / | / | / |
  |/ B|/ D|/ F|/ H|
31*---*---*---*---*
  |  /|  /|  /|  /|

      --->    --->
  0       2       4
32*-------*-------*
  |  A  _/| E   _/|
  |  _ // |  _ // |
  |_/ B/ D|_/F / H|
31*---*---*---*---*
  |  /|  /|  /|  /|

Texture coordinates work as normal as they will be calculated in the shader based on the new position of the vertex - this doesn't have any impact. This will currently only work for cards that support dynamic branching. It could possibly be optimized further to remove some of the branching so it'll also work efficiently on older cards too. Although it does use branching which can be expensive, there are only at most between 1 and 4 branches per vertex and one 1 for the majority of vertices (those not along an edge). I've got a very high-spec GPU and there is barely any difference (if any) using the extra branching with regard to frame rate. I haven't had time to try it on my older card yet. One thing to mention is that if you are geomorphing your terrain patches - you might be restricted slightly in that you won't be able to geomorph the outer edges of a patch if there is a LOD change in that direction. The reason being that the adjoining vertex in the lower LOD neighbouring patch, maybe be partly geomorphed which means it won't match up to the adjoining vertex in the current patch. I don't think this is limited to only this algorithm, but I managed to get around it quite easily with barely any visual change - just don't geomorph any vertices along an edge if it has a lower LOD to its adjoinging neighbour. I'd be really interested to hear if anyone chooses to implement it and if it is of benefit. If you have any questions regarding the algorithm, I'd be more than happy to help.

Share this post


Link to post
Share on other sites
Advertisement
You should check out Restricted Quadtree Triangulation (http://www.ifi.uzh.ch/vmml/admin/upload/Vis98.pdf). RQT handles stitching of discreet chunks much better than geoclipmapping, and also gives the added benefit that it will give you auto decimation based upon displacement metrics (rather than naively increasing resolution on things closer to the camera that don't need it)

You should also check out the XVOX demo (http://users.belgacom.net/gc610902/)
XVOX does some nifty tricks with morphing patches between tessellation levels over distances, and looks really good (although it suffers from additional vertex load being sent to the shader, as well as 2 stream lookups per 1 vert to do interpolation)

~Main

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!