Introduction

This is the first algorithm I’ve implemented with the shaders (mostly the fragment shader), it’s quite simple and it gives good results.

The Algorithm

This algorithm is based on two phases, a generation phase and an erosion phase.

The first phase is based on the following steps:

• compute a random line that divides the map in two sides
• add an height value to the elements of one side and subtract this value to the elements of the other side

repeat this for some iterations (I get a good result with 500~1000 iterations).

After one iteration you get something like this:

The height value that is added or subtracted to the map has to decrease after every iteration, a way to do this is the following:

GLfloat max_inc = 0.1;
GLfloat min_inc = 0.0;
GLfloat diff_inc = max_inc - min_inc;

…

for(int i = 0; i < num_it; i++)
{
 …
 inc = max_inc - (diff_inc * i / num_it);
 …
}

When the first phase is completed you get something like this:

This image is the result of 500 iterations.

As you can see from the previous image, the generated terrain is not so realistic, in fact it’s easy to notice the lines that splits the map and the different zones of color.

To fix this problem it’s needed another phase, that represents the erosion, where the image is blurred.

My blur algorithm is based on a simple average of values along the X and Y axis of a fragment and it’s repeated for six iterations (this number gives me best results, but it can be changed as I want).

These are the results of the erosion phase:

The left image is the terrain generated after 500 iterations, and the right image is the result of 6 iterations of blur.

The left image is the terrain generated after 1000 iterations, and the right image is the result of 6 iterations of blur.

The implementation

At the moment the program uses one vertex and two fragment shaders for the two phases.

The code is not optimized and needs a bit of polishing and rearrangement so I think there’s a good space for improvements, for these reasons I’m not posting any data about execution times yet, they would not be totally true, but I can say that the current tests I’ve made are really promising.

Useful resources

• Terrain Tutorial: The Fault Algorithm
  

Introduction

This post explains how to set and initialize properly the GL graphic contest for a GPGPU project.

The following code uses some SDL functions, if you need to use some other library (like GLUT) look for the corresponding functions.

Basic settings

If we want to display the results of our computation we would set something like the clear color with glClearColor, enable the double buffer using SDL_GL_SetAttribute SDL function. Furthermore we have to enable 2D texturing with glEnable.

The complete code for those settings is:

SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);

glClearColor(0.0, 0.0, 0.0, 1.0);

glEnable(GL_TEXTURE_2D);

The coordinate system

Two very important settings of the graphic contest are the coordinate system of the screen and the projection mode.

For the computational phase an orthogonal view is required so to have an exact correspondence between the texture texels and the screen pixels (so to avoid any interpolation), the function used for this is glOrtho. Another important setting is the viewport that represents the screen area affected by drawing operations, in order to have the right results the viewport has to be set to the texture dimensions with glViewport.

A good thing is that you can totally customize the coordinate system using glOrtho, so I’m used to set a coordinate system like this:

0,0----------w,0
|              |
|              |
|              |
0,h-----------w,h

and use a texture that has the same dimensions of the screen, so to avoid any changes between the computational and visualization phases.

Of course you can use a texture that has dimensions different from the screen’s ones, but you have to manage the thing with glViewport.

The code I use to set the coordinate system is the following:

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0.0, w, h, 0.0, -1.0, 1.0);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

glViewport(0, 0, w, h);

Computation and visualization

If you want to use properly the shaders for computational purposes and then display the results of your computation (draw the texture you get), you have to keep in mind that the coordinate system of the texture is different from the screen one, in fact it’s this one:

0,1----------1,1
|              |
|              |
|              |
|              |
|              |
0,0-----------1,0

This involves that you have to use two different functions for the computation and the visualization.
Using the screen coordinate system described above, these are the two functions I use.

This function is used for the computation:

void ShaderDraw(GLfloat w, GLfloat h)
{
	glBegin(GL_QUADS);

	glTexCoord2f(0.0, 1.0);
	glVertex2f(0.0, 0.0);

	glTexCoord2f(1.0, 1.0);
	glVertex2f(w, 0);

	glTexCoord2f(1.0, 0.0);
	glVertex2f(w, h);

	glTexCoord2f(0.0, 0.0);
	glVertex2f(0.0, h);

	glEnd();
}

This function is used for the visualization of the texture on screen

void ScreenDraw(GLfloat w, GLfloat h)
{
	glBegin(GL_QUADS);

	glTexCoord2d(0.0, 0.0);
	glVertex2f(0.0, 0.0);

	glTexCoord2d(1.0, 0.0);
	glVertex2f(w, 0.0);

	glTexCoord2d(1.0, 1.0);
	glVertex2f(w, h);

	glTexCoord2d(0.0, 1.0);
	glVertex2f(0.0, h);

	glEnd();
}

