PDA

View Full Version : Procedural terrain generation



shamus88
04-24-2009, 12:53 AM
Hi all!

I am currently trying out some techniques for procedural terrain generation and have recently started using OpenGL. I am now trying out the examples from the book "More OpenGL Game Programming" by Dave Astle.

I find his examples very interesting and informative indeed. However, I am currently kind of stuck in one particular example. In this example, he used VBOs to render the terrain. I want to modify this so that the terrain "morphs" into the new one rather then just popping straight to the new terrain after generating the heightmap.

However, I am finding difficulties in this area. I have changed the access patterns and also looked at some different interpolation techniques but I can't seem to get it to smoothly transition.

I am wondering if someone who have experience in this will be kind enough to give me some pointers on this matter?

I am particularly interested in this example because I am keen to implement VBOs for my terrain generation.
Pasted below is the code for his VBO class that also has frustrum culling. I have tried to add member function to the heightmap class to linearly interpolate 2 sets of values before passing it here but still that doesn't seem right. Any help would be very much appreciated. Thanks!


#include "CTerrainVBOCull.h"
// heights is accessed through calling the member function getHeightData() of the Height class
void init(heightData ***heights)
{
// Keep a copy of the heightmap data for ourselves.
data = *heights;
// Check to make sure we can use vertex buffer objects.
if (!GLEE_ARB_vertex_buffer_object)
MessageBox(0, "Your version of OpenGL does not support buffer objects", "Error", MB_OK);
// Build the buffer objects.
buildBufferObjectVertexArrays();
}
void CTerrainVBOCull::buildBufferObjectVertexArrays(voi d)
{
glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_NORMAL_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);
glClientActiveTextureARB(GL_TEXTURE0_ARB);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glClientActiveTextureARB(GL_TEXTURE1_ARB);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glClientActiveTextureARB(GL_TEXTURE2_ARB);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);
// Create vertex list.
if (bufferVertList > 0)
glDeleteBuffers(1, &bufferVertList);
glGenBuffers(1, &bufferVertList);
// 'allocate' memory for the vertex list.
glBindBuffer(GL_ARRAY_BUFFER_ARB, bufferVertList);
//glBufferData(GL_ARRAY_BUFFER_ARB, sizeof(GLfloat) * Height * Width * 8 + (sizeof(GLbyte) * Height * Width * 4), NULL, GL_STATIC_DRAW_ARB);
glBufferData(GL_ARRAY_BUFFER_ARB, sizeof(GLfloat) * Height * Width * 8 + (sizeof(GLbyte) * Height * Width * 4), NULL, GL_STREAM_DRAW_ARB);
// Calculate the offset in the array for the vertex, normal, and colors.
vertOffset = 0;
normalOffset = Height*Width*3;
textureCoordOffset = Height*Width*6;
colorOffset = Height*Width*8;
// Copy data into the buffer objects.
GLfloat *vertBuff = (GLfloat *)glMapBuffer(GL_ARRAY_BUFFER_ARB, GL_WRITE_ONLY_ARB);
int currentIndex = 0;
for (int z = 0; z < Height; z++)
{
for (int x = 0; x < Width; x++)
{
// Verticies.
vertBuff[vertOffset] = (float)x;
vertBuff[vertOffset+1] = data[x][z].y;
vertBuff[vertOffset+2] = (float)z;
vertOffset += 3;
// Normals.
vertBuff[normalOffset] = data[x][z].normal.x;
vertBuff[normalOffset+1] = data[x][z].normal.y;
vertBuff[normalOffset+2] = data[x][z].normal.z;
normalOffset += 3;
// Texture Coordinates.
vertBuff[textureCoordOffset] = data[x][z].u;
vertBuff[textureCoordOffset+1] = data[x][z].v;
textureCoordOffset += 2;
// Colors
GLubyte *byteBuff = (GLubyte *)&amp;vertBuff[colorOffset];
byteBuff[0] = data[x][z].color.r;
byteBuff[1] = data[x][z].color.g;
byteBuff[2] = data[x][z].color.b;
byteBuff[3] = data[x][z].color.a;
colorOffset += 1;
}
}
glUnmapBuffer(GL_ARRAY_BUFFER_ARB);
// Recalculate the offset in the array for the vertex, normal, and colors.
vertOffset = 0;
normalOffset = Height*Width*3;
textureCoordOffset = Height*Width*6;
colorOffset = Height*Width*8;
// Calculate the triangle index lists for each chunk.
for (int chunkZ = 0; chunkZ < Height/(ChunkHeight-1); chunkZ++)
{
for (int chunkX = 0; chunkX < Width/(ChunkWidth-1); chunkX++)
{
// Create the index buffer.
if (chunkArray[chunkX][chunkZ].bufferTriList > 0)
glDeleteBuffers(1, &amp;chunkArray[chunkX][chunkZ].bufferTriList);
glGenBuffers(1, &amp;chunkArray[chunkX][chunkZ].bufferTriList);

// 'allocate' memory for the buffer.
numElements = ((ChunkHeight-1) * (ChunkWidth*2+2))-2;
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, chunkArray[chunkX][chunkZ].bufferTriList);
//glBufferData(GL_ELEMENT_ARRAY_BUFFER_ARB, sizeof(GLuint) * numElements, NULL, GL_STATIC_DRAW_ARB);
glBufferData(GL_ELEMENT_ARRAY_BUFFER_ARB, sizeof(GLuint) * numElements, NULL, GL_STREAM_DRAW_ARB);


// Fill triangle buffer.
GLuint *triBuff = (GLuint *)glMapBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, GL_WRITE_ONLY_ARB);
currentIndex = 0;

