src/engine/octa.cpp

// core world management routines

#include "engine.h"

cube *worldroot = newcubes(F_SOLID);
int allocnodes = 0;

cubeext *growcubeext(cubeext *old, int maxverts)
{
    cubeext *ext = (cubeext *)new uchar[sizeof(cubeext) + maxverts*sizeof(vertinfo)];
    if(old)
    {
        ext->va = old->va;
        ext->ents = old->ents;
        ext->tjoints = old->tjoints;
    }
    else
    {
        ext->va = NULL;
        ext->ents = NULL;
        ext->tjoints = -1;
    }
    ext->maxverts = maxverts;
    return ext;
}

void setcubeext(cube &c, cubeext *ext)
{
    cubeext *old = c.ext;
    if(old == ext) return;
    c.ext = ext;
    if(old) delete[] (uchar *)old;
}

cubeext *newcubeext(cube &c, int maxverts, bool init)
{
    if(c.ext && c.ext->maxverts >= maxverts) return c.ext;
    cubeext *ext = growcubeext(c.ext, maxverts);
    if(init)
    {
        if(c.ext)
        {
            memcpy(ext->surfaces, c.ext->surfaces, sizeof(ext->surfaces));
            memcpy(ext->verts(), c.ext->verts(), c.ext->maxverts*sizeof(vertinfo));
        }
        else memset(ext->surfaces, 0, sizeof(ext->surfaces));
    }
    setcubeext(c, ext);
    return ext;
}

cube *newcubes(uint face, int mat)
{
    cube *c = new cube[8];
    loopi(8)
    {
        c->children = NULL;
        c->ext = NULL;
        c->visible = 0;
        c->merged = 0;
        setfaces(*c, face);
        loopl(6) c->texture[l] = DEFAULT_GEOM;
        c->material = mat;
        c++;
    }
    allocnodes++;
    return c-8;
}

int familysize(const cube &c)
{
    int size = 1;
    if(c.children) loopi(8) size += familysize(c.children[i]);
    return size;
}

void freeocta(cube *c)
{
    if(!c) return;
    loopi(8) discardchildren(c[i]);
    delete[] c;
    allocnodes--;
}

void freecubeext(cube &c)
{
    if(c.ext)
    {
        delete[] (uchar *)c.ext;
        c.ext = NULL;
    }
}

void discardchildren(cube &c, bool fixtex, int depth)
{
    c.material = MAT_AIR;
    c.visible = 0;
    c.merged = 0;
    if(c.ext)
    {
        if(c.ext->va) destroyva(c.ext->va);
        c.ext->va = NULL;
        c.ext->tjoints = -1;
        freeoctaentities(c);
        freecubeext(c);
    }
    if(c.children)
    {
        uint filled = F_EMPTY;
        loopi(8)
        {
            discardchildren(c.children[i], fixtex, depth+1);
            filled |= c.children[i].faces[0];
        }
        if(fixtex)
        {
            loopi(6) c.texture[i] = getmippedtexture(c, i);
            if(depth > 0 && filled != F_EMPTY) c.faces[0] = F_SOLID;
        }
        DELETEA(c.children);
        allocnodes--;
    }
}

void getcubevector(cube &c, int d, int x, int y, int z, ivec &p)
{
    ivec v(d, x, y, z);

    loopi(3)
        p[i] = edgeget(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]]);
}

void setcubevector(cube &c, int d, int x, int y, int z, const ivec &p)
{
    ivec v(d, x, y, z);

    loopi(3)
        edgeset(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]], p[i]);
}

static inline void getcubevector(cube &c, int i, ivec &p)
{
    p.x = edgeget(cubeedge(c, 0, (i>>R[0])&1, (i>>C[0])&1), (i>>D[0])&1);
    p.y = edgeget(cubeedge(c, 1, (i>>R[1])&1, (i>>C[1])&1), (i>>D[1])&1);
    p.z = edgeget(cubeedge(c, 2, (i>>R[2])&1, (i>>C[2])&1), (i>>D[2])&1);
}

static inline void setcubevector(cube &c, int i, const ivec &p)
{
    edgeset(cubeedge(c, 0, (i>>R[0])&1, (i>>C[0])&1), (i>>D[0])&1, p.x);
    edgeset(cubeedge(c, 1, (i>>R[1])&1, (i>>C[1])&1), (i>>D[1])&1, p.y);
    edgeset(cubeedge(c, 2, (i>>R[2])&1, (i>>C[2])&1), (i>>D[2])&1, p.z);
}

void optiface(uchar *p, cube &c)
{
    uint f = *(uint *)p;
    if(((f>>4)&0x0F0F0F0FU) == (f&0x0F0F0F0FU)) emptyfaces(c);
}

void printcube()
{
    cube &c = lookupcube(lu); // assume this is cube being pointed at
    conoutf(CON_DEBUG, "= %p = (%d, %d, %d) @ %d", (void *)&c, lu.x, lu.y, lu.z, lusize);
    conoutf(CON_DEBUG, " x  %.8x", c.faces[0]);
    conoutf(CON_DEBUG, " y  %.8x", c.faces[1]);
    conoutf(CON_DEBUG, " z  %.8x", c.faces[2]);
}

COMMAND(printcube, "");

bool isvalidcube(const cube &c)
{
    clipplanes p;
    genclipplanes(c, ivec(0, 0, 0), 256, p);
    loopi(8) // test that cube is convex
    {
        vec v = p.v[i];
        loopj(p.size) if(p.p[j].dist(v)>1e-3f) return false;
    }
    return true;
}

void validatec(cube *c, int size)
{
    loopi(8)
    {
        if(c[i].children)
        {
            if(size<=1)
            {
                solidfaces(c[i]);
                discardchildren(c[i], true);
            }
            else validatec(c[i].children, size>>1);
        }
        else if(size > 0x1000)
        {
            subdividecube(c[i], true, false);
            validatec(c[i].children, size>>1);
        }
        else
        {
            loopj(3)
            {
                uint f = c[i].faces[j], e0 = f&0x0F0F0F0FU, e1 = (f>>4)&0x0F0F0F0FU;
                if(e0 == e1 || ((e1+0x07070707U)|(e1-e0))&0xF0F0F0F0U)
                {
                    emptyfaces(c[i]);
                    break;
                }
            }
        }
    }
}

ivec lu;
int lusize;
cube &lookupcube(const ivec &to, int tsize, ivec &ro, int &rsize)
{
    int tx = clamp(to.x, 0, worldsize-1),
        ty = clamp(to.y, 0, worldsize-1),
        tz = clamp(to.z, 0, worldsize-1);
    int scale = worldscale-1, csize = abs(tsize);
    cube *c = &worldroot[octastep(tx, ty, tz, scale)];
    if(!(csize>>scale)) do
    {
        if(!c->children)
        {
            if(tsize > 0) do
            {
                subdividecube(*c);
                scale--;
                c = &c->children[octastep(tx, ty, tz, scale)];
            } while(!(csize>>scale));
            break;
        }
        scale--;
        c = &c->children[octastep(tx, ty, tz, scale)];
    } while(!(csize>>scale));
    ro = ivec(tx, ty, tz).mask(~0U<<scale);
    rsize = 1<<scale;
    return *c;
}

int lookupmaterial(const vec &v)
{
    ivec o(v);
    if(!insideworld(o)) return MAT_AIR;
    int scale = worldscale-1;
    cube *c = &worldroot[octastep(o.x, o.y, o.z, scale)];
    while(c->children)
    {
        scale--;
        c = &c->children[octastep(o.x, o.y, o.z, scale)];
    }
    return c->material;
}

const cube *neighbourstack[32];
int neighbourdepth = -1;

const cube &neighbourcube(const cube &c, int orient, const ivec &co, int size, ivec &ro, int &rsize)
{
    ivec n = co;
    int dim = dimension(orient);
    uint diff = n[dim];
    if(dimcoord(orient)) n[dim] += size; else n[dim] -= size;
    diff ^= n[dim];
    if(diff >= uint(worldsize)) { ro = n; rsize = size; return c; }
    int scale = worldscale;
    const cube *nc = worldroot;
    if(neighbourdepth >= 0)
    {
        scale -= neighbourdepth + 1;
        diff >>= scale;
        do { scale++; diff >>= 1; } while(diff);
        nc = neighbourstack[worldscale - scale];
    }
    scale--;
    nc = &nc[octastep(n.x, n.y, n.z, scale)];
    if(!(size>>scale) && nc->children) do
    {
        scale--;
        nc = &nc->children[octastep(n.x, n.y, n.z, scale)];
    } while(!(size>>scale) && nc->children);
    ro = n.mask(~0U<<scale);
    rsize = 1<<scale;
    return *nc;
}

