PolygonRasterizer

main.cpp

#pragma warning(disable : 28251)
#pragma warning(disable : 28159)

#define DPI_AWARE 0

#define WINDOW_TITLE L"Win32 Window"
#define WINDOW_CLASS L"FontDemo"

#pragma comment(lib, "Shcore.lib")
#pragma comment( linker, "/subsystem:console" )

#include <windows.h>
#include <iostream>
#include <ShellScalingAPI.h>

#include "RasterPolygon.h"
#include "PolyRasterV0.h"
#include "PolyRasterV1.h"
#include "PolyRasterV2.h"

#if _DEBUG
#include <crtdbg.h>
#endif

BITMAPINFO gFrameBufferInfo;
u8* gFrameBufferRGBA = 0;
u32 gFrameBufferWidth = 0;
u32 gFrameBufferHeight = 0;
u32 gDPIValue;
f32 gDPIScale;

#define MAKE_PATH(shape) \
	shape.StartPath();  \
	shape.AddPoint(400, 0);  \
	shape.AddPoint(800, 600);  \
	shape.AddPoint(0, 200);  \
	shape.AddPoint(800, 200);  \
	shape.AddPoint(0, 600);

void DrawFrame() {
	static Rasterizer::PolygonV0 poly0;
	static Rasterizer::PolygonV1 poly1;
	static Rasterizer::PolygonV2 poly2;
	Rasterizer::PolygonV0::Image img0;
	Rasterizer::PolygonV1::Image img1;
	Rasterizer::PolygonV2::Image img2;
	img0.bits = img1.bits = img2.bits = gFrameBufferRGBA;
	img0.width = img1.width = img2.width = gFrameBufferWidth;
	img0.height = img1.height = img2.height = gFrameBufferHeight;
	img0.components = img1.components = img2.components = 4;

	MAKE_PATH(poly0);
	MAKE_PATH(poly1);
	MAKE_PATH(poly2);
	
	LARGE_INTEGER timerStart = { 0 };
	LARGE_INTEGER timerStop = { 0 };

	LARGE_INTEGER timerFrequency;
	if (!QueryPerformanceFrequency(&timerFrequency)) {
		std::cout << "WinMain: QueryPerformanceFrequency failed\n";
	}
	else {
#if 0
		QueryPerformanceCounter(&timerStart);
		poly0.FillPath(img0, Rasterizer::PolygonV0::Color{ 255, 100, 100 });
		poly0.FillPath(img0, Rasterizer::PolygonV0::Color{ 100, 255, 100 });
		poly0.FillPath(img0, Rasterizer::PolygonV0::Color{ 100, 100, 255 });
		QueryPerformanceCounter(&timerStop);

		LONGLONG timerDiff = timerStop.QuadPart - timerStart.QuadPart;
		double ms = (double)timerDiff * 1000.0 / (double)timerFrequency.QuadPart;
		std::cout << "Poly V0: " << ms << " ms\n";
#endif

#if 0
		QueryPerformanceCounter(&timerStart);
		poly1.FillPath(img1, Rasterizer::PolygonV1::Color{ 255, 100, 100 });
		poly1.FillPath(img1, Rasterizer::PolygonV1::Color{ 100, 255, 100 });
		poly1.FillPath(img1, Rasterizer::PolygonV1::Color{ 100, 100, 255 });
		QueryPerformanceCounter(&timerStop);

		LONGLONG timerDiff1 = timerStop.QuadPart - timerStart.QuadPart;
		double ms1 = (double)timerDiff1 * 1000.0 / (double)timerFrequency.QuadPart;
		std::cout << "Poly V1: " << ms1 << " ms\n";
#endif

#if 1
		QueryPerformanceCounter(&timerStart);
		poly2.FillPath(img2, Rasterizer::PolygonV2::Color{ 255, 100, 100 });
		poly2.FillPath(img2, Rasterizer::PolygonV2::Color{ 100, 255, 100 });
		poly2.FillPath(img2, Rasterizer::PolygonV2::Color{ 100, 100, 255 });
		QueryPerformanceCounter(&timerStop);

		LONGLONG timerDiff2 = timerStop.QuadPart - timerStart.QuadPart;
		double ms2 = (double)timerDiff2 * 1000.0 / (double)timerFrequency.QuadPart;
		std::cout << "Poly V2: " << ms2 << " ms\n";
#endif
	}
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int iCmdShow);
LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam, LPARAM lParam);

