1 #include "engine.h"
2 #include "SDL_thread.h"
3
4 enum
5 {
6 PVS_HIDE_GEOM = 1<<0,
7 PVS_HIDE_BB = 1<<1
8 };
9
10 struct pvsnode
11 {
12 bvec edges;
13 uchar flags;
14 uint children;
15 };
16
17 static vector<pvsnode> origpvsnodes;
18
mergepvsnodes(pvsnode & p,pvsnode * children)19 static bool mergepvsnodes(pvsnode &p, pvsnode *children)
20 {
21 loopi(7) if(children[i].flags!=children[7].flags) return false;
22 bvec bbs[4];
23 loop(x, 2) loop(y, 2)
24 {
25 const bvec &lo = children[octaindex(2, x, y, 0)].edges,
26 &hi = children[octaindex(2, x, y, 1)].edges;
27 if(lo.x!=0xFF && (lo.x&0x11 || lo.y&0x11 || lo.z&0x11)) return false;
28 if(hi.x!=0xFF && (hi.x&0x11 || hi.y&0x11 || hi.z&0x11)) return false;
29
30 #define MERGEBBS(res, coord, row, col) \
31 if(lo.coord==0xFF) \
32 { \
33 if(hi.coord!=0xFF) \
34 { \
35 res.coord = ((hi.coord&~0x11)>>1) + 0x44; \
36 res.row = hi.row; \
37 res.col = hi.col; \
38 } \
39 } \
40 else if(hi.coord==0xFF) \
41 { \
42 res.coord = (lo.coord&0xEE)>>1; \
43 res.row = lo.row; \
44 res.col = lo.col; \
45 } \
46 else if(lo.row!=hi.row || lo.col!=hi.col || (lo.coord&0xF0)!=0x80 || (hi.coord&0xF)!=0) return false; \
47 else \
48 { \
49 res.coord = ((lo.coord&~0xF1)>>1) | (((hi.coord&~0x1F)>>1) + 0x40); \
50 res.row = lo.row; \
51 res.col = lo.col; \
52 }
53
54 bvec &res = bbs[x + 2*y];
55 MERGEBBS(res, z, x, y);
56 res.x = lo.x;
57 res.y = lo.y;
58 }
59 loop(x, 2)
60 {
61 bvec &lo = bbs[x], &hi = bbs[x+2];
62 MERGEBBS(lo, y, x, z);
63 }
64 bvec &lo = bbs[0], &hi = bbs[1];
65 MERGEBBS(p.edges, x, y, z);
66
67 return true;
68 }
69
genpvsnodes(cube * c,int parent=0,const ivec & co=ivec (0,0,0),int size=hdr.worldsize/2)70 static void genpvsnodes(cube *c, int parent = 0, const ivec &co = ivec(0, 0, 0), int size = hdr.worldsize/2)
71 {
72 int index = origpvsnodes.length();
73 loopi(8)
74 {
75 ivec o(i, co, size);
76 pvsnode &n = origpvsnodes.add();
77 n.flags = 0;
78 n.children = 0;
79 if(c[i].children || isempty(c[i]) || c[i].material&MAT_ALPHA) memset(n.edges.v, 0xFF, 3);
80 else loopk(3)
81 {
82 uint face = c[i].faces[k];
83 if(face==F_SOLID) n.edges[k] = 0x80;
84 else
85 {
86 uchar low = max(max(face&0xF, (face>>8)&0xF), max((face>>16)&0xF, (face>>24)&0xF)),
87 high = min(min((face>>4)&0xF, (face>>12)&0xF), min((face>>20)&0xF, (face>>28)&0xF));
88 if(size<8)
89 {
90 if(low&((8/size)-1)) { low += 8/size - (low&((8/size)-1)); }
91 if(high&((8/size)-1)) high &= ~(8/size-1);
92 }
93 if(low >= high) { memset(n.edges.v, 0xFF, 3); break; }
94 n.edges[k] = low | (high<<4);
95 }
96 }
97 }
98 int branches = 0;
99 loopi(8) if(c[i].children)
100 {
101 ivec o(i, co, size);
102 genpvsnodes(c[i].children, index+i, o, size>>1);
103 if(origpvsnodes[index+i].children) branches++;
104 }
105 if(!branches && mergepvsnodes(origpvsnodes[parent], &origpvsnodes[index])) origpvsnodes.setsize(index);
106 else origpvsnodes[parent].children = index;
107 }
108
109 struct shaftplane
110 {
111 float r, c, offset;
112 uchar rnear, cnear, rfar, cfar;
113 };
114
115 struct shaftbb
116 {
117 union
118 {
119 ushort v[6];
120 struct { usvec min, max; };
121 };
122
shaftbbshaftbb123 shaftbb() {}
shaftbbshaftbb124 shaftbb(const ivec &o, int size)
125 {
126 min.x = o.x;
127 min.y = o.y;
128 min.z = o.z;
129 max.x = o.x + size;
130 max.y = o.y + size;
131 max.z = o.z + size;
132 }
shaftbbshaftbb133 shaftbb(const ivec &o, int size, const bvec &edges)
134 {
135 min.x = o.x + (size*(edges.x&0xF))/8;
136 min.y = o.y + (size*(edges.y&0xF))/8;
137 min.z = o.z + (size*(edges.z&0xF))/8;
138 max.x = o.x + (size*(edges.x>>4))/8;
139 max.y = o.y + (size*(edges.y>>4))/8;
140 max.z = o.z + (size*(edges.z>>4))/8;
141 }
142
operator []shaftbb143 ushort &operator[](int i) { return v[i]; }
operator []shaftbb144 ushort operator[](int i) const { return v[i]; }
145
containsshaftbb146 bool contains(const shaftbb &o) const
147 {
148 return min.x<=o.min.x && min.y<=o.min.y && min.z<=o.min.z &&
149 max.x>=o.max.x && max.y>=o.max.y && max.z>=o.max.z;
150 }
151
outsideshaftbb152 bool outside(const ivec &o, int size) const
153 {
154 return o.x>=max.x || o.y>=max.y || o.z>=max.z ||
155 o.x+size<=min.x || o.y+size<=min.y || o.z+size<=min.z;
156 }
157
outsideshaftbb158 bool outside(const shaftbb &o) const
159 {
160 return o.min.x>max.x || o.min.y>max.y || o.min.z>max.z ||
161 o.max.x<min.x || o.max.y<min.y || o.max.z<min.z;
162 }
163
notinsideshaftbb164 bool notinside(const shaftbb &o) const
165 {
166 return o.min.x<min.x || o.min.y<min.y || o.min.z<min.z ||
167 o.max.x>max.x || o.max.y>max.y || o.max.z>max.z;
168 }
169 };
170
171 struct shaft
172 {
173 shaftbb bounds;
174 shaftplane planes[8];
175 int numplanes;
176
shaftshaft177 shaft(const shaftbb &from, const shaftbb &to)
178 {
179 calcshaft(from, to);
180 }
181
calcshaftshaft182 void calcshaft(const shaftbb &from, const shaftbb &to)
183 {
184 uchar match = 0, color = 0;
185 loopi(3)
186 {
187 if(to.min[i] < from.min[i]) { color |= 1<<i; bounds.min[i] = 0; }
188 else if(to.min[i] > from.min[i]) bounds.min[i] = to.min[i]+1;
189 else { match |= 1<<i; bounds.min[i] = to.min[i]; }
190
191 if(to.max[i] > from.max[i]) { color |= 8<<i; bounds.max[i] = USHRT_MAX; }
192 else if(to.max[i] < from.max[i]) bounds.max[i] = to.max[i]-1;
193 else { match |= 8<<i; bounds.max[i] = to.max[i]; }
194 }
195 numplanes = 0;
196 loopi(5) if(!(match&(1<<i))) for(int j = i+1; j<6; j++) if(!(match&(1<<j)) && i+3!=j && ((color>>i)^(color>>j))&1)
197 {
198 int r = i%3, c = j%3, d = (r+1)%3;
199 if(d==c) d = (c+1)%3;
200 shaftplane &p = planes[numplanes++];
201 p.r = from[j] - to[j];
202 if(i<3 ? p.r >= 0 : p.r < 0)
203 {
204 p.r = -p.r;
205 p.c = from[i] - to[i];
206 }
207 else p.c = to[i] - from[i];
208 p.offset = -(from[i]*p.r + from[j]*p.c);
209 p.rnear = p.r >= 0 ? r : 3+r;
210 p.cnear = p.c >= 0 ? c : 3+c;
211 p.rfar = p.r < 0 ? r : 3+r;
212 p.cfar = p.c < 0 ? c : 3+c;
213 }
214 }
215
outsideshaft216 bool outside(const shaftbb &o) const
217 {
218 if(bounds.outside(o)) return true;
219
220 for(const shaftplane *p = planes; p < &planes[numplanes]; p++)
221 {
222 if(o[p->rnear]*p->r + o[p->cnear]*p->c + p->offset > 0) return true;
223 }
224 return false;
225 }
226
insideshaft227 bool inside(const shaftbb &o) const
228 {
229 if(bounds.notinside(o)) return false;
230
231 for(const shaftplane *p = planes; p < &planes[numplanes]; p++)
232 {
233 if(o[p->rfar]*p->r + o[p->cfar]*p->c + p->offset > 0) return false;
234 }
235 return true;
236 }
237 };
238
239 struct pvsdata
240 {
241 int offset, len;
242
pvsdatapvsdata243 pvsdata() {}
pvsdatapvsdata244 pvsdata(int offset, int len) : offset(offset), len(len) {}
245 };
246
247 static vector<uchar> pvsbuf;
248
hthash(const pvsdata & k)249 static inline uint hthash(const pvsdata &k)
250 {
251 uint h = 5381;
252 loopi(k.len) h = ((h<<5)+h)^pvsbuf[k.offset+i];
253 return h;
254 }
255
htcmp(const pvsdata & x,const pvsdata & y)256 static inline bool htcmp(const pvsdata &x, const pvsdata &y)
257 {
258 return x.len==y.len && !memcmp(&pvsbuf[x.offset], &pvsbuf[y.offset], x.len);
259 }
260
261 static SDL_mutex *pvsmutex = NULL;
262 static hashtable<pvsdata, int> pvscompress;
263 static vector<pvsdata> pvs;
264
265 static SDL_mutex *viewcellmutex = NULL;
266 struct viewcellrequest
267 {
268 int *result;
269 ivec o;
270 int size;
271 };
272 static vector<viewcellrequest> viewcellrequests;
273
274 static bool genpvs_canceled = false;
275 static int numviewcells = 0;
276
277 VAR(0, maxpvsblocker, 1, 512, 1<<16);
278 VAR(0, pvsleafsize, 1, 64, 1024);
279
280 #define MAXWATERPVS 32
281
282 static struct
283 {
284 int height;
285 vector<materialsurface *> matsurfs;
286 } waterplanes[MAXWATERPVS];
287 static vector<materialsurface *> waterfalls;
288 uint numwaterplanes = 0;
289
290 struct pvsworker
291 {
pvsworkerpvsworker292 pvsworker() : thread(NULL), pvsnodes(new pvsnode[origpvsnodes.length()])
293 {
294 }
~pvsworkerpvsworker295 ~pvsworker()
296 {
297 delete[] pvsnodes;
298 }
299
300 SDL_Thread *thread;
301 pvsnode *pvsnodes;
302
303 shaftbb viewcellbb;
304
305 pvsnode *levels[32];
306 int curlevel;
307 ivec origin;
308
resetlevelspvsworker309 void resetlevels()
310 {
311 curlevel = worldscale;
312 levels[curlevel] = &pvsnodes[0];
313 origin = ivec(0, 0, 0);
314 }
315
hasvoxelpvsworker316 int hasvoxel(const ivec &p, int coord, int dir, int ocoord = 0, int odir = 0, int *omin = NULL)
317 {
318 uint diff = (origin.x^p.x)|(origin.y^p.y)|(origin.z^p.z);
319 if(diff >= uint(hdr.worldsize)) return 0;
320 diff >>= curlevel;
321 while(diff)
322 {
323 curlevel++;
324 diff >>= 1;
325 }
326
327 pvsnode *cur = levels[curlevel];
328 while(cur->children && !(cur->flags&PVS_HIDE_BB))
329 {
330 cur = &pvsnodes[cur->children];
331 curlevel--;
332 cur += ((p.z>>(curlevel-2))&4) | ((p.y>>(curlevel-1))&2) | ((p.x>>curlevel)&1);
333 levels[curlevel] = cur;
334 }
335
336 origin = ivec(p.x&(~0<<curlevel), p.y&(~0<<curlevel), p.z&(~0<<curlevel));
337
338 if(cur->flags&PVS_HIDE_BB || cur->edges==bvec(0x80, 0x80, 0x80))
339 {
340 if(omin)
341 {
342 int step = origin[ocoord] + (odir<<curlevel) - p[ocoord] + odir - 1;
343 if(odir ? step < *omin : step > *omin) *omin = step;
344 }
345 return origin[coord] + (dir<<curlevel) - p[coord] + dir - 1;
346 }
347
348 if(cur->edges.x==0xFF) return 0;
349 ivec bbp(p);
350 bbp.sub(origin);
351 ivec bbmin, bbmax;
352 bbmin.x = ((cur->edges.x&0xF)<<curlevel)/8;
353 if(bbp.x < bbmin.x) return 0;
354 bbmax.x = ((cur->edges.x>>4)<<curlevel)/8;
355 if(bbp.x >= bbmax.x) return 0;
356 bbmin.y = ((cur->edges.y&0xF)<<curlevel)/8;
357 if(bbp.y < bbmin.y) return 0;
358 bbmax.y = ((cur->edges.y>>4)<<curlevel)/8;
359 if(bbp.y >= bbmax.y) return 0;
360 bbmin.z = ((cur->edges.z&0xF)<<curlevel)/8;
361 if(bbp.z < bbmin.z) return 0;
362 bbmax.z = ((cur->edges.z>>4)<<curlevel)/8;
363 if(bbp.z >= bbmax.z) return 0;
364
365 if(omin)
366 {
367 int step = (odir ? bbmax[ocoord] : bbmin[ocoord]) - bbp[ocoord] + (odir - 1);
368 if(odir ? step < *omin : step > *omin) *omin = step;
369 }
370 return (dir ? bbmax[coord] : bbmin[coord]) - bbp[coord] + (dir - 1);
371 }
372
hidepvspvsworker373 void hidepvs(pvsnode &p)
374 {
375 if(p.children)
376 {
377 pvsnode *children = &pvsnodes[p.children];
378 loopi(8) hidepvs(children[i]);
379 p.flags |= PVS_HIDE_BB;
380 return;
381 }
382 p.flags |= PVS_HIDE_BB;
383 if(p.edges.x!=0xFF) p.flags |= PVS_HIDE_GEOM;
384 }
385
shaftcullpvspvsworker386 void shaftcullpvs(shaft &s, pvsnode &p, const ivec &co = ivec(0, 0, 0), int size = hdr.worldsize)
387 {
388 if(p.flags&PVS_HIDE_BB) return;
389 shaftbb bb(co, size);
390 if(s.outside(bb)) return;
391 if(s.inside(bb)) { hidepvs(p); return; }
392 if(p.children)
393 {
394 pvsnode *children = &pvsnodes[p.children];
395 uchar flags = 0xFF;
396 loopi(8)
397 {
398 ivec o(i, co, size>>1);
399 shaftcullpvs(s, children[i], o, size>>1);
400 flags &= children[i].flags;
401 }
402 if(flags & PVS_HIDE_BB) p.flags |= PVS_HIDE_BB;
403 return;
404 }
405 if(p.edges.x==0xFF) return;
406 shaftbb geom(co, size, p.edges);
407 if(s.inside(geom)) p.flags |= PVS_HIDE_GEOM;
408 }
409
410 queue<shaftbb, 32> prevblockers;
411
412 struct cullorder
413 {
414 int index, dist;
415
cullorderpvsworker::cullorder416 cullorder() {}
cullorderpvsworker::cullorder417 cullorder(int index, int dist) : index(index), dist(dist) {}
418 };
419
cullpvspvsworker420 void cullpvs(pvsnode &p, const ivec &co = ivec(0, 0, 0), int size = hdr.worldsize)
421 {
422 if(p.flags&(PVS_HIDE_BB | PVS_HIDE_GEOM) || genpvs_canceled) return;
423 if(p.children && !(p.flags&PVS_HIDE_BB))
424 {
425 pvsnode *children = &pvsnodes[p.children];
426 int csize = size>>1;
427 ivec dmin = ivec(co).add(csize>>1).sub(ivec(viewcellbb.min).add(ivec(viewcellbb.max)).shr(1)), dmax = ivec(dmin).add(csize);
428 dmin.mul(dmin);
429 dmax.mul(dmax);
430 ivec diff = ivec(dmax).sub(dmin);
431 cullorder order[8];
432 int dir = 0;
433 if(diff.x < 0) { diff.x = -diff.x; dir |= 1; }
434 if(diff.y < 0) { diff.y = -diff.y; dir |= 2; }
435 if(diff.z < 0) { diff.z = -diff.z; dir |= 4; }
436 order[0] = cullorder(0, 0);
437 order[7] = cullorder(7, diff.x + diff.y + diff.z);
438 order[1] = cullorder(1, diff.x);
439 order[2] = cullorder(2, diff.y);
440 order[3] = cullorder(4, diff.z);
441 if(order[2].dist < order[1].dist) swap(order[1], order[2]);
442 if(order[3].dist < order[2].dist) swap(order[2], order[3]);
443 if(order[2].dist < order[1].dist) swap(order[1], order[2]);
444 cullorder dxy(order[1].index|order[2].index, order[1].dist+order[2].dist),
445 dxz(order[1].index|order[3].index, order[1].dist+order[3].dist),
446 dyz(order[2].index|order[3].index, order[2].dist+order[3].dist);
447 int j;
448 for(j = 4; j > 0 && dxy.dist < order[j-1].dist; --j) order[j] = order[j-1];
449 order[j] = dxy;
450 for(j = 5; j > 0 && dxz.dist < order[j-1].dist; --j) order[j] = order[j-1];
451 order[j] = dxz;
452 for(j = 6; j > 0 && dyz.dist < order[j-1].dist; --j) order[j] = order[j-1];
453 order[j] = dyz;
454 loopi(8)
455 {
456 int index = order[i].index^dir;
457 ivec o(index, co, csize);
458 cullpvs(children[index], o, csize);
459 }
460 if(!(p.flags & PVS_HIDE_BB)) return;
461 }
462 bvec edges = p.children ? bvec(0x80, 0x80, 0x80) : p.edges;
463 if(edges.x==0xFF) return;
464 shaftbb geom(co, size, edges);
465 ivec diff = ivec(geom.max).sub(ivec(viewcellbb.min)).abs();
466 cullorder order[3] = { cullorder(0, diff.x), cullorder(1, diff.y), cullorder(2, diff.z) };
467 if(order[1].dist > order[0].dist) swap(order[0], order[1]);
468 if(order[2].dist > order[1].dist) swap(order[1], order[2]);
469 if(order[1].dist > order[0].dist) swap(order[0], order[1]);
470 loopi(6)
471 {
472 int dim = order[i >= 3 ? i-3 : i].index, dc = (i >= 3) != (geom.max[dim] <= viewcellbb.min[dim]) ? 1 : 0, r = R[dim], c = C[dim];
473 int ccenter = geom.min[c];
474 if(geom.min[r]==geom.max[r] || geom.min[c]==geom.max[c]) continue;
475 while(ccenter < geom.max[c])
476 {
477 ivec rmin;
478 rmin[dim] = geom[dim + 3*dc] + (dc ? -1 : 0);
479 rmin[r] = geom.min[r];
480 rmin[c] = ccenter;
481 ivec rmax = rmin;
482 rmax[r] = geom.max[r] - 1;
483 int rcenter = (rmin[r] + rmax[r])/2;
484 resetlevels();
485 for(int minstep = -1, maxstep = 1; (minstep || maxstep) && rmax[r] - rmin[r] < maxpvsblocker;)
486 {
487 if(minstep) minstep = hasvoxel(rmin, r, 0);
488 if(maxstep) maxstep = hasvoxel(rmax, r, 1);
489 rmin[r] += minstep;
490 rmax[r] += maxstep;
491 }
492 rmin[r] = rcenter + (rmin[r] - rcenter)/2;
493 rmax[r] = rcenter + (rmax[r] - rcenter)/2;
494 if(rmin[r]>=geom.min[r] && rmax[r]<geom.max[r]) { rmin[r] = geom.min[r]; rmax[r] = geom.max[r] - 1; }
495 ivec cmin = rmin, cmax = rmin;
496 if(rmin[r]>=geom.min[r] && rmax[r]<geom.max[r])
497 {
498 cmin[c] = geom.min[c];
499 cmax[c] = geom.max[c]-1;
500 }
501 int cminstep = -1, cmaxstep = 1;
502 for(; (cminstep || cmaxstep) && cmax[c] - cmin[c] < maxpvsblocker;)
503 {
504 if(cminstep)
505 {
506 cmin[c] += cminstep; cminstep = INT_MIN;
507 cmin[r] = rmin[r];
508 resetlevels();
509 for(int rstep = 1; rstep && cmin[r] <= rmax[r];)
510 {
511 rstep = hasvoxel(cmin, r, 1, c, 0, &cminstep);
512 cmin[r] += rstep;
513 }
514 if(cmin[r] <= rmax[r]) cminstep = 0;
515 }
516 if(cmaxstep)
517 {
518 cmax[c] += cmaxstep; cmaxstep = INT_MAX;
519 cmax[r] = rmin[r];
520 resetlevels();
521 for(int rstep = 1; rstep && cmax[r] <= rmax[r];)
522 {
523 rstep = hasvoxel(cmax, r, 1, c, 1, &cmaxstep);
524 cmax[r] += rstep;
525 }
526 if(cmax[r] <= rmax[r]) cmaxstep = 0;
527 }
528 }
529 if(!cminstep) cmin[c]++;
530 if(!cmaxstep) cmax[c]--;
531 ivec emin = rmin, emax = rmax;
532 if(cmin[c]>=geom.min[c] && cmax[c]<geom.max[c])
533 {
534 if(emin[r]>geom.min[r]) emin[r] = geom.min[r];
535 if(emax[r]<geom.max[r]-1) emax[r] = geom.max[r]-1;
536 }
537 int rminstep = -1, rmaxstep = 1;
538 for(; (rminstep || rmaxstep) && emax[r] - emin[r] < maxpvsblocker;)
539 {
540 if(rminstep)
541 {
542 emin[r] += -1; rminstep = INT_MIN;
543 emin[c] = cmin[c];
544 resetlevels();
545 for(int cstep = 1; cstep && emin[c] <= cmax[c];)
546 {
547 cstep = hasvoxel(emin, c, 1, r, 0, &rminstep);
548 emin[c] += cstep;
549 }
550 if(emin[c] <= cmax[c]) rminstep = 0;
551 }
552 if(rmaxstep)
553 {
554 emax[r] += 1; rmaxstep = INT_MAX;
555 emax[c] = cmin[c];
556 resetlevels();
557 for(int cstep = 1; cstep && emax[c] <= cmax[c];)
558 {
559 cstep = hasvoxel(emax, c, 1, r, 1, &rmaxstep);
560 emax[c] += cstep;
561 }
562 if(emax[c] <= cmax[c]) rmaxstep = 0;
563 }
564 }
565 if(!rminstep) emin[r]++;
566 if(!rmaxstep) emax[r]--;
567 shaftbb bb;
568 bb.min[dim] = rmin[dim];
569 bb.max[dim] = rmin[dim]+1;
570 bb.min[r] = emin[r];
571 bb.max[r] = emax[r]+1;
572 bb.min[c] = cmin[c];
573 bb.max[c] = cmax[c]+1;
574 if(bb.min[dim] >= viewcellbb.max[dim] || bb.max[dim] <= viewcellbb.min[dim])
575 {
576 int ddir = bb.min[dim] >= viewcellbb.max[dim] ? 1 : -1,
577 dval = ddir>0 ? USHRT_MAX-1 : 0,
578 dlimit = maxpvsblocker,
579 numsides = 0;
580 loopj(4)
581 {
582 ivec dmax;
583 int odim = j < 2 ? c : r;
584 if(j&1)
585 {
586 if(bb.max[odim] >= viewcellbb.max[odim]) continue;
587 dmax[odim] = bb.max[odim]-1;
588 }
589 else
590 {
591 if(bb.min[odim] <= viewcellbb.min[odim]) continue;
592 dmax[odim] = bb.min[odim];
593 }
594 numsides++;
595 dmax[dim] = bb.min[dim];
596 int stepdim = j < 2 ? r : c, stepstart = bb.min[stepdim], stepend = bb.max[stepdim];
597 int dstep = ddir;
598 for(; dstep && ddir*(dmax[dim] - (int)bb.min[dim]) < dlimit;)
599 {
600 dmax[dim] += dstep; dstep = ddir > 0 ? INT_MAX : INT_MIN;
601 dmax[stepdim] = stepstart;
602 resetlevels();
603 for(int step = 1; step && dmax[stepdim] < stepend;)
604 {
605 step = hasvoxel(dmax, stepdim, 1, dim, (ddir+1)/2, &dstep);
606 dmax[stepdim] += step;
607 }
608 if(dmax[stepdim] < stepend) dstep = 0;
609 }
610 dlimit = min(dlimit, ddir*(dmax[dim] - (int)bb.min[dim]));
611 if(!dstep) dmax[dim] -= ddir;
612 if(ddir>0) dval = min(dval, dmax[dim]);
613 else dval = max(dval, dmax[dim]);
614 }
615 if(numsides>0)
616 {
617 if(ddir>0) bb.max[dim] = dval+1;
618 else bb.min[dim] = dval;
619 }
620 //printf("(%d,%d,%d) x %d,%d,%d, side %d, ccenter = %d, origin = (%d,%d,%d), size = %d\n", bb.min.x, bb.min.y, bb.min.z, bb.max.x-bb.min.x, bb.max.y-bb.min.y, bb.max.z-bb.min.z, i, ccenter, co.x, co.y, co.z, size);
621 }
622 bool dup = false;
623 loopvj(prevblockers)
624 {
625 if(prevblockers[j].contains(bb)) { dup = true; break; }
626 }
627 if(!dup)
628 {
629 shaft s(viewcellbb, bb);
630 shaftcullpvs(s, pvsnodes[0]);
631 prevblockers.add(bb);
632 }
633 if(bb.contains(geom)) return;
634 ccenter = cmax[c] + 1;
635 }
636 }
637 }
638
compresspvspvsworker639 bool compresspvs(pvsnode &p, int size, int threshold)
640 {
641 if(!p.children) return true;
642 if(p.flags&PVS_HIDE_BB) { p.children = 0; return true; }
643 pvsnode *children = &pvsnodes[p.children];
644 bool canreduce = true;
645 loopi(8)
646 {
647 if(!compresspvs(children[i], size/2, threshold)) canreduce = false;
648 }
649 if(canreduce)
650 {
651 int hide = children[7].flags&PVS_HIDE_BB;
652 loopi(7) if((children[i].flags&PVS_HIDE_BB)!=hide) canreduce = false;
653 if(canreduce)
654 {
655 p.flags = (p.flags & ~PVS_HIDE_BB) | hide;
656 p.children = 0;
657 return true;
658 }
659 }
660 if(size <= threshold)
661 {
662 p.children = 0;
663 return true;
664 }
665 return false;
666 }
667
668 vector<uchar> outbuf;
669
serializepvspvsworker670 bool serializepvs(pvsnode &p, int storage = -1)
671 {
672 if(!p.children)
673 {
674 outbuf.add(0xFF);
675 loopi(8) outbuf.add(p.flags&PVS_HIDE_BB ? 0xFF : 0);
676 return true;
677 }
678 int index = outbuf.length();
679 pvsnode *children = &pvsnodes[p.children];
680 int i = 0;
681 uchar leafvalues = 0;
682 if(storage>=0)
683 {
684 for(; i < 8; i++)
685 {
686 pvsnode &child = children[i];
687 if(child.flags&PVS_HIDE_BB) leafvalues |= 1<<i;
688 else if(child.children) break;
689 }
690 if(i==8) { outbuf[storage] = leafvalues; return false; }
691 // if offset won't fit, just mark the space as a visible to avoid problems
692 int offset = (index - storage + 8)/9;
693 if(offset>255) { outbuf[storage] = 0; return false; }
694 outbuf[storage] = uchar(offset);
695 }
696 outbuf.add(0);
697 loopj(8) outbuf.add(leafvalues&(1<<j) ? 0xFF : 0);
698 uchar leafmask = (1<<i)-1;
699 for(; i < 8; i++)
700 {
701 pvsnode &child = children[i];
702 if(child.children) { if(!serializepvs(child, index+1+i)) leafmask |= 1<<i; }
703 else { leafmask |= 1<<i; outbuf[index+1+i] = child.flags&PVS_HIDE_BB ? 0xFF : 0; }
704 }
705 outbuf[index] = leafmask;
706 return true;
707 }
708
materialoccludedpvsworker709 bool materialoccluded(pvsnode &p, const ivec &co, int size, const ivec &bbmin, const ivec &bbmax)
710 {
711 pvsnode *children = &pvsnodes[p.children];
712 loopoctabox(co, size, bbmin, bbmax)
713 {
714 ivec o(i, co, size);
715 if(children[i].flags & PVS_HIDE_BB) continue;
716 if(!children[i].children || !materialoccluded(children[i], o, size/2, bbmin, bbmax)) return false;
717 }
718 return true;
719 }
720
materialoccludedpvsworker721 bool materialoccluded(vector<materialsurface *> &matsurfs)
722 {
723 if(pvsnodes[0].flags & PVS_HIDE_BB) return true;
724 if(!pvsnodes[0].children) return false;
725 loopv(matsurfs)
726 {
727 materialsurface &m = *matsurfs[i];
728 ivec bbmin(m.o), bbmax(m.o);
729 int dim = dimension(m.orient);
730 bbmin[dim] += dimcoord(m.orient) ? -2 : 2;
731 bbmax[C[dim]] += m.csize;
732 bbmax[R[dim]] += m.rsize;
733 if(!materialoccluded(pvsnodes[0], ivec(0, 0, 0), hdr.worldsize/2, bbmin, bbmax)) return false;
734 }
735 return true;
736 }
737
738 int wateroccluded, waterbytes;
739
calcpvspvsworker740 void calcpvs(const ivec &co, int size)
741 {
742 loopk(3)
743 {
744 viewcellbb.min[k] = co[k];
745 viewcellbb.max[k] = co[k]+size;
746 }
747 memcpy(pvsnodes, origpvsnodes.getbuf(), origpvsnodes.length()*sizeof(pvsnode));
748 prevblockers.clear();
749 cullpvs(pvsnodes[0]);
750
751 wateroccluded = 0;
752 loopi(numwaterplanes)
753 {
754 if(waterplanes[i].height < 0)
755 {
756 if(waterfalls.length() && materialoccluded(waterfalls)) wateroccluded |= 1<<i;
757 }
758 else if(waterplanes[i].matsurfs.length() && materialoccluded(waterplanes[i].matsurfs)) wateroccluded |= 1<<i;
759 }
760 waterbytes = 0;
761 loopi(4) if(wateroccluded&(0xFF<<(i*8))) waterbytes = i+1;
762
763 compresspvs(pvsnodes[0], hdr.worldsize, pvsleafsize);
764 outbuf.setsize(0);
765 serializepvs(pvsnodes[0]);
766 }
767
testviewcellpvsworker768 uchar *testviewcell(const ivec &co, int size, int *waterpvs = NULL, int *len = NULL)
769 {
770 calcpvs(co, size);
771
772 uchar *buf = new uchar[outbuf.length()];
773 memcpy(buf, outbuf.getbuf(), outbuf.length());
774 if(waterpvs) *waterpvs = wateroccluded;
775 if(len) *len = outbuf.length();
776 return buf;
777 }
778
genviewcellpvsworker779 int genviewcell(const ivec &co, int size)
780 {
781 calcpvs(co, size);
782
783 if(pvsmutex) SDL_LockMutex(pvsmutex);
784 numviewcells++;
785 pvsdata key(pvsbuf.length(), waterbytes + outbuf.length());
786 loopi(waterbytes) pvsbuf.add((wateroccluded>>(i*8))&0xFF);
787 pvsbuf.put(outbuf.getbuf(), outbuf.length());
788 int *val = pvscompress.access(key);
789 if(val) pvsbuf.setsize(key.offset);
790 else
791 {
792 val = &pvscompress[key];
793 *val = pvs.length();
794 pvs.add(key);
795 }
796 if(pvsmutex) SDL_UnlockMutex(pvsmutex);
797 return *val;
798 }
799
runpvsworker800 static int run(void *data)
801 {
802 pvsworker *w = (pvsworker *)data;
803 SDL_LockMutex(viewcellmutex);
804 while(viewcellrequests.length())
805 {
806 viewcellrequest req = viewcellrequests.pop();
807 SDL_UnlockMutex(viewcellmutex);
808 int result = w->genviewcell(req.o, req.size);
809 SDL_LockMutex(viewcellmutex);
810 *req.result = result;
811 }
812 SDL_UnlockMutex(viewcellmutex);
813 return 0;
814 }
815 };
816
817 struct viewcellnode
818 {
819 uchar leafmask;
820 union viewcellchild
821 {
822 int pvs;
823 viewcellnode *node;
824 } children[8];
825
viewcellnodeviewcellnode826 viewcellnode() : leafmask(0xFF)
827 {
828 loopi(8) children[i].pvs = -1;
829 }
~viewcellnodeviewcellnode830 ~viewcellnode()
831 {
832 loopi(8) if(!(leafmask&(1<<i))) delete children[i].node;
833 }
834 };
835
836 VAR(IDF_PERSIST, pvsthreads, 0, 0, 16);
837 static vector<pvsworker *> pvsworkers;
838
839 static volatile bool check_genpvs_progress = false;
840
genpvs_timer(Uint32 interval,void * param)841 static Uint32 genpvs_timer(Uint32 interval, void *param)
842 {
843 check_genpvs_progress = true;
844 return interval;
845 }
846
847 static int totalviewcells = 0;
848
show_genpvs_progress(int unique=pvs.length (),int processed=numviewcells)849 static void show_genpvs_progress(int unique = pvs.length(), int processed = numviewcells)
850 {
851 float bar1 = float(processed) / float(totalviewcells>0 ? totalviewcells : 1);
852
853 defformatstring(text1, "%d of %d view cells (%d unique)", processed, totalviewcells, unique);
854
855 progress(bar1, text1);
856
857 if(interceptkey(SDLK_ESCAPE)) genpvs_canceled = true;
858 check_genpvs_progress = false;
859 }
860
861 static shaftbb pvsbounds;
862
calcpvsbounds()863 static void calcpvsbounds()
864 {
865 loopk(3) pvsbounds.min[k] = USHRT_MAX;
866 loopk(3) pvsbounds.max[k] = 0;
867 loopv(valist)
868 {
869 vtxarray *va = valist[i];
870 loopk(3)
871 {
872 if(va->geommin[k]>va->geommax[k]) continue;
873 pvsbounds.min[k] = min(pvsbounds.min[k], (ushort)va->geommin[k]);
874 pvsbounds.max[k] = max(pvsbounds.max[k], (ushort)va->geommax[k]);
875 }
876 }
877 }
878
isallclip(cube * c)879 static inline bool isallclip(cube *c)
880 {
881 loopi(8)
882 {
883 cube &h = c[i];
884 if(h.children ? !isallclip(h.children) : (!isentirelysolid(h) && (h.material&MATF_CLIP)!=MAT_CLIP))
885 return false;
886 }
887 return true;
888 }
889
countviewcells(cube * c,const ivec & co,int size,int threshold)890 static int countviewcells(cube *c, const ivec &co, int size, int threshold)
891 {
892 int count = 0;
893 loopi(8)
894 {
895 ivec o(i, co, size);
896 if(pvsbounds.outside(o, size)) continue;
897 cube &h = c[i];
898 if(h.children)
899 {
900 if(size>threshold)
901 {
902 count += countviewcells(h.children, o, size>>1, threshold);
903 continue;
904 }
905 if(isallclip(h.children)) continue;
906 }
907 else if(isentirelysolid(h) || (h.material&MATF_CLIP)==MAT_CLIP) continue;
908 count++;
909 }
910 return count;
911 }
912
genviewcells(viewcellnode & p,cube * c,const ivec & co,int size,int threshold)913 static void genviewcells(viewcellnode &p, cube *c, const ivec &co, int size, int threshold)
914 {
915 if(genpvs_canceled) return;
916 loopi(8)
917 {
918 ivec o(i, co, size);
919 if(pvsbounds.outside(o, size)) continue;
920 cube &h = c[i];
921 if(h.children)
922 {
923 if(size>threshold)
924 {
925 p.leafmask &= ~(1<<i);
926 p.children[i].node = new viewcellnode;
927 genviewcells(*p.children[i].node, h.children, o, size>>1, threshold);
928 continue;
929 }
930 if(isallclip(h.children)) continue;
931 }
932 else if(isentirelysolid(h) || (h.material&MATF_CLIP)==MAT_CLIP) continue;
933 if(pvsworkers.length())
934 {
935 if(genpvs_canceled) return;
936 p.children[i].pvs = pvsworkers[0]->genviewcell(o, size);
937 if(check_genpvs_progress) show_genpvs_progress();
938 }
939 else
940 {
941 viewcellrequest &req = viewcellrequests.add();
942 req.result = &p.children[i].pvs;
943 req.o = o;
944 req.size = size;
945 }
946 }
947 }
948
949 static viewcellnode *viewcells = NULL;
950 static int lockedwaterplanes[MAXWATERPVS];
951 static uchar *curpvs = NULL, *lockedpvs = NULL;
952 static int curwaterpvs = 0, lockedwaterpvs = 0;
953
lookupviewcell(const vec & p)954 static inline pvsdata *lookupviewcell(const vec &p)
955 {
956 uint x = uint(floor(p.x)), y = uint(floor(p.y)), z = uint(floor(p.z));
957 if(!viewcells || (x|y|z)>=uint(hdr.worldsize)) return NULL;
958 viewcellnode *vc = viewcells;
959 for(int scale = worldscale-1; scale>=0; scale--)
960 {
961 int i = octastep(x, y, z, scale);
962 if(vc->leafmask&(1<<i))
963 {
964 return vc->children[i].pvs>=0 ? &pvs[vc->children[i].pvs] : NULL;
965 }
966 vc = vc->children[i].node;
967 }
968 return NULL;
969 }
970
lockpvs_(bool lock)971 static void lockpvs_(bool lock)
972 {
973 if(lockedpvs) DELETEA(lockedpvs);
974 if(!lock) return;
975 pvsdata *d = lookupviewcell(camera1->o);
976 if(!d) return;
977 int wbytes = d->len%9, len = d->len - wbytes;
978 lockedpvs = new uchar[len];
979 memcpy(lockedpvs, &pvsbuf[d->offset + wbytes], len);
980 lockedwaterpvs = 0;
981 loopi(wbytes) lockedwaterpvs |= pvsbuf[d->offset + i] << (i*8);
982 loopi(MAXWATERPVS) lockedwaterplanes[i] = waterplanes[i].height;
983 conoutf("\fglocked view cell at %.1f, %.1f, %.1f", camera1->o.x, camera1->o.y, camera1->o.z);
984 }
985
986 VARF(0, lockpvs, 0, 0, 1, lockpvs_(lockpvs!=0));
987
988 VARN(0, pvs, usepvs, 0, 1, 1);
989 VARN(0, waterpvs, usewaterpvs, 0, 1, 1);
990
setviewcell(const vec & p)991 void setviewcell(const vec &p)
992 {
993 if(!usepvs) curpvs = NULL;
994 else if(lockedpvs)
995 {
996 curpvs = lockedpvs;
997 curwaterpvs = lockedwaterpvs;
998 }
999 else
1000 {
1001 pvsdata *d = lookupviewcell(p);
1002 curpvs = d ? &pvsbuf[d->offset] : NULL;
1003 curwaterpvs = 0;
1004 if(d)
1005 {
1006 loopi(d->len%9) curwaterpvs |= *curpvs++ << (i*8);
1007 }
1008 }
1009 if(!usepvs || !usewaterpvs) curwaterpvs = 0;
1010 }
1011
clearpvs()1012 void clearpvs()
1013 {
1014 DELETEP(viewcells);
1015 pvs.setsize(0);
1016 pvsbuf.setsize(0);
1017 curpvs = NULL;
1018 numwaterplanes = 0;
1019 lockpvs = 0;
1020 lockpvs_(false);
1021 }
1022
1023 COMMAND(0, clearpvs, "");
1024
findwaterplanes()1025 static void findwaterplanes()
1026 {
1027 loopi(MAXWATERPVS)
1028 {
1029 waterplanes[i].height = -1;
1030 waterplanes[i].matsurfs.setsize(0);
1031 }
1032 waterfalls.setsize(0);
1033 numwaterplanes = 0;
1034 loopv(valist)
1035 {
1036 vtxarray *va = valist[i];
1037 loopj(va->matsurfs)
1038 {
1039 materialsurface &m = va->matbuf[j];
1040 if((m.material&MATF_VOLUME)!=MAT_WATER || m.orient==O_BOTTOM) { j += m.skip; continue; }
1041 if(m.orient!=O_TOP)
1042 {
1043 waterfalls.add(&m);
1044 continue;
1045 }
1046 loopk(numwaterplanes) if(waterplanes[k].height == m.o.z)
1047 {
1048 waterplanes[k].matsurfs.add(&m);
1049 goto nextmatsurf;
1050 }
1051 if(numwaterplanes < MAXWATERPVS)
1052 {
1053 waterplanes[numwaterplanes].height = m.o.z;
1054 waterplanes[numwaterplanes].matsurfs.add(&m);
1055 numwaterplanes++;
1056 }
1057 nextmatsurf:;
1058 }
1059 }
1060 if(waterfalls.length() > 0 && numwaterplanes < MAXWATERPVS) numwaterplanes++;
1061 }
1062
testpvs(int * vcsize)1063 void testpvs(int *vcsize)
1064 {
1065 lockpvs_(false);
1066
1067 uint oldnumwaterplanes = numwaterplanes;
1068 int oldwaterplanes[MAXWATERPVS];
1069 loopi(numwaterplanes) oldwaterplanes[i] = waterplanes[i].height;
1070
1071 findwaterplanes();
1072
1073 pvsnode &root = origpvsnodes.add();
1074 memset(root.edges.v, 0xFF, 3);
1075 root.flags = 0;
1076 root.children = 0;
1077 genpvsnodes(worldroot);
1078
1079 genpvs_canceled = false;
1080 check_genpvs_progress = false;
1081
1082 int size = *vcsize>0 ? *vcsize : 32;
1083 for(int mask = 1; mask < size; mask <<= 1) size &= ~mask;
1084
1085 ivec o = ivec(camera1->o).mask(~(size-1));
1086 pvsworker w;
1087 int len;
1088 lockedpvs = w.testviewcell(o, size, &lockedwaterpvs, &len);
1089 loopi(MAXWATERPVS) lockedwaterplanes[i] = waterplanes[i].height;
1090 lockpvs = 1;
1091 conoutf("\fggenerated test view cell of size %d at %.1f, %.1f, %.1f (%d B)", size, camera1->o.x, camera1->o.y, camera1->o.z, len);
1092
1093 origpvsnodes.setsize(0);
1094 numwaterplanes = oldnumwaterplanes;
1095 loopi(numwaterplanes) waterplanes[i].height = oldwaterplanes[i];
1096 }
1097
1098 COMMAND(0, testpvs, "i");
1099
genpvs(int * viewcellsize)1100 void genpvs(int *viewcellsize)
1101 {
1102 if(hdr.worldsize > 1<<15)
1103 {
1104 conoutf("\frmap is too large for PVS");
1105 return;
1106 }
1107
1108 progress(0, "generating PVS");
1109 genpvs_canceled = false;
1110 Uint32 start = SDL_GetTicks();
1111 progress(0, "finding view cells");
1112
1113 clearpvs();
1114 calcpvsbounds();
1115 findwaterplanes();
1116
1117 pvsnode &root = origpvsnodes.add();
1118 memset(root.edges.v, 0xFF, 3);
1119 root.flags = 0;
1120 root.children = 0;
1121 genpvsnodes(worldroot);
1122
1123 totalviewcells = countviewcells(worldroot, ivec(0, 0, 0), hdr.worldsize>>1, *viewcellsize>0 ? *viewcellsize : 32);
1124 numviewcells = 0;
1125 genpvs_canceled = false;
1126 check_genpvs_progress = false;
1127 SDL_TimerID timer = 0;
1128 int numthreads = pvsthreads > 0 ? pvsthreads : numcpus;
1129 if(numthreads<=1)
1130 {
1131 pvsworkers.add(new pvsworker);
1132 timer = SDL_AddTimer(500, genpvs_timer, NULL);
1133 }
1134 viewcells = new viewcellnode;
1135 genviewcells(*viewcells, worldroot, ivec(0, 0, 0), hdr.worldsize>>1, *viewcellsize>0 ? *viewcellsize : 32);
1136 if(numthreads<=1)
1137 {
1138 SDL_RemoveTimer(timer);
1139 }
1140 else
1141 {
1142 progress(0, "creating threads");
1143 if(!pvsmutex) pvsmutex = SDL_CreateMutex();
1144 if(!viewcellmutex) viewcellmutex = SDL_CreateMutex();
1145 loopi(numthreads)
1146 {
1147 pvsworker *w = pvsworkers.add(new pvsworker);
1148 w->thread = SDL_CreateThread(pvsworker::run, "pvs worker", w);
1149 }
1150 show_genpvs_progress(0, 0);
1151 while(!genpvs_canceled)
1152 {
1153 SDL_Delay(500);
1154 SDL_LockMutex(viewcellmutex);
1155 int unique = pvs.length(), processed = numviewcells, remaining = viewcellrequests.length();
1156 SDL_UnlockMutex(viewcellmutex);
1157 show_genpvs_progress(unique, processed);
1158 if(!remaining) break;
1159 }
1160 SDL_LockMutex(viewcellmutex);
1161 viewcellrequests.setsize(0);
1162 SDL_UnlockMutex(viewcellmutex);
1163 loopv(pvsworkers) SDL_WaitThread(pvsworkers[i]->thread, NULL);
1164 }
1165 pvsworkers.deletecontents();
1166
1167 origpvsnodes.setsize(0);
1168 pvscompress.clear();
1169
1170 Uint32 end = SDL_GetTicks();
1171 if(genpvs_canceled)
1172 {
1173 clearpvs();
1174 conoutf("\frgenpvs aborted");
1175 }
1176 else conoutf("\fggenerated %d unique view cells totaling %.1f kB and averaging %d B (%.1f seconds)",
1177 pvs.length(), pvsbuf.length()/1024.0f, pvsbuf.length()/max(pvs.length(), 1), (end - start) / 1000.0f);
1178 }
1179
1180 COMMAND(0, genpvs, "i");
1181
pvsstats()1182 void pvsstats()
1183 {
1184 conoutf("\fa%d unique view cells totaling %.1f kB and averaging %d B",
1185 pvs.length(), pvsbuf.length()/1024.0f, pvsbuf.length()/max(pvs.length(), 1));
1186 }
1187
1188 COMMAND(0, pvsstats, "");
1189
pvsoccluded(uchar * buf,const ivec & co,int size,const ivec & bbmin,const ivec & bbmax)1190 static inline bool pvsoccluded(uchar *buf, const ivec &co, int size, const ivec &bbmin, const ivec &bbmax)
1191 {
1192 uchar leafmask = buf[0];
1193 loopoctabox(co, size, bbmin, bbmax)
1194 {
1195 ivec o(i, co, size);
1196 if(leafmask&(1<<i))
1197 {
1198 uchar leafvalues = buf[1+i];
1199 if(!leafvalues || (leafvalues!=0xFF && octaboxoverlap(o, size>>1, bbmin, bbmax)&~leafvalues))
1200 return false;
1201 }
1202 else if(!pvsoccluded(buf+9*buf[1+i], o, size>>1, bbmin, bbmax)) return false;
1203 }
1204 return true;
1205 }
1206
pvsoccluded(uchar * buf,const ivec & bbmin,const ivec & bbmax)1207 static inline bool pvsoccluded(uchar *buf, const ivec &bbmin, const ivec &bbmax)
1208 {
1209 int diff = (bbmin.x^bbmax.x) | (bbmin.y^bbmax.y) | (bbmin.z^bbmax.z);
1210 if(diff&~((1<<worldscale)-1)) return false;
1211 int scale = worldscale-1;
1212 while(!(diff&(1<<scale)))
1213 {
1214 int i = octastep(bbmin.x, bbmin.y, bbmin.z, scale);
1215 scale--;
1216 uchar leafmask = buf[0];
1217 if(leafmask&(1<<i))
1218 {
1219 uchar leafvalues = buf[1+i];
1220 return leafvalues && (leafvalues==0xFF || !(octaboxoverlap(ivec(bbmin).mask(~((2<<scale)-1)), 1<<scale, bbmin, bbmax)&~leafvalues));
1221 }
1222 buf += 9*buf[1+i];
1223 }
1224 return pvsoccluded(buf, ivec(bbmin).mask(~((2<<scale)-1)), 1<<scale, bbmin, bbmax);
1225 }
1226
pvsoccluded(const ivec & bbmin,const ivec & bbmax)1227 bool pvsoccluded(const ivec &bbmin, const ivec &bbmax)
1228 {
1229 return curpvs!=NULL && pvsoccluded(curpvs, bbmin, bbmax);
1230 }
1231
pvsoccludedsphere(const vec & center,float radius)1232 bool pvsoccludedsphere(const vec ¢er, float radius)
1233 {
1234 if(curpvs==NULL) return false;
1235 ivec bbmin(vec(center).sub(radius)), bbmax(vec(center).add(radius+1));
1236 return pvsoccluded(curpvs, bbmin, bbmax);
1237 }
1238
waterpvsoccluded(int height)1239 bool waterpvsoccluded(int height)
1240 {
1241 if(!curwaterpvs) return false;
1242 if(lockedpvs)
1243 {
1244 loopi(MAXWATERPVS) if(lockedwaterplanes[i]==height) return (curwaterpvs&(1<<i))!=0;
1245 }
1246 else
1247 {
1248 loopi(numwaterplanes) if(waterplanes[i].height==height) return (curwaterpvs&(1<<i))!=0;
1249 }
1250 return false;
1251 }
1252
saveviewcells(stream * f,viewcellnode & p)1253 void saveviewcells(stream *f, viewcellnode &p)
1254 {
1255 f->putchar(p.leafmask);
1256 loopi(8)
1257 {
1258 if(p.leafmask&(1<<i)) f->putlil<int>(p.children[i].pvs);
1259 else saveviewcells(f, *p.children[i].node);
1260 }
1261 }
1262
savepvs(stream * f)1263 void savepvs(stream *f)
1264 {
1265 uint totallen = pvsbuf.length() | (numwaterplanes>0 ? 0x80000000U : 0);
1266 f->putlil<uint>(totallen);
1267 if(numwaterplanes>0)
1268 {
1269 f->putlil<uint>(numwaterplanes);
1270 loopi(numwaterplanes)
1271 {
1272 f->putlil<int>(waterplanes[i].height);
1273 if(waterplanes[i].height < 0) break;
1274 }
1275 }
1276 loopv(pvs) f->putlil<ushort>(pvs[i].len);
1277 f->write(pvsbuf.getbuf(), pvsbuf.length());
1278 saveviewcells(f, *viewcells);
1279 }
1280
loadviewcells(stream * f)1281 viewcellnode *loadviewcells(stream *f)
1282 {
1283 viewcellnode *p = new viewcellnode;
1284 p->leafmask = f->getchar();
1285 loopi(8)
1286 {
1287 if(p->leafmask&(1<<i)) p->children[i].pvs = f->getlil<int>();
1288 else p->children[i].node = loadviewcells(f);
1289 }
1290 return p;
1291 }
1292
loadpvs(stream * f)1293 void loadpvs(stream *f)
1294 {
1295 uint totallen = f->getlil<uint>();
1296 if(totallen & 0x80000000U)
1297 {
1298 totallen &= ~0x80000000U;
1299 numwaterplanes = f->getlil<uint>();
1300 loopi(numwaterplanes) waterplanes[i].height = f->getlil<int>();
1301 }
1302 int offset = 0;
1303 loopi(hdr.numpvs)
1304 {
1305 ushort len = f->getlil<ushort>();
1306 pvs.add(pvsdata(offset, len));
1307 offset += len;
1308 }
1309 f->read(pvsbuf.reserve(totallen).buf, totallen);
1310 pvsbuf.advance(totallen);
1311 viewcells = loadviewcells(f);
1312 }
1313
getnumviewcells()1314 int getnumviewcells() { return pvs.length(); }
1315
1316