#include "engine.h"

struct normalgroup
{
    vec pos;
    int flat, normals, tnormals;

    normalgroup() : flat(0), normals(-1), tnormals(-1) {}
    normalgroup(const vec &pos) : pos(pos), flat(0), normals(-1), tnormals(-1) {}
};

static inline bool htcmp(const vec &v, const normalgroup &n) { return v == n.pos; } 

struct normal
{
    int next;
    vec surface;
};

struct tnormal
{
    int next;
    float offset;
    int normals[2];
    normalgroup *groups[2];
};

hashset<normalgroup> normalgroups(1<<16);
vector<normal> normals;
vector<tnormal> tnormals;

VARR(lerpangle, 0, 44, 180);

static float lerpthreshold = 0;
static bool usetnormals = true;

static int addnormal(const vec &key, const vec &surface)
{
    normalgroup &g = normalgroups.access(key, key);
    normal &n = normals.add();
    n.next = g.normals;
    n.surface = surface;
    return g.normals = normals.length()-1;
}

static void addtnormal(const vec &key, float offset, int normal1, int normal2, normalgroup *group1, normalgroup *group2)
{
    normalgroup &g = normalgroups.access(key, key);
    tnormal &n = tnormals.add();
    n.next = g.tnormals;
    n.offset = offset;
    n.normals[0] = normal1;
    n.normals[1] = normal2;
    n.groups[0] = group1;
    n.groups[1] = group2;
    g.tnormals = tnormals.length()-1;
}

static int addnormal(const vec &key, int axis)
{
    normalgroup &g = normalgroups.access(key, key);
    g.flat += 1<<(4*axis);
    return axis - 6;
}

static inline void findnormal(const normalgroup &g, const vec &surface, vec &v)
{
    v = vec(0, 0, 0);
    int total = 0;
    if(surface.x >= lerpthreshold) { int n = (g.flat>>4)&0xF; v.x += n; total += n; }
    else if(surface.x <= -lerpthreshold) { int n = g.flat&0xF; v.x -= n; total += n; }
    if(surface.y >= lerpthreshold) { int n = (g.flat>>12)&0xF; v.y += n; total += n; }
    else if(surface.y <= -lerpthreshold) { int n = (g.flat>>8)&0xF; v.y -= n; total += n; }
    if(surface.z >= lerpthreshold) { int n = (g.flat>>20)&0xF; v.z += n; total += n; }
    else if(surface.z <= -lerpthreshold) { int n = (g.flat>>16)&0xF; v.z -= n; total += n; }
    for(int cur = g.normals; cur >= 0;)
    {
        normal &o = normals[cur];
        if(o.surface.dot(surface) >= lerpthreshold)
        {
            v.add(o.surface);
            total++;
        }
        cur = o.next;
    }
    if(total > 1) v.normalize();
    else if(!total) v = surface;
}

static inline bool findtnormal(const normalgroup &g, const vec &surface, vec &v)
{
    float bestangle = lerpthreshold;
    tnormal *bestnorm = NULL;
    for(int cur = g.tnormals; cur >= 0;)
    {
        tnormal &o = tnormals[cur];
        static const vec flats[6] = { vec(-1, 0, 0), vec(1, 0, 0), vec(0, -1, 0), vec(0, 1, 0), vec(0, 0, -1), vec(0, 0, 1) };
        vec n1 = o.normals[0] < 0 ? flats[o.normals[0]+6] : normals[o.normals[0]].surface,
            n2 = o.normals[1] < 0 ? flats[o.normals[1]+6] : normals[o.normals[1]].surface,
            nt;
        nt.lerp(n1, n2, o.offset).normalize();
        float tangle = nt.dot(surface);
        if(tangle >= bestangle)
        {
            bestangle = tangle;
            bestnorm = &o;
        }
        cur = o.next;
    }
    if(!bestnorm) return false;
    vec n1, n2;
    findnormal(*bestnorm->groups[0], surface, n1);
    findnormal(*bestnorm->groups[1], surface, n2);
    v.lerp(n1, n2, bestnorm->offset).normalize();
    return true;
}

void findnormal(const vec &key, const vec &surface, vec &v)
{
    const normalgroup *g = normalgroups.access(key);
    if(!g) v = surface;
    else if(g->tnormals < 0 || !findtnormal(*g, surface, v)) 
        findnormal(*g, surface, v);
}