int main(int argc, const char** argv) {
#if _DEBUG
	_CrtSetReportMode(_CRT_ASSERT, _CRTDBG_MODE_DEBUG);
#endif
	WinMain(GetModuleHandle(NULL), NULL, GetCommandLineA(), SW_SHOWDEFAULT);
	return 0;
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int iCmdShow) {
	HRESULT hr = SetProcessDpiAwareness(PROCESS_PER_MONITOR_DPI_AWARE);

	WNDCLASSEX wndclass;
	wndclass.cbSize = sizeof(WNDCLASSEX);
	wndclass.style = CS_HREDRAW | CS_VREDRAW;
	wndclass.lpfnWndProc = WndProc;
	wndclass.cbClsExtra = 0;
	wndclass.cbWndExtra = 0;
	wndclass.hInstance = hInstance;
	wndclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
	wndclass.hIconSm = LoadIcon(NULL, IDI_APPLICATION);
	wndclass.hCursor = LoadCursor(NULL, IDC_ARROW);
	wndclass.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
	wndclass.lpszMenuName = 0;
	wndclass.lpszClassName = WINDOW_CLASS;
	RegisterClassEx(&wndclass);

	int screenWidth = GetSystemMetrics(SM_CXSCREEN);
	int screenHeight = GetSystemMetrics(SM_CYSCREEN);

	int clientWidth = 800;
	int clientHeight = 600;

	gDPIValue = GetDpiForSystem();
	gDPIScale = (float)gDPIValue / 96.0f;
	std::cout << "DPI: " << gDPIValue << ", scale: " << gDPIScale << "\n";

	clientWidth = (int)((float)clientWidth * gDPIScale);
	clientHeight = (int)((float)clientHeight * gDPIScale);

	RECT windowRect;
	SetRect(&windowRect, (screenWidth / 2) - (clientWidth / 2), (screenHeight / 2) - (clientHeight / 2), (screenWidth / 2) + (clientWidth / 2), (screenHeight / 2) + (clientHeight / 2));

	DWORD style = (WS_OVERLAPPED | WS_CAPTION | WS_SYSMENU);
	AdjustWindowRectEx(&windowRect, style, FALSE, 0);

	HWND hwnd = CreateWindowEx(0, wndclass.lpszClassName, WINDOW_TITLE, style, windowRect.left, windowRect.top, windowRect.right - windowRect.left, windowRect.bottom - windowRect.top, NULL, NULL, hInstance, szCmdLine);

	gFrameBufferInfo.bmiHeader.biSize = sizeof(gFrameBufferInfo.bmiHeader);
	gFrameBufferInfo.bmiHeader.biWidth = clientWidth;
	gFrameBufferInfo.bmiHeader.biHeight = -clientHeight;
	gFrameBufferInfo.bmiHeader.biPlanes = 1;
	gFrameBufferInfo.bmiHeader.biBitCount = 32;
	gFrameBufferInfo.bmiHeader.biCompression = BI_RGB;

	gFrameBufferWidth = clientWidth;
	gFrameBufferHeight = clientHeight;

	int bitmapMemorySize = (gFrameBufferWidth * gFrameBufferHeight) * 4;
	gFrameBufferRGBA = (unsigned char*)VirtualAlloc(0, bitmapMemorySize, MEM_COMMIT, PAGE_READWRITE);
	memset(gFrameBufferRGBA, (125) | (125 << 8) | (125 << 16) | (255 << 24), bitmapMemorySize);

	ShowWindow(hwnd, SW_SHOW);
	UpdateWindow(hwnd);

	MSG msg;
	while (GetMessage(&msg, NULL, 0, 0) > 0) {
		TranslateMessage(&msg);
		DispatchMessage(&msg);
	}

	VirtualFree(gFrameBufferRGBA, 0, MEM_RELEASE);
	return (int)msg.wParam;
}

LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam, LPARAM lParam) {
	switch (iMsg) {
	case WM_CREATE:
		break;
	case WM_CLOSE:
		DestroyWindow(hwnd);
		break;
	case WM_DESTROY:
		PostQuitMessage(0);
		break;
	case WM_PAINT:
	{
		i32 bitmapMemorySize = (gFrameBufferWidth * gFrameBufferHeight) * 4;
		memset(gFrameBufferRGBA, (125) | (125 << 8) | (125 << 16) | (255 << 24), bitmapMemorySize);
		DrawFrame();


		PAINTSTRUCT ps;
		RECT clientRect;

		HDC hdc = BeginPaint(hwnd, &ps);

		GetClientRect(hwnd, &clientRect);
		i32 clientWidth = clientRect.right - clientRect.left;
		i32 clientHeight = clientRect.bottom - clientRect.top;

		StretchDIBits(hdc,
			0, 0, clientWidth, clientHeight,
			0, 0, gFrameBufferWidth, gFrameBufferHeight,
			gFrameBufferRGBA, &gFrameBufferInfo,
			DIB_RGB_COLORS, SRCCOPY);

		EndPaint(hwnd, &ps);

		return 0;
	}
	break;
	case WM_ERASEBKGND:
		return 0;
	}

	return DefWindowProc(hwnd, iMsg, wParam, lParam);
}

void DrawPixel(i32 x, i32 y, u8 r, u8 g, u8 b) {
	if (x < 0 || x >= gFrameBufferWidth || y < 0 || y >= gFrameBufferHeight) {
		return;
	}
	i32 pixel = (y * gFrameBufferWidth + x) * 4;
	gFrameBufferRGBA[pixel + 0] = b;
	gFrameBufferRGBA[pixel + 1] = g;
	gFrameBufferRGBA[pixel + 2] = r;
	gFrameBufferRGBA[pixel + 3] = 255;
}

void DrawPoint(i32 x, i32 y, u8 r, u8 g, u8 b) {
	DrawPixel(x + 0, y, r, g, b);
	DrawPixel(x - 1, y, r, g, b);
	DrawPixel(x + 1, y, r, g, b);
	DrawPixel(x + 2, y, r, g, b);

	DrawPixel(x + 0, y - 1, r, g, b);
	DrawPixel(x - 1, y - 1, r, g, b);
	DrawPixel(x + 1, y - 1, r, g, b);
	DrawPixel(x + 2, y - 1, r, g, b);

	DrawPixel(x + 0, y + 1, r, g, b);
	DrawPixel(x + 1, y + 1, r, g, b);

	DrawPixel(x + 0, y - 2, r, g, b);
	DrawPixel(x + 1, y - 2, r, g, b);
}

void DrawLine(i32 x0, i32 y0, i32 x1, i32 y1, u8 r, u8 g, u8 b) {
	i32 dx = abs(x1 - x0);
	i32 dy = abs(y1 - y0);

	i32 xStep = x0 < x1 ? 1 : -1;
	i32 yStep = y0 < y1 ? 1 : -1;

	i32 error = 0;

	if (dx > dy) {
		i32 m = 2 * dy;
		i32 scale = 2 * dx;
		for (i32 x = x0, y = y0; x != x1 + xStep; x += xStep) {
			DrawPixel(x, y, r, g, b);

			error += m;
			if (error >= dx) {
				y += yStep;
				error -= scale;
			}
		}
	}
	else {
		i32 m = 2 * dx;
		i32 scale = 2 * dy;
		for (i32 y = y0, x = x0; y != y1 + yStep; y += yStep) {
			DrawPixel(x, y, r, g, b);

			error += m;
			if (error >= dy) {
				x += xStep;
				error -= scale;
			}
		}
	}
}

PolyRasterV0.cpp

#include "PolyRasterV0.h"
#include <cmath>
#include <iostream>

namespace Rasterizer {
	void raster_polygon_assert(bool b) {
		if (!b) {
			*((u8*)0) = 42;
		}
	}
}

Rasterizer::PolygonV0::PolygonV0() {
	// init edge chunks
	mEdges.next = 0;
	// init next pointer for all edges in edge chunks
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		mEdges.edges[i].next = &mEdges.edges[i + 1];
	}
	mEdges.edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;
	mFreeListHead = &mEdges.edges[0];
	mUseListHead = 0;
	mMin = { 0 };
	mMax = { 0 };
	mLastPathStart = { 0 };
	mPathClosedSinceStart = false;
	mNumEdges = 0;
}

Rasterizer::PolygonV0::~PolygonV0() {
	EdgeChunk* iterator = mEdges.next;

	while (iterator != 0) {
		EdgeChunk* toDelete = iterator;
		iterator = iterator->next;
		delete toDelete;
	}
}

void Rasterizer::PolygonV0::AllocateChunk() {
	// Allocate memory
	EdgeChunk* newChunk = new EdgeChunk();
	newChunk->next = 0;

	// Initialize next pointer for all edges
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		newChunk->edges[i].next = &newChunk->edges[i + 1];
	}
	newChunk->edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;

	// Find tail of chunks list
	EdgeChunk* tail = &mEdges;
	while (tail->next != 0) {
		tail = tail->next;
	}
	tail->next = newChunk;

	// Insert chunks into free list
	newChunk->edges[0].next = mFreeListHead;
	mFreeListHead = &newChunk->edges[0];
}

void Rasterizer::PolygonV0::StartPath() {
	if (mUseListHead != 0) {
		mUseListHead->next = mFreeListHead;
		mFreeListHead = mUseListHead;
		mUseListHead = 0;
	}
	mUseListHead = 0;
	mPathClosedSinceStart = false;
	mNumEdges = 0;
}

void Rasterizer::PolygonV0::AddPoint(f32 x, f32 y) {
	// If there is a previous edge, set this as point two and add it
	if (mUseListHead != 0) {
		mUseListHead->p1.x = x;
		mUseListHead->p1.y = y;
	}
	else {
		// There is no hot edge, this is the first point being added to the path
		mMin.x = mMax.x = x;
		mMin.y = mMax.y = y;
		mLastPathStart.x = x;
		mLastPathStart.y = y;
	}

	// Take an edge out of free list
	if (mFreeListHead == 0) {
		AllocateChunk();
	}
	Edge* edge = mFreeListHead;
	mFreeListHead = mFreeListHead->next;

	// Setup next edge edge
	edge->p0.x = x;
	edge->p0.y = y;

	// Add to used edge list
	edge->next = mUseListHead;
	mUseListHead = edge;
	mNumEdges += 1;

	// Expand bounding box
	if (x < mMin.x) { mMin.x = x; }
	if (y < mMin.y) { mMin.y = y; }
	if (x > mMax.x) { mMax.x = x; }
	if (y > mMax.y) { mMax.y = y; }
}

void Rasterizer::PolygonV0::FillPath(Image& target, const Color& color) {
	// Close path by adding the start point again
	if (mUseListHead != 0 && !mPathClosedSinceStart) {
		mUseListHead->p1.x = mLastPathStart.x;
		mUseListHead->p1.y = mLastPathStart.y;
		mPathClosedSinceStart = true;
	}

	// Round bounding box up to nearest integer coordinates
	// so we don't miss any of the edge pixels
	i32 minX = (mMin.x < 0.0f) ? mMin.x - 0.5f : mMin.x + 0.5f;
	i32 minY = (mMin.y < 0.0f) ? mMin.y - 0.5f : mMin.y + 0.5f;
	i32 maxX = (mMax.x < 0.0f) ? mMax.x - 0.5f : mMax.x + 0.5f;
	i32 maxY = (mMax.y < 0.0f) ? mMax.y - 0.5f : mMax.y + 0.5f;

	// For each scanline
	for (i32 y = minY; y <= maxY; ++y) { // Scanline
		for (i32 x = minX; x <= maxX; ++x) {
			// For each pixel, loop trough every edge to compute winding number
			i32 winding = 0;
			Edge* iter = mUseListHead;
			while (iter != 0) {
				// Ignore edges that do not intersect the scanline
				if (iter->p0.y < (float)y && iter->p1.y < (float)y) { // Above scanline
					iter = iter->next;
					continue;
				}
				else if (iter->p0.y > (float)y && iter->p1.y > (float)y) { // Below scanline
					iter = iter->next;
					continue;
				}
				else if (iter->p0.y == iter->p1.y) { // Skip horizontal
					iter = iter->next;
					continue;
				}

				// Just looking for the sign of the z axis of the cross produce here
				Point pointToStart{ iter->p0.x - (float)x, iter->p0.y - (float)y };
				Point pointToEnd{ iter->p1.x - (float)x, iter->p1.y - (float)y };
				float crossZ = pointToStart.x * pointToEnd.y - pointToStart.y * pointToEnd.x;

				// Adjust winding order for any edge that crosses the scan line
				if (iter->p0.y < (float)y && iter->p1.y >= (float)y) { // Crossing from top to bottom
					if (crossZ > 0) { // On Right
						--winding;
					}
				}
				else if (iter->p0.y >= (float)y && iter->p1.y < (float)y) { // Crossing from bottom to top
					if (crossZ < 0) { // On Left
						++winding;
					}
				}

				iter = iter->next;
			}

			// If the current pixel is inside the polygon, shade it
			if (winding != 0) {
				u32 pixel = ((u32)y * (target.width) + (u32)x) * target.components;
				if (pixel >= target.width * target.height * target.components) {
					continue; // Clip pixel
				}

				if (target.components == 1) {
					target.bits[pixel + 0] = color.r;
				}
				else if (target.components == 2) {
					target.bits[pixel + 0] = color.r;
					target.bits[pixel + 1] = color.g;
				}
				else if (target.components == 3) {
					target.bits[pixel + 0] = color.b;
					target.bits[pixel + 1] = color.g;
					target.bits[pixel + 2] = color.r;
				}
				else {
					target.bits[pixel + 0] = color.b;
					target.bits[pixel + 1] = color.g;
					target.bits[pixel + 2] = color.r;
					target.bits[pixel + 3] = color.a;
				}
				
			}
		}
	}
}

PolyRasterV0.h

#pragma once

#include "PolyCommon.h"

namespace Rasterizer {
	class PolygonV0 {
	public:
		struct Point { f32 x; f32 y; };
		struct Color { u8 r; u8 g; u8 b; u8 a; };
		struct Image { u8* bits; u32 width; u32 height; u32 components; };
	protected:
		struct Edge {
			Point p0;
			Point p1;
			Edge* next;
		};
		struct EdgeChunk {
			Edge edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK];
			EdgeChunk* next;
		};
	protected:
		EdgeChunk mEdges;
		Edge* mFreeListHead;
		Edge* mUseListHead;
		Point mMin;
		Point mMax;
		Point mLastPathStart;
		bool mPathClosedSinceStart;
		u32 mNumEdges;
		void AllocateChunk();
	public:
		PolygonV0();
		PolygonV0(const PolygonV0&) = delete;
		PolygonV0* operator=(const PolygonV0&) = delete;
		~PolygonV0();

		void StartPath();
		void AddPoint(f32 x, f32 y);
		void FillPath(Image& target, const Color& color);
	};
}

PolyRasterV1.cpp

#include "PolyRasterV1.h"
#include <cmath>
#include <iostream>

Rasterizer::PolygonV1::PolygonV1() {
	// init edge chunks
	mEdges.next = 0;
	// init next pointer for all edges in edge chunks
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		mEdges.edges[i].next = &mEdges.edges[i + 1];
	}
	mEdges.edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;
	mFreeListHead = &mEdges.edges[0];
	mUseListHead = 0;
	mMin = { 0 };
	mMax = { 0 };
	mLastPathStart = { 0 };
	mPathClosedSinceStart = false;
	mNumEdges = 0;
}

Rasterizer::PolygonV1::~PolygonV1() {
	EdgeChunk* iterator = mEdges.next;

	while (iterator != 0) {
		EdgeChunk* toDelete = iterator;
		iterator = iterator->next;
		delete toDelete;
	}
}

void Rasterizer::PolygonV1::AllocateChunk() {
	// Allocate memory
	EdgeChunk* newChunk = new EdgeChunk();
	newChunk->next = 0;

	// Initialize next pointer for all edges
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		newChunk->edges[i].next = &newChunk->edges[i + 1];
	}
	newChunk->edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;

	// Find tail of chunks list
	EdgeChunk* tail = &mEdges;
	while (tail->next != 0) {
		tail = tail->next;
	}
	tail->next = newChunk;

	// Insert chunks into free list
	newChunk->edges[0].next = mFreeListHead;
	mFreeListHead = &newChunk->edges[0];
}

void Rasterizer::PolygonV1::StartPath() {
	if (mUseListHead != 0) {
		mUseListHead->next = mFreeListHead;
		mFreeListHead = mUseListHead;
		mUseListHead = 0;
	}
	mUseListHead = 0;
	mPathClosedSinceStart = false;
	mNumEdges = 0;
}

void Rasterizer::PolygonV1::AddPoint(f32 x, f32 y) {
	// If there is a previous edge, set this as point two and add it
	if (mUseListHead != 0) {
		mUseListHead->p1.x = x;
		mUseListHead->p1.y = y;
	}
	else {
		// There is no hot edge, this is the first point being added to the path
		mMin.x = mMax.x = x;
		mMin.y = mMax.y = y;
		mLastPathStart.x = x;
		mLastPathStart.y = y;
	}

	// Take an edge out of free list
	if (mFreeListHead == 0) {
		AllocateChunk();
	}
	Edge* edge = mFreeListHead;
	mFreeListHead = mFreeListHead->next;

	// Setup next edge edge
	edge->p0.x = x;
	edge->p0.y = y;

	// Add to used edge list
	edge->next = mUseListHead;
	mUseListHead = edge;
	mNumEdges += 1;

	// Expand bounding box
	if (x < mMin.x) { mMin.x = x; }
	if (y < mMin.y) { mMin.y = y; }
	if (x > mMax.x) { mMax.x = x; }
	if (y > mMax.y) { mMax.y = y; }
}

void Rasterizer::PolygonV1::SortEdgesY() {
	u32 leftSize = mNumEdges / 2;
	u32 rightSize = mNumEdges - leftSize;
	Edge* left = mUseListHead;
	Edge* right = mUseListHead;

	if (leftSize > 0) {
		for (u32 i = 0; i < leftSize - 1; ++i) {
			right = right->next;
		} // Right actually holds the last left element, use this to null out next pointer
		Edge* tmp = right->next;
		right->next = 0;
		right = tmp;
	}


	mUseListHead = MergeSortRecursiveY(left, leftSize, right, rightSize);
}

Rasterizer::PolygonV1::Edge* Rasterizer::PolygonV1::MergeSortRecursiveY(Edge* left, u32 leftSize, Edge* right, u32 rightSize) {
	if (leftSize >= 2) {
		Edge* splitLeft = left;
		u32 splitLeftSize = leftSize / 2;
		Edge* splitRight = left;
		u32 splitRightSize = leftSize - splitLeftSize;

		for (u32 i = 0; i < splitLeftSize - 1; ++i) {
			splitRight = splitRight->next;
		} // Right actually holds the last left element, use this to null out next pointer
		Edge* tmp = splitRight->next;
		splitRight->next = 0;
		splitRight = tmp;

		left = MergeSortRecursiveY(splitLeft, splitLeftSize, splitRight, splitRightSize);
	}
	if (rightSize >= 2) {
		Edge* splitLeft = right;
		u32 splitLeftSize = rightSize / 2;
		Edge* splitRight = right;
		u32 splitRightSize = rightSize - splitLeftSize;

		for (u32 i = 0; i < splitLeftSize - 1; ++i) {
			splitRight = splitRight->next;
		}
		Edge* tmp = splitRight->next;
		splitRight->next = 0;
		splitRight = tmp;

		right = MergeSortRecursiveY(splitLeft, splitLeftSize, splitRight, splitRightSize);
	}

	Edge* head = 0;
	Edge* tail = 0;

	while (left != 0 || right != 0) {
		if (head == 0) { // List is empty
			RASTER_POLYGON_ASSERT(tail == 0);
			if (left != 0 && right != 0) {
				if (fminf(left->p0.y, left->p1.y) < fminf(right->p0.y, right->p1.y)) {
					head = tail = left;
					left = left->next;
				}
				else {
					head = tail = right;
					right = right->next;
				}
			}
			else if (left != 0) {
				head = tail = left;
				left = left->next;
			}
			else if (right != 0) {
				head = tail = right;
				right = right->next;
			}
			tail->next = 0;
		}
		else {
			if (left != 0 && right != 0) {
				if (fminf(left->p0.y, left->p1.y) < fminf(right->p0.y, right->p1.y)) {
					tail->next = left;
					tail = left;
					left = left->next;
				}
				else {
					tail->next = right;
					tail = right;
					right = right->next;
				}
			}
			else if (left != 0) {
				tail->next = left;
				tail = left;
				left = left->next;
			}
			else if (right != 0) {
				tail->next = right;
				tail = right;
				right = right->next;
			}
			tail->next = 0;
		}
	}

	return head;
}

void Rasterizer::PolygonV1::FillPath(Image& target, const Color& color) {
	// Close path by adding the start point again
	if (mUseListHead != 0 && !mPathClosedSinceStart) {
		mUseListHead->p1.x = mLastPathStart.x;
		mUseListHead->p1.y = mLastPathStart.y;
		mPathClosedSinceStart = true;
	}

	// Round bounding box up to nearest integer coordinates
	// so we don't miss any of the edge pixels
	i32 minX = (mMin.x < 0.0f) ? mMin.x - 0.5f : mMin.x + 0.5f;
	i32 minY = (mMin.y < 0.0f) ? mMin.y - 0.5f : mMin.y + 0.5f;
	i32 maxX = (mMax.x < 0.0f) ? mMax.x - 0.5f : mMax.x + 0.5f;
	i32 maxY = (mMax.y < 0.0f) ? mMax.y - 0.5f : mMax.y + 0.5f;

	// Sort edges in y order
	SortEdgesY();

	Edge* activeEdgeList = 0;
	Edge* inactiveEdgeList = 0;

	// For each scanline
	for (i32 y = minY; y <= maxY; ++y) { // Scanline
		// Add any edge that crosses the scanline to the active edges list
		while (mUseListHead != 0 && (mUseListHead->p0.y <= (float)y || mUseListHead->p1.y <= (float)y)) {
			if (activeEdgeList == 0) {
				activeEdgeList = mUseListHead;
				mUseListHead = mUseListHead->next;
				activeEdgeList->next = 0;
			}
			else {
				Edge* move = mUseListHead;
				mUseListHead = mUseListHead->next;
				move->next = activeEdgeList;
				activeEdgeList = move;
			}
		}

		// Remove any edge that is no longer valid
		Edge* iter = activeEdgeList;
		Edge* last = 0;
		while (iter != 0) {
			bool above = iter->p0.y < (float)y&& iter->p1.y < (float)y;
			bool horizontal = (i32)iter->p0.y == (i32)iter->p1.y;

			if (above || horizontal) {
				if (last == 0) { // Removing head
					Edge* tmp = activeEdgeList;
					activeEdgeList = activeEdgeList->next;
					tmp->next = inactiveEdgeList;
					inactiveEdgeList = tmp;
					// Don't advance last, we just removed the head, next one might be invalid too
					iter = iter->next;
					continue;
				}
				else { // Removing any other items
					last->next = iter->next;
					Edge* tmp = iter;
					iter = iter->next;

					tmp->next = inactiveEdgeList;
					inactiveEdgeList = tmp;
					continue;
				}
			}

			last = iter;
			iter = iter->next;
		}

		for (i32 x = minX; x <= maxX; ++x) {
			// For each pixel, loop trough every edge to compute winding number
			i32 winding = 0;
			iter = activeEdgeList;
			while (iter != 0) {
				// At this point, the edge is sure to be crossing the scanline

				// Just looking for the sign of the z axis of the cross produce here
				Point pointToStart{ iter->p0.x - (float)x, iter->p0.y - (float)y };
				Point pointToEnd{ iter->p1.x - (float)x, iter->p1.y - (float)y };
				float crossZ = pointToStart.x * pointToEnd.y - pointToStart.y * pointToEnd.x;

				// Adjust winding order for any edge that crosses the scan line
				if (iter->p0.y < (float)y && iter->p1.y >= (float)y) { // Crossing from top to bottom
					if (crossZ > 0) { // On Right
						--winding;
					}
				}
				else if (iter->p0.y >= (float)y && iter->p1.y < (float)y) { // Crossing from bottom to top
					if (crossZ < 0) { // On Left
						++winding;
					}
				}

				last = iter;
				iter = iter->next;
			}

			// If the current pixel is inside the polygon, shade it
			if (winding != 0) {
				u32 pixel = ((u32)y * (target.width) + (u32)x) * target.components;
				if (pixel >= target.width * target.height * target.components) {
					continue; // Clip pixel
				}

				if (target.components == 1) {
					target.bits[pixel + 0] = color.r;
				}
				else if (target.components == 2) {
					target.bits[pixel + 0] = color.r;
					target.bits[pixel + 1] = color.g;
				}
				else if (target.components == 3) {
					target.bits[pixel + 0] = color.b;
					target.bits[pixel + 1] = color.g;
					target.bits[pixel + 2] = color.r;
				}
				else {
					target.bits[pixel + 0] = color.b;
					target.bits[pixel + 1] = color.g;
					target.bits[pixel + 2] = color.r;
					target.bits[pixel + 3] = color.a;
				}
			}
		}
	}

	// move active edges to be inactive
	while (activeEdgeList != 0) {
		Edge* active = activeEdgeList;
		activeEdgeList = activeEdgeList->next;

		active->next = inactiveEdgeList;
		inactiveEdgeList = active;
	}

	while (mUseListHead != 0) {
		Edge* active = mUseListHead;
		mUseListHead = mUseListHead->next;

		active->next = inactiveEdgeList;
		inactiveEdgeList = active;
	}

	mUseListHead = inactiveEdgeList;
}

PolyRasterV1.h

#pragma once

#include "PolyCommon.h"

namespace Rasterizer {
	class PolygonV1 {
	public:
		struct Point { f32 x; f32 y; };
		struct Color { u8 r; u8 g; u8 b; u8 a; };
		struct Image { u8* bits; u32 width; u32 height; u32 components; };
	protected:
		struct Edge {
			Point p0;
			Point p1;
			Edge* next;
		};
		struct EdgeChunk {
			Edge edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK];
			EdgeChunk* next;
		};
	protected:
		EdgeChunk mEdges;
		Edge* mFreeListHead;
		Edge* mUseListHead;
		Point mMin;
		Point mMax;
		Point mLastPathStart;
		bool mPathClosedSinceStart;
		u32 mNumEdges;
		void AllocateChunk();
		void SortEdgesY(); // https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
		Edge* MergeSortRecursiveY(Edge* left, u32 leftSize, Edge* right, u32 rightSize);
	public:
		PolygonV1();
		PolygonV1(const PolygonV1&) = delete;
		PolygonV1* operator=(const PolygonV1&) = delete;
		~PolygonV1();

		void StartPath();
		void AddPoint(f32 x, f32 y); // Will allocate new edge chunk when needed
		void FillPath(Image& target, const Color& color);
	};
}

PolyRasterV2.cpp

#include "PolyRasterV2.h"
#include <cmath>
#include <iostream>

Rasterizer::PolygonV2::PolygonV2() {
	// init edge chunks
	mEdges.next = 0;
	// init next pointer for all edges in edge chunks
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		mEdges.edges[i].next = &mEdges.edges[i + 1];
	}
	mEdges.edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;
	mFreeEdgesHead = &mEdges.edges[0];
	mInUseEdgesHead = 0;
	mMin = { 0 };
	mMax = { 0 };
	mLastPathStart = { 0 };
	mPathClosedSinceStart = false;
	mNumEdges = 0;

	mRasters.next = 0;
	for (u32 i = 0; i < RASTER_POLYGON_NUM_RASTER_PER_CHUNK - 1; ++i) {
		mRasters.edges[i].next = &mRasters.edges[i + 1];
	}
	mRasters.edges[RASTER_POLYGON_NUM_RASTER_PER_CHUNK - 1].next = 0;
	mFreeRasterHead = &mRasters.edges[0];
}

Rasterizer::PolygonV2::~PolygonV2() {
	EdgeChunk* iterator = mEdges.next;

	while (iterator != 0) {
		EdgeChunk* toDelete = iterator;
		iterator = iterator->next;
		delete toDelete;
	}
}

void Rasterizer::PolygonV2::AllocateChunk() {
	// Allocate memory
	EdgeChunk* newChunk = new EdgeChunk();
	newChunk->next = 0;

	// Initialize next pointer for all edges
	for (u32 i = 0; i < RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1; ++i) {
		newChunk->edges[i].next = &newChunk->edges[i + 1];
	}
	newChunk->edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK - 1].next = 0;

	// Add allocated chunk
	newChunk->next = mEdges.next;
	mEdges.next = newChunk;

	// Insert chunks into free list
	newChunk->edges[0].next = mFreeEdgesHead;
	mFreeEdgesHead = &newChunk->edges[0];
}

void Rasterizer::PolygonV2::AllocateRasterChunk() {
	RasterEdgeChunk* newChunk = new RasterEdgeChunk();
	newChunk->next = 0;

	for (u32 i = 0; i < RASTER_POLYGON_NUM_RASTER_PER_CHUNK - 1; ++i) {
		newChunk->edges[i].next = &newChunk->edges[i + 1];
	}
	newChunk->edges[RASTER_POLYGON_NUM_RASTER_PER_CHUNK - 1].next = 0;

	newChunk->next = mRasters.next;
	mRasters.next = newChunk;

	newChunk->edges[0].next = mFreeRasterHead;
	mFreeRasterHead = &newChunk->edges[0];
}

void Rasterizer::PolygonV2::StartPath() {
	if (mInUseEdgesHead != 0) {
		mInUseEdgesHead->next = mFreeEdgesHead;
		mFreeEdgesHead = mInUseEdgesHead;
		mInUseEdgesHead = 0;
	}
	mInUseEdgesHead = 0;
	mPathClosedSinceStart = false;
	mNumEdges = 0;
}

void Rasterizer::PolygonV2::AddPoint(f32 x, f32 y) {
	// If there is a previous edge, set this as point two and add it
	if (mInUseEdgesHead != 0) {
		mInUseEdgesHead->p1.x = x;
		mInUseEdgesHead->p1.y = y;
	}
	else {
		// There is no hot edge, this is the first point being added to the path
		mMin.x = mMax.x = x;
		mMin.y = mMax.y = y;
		mLastPathStart.x = x;
		mLastPathStart.y = y;
	}

	// Take an edge out of free list
	if (mFreeEdgesHead == 0) {
		AllocateChunk();
	}
	Edge* edge = mFreeEdgesHead;
	mFreeEdgesHead = mFreeEdgesHead->next;

	// Setup next edge edge
	edge->p0.x = x;
	edge->p0.y = y;

	// Add to used edge list
	edge->next = mInUseEdgesHead;
	mInUseEdgesHead = edge;
	mNumEdges += 1;

	// Expand bounding box
	if (x < mMin.x) { mMin.x = x; }
	if (y < mMin.y) { mMin.y = y; }
	if (x > mMax.x) { mMax.x = x; }
	if (y > mMax.y) { mMax.y = y; }
}

