#include "engine.h"

struct QuadNode {
	int x, y, size;
	uint filled;
	QuadNode *child[4];
	QuadNode(int x, int y, int size) : x(x), y(y), size(size), filled(0) { loopi(4) child[i] = 0; }
	void clear() { loopi(4) DELETEP(child[i]); }
	~QuadNode() { clear(); }
	void insert(int mx, int my, int msize) {
		if(size == msize) {
			filled = 0xF;
			return;
		}
		int csize = size>>1, i = 0;
		if(mx >= x+csize) i |= 1;
		if(my >= y+csize) i |= 2;
		if(csize == msize) {
			filled |= (1 << i);
			return;
		}
		if(!child[i]) child[i] = new QuadNode(i&1 ? x+csize : x, i&2 ? y+csize : y, csize);
		child[i]->insert(mx, my, msize);
		loopj(4) if(child[j]) {
			if(child[j]->filled == 0xF) {
				DELETEP(child[j]);
				filled |= (1 << j);
			}
		}
	}
	void genmatsurf(ushort mat, uchar orient, uchar visible, int x, int y, int z, int size, materialsurface *&matbuf) {
		materialsurface &m = *matbuf++;
		m.material = mat;
		m.orient = orient;
		m.visible = visible;
		m.csize = size;
		m.rsize = size;
		int dim = dimension(orient);
		m.o[C[dim]] = x;
		m.o[R[dim]] = y;
		m.o[dim] = z;
	}
	void genmatsurfs(ushort mat, uchar orient, uchar flags, int z, materialsurface *&matbuf) {
		if(filled == 0xF) genmatsurf(mat, orient, flags, x, y, z, size, matbuf);
		else if(filled) {
			int csize = size>>1;
			loopi(4) if(filled & (1 << i))
				genmatsurf(mat, orient, flags, i&1 ? x+csize : x, i&2 ? y+csize : y, z, csize, matbuf);
		}
		loopi(4) if(child[i]) child[i]->genmatsurfs(mat, orient, flags, z, matbuf);
	}
};

static const bvec4 matnormals[6] = {
	bvec4(0x80, 0, 0),
	bvec4(0x7F, 0, 0),
	bvec4(0, 0x80, 0),
	bvec4(0, 0x7F, 0),
	bvec4(0, 0, 0x80),
	bvec4(0, 0, 0x7F)
};

static void drawmaterial(const materialsurface &m, float offset, const bvec4 &color) {
	if(gle::attribbuf.empty()) {
		gle::defvertex();
		gle::defcolor(4, GL_UNSIGNED_BYTE);
		gle::begin(GL_QUADS);
	}
	float x = m.o.x, y = m.o.y, z = m.o.z, csize = m.csize, rsize = m.rsize;
	switch(m.orient) {
	#define GENFACEORIENT(orient, v0, v1, v2, v3) \
		case orient: v0 v1 v2 v3 break;
	#define GENFACEVERT(orient, vert, mx,my,mz, sx,sy,sz) { \
		 \
			gle::attribf(mx sx, my sy, mz sz); \
			gle::attrib(color); \
		}
		GENFACEVERTS(x, x, y, y, z, z, /**/, + csize, /**/, + rsize, + offset, - offset)
	#undef GENFACEORIENT
	#undef GENFACEVERT
	}
}

const struct material {
	const char *name;
	ushort id;
} materials[] = {
 {
	"air", MAT_AIR}, {
	"clip", MAT_CLIP}, {
	"noclip", MAT_NOCLIP}, {
	"gameclip", MAT_GAMECLIP}, {
	"death", MAT_DEATH}, {
	"alpha", MAT_ALPHA}
};

int findmaterial(const char *name) {
	loopi(sizeof(materials)/sizeof(material)) {
		if(!strcmp(materials[i].name, name)) return materials[i].id;
	}
	return -1;
}