// Calculate the extents of the chunk.
int startx = chunkX * (ChunkWidth-1);
int startz = chunkZ * (ChunkHeight-1);
int endx = startx + ChunkWidth;
int endz = startz + ChunkHeight;

// Initialize the min and max values based on the first vertex.
float maxX, maxY, maxZ;
float minX, minY, minZ;

maxX = startx;
minX = startx;
maxY = data[startx][startz].y;
minY = data[startx][startz].y;
maxZ = startz;
minZ = startz;

// Loop through the chunk extents and create the list.
for (int z = startz; z < endz-1; z++)
{
for (int x = startx; x < endx; x++)
{
// Update the min and max values.
maxX = maxX > x ? maxX : x;
minX = minX < x ? minX : x;
maxY = maxY > data[x][z].y ? maxY : data[x][z].y;
minY = minY < data[x][z].y ? minY : data[x][z].y;
maxZ = maxZ > z ? maxZ : z;
minZ = minZ < z ? minZ : z;

// Used for degenerate triangles.
if (x == startx &amp;&amp; z != startz)
triBuff[currentIndex++] = x + (z * Width);

triBuff[currentIndex++] = x + (z * Width);
triBuff[currentIndex++] = x + ((z+1) * Width);

// Used for degenerate triangles.
if (x == endx-1 &amp;&amp; z != endz-2)
triBuff[currentIndex++] = x + ((z+1) * Width);
}
}
glUnmapBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB);