VARR(lerpsubdiv, 0, 2, 4);
VARR(lerpsubdivsize, 4, 4, 128);

static uint progress = 0;

void show_addnormals_progress()
{
    float bar1 = float(progress) / float(allocnodes);
    renderprogress(bar1, "computing normals...");
}

void addnormals(cube &c, const ivec &o, int size)
{
    CHECK_CALCLIGHT_PROGRESS(return, show_addnormals_progress);

    if(c.children)
    {
        progress++;
        size >>= 1;
        loopi(8) addnormals(c.children[i], ivec(i, o, size), size);
        return;
    }
    else if(isempty(c)) return;

    vec pos[MAXFACEVERTS];
    int norms[MAXFACEVERTS];
    int tj = usetnormals && c.ext ? c.ext->tjoints : -1, vis;
    loopi(6) if((vis = visibletris(c, i, o, size)))
    {
        CHECK_CALCLIGHT_PROGRESS(return, show_addnormals_progress);
        if(c.texture[i] == DEFAULT_SKY) continue;

        vec planes[2];
        int numverts = c.ext ? c.ext->surfaces[i].numverts&MAXFACEVERTS : 0, convex = 0, numplanes = 0;
        if(numverts)
        {
            vertinfo *verts = c.ext->verts() + c.ext->surfaces[i].verts;
            vec vo(ivec(o).mask(~0xFFF));
            loopj(numverts)
            {
                vertinfo &v = verts[j];
                pos[j] = vec(v.x, v.y, v.z).mul(1.0f/8).add(vo);
            }
            if(!(c.merged&(1<<i)) && !flataxisface(c, i)) convex = faceconvexity(verts, numverts, size);
        }
        else if(c.merged&(1<<i)) continue;
        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(o);
            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);
        }

        if(!flataxisface(c, i))
        {
            planes[numplanes++].cross(pos[0], pos[1], pos[2]).normalize();
            if(convex) planes[numplanes++].cross(pos[0], pos[2], pos[3]).normalize();
        }

        if(!numplanes) loopk(numverts) norms[k] = addnormal(pos[k], i);
        else if(numplanes==1) loopk(numverts) norms[k] = addnormal(pos[k], planes[0]);
        else 
        { 
            vec avg = vec(planes[0]).add(planes[1]).normalize();
            norms[0] = addnormal(pos[0], avg);
            norms[1] = addnormal(pos[1], planes[0]);
            norms[2] = addnormal(pos[2], avg);
            for(int k = 3; k < numverts; k++) norms[k] = addnormal(pos[k], planes[1]);
        }

        while(tj >= 0 && tjoints[tj].edge < i*(MAXFACEVERTS+1)) tj = tjoints[tj].next;
        while(tj >= 0 && tjoints[tj].edge < (i+1)*(MAXFACEVERTS+1))
        {
            int edge = tjoints[tj].edge, e1 = edge%(MAXFACEVERTS+1), e2 = (e1+1)%numverts;
            const vec &v1 = pos[e1], &v2 = pos[e2];
            ivec d(vec(v2).sub(v1).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[axis], v2[axis])*8)&~0x7FFF,
                offset1 = (int(v1[axis]*8) - origin) / d[axis],
                offset2 = (int(v2[axis]*8) - origin) / d[axis];
            vec o = vec(v1).sub(vec(d).mul(offset1/8.0f)), n1, n2;
            float doffset = 1.0f / (offset2 - offset1);

            while(tj >= 0)
            {
                tjoint &t = tjoints[tj];
                if(t.edge != edge) break;
                float offset = (t.offset - offset1) * doffset;
                vec tpos = vec(d).mul(t.offset/8.0f).add(o); 
                addtnormal(tpos, offset, norms[e1], norms[e2], normalgroups.access(v1), normalgroups.access(v2));
                tj = t.next;
            }
        }
    }
}

void calcnormals(bool lerptjoints)
{
    if(!lerpangle) return;
    usetnormals = lerptjoints; 
    if(usetnormals) findtjoints();
    lerpthreshold = cos(lerpangle*RAD) - 1e-5f; 
    progress = 1;
    loopi(8) addnormals(worldroot[i], ivec(i, ivec(0, 0, 0), worldsize/2), worldsize/2);
}

void clearnormals()
{
    normalgroups.clear();
    normals.setsize(0);
    tnormals.setsize(0);
}

