// octarender.cpp: fill vertex arrays with different cube surfaces.

#include "engine.h"

struct vboinfo
{
	int uses;
};

hashtable<GLuint, vboinfo> vbos;

VAR(printvbo, 0, 0, 1);
VARFN(vbosize, maxvbosize, 0, 1<<14, 1<<16, allchanged());

enum
{
	VBO_VBUF = 0,
	VBO_EBUF,
	VBO_SKYBUF,
	NUMVBO
};

static vector<uchar> vbodata[NUMVBO];
static vector<vtxarray *> vbovas[NUMVBO];
static int vbosize[NUMVBO];

void destroyvbo(GLuint vbo)
{
	vboinfo *exists = vbos.access(vbo);
	if(!exists) return;
	vboinfo &vbi = *exists;
	if(vbi.uses <= 0) return;
	vbi.uses--;
	if(!vbi.uses)
	{
		glDeleteBuffers_(1, &vbo);
		vbos.remove(vbo);
	}
}

void genvbo(int type, void *buf, int len, vtxarray **vas, int numva)
{
	gle::disable();

	GLuint vbo;
	glGenBuffers_(1, &vbo);
	GLenum target = type==VBO_VBUF ? GL_ARRAY_BUFFER : GL_ELEMENT_ARRAY_BUFFER;
	glBindBuffer_(target, vbo);
	glBufferData_(target, len, buf, GL_STATIC_DRAW);
	glBindBuffer_(target, 0);

	vboinfo &vbi = vbos[vbo];
	vbi.uses = numva;

	if(printvbo) conoutf(CON_DEBUG, "vbo %d: type %d, size %d, %d uses", vbo, type, len, numva);

	loopi(numva)
	{
		vtxarray *va = vas[i];
		switch(type)
		{
			case VBO_VBUF:
				va->vbuf = vbo;
				break;
			case VBO_EBUF:
				va->ebuf = vbo;
				break;
			case VBO_SKYBUF:
				va->skybuf = vbo;
				break;
		}
	}
}

bool readva(vtxarray *va, ushort *&edata, vertex *&vdata)
{
	if(!va->vbuf || !va->ebuf) return false;

	edata = new ushort[3*va->tris];
	vdata = new vertex[va->verts];

	gle::bindebo(va->ebuf);
	glGetBufferSubData_(GL_ELEMENT_ARRAY_BUFFER, (size_t)va->edata, 3*va->tris*sizeof(ushort), edata);
	gle::clearebo();

	gle::bindvbo(va->vbuf);
	glGetBufferSubData_(GL_ARRAY_BUFFER, va->voffset*sizeof(vertex), va->verts*sizeof(vertex), vdata);
	gle::clearvbo();
	return true;
}

void flushvbo(int type = -1)
{
	if(type < 0)
	{
		loopi(NUMVBO) flushvbo(i);
		return;
	}

	vector<uchar> &data = vbodata[type];
	if(data.empty()) return;
	vector<vtxarray *> &vas = vbovas[type];
	genvbo(type, data.getbuf(), data.length(), vas.getbuf(), vas.length());
	data.setsize(0);
	vas.setsize(0);
	vbosize[type] = 0;
}

uchar *addvbo(vtxarray *va, int type, int numelems, int elemsize)
{
	vbosize[type] += numelems;

	vector<uchar> &data = vbodata[type];
	vector<vtxarray *> &vas = vbovas[type];

	vas.add(va);

	int len = numelems*elemsize;
	uchar *buf = data.reserve(len).buf;
	data.advance(len);
	return buf;
}

struct verthash
{
	static const int SIZE = 1<<13;
	int table[SIZE];
	vector<vertex> verts;
	vector<int> chain;

	verthash() { clearverts(); }

	void clearverts()
	{
		memset(table, -1, sizeof(table));
		chain.setsize(0);
		verts.setsize(0);
	}

	int addvert(const vertex &v)
	{
		uint h = hthash(v.pos)&(SIZE-1);
		for(int i = table[h]; i>=0; i = chain[i])
		{
			const vertex &c = verts[i];
			if(c.pos==v.pos && c.tc==v.tc && c.norm==v.norm && c.tangent==v.tangent && (v.lm.iszero() || c.lm==v.lm))
				return i;
		}
		if(verts.length() >= USHRT_MAX) return -1;
		verts.add(v);
		chain.add(table[h]);
		return table[h] = verts.length()-1;
	}

	int addvert(const vec &pos, const vec2 &tc = vec2(0, 0), const svec2 &lm = svec2(0, 0), const bvec &norm = bvec(128, 128, 128), const bvec4 &tangent = bvec4(128, 128, 128, 128))
	{
		vertex vtx;
		vtx.pos = pos;
		vtx.tc = tc;
		vtx.lm = lm;
		vtx.norm = norm;
		vtx.tangent = tangent;
		return addvert(vtx);
	}
};

enum
{
	NO_ALPHA = 0,
	ALPHA_BACK,
	ALPHA_FRONT
};

struct sortkey
{
	 ushort tex, lmid, envmap;
	 uchar dim, layer, alpha;

	 sortkey() {}
	 sortkey(ushort tex, ushort lmid, uchar dim, uchar layer = LAYER_TOP, ushort envmap = EMID_NONE, uchar alpha = NO_ALPHA)
	  : tex(tex), lmid(lmid), envmap(envmap), dim(dim), layer(layer), alpha(alpha)
	 {}

	 bool operator==(const sortkey &o) const { return tex==o.tex && lmid==o.lmid && envmap==o.envmap && dim==o.dim && layer==o.layer && alpha==o.alpha; }
};

struct sortval
{
	 int unlit;
	 vector<ushort> tris[2];

	 sortval() : unlit(0) {}
};

static inline bool htcmp(const sortkey &x, const sortkey &y)
{
	return x == y;
}

static inline uint hthash(const sortkey &k)
{
	return k.tex + k.lmid*9741;
}

struct vacollect : verthash
{
	ivec origin;
	int size;
	hashtable<sortkey, sortval> indices;
	vector<sortkey> texs;
	vector<materialsurface> matsurfs;
	vector<octaentities *> mapmodels;
	vector<ushort> skyindices, explicitskyindices;
	vector<facebounds> skyfaces[6];
	int worldtris, skytris, skymask, skyclip, skyarea;

	void clear()
	{
		clearverts();
		worldtris = skytris = 0;
		skymask = 0;
		skyclip = INT_MAX;
		skyarea = 0;
		indices.clear();
		skyindices.setsize(0);
		explicitskyindices.setsize(0);
		matsurfs.setsize(0);
		mapmodels.setsize(0);
		texs.setsize(0);
		loopi(6) skyfaces[i].setsize(0);
	}

