0
$\begingroup$

Here is my simple scanline-based triangle rasterizer using pure integer arithmetic. I adapted the code from this Stack Overflow answer The below code attempts to render a coloured quadrilateral by rendering two triangles.

/* g++ trig.cpp -o trig -lSDL2 */

#include <cstdlib>
#include <ctime>

#define SDL_MAIN_HANDLED
#include <SDL2/SDL.h>

#define SCREEN_HEIGHT 400
#define SCREEN_WIDTH  600

// TODO make an array of values to be interpolated
// TODO 1/z buffer using something like this: 0xfffff / z where z is integer
// TODO uv texture mapping
typedef struct
{
    int x, y, z;
    uint8_t r, g, b;
    int u, v;
} Point2D;

uint8_t pixels[SCREEN_HEIGHT * SCREEN_WIDTH * 4];

void SetPixel(int x, int y, uint8_t r, uint8_t g, uint8_t b)
{
    int offset = y * SCREEN_WIDTH * 4 + x * 4;

    pixels[offset] = r;
    pixels[offset + 1] = g;
    pixels[offset + 2] = b;
    pixels[offset + 3] = 255;
}

int ContourX[SCREEN_HEIGHT][2]; // min X and max X for every horizontal line within the triangle
int ContourR[SCREEN_HEIGHT][2]; // red value for every horizontal line
int ContourG[SCREEN_HEIGHT][2]; // green value for every horizontal line
int ContourB[SCREEN_HEIGHT][2]; // blue value for every horizontal line

#define ABS(x) ((x >= 0) ? x : -x)

// Scans a side of a triangle setting min X and max X in ContourX[][] (same for ContourR, ContourG, and ContourB) using the Bresenham's
void TriangleLine(const Point2D& p0, const Point2D& p1)
{
    // DDA variables
    int kx, ky, kr, kg, kb; // step directions
    int dx, dy, dr, dg, db; // abs delta
    kx = 0; dx = p1.x - p0.x; if (dx > 0) kx = 1; if (dx < 0) { kx = -1; dx = -dx; }
    ky = 0; dy = p1.y - p0.y; if (dy > 0) ky = 1; if (dy < 0) { ky = -1; dy = -dy; }
    kr = 0; dr = p1.r - p0.r; if (dr > 0) kr = 1; if (dr < 0) { kr = -1; dr = -dr; }
    kg = 0; dg = p1.g - p0.g; if (dg > 0) kg = 1; if (dg < 0) { kg = -1; dg = -dg; }
    kb = 0; db = p1.b - p0.b; if (db > 0) kb = 1; if (db < 0) { kb = -1; db = -db; }

    int n;
    n = dx;
    if (n < dy) n = dy;
    if (n < dr) n = dr;
    if (n < dg) n = dg;
    if (n < db) n = db;
    if (!n) n = 1;

    // target buffer according to ky direction
    int target; if (ky > 0) target = 0; else target = 1;

    // integer DDA line start point
    int x = p0.x;
    int y = p0.y;
    int r = p0.r;
    int g = p0.g;
    int b = p0.b;

    // fix endpoints just to be sure (wrong division constants by +/-1 can cause that last point is missing)
    ContourX[p0.y][target] = p0.x;
    ContourR[p0.y][target] = p0.r;
    ContourG[p0.y][target] = p0.g;
    ContourB[p0.y][target] = p0.b;

    ContourX[p1.y][target] = p1.x;
    ContourR[p1.y][target] = p1.r;
    ContourG[p1.y][target] = p1.g;
    ContourB[p1.y][target] = p1.b;

    int cx, cy, cr, cg, cb, i;
    for (cx = cy = cr = cg = cb = n, i = 0; i < n; ++i)
    {
        ContourX[y][target] = x;
        ContourR[y][target] = r;
        ContourG[y][target] = g;
        ContourB[y][target] = b;

        cx -= dx; if (cx <= 0){ cx += n; x += kx; }
        cy -= dy; if (cy <= 0){ cy += n; y += ky; }
        cr -= dr; if (cr <= 0){ cr += n; r += kr; }
        cg -= dg; if (cg <= 0){ cg += n; g += kg; }
        cb -= db; if (cb <= 0){ cb += n; b += kb; }
    }
}

