Skip to content

22. Triangle Rasterization

Dated: 14-05-2025

Solid Fill Triangle Rendering

Sort the vertices of a triangle based on the \(y\) value.

  1. Top vertex - \((x_0, y_0)\)
  2. Middle vertex - \((x_1, y_1)\)
  3. Bottom vertex - \((x_2, y_2)\)

Now consider the filling process to be done in 2 parts.

  1. from \(y_0\) to \(y_1\)
  2. from \(y_1\) to \(y_2\)

Both routines will use DDA algorithm to find \(x\) values across the pixel span of each scanline.

Sub Pixel Accuracy

void SubPixDDA(float x_a, float y_a, float x_b, float y_b) {
    int y_ai, y_bi; // Scanline range
    int y; // iterator for scanline

    float xp; // pre-step in x
    float x;  // current x position
    float yf; // fractional distance in y

    float dxdy = (x_b - x_a) / (y_b - y_a); // 1 / slope

    y_ai = ceil(y_a);
    y_bi = ceil(y_b);

    yf = y_ai - y_a;
    xp = dxdy * yf;

    x = x_a + xp;

    for (y = y_ai; y < y_bi; y++) {
        x += dxdy;
    }
}

Smooth Shaded Triangle Rasterization

This is used to approximate

  • Light fall off
  • curved surface

This technique linearly interpolates the RGB colors.

To avoid artifacts, use sub texel accuracy technique.

Texture Mapped Triangle Rasterization

This is the process of interpolating an image over the triangle.
The image itself is called the texture map and a pixel on it is called a texel.

Color BilinearSampling(float u, float v, Color texMap[256][256]) {
    Color c00, c01, c10, c11;
    int u0, u1, v0, v1;
    float u_frac, v_frac;

    u0 = floor(u);
    u1 = ceil(u);
    v0 = floor(v);
    v1 = ceil(v);

    u_frac = u - u0;
    v_frac = v - v0;

    c00 = texMap[u0][v0];
    c01 = texMap[u0][v1];
    c10 = texMap[u1][v0];
    c11 = texMap[u1][v1];

    return (
        v_frac * (u_frac * c11 + (1 - u_frac) * c01) +
        (1 - v_frac) * (u_frac * c10 + (1 - u_frac) * c00);
    );
}

Sub Texel Accuracy

Any value that is interpolated over the triangle such as \(r, g\) and \(b\) for smooth shading and \(u\) and \(v\) for texture mapping must take into account the fractional component of the vertex information.
Taking these fractional quantities into account is called sub texel accuracy.

To formalize this, it is identical to the sub pixel DDA.
All that need to be done is to substitute \(u\) or \(v\) for \(x\) in the original, and substitute \(x\) for \(y\) in the original.

Flat Filling Triangles

The general function1 for linear interpolation is

\[f(x) = A + x \times \left(\frac{B - A}{\text{steps}}\right)\]

Pseudo Code

Imagine a triangle with 3 vertices \(A, B\) and \(C\).
First, sort them such that

\[A.y \le B.y \le C.y\]

Now, each scanline will have a left end point i.e. \(S.x\) and a right end point i.e. \(E.x\).

\[S = A \implies S.x = A.x \quad \text{and} \quad S.y = A.y\]
if (B.y - A.y > 0) dx1 = (B.x - A.x) / (B.y - A.y);
else dx1 = 0;

if (C.y - A.y > 0) dx2 = (C.x - A.x) / (C.y - A.y);
else dx2 = 0;

if (C.y - B.y > 0) dx3 = (C.x - B.x) / (C.y - B.y);
else dx3 = 0;

S = E = A;

if(dx1 > dx2) {
    for (; S.y <= B.y; S.y++, E.y++, S.x += dx2, E.x += dx1)
        horizontal_line(S.x, E.x, S.y, E.x, color);

    E = B;

    for (; S.y <= C.y; S.y++, E.y++, S.x += dx2, E.x += dx3)
        horizontal_line(S.x, E.x, S.y, E.x, color);
}

else {
    for (; S.y <= B.y; S.y++, E.y++, S.x += dx1, E.x += dx2)
        horizontal_line(S.x, E.x, S.y, E.x, color);

    S=B;

    for (; S.y <= C.y; S.y++, E.y++, S.x += dx3, E.x += dx2)
        horizontal_line(S.x, E.x, S.y, E.x, color);
}

Gouraud Shading

The idea of gouraud and flat triangle is nearly the same.
Gouraud takes 3 additional parameters, which are the colors for all 3 vertices, which are linearly interpolated across the triangle.

The 256 color version needs

  • \(x\) related to \(y\)
  • color related to \(x\)
  • color related to \(y\)

The hi color version needs

  • \(x\) related to \(y\)
  • color.red related to \(x\)
  • color.green related to \(x\)
  • color.blue related to \(x\)
  • color.red related to \(y\)
  • color.green related to \(y\)
  • color.blue related to \(y\)