	void remapunlit(vector<sortkey> &remap)
	{
		uint lastlmid[8] = { LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT },
			 firstlmid[8] = { LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT, LMID_AMBIENT };
		int firstlit[8] = { -1, -1, -1, -1, -1, -1, -1, -1 };
		loopv(texs)
		{
			sortkey &k = texs[i];
			if(k.lmid>=LMID_RESERVED)
			{
				LightMapTexture &lmtex = lightmaptexs[k.lmid];
				int type = lmtex.type&LM_TYPE;
				if(k.layer==LAYER_BLEND) type += 2;
				else if(k.alpha) type += 4 + 2*(k.alpha-1);
				lastlmid[type] = lmtex.unlitx>=0 ? (int) k.lmid : (int) LMID_AMBIENT;
				if(firstlmid[type]==LMID_AMBIENT && lastlmid[type]!=LMID_AMBIENT)
				{
					firstlit[type] = i;
					firstlmid[type] = lastlmid[type];
				}
			}
			else if(k.lmid==LMID_AMBIENT)
			{
				Shader *s = lookupvslot(k.tex, false).slot->shader;
				int type = s->type&SHADER_NORMALSLMS ? LM_BUMPMAP0 : LM_DIFFUSE;
				if(k.layer==LAYER_BLEND) type += 2;
				else if(k.alpha) type += 4 + 2*(k.alpha-1);
				if(lastlmid[type]!=LMID_AMBIENT)
				{
					sortval &t = indices[k];
					if(t.unlit<=0) t.unlit = lastlmid[type];
				}
			}
		}
		loopj(2)
		{
			int offset = 2*j;
			if(firstlmid[offset]==LMID_AMBIENT && firstlmid[offset+1]==LMID_AMBIENT) continue;
			loopi(max(firstlit[offset], firstlit[offset+1]))
			{
				sortkey &k = texs[i];
				if((j ? k.layer!=LAYER_BLEND : k.layer==LAYER_BLEND) || k.alpha) continue;
				if(k.lmid!=LMID_AMBIENT) continue;
				Shader *s = lookupvslot(k.tex, false).slot->shader;
				int type = offset + (s->type&SHADER_NORMALSLMS ? LM_BUMPMAP0 : LM_DIFFUSE);
				if(firstlmid[type]==LMID_AMBIENT) continue;
				indices[k].unlit = firstlmid[type];
			}
		}
		loopj(2)
		{
			int offset = 4 + 2*j;
			if(firstlmid[offset]==LMID_AMBIENT && firstlmid[offset+1]==LMID_AMBIENT) continue;
			loopi(max(firstlit[offset], firstlit[offset+1]))
			{
				sortkey &k = texs[i];
				if(k.alpha != j+1) continue;
				if(k.lmid!=LMID_AMBIENT) continue;
				Shader *s = lookupvslot(k.tex, false).slot->shader;
				int type = offset + (s->type&SHADER_NORMALSLMS ? LM_BUMPMAP0 : LM_DIFFUSE);
				if(firstlmid[type]==LMID_AMBIENT) continue;
				indices[k].unlit = firstlmid[type];
			}
		}
		loopv(remap)
		{
			sortkey &k = remap[i];
			sortval &t = indices[k];
			if(t.unlit<=0) continue;
			LightMapTexture &lm = lightmaptexs[t.unlit];
			svec2 lmtc(short(ceil((lm.unlitx + 0.5f) * SHRT_MAX/lm.w)),
					   short(ceil((lm.unlity + 0.5f) * SHRT_MAX/lm.h)));
			loopl(2) loopvj(t.tris[l])
			{
				vertex &vtx = verts[t.tris[l][j]];
				if(vtx.lm.iszero()) vtx.lm = lmtc;
				else if(vtx.lm != lmtc)
				{
					vertex vtx2 = vtx;
					vtx2.lm = lmtc;
					t.tris[l][j] = addvert(vtx2);
				}
			}
			sortval *dst = indices.access(sortkey(k.tex, t.unlit, k.dim, k.layer, k.envmap, k.alpha));
			if(dst) loopl(2) loopvj(t.tris[l]) dst->tris[l].add(t.tris[l][j]);
		}
	}

	void optimize()
	{
		vector<sortkey> remap;
		enumeratekt(indices, sortkey, k, sortval, t,
			loopl(2) if(t.tris[l].length() && t.unlit<=0)
			{
				if(k.lmid>=LMID_RESERVED && lightmaptexs[k.lmid].unlitx>=0)
				{
					sortkey ukey(k.tex, LMID_AMBIENT, k.dim, k.layer, k.envmap, k.alpha);
					sortval *uval = indices.access(ukey);
					if(uval && uval->unlit<=0)
					{
						if(uval->unlit<0) texs.removeobj(ukey);
						else remap.add(ukey);
						uval->unlit = k.lmid;
					}
				}
				else if(k.lmid==LMID_AMBIENT)
				{
					remap.add(k);
					t.unlit = -1;
				}
				texs.add(k);
				break;
			}
		);
		texs.sort(texsort);

		remapunlit(remap);

		matsurfs.shrink(optimizematsurfs(matsurfs.getbuf(), matsurfs.length()));
	}

	static inline bool texsort(const sortkey &x, const sortkey &y)
	{
		if(x.alpha < y.alpha) return true;
		if(x.alpha > y.alpha) return false;
		if(x.layer < y.layer) return true;
		if(x.layer > y.layer) return false;
		if(x.tex == y.tex)
		{
			if(x.lmid < y.lmid) return true;
			if(x.lmid > y.lmid) return false;
			if(x.envmap < y.envmap) return true;
			if(x.envmap > y.envmap) return false;
			if(x.dim < y.dim) return true;
			if(x.dim > y.dim) return false;
			return false;
		}
		VSlot &xs = lookupvslot(x.tex, false), &ys = lookupvslot(y.tex, false);
		if(xs.slot->shader < ys.slot->shader) return true;
		if(xs.slot->shader > ys.slot->shader) return false;
		if(xs.slot->params.length() < ys.slot->params.length()) return true;
		if(xs.slot->params.length() > ys.slot->params.length()) return false;
		if(x.tex < y.tex) return true;
		else return false;
	}

#define GENVERTS(type, ptr, body) do \
	{ \
		type *f = (type *)ptr; \
		loopv(verts) \
		{ \
			const vertex &v = verts[i]; \
			body; \
			f++; \
		} \
	} while(0)

	void genverts(void *buf)
	{
		GENVERTS(vertex, buf, { *f = v; f->norm.flip(); f->tangent.flip(); });
	}

	void setupdata(vtxarray *va)
	{
		va->verts = verts.length();
		va->tris = worldtris/3;
		va->vbuf = 0;
		va->vdata = 0;
		va->minvert = 0;
		va->maxvert = va->verts-1;
		va->voffset = 0;
		if(va->verts)
		{
			if(vbosize[VBO_VBUF] + verts.length() > maxvbosize ||
			   vbosize[VBO_EBUF] + worldtris > USHRT_MAX ||
			   vbosize[VBO_SKYBUF] + skytris > USHRT_MAX)
				flushvbo();

			va->voffset = vbosize[VBO_VBUF];
			uchar *vdata = addvbo(va, VBO_VBUF, va->verts, sizeof(vertex));
			genverts(vdata);
			va->minvert += va->voffset;
			va->maxvert += va->voffset;
		}

		va->matbuf = NULL;
		va->matsurfs = matsurfs.length();
		if(va->matsurfs)
		{
			va->matbuf = new materialsurface[matsurfs.length()];
			memcpy(va->matbuf, matsurfs.getbuf(), matsurfs.length()*sizeof(materialsurface));
		}

		va->skybuf = 0;
		va->skydata = 0;
		va->sky = skyindices.length();
		va->explicitsky = explicitskyindices.length();
		if(va->sky + va->explicitsky)
		{
			va->skydata += vbosize[VBO_SKYBUF];
			ushort *skydata = (ushort *)addvbo(va, VBO_SKYBUF, va->sky+va->explicitsky, sizeof(ushort));
			memcpy(skydata, skyindices.getbuf(), va->sky*sizeof(ushort));
			memcpy(skydata+va->sky, explicitskyindices.getbuf(), va->explicitsky*sizeof(ushort));
			if(va->voffset) loopi(va->sky+va->explicitsky) skydata[i] += va->voffset;
		}

		va->eslist = NULL;
		va->texs = texs.length();
		va->blendtris = 0;
		va->blends = 0;
		va->alphabacktris = 0;
		va->alphaback = 0;
		va->alphafronttris = 0;
		va->alphafront = 0;
		va->ebuf = 0;
		va->edata = 0;
		va->texmask = 0;
		if(va->texs)
		{
			va->eslist = new elementset[va->texs];
			va->edata += vbosize[VBO_EBUF];
			ushort *edata = (ushort *)addvbo(va, VBO_EBUF, worldtris, sizeof(ushort)), *curbuf = edata;
			loopv(texs)
			{
				const sortkey &k = texs[i];
				const sortval &t = indices[k];
				elementset &e = va->eslist[i];
				e.texture = k.tex;
				e.lmid = t.unlit>0 ? t.unlit : k.lmid;
				e.dim = k.dim;
				e.layer = k.layer;
				e.envmap = k.envmap;
				ushort *startbuf = curbuf;
				loopl(2)
				{
					e.minvert[l] = USHRT_MAX;
					e.maxvert[l] = 0;

					if(t.tris[l].length())
					{
						memcpy(curbuf, t.tris[l].getbuf(), t.tris[l].length() * sizeof(ushort));

						loopvj(t.tris[l])
						{
							curbuf[j] += va->voffset;
							e.minvert[l] = min(e.minvert[l], curbuf[j]);
							e.maxvert[l] = max(e.maxvert[l], curbuf[j]);
						}

						curbuf += t.tris[l].length();
					}
					e.length[l] = curbuf-startbuf;
				}
				if(k.layer==LAYER_BLEND) { va->texs--; va->tris -= e.length[1]/3; va->blends++; va->blendtris += e.length[1]/3; }
				else if(k.alpha==ALPHA_BACK) { va->texs--; va->tris -= e.length[1]/3; va->alphaback++; va->alphabacktris += e.length[1]/3; }
				else if(k.alpha==ALPHA_FRONT) { va->texs--; va->tris -= e.length[1]/3; va->alphafront++; va->alphafronttris += e.length[1]/3; }

				Slot &slot = *lookupvslot(k.tex, false).slot;
				loopvj(slot.sts) va->texmask |= 1<<slot.sts[j].type;
				if(slot.shader->type&SHADER_ENVMAP) va->texmask |= 1<<TEX_ENVMAP;
			}
		}

		va->alphatris = va->alphabacktris + va->alphafronttris;

		if(mapmodels.length()) va->mapmodels.put(mapmodels.getbuf(), mapmodels.length());
	}

