Course content

• Article 1: Bresenham's algorithm
• Article 2: rasterize a triangle + trim the back faces
• Article 3: Removing invisible surfaces: z-buffer
• Article 4: Required Geometry: Matrix Festival
  
  • 4a: Building perspective distortion
  • 4b: we move the camera and what follows from this
  • 4c: new rasterizer and perspective distortion correction
• Article 5: We write shaders under our library
• Article 6: A little more than just a shader: rendering shadows

Code improvement

• Article 3.1: It is time for refactoring
• Article 3.14: Beautiful Matrix Class

---

Official translation (with a bit of polishing) is available here.

---

Update:

Attention, article 4c provides a new, simpler version of the rasterizer.

Let's get acquainted, it's me.



That is, the model of my head, rendered in the program, which we will do in the next hour or two.

Last time, we drew a wire mesh of a three-dimensional model, this time we will fill the polygons. More precisely, triangles, since OpenGL triangulates almost any polygon, so there’s no need to disassemble a complicated case. I remind you that this series of articles was created for independentprogramming. The time I give here is not the time to read my code. This is the time to write your code from scratch. My code is here only to compare your (working) code with mine. I am not a good programmer at all, so your code can be significantly better than mine. Any criticism is welcome, glad to any questions.

Please, if you follow this tutorial and write your code, post it on github.com/code.google.com and the like and give links in the comments! This can help both you (other people can advise) and future readers.

Draw a filled triangle

So, the topic for today (about two hours for poorly programming, but motivated students): drawing two-dimensional triangles. Last time, we analyzed the Bresenham algorithm for rasterizing a segment, now the task is to draw a filled triangle. You will laugh, but this is not a trivial task. I don’t know why, but I know that it is. Most of my students spend substantially more than a couple of hours on this task without hints. Let's determine the method, and then we will program.

At the very beginning, let's look at this pseudocode:

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 love this method. He is simple and working. Finding a describing rectangle is extremely simple; checking whether a point belongs to a two-dimensional triangle (and to any convex polygon) is also simple.

Offtopic: if I need to write a code that will spin on, say, an airplane, and this code will have to check whether the point belongs to the polygon, I will never land on this airplane. This is a surprisingly difficult problem if we want to solve it reliably .

Why do I love this code? Yes, because, having seen this, a completely newcomer to programming will take it with enthusiasm, a person who is a little familiar with programming will only smug smugly, they say, an idiot wrote. And an expert in computer graphics programming will just shrug, well, yes, yes, that's how it works in real life. Massively parallel computing in thousands of small GPUs (I'm talking about ordinary consumer computers) do wonders. But we will write code for the central processor, so we will not use this method. And what's the difference, as it is in silicon, our abstraction is quite enough to understand the principle of work.

Okay, 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, on githabe available code mark . Everything is simple in this code: I give three triangles for the initial debugging of your code; if inside the triangle function just make a call to line (), then we get the outline of the triangle. How to draw a filled triangle?

A good triangle rendering method should have the following properties:

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

You can add many more requirements, but we are satisfied with these three.

Traditionally used line sweeping (sweeping segment?):

• Sort the vertices of the triangle by their y-coordinate
• Rasterize the left and right borders of the triangle in parallel
• Draw the horizontal line between the left and right border points

Then my students start to get lost, who is left, who is right, and indeed, there are three segments in the triangle ...
At this moment I leave my students for about an hour, reading my code is much less valuable than comparing my (suffering!) Code with mine .

[an hour has passed]

How do I draw? Once again, if you have a better method, then I will take it into service with great pleasure. Let's assume that we have three points of the triangle, t0, t1, t2, they are sorted in ascending y-coordinate.
Then the boundary A will be between t0 and t2, the 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 we have border A painted in red and border B in green.



Border B, unfortunately, is composite. Let's draw the bottom half of the triangle, cutting it horizontally at the break point of border 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 (Ax, y, red);
        image.set (Bx, y, green);
    }
}

Notice that this time I got discontinuous segments. Unlike the last time (where we drew the lines), I did not bother to rotate the image 90 °. Why? This is not the whole obvious point. Simply, if we connect the corresponding pairs of points with horizontal lines, the spaces will disappear:



Now it remains to draw the second half of the triangle. This can be done by adding a 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 (Ax> Bx) std :: swap (A, B);
        for (int j = Ax; j <= Bx; j ++) {
            image.set (j, y, color); // attention, due to int casts t0.y + i! = Ay
        }
    }
    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 (Ax> Bx) std :: swap (A, B);
        for (int j = Ax; j <= Bx; j ++) {
            image.set (j, y, color); // attention, due to int casts t0.y + i! = Ay
        }
    }
}

One could calm down on this, but indigestion happens when I see the same code twice, and even so close. Therefore, we will make it a little less readable, but simpler 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 (Ax> Bx) std :: swap (A, B);
        for (int j = Ax; j <= Bx; j ++) {
            image.set (j, t0.y + i, color); // attention, due to int casts t0.y + i! = Ay
        }
    }
}

The fingerprint of the code for drawing 2d triangles.

Draw 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 check how well we encoded the filling of the triangles. Here is 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: as before, we go through all the triangles, turn the world coordinates into screen coordinates and draw triangles. A detailed description of the different coordinate systems in subsequent articles. You should get something like this:

Flat tint

Let's now remove these clown colors and illuminate our model.
Captain Evidence: “At the same light intensity, the polygon is lit as brightly as possible if the light is perpendicular to it.”

Let's compare:




We will get zero illumination if the polygon is parallel to the light vector.
To rephrase: the intensity of illumination is equal to the scalar product of the light vector and the normal to this triangle.
The normal to a triangle can be calculated simply as a vector product of its two edges.

    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 scalar product may be negative, what does this mean? This means that light falls behind the polygon. If the model is good (usually not our concern, but 3D modelers), then we just can not draw this triangle. This allows you to quickly remove part of the invisible triangles. In English literature called Back-face culling .


Does my head model look more detailed? Well, there’s a quarter million triangles in it. Nothing, we will add details later, having received the picture that I gave for the seed in the first article.

Notice the inside of the mouth is drawn over the lips. Well, what, such a quick clipping of invisible triangles removes everything unnecessary only for convex models. We will remove these flaws next time by encoding z-buffer.

Current version renderer.