Thanks for the video! I’d ask questions but graphics programming is scary. I know, I’ve tried it before and didn’t like it. 
Every now and again I get an urge to fiddle with procedural planet generation. I think I’m near a 3rd revision of my planet generation adventure, started with XNA and moved over to Unity. My last two week spell did produce some results, this is what it looks like atm.
(accidental double post above)
@cybercritic Nice! That looks very similar to the idea I had in mind for what ended up becoming the 2nd prototype (snow/mountains)… Namely, having sliders to tweak various parameters and play with the look of the terrain. I ended up getting derailed from that ambition, and focused the snowy prototype on 3D level-of-detail algorithms instead.
Specifically, I tried scanning (parallel sum) the terrain height data generated on the gpu, then sending that information to the CPU where it would create a spherical-coordinate-system-aligned-bounding-box. Next, test a number of camera-centered LOD spheres (one for each LOD desired) against those bounding boxes The transformation was significantly easier when you first transform the camera’s position into the bounding box’s position - not the other way around (lesson learned the hard way) - particularly buecause this allows you to make a very good AABB approximation of the spherical-aligned box (SCABB?). I am still undecided whether or not the end result is worth the the effort (programming-wise or computational-wise), though - it does help ‘edge’ cases where there’s a steep change in elevation within a patch, but testing against a patches’ average coordinate is a pretty close approximation to this. Either way, it was a good adventure in running compute algorithms on the GPU (something that has benefited other projects since then greatly…)
Anyhow, thanks for sharing! I really like your terrain coloring alg!
It was this, Indie Planet Generation, you can also click on the edit “pen” to see what was there.
The last revision on my prototype is using a compute shader for the height generation and the spherical mapping is working fine. I’m not sure what exactly you need those boxes for, haven’t even thought about needing them. Also I’m using the mid-point displacement algorithm for height generation, the theory being that you could generate a surface height map in a dedicated planet modelling program, at a specific LOD detail and then let the algorithm just continue generating lower level data from that point…
One thing that I can say about planet generation is that there are always problems to be solved and something new to be learned 
[quote=“cybercritic, post:18, topic:765”]
One thing that I can say about planet generation is that there are always problems to be solved and something new to be learned
[/quote] Amen!
So, I need the bounding boxes to determine how far away I am from a piece of terrain, in order to determine its LOD.
Initially, I tried to do this without requiring knowledge of the generated terrain’s height, other than inherently knowing the minimum and maximum height of terrain that could exist on the planet. So effectively, my LOD determination was 2D. Basically, here’s what’s going on (that’s link’s an interactive web app I made demonstrating the concept…I’d had the processing sketch already, but converting it to javascript for this post was trivial. Processing.js rocks…)
The problem here is that whenever the camera is within the [terrainMinHeight, terrainMaxHeight] range, you’re basically having to assume that it’s right at the surface for your LOD determinations. In other words, imagine your terrain can range from -10,000 to +10,000 units, and that the camera is somewhere between those two heights. Even though directly under the camera the terrain may be at height -4,000, and the camera at height +2,000, a huge distance away, the CPU has no way of knowing the distance is that large (because it doesn’t have terrain height data, which is all on the GPU). Thus it must select the finest level of detail.
So, I needed to send some height data from the GPU to the CPU (which I’d probably need to do anyway, unless all terrain collision detection is performed on the GPU). By giving the CPU the exact min and max height values of a terrain patch, it can compute a bounding box and allow us to perform a true 3D level-of-detail test. The actual bounding box test can be somewhat tricky, but the approximation I mentioned in the last post was to simply do a distance test to the patches’ bounding box’ 3D midpoint: Note, you still need its max and min height to determine this.
I hope that explanation is a bit better than the first. With the huge variety of techniques available for this kind of work (and no real “single-best techniques”, it’s easy to falsely assume everyone uses the same terminology when describing a concept.
How about just checking the distance of your camera position to some vertex, the middle one of your patch for instance and split according to that distance?
Seems a lot less intense than what you are doing with those bounding boxes…
Absolutely, and that’s the approximation I mention in the 2nd to last paragraph. But note, you still need to send height data from the GPU to the CPU to do this (a patches’ min and max height will suffice). Why? Because even if I have the ‘lateral’ midpoint of a patch (i.e. ‘latitude and logitude’), it’s ‘vertical’ midpoint could be anywhere from -10,000 to +10,000.
Your vertex contains the xyz position…
EDIT: I see what you’re saying - instead of calculating the min and max heights of the patch (to get an accurate bounding box), simply pick an arbitrary vertex within the patch - say the center vertex - and test against it’s height. That definintely works, although it is even more of an approximation - which only matters if there’s sufficiently high elevation change taking place within one single patch.
Keep in mind, all the vertex data is generated on the GPU, and the CPU (which is where the LOD calculations are taking place) has none of that information unless I explicitly send it there.
Navy, the little “pencil” is the edit button
I found myself wanting an accurate bounding box for a terrain patch for other reasons, anyway - i.e. more advanced occlusion culling (imagine you’re standing at the foot of a tall cliff).
But in this whole process, the single most expensive part is sending data from the GPU to the CPU - and the difference between sending just a single vec4 (i.e. one vertex’s coordinates), sending two floats (calculated patch min and max height), or sending all 128x128xvec4s is actually quite small as well (especially when batched across multiple patches).
Even the gpu scan to calculate the patch’s min and max is fairly cheap, when batched, and it’s only performed once (ever - I can store those values in a geo-indexed hashmap, which if completely filled for an earth-size planet with 1cm vertex resolution is still under 200mb (and kept either on disk or in host RAM, not the gpu’s)).
EDIT
[quote=“cybercritic, post:25, topic:765, full:true”]
Navy, the little “pencil” is the edit button
[/quote] Lol, yes, I know I know But you’re responding too quickly for me haha 
Continuing…
The bounding box calculations are actually pretty simple. Transform the camera’s position into the terrain patches’ “model coordinate system”, and run a box vs sphere test for each LOD… that’s it!
Point here is - without transfering some height info from GPU to CPU, you can’t do a good LOD test. Once you’ve decided to do that, there are many ways to skin the cat, three of which we discussed (in order from least to most ‘accurate’):
- Distance test against a single vertex in patch
- Distance test against patch’s bounding box’s ‘true center’
- Sphere vs Box test against patch’s bounding box
The horse is really dead by now.
Would you mind sharing how you did your horizon-based occlusion culling. I am creating my small little procedural planet engine myself (including floating origin, positioning based on double precision coordinate system, reference frame velocity (to push speeds above lightspeed), and procedural planets based on cubespheres and quadtree.
But I still suffer on a good working culling mechanism, currently focussing on horizon culling.
I’ve implemented the following algorithm into Unity3D, the engine that I am using, but still culling seems not work good and framerates get low when getting near the planet (~lvl 20 in the quadtree). I throw all four positions into the algorith to check if they are occluded. If all are occluded I merge until the parent is visible (or I reached the very parent node).
If one is not occluded, I check depending on the distance if I need to splitt.
So any hint about your algorithm and strategy would help a lot.
Images:
(I may not add them as new user, maybe with the next post?)
public bool HorizonCullingAlgorithm2(Vector3 cameraPosition, Vector3 testPosition, float radius) {
Vector3 planetCenter = new Vector3 (0, 0, 0); // As we check against a planet at (0,0,0) and the calculated cameraPosition which must be an offset position.
Vector3 planeCoordinate = testPosition;
int angleThreshhold = 10;
// 1a) Horizon Angle
// h = Distance camera to planet center / r = planet radius / t = horizon angle
// float h = VectorServiceProvider.Distance(center,cameraPosition); // Distance from camera to planet center
float h = Vector3.Distance(planetCenter,cameraPosition);
float r = (float)radius*0.5f;
//float r = (float)radius;
float t = (float)(Math.Acos(r / h) * (180.0f / Math.PI));
// 1b) Plane Angle
// Get the camera position and plane position in space
Vector3 C = cameraPosition;
Vector3 P1 = planeCoordinate;
// Normalize each vector
C = C.normalized;
P1 = P1.normalized;
// Calculate the angle between the two vectors
double PlaneAngle = ((float)Math.Acos(Vector3.Dot(C,P1)) * (180.0 / Math.PI));
// 1c) Compare Angles. If true the plane is within the horizon
if (PlaneAngle < t + angleThreshhold ) {
return false;
}
return true;
}
Why don’t you do this in the shader, you can use “clip” to kill the pixel, also you might be able to kill anything that is not looking at the camera, instead of going with the plane and distance calculations?
/edit
You are at level 20 in your quad-tree (420), wouldn’t that make your vertex to vertex resolution at sub-mm on Earth scale?
I precalulcate everything on the CPU (noise, vertices, index etc) and push it to the GPU (create the Unity3D Gamebject) as soon as the precalucation is done. I really want to get rid of the whole object including all the calculated data in the quadtree if I dont need it. Doing this by using the Horizon Culling approach seems like a good idea to me as you really discard a lot of stuff when you approach lower distances of the sphere.
Plus, I dont have enough experience in working with shaders, so I look for an approach to do this in my quadtree directly.
Hmm I was suprised by your hint of lvl 20 as I thought, whyever, this is far from being good for planets. Due to this is recaluclated it, and hmm yeah seems like I was heading too far trying to go downwards the quadtree?I think I am not at sub-mm, but really close to something ok. Entering the stuff in Excel, I guess I am at least at something like meter detail for the vertices and cm detail for the texture. Which indeed should be fine. So seems like I should stick with a maximum depth of level 20 for the tree and try to optimize the textures and noise from here on? Seems like it if I am not wrong. Thanks for the hint!
Earth Circumference(km): 40.000
Earth Circumference (m): 40.000.000
Planes for Circumference: 4 (due to cubesphere)
Vertices per plane: 32
Texture resolution: 128
Distance width of plane (m) (lvl 00): 10.000.000 m
Distance width of plane (m) (lvl 01): 5.000.000 m
Distance width of plane (m) (lvl 02): 2.500.000 m
Distance width of plane (m) (lvl 03): 1.250.000 m
Distance width of plane (m) (lvl 04): 625.000 m
Distance width of plane (m) (lvl 05): 312.500 m
Distance width of plane (m) (lvl 06): 156.250 m
Distance width of plane (m) (lvl 07): 78.125 m
Distance width of plane (m) (lvl 08): 39.063 m
Distance width of plane (m) (lvl 09): 19.531 m
Distance width of plane (m) (lvl 10): 9.766 m
Distance width of plane (m) (lvl 11): 4.883 m
Distance width of plane (m) (lvl 12): 2.441 m
Distance width of plane (m) (lvl 13): 1.221 m
Distance width of plane (m) (lvl 14): 610 m
Distance width of plane (m) (lvl 15): 305 m
Distance width of plane (m) (lvl 16): 153 m
Distance width of plane (m) (lvl 17): 76 m
Distance width of plane (m) (lvl 18): 38 m
Distance width of plane (m) (lvl 19): 19 m
Distance width of plane (m) (lvl 20): 10 m
Distance of vertices (m) (lvl 20): 10 m / 32 = ~30cm
Distance of texturepixel (m) (lvl 20): 10 m / 128 = ~7cm
Do show something please, a video would be wonderful. 
You can drive go-carts at that resolution…
I’ll share, gladly.
One of the keys to speeding things along is only performing the test when necessary. There are many ways to reduce the number of horizon occlusion checks you actually need to perform, such as only doing so once the camera has traveled a certain distance relative to the planet since the last check. Whenever an occlusion test is performed against a patch, I record the location of the camera relative to the planet (i.e. cameraPos - planetOrigin) at that moment. The next time I go to test against that patch, if the camera’s current position relative to the planet isn’t sufficiently far enough from its relative position the last time it was checked for that patch, I skip the test and simply reuse the last result. The ‘sufficiently far enough’ distance should be different for each LoD - I used a look-up-table with values that equated to approximately 10% of a patch’s diameter at each LoD, although this number is best determined through experimentation (keep a count of how many tests you skip per frame).
Another way to reduce the number of tests is to use frustum culling. I haven’t yet implemented it, but at some point intend to try out this approach: flipcode - Frustum Culling . However you do it, do it prior to the horizon test.
Next, I calculate the radius of the “visibility sphere”. The “visibility sphere” is centered on the camera. If the camera was in orbit around a perfectly smooth planet (spherical planet). the radius of the “visibility sphere” would be the distance from the camera to the furthest point on the planet’s horizon. Nothing is visible beyond this distance.
If the planet is NOT perfectly smooth, however, we have to extend that sphere. Image a very tall, steep mountain sitting just beyond the smooth planet’s visibility sphere - you should clearly see the mountain’s peak. So, when dealing with a featured terrain, we need to modify the calculation of the visibility sphere. I do this by taking into consideration the maximum possible height of the terrain. Please reference the following image for the derivation of that equation (this graphic is something I produced three years ago to help myself develop the equation, and then help me remember it three years later!):
(You may want to open it in a new tab and zoom in to see the red text)
With the radius of the “visibility sphere” having been determined, you could simply test each of the vertices of your terrain patch bounding boxes to see if their distance to the camera is greater or less than the radius of the visibility sphere. If any vertex is less than the radius, subdivide and re-test the children patches.
I am using a slightly more complex method, simply because case does exist where no bounding box vertex falls within the visibility sphere, but part of the patch does. (i.e. imagine a 2-D square at the origin, with vertices at (1,1), (-1,-1), etc. Now image a sphere of diameter 0.5 placed at (1.2, 0). The sphere clearly intersects the box, although none of the box’s vertices fall within the sphere).
To do so, I use an AABB (Axis-Aligned-Bonding-Box) - but not in the traditional sense. Normally an AABB is aligned to the world axis, regardless of the object’s orientation. This causes the dimensions of the AABB to change as the object (unless it’s a sphere) changes orientation. At certain orientations, the AABB is not a very tight representation of the object.
Instead, I use the model’s native coordinate system, so that the AABB matches the patch much more closesly. Here’s what I mean
:
(Hooray for Paint.net!)
Next, I transform the camera (and hence the visibility sphere) into the model’s coordinate system. Finally, I conduct a simple AABB - Sphere collision check between the visibility sphere and the patch’s AABB.
This process is integrated directly into my patch LoD determination: If the patch falls within the visibility sphere, I don’t immediately subdivide it and test it’s children. Instead, I check it against yet another camera-centered sphere: A “LoD Transition” sphere. That is: each level-of-detail has a certain ‘optimal distance’, which keeps the “vertices per pixel” in an appropriate range. I calculate this range band for each of my LoD based upon the monitor’s resolution, the camera’s field of view, and the number of vertices per patch. I don’t have the derivation of this equation written out, but it was fairly basic and made several worst-case assumptions (i.e. face-on angle to each patch, etc), in order to determine how close you could get to a patch before the number of pixels between each vertex in screen space exceeded a certain threshold.
So, with an LoD distance band look-up-table, I next check the patch against another camera-centered sphere with radius from this table based upon the patch’s LoD. If the sphere collides with the patch’s AABB, then the patch is too close to the camera for its current level of detail, and must be subdivided. If not, it’s at the appropriate LoD - add it to the drawing queue!
Hope this was helpful. As always, I’d be happy to elaborate on anything that may have been confusing.
I also have a couple of proccessing.org prototypes demoing these concepts… let me see if i can dig them up and post them somehwere…