t-mat/AdvancedRasterization.cpp

## AdvancedRasterization.cpp
// Advanced Rasterization by Nicolas "Nick" Capens - Devmaster Forum
// https://web.archive.org/web/20141221050705/http://forum.devmaster.net/t/advanced-rasterization/6145
//
// Result : https://godbolt.org/z/rzvzzf3cc

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdint>

const uint8_t black = '.';
const uint8_t white = 'W';
const uint8_t blue  = '*';

struct Vertex {
    float x, y;
};

template <typename T> T min3(T a, T b, T c) {
    return std::min(a, std::min(b, c));
}

template <typename T> T max3(T a, T b, T c) {
    return std::max(a, std::max(b, c));
}

int iround(float a) {
    return static_cast<int>(std::roundf(a));
}

// This is the simplest working implementation of the half-space functions algorithm.
// Unfortunately, this implementation isn't fast at all. For every pixel, six multiplications and no less than fifteen
// subtractions are required.
void drawTriangle0(uint8_t      *buf,
                   int           width,
                   int           height,
                   int           bytesPerPixel,
                   int           stride,
                   const Vertex &v1,
                   const Vertex &v2,
                   const Vertex &v3) {
    const float y1 = (float)v1.y;
    const float y2 = (float)v2.y;
    const float y3 = (float)v3.y;

    const float x1 = (float)v1.x;
    const float x2 = (float)v2.x;
    const float x3 = (float)v3.x;

    // Bounding rectangle
    const int minx = (int)min3(x1, x2, x3);
    const int maxx = (int)max3(x1, x2, x3);
    const int miny = (int)min3(y1, y2, y3);
    const int maxy = (int)max3(y1, y2, y3);

    auto colorBuffer = buf + miny * stride;

    // Scan through bounding rectangle
    for (int y = miny; y < maxy; ++y) {
        for (int x = minx; x < maxx; ++x) {
            // When all half-space functions positive, pixel is in triangle
            if ((x1 - x2) * (y - y1) - (y1 - y2) * (x - x1) > 0 && //
                (x2 - x3) * (y - y2) - (y2 - y3) * (x - x2) > 0 && //
                (x3 - x1) * (y - y3) - (y3 - y1) * (x - x3) > 0    //
            ) {
                colorBuffer[x] = white;
            }
        }

        colorBuffer += stride;
    }
}

// Per horizontal line that we scan, only the x component in the formula changes.
// Also for stepping in the y direction it's just an addition of a constant.
void drawTriangle1(uint8_t      *buf,
                   int           width,
                   int           height,
                   int           bytesPerPixel,
                   int           stride,
                   const Vertex &v1,
                   const Vertex &v2,
                   const Vertex &v3) {
    const float y1 = (float)v1.y;
    const float y2 = (float)v2.y;
    const float y3 = (float)v3.y;

    const float x1 = (float)v1.x;
    const float x2 = (float)v2.x;
    const float x3 = (float)v3.x;

    // Deltas
    const float Dx12 = x1 - x2;
    const float Dx23 = x2 - x3;
    const float Dx31 = x3 - x1;

    const float Dy12 = y1 - y2;
    const float Dy23 = y2 - y3;
    const float Dy31 = y3 - y1;

    // Bounding rectangle
    const int minx = (int)min3(x1, x2, x3);
    const int maxx = (int)max3(x1, x2, x3);
    const int miny = (int)min3(y1, y2, y3);
    const int maxy = (int)max3(y1, y2, y3);

    auto colorBuffer = buf + miny * stride;

    // Constant part of half-edge functions
    const float C1 = Dy12 * x1 - Dx12 * y1;
    const float C2 = Dy23 * x2 - Dx23 * y2;
    const float C3 = Dy31 * x3 - Dx31 * y3;

    float Cy1 = C1 + Dx12 * miny - Dy12 * minx;
    float Cy2 = C2 + Dx23 * miny - Dy23 * minx;
    float Cy3 = C3 + Dx31 * miny - Dy31 * minx;

    // Scan through bounding rectangle
    for (int y = miny; y < maxy; ++y) {
        // Start value for horizontal scan
        float Cx1 = Cy1;
        float Cx2 = Cy2;
        float Cx3 = Cy3;

        for (int x = minx; x < maxx; ++y) {
            if (Cx1 > 0 && Cx2 > 0 && Cx3 > 0) {
                colorBuffer[x] = white;
            }

            Cx1 -= Dy12;
            Cx2 -= Dy23;
            Cx3 -= Dy31;
        }

        Cy1 += Dx12;
        Cy2 += Dx23;
        Cy3 += Dx31;

        colorBuffer += stride;
    }
}