Rasterizer::PolygonV2::RasterEdge* Rasterizer::PolygonV2::SortRasterEdgesX(RasterEdge* head, u32 size) {
	u32 leftSize = size / 2;
	u32 rightSize = size - leftSize;
	RasterEdge* left = head;
	RasterEdge* right = 0;

	if (leftSize > 0) {
		right = head;
		for (u32 i = 0; i < leftSize - 1; ++i) {
			right = right->next;
		} // Right actually holds the last left element, use this to null out next pointer
		RasterEdge* tmp = right->next;
		right->next = 0;
		right = tmp;
	}

	if (leftSize >= 2) {
		left = SortRasterEdgesX(left, leftSize);
	}
	if (rightSize >= 2) {
		right = SortRasterEdgesX(right, rightSize);
	}

	head = 0;
	RasterEdge* tail = 0;

	while (left != 0 || right != 0) {
		if (left != 0 && right != 0) {
			if (left->x < right->x) {
				if (tail == 0) {
					head = tail = left;
				}
				else {
					tail->next = left;
					tail = left;
				}
				left = left->next;
				tail->next = 0;
			}
			else {
				if (tail == 0) {
					head = tail = right;
				}
				else {
					tail->next = right;
					tail = right;
				}
				right = right->next;
				tail->next = 0;
			}
		}
		else if (left != 0) {
			if (tail == 0) {
				head = tail = left;
			}
			else {
				tail->next = left;
				tail = left;
			}
			left = left->next;
			tail->next = 0;
		}
		else if (right != 0) {
			if (tail == 0) {
				head = tail = right;
			}
			else {
				tail->next = right;
				tail = right;
			}
			right = right->next;
			tail->next = 0;
		}
	}

	return head;
}

Rasterizer::PolygonV2::Edge* Rasterizer::PolygonV2::SortEdgesY(Edge* head, u32 size) {
	u32 leftSize = size / 2;
	u32 rightSize = size - leftSize;
	Edge* left = head;
	Edge* right = 0;

	if (leftSize > 0) {
		right = head;
		for (u32 i = 0; i < leftSize - 1; ++i) {
			right = right->next;
		} // Right actually holds the last left element, use this to null out next pointer
		Edge* tmp = right->next;
		right->next = 0;
		right = tmp;
	}

	if (leftSize >= 2) {
		left = SortEdgesY(left, leftSize);
	}
	if (rightSize >= 2) {
		right = SortEdgesY(right, rightSize);
	}

	head = 0;
	Edge* tail = 0;

	while (left != 0 || right != 0) {
		if (left != 0 && right != 0) {
			if (fminf(left->p0.y, left->p1.y) < fminf(right->p0.y, right->p1.y)) {
				if (tail == 0) {
					head = tail = left;
				}
				else {
					tail->next = left;
					tail = left;
				}
				left = left->next;
				tail->next = 0;
			}
			else {
				if (tail == 0) {
					head = tail = right;
				}
				else {
					tail->next = right;
					tail = right;
				}
				right = right->next;
				tail->next = 0;
			}
		}
		else if (left != 0) {
			if (tail == 0) {
				head = tail = left;
			}
			else {
				tail->next = left;
				tail = left;
			}
			left = left->next;
			tail->next = 0;
		}
		else if (right != 0) {
			if (tail == 0) {
				head = tail = right;
			}
			else {
				tail->next = right;
				tail = right;
			}
			right = right->next;
			tail->next = 0;
		}
	}

	return head;
}