	bool emptyva()
	{
		return verts.empty() && matsurfs.empty() && skyindices.empty() && explicitskyindices.empty() && mapmodels.empty();
	}
} vc;

int recalcprogress = 0;
#define progress(s)	 if((recalcprogress++&0xFFF)==0) renderprogress(recalcprogress/(float)allocnodes, s);

vector<tjoint> tjoints;

vec shadowmapmin, shadowmapmax;

int calcshadowmask(vec *pos, int numpos)
{
	extern vec shadowdir;
	int mask = 0, used = 1;
	vec pe = vec(pos[1]).sub(pos[0]);
	loopk(numpos-2)
	{
		vec e = vec(pos[k+2]).sub(pos[0]);
		if(vec().cross(pe, e).dot(shadowdir)>0)
		{
			mask |= 1<<k;
			used |= 6<<k;
		}
		pe = e;
	}
	if(!mask) return 0;
	loopk(numpos) if(used&(1<<k))
	{
		const vec &v = pos[k];
		shadowmapmin.min(v);
		shadowmapmax.max(v);
	}
	return mask;
}

VARFP(filltjoints, 0, 1, 1, allchanged());

void reduceslope(ivec &n)
{
	int mindim = -1, minval = 64;
	loopi(3) if(n[i])
	{
		int val = abs(n[i]);
		if(mindim < 0 || val < minval)
		{
			mindim = i;
			minval = val;
		}
	}
	if(!(n[R[mindim]]%minval) && !(n[C[mindim]]%minval)) n.div(minval);
	while(!((n.x|n.y|n.z)&1)) n.shr(1);
}

// [rotation][dimension]
extern const vec orientation_tangent[8][3] =
{
	{ vec(0,  1,  0), vec( 1, 0,  0), vec( 1,  0, 0) },
	{ vec(0,  0, -1), vec( 0, 0, -1), vec( 0,  1, 0) },
	{ vec(0, -1,  0), vec(-1, 0,  0), vec(-1,  0, 0) },
	{ vec(0,  0,  1), vec( 0, 0,  1), vec( 0, -1, 0) },
	{ vec(0, -1,  0), vec(-1, 0,  0), vec(-1,  0, 0) },
	{ vec(0,  1,  0), vec( 1, 0,  0), vec( 1,  0, 0) },
	{ vec(0,  0, -1), vec( 0, 0, -1), vec( 0,  1, 0) },
	{ vec(0,  0,  1), vec( 0, 0,  1), vec( 0, -1, 0) },
};
extern const vec orientation_bitangent[8][3] =
{
	{ vec(0,  0, -1), vec( 0, 0, -1), vec( 0,  1, 0) },
	{ vec(0, -1,  0), vec(-1, 0,  0), vec(-1,  0, 0) },
	{ vec(0,  0,  1), vec( 0, 0,  1), vec( 0, -1, 0) },
	{ vec(0,  1,  0), vec( 1, 0,  0), vec( 1,  0, 0) },
	{ vec(0,  0, -1), vec( 0, 0, -1), vec( 0,  1, 0) },
	{ vec(0,  0,  1), vec( 0, 0,  1), vec( 0, -1, 0) },
	{ vec(0,  1,  0), vec( 1, 0,  0), vec( 1,  0, 0) },
	{ vec(0, -1,  0), vec(-1, 0,  0), vec(-1,  0, 0) },
};

void addtris(const sortkey &key, int orient, vertex *verts, int *index, int numverts, int convex, int shadowmask, int tj)
{
	int &total = key.tex==DEFAULT_SKY ? vc.skytris : vc.worldtris;
	int edge = orient*(MAXFACEVERTS+1);
	loopi(numverts-2) if(index[0]!=index[i+1] && index[i+1]!=index[i+2] && index[i+2]!=index[0])
	{
		vector<ushort> &idxs = key.tex==DEFAULT_SKY ? vc.explicitskyindices : vc.indices[key].tris[(shadowmask>>i)&1];
		int left = index[0], mid = index[i+1], right = index[i+2], start = left, i0 = left, i1 = -1;
		loopk(4)
		{
			int i2 = -1, ctj = -1, cedge = -1;
			switch(k)
			{
			case 1: i1 = i2 = mid; cedge = edge+i+1; break;
			case 2: if(i1 != mid || i0 == left) { i0 = i1; i1 = right; } i2 = right; if(i+1 == numverts-2) cedge = edge+i+2; break;
			case 3: if(i0 == start) { i0 = i1; i1 = left; } i2 = left; // fall-through
			default: if(!i) cedge = edge; break;
			}
			if(i1 != i2)
			{
				if(total + 3 > USHRT_MAX) return;
				total += 3;
				idxs.add(i0);
				idxs.add(i1);
				idxs.add(i2);
				i1 = i2;
			}
			if(cedge >= 0)
			{
				for(ctj = tj;;)
				{
					if(ctj < 0) break;
					if(tjoints[ctj].edge < cedge) { ctj = tjoints[ctj].next; continue; }
					if(tjoints[ctj].edge != cedge) ctj = -1;
					break;
				}
			}
			if(ctj >= 0)
			{
				int e1 = cedge%(MAXFACEVERTS+1), e2 = (e1+1)%numverts;
				vertex &v1 = verts[e1], &v2 = verts[e2];
				ivec d(vec(v2.pos).sub(v1.pos).mul(8));
				int axis = abs(d.x) > abs(d.y) ? (abs(d.x) > abs(d.z) ? 0 : 2) : (abs(d.y) > abs(d.z) ? 1 : 2);
				if(d[axis] < 0) d.neg();
				reduceslope(d);
				int origin = int(min(v1.pos[axis], v2.pos[axis])*8)&~0x7FFF,
					offset1 = (int(v1.pos[axis]*8) - origin) / d[axis],
					offset2 = (int(v2.pos[axis]*8) - origin) / d[axis];
				vec o = vec(v1.pos).sub(vec(d).mul(offset1/8.0f));
				float doffset = 1.0f / (offset2 - offset1);

				if(i1 < 0) for(;;)
				{
					tjoint &t = tjoints[ctj];
					if(t.next < 0 || tjoints[t.next].edge != cedge) break;
					ctj = t.next;
				}
				while(ctj >= 0)
				{
					tjoint &t = tjoints[ctj];
					if(t.edge != cedge) break;
					float offset = (t.offset - offset1) * doffset;
					vertex vt;
					vt.pos = vec(d).mul(t.offset/8.0f).add(o);
					vt.tc.lerp(v1.tc, v2.tc, offset);
					vt.lm.x = short(v1.lm.x + (v2.lm.x-v1.lm.x)*offset),
					vt.lm.y = short(v1.lm.y + (v2.lm.y-v1.lm.y)*offset);
					vt.norm.lerp(v1.norm, v2.norm, offset);
					vt.tangent.lerp(v1.tangent, v2.tangent, offset);
					int i2 = vc.addvert(vt);
					if(i2 < 0) return;
					if(i1 >= 0)
					{
						if(total + 3 > USHRT_MAX) return;
						total += 3;
						idxs.add(i0);
						idxs.add(i1);
						idxs.add(i2);
						i1 = i2;
					}
					else start = i0 = i2;
					ctj = t.next;
				}
			}
		}
	}
}

static inline void calctexgen(VSlot &vslot, int dim, vec4 &sgen, vec4 &tgen)
{
	Texture *tex = vslot.slot->sts.empty() ? notexture : vslot.slot->sts[0].t;
	const texrotation &r = texrotations[vslot.rotation];
	float k = TEX_SCALE/vslot.scale,
		  xs = r.flipx ? -tex->xs : tex->xs,
		  ys = r.flipy ? -tex->ys : tex->ys,
		  sk = k/xs, tk = k/ys,
		  soff = -(r.swapxy ? vslot.offset.y : vslot.offset.x)/xs,
		  toff = -(r.swapxy ? vslot.offset.x : vslot.offset.y)/ys;
	static const int si[] = { 1, 0, 0 }, ti[] = { 2, 2, 1 };
	int sdim = si[dim], tdim = ti[dim];
	sgen = vec4(0, 0, 0, soff);
	tgen = vec4(0, 0, 0, toff);
	if(r.swapxy)
	{
		sgen[tdim] = (dim <= 1 ? -sk : sk);
		tgen[sdim] = tk;
	}
	else
	{
		sgen[sdim] = sk;
		tgen[tdim] = (dim <= 1 ? -tk : tk);
	}
}

ushort encodenormal(const vec &n)
{
	if(n.iszero()) return 0;
	int yaw = int(-atan2(n.x, n.y)/RAD), pitch = int(asin(n.z)/RAD);
	return ushort(clamp(pitch + 90, 0, 180)*360 + (yaw < 0 ? yaw%360 + 360 : yaw%360) + 1);
}

vec decodenormal(ushort norm)
{
	if(!norm) return vec(0, 0, 1);
	norm--;
	const vec2 &yaw = sincos360[norm%360], &pitch = sincos360[norm/360+270];
	return vec(-yaw.y*pitch.x, yaw.x*pitch.x, pitch.y);
}

void guessnormals(const vec *pos, int numverts, vec *normals)
{
	vec n1, n2;
	n1.cross(pos[0], pos[1], pos[2]);
	if(numverts != 4)
	{
		n1.normalize();
		loopk(numverts) normals[k] = n1;
		return;
	}
	n2.cross(pos[0], pos[2], pos[3]);
	if(n1.iszero())
	{
		n2.normalize();
		loopk(4) normals[k] = n2;
		return;
	}
	else n1.normalize();
	if(n2.iszero())
	{
		loopk(4) normals[k] = n1;
		return;
	}
	else n2.normalize();
	vec avg = vec(n1).add(n2).normalize();
	normals[0] = avg;
	normals[1] = n1;
	normals[2] = avg;
	normals[3] = n2;
}

void addcubeverts(VSlot &vslot, int orient, int size, vec *pos, int convex, ushort texture, ushort lmid, vertinfo *vinfo, int numverts, int tj = -1, ushort envmap = EMID_NONE, int grassy = 0, bool alpha = false, int layer = LAYER_TOP)
{
	(void) grassy;
	int dim = dimension(orient);
	int shadowmask = texture==DEFAULT_SKY || alpha ? 0 : calcshadowmask(pos, numverts);

	LightMap *lm = NULL;
	LightMapTexture *lmtex = NULL;
	if(lightmaps.inrange(lmid-LMID_RESERVED))
	{
		lm = &lightmaps[lmid-LMID_RESERVED];
		if((lm->type&LM_TYPE)==LM_DIFFUSE ||
			((lm->type&LM_TYPE)==LM_BUMPMAP0 &&
				lightmaps.inrange(lmid+1-LMID_RESERVED) &&
				(lightmaps[lmid+1-LMID_RESERVED].type&LM_TYPE)==LM_BUMPMAP1))
			lmtex = &lightmaptexs[lm->tex];
		else lm = NULL;
	}

	vec4 sgen, tgen;
	calctexgen(vslot, dim, sgen, tgen);
	vertex verts[MAXFACEVERTS];
	int index[MAXFACEVERTS];
	loopk(numverts)
	{
		vertex &v = verts[k];
		v.pos = pos[k];
		v.tc = vec2(sgen.dot(v.pos), tgen.dot(v.pos));
		if(lmtex)
		{
			v.lm = svec2(short(ceil((lm->offsetx + vinfo[k].u*(float(LM_PACKW)/float(USHRT_MAX+1)) + 0.5f) * float(SHRT_MAX)/lmtex->w)),
						 short(ceil((lm->offsety + vinfo[k].v*(float(LM_PACKH)/float(USHRT_MAX+1)) + 0.5f) * float(SHRT_MAX)/lmtex->h)));
		}
		else v.lm = svec2(0, 0);
		if(vinfo && vinfo[k].norm)
		{
			vec n = decodenormal(vinfo[k].norm), t = orientation_tangent[vslot.rotation][dim];
			t.project(n).normalize();
			v.norm = bvec(n);
			v.tangent = bvec4(bvec(t), orientation_bitangent[vslot.rotation][dim].scalartriple(n, t) < 0 ? 0 : 255);
		}
		else
		{
			v.norm = vinfo && vinfo[k].norm && envmap != EMID_NONE ? bvec(decodenormal(vinfo[k].norm)) : bvec(128, 128, 255);
			v.tangent = bvec4(255, 128, 128, 255);
		}
		index[k] = vc.addvert(v);
		if(index[k] < 0) return;
	}

	if(texture == DEFAULT_SKY)
	{
		loopk(numverts) vc.skyclip = min(vc.skyclip, int(pos[k].z*8)>>3);
		vc.skymask |= 0x3F&~(1<<orient);
	}

	if(lmid >= LMID_RESERVED) lmid = lm ? lm->tex : LMID_AMBIENT;

	sortkey key(texture, lmid, !vslot.scroll.iszero() ? dim : 3, layer == LAYER_BLEND ? LAYER_BLEND : LAYER_TOP, envmap, alpha ? (vslot.alphaback ? ALPHA_BACK : (vslot.alphafront ? ALPHA_FRONT : NO_ALPHA)) : NO_ALPHA);
	addtris(key, orient, verts, index, numverts, convex, shadowmask, tj);
}

struct edgegroup
{
	ivec slope, origin;
	int axis;
};

static uint hthash(const edgegroup &g)
{
	return g.slope.x^(g.slope.y<<2)^(g.slope.z<<4)^g.origin.x^g.origin.y^g.origin.z;
}

static bool htcmp(const edgegroup &x, const edgegroup &y)
{
	return x.slope==y.slope && x.origin==y.origin;
}

enum
{
	CE_START = 1<<0,
	CE_END   = 1<<1,
	CE_FLIP  = 1<<2,
	CE_DUP   = 1<<3
};

struct cubeedge
{
	cube *c;
	int next, offset;
	ushort size;
	uchar index, flags;
};

vector<cubeedge> cubeedges;
hashtable<edgegroup, int> edgegroups(1<<13);