// The real solution might sound crazy: use integers!
// What we'll use here is a top-left fill convention, just like DirectX and OpenGL.
void drawTriangle2(uint8_t      *buf,
                   int           width,
                   int           height,
                   int           bytesPerPixel,
                   int           stride,
                   const Vertex &v1,
                   const Vertex &v2,
                   const Vertex &v3) {
    // 28.4 fixed-point coordinates
    const int Y1 = iround(16.0f * v1.y);
    const int Y2 = iround(16.0f * v2.y);
    const int Y3 = iround(16.0f * v3.y);

    const int X1 = iround(16.0f * v1.x);
    const int X2 = iround(16.0f * v2.x);
    const int X3 = iround(16.0f * v3.x);

    // Deltas
    const int DX12 = X1 - X2;
    const int DX23 = X2 - X3;
    const int DX31 = X3 - X1;

    const int DY12 = Y1 - Y2;
    const int DY23 = Y2 - Y3;
    const int DY31 = Y3 - Y1;

    // Fixed-point deltas
    const int FDX12 = DX12 << 4;
    const int FDX23 = DX23 << 4;
    const int FDX31 = DX31 << 4;

    const int FDY12 = DY12 << 4;
    const int FDY23 = DY23 << 4;
    const int FDY31 = DY31 << 4;

    // Bounding rectangle
    const int minx = (min3(X1, X2, X3) + 0xF) >> 4;
    const int maxx = (max3(X1, X2, X3) + 0xF) >> 4;
    const int miny = (min3(Y1, Y2, Y3) + 0xF) >> 4;
    const int maxy = (max3(Y1, Y2, Y3) + 0xF) >> 4;

    auto colorBuffer = buf + miny * stride;

    // Correct for fill convention
    const int O1 = (DY12 < 0 || (DY12 == 0 && DX12 > 0)) ? 1 : 0;
    const int O2 = (DY23 < 0 || (DY23 == 0 && DX23 > 0)) ? 1 : 0;
    const int O3 = (DY31 < 0 || (DY31 == 0 && DX31 > 0)) ? 1 : 0;

    // Half-edge constants
    const int C1 = DY12 * X1 - DX12 * Y1 + O1;
    const int C2 = DY23 * X2 - DX23 * Y2 + O2;
    const int C3 = DY31 * X3 - DX31 * Y3 + O3;

    {
        int CY1 = C1 + DX12 * (miny << 4) - DY12 * (minx << 4);
        int CY2 = C2 + DX23 * (miny << 4) - DY23 * (minx << 4);
        int CY3 = C3 + DX31 * (miny << 4) - DY31 * (minx << 4);

        for (int y = miny; y < maxy; ++y) {
            int CX1 = CY1;
            int CX2 = CY2;
            int CX3 = CY3;

            for (int x = minx; x < maxx; ++x) {
                if (CX1 > 0 && CX2 > 0 && CX3 > 0) {
                    colorBuffer[x] = white;
                }

                CX1 -= FDY12;
                CX2 -= FDY23;
                CX3 -= FDY31;
            }

            CY1 += FDX12;
            CY2 += FDX23;
            CY3 += FDX31;

            colorBuffer += stride;
        }
    }
}