////////// (re)mip //////////

int getmippedtexture(const cube &p, int orient)
{
    cube *c = p.children;
    int d = dimension(orient), dc = dimcoord(orient), texs[4] = { -1, -1, -1, -1 }, numtexs = 0;
    loop(x, 2) loop(y, 2)
    {
        int n = octaindex(d, x, y, dc);
        if(isempty(c[n]))
        {
            n = oppositeocta(d, n);
            if(isempty(c[n]))
                continue;
        }
        int tex = c[n].texture[orient];
        if(tex > DEFAULT_SKY) loopi(numtexs) if(texs[i] == tex) return tex;
        texs[numtexs++] = tex;
    }
    loopirev(numtexs) if(!i || texs[i] > DEFAULT_SKY) return texs[i];
    return DEFAULT_GEOM;
}

void forcemip(cube &c, bool fixtex)
{
    cube *ch = c.children;
    emptyfaces(c);

    loopi(8) loopj(8)
    {
        int n = i^(j==3 ? 4 : (j==4 ? 3 : j));
        if(!isempty(ch[n])) // breadth first search for cube near vert
        {
            ivec v;
            getcubevector(ch[n], i, v);
            // adjust vert to parent size
            setcubevector(c, i, ivec(n, v, 8).shr(1));
            break;
        }
    }

    if(fixtex) loopj(6)
        c.texture[j] = getmippedtexture(c, j);
}

static int midedge(const ivec &a, const ivec &b, int xd, int yd, bool &perfect)
{
    int ax = a[xd], ay = a[yd], bx = b[xd], by = b[yd];
    if(ay==by) return ay;
    if(ax==bx) { perfect = false; return ay; }
    bool crossx = (ax<8 && bx>8) || (ax>8 && bx<8);
    bool crossy = (ay<8 && by>8) || (ay>8 && by<8);
    if(crossy && !crossx) { midedge(a,b,yd,xd,perfect); return 8; } // to test perfection
    if(ax<=8 && bx<=8) return ax>bx ? ay : by;
    if(ax>=8 && bx>=8) return ax<bx ? ay : by;
    int risex = (by-ay)*(8-ax)*256;
    int s = risex/(bx-ax);
    int y = s/256 + ay;
    if(((abs(s)&0xFF)!=0) || // ie: rounding error
        (crossy && y!=8) ||
        (y<0 || y>16)) perfect = false;
    return crossy ? 8 : min(max(y, 0), 16);
}

static inline bool crosscenter(const ivec &a, const ivec &b, int xd, int yd)
{
    int ax = a[xd], ay = a[yd], bx = b[xd], by = b[yd];
    return (((ax <= 8 && bx <= 8) || (ax >= 8 && bx >= 8)) &&
            ((ay <= 8 && by <= 8) || (ay >= 8 && by >= 8))) ||
           (ax + bx == 16 && ay + by == 16);
}

bool subdividecube(cube &c, bool fullcheck, bool brighten)
{
    if(c.children) return true;
    if(c.ext) memset(c.ext->surfaces, 0, sizeof(c.ext->surfaces));
	if(isempty(c) || isentirelysolid(c))
    {
		c.children = newcubes(isempty(c) ? F_EMPTY : F_SOLID, c.material);
        loopi(8)
        {
            loopl(6) c.children[i].texture[l] = c.texture[l];
            if(brighten && !isempty(c)) brightencube(c.children[i]);
        }
        return true;
    }
    cube *ch = c.children = newcubes(F_SOLID, c.material);
    bool perfect = true;
    ivec v[8];
    loopi(8)
    {
        getcubevector(c, i, v[i]);
        v[i].mul(2);
    }

    loopj(6)
    {
        int d = dimension(j), z = dimcoord(j);
        const ivec &v00 = v[octaindex(d, 0, 0, z)],
                   &v10 = v[octaindex(d, 1, 0, z)],
                   &v01 = v[octaindex(d, 0, 1, z)],
                   &v11 = v[octaindex(d, 1, 1, z)];
        int e[3][3];
        // corners
        e[0][0] = v00[d];
        e[0][2] = v01[d];
        e[2][0] = v10[d];
        e[2][2] = v11[d];
        // edges
        e[0][1] = midedge(v00, v01, C[d], d, perfect);
        e[1][0] = midedge(v00, v10, R[d], d, perfect);
        e[1][2] = midedge(v11, v01, R[d], d, perfect);
        e[2][1] = midedge(v11, v10, C[d], d, perfect);
        // center
        bool p1 = perfect, p2 = perfect;
        int c1 = midedge(v00, v11, R[d], d, p1);
        int c2 = midedge(v01, v10, R[d], d, p2);
        if(z ? c1 > c2 : c1 < c2)
        {
            e[1][1] = c1;
            perfect = p1 && (c1 == c2 || crosscenter(v00, v11, C[d], R[d]));
        }
        else
        {
            e[1][1] = c2;
            perfect = p2 && (c1 == c2 || crosscenter(v01, v10, C[d], R[d]));
        }

        loopi(8)
        {
            ch[i].texture[j] = c.texture[j];
            int rd = (i>>R[d])&1, cd = (i>>C[d])&1, dd = (i>>D[d])&1;
            edgeset(cubeedge(ch[i], d, 0, 0), z, clamp(e[rd][cd] - dd*8, 0, 8));
            edgeset(cubeedge(ch[i], d, 1, 0), z, clamp(e[1+rd][cd] - dd*8, 0, 8));
            edgeset(cubeedge(ch[i], d, 0, 1), z, clamp(e[rd][1+cd] - dd*8, 0, 8));
            edgeset(cubeedge(ch[i], d, 1, 1), z, clamp(e[1+rd][1+cd] - dd*8, 0, 8));
        }
    }

    validatec(ch);
    if(fullcheck) loopi(8) if(!isvalidcube(ch[i])) // not so good...
    {
        emptyfaces(ch[i]);
        perfect=false;
    }
    if(brighten) loopi(8) if(!isempty(ch[i])) brightencube(ch[i]);
    return perfect;
}

bool crushededge(uchar e, int dc) { return dc ? e==0 : e==0x88; }

int visibleorient(const cube &c, int orient)
{
    loopi(2)
    {
        int a = faceedgesidx[orient][i*2 + 0];
        int b = faceedgesidx[orient][i*2 + 1];
        loopj(2)
        {
            if(crushededge(c.edges[a],j) &&
               crushededge(c.edges[b],j) &&
                touchingface(c, orient)) return ((a>>2)<<1) + j;
        }
    }
    return orient;
}

VAR(mipvis, 0, 0, 1);

static int remipprogress = 0, remiptotal = 0;

bool remip(cube &c, const ivec &co, int size)
{
    cube *ch = c.children;
    if(!ch)
    {
        if(size<<1 <= 0x1000) return true;
        subdividecube(c);
        ch = c.children;
    }
    else if((remipprogress++&0xFFF)==1) renderprogress(float(remipprogress)/remiptotal, "remipping...");

    bool perfect = true;
    loopi(8)
    {
        ivec o(i, co, size);
        if(!remip(ch[i], o, size>>1)) perfect = false;
    }

    solidfaces(c); // so texmip is more consistent
    loopj(6)
        c.texture[j] = getmippedtexture(c, j); // parents get child texs regardless

    if(!perfect) return false;
    if(size<<1 > 0x1000) return false;

    ushort mat = MAT_AIR;
    loopi(8)
    {
        mat = ch[i].material;
        if((mat&MATF_CLIP) == MAT_NOCLIP || mat&MAT_ALPHA)
        {
            if(i > 0) return false;
            while(++i < 8) if(ch[i].material != mat) return false;
            break;
        }
        else if(!isentirelysolid(ch[i]))
        {
            while(++i < 8)
            {
                int omat = ch[i].material;
                if(isentirelysolid(ch[i]) ? (omat&MATF_CLIP) == MAT_NOCLIP || omat&MAT_ALPHA : mat != omat) return false;
            }
            break;
        }
    }

    cube n = c;
    n.ext = NULL;
    forcemip(n);
    n.children = NULL;
    if(!subdividecube(n, false, false))
        { freeocta(n.children); return false; }

    cube *nh = n.children;
    uchar vis[6] = {0, 0, 0, 0, 0, 0};
    loopi(8)
    {
        if(ch[i].faces[0] != nh[i].faces[0] ||
           ch[i].faces[1] != nh[i].faces[1] ||
           ch[i].faces[2] != nh[i].faces[2])
            { freeocta(nh); return false; }

        if(isempty(ch[i]) && isempty(nh[i])) continue;

        ivec o(i, co, size);
        loop(orient, 6)
            if(visibleface(ch[i], orient, o, size, MAT_AIR, (mat&MAT_ALPHA)^MAT_ALPHA, MAT_ALPHA))
            {
                if(ch[i].texture[orient] != n.texture[orient]) { freeocta(nh); return false; }
                vis[orient] |= 1<<i;
            }
    }
    if(mipvis) loop(orient, 6)
    {
        int mask = 0;
        loop(x, 2) loop(y, 2) mask |= 1<<octaindex(dimension(orient), x, y, dimcoord(orient));
        if(vis[orient]&mask && (vis[orient]&mask)!=mask) { freeocta(nh); return false; }
    }

    freeocta(nh);
    discardchildren(c);
    loopi(3) c.faces[i] = n.faces[i];
    c.material = mat;
    loopi(6) if(vis[i]) c.visible |= 1<<i;
    if(c.visible) c.visible |= 0x40;
    brightencube(c);
    return true;
}

