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