void calclerpverts(const vec2 *c, const vec *n, lerpvert *lv, int &numv)
{
    int i = 0;
    loopj(numv)
    {
        if(j)
        {
            if(c[j] == c[j-1] && n[j] == n[j-1]) continue;
            if(j == numv-1 && c[j] == c[0] && n[j] == n[0]) continue;
        }
        lv[i].normal = n[j];
        lv[i].tc = c[j];
        i++;
    }
    numv = i;
}

void setlerpstep(float v, lerpbounds &bounds)
{
    if(bounds.min->tc.y + 1 > bounds.max->tc.y)
    {
        bounds.nstep = vec(0, 0, 0);
        bounds.normal = bounds.min->normal;
        if(bounds.min->normal != bounds.max->normal)
        {
            bounds.normal.add(bounds.max->normal);
            bounds.normal.normalize();
        }
        bounds.ustep = 0;
        bounds.u = bounds.min->tc.x;
        return;
    }

    bounds.nstep = bounds.max->normal;
    bounds.nstep.sub(bounds.min->normal);
    bounds.nstep.div(bounds.max->tc.y-bounds.min->tc.y);

    bounds.normal = bounds.nstep;
    bounds.normal.mul(v - bounds.min->tc.y);
    bounds.normal.add(bounds.min->normal);

    bounds.ustep = (bounds.max->tc.x-bounds.min->tc.x) / (bounds.max->tc.y-bounds.min->tc.y);
    bounds.u = bounds.ustep * (v-bounds.min->tc.y) + bounds.min->tc.x;
}

void initlerpbounds(float u, float v, const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end)
{
    const lerpvert *first = &lv[0], *second = NULL;
    loopi(numv-1)
    {
        if(lv[i+1].tc.y < first->tc.y) { second = first; first = &lv[i+1]; }
        else if(!second || lv[i+1].tc.y < second->tc.y) second = &lv[i+1];
    }

    if(int(first->tc.y) < int(second->tc.y)) { start.min = end.min = first; }
    else if(first->tc.x > second->tc.x) { start.min = second; end.min = first; }
    else { start.min = first; end.min = second; }

    if((lv[1].tc.x - lv->tc.x)*(lv[2].tc.y - lv->tc.y) > (lv[1].tc.y - lv->tc.y)*(lv[2].tc.x - lv->tc.x))
    { 
        start.winding = end.winding = 1;
        start.max = (start.min == lv ? &lv[numv-1] : start.min-1);
        end.max = (end.min == &lv[numv-1] ? lv : end.min+1);
    }
    else
    {
        start.winding = end.winding = -1;
        start.max = (start.min == &lv[numv-1] ? lv : start.min+1);
        end.max = (end.min == lv ? &lv[numv-1] : end.min-1);
    }

    setlerpstep(v, start);
    setlerpstep(v, end);
}

void updatelerpbounds(float v, const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end)
{
    if(v >= start.max->tc.y)
    {
        const lerpvert *next = start.winding > 0 ?
                (start.max == lv ? &lv[numv-1] : start.max-1) :
                (start.max == &lv[numv-1] ? lv : start.max+1);
        if(next->tc.y > start.max->tc.y)
        {
            start.min = start.max;
            start.max = next;
            setlerpstep(v, start);
        }
    }
    if(v >= end.max->tc.y)
    {
        const lerpvert *next = end.winding > 0 ?
                (end.max == &lv[numv-1] ? lv : end.max+1) :
                (end.max == lv ? &lv[numv-1] : end.max-1);
        if(next->tc.y > end.max->tc.y)
        {
            end.min = end.max;
            end.max = next;
            setlerpstep(v, end);
        }
    }
}

void lerpnormal(float u, float v, const lerpvert *lv, int numv, lerpbounds &start, lerpbounds &end, vec &normal, vec &nstep)
{   
    updatelerpbounds(v, lv, numv, start, end);

    if(start.u + 1 > end.u)
    {
        nstep = vec(0, 0, 0);
        normal = start.normal;
        normal.add(end.normal);
        normal.normalize();
    }
    else
    {
        vec nstart(start.normal), nend(end.normal);
        nstart.normalize();
        nend.normalize();
       
        nstep = nend;
        nstep.sub(nstart);
        nstep.div(end.u-start.u);

        normal = nstep;
        normal.mul(u-start.u);
        normal.add(nstart);
        normal.normalize();
    }
     
    start.normal.add(start.nstep);
    start.u += start.ustep;

    end.normal.add(end.nstep); 
    end.u += end.ustep;
}