<p>Here is my simple scanline-based triangle rasterizer using pure integer arithmetic. I adapted the code from <a href="https://stackoverflow.com/questions/65460132/how-to-hide-invisible-elements-of-the-3d-drawing/65664918#65664918">this Stack Overflow answer</a> The below code attempts to render a coloured quadrilateral by rendering two triangles.</p>
<pre><code>/* g++ trig.cpp -o trig -lSDL2 */

#include &lt;cstdlib&gt;
#include &lt;ctime&gt;

#define SDL_MAIN_HANDLED
#include &lt;SDL2/SDL.h&gt;

#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 &gt;= 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&amp; p0, const Point2D&amp; 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 &gt; 0) kx = 1; if (dx &lt; 0) { kx = -1; dx = -dx; }
    ky = 0; dy = p1.y - p0.y; if (dy &gt; 0) ky = 1; if (dy &lt; 0) { ky = -1; dy = -dy; }
    kr = 0; dr = p1.r - p0.r; if (dr &gt; 0) kr = 1; if (dr &lt; 0) { kr = -1; dr = -dr; }
    kg = 0; dg = p1.g - p0.g; if (dg &gt; 0) kg = 1; if (dg &lt; 0) { kg = -1; dg = -dg; }
    kb = 0; db = p1.b - p0.b; if (db &gt; 0) kb = 1; if (db &lt; 0) { kb = -1; db = -db; }

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

    // target buffer according to ky direction
    int target; if (ky &gt; 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 &lt; n; ++i)
    {
        ContourX[y][target] = x;
        ContourR[y][target] = r;
        ContourG[y][target] = g;
        ContourB[y][target] = b;

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

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

    int y0, y1; // min and max y
    y0 = p0.y; if (y0 &gt; p1.y) y0 = p1.y; if (y0 &gt; p2.y) y0 = p2.y;
    y1 = p0.y; if (y1 &lt; p1.y) y1 = p1.y; if (y1 &lt; 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 &lt;= y1; ++y)
    {
        if (ContourX[y][0] &lt; 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 &gt; 0) kr = 1; if (dr &lt; 0) { kr = -1; dr = -dr; }
        kg = 0; dg = g1 - g0; if (dg &gt; 0) kg = 1; if (dg &lt; 0) { kg = -1; dg = -dg; }
        kb = 0; db = b1 - b0; if (db &gt; 0) kb = 1; if (db &lt; 0) { kb = -1; db = -db; }

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

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

            cr -= dr; if (cr &lt;= 0) { cr += dx; r += kr; }
            cg -= dg; if (cg &lt;= 0) { cg += dx; g += kg; }
            cb -= db; if (cb &lt;= 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
    (
        &quot;Trig&quot;,
        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(&amp;event))
        {
            switch (event.type)
            {
            case SDL_QUIT:
            {
                quit = true;
                break;
            }
            }
        }

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

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

    return 0;
}
</code></pre>
<p>The problem is that there is an unfilled diagonal line in a quadrilateral</p>
<p><a href="https://i.sstatic.net/Nx38t.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Nx38t.png" alt="" /></a></p>
<p>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?</p>
<p>When I change the order of vertexes to</p>
<pre><code>    DrawTriangle(p0, p1, p2);
    DrawTriangle(p1, p2, p3);
</code></pre>
<p>The problem seems to be solved but there are overlapping pixels if I change my pixel rendering function to</p>
<pre><code>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;
}
</code></pre>
<p>I asked <a href="https://computergraphics.stackexchange.com/questions/12737/how-to-draw-smoother-lines-and-triangles">this related question</a> 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.</p>
<p>Edit: I learned about the &quot;top left rule&quot; and I changed this line in <code>DrawTriangle</code></p>
<pre><code>for (int x = x0; x &lt;= x1; ++x)
</code></pre>
<p>to</p>
<pre><code>for (int x = x0; x &lt; x1; ++x)
</code></pre>
<p>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?</p>

CC BY-SA 4.0
2022-08-17T00:23:52.650Z
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.
Nicol Bolas
CC BY-SA 4.0
2022-08-17T00:30:53.480Z
@NicolBolas you are right, fixed
Jimmy Yang
<c++><interpolation><scanline>
How to make sure that triangles share edges (also not overlap each other) when rendering a quadrilateral?
Jimmy Yang
# How to make sure that triangles share edges (also not overlap each other) when rendering a quadrilateral?

(Asked by: username_0 on 2022-08-16)

Here is my simple scanline-based triangle rasterizer using pure integer arithmetic. I adapted the code from [this Stack Overflow answer](https://stackoverflow.com/questions/65460132/how-to-hide-invisible-elements-of-the-3d-drawing/65664918#65664918) 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

[![](https://i.sstatic.net/Nx38t.png)](https://i.sstatic.net/Nx38t.png)

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](https://computergraphics.stackexchange.com/questions/12737/how-to-draw-smoother-lines-and-triangles) 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?

**Tags:** c++, interpolation, scanline

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 you are right, fixed  

---

## 0 answers

