A Short Course in Computer Graphics. How to Write a Simple OpenGL. Article 2 of 6

Hi, everyone. It’s me.

It’s a model of my head rendered in the program we will create in the next hour or two.

Last time we drew the wire mesh of a three-dimensional model. This time, we will fill polygons, or rather triangles, as OpenGL triangles almost any polygon, so there's no need to consider a complex case. Reminding you, that this series of articles is designed for your own programming. The time that I provide here is not for reading my code. It’s time for writing your code from scratch. My code is provided here just to compare your (working) code with mine. Any comments and questions are welcome.

If you’re following this tutorial and writing your own code, upload it to github.com/code.google.com and other similar websites and provide links in comments. This can help you (other people will give advice), as well as other readers.

Drawing a Filled Triangle

Thus, the task is to draw two-dimensional triangles. It will take two hours for students that are not really good at programming, but are motivated. Last time we reviewed Bresenham’s line algorithm for the rasterization of a line segment. Today’s task is to draw a filled triangle. Funny enough, but this task is not trivial. I don’t know why, but I know that it’s true. Most of my students spend much more than a couple of hours, solving this task without prompting. Let’s define the method, and then get down to programming:

First of all, take a look at the following pseudo-code:

triangle(vec2 points[3]) {
    vec2 bbox[2] = find_bounding_box(points);
    for (each pixel in the bounding box) {
        if (inside(points, pixel)) {
            put_pixel(pixel);
        }
    }
}

I really like this method. It is simple and it works. It’s quite simple to find a describing rectangle. It’s also no problem to check whether a point belongs to the two-dimensional triangle (or any convex polygon).

Off Topic: if I have to write code that will run on, say, a plane, and this code will have to check whether a point belongs to a polygon, I will never get on this plane. Turns out, it’s surprisingly difficult to solve this problem reliably.

Why do I like this code? Because after seeing this, a newbie in programming will accept it with enthusiasm, and the one familiar with programming will simply chuckle thinking something like “What an idiot wrote it?”. And an expert in computer graphics programming will shrug his shoulders and say: “Well, that’s how it works in real life”. Massively parallel computations in thousands of small graphic processes (I'm talking about regular consumer computers) work wonders. But we will write code for the CPU, so we are not going to use this method. Anyway, our abstraction is quite enough for understanding the operating principle.

So, the initial stub will look like this:

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    line(t0, t1, image, color);
    line(t1, t2, image, color);
    line(t2, t0, image, color);
}
[...]
    Vec2i t0[3] = {Vec2i(10, 70),   Vec2i(50, 160),  Vec2i(70, 80)};
    Vec2i t1[3] = {Vec2i(180, 50),  Vec2i(150, 1),   Vec2i(70, 180)};
    Vec2i t2[3] = {Vec2i(180, 150), Vec2i(120, 160), Vec2i(130, 180)};
    triangle(t0[0], t0[1], t0[2], image, red);
    triangle(t1[0], t1[1], t1[2], image, white);
    triangle(t2[0], t2[1], t2[2], image, green);

As usual, the appropriate commit is available on github. The code is simple: I provide three triangles for the initial debugging of your code. If we invoke line() inside the triangle function, we’ll get the contour of the triangle. How to draw a filled triangle?

A good method of drawing a triangle should have the following features:

• It should be (surprise!) simple and fast.
  
• It should be symmetrical: the picture should not depend on the order of vertices passed to the drawing function.
  
• If two triangles have two common vertices, there should be no holes between them because of rasterization rounding.
  

We could add much more requirements, but let’s do with these ones.

Line sweeping is traditionally used:

• Sort vertices of the triangle on their y-coordinate;
  
• Rasterize in parallel the left and the right sides of the triangle;
  
• Draw a horizontal line segment between the left and the right boundary points.
  

That’s when my students began to feel at a loss trying to find out which one of the line segments was right and which one was left. Besides, the triangle had three line segments…

At this point, I left my students for about an hour, reading my code was less valuable than comparing their code with mine.

[one hour passed]

How do I draw? Once again, if you have a better method, I’ll be glad to take it on board. Let’s assume that we have three points of the triangle, t0, t1, t2, they are sorted in ascending order in the y-coordinate.

Then, boundary A will be between t0 and t2, boundary B will be between t0 and t1, and then between t1 and t2.

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    // sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
    if (t0.y>t1.y) std::swap(t0, t1);
    if (t0.y>t2.y) std::swap(t0, t2);
    if (t1.y>t2.y) std::swap(t1, t2);
    line(t0, t1, image, green);
    line(t1, t2, image, green);
    line(t2, t0, image, red);
}

Here, boundary A is red, and boundary B is green.

Unfortunately, boundary B is compound. Let's draw the bottom half of the triangle by cutting it horizontally in the angle of boundary B.

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    // sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
    if (t0.y>t1.y) std::swap(t0, t1);
    if (t0.y>t2.y) std::swap(t0, t2);
    if (t1.y>t2.y) std::swap(t1, t2);
    int total_height = t2.y-t0.y;
    for (int y=t0.y; y<=t1.y; y++) {
        int segment_height = t1.y-t0.y+1;
        float alpha = (float)(y-t0.y)/total_height;
        float beta  = (float)(y-t0.y)/segment_height; // be careful with divisions by zero
        Vec2i A = t0 + (t2-t0)*alpha;
        Vec2i B = t0 + (t1-t0)*beta;
        image.set(A.x, y, red);
        image.set(B.x, y, green);
    }
}

