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