// Assign the min and max values found.
chunkArray[chunkX][chunkZ].maxX = maxX;
chunkArray[chunkX][chunkZ].maxY = maxY;
chunkArray[chunkX][chunkZ].maxZ = maxZ;
chunkArray[chunkX][chunkZ].minX = minX;
chunkArray[chunkX][chunkZ].minY = minY;
chunkArray[chunkX][chunkZ].minZ = minZ;

}
}
}
void CTerrainVBOCull::draw(bool boundingBox)
{
// Make sure the frustum is updated to the current camera position.
glPushMatrix();
frustum.calculateFrustum();
glPopMatrix();
// Set up the vertex list.
glBindBuffer(GL_ARRAY_BUFFER_ARB, bufferVertList);
glVertexPointer(3, GL_FLOAT, 0, (float *)NULL + vertOffset);
glNormalPointer(GL_FLOAT, 0, (float *)NULL + normalOffset);
glColorPointer(4, GL_UNSIGNED_BYTE, 0, (float *)NULL + colorOffset);
glClientActiveTextureARB(GL_TEXTURE0_ARB);
// glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glTexCoordPointer(2, GL_FLOAT, 0, (float *)NULL + textureCoordOffset);
glClientActiveTextureARB(GL_TEXTURE1_ARB);
// glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glTexCoordPointer(2, GL_FLOAT, 0, (float *)NULL + textureCoordOffset);
glClientActiveTextureARB(GL_TEXTURE2_ARB);
// glEnableClientState(GL_TEXTURE_COORD_ARRAY);
glTexCoordPointer(2, GL_FLOAT, 0, (float *)NULL + textureCoordOffset);
// Loop through the chunks.
for (int z = 0; z < Height / (ChunkHeight-1); z++)
{
for (int x = 0; x < Width / (ChunkWidth -1); x++)
{
float maxX = chunkArray[x][z].maxX;
float maxY = chunkArray[x][z].maxY;
float maxZ = chunkArray[x][z].maxZ;
float minX = chunkArray[x][z].minX;
float minY = chunkArray[x][z].minY;
float minZ = chunkArray[x][z].minZ;
// Check to see if the corners of the chunk are within the frustum.
if (!frustum.pointInFrustum(maxX, maxY, maxZ) &amp;&amp;
!frustum.pointInFrustum(minX, maxY, minZ) &amp;&amp;
!frustum.pointInFrustum(minX, maxY, maxZ) &amp;&amp;
!frustum.pointInFrustum(maxX, maxY, minZ) &amp;&amp;
!frustum.pointInFrustum(maxX, minY, maxZ) &amp;&amp;
!frustum.pointInFrustum(minX, minY, minZ) &amp;&amp;
!frustum.pointInFrustum(minX, minY, maxZ) &amp;&amp;
!frustum.pointInFrustum(maxX, minY, minZ))
continue;
// bind the buffer and draw the chunk.
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, chunkArray[x][z].bufferTriList);
glDrawElements(GL_TRIANGLE_STRIP, numElements, GL_UNSIGNED_INT, 0);
// Draw the bounding box.
if (boundingBox)
{
glColor3f(1.0f, 0.0f, 0.0f);
glBegin(GL_LINES);
glVertex3f(maxX, maxY, maxZ);
glVertex3f(minX, maxY, maxZ);
glVertex3f(minX, maxY, maxZ);
glVertex3f(minX, maxY, minZ);

glVertex3f(minX, maxY, minZ);
glVertex3f(maxX, maxY, minZ);
glVertex3f(maxX, maxY, minZ);
glVertex3f(maxX, maxY, maxZ);

glVertex3f(maxX, minY, maxZ);
glVertex3f(minX, minY, maxZ);
glVertex3f(minX, minY, maxZ);
glVertex3f(minX, minY, minZ);

glVertex3f(minX, minY, minZ);
glVertex3f(maxX, minY, minZ);
glVertex3f(maxX, minY, minZ);
glVertex3f(maxX, minY, maxZ);

glVertex3f(maxX, maxY, maxZ);
glVertex3f(maxX, minY, maxZ);
glVertex3f(maxX, maxY, minZ);
glVertex3f(maxX, minY, minZ);

glVertex3f(minX, maxY, minZ);
glVertex3f(minX, minY, minZ);
glVertex3f(minX, maxY, maxZ);
glVertex3f(minX, minY, maxZ);

glEnd();
}
}
}
}

Also included my linear interpolation function in the height class:

void CHeightClass::MorphInit(int type)
{
if(type == CHeightClass::Midpoint)
{
if(tempA == NULL) tempA = new float[Width*Height];
if(tempB == NULL) tempB = new float[Width*Height];
createHeightmapMidpoint();
for(int ix=0; ix<Width; ix++)
for(int iy=0; iy<Height; iy++)
tempA[ix*Height+iy] = columns[ix][iy].y;
createHeightmapMidpoint(rand_seed);
for(int ix=0; ix<Width; ix++)
for(int iy=0; iy<Height; iy++)
tempB[ix*Height+iy] = columns[ix][iy].y;
}
}

void CHeightClass::MorphRun()
{
float mu = 0.5 ; //0-1
for(int ix=0; ix<Width; ix++)
for(int iy=0; iy<Height; iy++)
{
columns[ix][iy].y = tempA[ix*Height+iy]*(1-mu)+tempB[ix*Height+iy]*mu;
}
// Create normals.
createNormals();
}

shamus88
04-24-2009, 07:31 AM
I would also be very happy if someone could give some pointers on procedural terrain generation. I have attempted some basic online tutorial about how to load in RAW files and generate a terrain mesh from it.

I am wondering if someone could kindly show an example of a simple code that can generate the vertices for the mesh dynamically during runtime? Not many examples out there for me to refer to.

Dark Photon
04-24-2009, 08:27 PM
I would also be very happy if someone could give some pointers on procedural terrain generation. I have attempted some basic online tutorial about how to load in RAW files and generate a terrain mesh from it.