Note that we’ve got nowhere continuous line segments here. Unlike the last time (when we drew straight lines) I didn’t bother with rotating the image. Why? Turns out, it’s not obvious for everyone. If we connect the corresponding pairs of points by horizontal lines, gaps will disappear:

Now, it’s time to draw the second part of the triangle. We can do this by adding the second loop:

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    // sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
    if (t0.y>t1.y) std::swap(t0, t1);
    if (t0.y>t2.y) std::swap(t0, t2);
    if (t1.y>t2.y) std::swap(t1, t2);
    int total_height = t2.y-t0.y;
    for (int y=t0.y; y<=t1.y; y++) {
        int segment_height = t1.y-t0.y+1;
        float alpha = (float)(y-t0.y)/total_height;
        float beta  = (float)(y-t0.y)/segment_height; // be careful with divisions by zero
        Vec2i A = t0 + (t2-t0)*alpha;
        Vec2i B = t0 + (t1-t0)*beta;
        if (A.x>B.x) std::swap(A, B);
        for (int j=A.x; j<=B.x; j++) {
            image.set(j, y, color); // attention, due to int casts t0.y+i != A.y
        }
    }
    for (int y=t1.y; y<=t2.y; y++) {
        int segment_height =  t2.y-t1.y+1;
        float alpha = (float)(y-t0.y)/total_height;
        float beta  = (float)(y-t1.y)/segment_height; // be careful with divisions by zero
        Vec2i A = t0 + (t2-t0)*alpha;
        Vec2i B = t1 + (t2-t1)*beta;
        if (A.x>B.x) std::swap(A, B);
        for (int j=A.x; j<=B.x; j++) {
            image.set(j, y, color); // attention, due to int casts t0.y+i != A.y
        }
    }
}

This could be enough, but I really don’t like to see the same code twice, especially so close to each other. That's why we will make it a bit less readable, but easier for modifications:

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    if (t0.y==t1.y && t0.y==t2.y) return; // i dont care about degenerate triangles
    // sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
    if (t0.y>t1.y) std::swap(t0, t1);
    if (t0.y>t2.y) std::swap(t0, t2);
    if (t1.y>t2.y) std::swap(t1, t2);
    int total_height = t2.y-t0.y;
    for (int i=0; it1.y-t0.y || t1.y==t0.y;
        int segment_height = second_half ? t2.y-t1.y : t1.y-t0.y;
        float alpha = (float)i/total_height;
        float beta  = (float)(i-(second_half ? t1.y-t0.y : 0))/segment_height; // be careful: with above conditions no division by zero here
        Vec2i A =               t0 + (t2-t0)*alpha;
        Vec2i B = second_half ? t1 + (t2-t1)*beta : t0 + (t1-t0)*beta;
        if (A.x>B.x) std::swap(A, B);
        for (int j=A.x; j<=B.x; j++) {
            image.set(j, t0.y+i, color); // attention, due to int casts t0.y+i != A.y
        }
    }
}

Here’s the commit for drawing 2D triangles.

Drawing a Model

We already know how to draw a model with empty triangles. Let’s fill them with a random color. This will help us to see how well we have encoded filling of triangles. Here’s the code.

for (int i=0; infaces(); i++) {
        std::vector face = model->face(i);
        Vec2i screen_coords[3];
        for (int j=0; j<3; j++) {
            Vec3f world_coords = model->vert(face[j]);
            screen_coords[j] = Vec2i((world_coords.x+1.)*width/2., (world_coords.y+1.)*height/2.);
        }
        triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(rand()%255, rand()%255, rand()%255, 255));
    }

It's simple: just like before, we traverse all the triangles, convert world coordinates to screen ones and draw triangles. I’ll provide the detailed description of various coordinate systems in my future articles. It should look something like this:

Flat Shading

Let’s get rid of these clown-colors and illuminate our model.

Captain Obvious: «At the same light intensity, the polygon is illuminated most brightly when it is perpendicular to the light.»

Let’s compare:

We’ll get zero illumination, if the polygon is parallel to the vector of light.

To paraphrase: the intensity of illumination is equal to the scalar product of the vector of light and the normal to the given triangle.

The normal to the triangle can be calculated simply as the cross product of its two sides.

for (int i=0; infaces(); i++) {
        std::vector face = model->face(i);
        Vec2i screen_coords[3];
        Vec3f world_coords[3];
        for (int j=0; j<3; j++) {
            Vec3f v = model->vert(face[j]);
            screen_coords[j] = Vec2i((v.x+1.)*width/2., (v.y+1.)*height/2.);
            world_coords[j]  = v;
        }
        Vec3f n = (world_coords[2]-world_coords[0])^(world_coords[1]-world_coords[0]);
        n.normalize();
        float intensity = n*light_dir;
        if (intensity>0) {
            triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(intensity*255, intensity*255, intensity*255, 255));
        }
    }

But the inner product can be negative. What does it mean? It means that the light falls behind the polygon. If the model is good (usually, it’s a task for 3D modelers), we can simply not draw this triangle. This allows us to quickly remove some invisible triangles. It’s called Back-face culling.

Is the model of my head more detailed now? Well, there are a quarter million triangles in it. We will add more details later and get the picture I provided in the first article.

Note that the inner cavity of the mouth is drawn on top of the lips. Such a fast clipping of invisible triangles removes everything unnecessary for convex models. We’ll get rid of these flaws the next time, when we encode the z-buffer.

Here’s the current version of the render.