void mpremip(bool local)
{
    extern selinfo sel;
    if(local) game::edittrigger(sel, EDIT_REMIP);
    remipprogress = 1;
    remiptotal = allocnodes;
    loopi(8)
    {
        ivec o(i, ivec(0, 0, 0), worldsize>>1);
        remip(worldroot[i], o, worldsize>>2);
    }
    calcmerges();
    if(!local) allchanged();
}

void remip_()
{
    mpremip(true);
    allchanged();
}

COMMANDN(remip, remip_, "");

static inline int edgeval(cube &c, const ivec &p, int dim, int coord)
{
    return edgeget(cubeedge(c, dim, p[R[dim]]>>3, p[C[dim]]>>3), coord);
}

void genvertp(cube &c, ivec &p1, ivec &p2, ivec &p3, plane &pl, bool solid = false)
{
    int dim = 0;
    if(p1.y==p2.y && p2.y==p3.y) dim = 1;
    else if(p1.z==p2.z && p2.z==p3.z) dim = 2;

    int coord = p1[dim];
    ivec v1(p1), v2(p2), v3(p3);
    v1[dim] = solid ? coord*8 : edgeval(c, p1, dim, coord);
    v2[dim] = solid ? coord*8 : edgeval(c, p2, dim, coord);
    v3[dim] = solid ? coord*8 : edgeval(c, p3, dim, coord);

    pl.toplane(vec(v1), vec(v2), vec(v3));
}

static bool threeplaneintersect(plane &pl1, plane &pl2, plane &pl3, vec &dest)
{
    vec &t1 = dest, t2, t3, t4;
    t1.cross(pl1, pl2); t4 = t1; t1.mul(pl3.offset);
    t2.cross(pl3, pl1);          t2.mul(pl2.offset);
    t3.cross(pl2, pl3);          t3.mul(pl1.offset);
    t1.add(t2);
    t1.add(t3);
    t1.mul(-1);
    float d = t4.dot(pl3);
    if(d==0) return false;
    t1.div(d);
    return true;
}

static void genedgespanvert(ivec &p, cube &c, vec &v)
{
    ivec p1(8-p.x, p.y, p.z);
    ivec p2(p.x, 8-p.y, p.z);
    ivec p3(p.x, p.y, 8-p.z);

    plane plane1, plane2, plane3;
    genvertp(c, p, p1, p2, plane1);
    genvertp(c, p, p2, p3, plane2);
    genvertp(c, p, p3, p1, plane3);
    if(plane1==plane2) genvertp(c, p, p1, p2, plane1, true);
    if(plane1==plane3) genvertp(c, p, p1, p2, plane1, true);
    if(plane2==plane3) genvertp(c, p, p2, p3, plane2, true);

    ASSERT(threeplaneintersect(plane1, plane2, plane3, v));
    //ASSERT(v.x>=0 && v.x<=8);
    //ASSERT(v.y>=0 && v.y<=8);
    //ASSERT(v.z>=0 && v.z<=8);
    v.x = max(0.0f, min(8.0f, v.x));
    v.y = max(0.0f, min(8.0f, v.y));
    v.z = max(0.0f, min(8.0f, v.z));
}

void edgespan2vectorcube(cube &c)
{
    if(isentirelysolid(c) || isempty(c)) return;
    cube o = c;
    loop(x, 2) loop(y, 2) loop(z, 2)
    {
        ivec p(8*x, 8*y, 8*z);
        vec v;
        genedgespanvert(p, o, v);

        edgeset(cubeedge(c, 0, y, z), x, int(v.x+0.49f));
        edgeset(cubeedge(c, 1, z, x), y, int(v.y+0.49f));
        edgeset(cubeedge(c, 2, x, y), z, int(v.z+0.49f));
    }
}

const ivec cubecoords[8] = // verts of bounding cube
{
#define GENCUBEVERT(n, x, y, z) ivec(x, y, z),
    GENCUBEVERTS(0, 8, 0, 8, 0, 8)
#undef GENCUBEVERT
};

template<class T>
static inline void gencubevert(const cube &c, int i, T &v)
{
    switch(i)
    {
        default:
#define GENCUBEVERT(n, x, y, z) \
        case n: \
            v = T(edgeget(cubeedge(c, 0, y, z), x), \
                  edgeget(cubeedge(c, 1, z, x), y), \
                  edgeget(cubeedge(c, 2, x, y), z)); \
            break;
        GENCUBEVERTS(0, 1, 0, 1, 0, 1)
#undef GENCUBEVERT
    }
}

void genfaceverts(const cube &c, int orient, ivec v[4])
{
    switch(orient)
    {
        default:
#define GENFACEORIENT(o, v0, v1, v2, v3) \
        case o: v0 v1 v2 v3 break;
#define GENFACEVERT(o, n, x,y,z, xv,yv,zv) \
            v[n] = ivec(edgeget(cubeedge(c, 0, y, z), x), \
                        edgeget(cubeedge(c, 1, z, x), y), \
                        edgeget(cubeedge(c, 2, x, y), z));
        GENFACEVERTS(0, 1, 0, 1, 0, 1, , , , , , )
    #undef GENFACEORIENT
    #undef GENFACEVERT
    }
}

const ivec facecoords[6][4] =
{
#define GENFACEORIENT(o, v0, v1, v2, v3) \
    { v0, v1, v2, v3 },
#define GENFACEVERT(o, n, x,y,z, xv,yv,zv) \
        ivec(x,y,z)
    GENFACEVERTS(0, 8, 0, 8, 0, 8, , , , , , )
#undef GENFACEORIENT
#undef GENFACEVERT
};

const uchar fv[6][4] = // indexes for cubecoords, per each vert of a face orientation
{
    { 2, 1, 6, 5 },
    { 3, 4, 7, 0 },
    { 4, 5, 6, 7 },
    { 1, 2, 3, 0 },
    { 6, 1, 0, 7 },
    { 5, 4, 3, 2 },
};

const uchar fvmasks[64] = // mask of verts used given a mask of visible face orientations
{
    0x00, 0x66, 0x99, 0xFF, 0xF0, 0xF6, 0xF9, 0xFF,
    0x0F, 0x6F, 0x9F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0xC3, 0xE7, 0xDB, 0xFF, 0xF3, 0xF7, 0xFB, 0xFF,
    0xCF, 0xEF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0x3C, 0x7E, 0xBD, 0xFF, 0xFC, 0xFE, 0xFD, 0xFF,
    0x3F, 0x7F, 0xBF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
};

const uchar faceedgesidx[6][4] = // ordered edges surrounding each orient
{//0..1 = row edges, 2..3 = column edges
    { 4,  5,  8, 10 },
    { 6,  7,  9, 11 },
    { 8,  9,  0, 2 },
    { 10, 11, 1, 3 },
    { 0,  1,  4, 6 },
    { 2,  3,  5, 7 },
};

bool flataxisface(const cube &c, int orient)
{
    uint face = c.faces[dimension(orient)];
    if(dimcoord(orient)) face >>= 4;
    return (face&0x0F0F0F0F) == 0x01010101*(face&0x0F);
}

bool collideface(const cube &c, int orient)
{
    if(flataxisface(c, orient))
    {
        uchar r1 = c.edges[faceedgesidx[orient][0]], r2 = c.edges[faceedgesidx[orient][1]];
        if(uchar((r1>>4)|(r2&0xF0)) == uchar((r1&0x0F)|(r2<<4))) return false;
        uchar c1 = c.edges[faceedgesidx[orient][2]], c2 = c.edges[faceedgesidx[orient][3]];
        if(uchar((c1>>4)|(c2&0xF0)) == uchar((c1&0x0F)|(c2<<4))) return false;
    }
    return true;
}

