Recently, I've been looking into procedural generation in the form of a planet. After reading many many articles i managed to create my own 'planet' though some work still needs to be done for it to look like a planet and yes... The repetition of many was intended. Before i can really start making my planet generate nice terrain i will need to implement some form of LOD. After reading through pretty much all of the articles on LOD that are on http://vterrain.org/LOD/Implementations/ i believe it would be best to use a Quadtree due to how i create my planet.

So first off here is a picture of my planet:

That picture might be a bit big but you get the idea... So the planet has it's heights generated on the shader using perlin noise and so it can change in real time. However, it is clear that the scale is all wrong. I need an adaptive quad tree to achieve good looking terrain at space, atmosphere and ground levels. The only problem is... I don't know how to fill the quad tree with the data.

How is the vertex data stored in a quad tree and split? Splitting the quad tree is one thing but splitting the data is another.

My implementation is done like this article - http://acko.net/blog/making-worlds-1-of-spheres-and-cubes/
I create the sphere from a cube by normalizing it. So this brings me on to another problem: I'll need 6 quad trees to split my planet up. One for each face. How will i extract the planes to subdivide them from vertex data?

My last question is how do i actually fill the quadtree with the data. Most examples on the internet all use things such as Ogre/Irrlicht/D3D and i haven't seen any detail on how to do this in OpenGL. Some source code would be a great help. If you require any of my source code to answer just comment and i will attatch it. For example - How could i change this to hold vertex data - https://github.com/veeableful/Adaptive_Quadtree_Minimal Thanks in advance.

A video of the shader noise generation can be seen here:

">

I have also been working on/off on a planet generator. While I make no claims to the 'idealness' of my method, it does seem to work. You're on the right track for an adaptive quadtree, because that is what I'm using. I looked into a bunch of terrain algorithms, and (ignoring older, more dynamic algorithms like ROAM), I've seen two main strategies:

• Fixed number of patches, dynamic detail levels: You need a 'small' outdoor environment. The ground is divided into patches which can be preloaded into GL (or DX if you prefer). Each patch can be drawn at different detail levels. So, a given 'square' of ground might be drawn at 1x1 all the way to 32x32, or even 64x64 quads. This seems fine for environments where the draw distance will always be limited. If this is a game 'on foot' or a flying game with a low maximum altitude, this works fine. You can even 'scroll' over a larger world by loadeding in extra patches where you need them. The basic render loop for this just needs to decide which patches are visible (frustum cull) and then at what detail level. I started with this one, and it seems to work great until you get too far up from the planet surface.

• Fixed patch detail, dynamic number of patches: This is what I'm using because it makes more sense for planets, where the scale and total amount drawn can change a bit. I chose I fixed patch detail amount. Suppose its 32x32 quads. All patches are drawn at the fixed patch detail level. As detail is needed, patches are split into 4 children subpatches. Detail is taken away by recombining the 4 children back into their parent patch.

I use the same basic approach you are taking: I start with a cube of quads that I have squished into a sphere.

I do not understand this question:

How will i extract the planes to subdivide them from vertex data?

Are you squishing a cube into a sphere, and they trying to decide which quads in the sphere belong to which plane? I did it this way:

• I am using opengl , so I assume the coordinate system of positive Y is 'up', positive X is 'right' and positive Z sticks out of the monitor poking me in the eye.
• Decide the center of the planet is <0,0,0>. And that the planet will fit in a box from <-1,-1,-1> to <1,1,1>. That makes all the math easy. You can move the planet around and resize it later.
• Start with a working quadtree algorithm for a single plane, at Y=1. The plane should cover from <-1,1,-1> to < 1,1,1>. A nice square. No deformations yet, just draw a quadtree in wireframe. As you get closer and farther than the plane, it should split/recombine.
• After that is working, 'bend' the square around the top of the sphere. For each point, simply normalize it, so it is a distance of 1 from the center point of <0,0,0>. This will create the top 'lid' of the planet. You should have the top part of the ball.
• Displace the points on the top of the ball. Not in the 'y' direction, but in the 'up' direction relative to the inhabitants of the ball. You will find this direction is the same direction as the 'normal' of the ball, and since the radius of the ball is 1, and it is centered at <0,0,0>, the position of your point IS also the direction you need to displace in. Very convenient.
• You should have a working 'top' of a planet, where you can fly around and get more/less detail where you need it.
• Add in the other 5 planes.

