Archive for the ‘ Algorithms ’ Category

OpenGL Color Interpolation


Using the GL_LINES mode, OpenGL will draw for us a line for every two vertices we specify.

glBegin (GL_LINES);

    glColor3f  (1, 0, 0);
    glVertex2f (x0, y0);
    glColor3f  (0, 0, 1);
    glVertex2f (x1, y1);

glEnd ();

Behind the scenes, OpenGL is using interpolation to draw the line. That is, given 2 points, OpenGL will determine the set of pixels that the line would cross through and then change their color based on the color of the line. Bresenham‘s algorithm is a famous algorithm for drawing lines, and it (or some extension of it) is probably the one used internally by OpenGL.

Using the basic linear equation we all learned in school (y = ax + b), we should be able to get to an algorithm that draws the points across the lines. We are drawing a line segment from vertex v0 (x0, y0) to vertex v1 (x1, y1). Let’s denote any point across the line as vertex v with coordinates (x, y). Given those three vertices, we can build the following 3 independent equations.

Now, we should try to create some relationship between those 3 independent equations and try to get rid of the unknowns a and b. Let’s first try to get rid of b.

Let’s try y – y0 and y1 – y0, we will get the following two independent equations.

Now, let’s try to create a relationship between those 2 independent equations and at the same time try to get rid of a.

We can now sample some values of x between x0 and x1 and get the value of y using the above equation. This is the basic idea behind drawing a line. In addition to drawing the line, OpenGL is also doing something else behind the scenes: Color Interpolation. If you run the above code sample in OpenGL, you’ll see the following line:

As points are moving from vertex v0 to vertex v1, their color is also transitioning from v0 color to v1 color. This is handled by the OpenGL Smooth shading model. OpenGL supports two shading models: Smooth and Flat. Flat shading means that no shading calculations are performed on the interior of the primitives. The color of the interiors is the color of the last vertex specified. You can set it by calling glShadeModel (GL_FLAT). Smooth shading is thedefault shading model in OpenGL and you can explicitly set it by calling glShadeModel (GL_SMOOTH).

Even though OpenGL automatically does color interpolation (in case of smooth shading), it would be interesting if we try to implement it and experiment a little bit with it.

To implement the linear interpolation of the points and their colors, we are going to use the below generic linear interpolation method, where u is any value we select from 0 to 1.

First, let’s define the point data structure.

//  Define the point data structure
typedef struct Point
{
    float x;                  //  x position of the point
    float y;                  //  y position of the point
    float z;                  //  z position of the point
    float r;                  //  red color component of the point
    float g;                  //  green color component of the point
    float b;                  //  blue color component of the point
    float a;                  //  alpha color component of the point
} Point;

Next we set the number N of how many points we want to sample on the line, and initialize the array that will hold the points.

//  represents the number of points the line consists of
#define N 250

//  Declare the array of points
Point linePoints[N];

Now, we generate the location and color components for the points on the line using the above linear interpolation formula.

//  Location and color interpolation
for (i = 0; i < N; i++)
{
    u = (float)i/(N - 1);

    linePoints[i].x = v0.x * (1.0 - u) + v1.x * u;
    linePoints[i].y = v0.y * (1.0 - u) + v1.y * u;
    linePoints[i].z = v0.z * (1.0 - u) + v1.z * u;
    linePoints[i].r = v0.r * (1.0 - u) + v1.r * u;
    linePoints[i].g = v0.g * (1.0 - u) + v1.g * u;
    linePoints[i].b = v0.b * (1.0 - u) + v1.b * u;
    linePoints[i].a = v0.a * (1.0 - u) + v1.a * u;
}

Finally, we draw this set of points.

glBegin (GL_POINTS);

for (i = 0; i < N; i++)
{
    glColor4f  (linePoints[i].r, linePoints[i].g, linePoints[i].b, linePoints[i].a);
    glVertex3f (linePoints[i].x, linePoints[i].y, linePoints[i].z);
}

glEnd ();

More implementation details are available in the full source code of this OpenGL app. You can use this app for experimenting with color interpolation and you might even notice how the OpenGL interpolation method is way faster than our simplistic implementation (if you have a machine with a relatively slow processor). If you have any issues compiling or running the app, check out this section for details about compiling and running an OpenGL app that uses the GLUT library.

C Round Function


It’s really weird that the C math library (math.h) doesn’t support the round function. It only includes the floor function which rounds down a float to an integer (can also be done by implicit or explicit casting) and the ceil function which rounds the value up.

For example,

int x;

x = floor(1.2);   //  x is set to 1
x = floor(1.8);   //  x is set to 1
x = (int)1.8;     //  x is set to 1 (Explicit Narrowing Conversion)
x = 1.8;          //  x is set to 1 (Implicit Narrowing Conversion)
x = ceil(1.2);    //  x is set to 2
x = ceil(1.8);    //  x is set to 2

The round function is supposed to round the float value to the nearest integer.

x = round(1.2);    //  x is set to 1
x = round(1.8);    //  x is set to 2

This can be done adding a 0.5 to the value and then truncating it.

x = (int)(1.2 + 0.5);  //  x is set to 1
x = (int)(1.8 + 0.5);  //  x is set to 2

We also have to take negative values into consideration by adding -0.5 and then truncating.

x = (int)(-1.2 - 0.5);  //  x is set to -1
x = (int)(-1.8 - 0.5);  //  x is set to -2

Thus, here is the resulting C function:

int round(double number)
{
    return (number >= 0) ? (int)(number + 0.5) : (int)(number - 0.5);
}

Note that you might want to use long rather than int to include support for larger numbers and avoid integer overflow.

That’s it, pretty much primitive, but fun!

Enjoy!
Ali B

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: