1 // core world management routines
2
3 #include "engine.h"
4
5 cube *worldroot = newcubes(F_SOLID);
6 int allocnodes = 0;
7
growcubeext(cubeext * old,int maxverts)8 cubeext *growcubeext(cubeext *old, int maxverts)
9 {
10 cubeext *ext = (cubeext *)new uchar[sizeof(cubeext) + maxverts*sizeof(vertinfo)];
11 if(old)
12 {
13 ext->va = old->va;
14 ext->ents = old->ents;
15 ext->tjoints = old->tjoints;
16 }
17 else
18 {
19 ext->va = NULL;
20 ext->ents = NULL;
21 ext->tjoints = -1;
22 }
23 ext->maxverts = maxverts;
24 return ext;
25 }
26
setcubeext(cube & c,cubeext * ext)27 void setcubeext(cube &c, cubeext *ext)
28 {
29 cubeext *old = c.ext;
30 if(old == ext) return;
31 c.ext = ext;
32 if(old) delete[] (uchar *)old;
33 }
34
newcubeext(cube & c,int maxverts,bool init)35 cubeext *newcubeext(cube &c, int maxverts, bool init)
36 {
37 if(c.ext && c.ext->maxverts >= maxverts) return c.ext;
38 cubeext *ext = growcubeext(c.ext, maxverts);
39 if(init)
40 {
41 if(c.ext)
42 {
43 memcpy(ext->surfaces, c.ext->surfaces, sizeof(ext->surfaces));
44 memcpy(ext->verts(), c.ext->verts(), c.ext->maxverts*sizeof(vertinfo));
45 }
46 else memset(ext->surfaces, 0, sizeof(ext->surfaces));
47 }
48 setcubeext(c, ext);
49 return ext;
50 }
51
newcubes(uint face,int mat)52 cube *newcubes(uint face, int mat)
53 {
54 cube *c = new cube[8];
55 loopi(8)
56 {
57 c->children = NULL;
58 c->ext = NULL;
59 c->visible = 0;
60 c->merged = 0;
61 setfaces(*c, face);
62 loopl(6) c->texture[l] = DEFAULT_GEOM;
63 c->material = mat;
64 c++;
65 }
66 allocnodes++;
67 return c-8;
68 }
69
familysize(const cube & c)70 int familysize(const cube &c)
71 {
72 int size = 1;
73 if(c.children) loopi(8) size += familysize(c.children[i]);
74 return size;
75 }
76
freeocta(cube * c)77 void freeocta(cube *c)
78 {
79 if(!c) return;
80 loopi(8) discardchildren(c[i]);
81 delete[] c;
82 allocnodes--;
83 }
84
freecubeext(cube & c)85 void freecubeext(cube &c)
86 {
87 if(c.ext)
88 {
89 delete[] (uchar *)c.ext;
90 c.ext = NULL;
91 }
92 }
93
discardchildren(cube & c,bool fixtex,int depth)94 void discardchildren(cube &c, bool fixtex, int depth)
95 {
96 c.material = MAT_AIR;
97 c.visible = 0;
98 c.merged = 0;
99 if(c.ext)
100 {
101 if(c.ext->va) destroyva(c.ext->va);
102 c.ext->va = NULL;
103 c.ext->tjoints = -1;
104 freeoctaentities(c);
105 freecubeext(c);
106 }
107 if(c.children)
108 {
109 uint filled = F_EMPTY;
110 loopi(8)
111 {
112 discardchildren(c.children[i], fixtex, depth+1);
113 filled |= c.children[i].faces[0];
114 }
115 if(fixtex)
116 {
117 loopi(6) c.texture[i] = getmippedtexture(c, i);
118 if(depth > 0 && filled != F_EMPTY) c.faces[0] = F_SOLID;
119 }
120 DELETEA(c.children);
121 allocnodes--;
122 }
123 }
124
getcubevector(cube & c,int d,int x,int y,int z,ivec & p)125 void getcubevector(cube &c, int d, int x, int y, int z, ivec &p)
126 {
127 ivec v(d, x, y, z);
128
129 loopi(3)
130 p[i] = edgeget(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]]);
131 }
132
setcubevector(cube & c,int d,int x,int y,int z,const ivec & p)133 void setcubevector(cube &c, int d, int x, int y, int z, const ivec &p)
134 {
135 ivec v(d, x, y, z);
136
137 loopi(3)
138 edgeset(cubeedge(c, i, v[R[i]], v[C[i]]), v[D[i]], p[i]);
139 }
140
getcubevector(cube & c,int i,ivec & p)141 static inline void getcubevector(cube &c, int i, ivec &p)
142 {
143 p.x = edgeget(cubeedge(c, 0, (i>>R[0])&1, (i>>C[0])&1), (i>>D[0])&1);
144 p.y = edgeget(cubeedge(c, 1, (i>>R[1])&1, (i>>C[1])&1), (i>>D[1])&1);
145 p.z = edgeget(cubeedge(c, 2, (i>>R[2])&1, (i>>C[2])&1), (i>>D[2])&1);
146 }
147
setcubevector(cube & c,int i,const ivec & p)148 static inline void setcubevector(cube &c, int i, const ivec &p)
149 {
150 edgeset(cubeedge(c, 0, (i>>R[0])&1, (i>>C[0])&1), (i>>D[0])&1, p.x);
151 edgeset(cubeedge(c, 1, (i>>R[1])&1, (i>>C[1])&1), (i>>D[1])&1, p.y);
152 edgeset(cubeedge(c, 2, (i>>R[2])&1, (i>>C[2])&1), (i>>D[2])&1, p.z);
153 }
154
optiface(uchar * p,cube & c)155 void optiface(uchar *p, cube &c)
156 {
157 uint f = *(uint *)p;
158 if(((f>>4)&0x0F0F0F0FU) == (f&0x0F0F0F0FU)) emptyfaces(c);
159 }
160
printcube()161 void printcube()
162 {
163 cube &c = lookupcube(lu); // assume this is cube being pointed at
164 conoutf("\fa= %p = (%d, %d, %d) @ %d", &c, lu.x, lu.y, lu.z, lusize);
165 conoutf("\fa x %.8x", c.faces[0]);
166 conoutf("\fa y %.8x", c.faces[1]);
167 conoutf("\fa z %.8x", c.faces[2]);
168 }
169
170 COMMAND(0, printcube, "");
171
isvalidcube(const cube & c)172 bool isvalidcube(const cube &c)
173 {
174 clipplanes p;
175 genclipplanes(c, ivec(0, 0, 0), 256, p);
176 loopi(8) // test that cube is convex
177 {
178 vec v;
179 calcvert(c, ivec(0, 0, 0), 256, v, i);
180 if(!pointincube(p, v))
181 return false;
182 }
183 return true;
184 }
185
validatec(cube * c,int size)186 void validatec(cube *c, int size)
187 {
188 loopi(8)
189 {
190 if(c[i].children)
191 {
192 if(size<=1)
193 {
194 solidfaces(c[i]);
195 discardchildren(c[i], true);
196 }
197 else validatec(c[i].children, size>>1);
198 }
199 else if(size > 0x1000)
200 {
201 subdividecube(c[i], true, false);
202 validatec(c[i].children, size>>1);
203 }
204 else
205 {
206 loopj(3)
207 {
208 uint f = c[i].faces[j], e0 = f&0x0F0F0F0FU, e1 = (f>>4)&0x0F0F0F0FU;
209 if(e0 == e1 || ((e1+0x07070707U)|(e1-e0))&0xF0F0F0F0U)
210 {
211 emptyfaces(c[i]);
212 break;
213 }
214 }
215 }
216 }
217 }
218
219 ivec lu;
220 int lusize;
lookupcube(const ivec & to,int tsize,ivec & ro,int & rsize)221 cube &lookupcube(const ivec &to, int tsize, ivec &ro, int &rsize)
222 {
223 int tx = clamp(to.x, 0, hdr.worldsize-1),
224 ty = clamp(to.y, 0, hdr.worldsize-1),
225 tz = clamp(to.z, 0, hdr.worldsize-1);
226 int scale = worldscale-1, csize = abs(tsize);
227 cube *c = &worldroot[octastep(tx, ty, tz, scale)];
228 if(!(csize>>scale)) do
229 {
230 if(!c->children)
231 {
232 if(tsize > 0) do
233 {
234 subdividecube(*c);
235 scale--;
236 c = &c->children[octastep(tx, ty, tz, scale)];
237 } while(!(csize>>scale));
238 break;
239 }
240 scale--;
241 c = &c->children[octastep(tx, ty, tz, scale)];
242 } while(!(csize>>scale));
243 ro = ivec(tx, ty, tz).mask(~0<<scale);
244 rsize = 1<<scale;
245 return *c;
246 }
247
lookupmaterial(const vec & v)248 int lookupmaterial(const vec &v)
249 {
250 ivec o(v);
251 if(!insideworld(o)) return MAT_AIR;
252 int scale = worldscale-1;
253 cube *c = &worldroot[octastep(o.x, o.y, o.z, scale)];
254 while(c->children)
255 {
256 scale--;
257 c = &c->children[octastep(o.x, o.y, o.z, scale)];
258 }
259 return c->material;
260 }
261
262 const cube *neighbourstack[32];
263 int neighbourdepth = -1;
264
neighbourcube(const cube & c,int orient,const ivec & co,int size,ivec & ro,int & rsize)265 const cube &neighbourcube(const cube &c, int orient, const ivec &co, int size, ivec &ro, int &rsize)
266 {
267 ivec n = co;
268 int dim = dimension(orient);
269 uint diff = n[dim];
270 if(dimcoord(orient)) n[dim] += size; else n[dim] -= size;
271 diff ^= n[dim];
272 if(diff >= uint(hdr.worldsize)) { ro = n; rsize = size; return c; }
273 int scale = worldscale;
274 const cube *nc = worldroot;
275 if(neighbourdepth >= 0)
276 {
277 scale -= neighbourdepth + 1;
278 diff >>= scale;
279 do { scale++; diff >>= 1; } while(diff);
280 nc = neighbourstack[worldscale - scale];
281 }
282 scale--;
283 nc = &nc[octastep(n.x, n.y, n.z, scale)];
284 if(!(size>>scale) && nc->children) do
285 {
286 scale--;
287 nc = &nc->children[octastep(n.x, n.y, n.z, scale)];
288 } while(!(size>>scale) && nc->children);
289 ro = n.mask(~0<<scale);
290 rsize = 1<<scale;
291 return *nc;
292 }
293
294 ////////// (re)mip //////////
295
getmippedtexture(const cube & p,int orient)296 int getmippedtexture(const cube &p, int orient)
297 {
298 cube *c = p.children;
299 int d = dimension(orient), dc = dimcoord(orient), texs[4] = { -1, -1, -1, -1 }, numtexs = 0;
300 loop(x, 2) loop(y, 2)
301 {
302 int n = octaindex(d, x, y, dc);
303 if(isempty(c[n]))
304 {
305 n = oppositeocta(d, n);
306 if(isempty(c[n]))
307 continue;
308 }
309 int tex = c[n].texture[orient];
310 if(tex > DEFAULT_SKY) loopi(numtexs) if(texs[i] == tex) return tex;
311 texs[numtexs++] = tex;
312 }
313 loopirev(numtexs) if(!i || texs[i] > DEFAULT_SKY) return texs[i];
314 return DEFAULT_GEOM;
315 }
316
forcemip(cube & c,bool fixtex)317 void forcemip(cube &c, bool fixtex)
318 {
319 cube *ch = c.children;
320 emptyfaces(c);
321
322 loopi(8) loopj(8)
323 {
324 int n = i^(j==3 ? 4 : (j==4 ? 3 : j));
325 if(!isempty(ch[n])) // breadth first search for cube near vert
326 {
327 ivec v;
328 getcubevector(ch[n], i, v);
329 // adjust vert to parent size
330 setcubevector(c, i, ivec(n, v, 8).shr(1));
331 break;
332 }
333 }
334
335 if(fixtex) loopj(6)
336 c.texture[j] = getmippedtexture(c, j);
337 }
338
midedge(const ivec & a,const ivec & b,int xd,int yd,bool & perfect)339 static int midedge(const ivec &a, const ivec &b, int xd, int yd, bool &perfect)
340 {
341 int ax = a[xd], ay = a[yd], bx = b[xd], by = b[yd];
342 if(ay==by) return ay;
343 if(ax==bx) { perfect = false; return ay; }
344 bool crossx = (ax<8 && bx>8) || (ax>8 && bx<8);
345 bool crossy = (ay<8 && by>8) || (ay>8 && by<8);
346 if(crossy && !crossx) { midedge(a,b,yd,xd,perfect); return 8; } // to test perfection
347 if(ax<=8 && bx<=8) return ax>bx ? ay : by;
348 if(ax>=8 && bx>=8) return ax<bx ? ay : by;
349 int risex = (by-ay)*(8-ax)*256;
350 int s = risex/(bx-ax);
351 int y = s/256 + ay;
352 if(((abs(s)&0xFF)!=0) || // ie: rounding error
353 (crossy && y!=8) ||
354 (y<0 || y>16)) perfect = false;
355 return crossy ? 8 : min(max(y, 0), 16);
356 }
357
crosscenter(const ivec & a,const ivec & b,int xd,int yd)358 static inline bool crosscenter(const ivec &a, const ivec &b, int xd, int yd)
359 {
360 int ax = a[xd], ay = a[yd], bx = b[xd], by = b[yd];
361 return (((ax <= 8 && bx <= 8) || (ax >= 8 && bx >= 8)) &&
362 ((ay <= 8 && by <= 8) || (ay >= 8 && by >= 8))) ||
363 (ax + bx == 16 && ay + by == 16);
364 }
365
subdividecube(cube & c,bool fullcheck,bool brighten)366 bool subdividecube(cube &c, bool fullcheck, bool brighten)
367 {
368 if(c.children) return true;
369 if(c.ext) memset(c.ext->surfaces, 0, sizeof(c.ext->surfaces));
370 if(isempty(c) || isentirelysolid(c))
371 {
372 c.children = newcubes(isempty(c) ? F_EMPTY : F_SOLID, c.material);
373 loopi(8)
374 {
375 loopl(6) c.children[i].texture[l] = c.texture[l];
376 if(brighten && !isempty(c)) brightencube(c.children[i]);
377 }
378 return true;
379 }
380 cube *ch = c.children = newcubes(F_SOLID, c.material);
381 bool perfect = true;
382 ivec v[8];
383 loopi(8)
384 {
385 getcubevector(c, i, v[i]);
386 v[i].mul(2);
387 }
388
389 loopj(6)
390 {
391 int d = dimension(j), z = dimcoord(j);
392 const ivec &v00 = v[octaindex(d, 0, 0, z)],
393 &v10 = v[octaindex(d, 1, 0, z)],
394 &v01 = v[octaindex(d, 0, 1, z)],
395 &v11 = v[octaindex(d, 1, 1, z)];
396 int e[3][3];
397 // corners
398 e[0][0] = v00[d];
399 e[0][2] = v01[d];
400 e[2][0] = v10[d];
401 e[2][2] = v11[d];
402 // edges
403 e[0][1] = midedge(v00, v01, C[d], d, perfect);
404 e[1][0] = midedge(v00, v10, R[d], d, perfect);
405 e[1][2] = midedge(v11, v01, R[d], d, perfect);
406 e[2][1] = midedge(v11, v10, C[d], d, perfect);
407 // center
408 bool p1 = perfect, p2 = perfect;
409 int c1 = midedge(v00, v11, R[d], d, p1);
410 int c2 = midedge(v01, v10, R[d], d, p2);
411 if(z ? c1 > c2 : c1 < c2)
412 {
413 e[1][1] = c1;
414 perfect = p1 && (c1 == c2 || crosscenter(v00, v11, C[d], R[d]));
415 }
416 else
417 {
418 e[1][1] = c2;
419 perfect = p2 && (c1 == c2 || crosscenter(v01, v10, C[d], R[d]));
420 }
421
422 loopi(8)
423 {
424 ch[i].texture[j] = c.texture[j];
425 int rd = (i>>R[d])&1, cd = (i>>C[d])&1, dd = (i>>D[d])&1;
426 edgeset(cubeedge(ch[i], d, 0, 0), z, clamp(e[rd][cd] - dd*8, 0, 8));
427 edgeset(cubeedge(ch[i], d, 1, 0), z, clamp(e[1+rd][cd] - dd*8, 0, 8));
428 edgeset(cubeedge(ch[i], d, 0, 1), z, clamp(e[rd][1+cd] - dd*8, 0, 8));
429 edgeset(cubeedge(ch[i], d, 1, 1), z, clamp(e[1+rd][1+cd] - dd*8, 0, 8));
430 }
431 }
432
433 validatec(ch);
434 if(fullcheck) loopi(8) if(!isvalidcube(ch[i])) // not so good...
435 {
436 emptyfaces(ch[i]);
437 perfect=false;
438 }
439 if(brighten) loopi(8) if(!isempty(ch[i])) brightencube(ch[i]);
440 return perfect;
441 }
442
crushededge(uchar e,int dc)443 bool crushededge(uchar e, int dc) { return dc ? e==0 : e==0x88; }
444
visibleorient(const cube & c,int orient)445 int visibleorient(const cube &c, int orient)
446 {
447 loopi(2)
448 {
449 int a = faceedgesidx[orient][i*2 + 0];
450 int b = faceedgesidx[orient][i*2 + 1];
451 loopj(2)
452 {
453 if(crushededge(c.edges[a],j) &&
454 crushededge(c.edges[b],j) &&
455 touchingface(c, orient)) return ((a>>2)<<1) + j;
456 }
457 }
458 return orient;
459 }
460
461 VAR(0, mipvis, 0, 0, 1);
462
463 static int remipprogress = 0, remiptotal = 0;
464
remip(cube & c,const ivec & co,int size)465 bool remip(cube &c, const ivec &co, int size)
466 {
467 cube *ch = c.children;
468 if(!ch)
469 {
470 if(size<<1 <= 0x1000) return true;
471 subdividecube(c);
472 ch = c.children;
473 }
474 else if((remipprogress++&0x7FF)==1) progress(float(remipprogress)/remiptotal, "remipping...");
475
476 bool perfect = true;
477 loopi(8)
478 {
479 ivec o(i, co, size);
480 if(!remip(ch[i], o, size>>1)) perfect = false;
481 }
482
483 solidfaces(c); // so texmip is more consistent
484 loopj(6)
485 c.texture[j] = getmippedtexture(c, j); // parents get child texs regardless
486
487 if(!perfect) return false;
488 if(size<<1 > 0x1000) return false;
489
490 ushort mat = MAT_AIR;
491 loopi(8)
492 {
493 mat = ch[i].material;
494 if((mat&MATF_CLIP) == MAT_NOCLIP || mat&MAT_ALPHA)
495 {
496 if(i > 0) return false;
497 while(++i < 8) if(ch[i].material != mat) return false;
498 break;
499 }
500 else if(!isentirelysolid(ch[i]))
501 {
502 while(++i < 8)
503 {
504 int omat = ch[i].material;
505 if(isentirelysolid(ch[i]) ? (omat&MATF_CLIP) == MAT_NOCLIP || omat&MAT_ALPHA : mat != omat) return false;
506 }
507 break;
508 }
509 }
510
511 cube n = c;
512 n.ext = NULL;
513 forcemip(n);
514 n.children = NULL;
515 if(!subdividecube(n, false, false))
516 { freeocta(n.children); return false; }
517
518 cube *nh = n.children;
519 uchar vis[6] = {0, 0, 0, 0, 0, 0};
520 loopi(8)
521 {
522 if(ch[i].faces[0] != nh[i].faces[0] ||
523 ch[i].faces[1] != nh[i].faces[1] ||
524 ch[i].faces[2] != nh[i].faces[2])
525 { freeocta(nh); return false; }
526
527 if(isempty(ch[i]) && isempty(nh[i])) continue;
528
529 ivec o(i, co, size);
530 loop(orient, 6)
531 if(visibleface(ch[i], orient, o, size, MAT_AIR, (mat&MAT_ALPHA)^MAT_ALPHA, MAT_ALPHA))
532 {
533 if(ch[i].texture[orient] != n.texture[orient]) { freeocta(nh); return false; }
534 vis[orient] |= 1<<i;
535 }
536 }
537 if(mipvis) loop(orient, 6)
538 {
539 int mask = 0;
540 loop(x, 2) loop(y, 2) mask |= 1<<octaindex(dimension(orient), x, y, dimcoord(orient));
541 if(vis[orient]&mask && (vis[orient]&mask)!=mask) { freeocta(nh); return false; }
542 }
543
544 freeocta(nh);
545 discardchildren(c);
546 loopi(3) c.faces[i] = n.faces[i];
547 c.material = mat;
548 loopi(6) if(vis[i]) c.visible |= 1<<i;
549 if(c.visible) c.visible |= 0x40;
550 brightencube(c);
551 return true;
552 }
553
mpremip(bool local)554 void mpremip(bool local)
555 {
556 if(local) client::edittrigger(sel, EDIT_REMIP);
557 remipprogress = 1;
558 remiptotal = allocnodes;
559 loopi(8)
560 {
561 ivec o(i, ivec(0, 0, 0), hdr.worldsize>>1);
562 remip(worldroot[i], o, hdr.worldsize>>2);
563 }
564 calcmerges();
565 if(!local) allchanged();
566 }
567
remip_()568 void remip_()
569 {
570 mpremip(true);
571 allchanged();
572 }
573
574 COMMANDN(0, remip, remip_, "");
575
edgeval(cube & c,const ivec & p,int dim,int coord)576 static inline int edgeval(cube &c, const ivec &p, int dim, int coord)
577 {
578 return edgeget(cubeedge(c, dim, p[R[dim]]>>3, p[C[dim]]>>3), coord);
579 }
580
genvertp(cube & c,ivec & p1,ivec & p2,ivec & p3,plane & pl,bool solid=false)581 static void genvertp(cube &c, ivec &p1, ivec &p2, ivec &p3, plane &pl, bool solid = false)
582 {
583 int dim = 0;
584 if(p1.y==p2.y && p2.y==p3.y) dim = 1;
585 else if(p1.z==p2.z && p2.z==p3.z) dim = 2;
586
587 int coord = p1[dim];
588 ivec v1(p1), v2(p2), v3(p3);
589 v1[dim] = solid ? coord*8 : edgeval(c, p1, dim, coord);
590 v2[dim] = solid ? coord*8 : edgeval(c, p2, dim, coord);
591 v3[dim] = solid ? coord*8 : edgeval(c, p3, dim, coord);
592
593 pl.toplane(vec(v1), vec(v2), vec(v3));
594 }
595
threeplaneintersect(plane & pl1,plane & pl2,plane & pl3,vec & dest)596 static bool threeplaneintersect(plane &pl1, plane &pl2, plane &pl3, vec &dest)
597 {
598 vec &t1 = dest, t2, t3, t4;
599 t1.cross(pl1, pl2); t4 = t1; t1.mul(pl3.offset);
600 t2.cross(pl3, pl1); t2.mul(pl2.offset);
601 t3.cross(pl2, pl3); t3.mul(pl1.offset);
602 t1.add(t2);
603 t1.add(t3);
604 t1.mul(-1);
605 float d = t4.dot(pl3);
606 if(d==0) return false;
607 t1.div(d);
608 return true;
609 }
610
genedgespanvert(ivec & p,cube & c,vec & v)611 static void genedgespanvert(ivec &p, cube &c, vec &v)
612 {
613 ivec p1(8-p.x, p.y, p.z);
614 ivec p2(p.x, 8-p.y, p.z);
615 ivec p3(p.x, p.y, 8-p.z);
616
617 plane plane1, plane2, plane3;
618 genvertp(c, p, p1, p2, plane1);
619 genvertp(c, p, p2, p3, plane2);
620 genvertp(c, p, p3, p1, plane3);
621 if(plane1==plane2) genvertp(c, p, p1, p2, plane1, true);
622 if(plane1==plane3) genvertp(c, p, p1, p2, plane1, true);
623 if(plane2==plane3) genvertp(c, p, p2, p3, plane2, true);
624
625 ASSERT(threeplaneintersect(plane1, plane2, plane3, v));
626 //ASSERT(v.x>=0 && v.x<=8);
627 //ASSERT(v.y>=0 && v.y<=8);
628 //ASSERT(v.z>=0 && v.z<=8);
629 v.x = max(0.0f, min(8.0f, v.x));
630 v.y = max(0.0f, min(8.0f, v.y));
631 v.z = max(0.0f, min(8.0f, v.z));
632 }
633
edgespan2vectorcube(cube & c)634 void edgespan2vectorcube(cube &c)
635 {
636 if(isentirelysolid(c) || isempty(c)) return;
637 cube o = c;
638 loop(x, 2) loop(y, 2) loop(z, 2)
639 {
640 ivec p(8*x, 8*y, 8*z);
641 vec v;
642 genedgespanvert(p, o, v);
643
644 edgeset(cubeedge(c, 0, y, z), x, int(v.x+0.49f));
645 edgeset(cubeedge(c, 1, z, x), y, int(v.y+0.49f));
646 edgeset(cubeedge(c, 2, x, y), z, int(v.z+0.49f));
647 }
648 }
649
650 const ivec cubecoords[8] = // verts of bounding cube
651 {
652 #define GENCUBEVERT(n, x, y, z) ivec(x, y, z),
653 GENCUBEVERTS(0, 8, 0, 8, 0, 8)
654 #undef GENCUBEVERT
655 };
656
657 template<class T>
gencubevert(const cube & c,int i,T & v)658 static inline void gencubevert(const cube &c, int i, T &v)
659 {
660 switch(i)
661 {
662 default:
663 #define GENCUBEVERT(n, x, y, z) \
664 case n: \
665 v = T(edgeget(cubeedge(c, 0, y, z), x), \
666 edgeget(cubeedge(c, 1, z, x), y), \
667 edgeget(cubeedge(c, 2, x, y), z)); \
668 break;
669 GENCUBEVERTS(0, 1, 0, 1, 0, 1)
670 #undef GENCUBEVERT
671 }
672 }
673
genfaceverts(const cube & c,int orient,ivec v[4])674 void genfaceverts(const cube &c, int orient, ivec v[4])
675 {
676 switch(orient)
677 {
678 default:
679 #define GENFACEORIENT(o, v0, v1, v2, v3) \
680 case o: v0 v1 v2 v3 break;
681 #define GENFACEVERT(o, n, x,y,z, xv,yv,zv) \
682 v[n] = ivec(edgeget(cubeedge(c, 0, y, z), x), \
683 edgeget(cubeedge(c, 1, z, x), y), \
684 edgeget(cubeedge(c, 2, x, y), z));
685 GENFACEVERTS(0, 1, 0, 1, 0, 1, , , , , , )
686 #undef GENFACEORIENT
687 #undef GENFACEVERT
688 }
689 }
690
691 const ivec facecoords[6][4] =
692 {
693 #define GENFACEORIENT(o, v0, v1, v2, v3) \
694 { v0, v1, v2, v3 },
695 #define GENFACEVERT(o, n, x,y,z, xv,yv,zv) \
696 ivec(x,y,z)
697 GENFACEVERTS(0, 8, 0, 8, 0, 8, , , , , , )
698 #undef GENFACEORIENT
699 #undef GENFACEVERT
700 };
701
702 const uchar fv[6][4] = // indexes for cubecoords, per each vert of a face orientation
703 {
704 { 2, 1, 6, 5 },
705 { 3, 4, 7, 0 },
706 { 4, 5, 6, 7 },
707 { 1, 2, 3, 0 },
708 { 6, 1, 0, 7 },
709 { 5, 4, 3, 2 },
710 };
711
712 const uchar fvmasks[64] = // mask of verts used given a mask of visible face orientations
713 {
714 0x00, 0x66, 0x99, 0xFF, 0xF0, 0xF6, 0xF9, 0xFF,
715 0x0F, 0x6F, 0x9F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
716 0xC3, 0xE7, 0xDB, 0xFF, 0xF3, 0xF7, 0xFB, 0xFF,
717 0xCF, 0xEF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
718 0x3C, 0x7E, 0xBD, 0xFF, 0xFC, 0xFE, 0xFD, 0xFF,
719 0x3F, 0x7F, 0xBF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
720 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
721 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
722 };
723
724 const uchar faceedgesidx[6][4] = // ordered edges surrounding each orient
725 {//0..1 = row edges, 2..3 = column edges
726 { 4, 5, 8, 10 },
727 { 6, 7, 9, 11 },
728 { 8, 9, 0, 2 },
729 { 10, 11, 1, 3 },
730 { 0, 1, 4, 6 },
731 { 2, 3, 5, 7 },
732 };
733
flataxisface(const cube & c,int orient)734 bool flataxisface(const cube &c, int orient)
735 {
736 uint face = c.faces[dimension(orient)];
737 if(dimcoord(orient)) face >>= 4;
738 return (face&0x0F0F0F0F) == 0x01010101*(face&0x0F);
739 }
740
collideface(const cube & c,int orient)741 bool collideface(const cube &c, int orient)
742 {
743 if(flataxisface(c, orient))
744 {
745 uchar r1 = c.edges[faceedgesidx[orient][0]], r2 = c.edges[faceedgesidx[orient][1]];
746 if(uchar((r1>>4)|(r2&0xF0)) == uchar((r1&0x0F)|(r2<<4))) return false;
747 uchar c1 = c.edges[faceedgesidx[orient][2]], c2 = c.edges[faceedgesidx[orient][3]];
748 if(uchar((c1>>4)|(c2&0xF0)) == uchar((c1&0x0F)|(c2<<4))) return false;
749 }
750 return true;
751 }
752
touchingface(const cube & c,int orient)753 bool touchingface(const cube &c, int orient)
754 {
755 uint face = c.faces[dimension(orient)];
756 return dimcoord(orient) ? (face&0xF0F0F0F0)==0x80808080 : (face&0x0F0F0F0F)==0;
757 }
758
notouchingface(const cube & c,int orient)759 bool notouchingface(const cube &c, int orient)
760 {
761 uint face = c.faces[dimension(orient)];
762 return dimcoord(orient) ? (face&0x80808080)==0 : ((0x88888888-face)&0x08080808) == 0;
763 }
764
faceconvexity(const ivec v[4])765 int faceconvexity(const ivec v[4])
766 {
767 ivec n;
768 n.cross(ivec(v[1]).sub(v[0]), ivec(v[2]).sub(v[0]));
769 return ivec(v[0]).sub(v[3]).dot(n);
770 // 1 if convex, -1 if concave, 0 if flat
771 }
772
faceconvexity(const vertinfo * verts,int numverts,int size)773 int faceconvexity(const vertinfo *verts, int numverts, int size)
774 {
775 if(numverts < 4) return 0;
776 ivec v0 = verts[0].getxyz(),
777 e1 = verts[1].getxyz().sub(v0),
778 e2 = verts[2].getxyz().sub(v0),
779 n;
780 if(size >= (8<<5))
781 {
782 if(size >= (8<<10)) n.cross(e1.shr(10), e2.shr(10));
783 else n.cross(e1, e2).shr(10);
784 }
785 else n.cross(e1, e2);
786 return verts[3].getxyz().sub(v0).dot(n);
787 }
788
faceconvexity(const ivec v[4],int & vis)789 int faceconvexity(const ivec v[4], int &vis)
790 {
791 ivec e1, e2, e3, n;
792 n.cross((e1 = v[1]).sub(v[0]), (e2 = v[2]).sub(v[0]));
793 int convex = (e3 = v[0]).sub(v[3]).dot(n);
794 if(!convex)
795 {
796 if(ivec().cross(e3, e2).iszero()) { if(!n.iszero()) vis = 1; }
797 else if(n.iszero()) { vis = 2; }
798 return 0;
799 }
800 return convex;
801 }
802
faceconvexity(const cube & c,int orient)803 int faceconvexity(const cube &c, int orient)
804 {
805 if(flataxisface(c, orient)) return 0;
806 ivec v[4];
807 genfaceverts(c, orient, v);
808 return faceconvexity(v);
809 }
810
faceorder(const cube & c,int orient)811 int faceorder(const cube &c, int orient) // gets above 'fv' so that each face is convex
812 {
813 return faceconvexity(c, orient)<0 ? 1 : 0;
814 }
815
faceedges(const cube & c,int orient,uchar edges[4])816 static inline void faceedges(const cube &c, int orient, uchar edges[4])
817 {
818 loopk(4) edges[k] = c.edges[faceedgesidx[orient][k]];
819 }
820
faceedges(const cube & c,int orient)821 uint faceedges(const cube &c, int orient)
822 {
823 union { uchar edges[4]; uint face; } u;
824 faceedges(c, orient, u.edges);
825 return u.face;
826 }
827
genfacevecs(const cube & cu,int orient,const ivec & pos,int size,bool solid,ivec2 * fvecs,const ivec * v=NULL)828 static inline int genfacevecs(const cube &cu, int orient, const ivec &pos, int size, bool solid, ivec2 *fvecs, const ivec *v = NULL)
829 {
830 int i = 0;
831 if(solid)
832 {
833 switch(orient)
834 {
835 #define GENFACEORIENT(orient, v0, v1, v2, v3) \
836 case orient: \
837 { \
838 if(dimcoord(orient)) { v0 v1 v2 v3 } else { v3 v2 v1 v0 } \
839 break; \
840 }
841 #define GENFACEVERT(orient, vert, xv,yv,zv, x,y,z) \
842 { ivec2 &f = fvecs[i]; x ((xv)<<3); y ((yv)<<3); z ((zv)<<3); i++; }
843 GENFACEVERTS(pos.x, pos.x+size, pos.y, pos.y+size, pos.z, pos.z+size, f.x = , f.x = , f.y = , f.y = , (void), (void))
844 #undef GENFACEVERT
845 }
846 return 4;
847 }
848 ivec buf[4];
849 if(!v) { genfaceverts(cu, orient, buf); v = buf; }
850 ivec2 prev(INT_MAX, INT_MAX);
851 switch(orient)
852 {
853 #define GENFACEVERT(orient, vert, sx,sy,sz, dx,dy,dz) \
854 { \
855 const ivec &e = v[vert]; \
856 ivec ef; \
857 ef.dx = e.sx; ef.dy = e.sy; ef.dz = e.sz; \
858 if(ef.z == dimcoord(orient)*8) \
859 { \
860 ivec2 &f = fvecs[i]; \
861 ivec pf; \
862 pf.dx = pos.sx; pf.dy = pos.sy; pf.dz = pos.sz; \
863 f = ivec2(ef.x*size + (pf.x<<3), ef.y*size + (pf.y<<3)); \
864 if(f != prev) { prev = f; i++; } \
865 } \
866 }
867 GENFACEVERTS(x, x, y, y, z, z, x, x, y, y, z, z)
868 #undef GENFACEORIENT
869 #undef GENFACEVERT
870 }
871 if(fvecs[0] == prev) i--;
872 return i;
873 }
874
clipfacevecy(const ivec2 & o,const ivec2 & dir,int cx,int cy,int size,ivec2 & r)875 static inline int clipfacevecy(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 &r)
876 {
877 if(dir.x >= 0)
878 {
879 if(cx <= o.x || cx >= o.x+dir.x) return 0;
880 }
881 else if(cx <= o.x+dir.x || cx >= o.x) return 0;
882
883 int t = (o.y-cy) + (cx-o.x)*dir.y/dir.x;
884 if(t <= 0 || t >= size) return 0;
885
886 r.x = cx;
887 r.y = cy + t;
888 return 1;
889 }
890
clipfacevecx(const ivec2 & o,const ivec2 & dir,int cx,int cy,int size,ivec2 & r)891 static inline int clipfacevecx(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 &r)
892 {
893 if(dir.y >= 0)
894 {
895 if(cy <= o.y || cy >= o.y+dir.y) return 0;
896 }
897 else if(cy <= o.y+dir.y || cy >= o.y) return 0;
898
899 int t = (o.x-cx) + (cy-o.y)*dir.x/dir.y;
900 if(t <= 0 || t >= size) return 0;
901
902 r.x = cx + t;
903 r.y = cy;
904 return 1;
905 }
906
clipfacevec(const ivec2 & o,const ivec2 & dir,int cx,int cy,int size,ivec2 * rvecs)907 static inline int clipfacevec(const ivec2 &o, const ivec2 &dir, int cx, int cy, int size, ivec2 *rvecs)
908 {
909 int r = 0;
910
911 if(o.x >= cx && o.x <= cx+size &&
912 o.y >= cy && o.y <= cy+size &&
913 ((o.x != cx && o.x != cx+size) || (o.y != cy && o.y != cy+size)))
914 {
915 rvecs[0].x = o.x;
916 rvecs[0].y = o.y;
917 r++;
918 }
919
920 r += clipfacevecx(o, dir, cx, cy, size, rvecs[r]);
921 r += clipfacevecx(o, dir, cx, cy+size, size, rvecs[r]);
922 r += clipfacevecy(o, dir, cx, cy, size, rvecs[r]);
923 r += clipfacevecy(o, dir, cx+size, cy, size, rvecs[r]);
924
925 ASSERT(r <= 2);
926 return r;
927 }
928
insideface(const ivec2 * p,int nump,const ivec2 * o,int numo)929 static inline bool insideface(const ivec2 *p, int nump, const ivec2 *o, int numo)
930 {
931 int bounds = 0;
932 ivec2 prev = o[numo-1];
933 loopi(numo)
934 {
935 const ivec2 &cur = o[i];
936 ivec2 dir(cur.x-prev.x, cur.y-prev.y);
937 int offset = dir.x*prev.y - dir.y*prev.x;
938 loopj(nump) if(dir.x*p[j].y - dir.y*p[j].x > offset) return false;
939 bounds++;
940 prev = cur;
941 }
942 return bounds>=3;
943 }
944
clipfacevecs(const ivec2 * o,int numo,int cx,int cy,int size,ivec2 * rvecs)945 static inline int clipfacevecs(const ivec2 *o, int numo, int cx, int cy, int size, ivec2 *rvecs)
946 {
947 cx <<= 3;
948 cy <<= 3;
949 size <<= 3;
950
951 int r = 0;
952 ivec2 prev = o[numo-1];
953 loopi(numo)
954 {
955 const ivec2 &cur = o[i];
956 r += clipfacevec(prev, ivec2(cur.x-prev.x, cur.y-prev.y), cx, cy, size, &rvecs[r]);
957 prev = cur;
958 }
959 ivec2 corner[4] = {ivec2(cx, cy), ivec2(cx+size, cy), ivec2(cx+size, cy+size), ivec2(cx, cy+size)};
960 loopi(4) if(insideface(&corner[i], 1, o, numo)) rvecs[r++] = corner[i];
961 ASSERT(r <= 8);
962 return r;
963 }
964
collapsedface(const cube & c,int orient)965 bool collapsedface(const cube &c, int orient)
966 {
967 int e0 = c.edges[faceedgesidx[orient][0]], e1 = c.edges[faceedgesidx[orient][1]],
968 e2 = c.edges[faceedgesidx[orient][2]], e3 = c.edges[faceedgesidx[orient][3]],
969 face = dimension(orient)*4,
970 f0 = c.edges[face+0], f1 = c.edges[face+1],
971 f2 = c.edges[face+2], f3 = c.edges[face+3];
972 if(dimcoord(orient)) { f0 >>= 4; f1 >>= 4; f2 >>= 4; f3 >>= 4; }
973 else { f0 &= 0xF; f1 &= 0xF; f2 &= 0xF; f3 &= 0xF; }
974 ivec v0(e0&0xF, e2&0xF, f0),
975 v1(e0>>4, e3&0xF, f1),
976 v2(e1>>4, e3>>4, f3),
977 v3(e1&0xF, e2>>4, f2);
978 return ivec().cross(v1.sub(v0), v2.sub(v0)).iszero() &&
979 ivec().cross(v2, v3.sub(v0)).iszero();
980 }
981
occludesface(const cube & c,int orient,const ivec & o,int size,const ivec & vo,int vsize,ushort vmat,ushort nmat,ushort matmask,const ivec2 * vf,int numv)982 static inline bool occludesface(const cube &c, int orient, const ivec &o, int size, const ivec &vo, int vsize, ushort vmat, ushort nmat, ushort matmask, const ivec2 *vf, int numv)
983 {
984 int dim = dimension(orient);
985 if(!c.children)
986 {
987 if(nmat != MAT_AIR && (c.material&matmask) == nmat)
988 {
989 ivec2 nf[8];
990 return clipfacevecs(vf, numv, o[C[dim]], o[R[dim]], size, nf) < 3;
991 }
992 if(isentirelysolid(c)) return true;
993 if(vmat != MAT_AIR && ((c.material&matmask) == vmat || (isliquid(vmat) && isclipped(c.material&MATF_VOLUME)))) return true;
994 if(touchingface(c, orient) && faceedges(c, orient) == F_SOLID) return true;
995 ivec2 cf[8];
996 int numc = clipfacevecs(vf, numv, o[C[dim]], o[R[dim]], size, cf);
997 if(numc < 3) return true;
998 if(isempty(c) || notouchingface(c, orient)) return false;
999 ivec2 of[4];
1000 int numo = genfacevecs(c, orient, o, size, false, of);
1001 return numo >= 3 && insideface(cf, numc, of, numo);
1002 }
1003
1004 size >>= 1;
1005 int coord = dimcoord(orient);
1006 loopi(8) if(octacoord(dim, i) == coord)
1007 {
1008 if(!occludesface(c.children[i], orient, ivec(i, o, size), size, vo, vsize, vmat, nmat, matmask, vf, numv)) return false;
1009 }
1010
1011 return true;
1012 }
1013
visibleface(const cube & c,int orient,const ivec & co,int size,ushort mat,ushort nmat,ushort matmask)1014 bool visibleface(const cube &c, int orient, const ivec &co, int size, ushort mat, ushort nmat, ushort matmask)
1015 {
1016 if(mat != MAT_AIR)
1017 {
1018 if(faceedges(c, orient)==F_SOLID && touchingface(c, orient)) return false;
1019 }
1020 else
1021 {
1022 if(collapsedface(c, orient)) return false;
1023 if(!touchingface(c, orient)) return true;
1024 }
1025
1026 ivec no;
1027 int nsize;
1028 const cube &o = neighbourcube(c, orient, co, size, no, nsize);
1029 if(&o==&c) return false;
1030
1031 int opp = opposite(orient);
1032 if(nsize > size || (nsize == size && !o.children))
1033 {
1034 if(nmat != MAT_AIR && (o.material&matmask) == nmat) return true;
1035 if(isentirelysolid(o)) return false;
1036 if(mat != MAT_AIR && ((o.material&matmask) == mat || (isliquid(mat) && (o.material&MATF_VOLUME) == MAT_GLASS))) return false;
1037 if(isempty(o) || notouchingface(o, opp)) return true;
1038 if(touchingface(o, opp) && faceedges(o, opp) == F_SOLID) return false;
1039
1040 ivec vo = ivec(co).mask(0xFFF);
1041 no.mask(0xFFF);
1042 ivec2 cf[4], of[4];
1043 int numc = genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf),
1044 numo = genfacevecs(o, opp, no, nsize, false, of);
1045 return numo < 3 || !insideface(cf, numc, of, numo);
1046 }
1047
1048 ivec vo = ivec(co).mask(0xFFF);
1049 no.mask(0xFFF);
1050 ivec2 cf[4];
1051 int numc = genfacevecs(c, orient, vo, size, mat != MAT_AIR, cf);
1052 return !occludesface(o, opp, no, nsize, vo, size, mat, nmat, matmask, cf, numc);
1053 }
1054
classifyface(const cube & c,int orient,const ivec & co,int size)1055 int classifyface(const cube &c, int orient, const ivec &co, int size)
1056 {
1057 if(collapsedface(c, orient)) return 0;
1058 int vismask = (c.material&MATF_CLIP) == MAT_NOCLIP ? 1 : 3;
1059 if(!touchingface(c, orient)) return vismask;
1060
1061 ivec no;
1062 int nsize;
1063 const cube &o = neighbourcube(c, orient, co, size, no, nsize);
1064 if(&o==&c) return 0;
1065
1066 int vis = 0, opp = opposite(orient);
1067 if(nsize > size || (nsize == size && !o.children))
1068 {
1069 if((~c.material & o.material) & MAT_ALPHA) vis |= 1;
1070 if((o.material&MATF_CLIP) == MAT_NOCLIP) vis |= vismask&2;
1071 if(vis == vismask || isentirelysolid(o)) return vis;
1072 if(isempty(o) || notouchingface(o, opp)) return vismask;
1073 if(touchingface(o, opp) && faceedges(o, opp) == F_SOLID) return vis;
1074
1075 ivec vo = ivec(co).mask(0xFFF);
1076 no.mask(0xFFF);
1077 ivec2 cf[4], of[4];
1078 int numc = genfacevecs(c, orient, vo, size, false, cf),
1079 numo = genfacevecs(o, opp, no, nsize, false, of);
1080 if(numo < 3 || !insideface(cf, numc, of, numo)) return vismask;
1081 return vis;
1082 }
1083
1084 ivec vo = ivec(co).mask(0xFFF);
1085 no.mask(0xFFF);
1086 ivec2 cf[4];
1087 int numc = genfacevecs(c, orient, vo, size, false, cf);
1088 if(!occludesface(o, opp, no, nsize, vo, size, MAT_AIR, (c.material&MAT_ALPHA)^MAT_ALPHA, MAT_ALPHA, cf, numc)) vis |= 1;
1089 if(vismask&2 && !occludesface(o, opp, no, nsize, vo, size, MAT_AIR, MAT_NOCLIP, MATF_CLIP, cf, numc)) vis |= 2;
1090 return vis;
1091 }
1092
1093 // more expensive version that checks both triangles of a face independently
visibletris(const cube & c,int orient,const ivec & co,int size,ushort nmat,ushort matmask)1094 int visibletris(const cube &c, int orient, const ivec &co, int size, ushort nmat, ushort matmask)
1095 {
1096 int vis = 3, touching = 0xF;
1097 ivec v[4], e1, e2, e3, n;
1098 genfaceverts(c, orient, v);
1099 n.cross((e1 = v[1]).sub(v[0]), (e2 = v[2]).sub(v[0]));
1100 int convex = (e3 = v[0]).sub(v[3]).dot(n);
1101 if(!convex)
1102 {
1103 if(ivec().cross(e3, e2).iszero() || v[1] == v[3]) { if(n.iszero()) return 0; vis = 1; touching = 0xF&~(1<<3); }
1104 else if(n.iszero()) { vis = 2; touching = 0xF&~(1<<1); }
1105 }
1106
1107 int dim = dimension(orient), coord = dimcoord(orient);
1108 if(v[0][dim] != coord*8) touching &= ~(1<<0);
1109 if(v[1][dim] != coord*8) touching &= ~(1<<1);
1110 if(v[2][dim] != coord*8) touching &= ~(1<<2);
1111 if(v[3][dim] != coord*8) touching &= ~(1<<3);
1112 static const int notouchmasks[2][16] = // mask of triangles not touching
1113 { // order 0: flat or convex
1114 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1115 { 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 1, 3, 0 },
1116 // order 1: concave
1117 { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 3, 2, 0 },
1118 };
1119 int order = convex < 0 ? 1 : 0, notouch = notouchmasks[order][touching];
1120 if((vis¬ouch)==vis) return vis;
1121
1122 ivec no;
1123 int nsize;
1124 const cube &o = neighbourcube(c, orient, co, size, no, nsize);
1125 if(&o==&c) return 0;
1126
1127 if((c.material&matmask) == nmat) nmat = MAT_AIR;
1128
1129 ivec vo = ivec(co).mask(0xFFF);
1130 no.mask(0xFFF);
1131 ivec2 cf[4], of[4];
1132 int opp = opposite(orient), numo = 0, numc;
1133 if(nsize > size || (nsize == size && !o.children))
1134 {
1135 if(isempty(o) || notouchingface(o, opp)) return vis;
1136 if(nmat != MAT_AIR && (o.material&matmask) == nmat) return vis;
1137 if(isentirelysolid(o) || (touchingface(o, opp) && faceedges(o, opp) == F_SOLID)) return vis¬ouch;
1138
1139 numc = genfacevecs(c, orient, vo, size, false, cf, v);
1140 numo = genfacevecs(o, opp, no, nsize, false, of);
1141 if(numo < 3) return vis;
1142 if(insideface(cf, numc, of, numo)) return vis¬ouch;
1143 }
1144 else
1145 {
1146 numc = genfacevecs(c, orient, vo, size, false, cf, v);
1147 if(occludesface(o, opp, no, nsize, vo, size, MAT_AIR, nmat, matmask, cf, numc)) return vis¬ouch;
1148 }
1149 if(vis != 3 || notouch) return vis;
1150
1151 static const int triverts[2][2][2][3] =
1152 { // order
1153 { // coord
1154 { { 1, 2, 3 }, { 0, 1, 3 } }, // verts
1155 { { 0, 1, 2 }, { 0, 2, 3 } }
1156 },
1157 { // coord
1158 { { 0, 1, 2 }, { 3, 0, 2 } }, // verts
1159 { { 1, 2, 3 }, { 1, 3, 0 } }
1160 }
1161 };
1162
1163 do
1164 {
1165 loopi(2)
1166 {
1167 const int *verts = triverts[order][coord][i];
1168 ivec2 tf[3] = { cf[verts[0]], cf[verts[1]], cf[verts[2]] };
1169 if(numo > 0) { if(!insideface(tf, 3, of, numo)) continue; }
1170 else if(!occludesface(o, opp, no, nsize, vo, size, MAT_AIR, nmat, matmask, tf, 3)) continue;
1171 return vis & ~(1<<i);
1172 }
1173 vis |= 4;
1174 } while(++order <= 1);
1175
1176 return 3;
1177 }
1178
calcvert(const cube & c,const ivec & co,int size,ivec & v,int i,bool solid)1179 void calcvert(const cube &c, const ivec &co, int size, ivec &v, int i, bool solid)
1180 {
1181 if(solid) v = cubecoords[i]; else gencubevert(c, i, v);
1182 // avoid overflow
1183 if(size>=8) v.mul(size/8);
1184 else v.div(8/size);
1185 v.add(ivec(co).shl(3));
1186 }
1187
calcvert(const cube & c,const ivec & co,int size,vec & v,int i,bool solid)1188 void calcvert(const cube &c, const ivec &co, int size, vec &v, int i, bool solid)
1189 {
1190 if(solid) v = vec(cubecoords[i]); else gencubevert(c, i, v);
1191 v.mul(size/8.0f).add(vec(co));
1192 }
1193
genclipplane(const cube & c,int orient,vec * v,plane * clip)1194 int genclipplane(const cube &c, int orient, vec *v, plane *clip)
1195 {
1196 int planes = 0, convex = faceconvexity(c, orient), order = convex < 0 ? 1 : 0;
1197 const vec &v0 = v[fv[orient][order]], &v1 = v[fv[orient][order+1]], &v2 = v[fv[orient][order+2]], &v3 = v[fv[orient][(order+3)&3]];
1198 if(v0==v2) return 0;
1199 if(v0!=v1 && v1!=v2) clip[planes++].toplane(v0, v1, v2);
1200 if(v0!=v3 && v2!=v3 && (!planes || convex)) clip[planes++].toplane(v0, v2, v3);
1201 return planes;
1202 }
1203
genclipplanes(const cube & c,const ivec & co,int size,clipplanes & p,bool collide)1204 void genclipplanes(const cube &c, const ivec &co, int size, clipplanes &p, bool collide)
1205 {
1206 // generate tight bounding box
1207 calcvert(c, co, size, p.v[0], 0);
1208 vec mx = p.v[0], mn = p.v[0];
1209 for(int i = 1; i < 8; i++)
1210 {
1211 calcvert(c, co, size, p.v[i], i);
1212 mx.max(p.v[i]);
1213 mn.min(p.v[i]);
1214 }
1215
1216 p.r = mx.sub(mn).mul(0.5f);
1217 p.o = mn.add(p.r);
1218
1219 p.size = 0;
1220 p.visible = 0;
1221 if(collide || (c.visible&0xC0) == 0x40)
1222 {
1223 loopi(6) if(c.visible&(1<<i))
1224 {
1225 int vis;
1226 if(flataxisface(c, i)) p.visible |= 1<<i;
1227 else if((vis = visibletris(c, i, co, size, MAT_NOCLIP, MATF_CLIP)))
1228 {
1229 int convex = faceconvexity(c, i), order = vis&4 || convex < 0 ? 1 : 0;
1230 const vec &v0 = p.v[fv[i][order]], &v1 = p.v[fv[i][order+1]], &v2 = p.v[fv[i][order+2]], &v3 = p.v[fv[i][(order+3)&3]];
1231 if(vis&1) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v1, v2); }
1232 if(vis&2 && (!(vis&1) || convex)) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v2, v3); }
1233 }
1234 }
1235 }
1236 else if(c.visible&0x80)
1237 {
1238 int vis;
1239 loopi(6) if((vis = visibletris(c, i, co, size)))
1240 {
1241 if(flataxisface(c, i)) p.visible |= 1<<i;
1242 else
1243 {
1244 int convex = faceconvexity(c, i), order = vis&4 || convex < 0 ? 1 : 0;
1245 const vec &v0 = p.v[fv[i][order]], &v1 = p.v[fv[i][order+1]], &v2 = p.v[fv[i][order+2]], &v3 = p.v[fv[i][(order+3)&3]];
1246 if(vis&1) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v1, v2); }
1247 if(vis&2 && (!(vis&1) || convex)) { p.side[p.size] = i; p.p[p.size++].toplane(v0, v2, v3); }
1248 }
1249 }
1250 }
1251 }
1252
mergefacecmp(const facebounds & x,const facebounds & y)1253 static inline bool mergefacecmp(const facebounds &x, const facebounds &y)
1254 {
1255 if(x.v2 < y.v2) return true;
1256 if(x.v2 > y.v2) return false;
1257 if(x.u1 < y.u1) return true;
1258 if(x.u1 > y.u1) return false;
1259 return false;
1260 }
1261
mergefacev(int orient,facebounds * m,int sz,facebounds & n)1262 static int mergefacev(int orient, facebounds *m, int sz, facebounds &n)
1263 {
1264 for(int i = sz-1; i >= 0; --i)
1265 {
1266 if(m[i].v2 < n.v1) break;
1267 if(m[i].v2 == n.v1 && m[i].u1 == n.u1 && m[i].u2 == n.u2)
1268 {
1269 n.v1 = m[i].v1;
1270 memmove(&m[i], &m[i+1], (sz - (i+1)) * sizeof(facebounds));
1271 return 1;
1272 }
1273 }
1274 return 0;
1275 }
1276
mergefaceu(int orient,facebounds & m,facebounds & n)1277 static int mergefaceu(int orient, facebounds &m, facebounds &n)
1278 {
1279 if(m.v1 == n.v1 && m.v2 == n.v2 && m.u2 == n.u1)
1280 {
1281 n.u1 = m.u1;
1282 return 1;
1283 }
1284 return 0;
1285 }
1286
mergeface(int orient,facebounds * m,int sz,facebounds & n)1287 static int mergeface(int orient, facebounds *m, int sz, facebounds &n)
1288 {
1289 for(bool merged = false; sz; merged = true)
1290 {
1291 int vmerged = mergefacev(orient, m, sz, n);
1292 sz -= vmerged;
1293 if(!vmerged && merged) break;
1294 if(!sz) break;
1295 int umerged = mergefaceu(orient, m[sz-1], n);
1296 sz -= umerged;
1297 if(!umerged) break;
1298 }
1299 m[sz++] = n;
1300 return sz;
1301 }
1302
mergefaces(int orient,facebounds * m,int sz)1303 int mergefaces(int orient, facebounds *m, int sz)
1304 {
1305 quicksort(m, sz, mergefacecmp);
1306
1307 int nsz = 0;
1308 loopi(sz) nsz = mergeface(orient, m, nsz, m[i]);
1309 return nsz;
1310 }
1311
1312 struct cfkey
1313 {
1314 uchar orient;
1315 ushort material, tex;
1316 ivec n;
1317 int offset;
1318 };
1319
htcmp(const cfkey & x,const cfkey & y)1320 static inline bool htcmp(const cfkey &x, const cfkey &y)
1321 {
1322 return x.orient == y.orient && x.tex == y.tex && x.n == y.n && x.offset == y.offset && x.material==y.material;
1323 }
1324
hthash(const cfkey & k)1325 static inline uint hthash(const cfkey &k)
1326 {
1327 return hthash(k.n)^k.offset^k.tex^k.orient^k.material;
1328 }
1329
mincubeface(const cube & cu,int orient,const ivec & o,int size,const facebounds & orig,facebounds & cf,ushort nmat,ushort matmask)1330 void mincubeface(const cube &cu, int orient, const ivec &o, int size, const facebounds &orig, facebounds &cf, ushort nmat, ushort matmask)
1331 {
1332 int dim = dimension(orient);
1333 if(cu.children)
1334 {
1335 size >>= 1;
1336 int coord = dimcoord(orient);
1337 loopi(8) if(octacoord(dim, i) == coord)
1338 mincubeface(cu.children[i], orient, ivec(i, o, size), size, orig, cf, nmat, matmask);
1339 return;
1340 }
1341 int c = C[dim], r = R[dim];
1342 ushort uco = (o[c]&0xFFF)<<3, vco = (o[r]&0xFFF)<<3;
1343 ushort uc1 = uco, vc1 = vco, uc2 = ushort(size<<3)+uco, vc2 = ushort(size<<3)+vco;
1344 uc1 = max(uc1, orig.u1);
1345 uc2 = min(uc2, orig.u2);
1346 vc1 = max(vc1, orig.v1);
1347 vc2 = min(vc2, orig.v2);
1348 if(!isempty(cu) && touchingface(cu, orient) && !(nmat!=MAT_AIR && (cu.material&matmask)==nmat))
1349 {
1350 uchar r1 = cu.edges[faceedgesidx[orient][0]], r2 = cu.edges[faceedgesidx[orient][1]],
1351 c1 = cu.edges[faceedgesidx[orient][2]], c2 = cu.edges[faceedgesidx[orient][3]];
1352 ushort u1 = max(c1&0xF, c2&0xF)*size+uco, u2 = min(c1>>4, c2>>4)*size+uco,
1353 v1 = max(r1&0xF, r2&0xF)*size+vco, v2 = min(r1>>4, r2>>4)*size+vco;
1354 u1 = max(u1, orig.u1);
1355 u2 = min(u2, orig.u2);
1356 v1 = max(v1, orig.v1);
1357 v2 = min(v2, orig.v2);
1358 if(v2-v1==vc2-vc1)
1359 {
1360 if(u2-u1==uc2-uc1) return;
1361 if(u1==uc1) uc1 = u2;
1362 if(u2==uc2) uc2 = u1;
1363 }
1364 else if(u2-u1==uc2-uc1)
1365 {
1366 if(v1==vc1) vc1 = v2;
1367 if(v2==vc2) vc2 = v1;
1368 }
1369 }
1370 if(uc1==uc2 || vc1==vc2) return;
1371 cf.u1 = min(cf.u1, uc1);
1372 cf.u2 = max(cf.u2, uc2);
1373 cf.v1 = min(cf.v1, vc1);
1374 cf.v2 = max(cf.v2, vc2);
1375 }
1376
mincubeface(const cube & cu,int orient,const ivec & co,int size,facebounds & orig)1377 bool mincubeface(const cube &cu, int orient, const ivec &co, int size, facebounds &orig)
1378 {
1379 ivec no;
1380 int nsize;
1381 const cube &nc = neighbourcube(cu, orient, co, size, no, nsize);
1382 facebounds mincf;
1383 mincf.u1 = orig.u2;
1384 mincf.u2 = orig.u1;
1385 mincf.v1 = orig.v2;
1386 mincf.v2 = orig.v1;
1387 mincubeface(nc, opposite(orient), no, nsize, orig, mincf, cu.material&MAT_ALPHA ? MAT_AIR : MAT_ALPHA, MAT_ALPHA);
1388 bool smaller = false;
1389 if(mincf.u1 > orig.u1) { orig.u1 = mincf.u1; smaller = true; }
1390 if(mincf.u2 < orig.u2) { orig.u2 = mincf.u2; smaller = true; }
1391 if(mincf.v1 > orig.v1) { orig.v1 = mincf.v1; smaller = true; }
1392 if(mincf.v2 < orig.v2) { orig.v2 = mincf.v2; smaller = true; }
1393 return smaller;
1394 }
1395
1396 VAR(0, maxmerge, 0, 6, 12);
1397 VAR(0, minface, 0, 4, 12);
1398
1399 struct pvert
1400 {
1401 ushort x, y;
1402
pvertpvert1403 pvert() {}
pvertpvert1404 pvert(ushort x, ushort y) : x(x), y(y) {}
1405
operator ==pvert1406 bool operator==(const pvert &o) const { return x == o.x && y == o.y; }
operator !=pvert1407 bool operator!=(const pvert &o) const { return x != o.x || y != o.y; }
1408 };
1409
1410 struct pedge
1411 {
1412 pvert from, to;
1413
pedgepedge1414 pedge() {}
pedgepedge1415 pedge(const pvert &from, const pvert &to) : from(from), to(to) {}
1416
operator ==pedge1417 bool operator==(const pedge &o) const { return from == o.from && to == o.to; }
operator !=pedge1418 bool operator!=(const pedge &o) const { return from != o.from || to != o.to; }
1419 };
1420
hthash(const pedge & x)1421 static inline uint hthash(const pedge &x) { return uint(x.from.x)^(uint(x.from.y)<<8); }
htcmp(const pedge & x,const pedge & y)1422 static inline bool htcmp(const pedge &x, const pedge &y) { return x == y; }
1423
1424 struct poly
1425 {
1426 cube *c;
1427 int numverts;
1428 bool merged;
1429 pvert verts[MAXFACEVERTS];
1430 };
1431
clippoly(poly & p,const facebounds & b)1432 bool clippoly(poly &p, const facebounds &b)
1433 {
1434 pvert verts1[MAXFACEVERTS+4], verts2[MAXFACEVERTS+4];
1435 int numverts1 = 0, numverts2 = 0, px = p.verts[p.numverts-1].x, py = p.verts[p.numverts-1].y;
1436 loopi(p.numverts)
1437 {
1438 int x = p.verts[i].x, y = p.verts[i].y;
1439 if(x < b.u1)
1440 {
1441 if(px > b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
1442 if(px > b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
1443 }
1444 else if(x > b.u2)
1445 {
1446 if(px < b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
1447 if(px < b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
1448 }
1449 else
1450 {
1451 if(px < b.u1)
1452 {
1453 if(x > b.u1) verts1[numverts1++] = pvert(b.u1, y + ((y - py)*(b.u1 - x))/(x - px));
1454 }
1455 else if(px > b.u2 && x < b.u2) verts1[numverts1++] = pvert(b.u2, y + ((y - py)*(b.u2 - x))/(x - px));
1456 verts1[numverts1++] = pvert(x, y);
1457 }
1458 px = x;
1459 py = y;
1460 }
1461 if(numverts1 < 3) return false;
1462 px = verts1[numverts1-1].x;
1463 py = verts1[numverts1-1].y;
1464 loopi(numverts1)
1465 {
1466 int x = verts1[i].x, y = verts1[i].y;
1467 if(y < b.v1)
1468 {
1469 if(py > b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
1470 if(py > b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
1471 }
1472 else if(y > b.v2)
1473 {
1474 if(py < b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
1475 if(py < b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
1476 }
1477 else
1478 {
1479 if(py < b.v1)
1480 {
1481 if(y > b.v1) verts2[numverts2++] = pvert(x + ((x - px)*(b.v1 - y))/(y - py), b.v1);
1482 }
1483 else if(py > b.v2 && y < b.v2) verts2[numverts2++] = pvert(x + ((x - px)*(b.v2 - y))/(y - py), b.v2);
1484 verts2[numverts2++] = pvert(x, y);
1485 }
1486 px = x;
1487 py = y;
1488 }
1489 if(numverts2 < 3) return false;
1490 if(numverts2 > MAXFACEVERTS) return false;
1491 memcpy(p.verts, verts2, numverts2*sizeof(pvert));
1492 p.numverts = numverts2;
1493 return true;
1494 }
1495
genpoly(cube & cu,int orient,const ivec & o,int size,int vis,ivec & n,int & offset,poly & p)1496 bool genpoly(cube &cu, int orient, const ivec &o, int size, int vis, ivec &n, int &offset, poly &p)
1497 {
1498 int dim = dimension(orient), coord = dimcoord(orient);
1499 ivec v[4];
1500 genfaceverts(cu, orient, v);
1501 if(flataxisface(cu, orient))
1502 {
1503 n = ivec(0, 0, 0);
1504 n[dim] = coord ? 1 : -1;
1505 }
1506 else
1507 {
1508 if(faceconvexity(v)) return false;
1509 n.cross(ivec(v[1]).sub(v[0]), ivec(v[2]).sub(v[0]));
1510 if(n.iszero()) n.cross(ivec(v[2]).sub(v[0]), ivec(v[3]).sub(v[0]));
1511 reduceslope(n);
1512 }
1513
1514 ivec po = ivec(o).mask(0xFFF).shl(3);
1515 loopk(4) v[k].mul(size).add(po);
1516 offset = -n.dot(v[3]);
1517
1518 int r = R[dim], c = C[dim], order = vis&4 ? 1 : 0;
1519 p.numverts = 0;
1520 if(coord)
1521 {
1522 const ivec &v0 = v[order]; p.verts[p.numverts++] = pvert(v0[c], v0[r]);
1523 if(vis&1) { const ivec &v1 = v[order+1]; p.verts[p.numverts++] = pvert(v1[c], v1[r]); }
1524 const ivec &v2 = v[order+2]; p.verts[p.numverts++] = pvert(v2[c], v2[r]);
1525 if(vis&2) { const ivec &v3 = v[(order+3)&3]; p.verts[p.numverts++] = pvert(v3[c], v3[r]); }
1526 }
1527 else
1528 {
1529 if(vis&2) { const ivec &v3 = v[(order+3)&3]; p.verts[p.numverts++] = pvert(v3[c], v3[r]); }
1530 const ivec &v2 = v[order+2]; p.verts[p.numverts++] = pvert(v2[c], v2[r]);
1531 if(vis&1) { const ivec &v1 = v[order+1]; p.verts[p.numverts++] = pvert(v1[c], v1[r]); }
1532 const ivec &v0 = v[order]; p.verts[p.numverts++] = pvert(v0[c], v0[r]);
1533 }
1534
1535 if(faceedges(cu, orient)!=F_SOLID)
1536 {
1537 int px = int(p.verts[p.numverts-2].x) - int(p.verts[p.numverts-3].x), py = int(p.verts[p.numverts-2].y) - int(p.verts[p.numverts-3].y),
1538 cx = int(p.verts[p.numverts-1].x) - int(p.verts[p.numverts-2].x), cy = int(p.verts[p.numverts-1].y) - int(p.verts[p.numverts-2].y),
1539 dir = px*cy - py*cx;
1540 if(dir > 0) return false;
1541 if(!dir) { if(p.numverts < 4) return false; p.verts[p.numverts-2] = p.verts[p.numverts-1]; p.numverts--; }
1542 px = cx; py = cy;
1543 cx = int(p.verts[0].x) - int(p.verts[p.numverts-1].x); cy = int(p.verts[0].y) - int(p.verts[p.numverts-1].y);
1544 dir = px*cy - py*cx;
1545 if(dir > 0) return false;
1546 if(!dir) { if(p.numverts < 4) return false; p.numverts--; }
1547 px = cx; py = cy;
1548 cx = int(p.verts[1].x) - int(p.verts[0].x); cy = int(p.verts[1].y) - int(p.verts[0].y);
1549 dir = px*cy - py*cx;
1550 if(dir > 0) return false;
1551 if(!dir) { if(p.numverts < 4) return false; p.verts[0] = p.verts[p.numverts-1]; p.numverts--; }
1552 px = cx; py = cy;
1553 cx = int(p.verts[2].x) - int(p.verts[1].x); cy = int(p.verts[2].y) - int(p.verts[1].y);
1554 dir = px*cy - py*cx;
1555 if(dir > 0) return false;
1556 if(!dir) { if(p.numverts < 4) return false; p.verts[1] = p.verts[2]; p.verts[2] = p.verts[3]; p.numverts--; }
1557 }
1558
1559 p.c = &cu;
1560 p.merged = false;
1561
1562 if(minface && size >= 1<<minface && touchingface(cu, orient))
1563 {
1564 facebounds b;
1565 b.u1 = b.u2 = p.verts[0].x;
1566 b.v1 = b.v2 = p.verts[0].y;
1567 for(int i = 1; i < p.numverts; i++)
1568 {
1569 const pvert &v = p.verts[i];
1570 b.u1 = min(b.u1, v.x);
1571 b.u2 = max(b.u2, v.x);
1572 b.v1 = min(b.v1, v.y);
1573 b.v2 = max(b.v2, v.y);
1574 }
1575 if(mincubeface(cu, orient, o, size, b) && clippoly(p, b))
1576 p.merged = true;
1577 }
1578
1579 return true;
1580 }
1581
1582 struct plink : pedge
1583 {
1584 int polys[2];
1585
plinkplink1586 plink() { clear(); }
plinkplink1587 plink(const pedge &p) : pedge(p) { clear(); }
1588
clearplink1589 void clear() { polys[0] = polys[1] = -1; }
1590 };
1591
mergepolys(int orient,hashset<plink> & links,vector<plink * > & queue,int owner,poly & p,poly & q,const pedge & e)1592 bool mergepolys(int orient, hashset<plink> &links, vector<plink *> &queue, int owner, poly &p, poly &q, const pedge &e)
1593 {
1594 int pe = -1, qe = -1;
1595 loopi(p.numverts) if(p.verts[i] == e.from) { pe = i; break; }
1596 loopi(q.numverts) if(q.verts[i] == e.to) { qe = i; break; }
1597 if(pe < 0 || qe < 0) return false;
1598 if(p.verts[(pe+1)%p.numverts] != e.to || q.verts[(qe+1)%q.numverts] != e.from) return false;
1599 /*
1600 * c----d
1601 * | |
1602 * F----T
1603 * | P |
1604 * b----a
1605 */
1606 pvert verts[2*MAXFACEVERTS];
1607 int numverts = 0, index = pe+2; // starts at A = T+1, ends at F = T+p.numverts
1608 loopi(p.numverts-1)
1609 {
1610 if(index >= p.numverts) index -= p.numverts;
1611 verts[numverts++] = p.verts[index++];
1612 }
1613 index = qe+2; // starts at C = T+2 = F+1, ends at T = T+q.numverts
1614 int px = int(verts[numverts-1].x) - int(verts[numverts-2].x), py = int(verts[numverts-1].y) - int(verts[numverts-2].y);
1615 loopi(q.numverts-1)
1616 {
1617 if(index >= q.numverts) index -= q.numverts;
1618 pvert &src = q.verts[index++];
1619 int cx = int(src.x) - int(verts[numverts-1].x), cy = int(src.y) - int(verts[numverts-1].y),
1620 dir = px*cy - py*cx;
1621 if(dir > 0) return false;
1622 if(!dir) numverts--;
1623 verts[numverts++] = src;
1624 px = cx;
1625 py = cy;
1626 }
1627 int cx = int(verts[0].x) - int(verts[numverts-1].x), cy = int(verts[0].y) - int(verts[numverts-1].y),
1628 dir = px*cy - py*cx;
1629 if(dir > 0) return false;
1630 if(!dir) numverts--;
1631
1632 if(numverts > MAXFACEVERTS) return false;
1633
1634 q.merged = true;
1635 q.numverts = 0;
1636
1637 p.merged = true;
1638 p.numverts = numverts;
1639 memcpy(p.verts, verts, numverts*sizeof(pvert));
1640
1641 int prev = p.numverts-1;
1642 loopj(p.numverts)
1643 {
1644 pedge e(p.verts[prev], p.verts[j]);
1645 int order = e.from.x > e.to.x || (e.from.x == e.to.x && e.from.y > e.to.y) ? 1 : 0;
1646 if(order) swap(e.from, e.to);
1647 plink &l = links.access(e, e);
1648 bool shouldqueue = l.polys[order] < 0 && l.polys[order^1] >= 0;
1649 l.polys[order] = owner;
1650 if(shouldqueue) queue.add(&l);
1651 prev = j;
1652 }
1653
1654 return true;
1655 }
1656
addmerge(cube & cu,int orient,const ivec & co,const ivec & n,int offset,poly & p)1657 void addmerge(cube &cu, int orient, const ivec &co, const ivec &n, int offset, poly &p)
1658 {
1659 cu.merged |= 1<<orient;
1660 if(!p.numverts)
1661 {
1662 if(cu.ext) cu.ext->surfaces[orient] = ambientsurface;
1663 return;
1664 }
1665 surfaceinfo surf = brightsurface;
1666 vertinfo verts[MAXFACEVERTS];
1667 surf.numverts |= p.numverts;
1668 int dim = dimension(orient), coord = dimcoord(orient), c = C[dim], r = R[dim];
1669 loopk(p.numverts)
1670 {
1671 pvert &src = p.verts[coord ? k : p.numverts-1-k];
1672 vertinfo &dst = verts[k];
1673 ivec v;
1674 v[c] = src.x;
1675 v[r] = src.y;
1676 v[dim] = -(offset + n[c]*src.x + n[r]*src.y)/n[dim];
1677 dst.set(v);
1678 }
1679 if(cu.ext)
1680 {
1681 const surfaceinfo &oldsurf = cu.ext->surfaces[orient];
1682 int numverts = oldsurf.numverts&MAXFACEVERTS;
1683 if(numverts == p.numverts)
1684 {
1685 ivec v0 = verts[0].getxyz();
1686 const vertinfo *oldverts = cu.ext->verts() + oldsurf.verts;
1687 loopj(numverts) if(v0 == oldverts[j].getxyz())
1688 {
1689 for(int k = 1; k < numverts; k++)
1690 {
1691 if(++j >= numverts) j = 0;
1692 if(verts[k].getxyz() != oldverts[j].getxyz()) goto nomatch;
1693 }
1694 return;
1695 }
1696 nomatch:;
1697 }
1698 }
1699 setsurface(cu, orient, surf, verts, p.numverts);
1700 }
1701
clearmerge(cube & c,int orient)1702 static inline void clearmerge(cube &c, int orient)
1703 {
1704 if(c.merged&(1<<orient))
1705 {
1706 c.merged &= ~(1<<orient);
1707 if(c.ext) c.ext->surfaces[orient] = brightsurface;
1708 }
1709 }
1710
addmerges(int orient,const ivec & co,const ivec & n,int offset,vector<poly> & polys)1711 void addmerges(int orient, const ivec &co, const ivec &n, int offset, vector<poly> &polys)
1712 {
1713 loopv(polys)
1714 {
1715 poly &p = polys[i];
1716 if(p.merged) addmerge(*p.c, orient, co, n, offset, p);
1717 else clearmerge(*p.c, orient);
1718 }
1719 }
1720
mergepolys(int orient,const ivec & co,const ivec & n,int offset,vector<poly> & polys)1721 void mergepolys(int orient, const ivec &co, const ivec &n, int offset, vector<poly> &polys)
1722 {
1723 if(polys.length() <= 1) { addmerges(orient, co, n, offset, polys); return; }
1724 hashset<plink> links(polys.length() <= 32 ? 128 : 1024);
1725 vector<plink *> queue;
1726 loopv(polys)
1727 {
1728 poly &p = polys[i];
1729 int prev = p.numverts-1;
1730 loopj(p.numverts)
1731 {
1732 pedge e(p.verts[prev], p.verts[j]);
1733 int order = e.from.x > e.to.x || (e.from.x == e.to.x && e.from.y > e.to.y) ? 1 : 0;
1734 if(order) swap(e.from, e.to);
1735 plink &l = links.access(e, e);
1736 l.polys[order] = i;
1737 if(l.polys[0] >= 0 && l.polys[1] >= 0) queue.add(&l);
1738 prev = j;
1739 }
1740 }
1741 vector<plink *> nextqueue;
1742 while(queue.length())
1743 {
1744 loopv(queue)
1745 {
1746 plink &l = *queue[i];
1747 if(l.polys[0] >= 0 && l.polys[1] >= 0)
1748 mergepolys(orient, links, nextqueue, l.polys[0], polys[l.polys[0]], polys[l.polys[1]], l);
1749 }
1750 queue.setsize(0);
1751 queue.move(nextqueue);
1752 }
1753 addmerges(orient, co, n, offset, polys);
1754 }
1755
1756 static int genmergeprogress = 0;
1757
1758 struct cfpolys
1759 {
1760 vector<poly> polys;
1761 };
1762
1763 static hashtable<cfkey, cfpolys> cpolys;
1764
genmerges(cube * c=worldroot,const ivec & o=ivec (0,0,0),int size=hdr.worldsize>>1)1765 void genmerges(cube *c = worldroot, const ivec &o = ivec(0, 0, 0), int size = hdr.worldsize>>1)
1766 {
1767 if((genmergeprogress++&0x7FF)==0) progress(float(genmergeprogress)/allocnodes, "merging surfaces...");
1768 neighbourstack[++neighbourdepth] = c;
1769 loopi(8)
1770 {
1771 ivec co(i, o, size);
1772 int vis;
1773 if(c[i].children) genmerges(c[i].children, co, size>>1);
1774 else if(!isempty(c[i])) loopj(6) if((vis = visibletris(c[i], j, co, size)))
1775 {
1776 cfkey k;
1777 poly p;
1778 if(size < 1<<maxmerge && c != worldroot)
1779 {
1780 if(genpoly(c[i], j, co, size, vis, k.n, k.offset, p))
1781 {
1782 k.orient = j;
1783 k.tex = c[i].texture[j];
1784 k.material = c[i].material&MAT_ALPHA;
1785 cpolys[k].polys.add(p);
1786 continue;
1787 }
1788 }
1789 else if(minface && size >= 1<<minface && touchingface(c[i], j))
1790 {
1791 if(genpoly(c[i], j, co, size, vis, k.n, k.offset, p) && p.merged)
1792 {
1793 addmerge(c[i], j, co, k.n, k.offset, p);
1794 continue;
1795 }
1796 }
1797 clearmerge(c[i], j);
1798 }
1799 if((size == 1<<maxmerge || c == worldroot) && cpolys.numelems)
1800 {
1801 enumeratekt(cpolys, cfkey, key, cfpolys, val,
1802 {
1803 mergepolys(key.orient, co, key.n, key.offset, val.polys);
1804 });
1805 cpolys.clear();
1806 }
1807 }
1808 --neighbourdepth;
1809 }
1810
calcmergedsize(int orient,const ivec & co,int size,const vertinfo * verts,int numverts)1811 int calcmergedsize(int orient, const ivec &co, int size, const vertinfo *verts, int numverts)
1812 {
1813 ushort x1 = verts[0].x, y1 = verts[0].y, z1 = verts[0].z,
1814 x2 = x1, y2 = y1, z2 = z1;
1815 for(int i = 1; i < numverts; i++)
1816 {
1817 const vertinfo &v = verts[i];
1818 x1 = min(x1, v.x);
1819 x2 = max(x2, v.x);
1820 y1 = min(y1, v.y);
1821 y2 = max(y2, v.y);
1822 z1 = min(z1, v.z);
1823 z2 = max(z2, v.z);
1824 }
1825 int bits = 0;
1826 while(1<<bits < size) ++bits;
1827 bits += 3;
1828 ivec mo(co);
1829 mo.mask(0xFFF);
1830 mo.shl(3);
1831 while(bits<15)
1832 {
1833 mo.mask(~((1<<bits)-1));
1834 if(mo.x <= x1 && mo.x + (1<<bits) >= x2 &&
1835 mo.y <= y1 && mo.y + (1<<bits) >= y2 &&
1836 mo.z <= z1 && mo.z + (1<<bits) >= z2)
1837 break;
1838 bits++;
1839 }
1840 return bits-3;
1841 }
1842
invalidatemerges(cube & c)1843 static void invalidatemerges(cube &c)
1844 {
1845 if(c.merged)
1846 {
1847 brightencube(c);
1848 c.merged = 0;
1849 }
1850 if(c.ext)
1851 {
1852 if(c.ext->va)
1853 {
1854 if(!(c.ext->va->hasmerges&(MERGE_PART | MERGE_ORIGIN))) return;
1855 destroyva(c.ext->va);
1856 c.ext->va = NULL;
1857 }
1858 if(c.ext->tjoints >= 0) c.ext->tjoints = -1;
1859 }
1860 if(c.children) loopi(8) invalidatemerges(c.children[i]);
1861 }
1862
1863 static int invalidatedmerges = 0;
1864
invalidatemerges(cube & c,const ivec & co,int size,bool msg)1865 void invalidatemerges(cube &c, const ivec &co, int size, bool msg)
1866 {
1867 if(msg && invalidatedmerges!=totalmillis)
1868 {
1869 progress(0, "invalidating merged surfaces...");
1870 invalidatedmerges = totalmillis;
1871 }
1872 invalidatemerges(c);
1873 }
1874
calcmerges()1875 void calcmerges()
1876 {
1877 genmergeprogress = 0;
1878 genmerges();
1879 }
1880
1881