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