diff options
Diffstat (limited to 'src/engine/octarender.cpp')
| -rw-r--r-- | src/engine/octarender.cpp | 1803 |
1 files changed, 1803 insertions, 0 deletions
diff --git a/src/engine/octarender.cpp b/src/engine/octarender.cpp new file mode 100644 index 0000000..faf609f --- /dev/null +++ b/src/engine/octarender.cpp @@ -0,0 +1,1803 @@ +// 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<grasstri> grasstris; + 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); + grasstris.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 ? k.lmid : 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(grasstris.length()) + { + va->grasstris.move(grasstris); + useshaderbyname("grass"); + } + + if(mapmodels.length()) va->mapmodels.put(mapmodels.getbuf(), mapmodels.length()); + } + + bool emptyva() + { + return verts.empty() && matsurfs.empty() && skyindices.empty() && explicitskyindices.empty() && grasstris.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; + } + } + } + } +} + +void addgrasstri(int face, vertex *verts, int numv, ushort texture, ushort lmid) +{ + grasstri &g = vc.grasstris.add(); + int i1, i2, i3, i4; + if(numv <= 3 && face%2) { i1 = face+1; i2 = face+2; i3 = i4 = 0; } + else { i1 = 0; i2 = face+1; i3 = face+2; i4 = numv > 3 ? face+3 : i3; } + g.v[0] = verts[i1].pos; + g.v[1] = verts[i2].pos; + g.v[2] = verts[i3].pos; + g.v[3] = verts[i4].pos; + g.numv = numv; + + g.surface.toplane(g.v[0], g.v[1], g.v[2]); + if(g.surface.z <= 0) { vc.grasstris.pop(); return; } + + g.minz = min(min(g.v[0].z, g.v[1].z), min(g.v[2].z, g.v[3].z)); + g.maxz = max(max(g.v[0].z, g.v[1].z), max(g.v[2].z, g.v[3].z)); + + g.center = vec(0, 0, 0); + loopk(numv) g.center.add(g.v[k]); + g.center.div(numv); + g.radius = 0; + loopk(numv) g.radius = max(g.radius, g.v[k].dist(g.center)); + + vec area, bx, by; + area.cross(vec(g.v[1]).sub(g.v[0]), vec(g.v[2]).sub(g.v[0])); + float scale; + int px, py; + + if(fabs(area.x) >= fabs(area.y) && fabs(area.x) >= fabs(area.z)) + scale = 1/area.x, px = 1, py = 2; + else if(fabs(area.y) >= fabs(area.x) && fabs(area.y) >= fabs(area.z)) + scale = -1/area.y, px = 0, py = 2; + else + scale = 1/area.z, px = 0, py = 1; + + bx.x = (g.v[2][py] - g.v[0][py])*scale; + bx.y = (g.v[2][px] - g.v[0][px])*scale; + bx.z = bx.x*g.v[2][px] - bx.y*g.v[2][py]; + + by.x = (g.v[2][py] - g.v[1][py])*scale; + by.y = (g.v[2][px] - g.v[1][px])*scale; + by.z = by.x*g.v[1][px] - by.y*g.v[1][py] - 1; + by.sub(bx); + + float tc1u = verts[i1].lm.x, + tc1v = verts[i1].lm.y, + tc2u = verts[i2].lm.x - verts[i1].lm.x, + tc2v = verts[i2].lm.y - verts[i1].lm.y, + tc3u = verts[i3].lm.x - verts[i1].lm.x, + tc3v = verts[i3].lm.y - verts[i1].lm.y; + + g.tcu = vec4(0, 0, 0, tc1u - (bx.z*tc2u + by.z*tc3u)); + g.tcu[px] = bx.x*tc2u + by.x*tc3u; + g.tcu[py] = -(bx.y*tc2u + by.y*tc3u); + + g.tcv = vec4(0, 0, 0, tc1v - (bx.z*tc2v + by.z*tc3v)); + g.tcv[px] = bx.x*tc2v + by.x*tc3v; + g.tcv[py] = -(bx.y*tc2v + by.y*tc3v); + + g.texture = texture; + g.lmid = lmid; +} + +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) +{ + 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); + + if(grassy) + { + for(int i = 0; i < numverts-2; i += 2) + { + int faces = 0; + if(index[0]!=index[i+1] && index[i+1]!=index[i+2] && index[i+2]!=index[0]) faces |= 1; + if(i+3 < numverts && index[0]!=index[i+2] && index[i+2]!=index[i+3] && index[i+3]!=index[0]) faces |= 2; + if(grassy > 1 && faces==3) addgrasstri(i, verts, 4, texture, lmid); + else + { + if(faces&1) addgrasstri(i, verts, 3, texture, lmid); + if(faces&2) addgrasstri(i+1, verts, 3, texture, lmid); + } + } + } +} + +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 ? (vslot.slot->texmask&(1<<TEX_ENVMAP) ? EMID_CUSTOM : closestenvmap(i, co, size)) : EMID_NONE, + envmap2 = layer && layer->slot->shader->type&SHADER_ENVMAP ? (layer->slot->texmask&(1<<TEX_ENVMAP) ? EMID_CUSTOM : closestenvmap(i, co, size)) : 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; + int grassy = vslot.slot->autograss && i!=O_BOTTOM ? (vis!=3 || convex ? 1 : 2) : 0; + if(!c.ext) + addcubeverts(vslot, i, size, pos, convex, c.texture[i], LMID_AMBIENT, NULL, numverts, hastj, envmap, grassy, (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, grassy, (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) ? EMID_CUSTOM : closestenvmap(i, co, size); + ushort envmap2 = layer && layer->slot->shader->type&SHADER_ENVMAP ? (layer->slot->texmask&(1<<TEX_ENVMAP) ? EMID_CUSTOM : closestenvmap(i, co, size)) : 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); + int grassy = vslot.slot->autograss && mf.orient!=O_BOTTOM && mf.numverts&LAYER_TOP ? 2 : 0; + addcubeverts(vslot, mf.orient, 1<<level, pos, 0, mf.tex, mf.lmid, mf.verts, numverts, mf.tjoints, mf.envmap, grassy, (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(); + initenvmaps(); + } + guessshadowdir(); + entitiesinoctanodes(); + tjoints.setsize(0); + if(filltjoints) findtjoints(); + octarender(); + if(load) precachetextures(); + setupmaterials(); + invalidatepostfx(); + updatevabbs(true); + resetblobs(); + lightents(); + if(load) + { + seedparticles(); + drawtextures(); + } +} + +void recalc() +{ + allchanged(true); +} + +COMMAND(recalc, ""); + |