void gencubeedges(cube &c, const ivec &co, int size)
{
	ivec pos[MAXFACEVERTS];
	int vis;
	loopi(6) if((vis = visibletris(c, i, co, size)))
	{
		int numverts = c.ext ? c.ext->surfaces[i].numverts&MAXFACEVERTS : 0;
		if(numverts)
		{
			vertinfo *verts = c.ext->verts() + c.ext->surfaces[i].verts;
			ivec vo = ivec(co).mask(~0xFFF).shl(3);
			loopj(numverts)
			{
				vertinfo &v = verts[j];
				pos[j] = ivec(v.x, v.y, v.z).add(vo);
			}
		}
		else if(c.merged&(1<<i)) continue;
		else
		{
			ivec v[4];
			genfaceverts(c, i, v);
			int order = vis&4 || (!flataxisface(c, i) && faceconvexity(v) < 0) ? 1 : 0;
			ivec vo = ivec(co).shl(3);
			pos[numverts++] = v[order].mul(size).add(vo);
			if(vis&1) pos[numverts++] = v[order+1].mul(size).add(vo);
			pos[numverts++] = v[order+2].mul(size).add(vo);
			if(vis&2) pos[numverts++] = v[(order+3)&3].mul(size).add(vo);
		}
		loopj(numverts)
		{
			int e1 = j, e2 = j+1 < numverts ? j+1 : 0;
			ivec d = pos[e2];
			d.sub(pos[e1]);
			if(d.iszero()) continue;
			int axis = abs(d.x) > abs(d.y) ? (abs(d.x) > abs(d.z) ? 0 : 2) : (abs(d.y) > abs(d.z) ? 1 : 2);
			if(d[axis] < 0)
			{
				d.neg();
				swap(e1, e2);
			}
			reduceslope(d);

			int t1 = pos[e1][axis]/d[axis],
				t2 = pos[e2][axis]/d[axis];
			edgegroup g;
			g.origin = ivec(pos[e1]).sub(ivec(d).mul(t1));
			g.slope = d;
			g.axis = axis;
			cubeedge ce;
			ce.c = &c;
			ce.offset = t1;
			ce.size = t2 - t1;
			ce.index = i*(MAXFACEVERTS+1)+j;
			ce.flags = CE_START | CE_END | (e1!=j ? CE_FLIP : 0);
			ce.next = -1;

			bool insert = true;
			int *exists = edgegroups.access(g);
			if(exists)
			{
				int prev = -1, cur = *exists;
				while(cur >= 0)
				{
					cubeedge &p = cubeedges[cur];
					if(ce.offset <= p.offset+p.size)
					{
						if(ce.offset < p.offset) break;
						if(p.flags&CE_DUP ?
							ce.offset+ce.size <= p.offset+p.size :
							ce.offset==p.offset && ce.size==p.size)
						{
							p.flags |= CE_DUP;
							insert = false;
							break;
						}
						if(ce.offset == p.offset+p.size) ce.flags &= ~CE_START;
					}
					prev = cur;
					cur = p.next;
				}
				if(insert)
				{
					ce.next = cur;
					while(cur >= 0)
					{
						cubeedge &p = cubeedges[cur];
						if(ce.offset+ce.size==p.offset) { ce.flags &= ~CE_END; break; }
						cur = p.next;
					}
					if(prev>=0) cubeedges[prev].next = cubeedges.length();
					else *exists = cubeedges.length();
				}
			}
			else edgegroups[g] = cubeedges.length();

			if(insert) cubeedges.add(ce);
		}
	}
}

void gencubeedges(cube *c = worldroot, const ivec &co = ivec(0, 0, 0), int size = worldsize>>1)
{
	progress("fixing t-joints...");
	neighbourstack[++neighbourdepth] = c;
	loopi(8)
	{
		ivec o(i, co, size);
		if(c[i].ext) c[i].ext->tjoints = -1;
		if(c[i].children) gencubeedges(c[i].children, o, size>>1);
		else if(!isempty(c[i])) gencubeedges(c[i], o, size);
	}
	--neighbourdepth;
}

void gencubeverts(cube &c, const ivec &co, int size, int csi)
{
	if(!(c.visible&0xC0)) return;

	int vismask = ~c.merged & 0x3F;
	if(!(c.visible&0x80)) vismask &= c.visible;
	if(!vismask) return;

	int tj = filltjoints && c.ext ? c.ext->tjoints : -1, vis;
	loopi(6) if(vismask&(1<<i) && (vis = visibletris(c, i, co, size)))
	{
		vec pos[MAXFACEVERTS];
		vertinfo *verts = NULL;
		int numverts = c.ext ? c.ext->surfaces[i].numverts&MAXFACEVERTS : 0, convex = 0;
		if(numverts)
		{
			verts = c.ext->verts() + c.ext->surfaces[i].verts;
			vec vo(ivec(co).mask(~0xFFF));
			loopj(numverts) pos[j] = vec(verts[j].getxyz()).mul(1.0f/8).add(vo);
			if(!flataxisface(c, i)) convex = faceconvexity(verts, numverts, size);
		}
		else
		{
			ivec v[4];
			genfaceverts(c, i, v);
			if(!flataxisface(c, i)) convex = faceconvexity(v);
			int order = vis&4 || convex < 0 ? 1 : 0;
			vec vo(co);
			pos[numverts++] = vec(v[order]).mul(size/8.0f).add(vo);
			if(vis&1) pos[numverts++] = vec(v[order+1]).mul(size/8.0f).add(vo);
			pos[numverts++] = vec(v[order+2]).mul(size/8.0f).add(vo);
			if(vis&2) pos[numverts++] = vec(v[(order+3)&3]).mul(size/8.0f).add(vo);
		}

		VSlot &vslot = lookupvslot(c.texture[i], true),
			  *layer = vslot.layer && !(c.material&MAT_ALPHA) ? &lookupvslot(vslot.layer, true) : NULL;
		ushort envmap = vslot.slot->shader->type&SHADER_ENVMAP ? (int) (vslot.slot->texmask&(1<<TEX_ENVMAP) ? (int) EMID_CUSTOM : (int) closestenvmap(i, co, size)) : (int) EMID_NONE,
			   envmap2 = layer && layer->slot->shader->type&SHADER_ENVMAP ? (int) (layer->slot->texmask&(1<<TEX_ENVMAP) ? (int) EMID_CUSTOM : (int) closestenvmap(i, co, size)) : (int) EMID_NONE;
		while(tj >= 0 && tjoints[tj].edge < i*(MAXFACEVERTS+1)) tj = tjoints[tj].next;
		int hastj = tj >= 0 && tjoints[tj].edge < (i+1)*(MAXFACEVERTS+1) ? tj : -1;
		if(!c.ext)
			addcubeverts(vslot, i, size, pos, convex, c.texture[i], LMID_AMBIENT, NULL, numverts, hastj, envmap, 0, (c.material&MAT_ALPHA)!=0);
		else
		{
			const surfaceinfo &surf = c.ext->surfaces[i];
			if(!surf.numverts || surf.numverts&LAYER_TOP)
				addcubeverts(vslot, i, size, pos, convex, c.texture[i], surf.lmid[0], verts, numverts, hastj, envmap, 0, (c.material&MAT_ALPHA)!=0, LAYER_TOP|(surf.numverts&LAYER_BLEND));
			if(surf.numverts&LAYER_BOTTOM)
				addcubeverts(layer ? *layer : vslot, i, size, pos, convex, vslot.layer, surf.lmid[1], surf.numverts&LAYER_DUP ? verts + numverts : verts, numverts, hastj, envmap2);
		}
	}
}

static inline bool skyoccluded(cube &c, int orient)
{
	return touchingface(c, orient) && faceedges(c, orient) == F_SOLID;
}

static int dummyskyfaces[6];
static inline int hasskyfaces(cube &c, const ivec &co, int size, int faces[6] = dummyskyfaces)
{
	int numfaces = 0;
	if(isempty(c) || c.material&MAT_ALPHA)
	{
		if(co.x == 0) faces[numfaces++] = O_LEFT;
		if(co.x + size == worldsize) faces[numfaces++] = O_RIGHT;
		if(co.y == 0) faces[numfaces++] = O_BACK;
		if(co.y + size == worldsize) faces[numfaces++] = O_FRONT;
		if(co.z == 0) faces[numfaces++] = O_BOTTOM;
		if(co.z + size == worldsize) faces[numfaces++] = O_TOP;
	}
	else if(!isentirelysolid(c))
	{
		if(co.x == 0 && !skyoccluded(c, O_LEFT)) faces[numfaces++] = O_LEFT;
		if(co.x + size == worldsize && !skyoccluded(c, O_RIGHT)) faces[numfaces++] = O_RIGHT;
		if(co.y == 0 && !skyoccluded(c, O_BACK)) faces[numfaces++] = O_BACK;
		if(co.y + size == worldsize && !skyoccluded(c, O_FRONT)) faces[numfaces++] = O_FRONT;
		if(co.z == 0 && !skyoccluded(c, O_BOTTOM)) faces[numfaces++] = O_BOTTOM;
		if(co.z + size == worldsize && !skyoccluded(c, O_TOP)) faces[numfaces++] = O_TOP;
	}
	return numfaces;
}

void minskyface(cube &cu, int orient, const ivec &co, int size, facebounds &orig)
{
	facebounds mincf;
	mincf.u1 = orig.u2;
	mincf.u2 = orig.u1;
	mincf.v1 = orig.v2;
	mincf.v2 = orig.v1;
	mincubeface(cu, orient, co, size, orig, mincf, MAT_ALPHA, MAT_ALPHA);
	orig.u1 = max(mincf.u1, orig.u1);
	orig.u2 = min(mincf.u2, orig.u2);
	orig.v1 = max(mincf.v1, orig.v1);
	orig.v2 = min(mincf.v2, orig.v2);
}

void genskyfaces(cube &c, const ivec &o, int size)
{
	int faces[6], numfaces = hasskyfaces(c, o, size, faces);
	if(!numfaces) return;

	loopi(numfaces)
	{
		int orient = faces[i], dim = dimension(orient);
		facebounds m;
		m.u1 = (o[C[dim]]&0xFFF)<<3;
		m.u2 = m.u1 + (size<<3);
		m.v1 = (o[R[dim]]&0xFFF)<<3;
		m.v2 = m.v1 + (size<<3);
		minskyface(c, orient, o, size, m);
		if(m.u1 >= m.u2 || m.v1 >= m.v2) continue;
		vc.skyarea += (int(m.u2-m.u1)*int(m.v2-m.v1) + (1<<(2*3))-1)>>(2*3);
		vc.skyfaces[orient].add(m);
	}
}

void addskyverts(const ivec &o, int size)
{
	loopi(6)
	{
		int dim = dimension(i), c = C[dim], r = R[dim];
		vector<facebounds> &sf = vc.skyfaces[i];
		if(sf.empty()) continue;
		vc.skymask |= 0x3F&~(1<<opposite(i));
		sf.setsize(mergefaces(i, sf.getbuf(), sf.length()));
		loopvj(sf)
		{
			facebounds &m = sf[j];
			int index[4];
			loopk(4)
			{
				const ivec &coords = facecoords[opposite(i)][k];
				vec v;
				v[dim] = o[dim];
				if(coords[dim]) v[dim] += size;
				v[c] = (o[c]&~0xFFF) + (coords[c] ? m.u2 : m.u1)/8.0f;
				v[r] = (o[r]&~0xFFF) + (coords[r] ? m.v2 : m.v1)/8.0f;
				index[k] = vc.addvert(v);
				if(index[k] < 0) goto nextskyface;
				vc.skyclip = min(vc.skyclip, int(v.z*8)>>3);
			}
			if(vc.skytris + 6 > USHRT_MAX) break;
			vc.skytris += 6;
			vc.skyindices.add(index[0]);
			vc.skyindices.add(index[1]);
			vc.skyindices.add(index[2]);

			vc.skyindices.add(index[0]);
			vc.skyindices.add(index[2]);
			vc.skyindices.add(index[3]);
		nextskyface:;
		}
	}
}

////////// Vertex Arrays //////////////

int allocva = 0;
int wtris = 0, wverts = 0, vtris = 0, vverts = 0, glde = 0, gbatches = 0;
vector<vtxarray *> valist, varoot;

vtxarray *newva(const ivec &co, int size)
{
	vc.optimize();

	vtxarray *va = new vtxarray;
	va->parent = NULL;
	va->o = co;
	va->size = size;
	va->skyarea = vc.skyarea;
	va->skyfaces = vc.skymask;
	va->skyclip = vc.skyclip < INT_MAX ? vc.skyclip : INT_MAX;
	va->curvfc = VFC_NOT_VISIBLE;
	va->occluded = OCCLUDE_NOTHING;
	va->query = NULL;
	va->bbmin = ivec(-1, -1, -1);
	va->bbmax = ivec(-1, -1, -1);
	va->hasmerges = 0;
	va->mergelevel = -1;

	vc.setupdata(va);

	wverts += va->verts;
	wtris  += va->tris + va->blends + va->alphatris;
	allocva++;
	valist.add(va);

	return va;
}

void destroyva(vtxarray *va, bool reparent)
{
	wverts -= va->verts;
	wtris -= va->tris + va->blends + va->alphatris;
	allocva--;
	valist.removeobj(va);
	if(!va->parent) varoot.removeobj(va);
	if(reparent)
	{
		if(va->parent) va->parent->children.removeobj(va);
		loopv(va->children)
		{
			vtxarray *child = va->children[i];
			child->parent = va->parent;
			if(child->parent) child->parent->children.add(child);
		}
	}
	if(va->vbuf) destroyvbo(va->vbuf);
	if(va->ebuf) destroyvbo(va->ebuf);
	if(va->skybuf) destroyvbo(va->skybuf);
	if(va->eslist) delete[] va->eslist;
	if(va->matbuf) delete[] va->matbuf;
	delete va;
}

void clearvas(cube *c)
{
	loopi(8)
	{
		if(c[i].ext)
		{
			if(c[i].ext->va) destroyva(c[i].ext->va, false);
			c[i].ext->va = NULL;
			c[i].ext->tjoints = -1;
		}
		if(c[i].children) clearvas(c[i].children);
	}
}

void updatevabb(vtxarray *va, bool force)
{
	if(!force && va->bbmin.x >= 0) return;

	va->bbmin = va->geommin;
	va->bbmax = va->geommax;
	va->bbmin.min(va->matmin);
	va->bbmax.max(va->matmax);
	loopv(va->children)
	{
		vtxarray *child = va->children[i];
		updatevabb(child, force);
		va->bbmin.min(child->bbmin);
		va->bbmax.max(child->bbmax);
	}
	loopv(va->mapmodels)
	{
		octaentities *oe = va->mapmodels[i];
		va->bbmin.min(oe->bbmin);
		va->bbmax.max(oe->bbmax);
	}
	va->bbmin.max(va->o);
	va->bbmax.min(ivec(va->o).add(va->size));

	if(va->skyfaces)
	{
		va->skyfaces |= 0x80;
		if(va->sky) loop(dim, 3) if(va->skyfaces&(3<<(2*dim)))
		{
			int r = R[dim], c = C[dim];
			if((va->skyfaces&(1<<(2*dim)) && va->o[dim] < va->bbmin[dim]) ||
			   (va->skyfaces&(2<<(2*dim)) && va->o[dim]+va->size > va->bbmax[dim]) ||
			   va->o[r] < va->bbmin[r] || va->o[r]+va->size > va->bbmax[r] ||
			   va->o[c] < va->bbmin[c] || va->o[c]+va->size > va->bbmax[c])
			{
				va->skyfaces &= ~0x80;
				break;
			}
		}
	}
}

void updatevabbs(bool force)
{
	loopv(varoot) updatevabb(varoot[i], force);
}

struct mergedface
{
	uchar orient, lmid, numverts;
	ushort mat, tex, envmap;
	vertinfo *verts;
	int tjoints;
};

#define MAXMERGELEVEL 12
static int vahasmerges = 0, vamergemax = 0;
static vector<mergedface> vamerges[MAXMERGELEVEL+1];