void drawTriangle3(uint8_t      *buf,
                   int           width,
                   int           height,
                   int           bytesPerPixel,
                   int           stride,
                   const Vertex &v1,
                   const Vertex &v2,
                   const Vertex &v3) {
    // Block size, standard 8x8 (must be power of two)
    //  const int q = 8;    // Original code
    const int q = 4; // For testing on terminal.

    // Start in corner of 8x8 block
    const int minMask = ~(q - 1);

    // 28.4 fixed-point coordinates
    const int Y1 = iround(16.0f * v1.y);
    const int Y2 = iround(16.0f * v2.y);
    const int Y3 = iround(16.0f * v3.y);

    const int X1 = iround(16.0f * v1.x);
    const int X2 = iround(16.0f * v2.x);
    const int X3 = iround(16.0f * v3.x);

    // Deltas
    const int DX12 = X1 - X2;
    const int DX23 = X2 - X3;
    const int DX31 = X3 - X1;

    const int DY12 = Y1 - Y2;
    const int DY23 = Y2 - Y3;
    const int DY31 = Y3 - Y1;

    // Fixed-point deltas
    const int FDX12 = DX12 << 4;
    const int FDX23 = DX23 << 4;
    const int FDX31 = DX31 << 4;

    const int FDY12 = DY12 << 4;
    const int FDY23 = DY23 << 4;
    const int FDY31 = DY31 << 4;

    // Bounding rectangle
    const int minx = ((min3(X1, X2, X3) + 0xF) >> 4) & minMask; // Start in corner of 8x8 block
    const int maxx = ((max3(X1, X2, X3) + 0xF) >> 4);
    const int miny = ((min3(Y1, Y2, Y3) + 0xF) >> 4) & minMask; // Start in corner of 8x8 block
    const int maxy = ((max3(Y1, Y2, Y3) + 0xF) >> 4);

    auto colorBuffer = buf + miny * stride;

    // Correct for fill convention
    const int O1 = (DY12 < 0 || (DY12 == 0 && DX12 > 0)) ? 1 : 0;
    const int O2 = (DY23 < 0 || (DY23 == 0 && DX23 > 0)) ? 1 : 0;
    const int O3 = (DY31 < 0 || (DY31 == 0 && DX31 > 0)) ? 1 : 0;

    // Half-edge constants
    const int C1 = DY12 * X1 - DX12 * Y1 + O1;
    const int C2 = DY23 * X2 - DX23 * Y2 + O2;
    const int C3 = DY31 * X3 - DX31 * Y3 + O3;

    // Loop through blocks
    for (int y = miny; y < maxy; y += q) {
        for (int x = minx; x < maxx; x += q) {
            // Corners of block
            const int x0 = x << 4;
            const int x1 = (x + q - 1) << 4;
            const int y0 = y << 4;
            const int y1 = (y + q - 1) << 4;

            // Evaluate half-space functions
            const bool a00 = C1 + DX12 * y0 - DY12 * x0 > 0;
            const bool a10 = C1 + DX12 * y0 - DY12 * x1 > 0;
            const bool a01 = C1 + DX12 * y1 - DY12 * x0 > 0;
            const bool a11 = C1 + DX12 * y1 - DY12 * x1 > 0;
            const int  a   = (a00 << 0) | (a10 << 1) | (a01 << 2) | (a11 << 3);

            const bool b00 = C2 + DX23 * y0 - DY23 * x0 > 0;
            const bool b10 = C2 + DX23 * y0 - DY23 * x1 > 0;
            const bool b01 = C2 + DX23 * y1 - DY23 * x0 > 0;
            const bool b11 = C2 + DX23 * y1 - DY23 * x1 > 0;
            const int  b   = (b00 << 0) | (b10 << 1) | (b01 << 2) | (b11 << 3);

            const bool c00 = C3 + DX31 * y0 - DY31 * x0 > 0;
            const bool c10 = C3 + DX31 * y0 - DY31 * x1 > 0;
            const bool c01 = C3 + DX31 * y1 - DY31 * x0 > 0;
            const bool c11 = C3 + DX31 * y1 - DY31 * x1 > 0;
            const int  c   = (c00 << 0) | (c10 << 1) | (c01 << 2) | (c11 << 3);

            // Skip block when outside an edge
            if (a == 0x0 || b == 0x0 || c == 0x0) {
                continue;
            }

            auto buffer = colorBuffer;

            // Accept whole block when totally covered
            if (a == 0xF && b == 0xF && c == 0xF) {
                for (int iy = 0; iy < q; ++iy) {
                    for (int ix = x; ix < x + q; ++ix) {
                        buffer[ix] = white;
                    }

                    buffer += stride;
                }
            } else // Partially covered block
            {
                int CY1 = C1 + DX12 * y0 - DY12 * x0;
                int CY2 = C2 + DX23 * y0 - DY23 * x0;
                int CY3 = C3 + DX31 * y0 - DY31 * x0;

                for (int iy = y; iy < y + q; ++iy) {
                    int CX1 = CY1;
                    int CX2 = CY2;
                    int CX3 = CY3;

                    for (int ix = x; ix < x + q; ++ix) {
                        if (CX1 > 0 && CX2 > 0 && CX3 > 0) {
                            buffer[ix] = blue;
                        }

                        CX1 -= FDY12;
                        CX2 -= FDY23;
                        CX3 -= FDY31;
                    }

                    CY1 += FDX12;
                    CY2 += FDX23;
                    CY3 += FDX31;

                    buffer += stride;
                }
            }
        }

        colorBuffer += q * stride;
    }
}

