# How to make sure that triangles share edges (also not overlap each other) when rendering a quadrilateral?

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?

• 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. Aug 17, 2022 at 0:23
• @NicolBolas you are right, fixed Aug 17, 2022 at 0:30