const char *findmaterialname(int mat) {
	loopi(sizeof(materials)/sizeof(materials[0])) if(materials[i].id == mat) return materials[i].name;
	return NULL;
}

const char *getmaterialdesc(int mat, const char *prefix) {
	static const ushort matmasks[] = { MATF_INDEX, MATF_CLIP, MAT_DEATH, MAT_ALPHA };
	static string desc;
	desc[0] = '\0';
	loopi(sizeof(matmasks)/sizeof(matmasks[0])) if(mat&matmasks[i]) {
		const char *matname = findmaterialname(mat&matmasks[i]);
		if(matname) {
			concatstring(desc, desc[0] ? ", " : prefix);
			concatstring(desc, matname);
		}
	}
	return desc;
}

int visiblematerial(const cube &c, int orient, const ivec &co, int size, ushort matmask) {
	ushort mat = c.material&matmask;
	switch(mat) {
	case MAT_AIR:
		 break;
	default:
		if(visibleface(c, orient, co, size, mat, MAT_AIR, matmask))
			return MATSURF_EDIT_ONLY;
		break;
	}
	return MATSURF_NOT_VISIBLE;
}

void genmatsurfs(const cube &c, const ivec &co, int size, vector<materialsurface> &matsurfs) {
	loopi(6) {
		static const ushort matmasks[] = { MATF_INDEX, MATF_CLIP, MAT_DEATH, MAT_ALPHA };
		loopj(sizeof(matmasks)/sizeof(matmasks[0])) {
			int matmask = matmasks[j];
			int vis = visiblematerial(c, i, co, size, matmask&~MATF_INDEX);
			if(vis != MATSURF_NOT_VISIBLE) {
				materialsurface m;
				m.material = c.material&matmask;
				m.orient = i;
				m.visible = vis;
				m.o = co;
				m.csize = m.rsize = size;
				if(dimcoord(i)) m.o[dimension(i)] += size;
				matsurfs.add(m);
				break;
			}
		}
	}
}

static inline bool mergematcmp(const materialsurface &x, const materialsurface &y) {
	int dim = dimension(x.orient), c = C[dim], r = R[dim];
	if(x.o[r] + x.rsize < y.o[r] + y.rsize) return true;
	if(x.o[r] + x.rsize > y.o[r] + y.rsize) return false;
	return x.o[c] < y.o[c];
}

static int mergematr(materialsurface *m, int sz, materialsurface &n) {
	int dim = dimension(n.orient), c = C[dim], r = R[dim];
	for(int i = sz-1; i >= 0; --i) {
		if(m[i].o[r] + m[i].rsize < n.o[r]) break;
		if(m[i].o[r] + m[i].rsize == n.o[r] && m[i].o[c] == n.o[c] && m[i].csize == n.csize) {
			n.o[r] = m[i].o[r];
			n.rsize += m[i].rsize;
			memmove(&m[i], &m[i+1], (sz - (i+1)) * sizeof(materialsurface));
			return 1;
		}
	}
	return 0;
}

static int mergematc(materialsurface &m, materialsurface &n) {
	int dim = dimension(n.orient), c = C[dim], r = R[dim];
	if(m.o[r] == n.o[r] && m.rsize == n.rsize && m.o[c] + m.csize == n.o[c]) {
		n.o[c] = m.o[c];
		n.csize += m.csize;
		return 1;
	}
	return 0;
}

static int mergemat(materialsurface *m, int sz, materialsurface &n) {
	for(bool merged = false; sz; merged = true) {
		int rmerged = mergematr(m, sz, n);
		sz -= rmerged;
		if(!rmerged && merged) break;
		if(!sz) break;
		int cmerged = mergematc(m[sz-1], n);
		sz -= cmerged;
		if(!cmerged) break;
	}
	m[sz++] = n;
	return sz;
}