void DrawTriangle(const Point2D& p0, const Point2D& p1, const Point2D& p2)
{
    TriangleLine(p0, p1);
    TriangleLine(p1, p2);
    TriangleLine(p2, p0);

    int y0, y1; // min and max y
    y0 = p0.y; if (y0 > p1.y) y0 = p1.y; if (y0 > p2.y) y0 = p2.y;
    y1 = p0.y; if (y1 < p1.y) y1 = p1.y; if (y1 < p2.y) y1 = p2.y;

    int x0, r0, g0, b0;
    int x1, r1, g1, b1;
    int dx;
    int kr, kg, kb;
    int dr, dg, db;
    int r, cr;
    int g, cg;
    int b, cb;

    for (int y = y0; y <= y1; ++y)
    {
        if (ContourX[y][0] < ContourX[y][1])
        {
            x0 = ContourX[y][0];
            r0 = ContourR[y][0];
            g0 = ContourG[y][0];
            b0 = ContourB[y][0];

            x1 = ContourX[y][1];
            r1 = ContourR[y][1];
            g1 = ContourG[y][1];
            b1 = ContourB[y][1];
        }
        else
        {
            x1 = ContourX[y][0];
            r1 = ContourR[y][0];
            g1 = ContourG[y][0];
            b1 = ContourB[y][0];

            x0 = ContourX[y][1];
            r0 = ContourR[y][1];
            g0 = ContourG[y][1];
            b0 = ContourB[y][1];
        }

        dx = x1 - x0;

        kr = 0; dr = r1 - r0; if (dr > 0) kr = 1; if (dr < 0) { kr = -1; dr = -dr; }
        kg = 0; dg = g1 - g0; if (dg > 0) kg = 1; if (dg < 0) { kg = -1; dg = -dg; }
        kb = 0; db = b1 - b0; if (db > 0) kb = 1; if (db < 0) { kb = -1; db = -db; }

        r = r0; cr = dx;
        g = g0; cg = dx;
        b = b0; cb = dx;

        for (int x = x0; x <= x1; ++x)
        {
            SetPixel(x, y, r, g, b);

            cr -= dr; if (cr <= 0) { cr += dx; r += kr; }
            cg -= dg; if (cg <= 0) { cg += dx; g += kg; }
            cb -= db; if (cb <= 0) { cb += dx; b += kb; }
        }
    }
}

int main(void)
{
    Point2D p0, p1, p2, p3;

    // clear the screen
    memset(pixels, 0, sizeof(pixels));

    // generate random triangle coordinates
    srand((unsigned) time(NULL));

    p0.x = 30;
    p0.y = 41;
    p0.r = 255;
    p0.g = 0;
    p0.b = 0;

    p1.x = 350;
    p1.y = 58;
    p1.r = 0;
    p1.g = 255;
    p1.b = 0;

    p2.x = 40;
    p2.y = 311;
    p2.r = 0;
    p2.g = 0;
    p2.b = 255;

    p3.x = 572;
    p3.y = 280;
    p3.r = 255;
    p3.g = 140;
    p3.b = 0;

    DrawTriangle(p0, p1, p2);
    DrawTriangle(p1, p3, p2);

    SDL_Init(SDL_INIT_EVERYTHING);

    SDL_Window* window = SDL_CreateWindow
    (
        "Trig",
        SDL_WINDOWPOS_UNDEFINED,
        SDL_WINDOWPOS_UNDEFINED,
        SCREEN_WIDTH,
        SCREEN_HEIGHT,
        SDL_WINDOW_SHOWN
    );

    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
    SDL_Texture* texture = SDL_CreateTexture(renderer, SDL_PIXELFORMAT_ABGR8888, SDL_TEXTUREACCESS_STREAMING, SCREEN_WIDTH, SCREEN_HEIGHT);
    SDL_Event event;

    bool quit = false;

    while (!quit)
    {
        if (SDL_PollEvent(&event))
        {
            switch (event.type)
            {
            case SDL_QUIT:
            {
                quit = true;
                break;
            }
            }
        }

        SDL_UpdateTexture(texture, NULL, &pixels[0], SCREEN_WIDTH * 4);
        SDL_RenderCopy(renderer, texture, NULL, NULL);
        SDL_RenderPresent(renderer);
    }

    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);
    SDL_Quit();

    return 0;
}

The problem is that there is an unfilled diagonal line in a quadrilateral

I am not sure what changes I should make to fix this issue. Any ideas? Also, how to make sure that edges don't overlap each other?

When I change the order of vertexes to

    DrawTriangle(p0, p1, p2);
    DrawTriangle(p1, p2, p3);

The problem seems to be solved but there are overlapping pixels if I change my pixel rendering function to

void SetPixel(int x, int y, uint8_t r, uint8_t g, uint8_t b)
{
    int offset = y * SCREEN_WIDTH * 4 + x * 4;

    pixels[offset] += r;
    pixels[offset + 1] += g;
    pixels[offset + 2] += b;
    pixels[offset + 3] = 255;
}

I asked this related question about a month ago and I didn't get a complete answer because I want to know implementation details. I appreciate it if anyone can modify my sample code to show how it is done.

Edit: I learned about the "top left rule" and I changed this line in DrawTriangle

for (int x = x0; x <= x1; ++x)

to

for (int x = x0; x < x1; ++x)

It seems to work well but I am not sure if this is the correct way to implement this rule. Are there any edge cases?

$\endgroup$
2
  • $\begingroup$ Is this a triangle rasterizer or a quadrilateral rasterizer? Because the latter would use the fact that it's a quadrilateral in its rasterization. Quadrilaterals don't have "diagonals", and a quad-rasterizer wouldn't care about them. It looks like it's just a triangle rasterizer. $\endgroup$ Aug 17, 2022 at 0:23
  • $\begingroup$ @NicolBolas you are right, fixed $\endgroup$
    – Jimmy Yang
    Aug 17, 2022 at 0:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.