That was the basic idea. Do you have any specific questions?

I'll also add a video of it mostly working. Notice there are seams where the detail levels between adjacent areas don't match. My next task (when I have time, that is) is to fill those in.

">

Thanks for the reply. The bit on the sorting out which vertices belong to which face helps a lot. My main problem though is actually storing data in a Quad Tree. Most information from articles simply say - Store it in a quadtree in patches size n*n. How would i adapt a Quad Tree that is created like this - https://github.com/veeableful/Adaptive_Quadtree_Minimal to be able to hold data? Some source code would be much appreciated.

For my planet generator (in the planning stages right now), I'm going to use an icosahedron for the basic spherical subdivision to get a set of equilateral triangles which will each represent flat-ish terrain cells. These cells can then be subdivided recursively into 4 smaller equilateral triangles, then extruded to lie on the surface of the sphere (or something else, depending on elevation). You could theoretically use a quad tree for the triangle subdivisions though the math for the spatial subdivision will be a little weird (because you're dealing with triangles and not rectangles).

I'm not sure how it's going to work out in practice, but it's another idea for you to think about.

For rendering a planet at a distance (i.e. you can see the whole thing), it's probably best to just build a big vertex buffer for the whole thing because that won't take more than a few tens of thousands of triangles to achieve pixel-perfect curvature, then only switch to LOD terrain when the view gets really close to the surface (within 10-20 miles for earth).

For rendering a planet at a distance (i.e. you can see the whole thing), it's probably best to just build a big vertex buffer for the whole thing because that won't take more than a few tens of thousands of triangles to achieve pixel-perfect curvature, then only switch to LOD terrain when the view gets really close to the surface (within 10-20 miles for earth).

I agree with this. Right now, each quadtree patch lives in its own VBO. I want to add two things 1. have neighboring patches share VBOs (for instance, the initial 6 patches used for the starting 'cube' planet could share one VBO) and 2. let 'root' level patches be drawn at different mipmap levels. This way, I could do this: 1) extreme distance: planet is a sprite 2) far away, planet is all in one VBO, drawn at different tesselations 3) when close up, start dividing into the quadtrees

Later tonight I'll post the structs I'm using. Yes, right, structs, I'm working in plain C because this is a hobby project. But you can adapt the info to these C++ classes easily.

Are you trying to generate the planet on the GPU or on the CPU? What I'm doing is creating the geometry on the CPU (because I need it for reasons other than rendering), and I send VBOs representing the geometry in each patch to the graphics card.

This is how I'm spliting patches right now:

Currently, I'm using random midpoint displacement. Suppose I have a patch I want to subdivide, and it's 33x33. I will create four patches, but the geometry has to be based on this parent patch. So, what I do is 'scale up' just I would do for an image. I take a 17x17 vertex region of the parent patch, and linearly interpolate it to a 33x33 patch. As I copy, the in-between vertices (vertices that exist in the child but not the parent) are given a displacement. You can see, there's a problem here. Suppose you have two neighboring patches sharing an edge. When I divide one patch, that edge will be expanded in detail by creating more points. Later, when I subdivide the other patch, the same edge will be expanded again, except different values will be created. This will create a mismatch gap between two neighboring patches even though they are both at the same detail level.

There are three ways to deal with this.

1. (the way I currently am now): each patch knows it's neighbors. (Not just which patch is it's neighbor, but which edge of that neighbor connects to it. Sure, on a flat plane like graph paper, each squares's 'right' edge lines up easy with the 'left' edge of another square. Cut up the graph paper and make various shapes out of it(like a cube), and you'll find that the 'left' edge of one square might meet the 'bottom' edge of it's neighbor. You need to match edge-to-edge, not just neighbor to neighbor.) When a patch divides, if it's neighbor already expanded out detail for an edge, the same points are copied into the new patch. This way, when both patches are at the same detail level, they match up perfectly.

2. The way to I want to do it: The random number generator will always generate the same displacement values for the same edges no matter which patch is doing it (Seed the RNG with quick hash of the edge points before generating the numbers that detail that edge.) If I can get this working, patch edge fix-up logic can go away.

3. The way a real game would deal with it: All the data is pre-stored on disk. When dividing a patch, stream in child patches from disc, the authoring tools already seamed everything up. Patches don't need to know their neighbors