static int mergemats(materialsurface *m, int sz) {
	quicksort(m, sz, mergematcmp);
	int nsz = 0;
	loopi(sz) nsz = mergemat(m, nsz, m[i]);
	return nsz;
}

static inline bool optmatcmp(const materialsurface &x, const materialsurface &y) {
	if(x.material < y.material) return true;
	if(x.material > y.material) return false;
	if(x.orient > y.orient) return true;
	if(x.orient < y.orient) return false;
	int dim = dimension(x.orient);
	return x.o[dim] < y.o[dim];
}

VARF(optmats, 0, 1, 1, allchanged());

int optimizematsurfs(materialsurface *matbuf, int matsurfs) {
	quicksort(matbuf, matsurfs, optmatcmp);
	if(!optmats) return matsurfs;
	materialsurface *cur = matbuf, *end = matbuf+matsurfs;
	while(cur < end) {
		 materialsurface *start = cur++;
		 int dim = dimension(start->orient);
		 while(cur < end &&
			   cur->material == start->material &&
			   cur->orient == start->orient &&
			   cur->visible == start->visible &&
			   cur->o[dim] == start->o[dim])
			++cur;
		 if(start->orient != O_TOP)
		 {
			if(start!=matbuf) memmove(matbuf, start, (cur-start)*sizeof(materialsurface));
			matbuf += mergemats(matbuf, cur-start);
		 }
		 else if(cur-start>=4)
		 {
			QuadNode vmats(0, 0, worldsize);
			loopi(cur-start) vmats.insert(start[i].o[C[dim]], start[i].o[R[dim]], start[i].csize);
			vmats.genmatsurfs(start->material, start->orient, start->visible, start->o[dim], matbuf);
		 }
		 else
		 {
			if(start!=matbuf) memmove(matbuf, start, (cur-start)*sizeof(materialsurface));
			matbuf += cur-start;
		 }
	}
	return matsurfs - (end-matbuf);
}

void setupmaterials(int start, int len) {
	if(!len) len = valist.length();
	for(int i = start; i < len; i++) {
		vtxarray *va = valist[i];
		materialsurface *skip = NULL;
		loopj(va->matsurfs) {
			materialsurface &m = va->matbuf[j];
			m.skip = 0;
			if(skip && m.material == skip->material && m.orient == skip->orient && skip->skip < 0xFFFF)
				skip->skip++;
			else
				skip = &m;
		}
	}
}

VARP(showmat, 0, 1, 1);

static int sortdim[3];
static ivec sortorigin;
static bool sortedit;

static inline bool vismatcmp(const materialsurface *xm, const materialsurface *ym) {
	const materialsurface &x = *xm, &y = *ym;
	int xdim = dimension(x.orient), ydim = dimension(y.orient);
	loopi(3) {
		int dim = sortdim[i], xmin, xmax, ymin, ymax;
		xmin = xmax = x.o[dim];
		if(dim==C[xdim]) xmax += x.csize;
		else if(dim==R[xdim]) xmax += x.rsize;
		ymin = ymax = y.o[dim];
		if(dim==C[ydim]) ymax += y.csize;
		else if(dim==R[ydim]) ymax += y.rsize;
		if(xmax > ymin && ymax > xmin) continue;
		int c = sortorigin[dim];
		if(c > xmin && c < xmax) return sortedit;
		if(c > ymin && c < ymax) return !sortedit;
		xmin = abs(xmin - c);
		xmax = abs(xmax - c);
		ymin = abs(ymin - c);
		ymax = abs(ymax - c);
		if(max(xmin, xmax) <= min(ymin, ymax)) return sortedit;
		else if(max(ymin, ymax) <= min(xmin, xmax)) return !sortedit;
	}
	if(x.material < y.material) return sortedit;
	if(x.material > y.material) return !sortedit;
	return false;
}

