Chunked Level of Detail for Rendering Planetary Heightmaps

[Pryme8]

Has anyone done this yet in babylon JS I see a couple of examples but none of the projects I can reference have worked out the camera height in the process or the blending between LOD layers.  I am going to start trying to make a working example from the paper http://www.vertexasylum.com/downloads/cdlod/cdlod_latest.pdf
but would like to see how others have handled it.
I have looked at github.com/darrylryan/BabylonTerrain and github.com/felixpalmer/lod-terrain but both of these are limited to 2d measurements and because I am going to be doing this on a planetary level with Spherical displacement I need to go a step farther.
 

Also I am wondering how I should handle the frustum calculations because in theory nothing on the backside of the planet will need to be rendered but how do I establish the "zone" is hidden on the other side of the planet? 

[jerome]

http://www.babylonjs-playground.com/#FJNR5#148

 

https://github.com/BabylonJS/Extensions/blob/master/DynamicTerrain/documentation/dynamicTerrainDocumentation.md

https://github.com/BabylonJS/Extensions/tree/master/DynamicTerrain

[Pryme8]

@jerome I can see the use in the technique you just posted, but it is still not what I am looking for.  Ill keep reading and see if there are some answers to my questions with your solution though!

If you take a peep at the pdf I linked in the top post, you will see why I say its not quite what I am looking for.


also I am looking to do it with planes projected into a sphere, and with multiple ones of them on the screen at any given time. see http://www.babylonjs-playground.com/#DPSB16#9 for the example of the way the mesh will be set up.

[Pryme8]

I have my t-junctions made... now I gotta figure out how to implement them in a spherical projection...  I wish I had more then part time to focus on this.
http://playground.babylonjs.com/#IJTGJ3#18

[Pryme8]

http://playground.babylonjs.com/#TJBTN2#1

So now I have my new terrain mesh, I have to incorporate the t-junctions now from the prior playgrounds for when it has neighbors at a lower LOD.
This was a big step I needed to get done because http://playground.babylonjs.com/#IJTGJ3#18 would not be workable in the manor that I wanted due to the fact there would be way to many draw calls if I created the number of "tPlanes" I would need to cover a quadrant.

Next step is the blending outer sections then create a new container object for quadrants of a 'zone'.  These zones will then get a container for the planetary level and I should be well on my way to CDLOD Planets.  With my Das_Noise Lib things will get serous really quick with this I think.

Anyways the question is: 
After looking at the math to create the indices what would be the best method to create the outer edges with the correct t-junctions,  Im guessing just some logic for if the row/col is at the first one or the last and then skip the extra point in the middle of the junctions by skipping even iterations.  The indices calculations are what I'm worried about, anyone have any bright ideas?

Maybe keep the points, but "ignore" the indices I don't need when making the step down junctions?

[Pryme8]

I am stumped...  I need to test a list of meshs for distance before each drawframe for their distance to camera, and if they are with in a certain range create a new set of meshes and then test their distance so on and so forth before each frame is rendered. 

http://playground.babylonjs.com/#TJBTN2#6
 

I guess I do not understand quad-tree equations, or how to recursively go through the steps of the LOD and keep testing their distances without impacting performance.

[JohnK]

This topic piqued my interest. I would have replied earlier but I wanted something to offer before answering and it has taken a few days to come up with something worthwhile. Well IMHO it is worthwhile, for me at least whether it is for you I will have to wait and see.

Hope you don't mind some suggestions even if they are a little tangential.

Two quotes from the CDLOD paper struck me (my bold and italics)

Quote

it is structured around a quadtree of regular grids, . . . which provides it with better level-of-detail distribution. . . .the same amount of on-screen triangle complexity.

Neither the sphere nor the mapping of a ground mesh onto the sphere meets these criteria.

    

However I noticed that you were using an icosphere (for the core) and though not totally meeting the criteria is does so much more closely than the other two methods.

Also the equilateral triangles could form the nodes for the CDLOD quadtree system.

So I decided to pursue the idea of using an icosphere but leave the CDLOD part for later after I saw what happened with just the icosphere.

The next step was to cause a perturbance using a heighmap. Now I remembered that  fur material not in high level mode allows the use of heightmaps. Giving this a try I found that it caused gapping on the icosphere along some edges.

             

flat = false                                                                                                  flat = true                                                                        flat = false and an updated version of CreateIcoSphere

