Sign in to follow this  
EmptyVoid

Chunked LOD with Procedural Planets

Recommended Posts

So I'm working on a procedural terrain engine and I'd like to know what you guys think would be the best way to do this. First what is the best way to fill in cracks form the chunks being of different levels. I think it's more logical to save all the different corners of a chunks in memory. Because I only need all the corners of one chunk per level the most most it would cost per level of detail is 6Kb of memory and I probably could get it allot smaller. Also I have an idea what if I save the index and vertex data in system memory and copy all the chunks to a index and vertex buffer when the chunks are updated. So I can pass all of the data off in one draw call every frame. I know copying that data would be slow but after I do that it would run very fast and I will only need to update it after you walk a good distance but I still want it to load fast on each update. So what do you guys think about those ideas? I'm pretty sure the guy thats making infinity is drawing each chunk one at a time and I think hes calculating the index buffer and not saving it to memory he seems to know what hes doing and I'm not sure if theres somthing wrong with my idea. But it seems to me given the case of procedural planets. That my ideas would be better. What do you all think?

Share this post


Link to post
Share on other sites
Well, I guess your problem needs more explanation. For instance, you mention Chunked LOD but you give no reasons why you discard Thatcher Ulrichs solution with skirts. You talk about procedural planets and mention Infinity. I am fairly sure that guy knows what he's doing and what he's trying to achieve as he's been trying out a lot of different things. Anyway, that makes me think your data is being generated dynamically, and then the best solution may not be Chunked LOD. The way I read the post, it seems you have decided already that Chunked LOD is the best solution and you want people to confirm your idea of crack fixing. But how can we do that unless we know more details of what you want to achieve?

The best way to do things depend on what your goals are. But how large do you expect your planet dataset to be? Is storage going to be a problem? What about visual quality? Do you plan to run an expensive fragment shader for the texturing? What are you using your terrain engine for (GIS? tech demo? game related?) All these affect the answers you will get from people. You need to help us understand the problem better.

Another thing is that you talk about the "corners" of the chunks, which I think is confusing. I expect what you mean are "edges" of the chunks?! Using the wrong terms can make readers think, you haven't researched into the problem enough by yourself.

Share this post


Link to post
Share on other sites
I think "ndhb" has summed it up but your basic idea for reducing draw calls doesn't sound too bad though it might impact on how you manage your texturing. Also the reduction in draw call might not give you any real performance boost as that might not be where you are limited.

How about getting ChunkedLOD working first in a basic implementation for your planet. Hell just ignore the crack filling/skirts to start with entirely if it makes it easier to get it working!

Once you've done that you'll have a basis to begin experimenting and profiling on.

Andy

Share this post


Link to post
Share on other sites
Thanks for the advice and I think the guy thats making infinity is drawing each chunk because hes making it a space game and hes going to be flying very fast over the terrain. Hes probably trying to remove loading time between the updates but I'm still not sure why he recreates the index buffers of each chunk on each update. But I'm not sure he does because I asked him some questions about his engine I'm just guessing thats how hes doing it from what he said.

"The algorithm at heart is geo-mipmapping. I have a quadtree that maintains a list of adjacents, and each time a chunk (I'm using a grid of 33x33 vertices) is split, the adjacents are updated, and the index arrays are rebuilt so that no gap appears between the chunks.

Once you understand geo-mipmapping, it's relatively easy. The planet is a cube made of 6 squares, each square between one of those quadtrees. The vertices are generated in this space, then normalized (which gives a direction going from the center of the planet, to the unit sphere) and multiplied by the radius and the displacement. Displacements are read from a heightmap or procedurally generated on the fly (with a combination of 3D Perlin noise functions). That way, the displacements also match between the cube faces seams.

The sphere you obtain doesn't have a uniform tesselation, but once you get enough details, it's really not noticeable."

and heres something else he said:

"There is one VB, IB and drawcall per chunk.

Good luck."

So I'm just guessing thats how he did it.

Share this post


Link to post
Share on other sites
Also I think my idea to only use one draw call would be better for my project because 95% of the time your going to be on the ground. And my project is sort of a tech demo and a game. It's going to be a MMORPG but we all know those never turn out so even if it don't. I want to enter it in the IGF and use it to show my skills for jobs.

Share this post


Link to post
Share on other sites
You have to take into account how you're going to do texturing and shading. Copying all your chunks on-the-fly into one huge vertex/index buffers and using 1 drawcall implies that you will not be able to switch textures between different chunks. That might or not be a problem, but you better think of it *before* you implement it.

I personally doubt you'll see any performance gain from using such an approach. If you're using a VB/IB per chunk in video memory, this data is static and won't change until the chunk gets split or merged. So the only "cost" associated to it is the 1 drawcall per chunk.

With a single huge VB/IB, you'll consume a precious cpu time and bandwidth to copy data into this VB/IB.. for each chunk and for each frame. Even when the chunk is unchanged. Of course, the advantage here is that you only have 1 drawcall.

So it's a matter of weighting "a few hundred drawcalls + static data" versus "1 drawcall + dynamic data".

The answer might even be video-card dependent.. so if you have the time, the best idea would be to try them both.

Note that in Infinity, the bottleneck is absolutely unrelated to the terrain LOD algorithm. I'm currently fighting against fillrate/pixel shading, and cpu overhead, so improvements to the terrain algorithm wouldn't even bring the framerate up.

Y.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ysaneya
You have to take into account how you're going to do texturing and shading. Copying all your chunks on-the-fly into one huge vertex/index buffers and using 1 drawcall implies that you will not be able to switch textures between different chunks. That might or not be a problem, but you better think of it *before* you implement it.

