12. Triangle

A filled triangle is ideal for arrows in flowcharts!

The algorithm for this particular rasterization method is based off the one found here.

The paramters supplied are the 3 vertices of the triangle.

Note: I'm using 1-indexed variables here to better match the variables in the algorithm.

void btprnt_draw_triangle(btprnt_region *r,
                          int v1x, int v1y,
                          int v2x, int v2y,
                          int v3x, int v3y,
                          int c);

Before the processing begins, vertices are sorted out in ascending order by y, making v1 the highest point.

{
    int tmpx;
    int tmpy;

    if (v1y > v2y) {
        tmpy = v1y;
        tmpx = v1x;

        v1y = v2y;
        v1x = v2x;

        v2y = tmpy;
        v2x = tmpx;
    }

    if (v1y > v3y) {
        tmpy = v1y;
        tmpx = v1x;

        v1y = v3y;
        v1x = v3x;

        v3y = tmpy;
        v3x = tmpx;
    }

    if (v2y > v3y) {
        tmpy = v2y;
        tmpx = v2x;

        v2y = v3y;
        v2x = v3x;

        v3y = tmpy;
        v3x = tmpx;
    }
}

The bresenham approach to filling involves draw two lines in parallel, and then drawing the horizontal lines between them.

This particular adaptation is from the java code, and assumes that vertices 2 + 3 sahre the same Y axis.

static int signum(int x)
{
    if (x < 0) return -1;
    if (x > 0) return 1;
    else return 0;
}


static void bresenham_fill(btprnt_region *r,
                           int v1x, int v1y,
                           int v2x, int v2y,
                           int v3x, int v3y,
                           int c)
{
    int vtmp1x;
    int vtmp1y;
    int vtmp2x;
    int vtmp2y;

    int changed1;
    int changed2;

    int dx1;
    int dy1;
    int dx2;
    int dy2;

    int signx1;
    int signx2;

    int signy1;
    int signy2;

    int e1;
    int e2;

    int i;

    vtmp1x = v1x;
    vtmp1y = v1y;

    vtmp2x = v1x;
    vtmp2y = v1y;

    changed1 = 0;
    changed2 = 0;

    dx1 = abs(v2x - v1x);
    dy1 = abs(v2y - v1y);

    dx2 = abs(v3x - v1x);
    dy2 = abs(v3y - v1y);

    signx1 = signum(v2x - v1x);
    signx2 = signum(v3x - v1x);

    signy1 = signum(v2y - v1y);
    signy2 = signum(v3y - v1y);

    if (dy1 > dx1) {
        int tmp;
        tmp = dx1;
        dx1 = dy1;
        dy1 = tmp;
        changed1 = 1;
    }

    if (dy2 > dx2) {
        int tmp;
        tmp = dx2;
        dx2 = dy2;
        dy2 = tmp;
        changed2 = 1;
    }

    e1 = 2 * dy1 - dx1;
    e2 = 2 * dy2 - dx2;

    for(i = 0; i <= dx1; i++) {
        btprnt_draw_line(r, vtmp1x, vtmp1y, vtmp2x, vtmp2y, c);

        while (e1 >= 0) {
            if (changed1) vtmp1x += signx1;
            else vtmp1y += signy1;

            e1 = e1 - 2 * dx1;
        }

        if (changed1) vtmp1y += signy1;
        else vtmp1x += signx1;

        e1 = e1 + 2 * dy1;

        while (vtmp2y != vtmp1y) {
            while (e2 >= 0) {
                if (changed2) vtmp2x += signx2;
                else vtmp2y += signy2;

                e2 = e2 - 2 * dx2;
            }

            if (changed2) vtmp2y += signy2;
            else vtmp2x += signx2;

            e2 = e2 + 2 * dy2;
        }
    }

}

In the more general case, the triangle is split in half into two smaller triangles: one with a flat bottom, the other with a flat top.

int v4x, v4y;

v4x = (v1x +
    ((float)(v2y - v1y)/(v3y - v1y)) *
    (v3x - v1x));
v4y = v2y;

bresenham_fill(r,
               v1x, v1y,
               v2x, v2y,
               v4x, v4y,
               c);

bresenham_fill(r,
               v3x, v3y,
               v2x, v2y,
               v4x, v4y,
               c);

<<flat_triangle_fill>>

void btprnt_draw_triangle(btprnt_region *r,
                          int v1x, int v1y,
                          int v2x, int v2y,
                          int v3x, int v3y,
                          int c)
{
<<sort_vertices_by_y>>
    if (v2y == v3y) {
        bresenham_fill(r,
                       v1x, v1y,
                       v2x, v2y,
                       v3x, v3y,
                       c);
    } if (v1y == v2y) {
        bresenham_fill(r,
                       v3x, v3y,
                       v1x, v1y,
                       v2x, v2y,
                       c);
    } else {
<<split_the_triangle>>
    }

}

---

prev | home | next