int genmergedfaces(cube &c, const ivec &co, int size, int minlevel = -1)
{
	if(!c.ext || isempty(c)) return -1;
	int tj = c.ext->tjoints, maxlevel = -1;
	loopi(6) if(c.merged&(1<<i))
	{
		surfaceinfo &surf = c.ext->surfaces[i];
		int numverts = surf.numverts&MAXFACEVERTS;
		if(!numverts)
		{
			if(minlevel < 0) vahasmerges |= MERGE_PART;
			continue;
		}
		mergedface mf;
		mf.orient = i;
		mf.mat = c.material;
		mf.tex = c.texture[i];
		mf.envmap = EMID_NONE;
		mf.lmid = surf.lmid[0];
		mf.numverts = surf.numverts;
		mf.verts = c.ext->verts() + surf.verts;
		mf.tjoints = -1;
		int level = calcmergedsize(i, co, size, mf.verts, mf.numverts&MAXFACEVERTS);
		if(level > minlevel)
		{
			maxlevel = max(maxlevel, level);

			while(tj >= 0 && tjoints[tj].edge < i*(MAXFACEVERTS+1)) tj = tjoints[tj].next;
			if(tj >= 0 && tjoints[tj].edge < (i+1)*(MAXFACEVERTS+1)) mf.tjoints = tj;

			VSlot &vslot = lookupvslot(mf.tex, true),
				  *layer = vslot.layer && !(c.material&MAT_ALPHA) ? &lookupvslot(vslot.layer, true) : NULL;
			if(vslot.slot->shader->type&SHADER_ENVMAP)
				mf.envmap = vslot.slot->texmask&(1<<TEX_ENVMAP) ? (int) EMID_CUSTOM : (int) closestenvmap(i, co, size);
			ushort envmap2 = layer && layer->slot->shader->type&SHADER_ENVMAP ? (int) (layer->slot->texmask&(1<<TEX_ENVMAP) ? (int) EMID_CUSTOM : (int) closestenvmap(i, co, size)) : (int) EMID_NONE;

			if(surf.numverts&LAYER_TOP) vamerges[level].add(mf);
			if(surf.numverts&LAYER_BOTTOM)
			{
				mf.tex = vslot.layer;
				mf.envmap = envmap2;
				mf.lmid = surf.lmid[1];
				mf.numverts &= ~LAYER_TOP;
				if(surf.numverts&LAYER_DUP) mf.verts += numverts;
				vamerges[level].add(mf);
			}
		}
	}
	if(maxlevel >= 0)
	{
		vamergemax = max(vamergemax, maxlevel);
		vahasmerges |= MERGE_ORIGIN;
	}
	return maxlevel;
}

int findmergedfaces(cube &c, const ivec &co, int size, int csi, int minlevel)
{
	if(c.ext && c.ext->va && !(c.ext->va->hasmerges&MERGE_ORIGIN)) return c.ext->va->mergelevel;
	else if(c.children)
	{
		int maxlevel = -1;
		loopi(8)
		{
			ivec o(i, co, size/2);
			int level = findmergedfaces(c.children[i], o, size/2, csi-1, minlevel);
			maxlevel = max(maxlevel, level);
		}
		return maxlevel;
	}
	else if(c.ext && c.merged) return genmergedfaces(c, co, size, minlevel);
	else return -1;
}

void addmergedverts(int level, const ivec &o)
{
	vector<mergedface> &mfl = vamerges[level];
	if(mfl.empty()) return;
	vec vo(ivec(o).mask(~0xFFF));
	vec pos[MAXFACEVERTS];
	loopv(mfl)
	{
		mergedface &mf = mfl[i];
		int numverts = mf.numverts&MAXFACEVERTS;
		loopi(numverts)
		{
			vertinfo &v = mf.verts[i];
			pos[i] = vec(v.x, v.y, v.z).mul(1.0f/8).add(vo);
		}
		VSlot &vslot = lookupvslot(mf.tex, true);
		addcubeverts(vslot, mf.orient, 1<<level, pos, 0, mf.tex, mf.lmid, mf.verts, numverts, mf.tjoints, mf.envmap, 0, (mf.mat&MAT_ALPHA)!=0, mf.numverts&LAYER_BLEND);
		vahasmerges |= MERGE_USE;
	}
	mfl.setsize(0);
}

void rendercube(cube &c, const ivec &co, int size, int csi, int &maxlevel)  // creates vertices and indices ready to be put into a va
{
	//if(size<=16) return;
	if(c.ext && c.ext->va)
	{
		maxlevel = max(maxlevel, c.ext->va->mergelevel);
		return;							// don't re-render
	}

	if(c.children)
	{
		neighbourstack[++neighbourdepth] = c.children;
		c.escaped = 0;
		loopi(8)
		{
			ivec o(i, co, size/2);
			int level = -1;
			rendercube(c.children[i], o, size/2, csi-1, level);
			if(level >= csi)
				c.escaped |= 1<<i;
			maxlevel = max(maxlevel, level);
		}
		--neighbourdepth;

		if(csi <= MAXMERGELEVEL && vamerges[csi].length()) addmergedverts(csi, co);

		if(c.ext)
		{
			if(c.ext->ents && c.ext->ents->mapmodels.length()) vc.mapmodels.add(c.ext->ents);
		}
		return;
	}

	genskyfaces(c, co, size);

	if(!isempty(c))
	{
		gencubeverts(c, co, size, csi);
		if(c.merged) maxlevel = max(maxlevel, genmergedfaces(c, co, size));
	}
	if(c.material != MAT_AIR) genmatsurfs(c, co, size, vc.matsurfs);

	if(c.ext)
	{
		if(c.ext->ents && c.ext->ents->mapmodels.length()) vc.mapmodels.add(c.ext->ents);
	}

	if(csi <= MAXMERGELEVEL && vamerges[csi].length()) addmergedverts(csi, co);
}

void calcgeombb(const ivec &co, int size, ivec &bbmin, ivec &bbmax)
{
	vec vmin(co), vmax = vmin;
	vmin.add(size);

	loopv(vc.verts)
	{
		const vec &v = vc.verts[i].pos;
		vmin.min(v);
		vmax.max(v);
	}

	bbmin = ivec(vmin.mul(8)).shr(3);
	bbmax = ivec(vmax.mul(8)).add(7).shr(3);
}

void calcmatbb(const ivec &co, int size, ivec &bbmin, ivec &bbmax)
{
	bbmax = co;
	(bbmin = bbmax).add(size);
	loopv(vc.matsurfs)
	{
		materialsurface &m = vc.matsurfs[i];
		switch(m.material&MATF_VOLUME)
		{
			case MAT_WATER:
			case MAT_GLASS:
			case MAT_LAVA:
				break;

			default:
				continue;
		}

		int dim = dimension(m.orient),
			r = R[dim],
			c = C[dim];
		bbmin[dim] = min(bbmin[dim], m.o[dim]);
		bbmax[dim] = max(bbmax[dim], m.o[dim]);

		bbmin[r] = min(bbmin[r], m.o[r]);
		bbmax[r] = max(bbmax[r], m.o[r] + m.rsize);

		bbmin[c] = min(bbmin[c], m.o[c]);
		bbmax[c] = max(bbmax[c], m.o[c] + m.csize);
	}
}

void setva(cube &c, const ivec &co, int size, int csi)
{
	ASSERT(size <= 0x1000);

	int vamergeoffset[MAXMERGELEVEL+1];
	loopi(MAXMERGELEVEL+1) vamergeoffset[i] = vamerges[i].length();

	vc.origin = co;
	vc.size = size;

	shadowmapmin = vec(co).add(size);
	shadowmapmax = vec(co);

	int maxlevel = -1;
	rendercube(c, co, size, csi, maxlevel);

	ivec bbmin, bbmax;

	calcgeombb(co, size, bbmin, bbmax);

	addskyverts(co, size);

	if(size == min(0x1000, worldsize/2) || !vc.emptyva())
	{
		vtxarray *va = newva(co, size);
		ext(c).va = va;
		va->geommin = bbmin;
		va->geommax = bbmax;
		calcmatbb(co, size, va->matmin, va->matmax);
		va->shadowmapmin = ivec(shadowmapmin.mul(8)).shr(3);
		va->shadowmapmax = ivec(shadowmapmax.mul(8)).add(7).shr(3);
		va->hasmerges = vahasmerges;
		va->mergelevel = vamergemax;
	}
	else
	{
		loopi(MAXMERGELEVEL+1) vamerges[i].setsize(vamergeoffset[i]);
	}

	vc.clear();
}