I personally doubt you'll see any performance gain from using such an approach. If you're using a VB/IB per chunk in video memory, this data is static and won't change until the chunk gets split or merged. So the only "cost" associated to it is the 1 drawcall per chunk.

With a single huge VB/IB, you'll consume a precious cpu time and bandwidth to copy data into this VB/IB.. for each chunk and for each frame. Even when the chunk is unchanged. Of course, the advantage here is that you only have 1 drawcall.

So it's a matter of weighting "a few hundred drawcalls + static data" versus "1 drawcall + dynamic data".

The answer might even be video-card dependent.. so if you have the time, the best idea would be to try them both.

Note that in Infinity, the bottleneck is absolutely unrelated to the terrain LOD algorithm. I'm currently fighting against fillrate/pixel shading, and cpu overhead, so improvements to the terrain algorithm wouldn't even bring the framerate up.

Y.



Thats why your the man Ysaneya! You know allot more them most of us here on GameDev. But what I'd really like to know is why you rebuild the index buffer every time you update the chunks would it not be better to just save this information?


There would be other forms of optimization you could do with it being one mesh. Such as removing overlapping vertices and cashing the vertices reordering the mesh into strips etc.

[Edited because I had more thoughts about the draw method.]

Share this post


Link to post
Share on other sites
Quote:
Original post by EmptyVoid
Quote:
Original post by Ysaneya
...

But what I'd really like to know is why you rebuild the index buffer every time you update the chunks would it not be better to just save this information?

I am pretty sure that the index buffers have to be reorganised, as the cracks between chunks are fixed by changing the triangles at the edges (by changing the indices such that some vertices are unused).

Quote:
There would be other forms of optimization you could do with it being one mesh. Such as removing overlapping vertices and cashing the vertices reordering the mesh into strips etc.

Triangle-strips are rarely worth the additional processing cost on modern GPUs, as triangle-lists tend to be equally fast. Removing overlapping vertices may require completely rebuilding the vertex and index buffers, in which case it will most likely drag your frame rate into the gutter.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by EmptyVoid
Quote:
Original post by Ysaneya
...

But what I'd really like to know is why you rebuild the index buffer every time you update the chunks would it not be better to just save this information?

I am pretty sure that the index buffers have to be reorganised, as the cracks between chunks are fixed by changing the triangles at the edges (by changing the indices such that some vertices are unused).

Quote:
There would be other forms of optimization you could do with it being one mesh. Such as removing overlapping vertices and cashing the vertices reordering the mesh into strips etc.

Triangle-strips are rarely worth the additional processing cost on modern GPUs, as triangle-lists tend to be equally fast. Removing overlapping vertices may require completely rebuilding the vertex and index buffers, in which case it will most likely drag your frame rate into the gutter.


It seems you have no idea what I'm talking about... I know the index buffer needs to be rebuilt but you could just save the edges in memory and not have to do any processing. Optimizing will not slow the rendering time down. It will increase the load time after you've walked a quarter mile but I still don't think it would be as bad as rendering 100 or so chunks with 2178 polygons each and probably an extra 20% more overlapping vertices then my idea.

I want to use a LPD3DXMESH and use this command on the mesh.

Mesh->OptimizeInplace(D3DXMESHOPT_VERTEXCACHE | D3DXMESHOPT_ATTRSORT | D3DXMESHOPT_COMPACT, adjacency, adjacency, 0, 0);

Share this post


Link to post
Share on other sites
Quote:
Original post by EmptyVoid
But what I'd really like to know is why you rebuild the index buffer every time you update the chunks


I don't. While conceptually there is one VB/IB per chunk, you will quickly notice that when you're restricting terrain patches to have at most a LOD level difference <= 1, you have 16 possible IB combinations (north/east/south/west = 4 directions, and for each, the adjacent patch is at the same LOD level, or at +1 LOD level, so that's 2^4 combinations). So I precalculate those 16 IBs, and at render time only find which of the 16 combination my patch is in, and use the appropriate IB.

Y.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ysaneya
Quote:
Original post by EmptyVoid
But what I'd really like to know is why you rebuild the index buffer every time you update the chunks


I don't. While conceptually there is one VB/IB per chunk, you will quickly notice that when you're restricting terrain patches to have at most a LOD level difference <= 1, you have 16 possible IB combinations (north/east/south/west = 4 directions, and for each, the adjacent patch is at the same LOD level, or at +1 LOD level, so that's 2^4 combinations). So I precalculate those 16 IBs, and at render time only find which of the 16 combination my patch is in, and use the appropriate IB.

Y.


Ysaneya your my hero. I'm not even joking!
I'm pretty sure by using only one draw call will only add at most 20% more frames and increase the loading between update by like 500% or more. So yeah it's probably better to use your method in most cases but I'll do some test and I'll report back on the forums about my findings.

Also did you measure the hight of each chunk and increase or decrease the LOD of each chunk based on that? I'm not sure it would work right with the one LOD level difference thing and I'm also not sure it's worth the effort.

One last thing should I use a shader to add the noise and normalize the cube around the sphere. The only thing about that is I would have to recreate those math functions in the engine and use them with the physics engine which is not all that bad but I think you may know a better way. Just so you know I'm using PhysX for the physics. What are you using?

[Edited to add allot more stuff.]

[Edited by - EmptyVoid on March 8, 2008 12:14:46 PM]

Share this post


Link to post
Share on other sites

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