Sign in to follow this  

Confused with chunked LOD!

This topic is 4831 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

Hey all, Well I'm now working on implementing chunked LOD into my terrain, as I think it's the last thing I need to look into performance-wise for my terrain engine. I'm severeley confused by it though, mistakenly, I assumed that the paper by Thatcher Ulrich would explain everything I needed to know. As I'm sure anyone who has implemented it will know, it also requires that you understand view independant progressive meshes, which I *think* requires you to understand the winged edge or a similar structure. Now after having read up on everything I can find, I'm still somewhat confused, as it's a much larger topic to take in than I realised it would be. Ideally if anyone has any, or knows of any sample code that I might be able to pick apart and use to help me implement it myslf, that would be ideal. I realise that I may have to completely rethink my way of creating terrain. Currently, I simply load in a set of heights from a .raw file (or from a saved file from my editor) assign these into a grid of vertices. I then create index buffers such that the triangles are arranged roughly as follow: |-----| | /| /| |/ |/ | ----- | /| /| |/ |/ | ------ First of all, I'm wondering if I'm making my life hard by not using the typical diamond arrangement of indices that I seem to see in many wireframe screenshots. I've roughly worked out a way to create and fill a winged edge structure, but now I realise that this should be updated after each edge collapse, I'm finding it hard to work out how exactly to update it, or whether to rebuild it entirely which would mean that I have to adapt my winged edge routine as it currently only works for a heightmap with indices laid out in a grid as above. In other words, I don't think it would work once edges are removed. I also am stumped as to an easy method to calculate the error metric upon an edge collapse, I know that you should take the maximum deviation from the affected vertices height and use that, but am stumped with working out what height the terrain is going to be at the point where the vertex once was. My current hack is to calculate the average of the surrounding heights, but obviously that wont work if any of the surrounding vertices are removed as well. On top of all this, I'm also confused about edge collapses (though this may have to do with my non-typical indices arrangement). When collapsing an edge, so far as I gather you collapse the two verts of an edge into just one of the verts. This also kills off the two triangles on either side of the edge. I'm not exactly sure what this means in relation to recreating my index buffer. When it says that the two triangles are killed off, I assume this means that the other vertices in the triangle (not part of the collapsed edge) are not used again by any other triangle, and instead when referencing those vertices, the next index in the index buffer thatisn't part of a killed triangle takes it's place? Is that right or am I way off base... I suspect I'm just confuse and completely wrong!! I think my problem is that I'm approaching the building of the heightmap in the wrong manner, I suspect that rather than filling a winged edge structure based on what I know about my regular grid of verts, I should be approaching it from the angle of treating every triangle separately rather than trying to account for the general pattern, and then extracting the winged edge data from the data held by each triangle (or quad or whatever), rather than using an algorithm to fill in the data. I guess that if I approached it from this way, I could rebuild the winged edges much more easily, and I suspect that calculating error metrics may be tied in with this as well. Well I hope I'm making sense, for extra info I'm using Direct3D and my triangles are arranged as triangle lists. Could anyone be so kind as to point me in the right direction!!? Thanks a lot, Steve

Share this post


Link to post
Share on other sites
Um i haven't read the ChunkedLOD paper in a while so won't comment on it until i've read up a bit.

I personally dont like using ROAM, progressive mesh or other continuous LOD methods for terrain, i feel that they're usually a waste of time unless you're just writing a terrain renderer and there are better things you could be spending your time on than processing a terrain mesh.

So to help instead of rant [smile] i used a simple quadtree, with leaves containing the terrain mesh, and "skirts" to avoid doing any runtime geomorphing, texturing is done based on Charles Blooms "Texture Splatting".

I'll have to read ChunkedLOD again to make sure but couldn't do away with the whole winged edge system? Modern GPU's handle triangle lists at least as fast as triangle strips.

Andy

Share this post


Link to post
Share on other sites
Ookay one quick read later of his paper.

You can safely skip the implementation of a progressive mesh algortihm, well for now anyway, you might feel you want it later but i dont personally think you will.

Instead of having anything fancy just define your terrain for each chunk as you have been doing, i.e. as a regular grid of vertices and build up your triangle mesh, perhaps adding a flange or "skirt" to hide any lack of geomorphing or other blending between LOD levels.

Doing the above will make your transition to Chunked LOD much easier, and you can still implement a progressive mesh system later. Although i wouldn't as a regular mesh is much better for in game collision queries.

Andy

Share this post


Link to post
Share on other sites
As I understand it, the basis of Chunked LOD is a quadtree with a mesh at every node, and if the error at a node is above a threshold, then then consider rendering the 4 sub-nodes instead. The rest is implementation detail and optimization.

Generally the mesh for each node is derived from the heightmap, but how the mesh is generated is up to you. Just to get it working, do something simple like remove every other vertex at each level.

For a 1025x1025 heightmap, your quadtree might look like this:

The root node ...
contains a 33 x 33 mesh (every 32nd vertex), and each of its 4 sub-nodes ...
contains a 33 x 33 mesh (every 16th vertex), and each of its 4 subnodes ...
contains a 33 x 33 mesh (every 8th vertex), and each of its 4 subnodes ...
contains a 33 x 33 mesh (every 4th vertex), and each of its 4 subnodes ...
contains a 33 x 33 mesh (every other vertex), and each of its 4 subnodes ...
contains a 33 x 33 mesh (every vertex).

Share this post


Link to post
Share on other sites
Quote:
Original post by JohnBolton
The root node ...
contains a 33 x 33 mesh (every 32nd vertex), and each of its 4 sub-nodes ...
contains a 33 x 33 mesh (every 16th vertex), and each of its 4 subnodes ...


why the whole mesh? it should depend on what you want/need. save memory or get maximum speed. you can save the whole heightmap once and get away with one index buffer per level, then each node would only story a) a pointer to the right index buffer (a byte as index into an array if you REALLY need to save memory) and an offset into the vertex buffer to draw the right piece.

compared to geomipmapping
the good thing is: you dont waste performance with tons of low detail patches with only two triangles per call.
the bad thing is: if you need high detail at one position all the neighbours have to be drawn at high detail as well.

Share this post


Link to post
Share on other sites
Hmm, okay, thanks for all the advice which I'll try to take in more thoroughly once I'm home later. I'm still a bit confused though, as I thought the point to Chunked LOD was the progressive mesh? The point being that you don't just remove "every other vertex" or anything like that, but that you remove them selectively in a pre-processing stage to ensure that you only have as many verts as you need for any given LOD stage, given their projective error. So basically you pre-generate a mesh and then choose the appropriate one for the distance from the view.... and the bit I'm stuck at is pre-generating the mesh, but the methods I'm seeing here at first glance just sound like entirely different techniques??!

Cheers,

Steve

Share this post


Link to post
Share on other sites
Yeah a full implementation of ChunkedLOD could use the progressive mesh system that he does, what im saying is that you can implement everything else on the way to that so that you have a fully working terrain renderer without it, but with all the existing benefits.

The only problems are that you're memory usage will be larger because of the unoptimised meshes that populate each node of the quadtree.

You can then implement a progressive mesh scheme later if you feel its worth it. (but i never have)

Andy

Share this post


Link to post
Share on other sites

This topic is 4831 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this