These functions draw the texture on the whole screen, if you want to change this you have to modify properly the parameters of the glVertex call.

Example code

This is the complete code I use for my init function:

void GLInit(int w, int h)
{
	SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);

	glClearColor(1.0, 0.0, 1.0, 1.0);

	glEnable(GL_TEXTURE_2D);

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glOrtho(0.0, w, h, 0.0, -1.0, 1.0);

	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();

	glViewport(0, 0, w, h);
}

Introduction

In this post I’m going to discuss a common technique in GPGPU projects, this technique allows a shader to use two textures as input and output data so to be able to perform a computation based on more iterations.

The technique described in this post is based on Textures and the Frame Buffer Object, so I suggest you to read my two previous posts before to read this one.

The technique

The base concept of this technique is quite simple, all we need is a Frame Buffer Object and two textures linked to it.

The Ping-Pong technique is used for all the programs that need to store the result of a computation, so all the programs based on more iterations.

The first thing to do is to create a FBO and two textures (with same dimensions and internalFormat), then attach the two texturs to the FBO, after that it’s possible to use one texture as input, so read its values in the shader (vertex and fragment shaders can read one or more textures as a rule) and use the other one as output thanks to the glDrawBuffer function that sets the second texture as output buffer (so the fragments computed in the fragment shader will be wrote in the texture).

After the first iteration, it’s enough to swap the two textures so to use the computed values in the previous step as input for the next computation.

Some implementation details

The key element of this technique is the texture swapping, an easy way to do that is storing the Texture ids in a two elements array and access the array with two integer variables, for example read_tex and write_tex .

So to swap the textures all you have to do is swapping the values of these two variables.

Example code

This is the code used to init properly the FBO and the two textures:

int read_tex = 0;
int write_tex = 1;
GLuint tex[2];

glGenTextures(2, tex);
…
// create and init the FBO
GLuint fb;
glGenFramebuffersEXT(1, &fb);
glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, fb);
…
// create and init the the two textures - this is the code for the first one
glActiveTexture(GL_TEXTURE0);
glBindTexture(GL_TEXTURE_2D, tex[read_tex]);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, W, H, 0, GL_RGBA, GL_FLOAT, data);
…
// attach the textures to the FBO
GLenum att_point[] = {GL_COLOR_ATTACHMENT0_EXT, GL_COLOR_ATTACHMENT1_EXT};
glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, att_point[read_tex], GL_TEXTURE_2D, tex[read_tex], 0);
glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, att_point[write_tex], GL_TEXTURE_2D, tex[write_tex], 0);
…
// create, init and enable the shaders

now everything is ready for the computational loop:

for(int i = 0; i < num_it; i++)
{
	// set the second texture as output buffer for the shader
	glDrawBuffer(att_point[write_tex]);

	// attach the input texture to the first Texture Unit
	glActiveTexture(GL_TEXTURE0);
	glBindTexture(GL_TEXTURE_2D, tex[read_tex]);
	glUniform1i(tex0_loc, 0);

	// draw a square with the texture on it so to perform the computation
	ShaderDraw();

	// swap read and write indexes
	if(read_tex)
	{
		read_tex = 0;
		write_tex = 1;
	}
	else
	{
		read_tex = 1;
		write_tex = 0;
	}
}

Useful resources

• GPGPU::Basic Math Tutorial

Introduction

In order to perform computation with shaders you have to read and write data from/to textures, even if the former task is an usual operation for a shader, the latter requires some GL code, in fact you can’t directly write data to a texture with a shader, but just to the buffers provided to GL by the window system.

In this post I’m going to discuss how to render directly to textures, so how to use texture for computational purpose.

The Frame Buffer object

All we need to render directly to a texture is an extension called GL_EXT_framebuffer_object, this extensions allows us to draw to rendering destinations other than the buffers provided by GL.

The Frame buffer is an OpenGL object, so the first thing we need to do is to create an handle to it using the function glGenFramebuffersEXT, then we have to bind it to the current context with the function glBindFramebufferEXT.

After that we can attach one or more textures to the FBO using the function glFramebufferTexture2DEXT, each texture is so attached to a different attach point identified by the constants GL_COLOR_ATTACHMENT0_EXT, GL_COLOR_ATTACHMENT1_EXT, etc…

After we have set everything up, we can use the attached textures for reading data with the function glReadBuffer and for drawing data with the function glDrawBuffer.

Example code

this is an example code that shows how to set up a FBO, attach a texture to it and use this texture as target buffer for writing operations.