bool touchingface(const cube &c, int orient)
{
    uint face = c.faces[dimension(orient)];
    return dimcoord(orient) ? (face&0xF0F0F0F0)==0x80808080 : (face&0x0F0F0F0F)==0;
}

bool notouchingface(const cube &c, int orient)
{
    uint face = c.faces[dimension(orient)];
    return dimcoord(orient) ? (face&0x80808080)==0 : ((0x88888888-face)&0x08080808) == 0;
}

int faceconvexity(const ivec v[4])
{
    ivec n;
    n.cross(ivec(v[1]).sub(v[0]), ivec(v[2]).sub(v[0]));
    return ivec(v[0]).sub(v[3]).dot(n);
    // 1 if convex, -1 if concave, 0 if flat
}

int faceconvexity(const vertinfo *verts, int numverts, int size)
{
    if(numverts < 4) return 0;
    ivec v0 = verts[0].getxyz(),
         e1 = verts[1].getxyz().sub(v0),
         e2 = verts[2].getxyz().sub(v0),
         n;
    if(size >= (8<<5))
    {
        if(size >= (8<<10)) n.cross(e1.shr(10), e2.shr(10));
        else n.cross(e1, e2).shr(10);
    }
    else n.cross(e1, e2);
    return verts[3].getxyz().sub(v0).dot(n);
}

int faceconvexity(const ivec v[4], int &vis)
{
    ivec e1, e2, e3, n;
    n.cross((e1 = v[1]).sub(v[0]), (e2 = v[2]).sub(v[0]));
    int convex = (e3 = v[0]).sub(v[3]).dot(n);
    if(!convex)
    {
        if(ivec().cross(e3, e2).iszero()) { if(!n.iszero()) vis = 1; }
        else if(n.iszero()) { vis = 2; }
        return 0;
    }
    return convex;
}

int faceconvexity(const cube &c, int orient)
{
    if(flataxisface(c, orient)) return 0;
    ivec v[4];
    genfaceverts(c, orient, v);
    return faceconvexity(v);
}

int faceorder(const cube &c, int orient) // gets above 'fv' so that each face is convex
{
    return faceconvexity(c, orient)<0 ? 1 : 0;
}

static inline void faceedges(const cube &c, int orient, uchar edges[4])
{
    loopk(4) edges[k] = c.edges[faceedgesidx[orient][k]];
}

uint faceedges(const cube &c, int orient)
{
    union { uchar edges[4]; uint face; } u;
    faceedges(c, orient, u.edges);
    return u.face;
}

static inline int genfacevecs(const cube &cu, int orient, const ivec &pos, int size, bool solid, ivec2 *fvecs, const ivec *v = NULL)
{
    int i = 0;
    if(solid)
    {
        switch(orient)
        {
        #define GENFACEORIENT(orient, v0, v1, v2, v3) \
            case orient: \
            { \
                if(dimcoord(orient)) { v0 v1 v2 v3 } else { v3 v2 v1 v0 } \
                break; \
            }
        #define GENFACEVERT(orient, vert, xv,yv,zv, x,y,z) \
            { ivec2 &f = fvecs[i]; x ((xv)<<3); y ((yv)<<3); z ((zv)<<3); i++; }
            GENFACEVERTS(pos.x, pos.x+size, pos.y, pos.y+size, pos.z, pos.z+size, f.x = , f.x = , f.y = , f.y = , (void), (void))
        #undef GENFACEVERT
        }
        return 4;
    }
    ivec buf[4];
    if(!v) { genfaceverts(cu, orient, buf); v = buf; }
    ivec2 prev(INT_MAX, INT_MAX);
    switch(orient)
    {
    #define GENFACEVERT(orient, vert, sx,sy,sz, dx,dy,dz) \
        { \
            const ivec &e = v[vert]; \
            ivec ef; \
            ef.dx = e.sx; ef.dy = e.sy; ef.dz = e.sz; \
            if(ef.z == dimcoord(orient)*8) \
            { \
                ivec2 &f = fvecs[i]; \
                ivec pf; \
                pf.dx = pos.sx; pf.dy = pos.sy; pf.dz = pos.sz; \
                f = ivec2(ef.x*size + (pf.x<<3), ef.y*size + (pf.y<<3)); \
                if(f != prev) { prev = f; i++; } \
            } \
        }
        GENFACEVERTS(x, x, y, y, z, z, x, x, y, y, z, z)
    #undef GENFACEORIENT
    #undef GENFACEVERT
    }
    if(fvecs[0] == prev) i--;
    return i;
}

static inline int clipfacevecy(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 &r)
{
    if(dir.x >= 0)
    {
        if(cx <= o.x || cx >= o.x+dir.x) return 0;
    }
    else if(cx <= o.x+dir.x || cx >= o.x) return 0;

    int t = (o.y-cy) + (cx-o.x)*dir.y/dir.x;
    if(t <= 0 || t >= size) return 0;

    r.x = cx;
    r.y = cy + t;
    return 1;
}

static inline int clipfacevecx(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 &r)
{
    if(dir.y >= 0)
    {
        if(cy <= o.y || cy >= o.y+dir.y) return 0;
    }
    else if(cy <= o.y+dir.y || cy >= o.y) return 0;

    int t = (o.x-cx) + (cy-o.y)*dir.x/dir.y;
    if(t <= 0 || t >= size) return 0;

    r.x = cx + t;
    r.y = cy;
    return 1;
}

static inline int clipfacevec(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 *rvecs)
{
    int r = 0;

    if(o.x >= cx && o.x <= cx+size &&
       o.y >= cy && o.y <= cy+size &&
       ((o.x != cx && o.x != cx+size) || (o.y != cy && o.y != cy+size)))
    {
        rvecs[0].x = o.x;
        rvecs[0].y = o.y;
        r++;
    }

    r += clipfacevecx(o, dir, cx, cy, size, rvecs[r]);
    r += clipfacevecx(o, dir, cx, cy+size, size, rvecs[r]);
    r += clipfacevecy(o, dir, cx, cy, size, rvecs[r]);
    r += clipfacevecy(o, dir, cx+size, cy, size, rvecs[r]);

    ASSERT(r <= 2);
    return r;
}

static inline bool insideface(const ivec2 *p, int nump, const ivec2 *o, int numo)
{
    int bounds = 0;
    ivec2 prev = o[numo-1];
    loopi(numo)
    {
        const ivec2 &cur = o[i];
        ivec2 dir(cur.x-prev.x, cur.y-prev.y);
        int offset = dir.x*prev.y - dir.y*prev.x;
        loopj(nump) if(dir.x*p[j].y - dir.y*p[j].x > offset) return false;
        bounds++;
        prev = cur;
    }
    return bounds>=3;
}

static inline int clipfacevecs(const ivec2 *o, int numo, int cx, int cy, int size, ivec2 *rvecs)
{
    cx <<= 3;
    cy <<= 3;
    size <<= 3;

    int r = 0;
    ivec2 prev = o[numo-1];
    loopi(numo)
    {
        const ivec2 &cur = o[i];
        r += clipfacevec(prev, ivec2(cur.x-prev.x, cur.y-prev.y), cx, cy, size, &rvecs[r]);
        prev = cur;
    }
    ivec2 corner[4] = {ivec2(cx, cy), ivec2(cx+size, cy), ivec2(cx+size, cy+size), ivec2(cx, cy+size)};
    loopi(4) if(insideface(&corner[i], 1, o, numo)) rvecs[r++] = corner[i];
    ASSERT(r <= 8);
    return r;
}

bool collapsedface(const cube &c, int orient)
{
    int e0 = c.edges[faceedgesidx[orient][0]], e1 = c.edges[faceedgesidx[orient][1]],
        e2 = c.edges[faceedgesidx[orient][2]], e3 = c.edges[faceedgesidx[orient][3]],
        face = dimension(orient)*4,
        f0 = c.edges[face+0], f1 = c.edges[face+1],
        f2 = c.edges[face+2], f3 = c.edges[face+3];
    if(dimcoord(orient)) { f0 >>= 4; f1 >>= 4; f2 >>= 4; f3 >>= 4; }
    else { f0 &= 0xF; f1 &= 0xF; f2 &= 0xF; f3 &= 0xF; }
    ivec v0(e0&0xF, e2&0xF, f0),
         v1(e0>>4, e3&0xF, f1),
         v2(e1>>4, e3>>4, f3),
         v3(e1&0xF, e2>>4, f2);
    return ivec().cross(v1.sub(v0), v2.sub(v0)).iszero() &&
           ivec().cross(v2, v3.sub(v0)).iszero();
}