This is because, even when flat = false, each triangular facet in the icosphere has its own three vertices and so at the borders of the heightmap if pixel colors are not identical vertices appearing to share a position have their positions out even by a small factor can be moved differently. The  flat option, with default true for the icosphere  only changes the the normals of the facet vertices and does not make the mesh smooth by sharing vertices.

Another benefit of facets sharing vertices is that there is a reduction in the number of vertices by a factor of just over 5.

The next step was to update the CreateIcoSphere function to remove repeated vertices when flat = false and as you can see in the third image there is some seaming but no gapping.

Having done this update I cannot use the PG to show the results as I modified babylon.max.js (for those who are interested this is not the final v3.0 but one I downloaded during its beta stage).

So I uploaded to github to give these examples.

example 1

example 2

example 3

The main differences are the type of image used for heightmap and texture. Call the one below an isomap. This comes directly from the work of G'Kar in this post.

example 1 matching rectangular image and rectangular heightmap

example 2 rectangular heightmap and isomap image

example 3 matching image and heightmap from isomap.

This is about as far as I have got in development. Have to go out now but will add a few more of my thoughts later.

 

[JohnK]

14 hours ago, Pryme8 said:

I guess I do not understand quad-tree equations, or how to recursively go through the steps of the LOD and keep testing their distances without impacting performance.

Neither do I but I am not sure it is necessary for spheres. During the next paragraph I do not really know what I am talking about but other might be able to correct any misunderstanding.

In the CDLOD paper they are talking about a giant terrain only some of which gets rendered at any time. From their tables the most triangles rendered at any one time is 446K, so their CDLOD methods brings the triangles needed for the whole terrain down to 446K that have to be rendered each frame. SO 446K is an acceptable number of triangles. Setting the number of subdivisions to 128 for the icosphere gives 330K triangles and it seems pretty smooth to me. Setting the subdivisions to 256 which is probably way over the top gives 1310K triangles and takes a few seconds to load it renders frame by frame well. IMHO because you are working with spheres not planes then you can get away with not using LOD.

If you have a number of planets then have two or three different versions for each planet with number of subdivisions depending how far away you are, enabling each as appropriate.

 

What I haven't worked out yet is how you make an isomap of an area. Will look into that next.

Good luck with you project.

[Pryme8]

When I get home Ill take a look at your demos, they seem to not be working for me at work >_<.

[Pryme8]

Anyone have a better equation then this to figure out when to up the meshes LOD?  Im using something like:

var _d = Math.pow(minDistance, maxLOD - meshesLODLevel);