void sortmaterials(vector<materialsurface *> &vismats) {
	sortorigin = ivec(camera1->o);
	vec dir;
	vecfromyawpitch(camera1->yaw, camera1->pitch, 1, 0, dir);
	loopi(3) { dir[i] = fabs(dir[i]); sortdim[i] = i; }
	if(dir[sortdim[2]] > dir[sortdim[1]]) swap(sortdim[2], sortdim[1]);
	if(dir[sortdim[1]] > dir[sortdim[0]]) swap(sortdim[1], sortdim[0]);
	if(dir[sortdim[2]] > dir[sortdim[1]]) swap(sortdim[2], sortdim[1]);
	for(vtxarray *va = visibleva; va; va = va->next) {
		if(!va->matsurfs || va->occluded >= OCCLUDE_BB) continue;
		loopi(va->matsurfs) {
			materialsurface &m = va->matbuf[i];
			if(!editmode || !showmat || drawtex) {
				if(m.visible == MATSURF_EDIT_ONLY) { i += m.skip; continue; }
			}
			vismats.add(&m);
		}
	}
	sortedit = editmode && showmat && !drawtex;
	vismats.sort(vismatcmp);
}

void rendermatgrid(vector<materialsurface *> &vismats) {
	enablepolygonoffset(GL_POLYGON_OFFSET_LINE);
	glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
	int lastmat = -1;
	bvec4 color(0, 0, 0, 0);
	loopvrev(vismats) {
		materialsurface &m = *vismats[i];
		if(m.material != lastmat) {
			switch(m.material&~MATF_INDEX) {
				case MAT_CLIP:	 color = bvec4(85,  0,  0, 255); break; // red
				case MAT_NOCLIP:   color = bvec4( 0, 85,  0, 255); break; // green
				case MAT_GAMECLIP: color = bvec4(85, 85,  0, 255); break; // yellow
				case MAT_DEATH:	color = bvec4(40, 40, 40, 255); break; // black
				case MAT_ALPHA:	color = bvec4(85,  0, 85, 255); break; // pink
				default: continue;
			}
			lastmat = m.material;
		}
		drawmaterial(m, -0.1f, color);
	}
	xtraverts += gle::end();
	glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
	disablepolygonoffset(GL_POLYGON_OFFSET_LINE);
}

void rendermaterials() {
	vector<materialsurface *> vismats;
	sortmaterials(vismats);
	if(vismats.empty()) return;
	glDisable(GL_CULL_FACE);
	int lastorient = -1, lastmat = -1;
	bool depth = true, blended = false;
	GLOBALPARAM(camera, camera1->o);
	if(editmode && showmat && !drawtex) {
		glBlendFunc(GL_ZERO, GL_ONE_MINUS_SRC_COLOR);
		glEnable(GL_BLEND); blended = true;
		bvec4 color(0, 0, 0, 0);
		loopv(vismats) {
			const materialsurface &m = *vismats[i];
			if(lastmat!=m.material) {
				switch(m.material&~MATF_INDEX) {
					case MAT_CLIP:	 color = bvec4(  0, 255, 255, 255); break; // red
					case MAT_NOCLIP:   color = bvec4(255,   0, 255, 255); break; // green
					case MAT_GAMECLIP: color = bvec4(  0,   0, 255, 255); break; // yellow
					case MAT_DEATH:	color = bvec4(192, 192, 192, 255); break; // black
					case MAT_ALPHA:	color = bvec4(  0, 255,   0, 255); break; // pink
					default: continue;
				}
				lastmat = m.material;
			}
			drawmaterial(m, -0.1f, color);
		}
		xtraverts += gle::end();
	}
	if(lastorient >= 0)
		if(lastmat&~MATF_INDEX)
			xtraverts += gle::end();
	if(!depth) glDepthMask(GL_TRUE);
	if(blended) glDisable(GL_BLEND);
	extern int wireframe;
	if(editmode && showmat && !drawtex && !wireframe)
		rendermatgrid(vismats);
	glEnable(GL_CULL_FACE);
}