int main(int argc, const char *argv[]) {
    int method = 3;

    if (argc > 2) {
        method = atoi(argv[1]);
    }

    const int width         = 32;
    const int height        = 16;
    const int bytesPerPixel = (int)sizeof(uint8_t);
    const int stride        = bytesPerPixel * width;

    std::vector<uint8_t> linearBuf(stride * height);

    for(auto& c : linearBuf) {
        c = black;
    }

    Vertex v1 = {width / 2, 1};
    Vertex v2 = {1, height / 2};
    Vertex v3 = {width * 2 / 3, height - 1};

    switch (method) {
    case 0:
        drawTriangle0(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
        break;
    case 1:
        drawTriangle1(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
        break;
    case 2:
        drawTriangle2(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
        break;
    default:
    case 3:
        drawTriangle3(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
        break;
    }

    printf("method = %d\n", method);
    printf("|");
    for (int x = 0; x < width; ++x) {
        printf("-");
    }
    printf("|\n");

    for (int y = 0; y < height; ++y) {
        printf("|");
        for (int x = 0; x < width; ++x) {
            printf("%c", linearBuf[(y * width) + x]);
        }
        printf("|\n");
    }

    printf("|");
    for (int x = 0; x < width; ++x) {
        printf("-");
    }
    printf("|\n");
}
	// Advanced Rasterization by Nicolas "Nick" Capens - Devmaster Forum
	// https://web.archive.org/web/20141221050705/http://forum.devmaster.net/t/advanced-rasterization/6145
	//
	// Result : https://godbolt.org/z/rzvzzf3cc

	#include <stdio.h>
	#include <algorithm>
	#include <vector>
	#include <cmath>
	#include <cstdint>

	const uint8_t black = '.';
	const uint8_t white = 'W';
	const uint8_t blue = '*';

	struct Vertex {
	float x, y;
	};

	template <typename T> T min3(T a, T b, T c) {
	return std::min(a, std::min(b, c));
	}

	template <typename T> T max3(T a, T b, T c) {
	return std::max(a, std::max(b, c));
	}

	int iround(float a) {
	return static_cast<int>(std::roundf(a));
	}

	// This is the simplest working implementation of the half-space functions algorithm.
	// Unfortunately, this implementation isn't fast at all. For every pixel, six multiplications and no less than fifteen
	// subtractions are required.
	void drawTriangle0(uint8_t *buf,
	int width,
	int height,
	int bytesPerPixel,
	int stride,
	const Vertex &v1,
	const Vertex &v2,
	const Vertex &v3) {
	const float y1 = (float)v1.y;
	const float y2 = (float)v2.y;
	const float y3 = (float)v3.y;

	const float x1 = (float)v1.x;
	const float x2 = (float)v2.x;
	const float x3 = (float)v3.x;

	// Bounding rectangle
	const int minx = (int)min3(x1, x2, x3);
	const int maxx = (int)max3(x1, x2, x3);
	const int miny = (int)min3(y1, y2, y3);
	const int maxy = (int)max3(y1, y2, y3);

	auto colorBuffer = buf + miny * stride;

	// Scan through bounding rectangle
	for (int y = miny; y < maxy; ++y) {
	for (int x = minx; x < maxx; ++x) {
	// When all half-space functions positive, pixel is in triangle
	if ((x1 - x2) * (y - y1) - (y1 - y2) * (x - x1) > 0 && //
	(x2 - x3) * (y - y2) - (y2 - y3) * (x - x2) > 0 && //
	(x3 - x1) * (y - y3) - (y3 - y1) * (x - x3) > 0 //
	) {
	colorBuffer[x] = white;
	}
	}

	colorBuffer += stride;
	}
	}

	// Per horizontal line that we scan, only the x component in the formula changes.
	// Also for stepping in the y direction it's just an addition of a constant.
	void drawTriangle1(uint8_t *buf,
	int width,
	int height,
	int bytesPerPixel,
	int stride,
	const Vertex &v1,
	const Vertex &v2,
	const Vertex &v3) {
	const float y1 = (float)v1.y;
	const float y2 = (float)v2.y;
	const float y3 = (float)v3.y;

	const float x1 = (float)v1.x;
	const float x2 = (float)v2.x;
	const float x3 = (float)v3.x;

	// Deltas
	const float Dx12 = x1 - x2;
	const float Dx23 = x2 - x3;
	const float Dx31 = x3 - x1;

	const float Dy12 = y1 - y2;
	const float Dy23 = y2 - y3;
	const float Dy31 = y3 - y1;

	// Bounding rectangle
	const int minx = (int)min3(x1, x2, x3);
	const int maxx = (int)max3(x1, x2, x3);
	const int miny = (int)min3(y1, y2, y3);
	const int maxy = (int)max3(y1, y2, y3);

	auto colorBuffer = buf + miny * stride;

	// Constant part of half-edge functions
	const float C1 = Dy12 * x1 - Dx12 * y1;
	const float C2 = Dy23 * x2 - Dx23 * y2;
	const float C3 = Dy31 * x3 - Dx31 * y3;

	float Cy1 = C1 + Dx12 * miny - Dy12 * minx;
	float Cy2 = C2 + Dx23 * miny - Dy23 * minx;
	float Cy3 = C3 + Dx31 * miny - Dy31 * minx;

	// Scan through bounding rectangle
	for (int y = miny; y < maxy; ++y) {
	// Start value for horizontal scan
	float Cx1 = Cy1;
	float Cx2 = Cy2;
	float Cx3 = Cy3;

	for (int x = minx; x < maxx; ++y) {
	if (Cx1 > 0 && Cx2 > 0 && Cx3 > 0) {
	colorBuffer[x] = white;
	}

	Cx1 -= Dy12;
	Cx2 -= Dy23;
	Cx3 -= Dy31;
	}

	Cy1 += Dx12;
	Cy2 += Dx23;
	Cy3 += Dx31;

	colorBuffer += stride;
	}
	}

	// The real solution might sound crazy: use integers!
	// What we'll use here is a top-left fill convention, just like DirectX and OpenGL.
	void drawTriangle2(uint8_t *buf,
	int width,
	int height,
	int bytesPerPixel,
	int stride,
	const Vertex &v1,
	const Vertex &v2,
	const Vertex &v3) {
	// 28.4 fixed-point coordinates
	const int Y1 = iround(16.0f * v1.y);
	const int Y2 = iround(16.0f * v2.y);
	const int Y3 = iround(16.0f * v3.y);

	const int X1 = iround(16.0f * v1.x);
	const int X2 = iround(16.0f * v2.x);
	const int X3 = iround(16.0f * v3.x);

	// Deltas
	const int DX12 = X1 - X2;
	const int DX23 = X2 - X3;
	const int DX31 = X3 - X1;

	const int DY12 = Y1 - Y2;
	const int DY23 = Y2 - Y3;
	const int DY31 = Y3 - Y1;

	// Fixed-point deltas
	const int FDX12 = DX12 << 4;
	const int FDX23 = DX23 << 4;
	const int FDX31 = DX31 << 4;

	const int FDY12 = DY12 << 4;
	const int FDY23 = DY23 << 4;
	const int FDY31 = DY31 << 4;

	// Bounding rectangle
	const int minx = (min3(X1, X2, X3) + 0xF) >> 4;
	const int maxx = (max3(X1, X2, X3) + 0xF) >> 4;
	const int miny = (min3(Y1, Y2, Y3) + 0xF) >> 4;
	const int maxy = (max3(Y1, Y2, Y3) + 0xF) >> 4;

	auto colorBuffer = buf + miny * stride;

	// Correct for fill convention
	const int O1 = (DY12 < 0 \|\| (DY12 == 0 && DX12 > 0)) ? 1 : 0;
	const int O2 = (DY23 < 0 \|\| (DY23 == 0 && DX23 > 0)) ? 1 : 0;
	const int O3 = (DY31 < 0 \|\| (DY31 == 0 && DX31 > 0)) ? 1 : 0;

	// Half-edge constants
	const int C1 = DY12 * X1 - DX12 * Y1 + O1;
	const int C2 = DY23 * X2 - DX23 * Y2 + O2;
	const int C3 = DY31 * X3 - DX31 * Y3 + O3;

	{
	int CY1 = C1 + DX12 * (miny << 4) - DY12 * (minx << 4);
	int CY2 = C2 + DX23 * (miny << 4) - DY23 * (minx << 4);
	int CY3 = C3 + DX31 * (miny << 4) - DY31 * (minx << 4);

	for (int y = miny; y < maxy; ++y) {
	int CX1 = CY1;
	int CX2 = CY2;
	int CX3 = CY3;

	for (int x = minx; x < maxx; ++x) {
	if (CX1 > 0 && CX2 > 0 && CX3 > 0) {
	colorBuffer[x] = white;
	}

	CX1 -= FDY12;
	CX2 -= FDY23;
	CX3 -= FDY31;
	}

	CY1 += FDX12;
	CY2 += FDX23;
	CY3 += FDX31;

	colorBuffer += stride;
	}
	}
	}

	void drawTriangle3(uint8_t *buf,
	int width,
	int height,
	int bytesPerPixel,
	int stride,
	const Vertex &v1,
	const Vertex &v2,
	const Vertex &v3) {
	// Block size, standard 8x8 (must be power of two)
	// const int q = 8; // Original code
	const int q = 4; // For testing on terminal.

	// Start in corner of 8x8 block
	const int minMask = ~(q - 1);

	// 28.4 fixed-point coordinates
	const int Y1 = iround(16.0f * v1.y);
	const int Y2 = iround(16.0f * v2.y);
	const int Y3 = iround(16.0f * v3.y);

	const int X1 = iround(16.0f * v1.x);
	const int X2 = iround(16.0f * v2.x);
	const int X3 = iround(16.0f * v3.x);

	// Deltas
	const int DX12 = X1 - X2;
	const int DX23 = X2 - X3;
	const int DX31 = X3 - X1;

	const int DY12 = Y1 - Y2;
	const int DY23 = Y2 - Y3;
	const int DY31 = Y3 - Y1;

	// Fixed-point deltas
	const int FDX12 = DX12 << 4;
	const int FDX23 = DX23 << 4;
	const int FDX31 = DX31 << 4;

	const int FDY12 = DY12 << 4;
	const int FDY23 = DY23 << 4;
	const int FDY31 = DY31 << 4;

	// Bounding rectangle
	const int minx = ((min3(X1, X2, X3) + 0xF) >> 4) & minMask; // Start in corner of 8x8 block
	const int maxx = ((max3(X1, X2, X3) + 0xF) >> 4);
	const int miny = ((min3(Y1, Y2, Y3) + 0xF) >> 4) & minMask; // Start in corner of 8x8 block
	const int maxy = ((max3(Y1, Y2, Y3) + 0xF) >> 4);

	auto colorBuffer = buf + miny * stride;

	// Correct for fill convention
	const int O1 = (DY12 < 0 \|\| (DY12 == 0 && DX12 > 0)) ? 1 : 0;
	const int O2 = (DY23 < 0 \|\| (DY23 == 0 && DX23 > 0)) ? 1 : 0;
	const int O3 = (DY31 < 0 \|\| (DY31 == 0 && DX31 > 0)) ? 1 : 0;

	// Half-edge constants
	const int C1 = DY12 * X1 - DX12 * Y1 + O1;
	const int C2 = DY23 * X2 - DX23 * Y2 + O2;
	const int C3 = DY31 * X3 - DX31 * Y3 + O3;

	// Loop through blocks
	for (int y = miny; y < maxy; y += q) {
	for (int x = minx; x < maxx; x += q) {
	// Corners of block
	const int x0 = x << 4;
	const int x1 = (x + q - 1) << 4;
	const int y0 = y << 4;
	const int y1 = (y + q - 1) << 4;

	// Evaluate half-space functions
	const bool a00 = C1 + DX12 * y0 - DY12 * x0 > 0;
	const bool a10 = C1 + DX12 * y0 - DY12 * x1 > 0;
	const bool a01 = C1 + DX12 * y1 - DY12 * x0 > 0;
	const bool a11 = C1 + DX12 * y1 - DY12 * x1 > 0;
	const int a = (a00 << 0) \| (a10 << 1) \| (a01 << 2) \| (a11 << 3);

	const bool b00 = C2 + DX23 * y0 - DY23 * x0 > 0;
	const bool b10 = C2 + DX23 * y0 - DY23 * x1 > 0;
	const bool b01 = C2 + DX23 * y1 - DY23 * x0 > 0;
	const bool b11 = C2 + DX23 * y1 - DY23 * x1 > 0;
	const int b = (b00 << 0) \| (b10 << 1) \| (b01 << 2) \| (b11 << 3);

	const bool c00 = C3 + DX31 * y0 - DY31 * x0 > 0;
	const bool c10 = C3 + DX31 * y0 - DY31 * x1 > 0;
	const bool c01 = C3 + DX31 * y1 - DY31 * x0 > 0;
	const bool c11 = C3 + DX31 * y1 - DY31 * x1 > 0;
	const int c = (c00 << 0) \| (c10 << 1) \| (c01 << 2) \| (c11 << 3);

	// Skip block when outside an edge
	if (a == 0x0 \|\| b == 0x0 \|\| c == 0x0) {
	continue;
	}

	auto buffer = colorBuffer;

	// Accept whole block when totally covered
	if (a == 0xF && b == 0xF && c == 0xF) {
	for (int iy = 0; iy < q; ++iy) {
	for (int ix = x; ix < x + q; ++ix) {
	buffer[ix] = white;
	}

	buffer += stride;
	}
	} else // Partially covered block
	{
	int CY1 = C1 + DX12 * y0 - DY12 * x0;
	int CY2 = C2 + DX23 * y0 - DY23 * x0;
	int CY3 = C3 + DX31 * y0 - DY31 * x0;

	for (int iy = y; iy < y + q; ++iy) {
	int CX1 = CY1;
	int CX2 = CY2;
	int CX3 = CY3;

	for (int ix = x; ix < x + q; ++ix) {
	if (CX1 > 0 && CX2 > 0 && CX3 > 0) {
	buffer[ix] = blue;
	}

	CX1 -= FDY12;
	CX2 -= FDY23;
	CX3 -= FDY31;
	}

	CY1 += FDX12;
	CY2 += FDX23;
	CY3 += FDX31;

	buffer += stride;
	}
	}
	}

	colorBuffer += q * stride;
	}
	}

	int main(int argc, const char *argv[]) {
	int method = 3;

	if (argc > 2) {
	method = atoi(argv[1]);
	}

	const int width = 32;
	const int height = 16;
	const int bytesPerPixel = (int)sizeof(uint8_t);
	const int stride = bytesPerPixel * width;

	std::vector<uint8_t> linearBuf(stride * height);

	for(auto& c : linearBuf) {
	c = black;
	}

	Vertex v1 = {width / 2, 1};
	Vertex v2 = {1, height / 2};
	Vertex v3 = {width * 2 / 3, height - 1};

	switch (method) {
	case 0:
	drawTriangle0(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
	break;
	case 1:
	drawTriangle1(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
	break;
	case 2:
	drawTriangle2(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
	break;
	default:
	case 3:
	drawTriangle3(linearBuf.data(), width, height, bytesPerPixel, stride, v1, v2, v3);
	break;
	}

	printf("method = %d\n", method);
	printf("\|");
	for (int x = 0; x < width; ++x) {
	printf("-");
	}
	printf("\|\n");

	for (int y = 0; y < height; ++y) {
	printf("\|");
	for (int x = 0; x < width; ++x) {
	printf("%c", linearBuf[(y * width) + x]);
	}
	printf("\|\n");
	}

	printf("\|");
	for (int x = 0; x < width; ++x) {
	printf("-");
	}
	printf("\|\n");
	}