The above does not address the gaps created with neighboring patches are at different detail levels. This is something I'm still working on. I will probably settle with 'skirts'.

Currently i've got my normalized cube on the CPU i then send this through a VBO to the shaders. Here i apply perlin noise functions to create my height. I then choose what texture to use based on height with a change value made with sin cos and tan to make sure it's not a straight line of height.

If i can just implement a Quad Tree i'll be able to continue to create my procedural planet. This is my main goal right now.

So currently my cube has thousands of vertices when i export it from blender and load it into my application. I'd like to cut this loading time a lot. If i just load a unit cube without any extra vertices and sub divide it using the Quad Tree the shader will work out the heights for each vertex. So any source code or description more than 'Put your data in a QuadTree as a patch' will be helpful. I've been looking at this subject for a week now and still haven't got any further. I guess each node will have a struct which holds a certain amount of triangles. When it overflows - 'The camera gets closer' the node will subdivide and it's 4 children will each generate it's own data which will equal the size of the parent node but be in more detail. This is how i imagine the quad tree working. As for rendering instead of using a VBO per leaf would it not be easier to have 1 VBO per planet. I believe there are ways to do this using sub data or something like this.

So top priority: Implement Quad Tree. I can show source code of my project if necessary.

So currently my cube has thousands of vertices when i export it from
blender and load it into my application. I'd like to cut this loading
time a lot.

Oh, now I know what you mean when you said that you were having trouble deciding which vertices go to which of the 6 planes. I think it would be a lot easier if instead you were to build the sphere inside the application, instead of loading a sphere made somewhere else. Before I show you how I build the sphere in-program, let me show you the struct I use first. I removed a few things specific to my app, so it's pretty basic:

#define EDGE_LEFT    0
#define EDGE_RIGHT   1
#define EDGE_TOP     2
#define EDGE_BOTTOM  3

typedef struct quadarray_s
{
	gx_vbuffer_t* vb;      //vertex buffer storing geometry for this patch
	vindex startindex;     //start and end draw index for this patch
	vindex endindex; 


	zint32 w;  		//2d array dimension.  w and h can both be 33 for example, for 33x33 patch
	zint32 h;

	struct quadarray_s* children[4];   //4 children patches to subdivide
	struct quadarray_s* parent;
	int self; 			   //which one of my parent's children am i?



	vec3 center;  //center of the quadarray
	float size;   //area metric       
	float dsize;  //displacement metric  

	//neighbors
	struct quadarray_s* adjacent[4];  //the 4 adjacent neighbors at the same detail level	
	int adjacent_edge[4];       //inverse relationship from neighbor

} quadarray_t ;

Probably the most confusing part is tracking neighbors, but you can probably ignore that at the moment. You can get started without it, there will just be cracks and seems between patches.

I create 6 quadarray patches, one for each face of the cube: (warning, messing C code!)

for (face = 0; face < 6; face++)  //6 sides of cube...
{

	//make quadarray

	qa = quadarray_mk(33,33);
	
	qa->size = .3;    //I set the 'size' of this patch to .3.  it's rather arbitray, I just declared this patch has area metric of .3
	qa->dsize = .01;   //I set the detail size of this patch to .1.  It's also arbitray, it just affects how 'big' the displacements are


	// a and b will visit each vertex in the quadarray.
	for (a=0;a < qa->w;a++)			//0 to 'width'
	{
		for (b=0;b<qa->h;b++)		//0 to 'height'
		{
			vec3* vv = quadarray_get_vertex(qa, a, b);

			//convert each of the integer vertex coordinates to float -1 to 1

			fa = ((a-qa->w/2)/  (float) (qa->w-1)) *2 ;
			fb  =  ((b-qa->h/2)/ (float) (qa->h-1)) *2 ;

			//now decide on a plane depending on what face we are on

			switch (face)
			{
				case 0: //top Y=1
					vec3set(*vv, fa, 1, fb);	
					break;

				case 1: //bottom Y=-1
					vec3set(*vv, -fa, -1, fb);
					break;


				case 2: //front Z=1
					vec3set(*vv, -fa, fb, 1);
					break;

				case 3:  //back Z=-1
					vec3set(*vv, fa, fb, -1);
					break;


				case 4:  //left  X=-1
					vec3set(*vv, -1, fb, -fa);
					break;

				case 5:  //right X=1
					vec3set(*vv, 1, fb, fa);
					break;

			}

			//normalize vv to unit length
			d = vec3dot(*vv,*vv);   
			d = sqrt(d);
			vec3scale(*vv, 1/d);		
		}
	}

	
	vector_add(active_quadarrays, qa);  /* Add to the vector of enabled quadarrays */
}