static inline bool occludesface(const cube &c, int orient, const ivec &o, int size, const ivec &vo, int vsize, ushort vmat, ushort nmat, ushort matmask, const ivec2 *vf, int numv)
{
    int dim = dimension(orient);
    if(!c.children)
    {
         if(nmat != MAT_AIR && (c.material&matmask) == nmat)
         {
            ivec2 nf[8];
            return clipfacevecs(vf, numv, o[C[dim]], o[R[dim]], size, nf) < 3;
         }
         if(isentirelysolid(c)) return true;
         if(vmat != MAT_AIR && ((c.material&matmask) == vmat || (isliquid(vmat) && isclipped(c.material&MATF_VOLUME)))) return true;
         if(touchingface(c, orient) && faceedges(c, orient) == F_SOLID) return true;
         ivec2 cf[8];
         int numc = clipfacevecs(vf, numv, o[C[dim]], o[R[dim]], size, cf);
         if(numc < 3) return true;
         if(isempty(c) || notouchingface(c, orient)) return false;
         ivec2 of[4];
         int numo = genfacevecs(c, orient, o, size, false, of);
         return numo >= 3 && insideface(cf, numc, of, numo);
    }

    size >>= 1;
    int coord = dimcoord(orient);
    loopi(8) if(octacoord(dim, i) == coord)
    {
        if(!occludesface(c.children[i], orient, ivec(i, o, size), size, vo, vsize, vmat, nmat, matmask, vf, numv)) return false;
    }

    return true;
}

bool visibleface(const cube &c, int orient, const ivec &co, int size, ushort mat, ushort nmat, ushort matmask)
{
    if(mat != MAT_AIR)
    {
        if(faceedges(c, orient)==F_SOLID && touchingface(c, orient)) return false;
    }
    else
    {
        if(collapsedface(c, orient)) return false;
        if(!touchingface(c, orient)) return true;
    }

    ivec no;
    int nsize;
    const cube &o = neighbourcube(c, orient, co, size, no, nsize);
    if(&o==&c) return false;

    int opp = opposite(orient);
    if(nsize > size || (nsize == size && !o.children))
    {
        if(nmat != MAT_AIR && (o.material&matmask) == nmat) return true;
        if(isentirelysolid(o)) return false;
        if(mat != MAT_AIR && ((o.material&matmask) == mat || (isliquid(mat) && (o.material&MATF_VOLUME) == MAT_GLASS))) return false;
        if(isempty(o) || notouchingface(o, opp)) return true;
        if(touchingface(o, opp) && faceedges(o, opp) == F_SOLID) return false;

        ivec vo = ivec(co).mask(0xFFF);
        no.mask(0xFFF);
        ivec2 cf[4], of[4];
        int numc = genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf),
            numo = genfacevecs(o, opp, no, nsize, false, of);
        return numo < 3 || !insideface(cf, numc, of, numo);
    }


    ivec vo = ivec(co).mask(0xFFF);
    no.mask(0xFFF);
    ivec2 cf[4];
    int numc = genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf);
    return !occludesface(o, opp, no, nsize, vo, size, mat, nmat, matmask, cf, numc);
}

int classifyface(const cube &c, int orient, const ivec &co, int size)
{
    if(collapsedface(c, orient)) return 0;
    int vismask = (c.material&MATF_CLIP) == MAT_NOCLIP ? 1 : 3;
    if(!touchingface(c, orient)) return vismask;

    ivec no;
    int nsize;
    const cube &o = neighbourcube(c, orient, co, size, no, nsize);
    if(&o==&c) return 0;

    int vis = 0, opp = opposite(orient);
    if(nsize > size || (nsize == size && !o.children))
    {
        if((~c.material & o.material) & MAT_ALPHA) vis |= 1;
        if((o.material&MATF_CLIP) == MAT_NOCLIP) vis |= vismask&2;
        if(vis == vismask || isentirelysolid(o)) return vis;
        if(isempty(o) || notouchingface(o, opp)) return vismask;
        if(touchingface(o, opp) && faceedges(o, opp) == F_SOLID) return vis;

        ivec vo = ivec(co).mask(0xFFF);
        no.mask(0xFFF);
        ivec2 cf[4], of[4];
        int numc = genfacevecs(c, orient, vo, size, false, cf),
            numo = genfacevecs(o, opp, no, nsize, false, of);
        if(numo < 3 || !insideface(cf, numc, of, numo)) return vismask;
        return vis;
    }

    ivec vo = ivec(co).mask(0xFFF);
    no.mask(0xFFF);
    ivec2 cf[4];
    int numc = genfacevecs(c, orient, vo, size, false, cf);
    if(!occludesface(o, opp, no, nsize, vo, size, MAT_AIR, (c.material&MAT_ALPHA)^MAT_ALPHA, MAT_ALPHA, cf, numc)) vis |= 1;
    if(vismask&2 && !occludesface(o, opp, no, nsize, vo, size, MAT_AIR, MAT_NOCLIP, MATF_CLIP, cf, numc)) vis |= 2;
    return vis;
}

// more expensive version that checks both triangles of a face independently
int visibletris(const cube &c, int orient, const ivec &co, int size, ushort nmat, ushort matmask)
{
    int vis = 3, touching = 0xF;
    ivec v[4], e1, e2, e3, n;
    genfaceverts(c, orient, v);
    n.cross((e1 = v[1]).sub(v[0]), (e2 = v[2]).sub(v[0]));
    int convex = (e3 = v[0]).sub(v[3]).dot(n);
    if(!convex)
    {
        if(ivec().cross(e3, e2).iszero() || v[1] == v[3]) { if(n.iszero()) return 0; vis = 1; touching = 0xF&~(1<<3); }
        else if(n.iszero()) { vis = 2; touching = 0xF&~(1<<1); }
    }

    int dim = dimension(orient), coord = dimcoord(orient);
    if(v[0][dim] != coord*8) touching &= ~(1<<0);
    if(v[1][dim] != coord*8) touching &= ~(1<<1);
    if(v[2][dim] != coord*8) touching &= ~(1<<2);
    if(v[3][dim] != coord*8) touching &= ~(1<<3);
    static const int notouchmasks[2][16] = // mask of triangles not touching
    { // order 0: flat or convex
       // 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
        { 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 1, 3, 0 },
      // order 1: concave
        { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3, 2, 0 },
    };
    int order = convex < 0 ? 1 : 0, notouch = notouchmasks[order][touching];
    if((vis&notouch)==vis) return vis;

    ivec no;
    int nsize;
    const cube &o = neighbourcube(c, orient, co, size, no, nsize);
    if(&o==&c) return 0;

    if((c.material&matmask) == nmat) nmat = MAT_AIR;

    ivec vo = ivec(co).mask(0xFFF);
    no.mask(0xFFF);
    ivec2 cf[4], of[4];
    int opp = opposite(orient), numo = 0, numc;
    if(nsize > size || (nsize == size && !o.children))
    {
        if(isempty(o) || notouchingface(o, opp)) return vis;
        if(nmat != MAT_AIR && (o.material&matmask) == nmat) return vis;
        if(isentirelysolid(o) || (touchingface(o, opp) && faceedges(o, opp) == F_SOLID)) return vis&notouch;

        numc = genfacevecs(c, orient, vo, size, false, cf, v);
        numo = genfacevecs(o, opp, no, nsize, false, of);
        if(numo < 3) return vis;
        if(insideface(cf, numc, of, numo)) return vis&notouch;
    }
    else
    {
        numc = genfacevecs(c, orient, vo, size, false, cf, v);
        if(occludesface(o, opp, no, nsize, vo, size, MAT_AIR, nmat, matmask, cf, numc)) return vis&notouch;
    }
    if(vis != 3 || notouch) return vis;

    static const int triverts[2][2][2][3] =
    { // order
        { // coord
            { { 1, 2, 3 }, { 0, 1, 3 } }, // verts
            { { 0, 1, 2 }, { 0, 2, 3 } }
        },
        { // coord
            { { 0, 1, 2 }, { 3, 0, 2 } }, // verts
            { { 1, 2, 3 }, { 1, 3, 0 } }
        }
    };

    do
    {
        loopi(2)
        {
            const int *verts = triverts[order][coord][i];
            ivec2 tf[3] = { cf[verts[0]], cf[verts[1]], cf[verts[2]] };
            if(numo > 0) { if(!insideface(tf, 3, of, numo)) continue; }
            else if(!occludesface(o, opp, no, nsize, vo, size, MAT_AIR, nmat, matmask, tf, 3)) continue;
            return vis & ~(1<<i);
        }
        vis |= 4;
    } while(++order <= 1);

    return 3;
}