struct Point {
    float x, y;
    float r, g, b;
};

void putpixel(const Point& p);

void drawTriangle(Point A, Point B, Point C) {
    float dx1, dr1, dg1, db1;
    float dx2, dr2, dg2, db2;
    float dx3, dr3, dg3, db3;
    float dr, dg, db;

    if (B.y - A.y > 0) {
        dx1 = (B.x - A.x) / (B.y - A.y);
        dr1 = (B.r - A.r) / (B.y - A.y);
        dg1 = (B.g - A.g) / (B.y - A.y);
        db1 = (B.b - A.b) / (B.y - A.y);
    } else {
        dx1 = dr1 = dg1 = db1 = 0;
    }

    if (C.y - A.y > 0) {
        dx2 = (C.x - A.x) / (C.y - A.y);
        dr2 = (C.r - A.r) / (C.y - A.y);
        dg2 = (C.g - A.g) / (C.y - A.y);
        db2 = (C.b - A.b) / (C.y - A.y);
    } else {
        dx2 = dr2 = dg2 = db2 = 0;
    }

    if (C.y - B.y > 0) {
        dx3 = (C.x - B.x) / (C.y - B.y);
        dr3 = (C.r - B.r) / (C.y - B.y);
        dg3 = (C.g - B.g) / (C.y - B.y);
        db3 = (C.b - B.b) / (C.y - B.y);
    } else {
        dx3 = dr3 = dg3 = db3 = 0;
    }

    Point S = A, E = A, P;

    if (dx1 > dx2) {
        for (; S.y <= B.y; S.y++, E.y++) {
            if (E.x - S.x > 0) {
                dr = (E.r - S.r) / (E.x - S.x);
                dg = (E.g - S.g) / (E.x - S.x);
                db = (E.b - S.b) / (E.x - S.x);
            } else {
                dr = dg = db = 0;
            }
            P = S;
            for (; P.x < E.x; P.x++) {
                putpixel(P);
                P.r += dr;
                P.g += dg;
                P.b += db;
            }
            S.x += dx2; S.r += dr2; S.g += dg2; S.b += db2;
            E.x += dx1; E.r += dr1; E.g += dg1; E.b += db1;
        }
        E = B;
        for (; S.y <= C.y; S.y++, E.y++) {
            if (E.x - S.x > 0) {
                dr = (E.r - S.r) / (E.x - S.x);
                dg = (E.g - S.g) / (E.x - S.x);
                db = (E.b - S.b) / (E.x - S.x);
            } else {
                dr = dg = db = 0;
            }
            P = S;
            for (; P.x < E.x; P.x++) {
                putpixel(P);
                P.r += dr;
                P.g += dg;
                P.b += db;
            }
            S.x += dx2; S.r += dr2; S.g += dg2; S.b += db2;
            E.x += dx3; E.r += dr3; E.g += dg3; E.b += db3;
        }
    } else {
        for (; S.y <= B.y; S.y++, E.y++) {
            if (E.x - S.x > 0) {
                dr = (E.r - S.r) / (E.x - S.x);
                dg = (E.g - S.g) / (E.x - S.x);
                db = (E.b - S.b) / (E.x - S.x);
            } else {
                dr = dg = db = 0;
            }
            P = S;
            for (; P.x < E.x; P.x++) {
                putpixel(P);
                P.r += dr;
                P.g += dg;
                P.b += db;
            }
            S.x += dx1; S.r += dr1; S.g += dg1; S.b += db1;
            E.x += dx2; E.r += dr2; E.g += dg2; E.b += db2;
        }
        S = B;
        for (; S.y <= C.y; S.y++, E.y++) {
            if (E.x - S.x > 0) {
                dr = (E.r - S.r) / (E.x - S.x);
                dg = (E.g - S.g) / (E.x - S.x);
                db = (E.b - S.b) / (E.x - S.x);
            } else {
                dr = dg = db = 0;
            }
            P = S;
            for (; P.x < E.x; P.x++) {
                putpixel(P);
                P.r += dr;
                P.g += dg;
                P.b += db;
            }
            S.x += dx3; S.r += dr3; S.g += dg3; S.b += db3;
            E.x += dx2; E.r += dr2; E.g += dg2; E.b += db2;
        }
    }
}

Textured Triangles

cs602_i_22_1.jpeg

Environmental Mapping

The pseudo normal vectors (perpendicular to the vertices) can be used to index the texture map to do environmental mapping, i.e. shading.

\[U = \vec N_x \times \left(\frac {\text{width}} 2\right) + \left(\frac{\text{width}} 2\right) - 1\]
\[V = \vec N_y \times \left(\frac {\text{height}} 2\right) + \left(\frac{\text{height}} 2\right) - 1\]

These height and width are of the texture map.

References

  1. Read more about functions. ↩