The above creates a perfect ball radius 1 centered around <0,0,0>. The quadarrays vector stores the current list of active quadarrays. 'Active' means current detail level.

The main algorithm I use is in the pseudocode here:

//once per render/update loop:

for qa = all quadarray_t* in active_quadarrays {


	//test for visibility and draw
	if (  qa is in camera frustum )
		draw (qa);


	if ( patch_too_small( qa, camera_position))
		split_patch(qa);

	if (patch_too_big(qa, camera_position))
		combine_patches(qa);

}


split_patch (quadarray_t* qa)
{
	remove qa from active_quadarrays

	if (!qa->children[0])
	{
		
		//patch has bot been split before, need to generate or load children

		qa->children[0] = ...
		qa->children[1] =...;
		qa->children[2] =...
		qa->children[3] = ...	


	}


	add qa->children[0] , children[1], children[2], and children[3] to active_quadarrays 
}

combine_patch (quadarray_t* qa) {

	//remove all siblings from active_quadarrays
	remove qa->parent->child[0]
	remove qa->parent->child[1]
	remove qa->parent->child[2]
	remove qa->parent->child[3]

	place qa->parent on active_quadarrays
}

I currently alpha-blend details in and out, so I am doing something more complicated than this. I have a 'fade in' and 'fade out' list. I hope to find some time to fix the cracks between detail levels and then cleanup the code. After that, I'll put it on github, and everyone can rip it apart and flame my archaic C style :)

Ahh that simplifies it a lot. By building it in the application it should theoretically subdivide infinitely. I'll read more later.

Edit: So after reading the code. I understand that making the cube in the application will be easier. However, the style of your quad tree looks different to most the stuff i've found online. Lets say i have these faces and have a quadtree/quadarray setup for them. When i split the face. It creates the 4 children. However, how do i actually split the face and not just the quadtree. I remove the current geometry and create 4 new patches the same W and H but at a different scale as it's children? How do i scale/move/generate these new vertices to be in the right place.

Ok, I see what you mean. When I get home tonight I can put up the function that creates subpatches. For now, lets separate geometry from topology. The topology is how vertices are connected. The topology of every single patch is the same. It is a rectangular array of 33x33 vertices, which have been pieced together in 32x32 quads. In GL , the index buffer defines topology because it says which points go together to make triangles. It doesn't matter that the patches have been scaled, rotated distorted, whatever, the topology is still just a grid like 'graph paper.' By setting a fixed patch size, we don't have to worry about different tesselation levels or anything like that.

Now to the geometry. To make things easy, each point in the patch is identified by two integer coordinates, 'a' and 'b', both varying from 0-32. You can think of it as a 33x33 pixel image. Except each 'pixel' contains float x,y,z coordinates instead of a color. Now what you want to do is three things:

a. Define the source regions. If I'm cutting a 33x33 pixel image up into quarters, each quarter will be 17x17. yes, the quarters will overlap their neighbors by 1 pixel. This is correct, since these 'pixels' in this map are actually points, and we want to share an edge of points with the other quarters so there are no gaps.

b. upscale each 17x17 region to a 33x33 map. This is easy. You can see if you go along a row 17 original source points, and average every two adjacent values you get 16 in-between values. 17+16 is 33 again. You have reused 17 points from the previous generation, and created 16 new points. You can do this for all 17 source rows. Now you have a 33x17 map. Going vertically, there are 16 in-between rows you can average, creating a final map of 33 in height. I recommend NOT trying to literally reuse the same points (as in same VBO) as the parent, but instead copy the positions into the child's VBO. 1 VBO per patch is reasonable to start with; maybe later adjacent quadtrees can share VBOs or something.

c. Displace. When averaging and creating in-between values, this is the place to add displacement.

I'll post that bit of code up tonight.

I haven't worked on this in a few weeks, but this thread is inspiring me to find the time to fix the cracks between different detail levels! Thanks!