GLuint fb;
glGenFramebuffersEXT(1, &fb);
glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, fb);

… // create a texture with texture name tex

glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, GL_COLOR_ATTACHMENT0_EXT, GL_TEXTURE_2D, tex, 0);

glDrawBuffer(GL_COLOR_ATTACHMENT0_EXT);

It’s important to remember that you can attach to a single FBO just textures of the same type (GL_TEXTURE_2D) and with the same dimension, if you need to work with textures of different type and/or dimension you have to use two or more FBOs.

Useful resources

• NVIDIA GDC 2005 Presentations - The OpenGL Framebuffer Object Extension
• gamedev.net - OpenGL FrameBuffer Object 101
• gamedev.net - OpenGL FrameBuffer Object 201

Introduction

This is the first post about coding, here I’m going to discuss about how to store data for a GPGPU project.

The main way to read and write data with a shader is using Textures, a 2D texture can be viewed as 2D array of data in an usual programming language.

The main function

If you want use textures as an array of data, the most important function to understand is glTexImage2D. You can compare this function to the C function used to create memory blocks: malloc.

Here I don’t want to explain everything about glTexImage2D (you can study the reference and the Red Book for detailed explanations), but I want to discuss the 2 most important parameters for our purpose: internalFormat and format.

internalFormat determines the number of components for each texel (a single element of the texture) and how many bits are used for these elements. So, for example, passing GL_RGBA gives you a texture with 4 components (R, G, B, A) for each texel and usually 8 bits for each component (this depends by the current graphic contest), instead passing GL_LUMINANCE gives you a texture with 1 component (L) each textel.

format describes how the elements are stored in the image data passed to the function. So, for example, GL_RGBA means that the first 4 values represents the 4 components (R, G, B, A) of a pixel, instead GL_LUMINANCE means that each value correspond to a single element with a single component.

Storing data

Using different combination of internalFormat and format with the same image data gives us different textures, some examples here:

internalFormat = GL_RGBA / format = GL_RGBA -> image data and texture data are mapped in the same way, so you have something like this (this is just a conceptual representation)

data[] = {0.1, 0.2, 0.3, 1.0, 0.1, 0.2, 0.3, 1.0, …}

texture[] = {0.1, 0.2, 0.3, 1.0, 0.1, 0.2, 0.3, 1.0, …}

internalFormat = GL_RGBA / format = GL_LUMINANCE -> each element from image data is replicated in the RGB components of the texture, and 1.0 is attached to the A component, so you have something like this (this is just a conceptual representation)
data[] = {0.1, 0.2, 0.3, 1.0, 0.1, 0.2, 0.3, 1.0, …}

texture[] = {0.1, 0.1, 0.1, 1.0, 0.2, 0.2, 0.2, 1.0, …}

I suggest you read the glTexImage2D reference and to experiment different combination in order to get the result you need.

Some useful extensions

Now that you know how to store and arrange your data, it’s important to decide what type of data to use in our texture, as I said before, passing GL_RGBA gives you elements with 8-bits components, but what if we need more accuracy?

We can use the extension ARB_texture_float, this extension adds texture internal formats with 16- and 32-bit floating-point components.

All we have to do in order to use this extension is using one of the new internalFormat types, for example GL_RGBA32F_ARB if we need 4 float components of 32-bit each one or GL_LUMINANCE16F_ARB if we need a single component of 16-bit.

An alternative could be using the GL_NV_float_buffer or the GL_ATI_texture_float propietary extensions, bu they are hardware dependent and I can’t tell you if they give you some better performance (I’ll do some benchmark someday).

Example code

This is an example code used to create a texture for GPGPU computing:

GLint n = tex_size * tex_size * NUM_COMPONENTS_X_TEXEL;
GLfloat * data = (GLfloat *)malloc(n * sizeof(GLfloat));
…
glGenTextures(1, &tex);
glBindTexture(GL_TEXTURE_2D, tex);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA32F_ARB, tex_size, tex_size, 0, GL_RGBA, GL_FLOAT, data);

It’s important to notice that GL_NEAREST parameter for MIN and MAG filters is really important, in fact using GL_LINEAR or something else gives you inaccurate results.

Another important thing to understand is that GL_FLOAT is not related to the texture elements or components, but it just describes the type of the elements stored in the memory pointed by data.

If you want to read data stored in a texture and store them in an usual array, you can use this code:

GLfloat * results = (GLfloat *)malloc(n * sizeof(GLfloat));
glGetTexImage(GL_TEXTURE_2D, 0, GL_RGBA, GL_FLOAT, results);