View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# OpenGL Procedural Planet Generation - Quadtrees and Geomipmapping

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

29 replies to this topic

### #1Vangoule  Members

Posted 28 January 2013 - 08:57 AM

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.

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:

Edited by Vangoule, 28 January 2013 - 10:42 AM.

### #2carangil  Members

Posted 28 January 2013 - 01:50 PM

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?

### #3carangil  Members

Posted 28 January 2013 - 01:53 PM

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.

### #4Vangoule  Members

Posted 28 January 2013 - 02:03 PM

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.

### #5Aressera  Members

Posted 28 January 2013 - 06:25 PM

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).

### #6carangil  Members

Posted 28 January 2013 - 06:34 PM

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'.

### #7Vangoule  Members

Posted 28 January 2013 - 06:44 PM

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 top priority: Implement Quad Tree. I can show source code of my project if necessary.

### #8carangil  Members

Posted 29 January 2013 - 03:32 AM

So currently my cube has thousands of vertices when i export it from
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

{
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
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
int adjacent_edge[4];       //inverse relationship from neighbor



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...
{

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);
}
}

}



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:

//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);

}

{

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] = ...

}

}

remove qa->parent->child[0]
remove qa->parent->child[1]
remove qa->parent->child[2]
remove qa->parent->child[3]

}



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

### #9Vangoule  Members

Posted 29 January 2013 - 03:57 AM

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.

Edited by Vangoule, 29 January 2013 - 11:42 AM.

### #10carangil  Members

Posted 29 January 2013 - 01:26 PM

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!

### #11Vangoule  Members

Posted 29 January 2013 - 01:33 PM

There is so much information about quad tree's. Everyone seems to do it differently. I'm currently experimenting in a separate project to try and get atleast one quad. I'll see how it goes. I'm not sure if i have enough information yet. I'll try get it working if not i'm hoping your code will save me from my problems. Thanks a lot for all the help.

### #12Vangoule  Members

Posted 30 January 2013 - 05:16 AM

Oh and as for Gaps. My noise function takes in a vec3 to calculate the height of a vertex. If a vertex is in the same place it will go to the same height. Therefore i should get no gaps. 'Hopefully' T-Junctions however will still exist. When creating the new patches - How are you 'linearly interpolating' them to scale them back up?

Edit: I assume i just average between two vertices. However, my vertices are in an std::vector<glm::vec3> so it's only 1 dimensional. So i'm trying to get my head round it atm. Though i'm still wondering how to position my patches. I'll upload some pictures when i'm finished. Currently not using indices so i have well over 20 buffers. (Bad FPS incoming) I'll sort that out when it works.

Edited by Vangoule, 30 January 2013 - 10:59 AM.

### #13Vangoule  Members

Posted 30 January 2013 - 01:22 PM

Ok, So basically i kinda got it working... Half way atleast. I make the quads i add my camera as an object and the first subdivide is fine. Howeevr, the next thing that i subdivide leaves a big hole. I'll try upload a pic in a sec.

### #14Vangoule  Members

Posted 30 January 2013 - 01:45 PM

Ok, So basically i kinda got it working... Half way atleast. I make the quads i add my camera as an object and the first subdivide is fine. However, the next thing that i subdivide leaves a big hole. It's probably due to positioning but i can't seem to find it. The source responsible for the terrain has been attached

#### Attached Files

Edited by Vangoule, 30 January 2013 - 01:49 PM.

### #15carangil  Members

Posted 31 January 2013 - 03:26 PM

I took a look at your source.  What does 'Object.cpp/hpp' represent?  Since you're storing the vertices inside the quadtree itself, I think you can drop Object completely.  There will be a point where you will want to place things on your quadtree grid (characters, portals into buildings or caves), but you should have your own 'entity' class defined somewhere else.

I notice when you create the child nodes, you are using a fixed offset like center.z+34.  Is it really fixed, shouldn't the next level down use half the offset and so forth?

I also notice you set the center values for the 4 children as only being (center.x, center.z)  +   (0,0), (34,0), (34,34) and (0,34).  Shouldn't some of them be '-'.   None of the children should be 0,0: The center of the child will not be the center of the current node.  Look at this:

-------------

|  ,  |  ,  |

|     |     |

|- - -* - - |

|  ,  |  ,  |

|     |     |

-------------

The * is the center of the current node, and the comma's are the center of the children nodes.

------,-----,

|     |     |

|     |     |

|- - -*,- - ,

|     |     |

|     |     |

-------------

I hope this helps!

Edited by DracoLacertae, 31 January 2013 - 03:30 PM.

### #16Vangoule  Members

Posted 31 January 2013 - 04:05 PM

The object class is just an object that can be added to the quadtree. In this case it's the camera. This just handles the subdividing depending on where it is. I could probably get rid of this when i switch to distance. As for the centers, I'm rendering using normal triangles and the rendering starts at the top left. So my 'centers' really ended up as corners. The problem is i don't know what numbers to be using in the positions. Through trial and error i got the NW quad to work properly but none of the others seem to.

### #17carangil  Members

Posted 31 January 2013 - 04:35 PM

What is the significance of the value 34 you're using?

### #18Vangoule  Members

Posted 31 January 2013 - 05:16 PM

The value was found by trial and error but it's the point at which the two planes overlayer eachother. Though the value came to be that number because of the scaling and things. I changed the order in which i scale and translate everything and now the value is 168 which is the equivelant of the 'right' value from 0. Here's the source code now. I'll try and upload the actual application aswell. However, i'm not sure if it'll run on your machine. This should allow you too see what's happening. The planes have different height values so you can tell them apart. Moving the camera on to a plane should subdivide it once. It can be downloaded here: http://www.mediafire.com/?lk4zn5lmga3h99c

#### Attached Files

Edited by Vangoule, 31 January 2013 - 05:27 PM.

### #19carangil  Members

Posted 01 February 2013 - 01:03 AM

Your zip is missing glew32.dll.  I tried using my local copy, but it crashed immediately; I think I might have a different version.  I'm downloading your source right now.

### #20Vangoule  Members

Posted 01 February 2013 - 02:51 AM

Hmm, Here's my version of glew. However, the program was compiled on Windows 8 and a lot of the DLL's are from Windows 8 so it may be that which is crashing it.