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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.