   Procedural Planet - Split Decisions
  Hi, I am trying to implement the LOD algorithm for a planet from http://www.gamedev.net/reference/articles/article2074.asp (Dont know the tag for links...sorry). I know this article method isn't the best LOD algorithm but I needed one that was simple and quick to implement.However I am struggling to think of the best way to determine what triangles to split and merge. The method holds all triangles in a list, and all parents in a separate list, to be merged in where necessary. I was thinking about using a error metric similar to ROAM but a bit simpler: if(fDistToTri/fTriEdgeLength * fDisplacement < threshold) spliti.e the closer the camera, the bigger the triangle and the bigger its displacement from the surface; the more likely it is to split.I loop round for all the triangles in the list; before I check a triangle I test if it is in FOV. However the splitting decision are pretty rubbish. Does anyone have any other suggestions for the split determination?Much appreciatedEDIT:Oh one other issue is that the triangles are held in a list but the VB requires an array. This means every time a split or combine occurs I have to loop round copying the vertex data into the array. The problem is that I cannot just add the new triangle to the array, as adding a new tri to the mesh changes the positions of indeterminate other triangles.   
  I've implemented a very similar algorithm for my procedural world and am using it with ridged multi-fractals. I simply refine based on the delta between the true position of the midpoint of each edge and its current position and then factor in the distance from the viewer. http://profile.imageshack.us/user/polypterus/images/detail/#58/asteroid1oq5.jpgI use breadth first traversal of my tree for refinement with the caveat that there can only be one level of difference between refinements, so if I refine a triange and it's neighbors need refinement I push them on the traversal queue (note: my queue is really a stack/queue combo and I push them on the front like a stack for this case)  before going on.  To do this I have set up my data structure so I can find neighbors quickly. As I am refining I am also pushing triangles on a separate stack for a bottom up unrefinement pass. So in short I go down on refine and up on unrefined. This works pretty well for me.Another thing is you get gaps where there are differences between triangle levels so I fill these with special non-equilateral cases.Also if this is for a game you need to think about collision detection so some bounding information comes in handy.Edit: actually I don't think the refinement and unrefinement criteria is so important. Or rather it's not something that is hard to change. Once you get your data structure in place you can try different things for that part of it.[Edited by - polypterus on April 24, 2009 3:16:15 PM];  Wow thats pretty awesome. I am not implementing it for a game I am doing a comparison between a solely GPU generated planet and a CPU generated planet for my honours project.Ill try implementing your method of refinement. The problem with mine was that triangles were not split smoothly, in that nothing would split until the camera was really close to the terrain and then lots of triangles would be split.Thanks for the reply though I have not had much luck getting responses lately lol.   ;Quote:Original post by DownieWow thats pretty awesome. I am not implementing it for a game I am doing a comparison between a solely GPU generated planet and a CPU generated planet for my honours project.That sounds cool. I do my stuff all on the CPU in double because my planets can get large. I then convert to float for the GPU and keep (0,0,0) near the camera so the z-buffer can still work.  I have a loop that constantly transfers and recalculates for new camera positions. When the new model is ready it tells the graphics card to switch over.  If you generate in single precision, stuff that is far from (0,0,0) will necessarily have less precision and when you get up to it, you will notice your terrain is rougher.  Just a couple more things to think about. Quote:Original post by DownieIll try implementing your method of refinement. The problem with mine was that triangles were not split smoothly, in that nothing would split until the camera was really close to the terrain and then lots of triangles would be split.You can always put some fixed limit on the delta so it doesn't refine after a certain point. That might help even things out a bit. I tend to like to put a lot of controls on stuff like this so I can play with it. ;Quote:You can always put some fixed limit on the delta so it doesn't refine after a certain point. That might help even things out a bit. I tend to like to put a lot of controls on stuff like this so I can play with it.Thats a good idea. Yeah it's probably better to have lots of controls such as that so it can be tweaked to suit performance or to give more detail to certain areas.Thanks for the advice   ;  Oh yeah forgot one thing. There are two ways to measure the delta between the segment and its new split point. You can measure it vertically along the line defined by the world center point and the new split point (which for my application is faster), or you can measure it perpendicular to the old segment.  This last way tends to be give better results because the delta is consistent no matter how steep your mountains are.  It also works if you ever want to support overhangs.  Again you can play with this and see how it turns out.   ;  Yeah I was doing it vertically from the core of the world it just seemed the most obvious way. The splits seem to be smoother now. I forgot I still had my mem mgr code in so that was slowing the splits down a bit lol.   ;Quote:Original post by DownieOh one other issue is that the triangles are held in a list but the VB requires an array. This means every time a split or combine occurs I have to loop round copying the vertex data into the array. The problem is that I cannot just add the new triangle to the array, as adding a new tri to the mesh changes the positions of indeterminate other triangles.This sort of triangle sub-division algorithm worked pretty well back in the days of immediate mode, but they are not very sensible on modern cards. Quad patches seem to to be the way of the future: start with a cube, and subdivide each face into four rectangular patches, ad infinitum. Each patch is actually a grid of vertices, which can be rendered in a single draw call.Quote:Original post by polypterusThat sounds cool. I do my stuff all on the CPU in double because my planets can get large. I then convert to float for the GPU and keep (0,0,0) near the camera so the z-buffer can still work.  I have a loop that constantly transfers and recalculates for new camera positions. When the new model is ready it tells the graphics card to switch over.  If you generate in single precision, stuff that is far from (0,0,0) will necessarily have less precision and when you get up to it, you will notice your terrain is rougher.  Just a couple more things to think about. Quad patches solve this problem as well, since each patch can have its own local coordinate system. Then the vertices are specified in patch local coordinates, and the patch location is specified in planet coordinates. To make this work, you need to transform the camera location into patch coordinates prior to rendering (instead of transforming the patch into camera coordinates, as is usual).   ;Quote:Original post by swiftcoderQuad patches solve this problem as well, since each patch can have its own local coordinate system. Then the vertices are specified in patch local coordinates, and the patch location is specified in planet coordinates. To make this work, you need to transform the camera location into patch coordinates prior to rendering (instead of transforming the patch into camera coordinates, as is usual).Hmmm, Sounds like an interesting solution. Have you tried it with large data? I always worry about rounding errors giving you single pixel gaps or something when you move the camera around for each scene. However if it works, it works. I suppose you would need to do collision detection on the GPU if you are doing refinement on the GPU. Either that or read the data back to the CPU somehow. It's always the little things that kill you. I'm just wondering if this would work in a complete game solution. Do you have a lot of experience with this method?;Quote:Original post by polypterusHmmm, Sounds like an interesting solution. Have you tried it with large data? I always worry about rounding errors giving you single pixel gaps or something when you move the camera around for each scene. However if it works, it works. I suppose you would need to do collision detection on the GPU if you are doing refinement on the GPU. Either that or read the data back to the CPU somehow.I synthesise the heightmap on the CPU, as procedural generation on the GPU is just too flaky (precision issues, driver issues, etc.), and we need the heightmap CPU-side for physics. However, I use shaders to generate the vertex data from each height map, as well as normals, material data, etc.Quote:It's always the little things that kill you. I'm just wondering if this would work in a complete game solution. Do you have a lot of experience with this method?My implementation is far from perfect, but Ysaneya uses this method, and discusses the challenges and benefits in some detail.   