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