if(_d > cameraDistance2Center){//split}else{//skip}

but the numbers get really high really fast and are not what I want.
http://playground.babylonjs.com/#TJBTN2#10

@JohnK I like the idea of doing it as a Icosphere as well, but will prolly go with the normalized cube.  This is so I can identify neighbors and make sure that I know when to use t-junctions for LOD changes.  If you can figure out how to do it with an icosphere (which you might have already in your demos ill look when I can) then I will for sure just use that ^_^.


*UPDATE*

changed it to this: var _d = this.minDist*Math.pow(2 , this.maxLOD - zone.level); and I like it
http://playground.babylonjs.com/#TJBTN2#13

now I need to make it handle more then one level shift...
if you move closer to the plane you will see it up its detail/split once.


*UPDATE 2*

http://playground.babylonjs.com/#TJBTN2#15
now to handle zooming out!

[Pryme8]

hopefully I figure out a good way to decide when to merge the meshes, and if I should dispose the larger LOD's from memory or not.

 

I think I am going to have each zone have a prototype function to check if all of its children are out of range of the LOD layer, and if so re-enable the parent, and dispose all its children.

http://playground.babylonjs.com/#TJBTN2#22

I am having trouble with this... uhg In my mind this should work.

[Pryme8]

*UPDATE*

 

MUAHAHAHA I have done it!     var newLOD = this.level+1; was the problem line... I had     var newLOD = this.level+=1; which broke all the calculations.
http://playground.babylonjs.com/#TJBTN2#23
 

Still a little glitchy, on the merging but I should be able to make this a working model now, it looks like it may be only able to go back one level of LOD at this time.  But given the limited focus I have gotten to put on this its a start!

*UPDATE*
Fixed http://playground.babylonjs.com/#TJBTN2#24

Now to do a Spherical Projection, and then implement my 3d Noise library to establish height maps.

[Pryme8]

http://playground.babylonjs.com/#TJBTN2#31

Terrain LOD yes Please  
@JohnK, @Wingnut <- You two should like this.  Ill be doing the planetary version here sometime once I have a chance to sit and focus.

You may have to refresh or hit run again till Das_Noise loads.

 

*EDIT* Also I changed the title of this thread to match the method that I decided to go with for the LOD.  I did not really understand CDLOD was moving the terrain not the camera, and that method does not work for what my final goal is. for a CDLOD solution @jerome above examples would work better.

[jerome]

your algo is pretty nice and the terrain really looks nice when flying upon with the camera.

My approach is different (and is my own from my experience about the BJS vertex buffer size variation regarding the GC behavior, no such a sophisticated algo like yours) : to keep a constant number of vertices for the terrain mesh and to adjust its shape to the map obvisouly but also to the current camera distance to simulate a LOD behavior.

Like you understand it, the terrain mesh moves with the camera (it was the real challenge to perform) because it's size fixed so not that big in the World, anyway it's far tinier than the map it adjusts to.

I used a ribbon because I'm lazy and because it's the simpler BJS provided mesh type to easily morph a map. I could have used a dedicated better designed basic terrain mesh looking like yours (maybe I'll do it some time).

[Pryme8]

@jerome
do you think I should displace the terrain prior to projecting it to a sphere, or apply the projection then displace the point by finding the vector angle of the point to the center of the planet and scaling it that way?

Im just mulling over my options and what would be the best solution for the displacement on a planetary scale.

[Pryme8]

http://playground.babylonjs.com/#TJBTN2#33

Ohh boy, things just got complicated!  I gotta figure out how to get this to split down in the correct way now that its a sphere.  I think I will hold off on the projection into a sphere until each quadtree leaf propagates into the correct area!

Its getting close though...

 

I need some help with my math:
so for each polar face I have a normal vector so like for the "front" one it would be 

new BABYLON.Vector3(Math.PI*-0.5,0,0)

which rotates the plane in the direction I need, but now I need to figure out how to include this in the placement of the LOD level up from the initial.  I do not want to have to do any sort of logic loops to establish which direction the plane needs to move I ws hoping for some sort of tricky math.

Like if my normal vector is the above one, convert it to 
var faceNorm = new BABYLON.Vector3(-1,0,0) and then apply that to the positioning calculation of

this.children[0].mesh.position = this.mesh.position.clone().add(new BABYLON.Vector3(-this.children[0]._size*0.5,0,this.children[0]._size*0.5));

and have it be something like

this.children[0].mesh.position = this.mesh.position.clone().add(
(new BABYLON.Vector3(-this.children[0]._size*0.5,0,this.children[0]._size*0.5)).cross(faceNorm)
);

Not sure if I was just speaking jibberish or if anyone gets what Im talking about.

Also Im going to have to come up with a new calculation for projecting the quadleaves into a sphere correctly, but ill do that after I get their positioning correct.



*UPDATE*

I found a work around: http://playground.babylonjs.com/#TJBTN2#35
now I need to figure out why my distance calculation is not working, it should not split the back and front poles that I have being displayed at the same time and in the same manor, so something is off on the position of the mesh or at least how I am referencing it.
Fuuu this is becoming a headache.

 

[Pryme8]

http://playground.babylonjs.com/#TJBTN2#36

Ok now I just need to figure out why all the meshes are returning the same position.

[jerome]

I think I would displace the terrain on the sphere directly (NOT displacing it first on a planar logic map and then projecting it)

[Pryme8]

Cool, now I have to figure out why the positions of the meshs are coming up as 0,0,0...

why would after I position the mesh/zones they have incorrect positions stored, but are appearing in the correct area?

Ahh it was line 76... so baking the vertices sets the mesh position to 0,0,0.
Is there a way to bake the vertices position, but keep the meshs position intact? <- @Deltakosh (if you have a moment)

 

[Pryme8]

http://playground.babylonjs.com/#TJBTN2#39

I am so close it hurts.... >_< I guess I need a new projection algorithm. 

***Edit***
Gotta make some fixes to the positioning and then this should work.


Ok now I am beating my head into a wall... everything works when its a cube, but the second I try to project into a sphere everything goes to shit...
Cube: http://playground.babylonjs.com/#TJBTN2#40
Sphere: http://playground.babylonjs.com/#TJBTN2#41

If change the displace method to not be wrapped in a timeout, I get even more odd behavior.
http://playground.babylonjs.com/#TJBTN2#42


About to give up on this >_< and go back to texture synthesis scripts... rabble rabble rabble...