I''ve been researching several different LOD techniques for terrain to learn about them overall. I''m kind of on a team that wants to do a game, but we haven''t really started yet. I figured I''d start playing around with terrain LOD, and if anything useful comes of it, maybe we can use it. I''ve done Chunked LOD before, but my method for actually generating each LOD was a huge hack (and therefore very ineffecient). I liked it though, and I still like the idea. But the idea of a continuous progressive mesh seemed appealing to me. I kept thinking that this would be one of the few ways to keep every single detail with good accuracy. However, after doing some research, I concluded that this kind of algorithm (SOAR, and I think ROAM is similar) is a little too CPU intensive for our uses. Sure, you can optimize it, but I''m not sure I have the skills to do so and produce a fast enough result (I know that SOAR requires a heck of a lot of optimizations). But I still really like the way SOAR (and other algorithms) dissects the mesh with the longest edge bisection algorithm. So I started playing around with that and made a program that generates a mesh calculated with a constant error threshold. It was fast - from a straight 256x256 grid of vertices it made a single contiguous triangle strip with more vertices where more detail was needed. I mainly like the way it generated a single triangle strip. But I still planned on using Chunked LOD to ease the use of the CPU. I was trying to figure out how I was going to split up the mesh for the higher levels, and I thought of doing this. Why not use the mesh in triangle chunks? Instead of breaking it up as a quadtree, why not break it up as triangles, which is natural to the mesh because of the longest edge bisection? You can start with the 4 triangles and recurse down them until you have all the chunks you need, and then traverse through them the same way you would with SOAR, except instead of adding a vertex here and there, add a chunk of vertices here and there. So you would have 4 or 5 different meshes at different details, broken up the way Chunked LOD describes it. And the recursion process to find which level to use is the same as well- except with triangles. I haven''t implement this yet, but it seems like it has potential. You could possibly still generate a single triangle strip- cracks can still be solved with simple skirts even. Between each chunk transition simply line it with the skirt, and then the vertex is back in the same position, ready for the next chunk. Anyway, I''m sure there are problems I don''t see with this. Or maybe someone has already thought of this. What do you think?

Well the big benefit of having a quadtree structure is that it''s easy and cheap to cull with your camera..

Maybe you should try implementing some sort of horizon culling algorithm, that should remove most of the invisible chunks of your terrain, that should improve the speed of your terrain..
In fact that would work perfectly with chunked lod..
nearby you have a lot of occlusion which is culled by horizon culling, further away lod kicks in and gives you a cheap approximation of the distant terrain.

quote:Original post by LogicalError
Well the big benefit of having a quadtree structure is that it''s easy and cheap to cull with your camera..

True. But couldn''t you cull a triangle by just checking 3 points?

quote:
Maybe you should try implementing some sort of horizon culling algorithm, that should remove most of the invisible chunks of your terrain, that should improve the speed of your terrain..
In fact that would work perfectly with chunked lod..
nearby you have a lot of occlusion which is culled by horizon culling, further away lod kicks in and gives you a cheap approximation of the distant terrain.

I have implementing a culling scheme before. I don''t see it being much more difficult (or inefficient) with triangles instead of squares. The exact same principle would apply, would it not?

okonomiyaki, are you talking about generating a triangle bintree?

quote:Original post by Lutz
okonomiyaki, are you talking about generating a triangle bintree?

Is that what it''s called? I guess there are things that I''m familiar with, and things that I''m not. I figured somebody would have already thought up of this kind of thing. I''ll google it. There''s a lot to learn!

ROAM uses bintrees if I remember correctly.

Bintree just stands for binary tree and has always zero or two children in the case of terrain rendering. If you do a longest edge bisection of a triangle T, two new triangles T1 and T2 will be build and they are the sons of T.

Frustum culling is also quite easy here. If you know the father triangle T and the min and max heights of all the descendants of T, you can easily figure out how to do it. I think for ROAM they do it like that with thinks called wedgies.

But anyway, although the graphics stuff can be done quickly generating a single generalized triangle strip, the LOD management is still quite CPU intensive.

quote:Original post by Etnu
3 point->box tests for every triangle in your frame vs. culling whole chunks (hundreds+ of triangles) at a time? I don''t think I need to explain the efficiency loss here.

No, because okonomiyaki will use the same principle as a quadtree, so tests will be done for sets of triangles.

I dont think we can call this structure a bintree because bintrees have 2 sons. The structure you will use (if I well understood) will have 4 sons.

I''m pretty sur using this kind of structure is ok, (I''m actually working on something like this so I hope it''s ok ) the only trouble you will encounter is that they are a lot less common than quadtrees so you will have difficulties to find help.

quote:Original post by Lutz
ROAM uses bintrees if I remember correctly.

Bintree just stands for binary tree and has always zero or two children in the case of terrain rendering. If you do a longest edge bisection of a triangle T, two new triangles T1 and T2 will be build and they are the sons of T.

Frustum culling is also quite easy here. If you know the father triangle T and the min and max heights of all the descendants of T, you can easily figure out how to do it. I think for ROAM they do it like that with thinks called wedgies.

But anyway, although the graphics stuff can be done quickly generating a single generalized triangle strip, the LOD management is still quite CPU intensive.

Ah, yes, I understand that correctly, just wasn''t aware of the name bintree :D (I just started researching it recently)
Yes, I can see some easy and efficient frustum culling coming about. I should be implementing it soon, so I hope I don''t come up to a problem with it.
Well, in terms of CPU intensity, it should be about the same as Chunked LOD, which isn''t a huge amount. You are right, LOD management can easily take over the CPU. But if I stick with the whole Chunked LOD concept, where I only recurse a couple times, and then say render certain chunks, it shouldn''t be that bad. Certainly worth the time saved by scratching away all the triangles.

quote:
3 point->box tests for every triangle in your frame vs. culling whole chunks (hundreds+ of triangles) at a time? I don''t think I need to explain the efficiency loss here.

MV is right. Of course I wouldn''t do it for all my triangles in the frame. I''m talking about the triangles in my bintree. Cull a triangle at level 0 and you cull away a fourth of the terrain. And chunks at level 1 and half as big, etc, just like Chunked LOD.

I''m still debating between how well this work out over quadtrees myself. The only way to find out is to do it and run some tests.
MV, definitely go ahead and try it, there''s nothing wrong with trying something uncommon You are right about the 4 children, in a sense. A bintree is still an appropriate name (for my structure) because each triangle still has 2 children. However, each vertex has 4 children, as described in the SOAR paper, and 2 parents. This is what I base my structure off of- I have a class mesh_vertex that enables me to traverse up and down this structure (and prevents cracks, etc, all that good stuff). Pretty neat stuff. No need to go into the details here unless someone is really interested