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