void Rasterizer::PolygonV2::FillPath(Image& target, const Color& color) {
	// Close path by adding the start point again
	if (mInUseEdgesHead != 0 && !mPathClosedSinceStart) {
		mInUseEdgesHead->p1.x = mLastPathStart.x;
		mInUseEdgesHead->p1.y = mLastPathStart.y;
		mPathClosedSinceStart = true;
	}

	// Round bounding box up to nearest integer coordinates
	// so we don't miss any of the edge pixels
	i32 minX = (mMin.x < 0.0f) ? mMin.x - 0.5f : mMin.x + 0.5f;
	i32 minY = (mMin.y < 0.0f) ? mMin.y - 0.5f : mMin.y + 0.5f;
	i32 maxX = (mMax.x < 0.0f) ? mMax.x - 0.5f : mMax.x + 0.5f;
	i32 maxY = (mMax.y < 0.0f) ? mMax.y - 0.5f : mMax.y + 0.5f;

	// Sort edges in y order
	mInUseEdgesHead = SortEdgesY(mInUseEdgesHead, mNumEdges);

	//Edge* activeEdgeList = 0; TODO: I guess bring this back based on the comments below
	Edge* inactiveEdgeList = 0;
	RasterEdge* activeEdges = 0;
	u32 numRasterEdges = 0;

	// For each scanline (the +1 will give all edges a change to be cleaned up while not drawing anything)
	for (i32 y = minY; y <= maxY + 1; ++y) { // Scanline
		// Add any edge that crosses the scanline to the active edges list
		while (mInUseEdgesHead != 0 && (mInUseEdgesHead->p0.y <= (float)y || mInUseEdgesHead->p1.y <= (float)y)) {
			// TODO: Skip horizontal edges here

			if (mFreeRasterHead == 0) {
				AllocateRasterChunk();
			}
			RasterEdge* newEdge = mFreeRasterHead;
			mFreeRasterHead = mFreeRasterHead->next;

			newEdge->topToBottom = mInUseEdgesHead->p0.y < mInUseEdgesHead->p1.y;
			newEdge->bottom = fmaxf(mInUseEdgesHead->p0.y, mInUseEdgesHead->p1.y);
			if (mInUseEdgesHead->p0.y < mInUseEdgesHead->p1.y) {
				newEdge->x = mInUseEdgesHead->p0.x;
				newEdge->y = mInUseEdgesHead->p0.y;
				float dy = mInUseEdgesHead->p1.y - mInUseEdgesHead->p0.y;
				newEdge->dxdy = (dy == 0.0f) ? 0.0f : (mInUseEdgesHead->p1.x - mInUseEdgesHead->p0.x) / dy;
			}
			else {
				newEdge->x = mInUseEdgesHead->p1.x;
				newEdge->y = mInUseEdgesHead->p1.y;
				float dy = mInUseEdgesHead->p0.y - mInUseEdgesHead->p1.y;
				newEdge->dxdy = (dy == 0.0f) ? 0.0f : (mInUseEdgesHead->p0.x - mInUseEdgesHead->p1.x) / dy;
			}

			newEdge->next = activeEdges;
			activeEdges = newEdge;
			numRasterEdges += 1;

			Edge* tmp = mInUseEdgesHead;
			mInUseEdgesHead = mInUseEdgesHead->next;
			tmp->next = inactiveEdgeList;
			inactiveEdgeList = tmp;
		}

		// Remove any edge that is no longer valid
		RasterEdge* iter = activeEdges;
		RasterEdge* last = 0;
		while (iter != 0) {
			if (iter->y > iter->bottom) {
				if (last == 0) { // Removing head
					RASTER_POLYGON_ASSERT(iter == activeEdges);
					iter = iter->next;

					RasterEdge* tmp = activeEdges;
					activeEdges = activeEdges->next;

					tmp->next = mFreeRasterHead;
					mFreeRasterHead = tmp;

				}
				else {
					last->next = iter->next;
					RasterEdge* tmp = iter;
					iter = iter->next;

					tmp->next = mFreeRasterHead;
					mFreeRasterHead = tmp;
				}

				// Don't advance last, we just removed the head, next one might be invalid too
				numRasterEdges -= 1;
				continue;
			}

			last = iter;
			iter = iter->next;
		}

		// Sort Raster edges based on x coord
		activeEdges = SortRasterEdgesX(activeEdges, numRasterEdges);

		// Draw
		i32 winding = 0;
		for (iter = activeEdges; iter != 0; iter = iter->next) {
			// I only care about the edge direction, we should be able to replace this bit!
			if (iter->topToBottom) { // Crossing from top to bottom
				--winding;
			}
			else { // Crossing from bottom to top
				++winding;
			}

			if (winding != 0 && iter->next != 0) {
				for (u32 this_x = (u32)iter->x, next_x = (u32)iter->next->x; this_x < next_x; ++this_x) {
					u32 pixel = ((u32)y * (target.width) + this_x) * target.components;
					if (pixel >= target.width * target.height * target.components) {
						continue; // Clip pixel
					}

					if (target.components == 1) {
						target.bits[pixel + 0] = color.r;
					}
					else if (target.components == 2) {
						target.bits[pixel + 0] = color.r;
						target.bits[pixel + 1] = color.g;
					}
					else if (target.components == 3) {
						target.bits[pixel + 0] = color.b;
						target.bits[pixel + 1] = color.g;
						target.bits[pixel + 2] = color.r;
					}
					else {
						target.bits[pixel + 0] = color.b;
						target.bits[pixel + 1] = color.g;
						target.bits[pixel + 2] = color.r;
						target.bits[pixel + 3] = color.a;
					}
				}
			}
		}

		// Advance edges
		for (iter = activeEdges; iter != 0; iter = iter->next) {
			iter->y += 1.0f;
			iter->x += iter->dxdy;
		}
	}

	// Cleanup
	RASTER_POLYGON_ASSERT(activeEdges == 0);
	RASTER_POLYGON_ASSERT(mInUseEdgesHead == 0);
	mInUseEdgesHead = inactiveEdgeList;
}

PolyRasterV2.h

#pragma once

#include "PolyCommon.h"

namespace Rasterizer {
	class PolygonV2 {
	public:
		struct Point { f32 x; f32 y; };
		struct Color { u8 r; u8 g; u8 b; u8 a; };
		struct Image { u8* bits; u32 width; u32 height; u32 components; };
	protected:
		struct Edge {
			Point p0;
			Point p1;
			Edge* next;
		};
		struct EdgeChunk {
			Edge edges[RASTER_POLYGON_NUM_EDGES_PER_CHUNK];
			EdgeChunk* next;
		};

		struct RasterEdge {
			f32 x, y, dxdy, bottom;
			bool topToBottom;
			RasterEdge* next;
		};
		struct RasterEdgeChunk {
			RasterEdge edges[RASTER_POLYGON_NUM_RASTER_PER_CHUNK];
			RasterEdgeChunk* next;
		};
	protected:
		EdgeChunk mEdges;
		RasterEdgeChunk mRasters; // TODO: Better Name
		Edge* mFreeEdgesHead; // TODO: Better name
		Edge* mInUseEdgesHead; // TODO: Better name
		RasterEdge* mFreeRasterHead; // TODO: Better Name
		Point mMin;
		Point mMax;
		Point mLastPathStart;
		bool mPathClosedSinceStart;
		u32 mNumEdges;
		void AllocateChunk();
		void AllocateRasterChunk();
		Edge* SortEdgesY(Edge* head, u32 size);
		RasterEdge* SortRasterEdgesX(RasterEdge* head, u32 size);
	public:
		PolygonV2();
		PolygonV2(const PolygonV2&) = delete;
		PolygonV2* operator=(const PolygonV2&) = delete;
		~PolygonV2();

		void StartPath();
		void AddPoint(f32 x, f32 y); // Will allocate new edge chunk when needed
		void FillPath(Image& target, const Color& color);
	};
}