Quadtrees but not really

main.cpp

#include <cmath>
#include <functional>
#include <set>

#include "windows.h"

#include "lodepng.h"
#include "SDL.h"

const int MIN_RECT_SIZE = 2;
const int MAX_ITERATIONS = 500000;
const int BEST_ERROR = 50;
const bool DRAW_BORDER = false;

typedef std::vector<unsigned char> Image;

unsigned imgW, imgH;

struct Rect {
	int x, y, w, h;
	int col[3];
	double diff = 0;
	Rect(int _x, int _y, int _w, int _h, Image &image);
};

std::multiset<Rect, std::function<bool(Rect, Rect)>> elements([](Rect a1, Rect a2){return a1.diff > a2.diff; });

Rect::Rect(int _x, int _y, int _w, int _h, Image &image) :
	x(_x), y(_y), w(_w), h(_h)
{
	col[0] = 0; col[1] = 0; col[2] = 0;
	for (int i = x; i < x + w; ++i){
		for (int j = y; j < y + h; ++j){
			int xy = (j * imgW + i) * 4;
			col[0] += image[xy];
			col[1] += image[xy + 1];
			col[2] += image[xy + 2];
		}
	}
	col[0] /= (w*h);
	col[1] /= (w*h);
	col[2] /= (w*h);

	for (int i = x; i < x + w; ++i){
		for (int j = y; j < y + h; ++j){
			int xy = (j * imgW + i) * 4;
			diff += pow((int)image[xy] - col[0], 2);
			diff += pow((int)image[xy + 1] - col[1], 2);
			diff += pow((int)image[xy + 2] - col[2], 2);
		}
	}
	diff /= w;
}

void draw(SDL_Renderer *ren, const Rect &rect, bool black, bool border = false){
	SDL_Rect drawRect = { rect.x, rect.y,
		border ? rect.w - 1 : rect.w,
		border ? rect.h - 1 : rect.h };
	SDL_SetRenderDrawColor(ren,
		black ? 0 : rect.col[0], black ? 0 : rect.col[1], black ? 0 : rect.col[2], 255);
	SDL_RenderFillRect(ren, &drawRect);
}

void divide(const Rect &rect, SDL_Renderer *ren, Image &image){
	int x = rect.x, y = rect.y;
	int w = rect.w, h = rect.h;

	draw(ren, rect, true);	//black background

	elements.erase(elements.begin());

	for (int i = 0; i < 4; ++i){
		Rect subrect(
			i % 2 == 0 ? x : x + w / 2,
			i > 1 ? y : y + h / 2,
			i % 2 == 0 ? w / 2 : w - w / 2,
			i > 1 ? h / 2 : h - h / 2,
			image);
		elements.insert(subrect);
		draw(ren, subrect, false, DRAW_BORDER);
	}
}

int _stdcall WinMain(HINSTANCE, HINSTANCE, char*, int){
	Image image;
	lodepng::decode(image, imgW, imgH, "image.png");

	SDL_Window *window;
	SDL_Renderer *ren;
	SDL_CreateWindowAndRenderer(imgW, imgH, SDL_WINDOW_SHOWN, &window, &ren);

	elements.emplace(0, 0, imgW, imgH, image);

	bool stop = false;
	bool done = false;

	int iteration = 0;
	LARGE_INTEGER frequency, t1, t2;
	double calcTime;
	QueryPerformanceFrequency(&frequency);

	while(!done){
		SDL_Event event;
		while(SDL_PollEvent(&event)){
			if (event.type == SDL_QUIT)
				done = true;
		}

		QueryPerformanceCounter(&t1);

		if (!stop){
			const Rect &worst = *(elements.begin());
			if (worst.w < MIN_RECT_SIZE || worst.h < MIN_RECT_SIZE){
				elements.erase(elements.begin());
				if (elements.size() == 0)
					stop = true;
				continue;
			}
			if (worst.diff < BEST_ERROR){
				stop = true;
				continue;
			}
			divide(worst, ren, image);

			iteration++;
			if (iteration > MAX_ITERATIONS) stop = true;
		}

		SDL_RenderPresent(ren);

		QueryPerformanceCounter(&t2);

		if (iteration % 2 == 0 && !stop){
			char str[80];
			calcTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
			sprintf(str, "%d cycles, %f ms", iteration, calcTime);
			SDL_SetWindowTitle(window, str);
		}

		if(stop)
			SDL_Delay(1);
	}

	SDL_DestroyWindow(window);
	SDL_DestroyRenderer(ren);

	return 0;
}