src/engine/octa.cpp

   1 // core world management routines
   2
   3 #include "pch.h"
   4 #include "engine.h"
   5
   6 cube *worldroot = newcubes(F_SOLID);
   7 int allocnodes = 0;
   8
   9 cubeext *newcubeext(cube &c)
  10 {
  11     if(c.ext) return c.ext;
  12     c.ext = new cubeext;
  13     c.ext->material = MAT_AIR;
  14     c.ext->visible = 0;
  15     c.ext->merged = 0;
  16     c.ext->mergeorigin = 0;
  17     c.ext->va = NULL;
  18     c.ext->clip = NULL;
  19     c.ext->surfaces = NULL;
  20     c.ext->normals = NULL;
  21     c.ext->ents = NULL;
  22     c.ext->merges = NULL;
  23     c.ext->tjoints = -1;
  24     return c.ext;
  25 }
  26
  27 cube *newcubes(uint face)
  28 {
  29     cube *c = new cube[8];
  30     loopi(8)
  31     {
  32         c->children = NULL;
  33         c->ext = NULL;
  34         setfaces(*c, face);
  35         loopl(6)
  36         {
  37             c->texture[l] = 2+l;
  38         }
  39         c++;
  40     }
  41     allocnodes++;
  42     return c-8;
  43 }
  44
  45 int familysize(cube &c)
  46 {
  47     int size = 1;
  48     if(c.children) loopi(8) size += familysize(c.children[i]);
  49     return size;
  50 }
  51
  52 void freeocta(cube *c)
  53 {
  54     if(!c) return;
  55     loopi(8) discardchildren(c[i]);
  56     delete[] c;
  57     allocnodes--;
  58 }
  59
  60 void freecubeext(cube &c)
  61 {
  62     DELETEP(c.ext);
  63 }
  64
  65 void discardchildren(cube &c)
  66 {
  67     if(c.ext)
  68     {
  69         if(c.ext->va) destroyva(c.ext->va);
  70         c.ext->va = NULL;
  71         c.ext->merged = 0;
  72         c.ext->tjoints = -1;
  73         freesurfaces(c);
  74         freenormals(c);
  75         freeclipplanes(c);
  76         freeoctaentities(c);
  77         freemergeinfo(c);
  78         freecubeext(c);
  79     }
  80     if(c.children)
  81     {
  82         freeocta(c.children);
  83         c.children = NULL;
  84     }
  85 }
  86
  87 void getcubevector(cube &c, int d, int x, int y, int z, ivec &p)
  88 {
  89     ivec v(d, x, y, z);
  90
  91     loopi(3)
  92         p[i] = edgeget(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]]);
  93 }
  94
  95 void setcubevector(cube &c, int d, int x, int y, int z, ivec &p)
  96 {
  97     ivec v(d, x, y, z);
  98
  99     loopi(3)
 100         edgeset(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]], p[i]);
 101 }
 102
 103 void optiface(uchar *p, cube &c)
 104 {
 105     loopi(4) if(edgeget(p[i], 0)!=edgeget(p[i], 1)) return;
 106     emptyfaces(c);
 107 }
 108
 109 void printcube()
 110 {
 111     cube &c = lookupcube(lu.x, lu.y, lu.z, 0); // assume this is cube being pointed at
 112     conoutf(CON_DEBUG, "= %p = (%d, %d, %d) @ %d", &c, lu.x, lu.y, lu.z, lusize);
 113     conoutf(CON_DEBUG, " x  %.8x", c.faces[0]);
 114     conoutf(CON_DEBUG, " y  %.8x", c.faces[1]);
 115     conoutf(CON_DEBUG, " z  %.8x", c.faces[2]);
 116 }
 117
 118 COMMAND(printcube, "");
 119
 120 bool isvalidcube(cube &c)
 121 {
 122     clipplanes p;
 123     genclipplanes(c, 0, 0, 0, 256, p);
 124     loopi(8) // test that cube is convex
 125     {
 126         vvec v;
 127         calcvert(c, 0, 0, 0, 256, v, i);
 128         if(!pointincube(p, v.tovec()))
 129             return false;
 130     }
 131     return true;
 132 }
 133
 134 void validatec(cube *c, int size)
 135 {
 136     loopi(8)
 137     {
 138         if(c[i].children)
 139         {
 140             if(size<=(8>>VVEC_FRAC))
 141             {
 142                 solidfaces(c[i]);
 143                 discardchildren(c[i]);
 144             }
 145             else validatec(c[i].children, size>>1);
 146         }
 147         else
 148         {
 149             loopj(3) optiface((uchar *)&(c[i].faces[j]), c[i]);
 150             loopj(12)
 151                 if(edgeget(c[i].edges[j], 1)>8 ||
 152                    edgeget(c[i].edges[j], 1)<edgeget(c[i].edges[j], 0))
 153                     emptyfaces(c[i]);
 154         }
 155     }
 156 }
 157
 158 ivec lu;
 159 int lusize;
 160 cube &lookupcube(int tx, int ty, int tz, int tsize)
 161 {
 162     int size = hdr.worldsize;
 163     int x = 0, y = 0, z = 0;
 164     cube *c = worldroot;
 165     for(;;)
 166     {
 167         size >>= 1;
 168         ASSERT(size);
 169         if(tz>=z+size) { z += size; c += 4; }
 170         if(ty>=y+size) { y += size; c += 2; }
 171         if(tx>=x+size) { x += size; c += 1; }
 172         //if(tsize==size) break;
 173         if(abs(tsize)>=size) break;
 174         if(c->children==NULL)
 175         {
 176             //if(!tsize) break;
 177             if(tsize<=0) break;
 178             subdividecube(*c);
 179         }
 180         c = c->children;
 181     }
 182     lu.x = x;
 183     lu.y = y;
 184     lu.z = z;
 185     lusize = size;
 186     return *c;
 187 }
 188
 189 cube &neighbourcube(int x, int y, int z, int size, int rsize, int orient)
 190 {
 191     switch(orient)
 192     {
 193         case O_BOTTOM: z -= size; break;
 194         case O_TOP:    z += size; break;
 195         case O_BACK:   y -= size; break;
 196         case O_FRONT:  y += size; break;
 197         case O_LEFT:   x -= size; break;
 198         case O_RIGHT:  x += size; break;
 199     }
 200     return lookupcube(x, y, z, rsize);
 201 }
 202
 203 int lookupmaterial(const vec &v)
 204 {
 205     ivec o(v);
 206     if(!insideworld(o)) return MAT_AIR;
 207     int scale = worldscale-1;
 208     cube *c = &worldroot[octastep(o.x, o.y, o.z, scale)];
 209     while(c->children)
 210     {
 211         scale--;
 212         c = &c->children[octastep(o.x, o.y, o.z, scale)];
 213     }
 214     return c->ext ? c->ext->material : MAT_AIR;
 215 }
 216
 217 ////////// (re)mip //////////
 218
 219 int getmippedtexture(cube &p, int orient)
 220 {
 221     cube *c = p.children;
 222     int d = dimension(orient);
 223     int dc = dimcoord(orient);
 224     int tex[4] = {-1,-1,-1,-1};
 225     loop(x,2) loop(y,2)
 226     {
 227         int n = octaindex(d, x, y, dc);
 228         if(isempty(c[n]))
 229             n = oppositeocta(d, n);
 230         if(isempty(c[n]))
 231             continue;
 232
 233         loopk(3)
 234             if(tex[k] == c[n].texture[orient])
 235                 return tex[k];
 236
 237         if(c[n].texture[orient] > 0) // assume 0 is sky. favour non-sky tex
 238             tex[x*2+y] = c[n].texture[orient];
 239     }
 240
 241     loopk(4)
 242         if(tex[k]>0) return tex[k];
 243
 244     return p.texture[orient];
 245 }
 246
 247 void forcemip(cube &c)
 248 {
 249     cube *ch = c.children;
 250     emptyfaces(c);
 251
 252     loopi(8) loopj(8)
 253     {
 254         int n = i^(j==3 ? 4 : (j==4 ? 3 : j));
 255         if(!isempty(ch[n])) // breadth first search for cube near vert
 256         {
 257             ivec v, p(i);
 258             getcubevector(ch[n], 2, p.x, p.y, p.z, v);
 259
 260             loopk(3) // adjust vert to parent size
 261             {
 262                 if(octacoord(k, n) == 1)
 263                     v[k] += 8;
 264                 v[k] >>= 1;
 265             }
 266
 267             setcubevector(c, 2, p.x, p.y, p.z, v);
 268             break;
 269         }
 270     }
 271
 272     loopj(6)
 273         c.texture[j] = getmippedtexture(c, j);
 274 }
 275
 276 int midedge(const ivec &a, const ivec &b, int xd, int yd, bool &perfect)
 277 {
 278     int ax = a[xd], bx = b[xd];
 279     int ay = a[yd], by = b[yd];
 280     if(ay==by) return ay;
 281     if(ax==bx) { perfect = false; return ay; }
 282     bool crossx = (ax<8 && bx>8) || (ax>8 && bx<8);
 283     bool crossy = (ay<8 && by>8) || (ay>8 && by<8);
 284     if(crossy && !crossx) { midedge(a,b,yd,xd,perfect); return 8; } // to test perfection
 285     if(ax<=8 && bx<=8) return ax>bx ? ay : by;
 286     if(ax>=8 && bx>=8) return ax<bx ? ay : by;
 287     int risex = (by-ay)*(8-ax)*256;
 288     int s = risex/(bx-ax);
 289     int y = s/256 + ay;
 290     if(((abs(s)&0xFF)!=0) || // ie: rounding error
 291         (crossy && y!=8) ||
 292         (y<0 || y>16)) perfect = false;
 293     return crossy ? 8 : min(max(y, 0), 16);
 294 }
 295
 296 bool subdividecube(cube &c, bool fullcheck, bool brighten)
 297 {
 298     if(c.children) return true;
 299         if(isempty(c) || isentirelysolid(c))
 300     {
 301         int mat = c.ext ? c.ext->material : MAT_AIR;
 302                 c.children = newcubes(isempty(c) ? F_EMPTY : F_SOLID);
 303         loopi(8)
 304         {
 305             loopl(6) c.children[i].texture[l] = c.texture[l];
 306             if(mat!=MAT_AIR) ext(c.children[i]).material = mat;
 307             if(brighten && !isempty(c)) brightencube(c.children[i]);
 308         }
 309         return true;
 310     }
 311     cube *ch = c.children = newcubes(F_SOLID);
 312     bool perfect = true, p1, p2;
 313     int mat = c.ext ? c.ext->material : MAT_AIR;
 314     ivec v[8];
 315     loopi(8)
 316     {
 317         ivec p(i);
 318         getcubevector(c, 2, p.x, p.y, p.z, v[i]);
 319         v[i].mul(2);
 320         if(mat!=MAT_AIR) ext(ch[i]).material = mat;
 321     }
 322
 323     loopj(6)
 324     {
 325         int d = dimension(j);
 326         int z = dimcoord(j);
 327         int e[3][3];
 328         ivec *v1[2][2];
 329         loop(y, 2) loop(x, 2)
 330             v1[x][y] = v+octaindex(d, x, y, z);
 331
 332         loop(y, 3) loop(x, 3)       // gen edges
 333         {
 334             if(x==1 && y==1)        // center
 335             {
 336                 int c1 = midedge(*v1[0][0], *v1[1][1], R[d], d, p1 = perfect);
 337                 int c2 = midedge(*v1[0][1], *v1[1][0], R[d], d, p2 = perfect);
 338                 e[x][y] = z ? max(c1,c2) : min(c1,c2);
 339                 perfect = e[x][y]==c1 ? p1 : p2;
 340             }
 341             else if(((x+y)&1)==0)   // corner
 342                 e[x][y] = (*v1[x>>1][y>>1])[d];
 343             else                    // edge
 344             {
 345                 int a = min(x, y), b = x&1;
 346                 e[x][y] = midedge(*v1[a][a], *v1[a^b][a^(1-b)], x==1?R[d]:C[d], d, perfect);
 347             }
 348         }
 349
 350         loopi(8)
 351         {
 352             ivec o(i);
 353             ch[i].texture[j] = c.texture[j];
 354             loop(y, 2) loop(x, 2) // assign child edges
 355             {
 356                 int ce = e[x+o[R[d]]][y+o[C[d]]];
 357                 if(o[D[d]]) ce -= 8;
 358                 ce = min(max(ce, 0), 8);
 359                 uchar &f = cubeedge(ch[i], d, x, y);
 360                 edgeset(f, z, ce);
 361             }
 362         }
 363     }
 364
 365     validatec(ch, hdr.worldsize);
 366     if(fullcheck) loopi(8) if(!isvalidcube(ch[i])) // not so good...
 367     {
 368         emptyfaces(ch[i]);
 369         perfect=false;
 370     }
 371     if(brighten) loopi(8) if(!isempty(ch[i])) brightencube(ch[i]);
 372     return perfect;
 373 }
 374
 375 bool crushededge(uchar e, int dc) { return dc ? e==0 : e==0x88; }
 376
 377 int visibleorient(cube &c, int orient)
 378 {
 379     loopi(2) loopj(2)
 380     {
 381         int a = faceedgesidx[orient][i*2 + 0];
 382         int b = faceedgesidx[orient][i*2 + 1];
 383         if(crushededge(c.edges[a],j) &&
 384            crushededge(c.edges[b],j) &&
 385            touchingface(c, orient)) return ((a>>2)<<1) + j;
 386     }
 387     return orient;
 388 }
 389
 390 VAR(mipvis, 0, 0, 1);
 391
 392 static int remipprogress = 0, remiptotal = 0;
 393
 394 bool remip(cube &c, int x, int y, int z, int size)
 395 {
 396     if(c.ext)
 397     {
 398         c.ext->merged = 0;
 399         if(c.ext->merges) freemergeinfo(c);
 400     }
 401
 402     cube *ch = c.children;
 403     if(!ch)
 404     {
 405         if(size<<1 <= VVEC_INT_MASK+1) return true;
 406         subdividecube(c);
 407         ch = c.children;
 408     }
 409     else if((remipprogress++&0x7FF)==1) show_out_of_renderloop_progress(float(remipprogress)/remiptotal, "remipping...");
 410
 411     bool perfect = true;
 412     uchar mat = ch[0].ext ? ch[0].ext->material : MAT_AIR;
 413
 414     loopi(8)
 415     {
 416         ivec o(i, x, y, z, size);
 417         if(!remip(ch[i], o.x, o.y, o.z, size>>1)) perfect = false;
 418     }
 419
 420     solidfaces(c); // so texmip is more consistent
 421     loopj(6)
 422         c.texture[j] = getmippedtexture(c, j); // parents get child texs regardless
 423
 424     if(!perfect) return false;
 425     if(size<<1 > VVEC_INT_MASK+1) return false;
 426
 427     cube n = c;
 428     forcemip(n);
 429     n.children = NULL;
 430     if(!subdividecube(n, false, false))
 431         { freeocta(n.children); return false; }
 432
 433     cube *nh = n.children;
 434     uchar vis[6] = {0, 0, 0, 0, 0, 0};
 435     loopi(8)
 436     {
 437         if(ch[i].faces[0] != nh[i].faces[0] ||
 438            ch[i].faces[1] != nh[i].faces[1] ||
 439            ch[i].faces[2] != nh[i].faces[2] ||
 440            (ch[i].ext ? ch[i].ext->material : MAT_AIR) != mat)
 441             { freeocta(nh); return false; }
 442
 443         if(isempty(ch[i]) && isempty(nh[i])) continue;
 444
 445         ivec o(i, x, y, z, size);
 446         loop(orient, 6)
 447             if(visibleface(ch[i], orient, o.x, o.y, o.z, size))
 448             {
 449                 if(ch[i].texture[orient] != n.texture[orient]) { freeocta(nh); return false; }
 450                 vis[orient] |= 1<<i;
 451             }
 452     }
 453     if(mipvis) loop(orient, 6)
 454     {
 455         int mask = 0;
 456         loop(x, 2) loop(y, 2) mask |= 1<<octaindex(dimension(orient), x, y, dimcoord(orient));
 457         if(vis[orient]&mask && (vis[orient]&mask)!=mask) { freeocta(nh); return false; }
 458     }
 459
 460     freeocta(nh);
 461     discardchildren(c);
 462     loopi(3) c.faces[i] = n.faces[i];
 463     if(mat!=MAT_AIR) ext(c).material = mat;
 464     brightencube(c);
 465     return true;
 466 }
 467
 468 void mpremip(bool local)
 469 {
 470     extern selinfo sel;
 471     if(local) cl->edittrigger(sel, EDIT_REMIP);
 472     remipprogress = 1;
 473     remiptotal = allocnodes;
 474     loopi(8)
 475     {
 476         ivec o(i, 0, 0, 0, hdr.worldsize>>1);
 477         remip(worldroot[i], o.x, o.y, o.z, hdr.worldsize>>2);
 478     }
 479     calcmerges();
 480     if(!local) allchanged();
 481 }
 482
 483 void remip_()
 484 {
 485     mpremip(true);
 486     allchanged();
 487 }
 488
 489 COMMANDN(remip, remip_, "");
 490
 491 uchar &edgelookup(cube &c, const ivec &p, int dim)
 492 {
 493    return c.edges[dim*4 +(p[C[dim]]>>3)*2 +(p[R[dim]]>>3)];
 494 }
 495
 496 int edgeval(cube &c, const ivec &p, int dim, int coord)
 497 {
 498     return edgeget(edgelookup(c,p,dim), coord);
 499 }
 500
 501 void genvertp(cube &c, ivec &p1, ivec &p2, ivec &p3, plane &pl)
 502 {
 503     int dim = 0;
 504     if(p1.y==p2.y && p2.y==p3.y) dim = 1;
 505     else if(p1.z==p2.z && p2.z==p3.z) dim = 2;
 506
 507     int coord = p1[dim];
 508
 509     ivec v1(p1), v2(p2), v3(p3);
 510     v1[D[dim]] = edgeval(c, p1, dim, coord);
 511     v2[D[dim]] = edgeval(c, p2, dim, coord);
 512     v3[D[dim]] = edgeval(c, p3, dim, coord);
 513
 514     pl.toplane(v1.tovec(), v2.tovec(), v3.tovec());
 515 }
 516
 517 bool threeplaneintersect(plane &pl1, plane &pl2, plane &pl3, vec &dest)
 518 {
 519     vec &t1 = dest, t2, t3, t4;
 520     t1.cross(pl1, pl2); t4 = t1; t1.mul(pl3.offset);
 521     t2.cross(pl3, pl1);          t2.mul(pl2.offset);
 522     t3.cross(pl2, pl3);          t3.mul(pl1.offset);
 523     t1.add(t2);
 524     t1.add(t3);
 525     t1.mul(-1);
 526     float d = t4.dot(pl3);
 527     if(d==0) return false;
 528     t1.div(d);
 529     return true;
 530 }
 531
 532 void genedgespanvert(ivec &p, cube &c, vec &v)
 533 {
 534     ivec p1(8-p.x, p.y, p.z);
 535     ivec p2(p.x, 8-p.y, p.z);
 536     ivec p3(p.x, p.y, 8-p.z);
 537
 538     cube s;
 539     solidfaces(s);
 540
 541     plane plane1, plane2, plane3;
 542     genvertp(c, p, p1, p2, plane1);
 543     genvertp(c, p, p2, p3, plane2);
 544     genvertp(c, p, p3, p1, plane3);
 545     if(plane1==plane2) genvertp(s, p, p1, p2, plane1);
 546     if(plane1==plane3) genvertp(s, p, p1, p2, plane1);
 547     if(plane2==plane3) genvertp(s, p, p2, p3, plane2);
 548
 549     ASSERT(threeplaneintersect(plane1, plane2, plane3, v));
 550     //ASSERT(v.x>=0 && v.x<=8);
 551     //ASSERT(v.y>=0 && v.y<=8);
 552     //ASSERT(v.z>=0 && v.z<=8);
 553     v.x = max(0.0f, min(8.0f, v.x));
 554     v.y = max(0.0f, min(8.0f, v.y));
 555     v.z = max(0.0f, min(8.0f, v.z));
 556 }
 557
 558 void edgespan2vectorcube(cube &c)
 559 {
 560     vec v;
 561
 562     if(c.children) loopi(8) edgespan2vectorcube(c.children[i]);
 563
 564     if(isentirelysolid(c) || isempty(c)) return;
 565
 566     cube n = c;
 567
 568     loop(x,2) loop(y,2) loop(z,2)
 569     {
 570         ivec p(8*x, 8*y, 8*z);
 571         genedgespanvert(p, c, v);
 572
 573         edgeset(cubeedge(n, 0, y, z), x, int(v.x+0.49f));
 574         edgeset(cubeedge(n, 1, z, x), y, int(v.y+0.49f));
 575         edgeset(cubeedge(n, 2, x, y), z, int(v.z+0.49f));
 576     }
 577
 578     c = n;
 579 }
 580
 581 void converttovectorworld()
 582 {
 583     conoutf(CON_WARN, "WARNING: old map, use savecurrentmap");
 584     loopi(8) edgespan2vectorcube(worldroot[i]);
 585 }
 586
 587 void genvectorvert(const ivec &p, cube &c, ivec &v)
 588 {
 589     v.x = edgeval(c, p, 0, p.x);
 590     v.y = edgeval(c, p, 1, p.y);
 591     v.z = edgeval(c, p, 2, p.z);
 592 }
 593
 594 const ivec cubecoords[8] = // verts of bounding cube
 595 {
 596     ivec(8, 8, 0),
 597     ivec(0, 8, 0),
 598     ivec(0, 8, 8),
 599     ivec(8, 8, 8),
 600     ivec(8, 0, 8),
 601     ivec(0, 0, 8),
 602     ivec(0, 0, 0),
 603     ivec(8, 0, 0),
 604 };
 605
 606 const ushort fv[6][4] = // indexes for cubecoords, per each vert of a face orientation
 607 {
 608     { 2, 1, 6, 5 },
 609     { 3, 4, 7, 0 },
 610     { 4, 5, 6, 7 },
 611     { 1, 2, 3, 0 },
 612     { 6, 1, 0, 7 },
 613     { 5, 4, 3, 2 },
 614 };
 615
 616 const uchar fvmasks[64] = // mask of verts used given a mask of visible face orientations
 617 {
 618     0x00, 0x66, 0x99, 0xFF, 0xF0, 0xF6, 0xF9, 0xFF,
 619     0x0F, 0x6F, 0x9F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 620     0xC3, 0xE7, 0xDB, 0xFF, 0xF3, 0xF7, 0xFB, 0xFF,
 621     0xCF, 0xEF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 622     0x3C, 0x7E, 0xBD, 0xFF, 0xFC, 0xFE, 0xFD, 0xFF,
 623     0x3F, 0x7F, 0xBF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 624     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 625     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 626 };
 627
 628 const uchar faceedgesidx[6][4] = // ordered edges surrounding each orient
 629 {//1st face,2nd face
 630     { 4, 5, 8, 10 },
 631     { 6, 7, 9, 11 },
 632     { 0, 2, 8, 9  },
 633     { 1, 3, 10,11 },
 634     { 0, 1, 4, 6 },
 635     { 2, 3, 5, 7 },
 636 };
 637
 638 const uchar faceedgesrcidx[6][4] =
 639 {//0..1 = row edges, 2..3 = column edges
 640     { 4,  5,  8, 10 },
 641     { 6,  7,  9, 11 },
 642     { 8,  9,  0, 2 },
 643     { 10, 11, 1, 3 },
 644     { 0,  1,  4, 6 },
 645     { 2,  3,  5, 7 },
 646 };
 647
 648 bool flataxisface(cube &c, int orient)
 649 {
 650     uint face = c.faces[dimension(orient)];
 651     if(dimcoord(orient)) face >>= 4;
 652     face &= 0x0F0F0F0F;
 653     return face == 0x01010101*(face&0x0F);
 654 }
 655
 656 bool touchingface(cube &c, int orient)
 657 {
 658     uint face = c.faces[dimension(orient)];
 659     return dimcoord(orient) ? (face&0xF0F0F0F0)==0x80808080 : (face&0x0F0F0F0F)==0;
 660 }
 661
 662 int faceconvexity(cube &c, int orient)
 663 {
 664    /* // fast approximation
 665     vec v[4];
 666     int d = dimension(orient);
 667     loopi(4) vertrepl(c, *(ivec *)cubecoords[fv[orient][i]], v[i], d, dimcoord(orient));
 668     int n = (int)(v[0][d] - v[1][d] + v[2][d] - v[3][d]);
 669     if (!dimcoord(orient)) n *= -1;
 670     return n; // returns +ve if convex when tris are verts 012, 023. -ve for concave.
 671     */
 672     // slow perfect
 673     ivec v[4];
 674
 675     if(flataxisface(c, orient)) return 0;
 676
 677     loopi(4) genvectorvert(cubecoords[fv[orient][i]], c, v[i]);
 678
 679     ivec n;
 680     n.cross(v[1].sub(v[0]), v[2].sub(v[0]));
 681     int x = n.dot(v[0]), y = n.dot(v[3]);
 682     if(x < y) return -1;     // concave
 683     else if(x > y) return 1; // convex
 684     else return 0;           // flat
 685 }
 686
 687 int faceorder(cube &c, int orient)
 688 {
 689 /*
 690     uchar *edges = &c.edges[4*dimension(orient)];
 691     uchar h[4];
 692     loopi(4) h[i] = dimcoord(orient) ? edges[i]>>4 : 8-(edges[i]&0xF);
 693     if(h[0]+h[3]<h[1]+h[2]) return 1;
 694     else return 0;
 695 */
 696     return faceconvexity(c, orient)<0 ? 1 : 0;
 697 }
 698
 699 int faceverts(cube &c, int orient, int vert) // gets above 'fv' so that each face is convex
 700 {
 701     return fv[orient][(vert + faceorder(c, orient))&3];
 702 }
 703
 704 uint faceedges(cube &c, int orient)
 705 {
 706     uchar edges[4];
 707     loopk(4) edges[k] = c.edges[faceedgesidx[orient][k]];
 708     return *(uint *)edges;
 709 }
 710
 711 struct facevec
 712 {
 713     int x, y;
 714
 715     facevec() {}
 716     facevec(int x, int y) : x(x), y(y) {}
 717
 718     bool operator==(const facevec &f) const { return x == f.x && y == f.y; }
 719 };
 720
 721 static inline void genfacevecs(cube &c, int orient, const ivec &pos, int size, bool solid, facevec *fvecs)
 722 {
 723     int dim = dimension(orient), coord = dimcoord(orient);
 724     const ushort *fvo = fv[orient];
 725     loopi(4)
 726     {
 727         const ivec &cc = cubecoords[fvo[i]];
 728         facevec &f = fvecs[coord ? i : 3 - i];
 729         int x, y;
 730         if(solid)
 731         {
 732             x = cc[C[dim]];
 733             y = cc[R[dim]];
 734         }
 735         else
 736         {
 737             x = edgeval(c, cc, C[dim], cc[C[dim]]);
 738             y = edgeval(c, cc, R[dim], cc[R[dim]]);
 739         }
 740         f.x = x*size/(8>>VVEC_FRAC)+(pos[C[dim]]<<VVEC_FRAC);
 741         f.y = y*size/(8>>VVEC_FRAC)+(pos[R[dim]]<<VVEC_FRAC);
 742     }
 743 }
 744
 745 static inline int clipfacevecy(const facevec &o, const facevec &dir, int cx, int cy, int size, facevec &r)
 746 {
 747     if(dir.x >= 0)
 748     {
 749         if(cx <= o.x || cx >= o.x+dir.x) return 0;
 750     }
 751     else if(cx <= o.x+dir.x || cx >= o.x) return 0;
 752
 753     int t = (o.y-cy) + (cx-o.x)*dir.y/dir.x;
 754     if(t <= 0 || t >= size) return 0;
 755
 756     r.x = cx;
 757     r.y = cy + t;
 758     return 1;
 759 }
 760
 761 static inline int clipfacevecx(const facevec &o, const facevec &dir, int cx, int cy, int size, facevec &r)
 762 {
 763     if(dir.y >= 0)
 764     {
 765         if(cy <= o.y || cy >= o.y+dir.y) return 0;
 766     }
 767     else if(cy <= o.y+dir.y || cy >= o.y) return 0;
 768
 769     int t = (o.x-cx) + (cy-o.y)*dir.x/dir.y;
 770     if(t <= 0 || t >= size) return 0;
 771
 772     r.x = cx + t;
 773     r.y = cy;
 774     return 1;
 775 }
 776
 777 static inline int clipfacevec(const facevec &o, const facevec &dir, int cx, int cy, int size, facevec *rvecs)
 778 {
 779     int r = 0;
 780
 781     if(o.x >= cx && o.x <= cx+size &&
 782        o.y >= cy && o.y <= cy+size &&
 783        ((o.x != cx && o.x != cx+size) || (o.y != cy && o.y != cy+size)))
 784     {
 785         rvecs[0].x = o.x;
 786         rvecs[0].y = o.y;
 787         r++;
 788     }
 789
 790     r += clipfacevecx(o, dir, cx, cy, size, rvecs[r]);
 791     r += clipfacevecx(o, dir, cx, cy+size, size, rvecs[r]);
 792     r += clipfacevecy(o, dir, cx, cy, size, rvecs[r]);
 793     r += clipfacevecy(o, dir, cx+size, cy, size, rvecs[r]);
 794
 795     ASSERT(r <= 2);
 796     return r;
 797 }
 798
 799 static inline bool insideface(const facevec *p, int nump, const facevec *o)
 800 {
 801     int bounds = 0;
 802     loopi(4)
 803     {
 804         const facevec &cur = o[i], &next = o[(i+1)%4];
 805         if(cur == next) continue;
 806         facevec dir(next.x-cur.x, next.y-cur.y);
 807         int offset = dir.x*cur.y - dir.y*cur.x;
 808         loopj(nump) if(dir.x*p[j].y - dir.y*p[j].x > offset) return false;
 809         bounds++;
 810     }
 811     return bounds>=3;
 812 }
 813
 814 static inline int clipfacevecs(const facevec *o, int cx, int cy, int size, facevec *rvecs)
 815 {
 816     cx <<= VVEC_FRAC;
 817     cy <<= VVEC_FRAC;
 818     size <<= VVEC_FRAC;
 819
 820     int r = 0;
 821     loopi(4)
 822     {
 823         const facevec &cur = o[i], &next = o[(i+1)%4];
 824         if(cur == next) continue;
 825         facevec dir(next.x-cur.x, next.y-cur.y);
 826         r += clipfacevec(cur, dir, cx, cy, size, &rvecs[r]);
 827     }
 828     facevec corner[4] = {facevec(cx, cy), facevec(cx+size, cy), facevec(cx+size, cy+size), facevec(cx, cy+size)};
 829     loopi(4) if(insideface(&corner[i], 1, o)) rvecs[r++] = corner[i];
 830     ASSERT(r <= 8);
 831     return r;
 832 }
 833
 834 bool collapsedface(uint cfe)
 835 {
 836     return ((cfe >> 4) & 0x0F0F) == (cfe & 0x0F0F) ||
 837            ((cfe >> 20) & 0x0F0F) == ((cfe >> 16) & 0x0F0F);
 838 }
 839
 840 static inline bool occludesface(cube &c, int orient, const ivec &o, int size, const ivec &vo, int vsize, uchar vmat, uchar nmat, uchar matmask, const facevec *vf)
 841 {
 842     int dim = dimension(orient);
 843     if(!c.children)
 844     {
 845          if(nmat != MAT_AIR && c.ext && (c.ext->material&matmask) == nmat)
 846          {
 847             facevec nf[8];
 848             return clipfacevecs(vf, o[C[dim]], o[R[dim]], size, nf) < 3;
 849          }
 850          if(isentirelysolid(c)) return true;
 851          if(vmat != MAT_AIR && c.ext && ((c.ext->material&matmask) == vmat || (isliquid(vmat) && isclipped(c.ext->material&MATF_VOLUME)))) return true;
 852          if(touchingface(c, orient) && faceedges(c, orient) == F_SOLID) return true;
 853          facevec cf[8];
 854          int numc = clipfacevecs(vf, o[C[dim]], o[R[dim]], size, cf);
 855          if(numc < 3) return true;
 856          if(isempty(c) || !touchingface(c, orient)) return false;
 857          facevec of[4];
 858          genfacevecs(c, orient, o, size, false, of);
 859          return insideface(cf, numc, of);
 860     }
 861
 862     size >>= 1;
 863     int coord = dimcoord(orient);
 864     loopi(8) if(octacoord(dim, i) == coord)
 865     {
 866         if(!occludesface(c.children[i], orient, ivec(i, o.x, o.y, o.z, size), size, vo, vsize, vmat, nmat, matmask, vf)) return false;
 867     }
 868
 869     return true;
 870 }
 871
 872 bool visibleface(cube &c, int orient, int x, int y, int z, int size, uchar mat, uchar nmat, uchar matmask)
 873 {
 874     uint cfe = faceedges(c, orient);
 875     if(mat != MAT_AIR)
 876     {
 877         if(cfe==F_SOLID && touchingface(c, orient)) return false;
 878     }
 879     else
 880     {
 881         if(!touchingface(c, orient)) return true;
 882         if(collapsedface(cfe)) return false;
 883     }
 884
 885     cube &o = neighbourcube(x, y, z, size, -size, orient);
 886     if(&o==&c) return false;
 887
 888     if(lusize > size || (lusize == size && !o.children))
 889     {
 890         if(nmat != MAT_AIR && o.ext && (o.ext->material&matmask) == nmat) return true;
 891         if(isentirelysolid(o)) return false;
 892         if(mat != MAT_AIR && o.ext && ((o.ext->material&matmask) == mat || (isliquid(mat) && (o.ext->material&MATF_VOLUME) == MAT_GLASS))) return false;
 893         if(isempty(o) || !touchingface(o, opposite(orient))) return true;
 894         if(faceedges(o, opposite(orient)) == F_SOLID) return false;
 895
 896         ivec vo(x, y, z);
 897         vo.mask(VVEC_INT_MASK);
 898         lu.mask(VVEC_INT_MASK);
 899         facevec cf[4], of[4];
 900         genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf);
 901         genfacevecs(o, opposite(orient), lu, lusize, false, of);
 902         return !insideface(cf, 4, of);
 903     }
 904
 905     ivec vo(x, y, z);
 906     vo.mask(VVEC_INT_MASK);
 907     lu.mask(VVEC_INT_MASK);
 908     facevec cf[4];
 909     genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf);
 910     return !occludesface(o, opposite(orient), lu, lusize, vo, size, mat, nmat, matmask, cf);
 911 }
 912
 913 void calcvert(cube &c, int x, int y, int z, int size, vvec &v, int i, bool solid)
 914 {
 915     ivec vv;
 916     if(solid || isentirelysolid(c)) vv = cubecoords[i];
 917     else genvectorvert(cubecoords[i], c, vv);
 918     v = vvec(vv.v);
 919     // avoid overflow
 920     if(size>=8) v.mul(size/8);
 921     else v.div(8/size);
 922     v.add(vvec(x, y, z));
 923 }
 924
 925 void calcvert(cube &c, int x, int y, int z, int size, vec &v, int i, bool solid)
 926 {
 927     ivec vv;
 928     if(solid || isentirelysolid(c)) vv = cubecoords[i];
 929     else genvectorvert(cubecoords[i], c, vv);
 930     v = vv.tovec().mul(size/8.0f).add(vec(x, y, z));
 931 }
 932
 933 int calcverts(cube &c, int x, int y, int z, int size, vvec *verts, bool *usefaces)
 934 {
 935     int vertused = 0;
 936     loopi(6) if((usefaces[i] = visibleface(c, i, x, y, z, size))) vertused |= fvmasks[1<<i];
 937     //loopk(4) vertused |= 1<<faceverts(c,i,k);
 938     loopi(8) if(vertused&(1<<i)) calcvert(c, x, y, z, size, verts[i], i);
 939     return vertused;
 940 }
 941
 942 int genclipplane(cube &c, int orient, vec *v, plane *clip)
 943 {
 944     int planes = 0;
 945     vec p[4];
 946     loopk(4) p[k] = v[faceverts(c,orient,k)];
 947
 948     if(p[0]==p[2]) return 0;
 949     if(p[0]!=p[1] && p[1]!=p[2]) clip[planes++].toplane(p[0], p[1], p[2]);
 950     if(p[0]!=p[3] && p[2]!=p[3] && (!planes || faceconvexity(c, orient))) clip[planes++].toplane(p[0], p[2], p[3]);
 951     return planes;
 952 }
 953
 954 void genclipplanes(cube &c, int x, int y, int z, int size, clipplanes &p)
 955 {
 956     bool usefaces[6];
 957     vvec sv[8];
 958     vec v[8];
 959     vec mx(x, y, z), mn(x+size, y+size, z+size);
 960     int vertused = calcverts(c, x, y, z, size, sv, usefaces);
 961
 962     loopi(8)
 963     {
 964         if(!(vertused&(1<<i))) // need all verts for proper box
 965             calcvert(c, x, y, z, size, sv[i], i);
 966
 967         v[i] = sv[i].tovec(x, y, z);
 968
 969         loopj(3) // generate tight bounding box
 970         {
 971             mn[j] = min(mn[j], v[i].v[j]);
 972             mx[j] = max(mx[j], v[i].v[j]);
 973         }
 974     }
 975
 976     p.r = mx;     // radius of box
 977     p.r.sub(mn);
 978     p.r.mul(0.5f);
 979     p.o = mn;     // center of box
 980     p.o.add(p.r);
 981
 982     p.size = 0;
 983     loopi(6) if(usefaces[i] && !touchingface(c, i)) // generate actual clipping planes
 984     {
 985         p.size += genclipplane(c, i, v, &p.p[p.size]);
 986     }
 987 }
 988
 989 static int mergefacecmp(const cubeface *x, const cubeface *y)
 990 {
 991     if(x->v2 < y->v2) return -1;
 992     if(x->v2 > y->v2) return 1;
 993     if(x->u1 < y->u1) return -1;
 994     if(x->u1 > y->u1) return 1;
 995     return 0;
 996 }
 997
 998 static int mergefacev(int orient, cubeface *m, int sz, cubeface &n)
 999 {
1000     for(int i = sz-1; i >= 0; --i)
1001     {
1002         if(m[i].v2 < n.v1) break;
1003         if(m[i].v2 == n.v1 && m[i].u1 == n.u1 && m[i].u2 == n.u2)
1004         {
1005             if(m[i].c) ext(*m[i].c).merged |= 1<<orient;
1006             if(n.c) ext(*n.c).merged |= 1<<orient;
1007             n.v1 = m[i].v1;
1008             memmove(&m[i], &m[i+1], (sz - (i+1)) * sizeof(cubeface));
1009             return 1;
1010         }
1011     }
1012     return 0;
1013 }
1014
1015 static int mergefaceu(int orient, cubeface &m, cubeface &n)
1016 {
1017     if(m.v1 == n.v1 && m.v2 == n.v2 && m.u2 == n.u1)
1018     {
1019         if(m.c) ext(*m.c).merged |= 1<<orient;
1020         if(n.c) ext(*n.c).merged |= 1<<orient;
1021         n.u1 = m.u1;
1022         return 1;
1023     }
1024     return 0;
1025 }
1026
1027 static int mergeface(int orient, cubeface *m, int sz, cubeface &n)
1028 {
1029     for(bool merged = false; sz; merged = true)
1030     {
1031         int vmerged = mergefacev(orient, m, sz, n);
1032         sz -= vmerged;
1033         if(!vmerged && merged) break;
1034         if(!sz) break;
1035         int umerged = mergefaceu(orient, m[sz-1], n);
1036         sz -= umerged;
1037         if(!umerged) break;
1038     }
1039     m[sz++] = n;
1040     return sz;
1041 }
1042
1043 int mergefaces(int orient, cubeface *m, int sz)
1044 {
1045     qsort(m, sz, sizeof(cubeface), (int (__cdecl *)(const void *, const void *))mergefacecmp);
1046
1047     int nsz = 0;
1048     loopi(sz) nsz = mergeface(orient, m, nsz, m[i]);
1049     return nsz;
1050 }
1051
1052 struct cfkey
1053 {
1054     uchar orient;
1055     ushort tex;
1056     ivec n;
1057     int offset;
1058 };
1059
1060 static inline bool htcmp(const cfkey &x, const cfkey &y)
1061 {
1062     return x.orient == y.orient && x.tex == y.tex && x.n == y.n && x.offset == y.offset;
1063 }
1064
1065 static inline uint hthash(const cfkey &k)
1066 {
1067     return hthash(k.n)^k.offset^k.tex^k.orient;
1068 }
1069
1070 struct cfval
1071 {
1072     vector<cubeface> faces;
1073 };
1074
1075 static hashtable<cfkey, cfval> cfaces;
1076
1077 void mincubeface(cube &cu, int orient, const ivec &o, int size, const mergeinfo &orig, mergeinfo &cf)
1078 {
1079     int dim = dimension(orient);
1080     if(cu.children)
1081     {
1082         size >>= 1;
1083         int coord = dimcoord(orient);
1084         loopi(8) if(octacoord(dim, i) == coord)
1085             mincubeface(cu.children[i], orient, ivec(i, o.x, o.y, o.z, size), size, orig, cf);
1086         return;
1087     }
1088     int c = C[dim], r = R[dim];
1089     ushort uco = ushort((o[c]&VVEC_INT_MASK)<<VVEC_FRAC), vco = ushort((o[r]&VVEC_INT_MASK)<<VVEC_FRAC);
1090     ushort uc1 = uco, vc1 = vco, uc2 = ushort(size<<VVEC_FRAC)+uco, vc2 = ushort(size<<VVEC_FRAC)+vco;
1091     uc1 = max(uc1, orig.u1);
1092     uc2 = min(uc2, orig.u2);
1093     vc1 = max(vc1, orig.v1);
1094     vc2 = min(vc2, orig.v2);
1095     if(!isempty(cu) && touchingface(cu, orient))
1096     {
1097         uchar r1 = cu.edges[faceedgesrcidx[orient][0]], r2 = cu.edges[faceedgesrcidx[orient][1]],
1098               c1 = cu.edges[faceedgesrcidx[orient][2]], c2 = cu.edges[faceedgesrcidx[orient][3]];
1099         ushort scale = ushort(size/(8>>VVEC_FRAC)),
1100               u1 = max(c1&0xF, c2&0xF)*scale+uco, u2 = min(c1>>4, c2>>4)*scale+uco,
1101               v1 = max(r1&0xF, r2&0xF)*scale+vco, v2 = min(r1>>4, r2>>4)*scale+vco;
1102         u1 = max(u1, orig.u1);
1103         u2 = min(u2, orig.u2);
1104         v1 = max(v1, orig.v1);
1105         v2 = min(v2, orig.v2);
1106         if(v2-v1==vc2-vc1)
1107         {
1108             if(u2-u1==uc2-uc1) return;
1109             if(u1==uc1) uc1 = u2;
1110             if(u2==uc2) uc2 = u1;
1111         }
1112         else if(u2-u1==uc2-uc1)
1113         {
1114             if(v1==vc1) vc1 = v2;
1115             if(v2==vc2) vc2 = v1;
1116         }
1117     }
1118     if(uc1==uc2 || vc1==vc2) return;
1119     cf.u1 = min(cf.u1, uc1);
1120     cf.u2 = max(cf.u2, uc2);
1121     cf.v1 = min(cf.v1, vc1);
1122     cf.v2 = max(cf.v2, vc2);
1123 }
1124
1125 bool mincubeface(cube &cu, int orient, const ivec &co, int size, mergeinfo &orig)
1126 {
1127     cube &nc = neighbourcube(co.x, co.y, co.z, size, -size, orient);
1128     mergeinfo mincf;
1129     mincf.u1 = orig.u2;
1130     mincf.u2 = orig.u1;
1131     mincf.v1 = orig.v2;
1132     mincf.v2 = orig.v1;
1133     mincubeface(nc, opposite(orient), lu, lusize, orig, mincf);
1134     bool smaller = false;
1135     if(mincf.u1 > orig.u1) { orig.u1 = mincf.u1; smaller = true; }
1136     if(mincf.u2 < orig.u2) { orig.u2 = mincf.u2; smaller = true; }
1137     if(mincf.v1 > orig.v1) { orig.v1 = mincf.v1; smaller = true; }
1138     if(mincf.v2 < orig.v2) { orig.v2 = mincf.v2; smaller = true; }
1139     return smaller;
1140 }
1141
1142 VAR(minface, 0, 1, 1);
1143
1144 bool gencubeface(cube &cu, int orient, const ivec &co, int size, ivec &n, int &offset, cubeface &cf)
1145 {
1146     uchar cfe[4];
1147     *(uint *)cfe = faceedges(cu, orient);
1148     if(cfe[0]!=cfe[1] || cfe[2]!=cfe[3] || (cfe[0]>>4)==(cfe[0]&0xF) || (cfe[2]>>4)==(cfe[2]&0xF)) return false;
1149     if(faceconvexity(cu, orient)) return false;
1150
1151     cf.c = &cu;
1152
1153     ivec v[4];
1154     loopi(4) genvectorvert(cubecoords[fv[orient][i]], cu, v[i]);
1155
1156     int scale = size/(8>>VVEC_FRAC);
1157     v[3].mul(scale);
1158     int dim = dimension(orient), c = C[dim], r = R[dim];
1159     cf.u1 = cf.u2 = ushort(v[3][c]);
1160     cf.v1 = cf.v2 = ushort(v[3][r]);
1161
1162     loopi(3)
1163     {
1164         ushort uc = ushort(v[i][c]*scale), vc = ushort(v[i][r]*scale);
1165         cf.u1 = min(cf.u1, uc);
1166         cf.u2 = max(cf.u2, uc);
1167         cf.v1 = min(cf.v1, vc);
1168         cf.v2 = max(cf.v2, vc);
1169     }
1170
1171     ivec vo(co);
1172     vo.mask(VVEC_INT_MASK);
1173     vo.mul(1<<VVEC_FRAC);
1174
1175     ushort uco = ushort(vo[c]), vco = ushort(vo[r]);
1176     cf.u1 += uco;
1177     cf.u2 += uco;
1178     cf.v1 += vco;
1179     cf.v2 += vco;
1180
1181     v[1].sub(v[0]);
1182     v[2].sub(v[0]);
1183     n.cross(v[1], v[2]);
1184
1185     // reduce the normal as much as possible without resorting to floating point
1186     int mindim = -1, minval = 64;
1187     loopi(3) if(n[i])
1188     {
1189         int val = abs(n[i]);
1190         if(mindim < 0 || val < minval)
1191         {
1192             mindim = i;
1193             minval = val;
1194         }
1195     }
1196     if(!(n[R[mindim]]%minval) && !(n[C[mindim]]%minval))
1197     {
1198         n[mindim] /= minval;
1199         n[R[mindim]] /= minval;
1200         n[C[mindim]] /= minval;
1201     }
1202     while((n[0]&1)==0 && (n[1]&1)==0 && (n[2]&1)==0)
1203     {
1204         n[0] >>= 1;
1205         n[1] >>= 1;
1206         n[2] >>= 1;
1207     }
1208
1209     v[3].add(vo);
1210     offset = -n.dot(v[3]);
1211
1212     if(minface && touchingface(cu, orient) && mincubeface(cu, orient, co, size, cf))
1213     {
1214         ext(cu).merged |= 1<<orient;
1215     }
1216
1217     return true;
1218 }
1219
1220 void addmergeinfo(cube &c, int orient, cubeface &cf)
1221 {
1222     if(!c.ext) newcubeext(c);
1223     int index = 0;
1224     loopi(orient) if(c.ext->mergeorigin&(1<<i)) index++;
1225     int total = index;
1226     loopi(6-orient-1) if(c.ext->mergeorigin&(1<<(i+orient+1))) total++;
1227     mergeinfo *m = new mergeinfo[total+1];
1228     if(index) memcpy(m, c.ext->merges, index*sizeof(mergeinfo));
1229     if(total>index) memcpy(&m[index+1], &c.ext->merges[index], (total-index)*sizeof(mergeinfo));
1230     if(c.ext->merges) delete[] c.ext->merges;
1231     c.ext->merges = m;
1232     m += index;
1233     c.ext->mergeorigin |= 1<<orient;
1234     m->u1 = cf.u1;
1235     m->u2 = cf.u2;
1236     m->v1 = cf.v1;
1237     m->v2 = cf.v2;
1238 }
1239
1240 void freemergeinfo(cube &c)
1241 {
1242     if(!c.ext) return;
1243     c.ext->mergeorigin = 0;
1244     DELETEA(c.ext->merges);
1245 }
1246
1247 VAR(maxmerge, 0, 6, VVEC_INT-1);
1248
1249 static int genmergeprogress = 0;
1250
1251 void genmergeinfo(cube *c = worldroot, const ivec &o = ivec(0, 0, 0), int size = hdr.worldsize>>1)
1252 {
1253     if((genmergeprogress++&0x7FF)==0) show_out_of_renderloop_progress(float(genmergeprogress)/allocnodes, "merging surfaces...");
1254     loopi(8)
1255     {
1256         ivec co(i, o.x, o.y, o.z, size);
1257         if(c[i].ext)
1258         {
1259             if(c[i].ext->merges) freemergeinfo(c[i]);
1260             c[i].ext->merged = 0;
1261         }
1262         if(c[i].children) genmergeinfo(c[i].children, co, size>>1);
1263         else if(!isempty(c[i])) loopj(6) if(visibleface(c[i], j, co.x, co.y, co.z, size))
1264         {
1265             cfkey k;
1266             cubeface cf;
1267             if(gencubeface(c[i], j, co, size, k.n, k.offset, cf))
1268             {
1269                 if(size >= 1<<maxmerge || c == worldroot)
1270                 {
1271                     if(c[i].ext && c[i].ext->merged&(1<<j)) addmergeinfo(c[i], j, cf);
1272                     continue;
1273                 }
1274                 k.orient = j;
1275                 k.tex = c[i].texture[j];
1276                 cfaces[k].faces.add(cf);
1277             }
1278         }
1279         if((size == 1<<maxmerge || c == worldroot) && cfaces.numelems)
1280         {
1281             ASSERT(size <= 1<<maxmerge);
1282             enumeratekt(cfaces, cfkey, key, cfval, val,
1283                 val.faces.setsize(mergefaces(key.orient, val.faces.getbuf(), val.faces.length()));
1284                 loopvj(val.faces) if(val.faces[j].c->ext && val.faces[j].c->ext->merged&(1<<key.orient))
1285                 {
1286                     addmergeinfo(*val.faces[j].c, key.orient, val.faces[j]);
1287                 }
1288             );
1289             cfaces.clear();
1290         }
1291
1292     }
1293 }
1294
1295 void genmergedverts(cube &cu, int orient, const ivec &co, int size, const mergeinfo &m, vvec *vv, plane *p)
1296 {
1297     ivec vo(co);
1298     vo.mask(VVEC_INT_MASK);
1299     vo.mul(1<<VVEC_FRAC);
1300
1301     ivec v[3], n;
1302     loopi(3) genvectorvert(cubecoords[faceverts(cu, orient, i)], cu, v[i]);
1303     v[1].sub(v[0]);
1304     v[2].sub(v[0]);
1305     n.cross(v[1], v[2]);
1306
1307     ASSERT(size >= 8>>VVEC_FRAC);
1308     v[0].mul(size/(8>>VVEC_FRAC));
1309     v[0].add(vo);
1310     int offset = -n.dot(v[0]);
1311
1312     int dim = dimension(orient), c = C[dim], r = R[dim];
1313     loopi(4)
1314     {
1315         const ivec &coords = cubecoords[fv[orient][i]];
1316         int cc = coords[c] ? m.u2 : m.u1,
1317             rc = coords[r] ? m.v2 : m.v1,
1318             dc = -(offset + n[c]*cc + n[r]*rc)/n[dim];
1319         vv[i][c] = ushort(cc);
1320         vv[i][r] = ushort(rc);
1321         vv[i][dim] = ushort(dc);
1322     }
1323
1324     if(p)
1325     {
1326         ivec po(co);
1327         po.mask(~VVEC_INT_MASK);
1328         vec pn(n.tovec());
1329         float mag = pn.magnitude();
1330         pn.div(mag);
1331         *p = plane(pn, (offset-(n.dot(po)<<VVEC_FRAC))/(mag*(1<<VVEC_FRAC)));
1332     }
1333 }
1334
1335 int calcmergedsize(int orient, const ivec &co, int size, const mergeinfo &m, const vvec *vv)
1336 {
1337     int dim = dimension(orient), c = C[dim], r = R[dim];
1338     ushort d1 = vv[3][dim], d2 = d1;
1339     loopi(3)
1340     {
1341         d1 = min(d1, vv[i][dim]);
1342         d2 = max(d2, vv[i][dim]);
1343     }
1344     int bits = 0;
1345     while(1<<bits < size) ++bits;
1346     bits += VVEC_FRAC;
1347     ivec mo(co);
1348     mo.mask(VVEC_INT_MASK);
1349     mo.mul(1<<VVEC_FRAC);
1350     while(bits<VVEC_INT+VVEC_FRAC-1)
1351     {
1352         mo.mask(~((1<<bits)-1));
1353         if(mo[dim] <= d1 && mo[dim] + (1<<bits) >= d2 &&
1354            mo[c] <= m.u1 && mo[c] + (1<<bits) >= m.u2 &&
1355            mo[r] <= m.v1 && mo[r] + (1<<bits) >= m.v2)
1356             break;
1357         bits++;
1358     }
1359     return bits-VVEC_FRAC;
1360 }
1361
1362 void invalidatemerges(cube &c)
1363 {
1364     if(c.ext)
1365     {
1366         if(c.ext->va)
1367         {
1368             if(!(c.ext->va->hasmerges&(MERGE_PART | MERGE_ORIGIN))) return;
1369             destroyva(c.ext->va);
1370             c.ext->va = NULL;
1371         }
1372         if(c.ext->merged)
1373         {
1374             brightencube(c);
1375             c.ext->merged = 0;
1376             if(c.ext->merges) freemergeinfo(c);
1377         }
1378         if(c.ext->tjoints >= 0) c.ext->tjoints = -1;
1379     }
1380     if(c.children) loopi(8) invalidatemerges(c.children[i]);
1381 }
1382
1383 void calcmerges()
1384 {
1385     genmergeprogress = 0;
1386     genmergeinfo();
1387 }
1388