static inline int setcubevisibility(cube &c, const ivec &co, int size)
{
	int numvis = 0, vismask = 0, collidemask = 0, checkmask = 0;
	loopi(6)
	{
		int facemask = classifyface(c, i, co, size);
		if(facemask&1)
		{
			vismask |= 1<<i;
			if(c.merged&(1<<i))
			{
				if(c.ext && c.ext->surfaces[i].numverts&MAXFACEVERTS) numvis++;
			}
			else
			{
				numvis++;
				if(c.texture[i] != DEFAULT_SKY && !(c.ext && c.ext->surfaces[i].numverts&MAXFACEVERTS)) checkmask |= 1<<i;
			}
		}
		if(facemask&2 && collideface(c, i)) collidemask |= 1<<i;
	}
	c.visible = collidemask | (vismask ? (vismask != collidemask ? (checkmask ? 0x80|0x40 : 0x80) : 0x40) : 0);
	return numvis;
}

VARF(vafacemax, 64, 384, 256*256, allchanged());
VARF(vafacemin, 0, 96, 256*256, allchanged());
VARF(vacubesize, 32, 128, 0x1000, allchanged());

int updateva(cube *c, const ivec &co, int size, int csi)
{
	progress("recalculating geometry...");
	int ccount = 0, cmergemax = vamergemax, chasmerges = vahasmerges;
	neighbourstack[++neighbourdepth] = c;
	loopi(8)									// counting number of semi-solid/solid children cubes
	{
		int count = 0, childpos = varoot.length();
		ivec o(i, co, size);
		vamergemax = 0;
		vahasmerges = 0;
		if(c[i].ext && c[i].ext->va)
		{
			varoot.add(c[i].ext->va);
			if(c[i].ext->va->hasmerges&MERGE_ORIGIN) findmergedfaces(c[i], o, size, csi, csi);
		}
		else
		{
			if(c[i].children) count += updateva(c[i].children, o, size/2, csi-1);
			else
			{
				if(!isempty(c[i])) count += setcubevisibility(c[i], o, size);
				count += hasskyfaces(c[i], o, size);
			}
			int tcount = count + (csi <= MAXMERGELEVEL ? vamerges[csi].length() : 0);
			if(tcount > vafacemax || (tcount >= vafacemin && size >= vacubesize) || size == min(0x1000, worldsize/2))
			{
				loadprogress = clamp(recalcprogress/float(allocnodes), 0.0f, 1.0f);
				setva(c[i], o, size, csi);
				if(c[i].ext && c[i].ext->va)
				{
					while(varoot.length() > childpos)
					{
						vtxarray *child = varoot.pop();
						c[i].ext->va->children.add(child);
						child->parent = c[i].ext->va;
					}
					varoot.add(c[i].ext->va);
					if(vamergemax > size)
					{
						cmergemax = max(cmergemax, vamergemax);
						chasmerges |= vahasmerges&~MERGE_USE;
					}
					continue;
				}
				else count = 0;
			}
		}
		if(csi+1 <= MAXMERGELEVEL && vamerges[csi].length()) vamerges[csi+1].move(vamerges[csi]);
		cmergemax = max(cmergemax, vamergemax);
		chasmerges |= vahasmerges;
		ccount += count;
	}
	--neighbourdepth;
	vamergemax = cmergemax;
	vahasmerges = chasmerges;

	return ccount;
}

void addtjoint(const edgegroup &g, const cubeedge &e, int offset)
{
	int vcoord = (g.slope[g.axis]*offset + g.origin[g.axis]) & 0x7FFF;
	tjoint &tj = tjoints.add();
	tj.offset = vcoord / g.slope[g.axis];
	tj.edge = e.index;

	int prev = -1, cur = ext(*e.c).tjoints;
	while(cur >= 0)
	{
		tjoint &o = tjoints[cur];
		if(tj.edge < o.edge || (tj.edge==o.edge && (e.flags&CE_FLIP ? tj.offset > o.offset : tj.offset < o.offset))) break;
		prev = cur;
		cur = o.next;
	}

	tj.next = cur;
	if(prev < 0) e.c->ext->tjoints = tjoints.length()-1;
	else tjoints[prev].next = tjoints.length()-1;
}

void findtjoints(int cur, const edgegroup &g)
{
	int active = -1;
	while(cur >= 0)
	{
		cubeedge &e = cubeedges[cur];
		int prevactive = -1, curactive = active;
		while(curactive >= 0)
		{
			cubeedge &a = cubeedges[curactive];
			if(a.offset+a.size <= e.offset)
			{
				if(prevactive >= 0) cubeedges[prevactive].next = a.next;
				else active = a.next;
			}
			else
			{
				prevactive = curactive;
				if(!(a.flags&CE_DUP))
				{
					if(e.flags&CE_START && e.offset > a.offset && e.offset < a.offset+a.size)
						addtjoint(g, a, e.offset);
					if(e.flags&CE_END && e.offset+e.size > a.offset && e.offset+e.size < a.offset+a.size)
						addtjoint(g, a, e.offset+e.size);
				}
				if(!(e.flags&CE_DUP))
				{
					if(a.flags&CE_START && a.offset > e.offset && a.offset < e.offset+e.size)
						addtjoint(g, e, a.offset);
					if(a.flags&CE_END && a.offset+a.size > e.offset && a.offset+a.size < e.offset+e.size)
						addtjoint(g, e, a.offset+a.size);
				}
			}
			curactive = a.next;
		}
		int next = e.next;
		e.next = active;
		active = cur;
		cur = next;
	}
}

void findtjoints()
{
	recalcprogress = 0;
	gencubeedges();
	tjoints.setsize(0);
	enumeratekt(edgegroups, edgegroup, g, int, e, findtjoints(e, g));
	cubeedges.setsize(0);
	edgegroups.clear();
}

void octarender()							   // creates va s for all leaf cubes that don't already have them
{
	int csi = 0;
	while(1<<csi < worldsize) csi++;

	recalcprogress = 0;
	varoot.setsize(0);
	updateva(worldroot, ivec(0, 0, 0), worldsize/2, csi-1);
	loadprogress = 0;
	flushvbo();

	explicitsky = 0;
	skyarea = 0;
	loopv(valist)
	{
		vtxarray *va = valist[i];
		explicitsky += va->explicitsky;
		skyarea += va->skyarea;
	}

	visibleva = NULL;
}

void precachetextures()
{
	vector<int> texs;
	loopv(valist)
	{
		vtxarray *va = valist[i];
		loopj(va->texs + va->blends) if(texs.find(va->eslist[j].texture) < 0) texs.add(va->eslist[j].texture);
	}
	loopv(texs)
	{
		loadprogress = float(i+1)/texs.length();
		lookupvslot(texs[i]);
	}
	loadprogress = 0;
}

void allchanged(bool load)
{
	renderprogress(0, "clearing vertex arrays...");
	clearvas(worldroot);
	resetqueries();
	resetclipplanes();
	if(load)
	{
		setupsky();
	}
	guessshadowdir();
	entitiesinoctanodes();
	tjoints.setsize(0);
	if(filltjoints) findtjoints();
	octarender();
	if(load) precachetextures();
	setupmaterials();
	updatevabbs(true);
	lightents();
	if(load)
	{
		seedparticles();
		drawtextures();
	}
}

void recalc()
{
	allchanged(true);
}

COMMAND(recalc, "");