I am wondering if someone could kindly show an example of a simple code that can generate the vertices for the mesh dynamically during runtime? Not many examples out there for me to refer to.
Last I checked seems like there was a good amount of code out there, if you really want something like this. Google for continuous LOD, view-dependent LOD, geometry clipmaps, geomipmapping, etc. References for those will point you to other algorithms you can google for. Ben Disco's VTerrain (http://www.vterrain.org/Doc/clod.html) package has source for several algs in it (or used to), OpenSceneGraph (http://www.openscenegraph.org) and others have had some implementations out there, here's another (http://tulrich.com/geekstuff/chunklod.html), etc.

You're going to find you'll need to prune your search based on your needs. Do you need texture(s) mapped on top? Do you need fixed predictable bounded performance in how long it takes to "adjust" your terrain mesh to render each frame? Do you need point/lineal/areal feature cut-ins? Do you need certain features to "always" be at a given position/altitude? How big must your terrain be? How much data is that? Can you just fit it all on the GPU and be done with it, or do you have to run-time page it? Are you using this mesh for AI nav as well? Can you precompute anything? Do you really just want a precomputed TIN mesh with several LODs, or do you need something else, and why? That will help you establish which algorithm you do need.

All sorts of stuff (http://iqdev.blogspot.com/2008/11/gpu-terrain-rendering-in-opengl-part-1.html) out there. Just google for GPU terrain rendering. Even an article in the lastest ShaderX (7) about using the GPU tessellator coming out on cards later this year (for D3D11) and some existing ATI boards do do dynamic terrain, though there are ATI mentions in past SIGGRAPHs/GDCs well. Google March of the Froblins (http://developer.amd.com/documentation/videos/pages/froblins.aspx), play the videos, and read the papers. Lots of stuff, but I'll stop there.

brett01
04-24-2009, 10:11 PM
use openscenegraph you can directly load the mesh using it.See the application osgdem using this you can convert into .osg files and directly load the mesh.

shamus88
04-25-2009, 02:14 AM
Last I checked seems like there was a good amount of code out there, if you really want something like this. Google for continuous LOD, view-dependent LOD, geometry clipmaps, geomipmapping, etc. References for those will point you to other algorithms you can google for. Ben Disco's VTerrain (http://www.vterrain.org/Doc/clod.html) package has source for several algs in it (or used to), OpenSceneGraph (http://www.openscenegraph.org) and others have had some implementations out there, here's another (http://tulrich.com/geekstuff/chunklod.html), etc.
Hi!
Thanks for the reply. I did do some reading up and researh beforehand but I am a beginner and most of the papers or articles out there are aimed at a more intermediate audience. I have to admit that I am not very intelligent and hence why I am looking for a more beginner friendly help. I have managed to find the above source code, which I find interesting but still have some problems understanding it fully.



You're going to find you'll need to prune your search based on your needs. Do you need texture(s) mapped on top? Do you need fixed predictable bounded performance in how long it takes to "adjust" your terrain mesh to render each frame? Do you need point/lineal/areal feature cut-ins? Do you need certain features to "always" be at a given position/altitude? How big must your terrain be? How much data is that? Can you just fit it all on the GPU and be done with it, or do you have to run-time page it? Are you using this mesh for AI nav as well? Can you precompute anything? Do you really just want a precomputed TIN mesh with several LODs, or do you need something else, and why? That will help you establish which algorithm you do need.
Thanks again for the tips! I am sorry if I didnt make my point clearer in my post. I was pretty tired at the moment of posting. However, my requirements are pretty simple. I have been doing most of the basic OpenGL tutorials and are pretty happy about it. I can generate a simple terrain using Vertex Arrays. However, I am interested how using VBOs could affect the performance.

I have not much requirements at the moment. I will just need simple lighting (no shadowing), ability to generate a decent sized terrain (around 1024x1024 vertices) using common algorithms such as Midpoint Displacement, Fault Line, Perlin Noise or perhaps the combination of them.

The terrain should be multi-textured and also feature a simple body of water. A simple skybox also should be featured. (I have made this using Vertex Arrays. The updates I want will be the terrain and water generation. The terrain should be able to morph/interpolate from one mesh to another (mesh would be generated randomly from the techniques I mentioned) and the water rendered accordingly at the end.

Well, my problem is I know how to do bits here and there as I am just a beginner in OpenGL. I am trying to "combine" the techniques to produce the results I want/hope to achieve. I know its a bad practice but I seem to learn better by examples.


All sorts of stuff (http://iqdev.blogspot.com/2008/11/gpu-terrain-rendering-in-opengl-part-1.html) out there. Just google for GPU terrain rendering. Even an article in the lastest ShaderX (7) about using the GPU tessellator coming out on cards later this year (for D3D11) and some existing ATI boards do do dynamic terrain, though there are ATI mentions in past SIGGRAPHs/GDCs well. Google March of the Froblins (http://developer.amd.com/documentation/videos/pages/froblins.aspx), play the videos, and read the papers. Lots of stuff, but I'll stop there.


I have tried Googling a lot as well and have read a lot of interesting articles. I will also try the links you have posted (thanks again!). Hopefully I will find a solution to what I would like to achieve. It seems simple but then I guess my grasp of OpenGL (and perhaps the understanding of certain theories) is not good enough at the moment.

shamus88
04-25-2009, 02:18 AM
use openscenegraph you can directly load the mesh using it.See the application osgdem using this you can convert into .osg files and directly load the mesh.

Hi there!

Thanks for your reply. Those packages seems interesting but I would prefer to learn the process with just using OpenGL at the moment, as I have just started out and not very sure about things.

I won't be doing a very complex scene. I have described in my reply above the sort of results that I hope to achieve. There are a lot of theories out there but very few examples(in code) so I am still in the dark as to how to proceed.

shamus88
04-25-2009, 04:36 AM
Oh and can I also shamelessly ask a question about the code I pasted above?

Why is the rendering so slow? It takes a few seconds on my fairly decent system for the Faultline algorithm. I have tried to lower the size of the heightmap and also the number of iterations for the algorithms but it is still slow.

Also I noticed that it during the VBO generation, besides the pause it also switches buffer (or looks like it). I will get a brief screen flash before the new terrain is rendered on screen. This is because my skybox will briefly dissapear (buffer swap?) and the screen cleared to red briefly.

I did some reading up and I am guessing its because of glMapBuffer? Is there a way to speed up the process of the rendering (and avoid that quick buffer switch)?

Any helpful pointers or help would be very much appreciated! Thanks.

ZbuffeR
04-25-2009, 04:57 AM
Faultline touches each vertex for each iteration, so it is pretty slow. You should separate the heightfield generation from the visualisation.

shamus88
04-25-2009, 09:57 AM
Faultline touches each vertex for each iteration, so it is pretty slow. You should separate the heightfield generation from the visualisation.


Right, maybe this code is to complex for me at the moment. I noticed that it also has frustrum culling and also chunked arrays...

Too bad I can't find an example code that generates random terrain from various algorithms.

ZbuffeR
04-25-2009, 03:09 PM
This one is old (the .exe even links to opengl.dll instead of opengl32.dll) :
http://www.gameprogrammer.com/fractal.html

But it should provide you code and explanations.

Dark Photon
04-25-2009, 07:27 PM
I did some reading up and I am guessing its because of glMapBuffer? Is there a way to speed up the process of the rendering (and avoid that quick buffer switch)?

The usual technique is to call glBufferData with a NULL pointer just before calling glMapBuffer, for the case where you're going to change the whole contents of the buffer. OR, use the new glMapBufferRange and pass it the "invalidate buffer" bit. From a recent post:

glMapBufferRange(target, 0, size, GL_MAP_WRITE_BIT | GL_MAP_INVALIDATE_BUFFER_BIT)

which should avoid some stalls. Try it and see.

But honestly, I'd say while you're getting started and familiar with OpenGL, forget VBOs. Just use plain jane vertex arrays. They're pretty efficient. Once you get comfortable, you can toss VBOs in as an optimization.

Dark Photon
04-25-2009, 07:30 PM
Right, maybe this code is to complex for me at the moment. I noticed that it also has frustrum culling and also chunked arrays...
Unless your terrain mesh is very small, you're gonna want frustum culling for good performance.

Since you're new to OpenGL (3D APIs in general perhaps), I'd suggest just start with a small test terrain where you can play at interactive rates without culling, trying different algorithms and optimizations, comparing performance and getting comfortable. Then when you want to scale up to larger terrains, read up on frustum culling and scene graphs, and integrate that into your terrain rendering.