void calcvert(const cube &c, const ivec &co, int size, ivec &v, int i, bool solid)
{
    if(solid) v = cubecoords[i]; else gencubevert(c, i, v);
    // avoid overflow
    if(size>=8) v.mul(size/8);
    else v.div(8/size);
    v.add(ivec(co).shl(3));
}

void calcvert(const cube &c, const ivec &co, int size, vec &v, int i, bool solid)
{
    if(solid) v = vec(cubecoords[i]); else gencubevert(c, i, v);
    v.mul(size/8.0f).add(vec(co));
}

int genclipplane(const cube &c, int orient, vec *v, plane *clip)
{
    int planes = 0, convex = faceconvexity(c, orient), order = convex < 0 ? 1 : 0;
    const vec &v0 = v[fv[orient][order]], &v1 = v[fv[orient][order+1]], &v2 = v[fv[orient][order+2]], &v3 = v[fv[orient][(order+3)&3]];
    if(v0==v2) return 0;
    if(v0!=v1 && v1!=v2) clip[planes++].toplane(v0, v1, v2);
    if(v0!=v3 && v2!=v3 && (!planes || convex)) clip[planes++].toplane(v0, v2, v3);
    return planes;
}

void genclipplanes(const cube &c, const ivec &co, int size, clipplanes &p, bool collide)
{
    // generate tight bounding box
    calcvert(c, co, size, p.v[0], 0);
    vec mx = p.v[0], mn = p.v[0];
    for(int i = 1; i < 8; i++)
    {
        calcvert(c, co, size, p.v[i], i);
        mx.max(p.v[i]);
        mn.min(p.v[i]);
    }

    p.r = mx.sub(mn).mul(0.5f);
    p.o = mn.add(p.r);

    p.size = 0;
    p.visible = 0;
    if(collide || (c.visible&0xC0) == 0x40)
    {
        loopi(6) if(c.visible&(1<<i))
        {
            int vis;
            if(flataxisface(c, i)) p.visible |= 1<<i;
            else if((vis = visibletris(c, i, co, size, MAT_NOCLIP, MATF_CLIP)))
            {
                int convex = faceconvexity(c, i), order = vis&4 || convex < 0 ? 1 : 0;
                const vec &v0 = p.v[fv[i][order]], &v1 = p.v[fv[i][order+1]], &v2 = p.v[fv[i][order+2]], &v3 = p.v[fv[i][(order+3)&3]];
                if(vis&1) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v1, v2); }
                if(vis&2 && (!(vis&1) || convex)) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v2, v3); }
            }
        }
    }
    else if(c.visible&0x80)
    {
        int vis;
        loopi(6) if((vis = visibletris(c, i, co, size)))
        {
            if(flataxisface(c, i)) p.visible |= 1<<i;
            else
            {
                int convex = faceconvexity(c, i), order = vis&4 || convex < 0 ? 1 : 0;
                const vec &v0 = p.v[fv[i][order]], &v1 = p.v[fv[i][order+1]], &v2 = p.v[fv[i][order+2]], &v3 = p.v[fv[i][(order+3)&3]];
                if(vis&1) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v1, v2); }
                if(vis&2 && (!(vis&1) || convex)) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v2, v3); }
            }
        }
    }
}

static inline bool mergefacecmp(const facebounds &x, const facebounds &y)
{
    if(x.v2 < y.v2) return true;
    if(x.v2 > y.v2) return false;
    if(x.u1 < y.u1) return true;
    if(x.u1 > y.u1) return false;
    return false;
}

static int mergefacev(int orient, facebounds *m, int sz, facebounds &n)
{
    for(int i = sz-1; i >= 0; --i)
    {
        if(m[i].v2 < n.v1) break;
        if(m[i].v2 == n.v1 && m[i].u1 == n.u1 && m[i].u2 == n.u2)
        {
            n.v1 = m[i].v1;
            memmove(&m[i], &m[i+1], (sz - (i+1)) * sizeof(facebounds));
            return 1;
        }
    }
    return 0;
}

static int mergefaceu(int orient, facebounds &m, facebounds &n)
{
    if(m.v1 == n.v1 && m.v2 == n.v2 && m.u2 == n.u1)
    {
        n.u1 = m.u1;
        return 1;
    }
    return 0;
}

static int mergeface(int orient, facebounds *m, int sz, facebounds &n)
{
    for(bool merged = false; sz; merged = true)
    {
        int vmerged = mergefacev(orient, m, sz, n);
        sz -= vmerged;
        if(!vmerged && merged) break;
        if(!sz) break;
        int umerged = mergefaceu(orient, m[sz-1], n);
        sz -= umerged;
        if(!umerged) break;
    }
    m[sz++] = n;
    return sz;
}

int mergefaces(int orient, facebounds *m, int sz)
{
    quicksort(m, sz, mergefacecmp);

    int nsz = 0;
    loopi(sz) nsz = mergeface(orient, m, nsz, m[i]);
    return nsz;
}

struct cfkey
{
    uchar orient;
    ushort material, tex;
    ivec n;
    int offset;
};

static inline bool htcmp(const cfkey &x, const cfkey &y)
{
    return x.orient == y.orient && x.tex == y.tex && x.n == y.n && x.offset == y.offset && x.material==y.material;
}

static inline uint hthash(const cfkey &k)
{
    return hthash(k.n)^k.offset^k.tex^k.orient^k.material;
}

void mincubeface(const cube &cu, int orient, const ivec &o, int size, const facebounds &orig, facebounds &cf, ushort nmat, ushort matmask)
{
    int dim = dimension(orient);
    if(cu.children)
    {
        size >>= 1;
        int coord = dimcoord(orient);
        loopi(8) if(octacoord(dim, i) == coord)
            mincubeface(cu.children[i], orient, ivec(i, o, size), size, orig, cf, nmat, matmask);
        return;
    }
    int c = C[dim], r = R[dim];
    ushort uco = (o[c]&0xFFF)<<3, vco = (o[r]&0xFFF)<<3;
    ushort uc1 = uco, vc1 = vco, uc2 = ushort(size<<3)+uco, vc2 = ushort(size<<3)+vco;
    uc1 = max(uc1, orig.u1);
    uc2 = min(uc2, orig.u2);
    vc1 = max(vc1, orig.v1);
    vc2 = min(vc2, orig.v2);
    if(!isempty(cu) && touchingface(cu, orient) && !(nmat!=MAT_AIR && (cu.material&matmask)==nmat))
    {
        uchar r1 = cu.edges[faceedgesidx[orient][0]], r2 = cu.edges[faceedgesidx[orient][1]],
              c1 = cu.edges[faceedgesidx[orient][2]], c2 = cu.edges[faceedgesidx[orient][3]];
        ushort u1 = max(c1&0xF, c2&0xF)*size+uco, u2 = min(c1>>4, c2>>4)*size+uco,
               v1 = max(r1&0xF, r2&0xF)*size+vco, v2 = min(r1>>4, r2>>4)*size+vco;
        u1 = max(u1, orig.u1);
        u2 = min(u2, orig.u2);
        v1 = max(v1, orig.v1);
        v2 = min(v2, orig.v2);
        if(v2-v1==vc2-vc1)
        {
            if(u2-u1==uc2-uc1) return;
            if(u1==uc1) uc1 = u2;
            if(u2==uc2) uc2 = u1;
        }
        else if(u2-u1==uc2-uc1)
        {
            if(v1==vc1) vc1 = v2;
            if(v2==vc2) vc2 = v1;
        }
    }
    if(uc1==uc2 || vc1==vc2) return;
    cf.u1 = min(cf.u1, uc1);
    cf.u2 = max(cf.u2, uc2);
    cf.v1 = min(cf.v1, vc1);
    cf.v2 = max(cf.v2, vc2);
}

bool mincubeface(const cube &cu, int orient, const ivec &co, int size, facebounds &orig)
{
    ivec no;
    int nsize;
    const cube &nc = neighbourcube(cu, orient, co, size, no, nsize);
    facebounds mincf;
    mincf.u1 = orig.u2;
    mincf.u2 = orig.u1;
    mincf.v1 = orig.v2;
    mincf.v2 = orig.v1;
    mincubeface(nc, opposite(orient), no, nsize, orig, mincf, cu.material&MAT_ALPHA ? MAT_AIR : MAT_ALPHA, MAT_ALPHA);
    bool smaller = false;
    if(mincf.u1 > orig.u1) { orig.u1 = mincf.u1; smaller = true; }
    if(mincf.u2 < orig.u2) { orig.u2 = mincf.u2; smaller = true; }
    if(mincf.v1 > orig.v1) { orig.v1 = mincf.v1; smaller = true; }
    if(mincf.v2 < orig.v2) { orig.v2 = mincf.v2; smaller = true; }
    return smaller;
}

VAR(maxmerge, 0, 6, 12);
VAR(minface, 0, 4, 12);

struct pvert
{
    ushort x, y;

    pvert() {}
    pvert(ushort x, ushort y) : x(x), y(y) {}

    bool operator==(const pvert &o) const { return x == o.x && y == o.y; }
    bool operator!=(const pvert &o) const { return x != o.x || y != o.y; }
};

struct pedge
{
    pvert from, to;

    pedge() {}
    pedge(const pvert &from, const pvert &to) : from(from), to(to) {}

    bool operator==(const pedge &o) const { return from == o.from && to == o.to; }
    bool operator!=(const pedge &o) const { return from != o.from || to != o.to; }
};

static inline uint hthash(const pedge &x) { return uint(x.from.x)^(uint(x.from.y)<<8); }
static inline bool htcmp(const pedge &x, const pedge &y) { return x == y; }

struct poly
{
    cube *c;
    int numverts;
    bool merged;
    pvert verts[MAXFACEVERTS];
};

bool clippoly(poly &p, const facebounds &b)
{
    pvert verts1[MAXFACEVERTS+4], verts2[MAXFACEVERTS+4];
    int numverts1 = 0, numverts2 = 0, px = p.verts[p.numverts-1].x, py = p.verts[p.numverts-1].y;
    loopi(p.numverts)
    {
        int x = p.verts[i].x, y = p.verts[i].y;
        if(x < b.u1)
        {
            if(px > b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
            if(px > b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
        }
        else if(x > b.u2)
        {
            if(px < b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
            if(px < b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
        }
        else
        {
            if(px < b.u1)
            {
                if(x > b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
            }
            else if(px > b.u2 && x < b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
            verts1[numverts1++] = pvert(x, y);
        }
        px = x;
        py = y;
    }
    if(numverts1 < 3) return false;
    px = verts1[numverts1-1].x;
    py = verts1[numverts1-1].y;
    loopi(numverts1)
    {
        int x = verts1[i].x, y = verts1[i].y;
        if(y < b.v1)
        {
            if(py > b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
            if(py > b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
        }
        else if(y > b.v2)
        {
            if(py < b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
            if(py < b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
        }
        else
        {
            if(py < b.v1)
            {
                if(y > b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
            }
            else if(py > b.v2 && y < b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
            verts2[numverts2++] = pvert(x, y);
        }
        px = x;
        py = y;
    }
    if(numverts2 < 3) return false;
    if(numverts2 > MAXFACEVERTS) return false;
    memcpy(p.verts, verts2, numverts2*sizeof(pvert));
    p.numverts = numverts2;
    return true;
}

bool genpoly(cube &cu, int orient, const ivec &o, int size, int vis, ivec &n, int &offset, poly &p)
{
    int dim = dimension(orient), coord = dimcoord(orient);
    ivec v[4];
    genfaceverts(cu, orient, v);
    if(flataxisface(cu, orient))
    {
         n = ivec(0, 0, 0);
         n[dim] = coord ? 1 : -1;
    }
    else
    {
        if(faceconvexity(v)) return false;
        n.cross(ivec(v[1]).sub(v[0]), ivec(v[2]).sub(v[0]));
        if(n.iszero()) n.cross(ivec(v[2]).sub(v[0]), ivec(v[3]).sub(v[0]));
        reduceslope(n);
    }

    ivec po = ivec(o).mask(0xFFF).shl(3);
    loopk(4) v[k].mul(size).add(po);
    offset = -n.dot(v[3]);

    int r = R[dim], c = C[dim], order = vis&4 ? 1 : 0;
    p.numverts = 0;
    if(coord)
    {
        const ivec &v0 = v[order]; p.verts[p.numverts++] = pvert(v0[c], v0[r]);
        if(vis&1) { const ivec &v1 = v[order+1]; p.verts[p.numverts++] = pvert(v1[c], v1[r]); }
        const ivec &v2 = v[order+2]; p.verts[p.numverts++] = pvert(v2[c], v2[r]);
        if(vis&2) { const ivec &v3 = v[(order+3)&3]; p.verts[p.numverts++] = pvert(v3[c], v3[r]); }
    }
    else
    {
        if(vis&2) { const ivec &v3 = v[(order+3)&3]; p.verts[p.numverts++] = pvert(v3[c], v3[r]); }
        const ivec &v2 = v[order+2]; p.verts[p.numverts++] = pvert(v2[c], v2[r]);
        if(vis&1) { const ivec &v1 = v[order+1]; p.verts[p.numverts++] = pvert(v1[c], v1[r]); }
        const ivec &v0 = v[order]; p.verts[p.numverts++] = pvert(v0[c], v0[r]);
    }

    if(faceedges(cu, orient)!=F_SOLID)
    {
        int px = int(p.verts[p.numverts-2].x) - int(p.verts[p.numverts-3].x), py = int(p.verts[p.numverts-2].y) - int(p.verts[p.numverts-3].y),
            cx = int(p.verts[p.numverts-1].x) - int(p.verts[p.numverts-2].x), cy = int(p.verts[p.numverts-1].y) - int(p.verts[p.numverts-2].y),
            dir = px*cy - py*cx;
        if(dir > 0) return false;
        if(!dir) { if(p.numverts < 4) return false; p.verts[p.numverts-2] = p.verts[p.numverts-1]; p.numverts--; }
        px = cx; py = cy;
        cx = int(p.verts[0].x) - int(p.verts[p.numverts-1].x); cy = int(p.verts[0].y) - int(p.verts[p.numverts-1].y);
        dir = px*cy - py*cx;
        if(dir > 0) return false;
        if(!dir) { if(p.numverts < 4) return false; p.numverts--; }
        px = cx; py = cy;
        cx = int(p.verts[1].x) - int(p.verts[0].x); cy = int(p.verts[1].y) - int(p.verts[0].y);
        dir = px*cy - py*cx;
        if(dir > 0) return false;
        if(!dir) { if(p.numverts < 4) return false; p.verts[0] = p.verts[p.numverts-1]; p.numverts--; }
        px = cx; py = cy;
        cx = int(p.verts[2].x) - int(p.verts[1].x); cy = int(p.verts[2].y) - int(p.verts[1].y);
        dir = px*cy - py*cx;
        if(dir > 0) return false;
        if(!dir) { if(p.numverts < 4) return false; p.verts[1] = p.verts[2]; p.verts[2] = p.verts[3]; p.numverts--; }
    }

    p.c = &cu;
    p.merged = false;

    if(minface && size >= 1<<minface && touchingface(cu, orient))
    {
        facebounds b;
        b.u1 = b.u2 = p.verts[0].x;
        b.v1 = b.v2 = p.verts[0].y;
        for(int i = 1; i < p.numverts; i++)
        {
            const pvert &v = p.verts[i];
            b.u1 = min(b.u1, v.x);
            b.u2 = max(b.u2, v.x);
            b.v1 = min(b.v1, v.y);
            b.v2 = max(b.v2, v.y);
        }
        if(mincubeface(cu, orient, o, size, b) && clippoly(p, b))
            p.merged = true;
    }

    return true;
}

struct plink : pedge
{
    int polys[2];

    plink() { clear(); }
    plink(const pedge &p) : pedge(p) { clear(); }

    void clear() { polys[0] = polys[1] = -1; }
};

bool mergepolys(int orient, hashset<plink> &links, vector<plink *> &queue, int owner, poly &p, poly &q, const pedge &e)
{
    int pe = -1, qe = -1;
    loopi(p.numverts) if(p.verts[i] == e.from) { pe = i; break; }
    loopi(q.numverts) if(q.verts[i] == e.to) { qe = i; break; }
    if(pe < 0 || qe < 0) return false;
    if(p.verts[(pe+1)%p.numverts] != e.to || q.verts[(qe+1)%q.numverts] != e.from) return false;
    /*
     *  c----d
     *  |    |
     *  F----T
     *  |  P |
     *  b----a
     */
    pvert verts[2*MAXFACEVERTS];
    int numverts = 0, index = pe+2; // starts at A = T+1, ends at F = T+p.numverts
    loopi(p.numverts-1)
    {
        if(index >= p.numverts) index -= p.numverts;
        verts[numverts++] = p.verts[index++];
    }
    index = qe+2; // starts at C = T+2 = F+1, ends at T = T+q.numverts
    int px = int(verts[numverts-1].x) - int(verts[numverts-2].x), py = int(verts[numverts-1].y) - int(verts[numverts-2].y);
    loopi(q.numverts-1)
    {
        if(index >= q.numverts) index -= q.numverts;
        pvert &src = q.verts[index++];
        int cx = int(src.x) - int(verts[numverts-1].x), cy = int(src.y) - int(verts[numverts-1].y),
            dir = px*cy - py*cx;
        if(dir > 0) return false;
        if(!dir) numverts--;
        verts[numverts++] = src;
        px = cx;
        py = cy;
    }
    int cx = int(verts[0].x) - int(verts[numverts-1].x), cy = int(verts[0].y) - int(verts[numverts-1].y),
        dir = px*cy - py*cx;
    if(dir > 0) return false;
    if(!dir) numverts--;

    if(numverts > MAXFACEVERTS) return false;

    q.merged = true;
    q.numverts = 0;

    p.merged = true;
    p.numverts = numverts;
    memcpy(p.verts, verts, numverts*sizeof(pvert));

    int prev = p.numverts-1;
    loopj(p.numverts)
    {
        pedge e(p.verts[prev], p.verts[j]);
        int order = e.from.x > e.to.x || (e.from.x == e.to.x && e.from.y > e.to.y) ? 1 : 0;
        if(order) swap(e.from, e.to);
        plink &l = links.access(e, e);
        bool shouldqueue = l.polys[order] < 0 && l.polys[order^1] >= 0;
        l.polys[order] = owner;
        if(shouldqueue) queue.add(&l);
        prev = j;
    }

    return true;
}

void addmerge(cube &cu, int orient, const ivec &co, const ivec &n, int offset, poly &p)
{
    cu.merged |= 1<<orient;
    if(!p.numverts)
    {
        if(cu.ext) cu.ext->surfaces[orient] = ambientsurface;
        return;
    }
    surfaceinfo surf = brightsurface;
    vertinfo verts[MAXFACEVERTS];
    surf.numverts |= p.numverts;
    int dim = dimension(orient), coord = dimcoord(orient), c = C[dim], r = R[dim];
    loopk(p.numverts)
    {
        pvert &src = p.verts[coord ? k : p.numverts-1-k];
        vertinfo &dst = verts[k];
        ivec v;
        v[c] = src.x;
        v[r] = src.y;
        v[dim] = -(offset + n[c]*src.x + n[r]*src.y)/n[dim];
        dst.set(v);
    }
    if(cu.ext)
    {
        const surfaceinfo &oldsurf = cu.ext->surfaces[orient];
        int numverts = oldsurf.numverts&MAXFACEVERTS;
        if(numverts == p.numverts)
        {
            ivec v0 = verts[0].getxyz();
            const vertinfo *oldverts = cu.ext->verts() + oldsurf.verts;
            loopj(numverts) if(v0 == oldverts[j].getxyz())
            {
                for(int k = 1; k < numverts; k++)
                {
                    if(++j >= numverts) j = 0;
                    if(verts[k].getxyz() != oldverts[j].getxyz()) goto nomatch;
                }
                return;
            }
        nomatch:;
        }
    }
    setsurface(cu, orient, surf, verts, p.numverts);
}

static inline void clearmerge(cube &c, int orient)
{
    if(c.merged&(1<<orient))
    {
        c.merged &= ~(1<<orient);
        if(c.ext) c.ext->surfaces[orient] = brightsurface;
    }
}

void addmerges(int orient, const ivec &co, const ivec &n, int offset, vector<poly> &polys)
{
    loopv(polys)
    {
        poly &p = polys[i];
        if(p.merged) addmerge(*p.c, orient, co, n, offset, p);
        else clearmerge(*p.c, orient);
    }
}

void mergepolys(int orient, const ivec &co, const ivec &n, int offset, vector<poly> &polys)
{
    if(polys.length() <= 1) { addmerges(orient, co, n, offset, polys); return; }
    hashset<plink> links(polys.length() <= 32 ? 128 : 1024);
    vector<plink *> queue;
    loopv(polys)
    {
        poly &p = polys[i];
        int prev = p.numverts-1;
        loopj(p.numverts)
        {
            pedge e(p.verts[prev], p.verts[j]);
            int order = e.from.x > e.to.x || (e.from.x == e.to.x && e.from.y > e.to.y) ? 1 : 0;
            if(order) swap(e.from, e.to);
            plink &l = links.access(e, e);
            l.polys[order] = i;
            if(l.polys[0] >= 0 && l.polys[1] >= 0) queue.add(&l);
            prev = j;
        }
    }
    vector<plink *> nextqueue;
    while(queue.length())
    {
        loopv(queue)
        {
            plink &l = *queue[i];
            if(l.polys[0] >= 0 && l.polys[1] >= 0)
                mergepolys(orient, links, nextqueue, l.polys[0], polys[l.polys[0]], polys[l.polys[1]], l);
        }
        queue.setsize(0);
        queue.move(nextqueue);
    }
    addmerges(orient, co, n, offset, polys);
}

static int genmergeprogress = 0;

struct cfpolys
{
    vector<poly> polys;
};

static hashtable<cfkey, cfpolys> cpolys;

void genmerges(cube *c = worldroot, const ivec &o = ivec(0, 0, 0), int size = worldsize>>1)
{
    if((genmergeprogress++&0xFFF)==0) renderprogress(float(genmergeprogress)/allocnodes, "merging faces...");
    neighbourstack[++neighbourdepth] = c;
    loopi(8)
    {
        ivec co(i, o, size);
        int vis;
        if(c[i].children) genmerges(c[i].children, co, size>>1);
        else if(!isempty(c[i])) loopj(6) if((vis = visibletris(c[i], j, co, size)))
        {
            cfkey k;
            poly p;
            if(size < 1<<maxmerge && c != worldroot)
            {
                if(genpoly(c[i], j, co, size, vis, k.n, k.offset, p))
                {
                    k.orient = j;
                    k.tex = c[i].texture[j];
                    k.material = c[i].material&MAT_ALPHA;
                    cpolys[k].polys.add(p);
                    continue;
                }
            }
            else if(minface && size >= 1<<minface && touchingface(c[i], j))
            {
                if(genpoly(c[i], j, co, size, vis, k.n, k.offset, p) && p.merged)
                {
                    addmerge(c[i], j, co, k.n, k.offset, p);
                    continue;
                }
            }
            clearmerge(c[i], j);
        }
        if((size == 1<<maxmerge || c == worldroot) && cpolys.numelems)
        {
            enumeratekt(cpolys, cfkey, key, cfpolys, val,
            {
                mergepolys(key.orient, co, key.n, key.offset, val.polys);
            });
            cpolys.clear();
        }
    }
    --neighbourdepth;
}

int calcmergedsize(int orient, const ivec &co, int size, const vertinfo *verts, int numverts)
{
    ushort x1 = verts[0].x, y1 = verts[0].y, z1 = verts[0].z,
           x2 = x1, y2 = y1, z2 = z1;
    for(int i = 1; i < numverts; i++)
    {
        const vertinfo &v = verts[i];
        x1 = min(x1, v.x);
        x2 = max(x2, v.x);
        y1 = min(y1, v.y);
        y2 = max(y2, v.y);
        z1 = min(z1, v.z);
        z2 = max(z2, v.z);
    }
    int bits = 0;
    while(1<<bits < size) ++bits;
    bits += 3;
    ivec mo(co);
    mo.mask(0xFFF);
    mo.shl(3);
    while(bits<15)
    {
        mo.mask(~((1<<bits)-1));
        if(mo.x <= x1 && mo.x + (1<<bits) >= x2 &&
           mo.y <= y1 && mo.y + (1<<bits) >= y2 &&
           mo.z <= z1 && mo.z + (1<<bits) >= z2)
            break;
        bits++;
    }
    return bits-3;
}

static void invalidatemerges(cube &c)
{
    if(c.merged)
    {
        brightencube(c);
        c.merged = 0;
    }
    if(c.ext)
    {
        if(c.ext->va)
        {
            if(!(c.ext->va->hasmerges&(MERGE_PART | MERGE_ORIGIN))) return;
            destroyva(c.ext->va);
            c.ext->va = NULL;
        }
        if(c.ext->tjoints >= 0) c.ext->tjoints = -1;
    }
    if(c.children) loopi(8) invalidatemerges(c.children[i]);
}

static int invalidatedmerges = 0;

void invalidatemerges(cube &c, const ivec &co, int size, bool msg)
{
    if(msg && invalidatedmerges!=totalmillis)
    {
        renderprogress(0, "invalidating merged surfaces...");
        invalidatedmerges = totalmillis;
    }
    invalidatemerges(c);
}

void calcmerges()
{
    genmergeprogress = 0;
    genmerges();
}