1 #include "engine.h"
2
3 enum
4 {
5 PVS_HIDE_GEOM = 1<<0,
6 PVS_HIDE_BB = 1<<1
7 };
8
9 struct pvsnode
10 {
11 bvec edges;
12 uchar flags;
13 uint children;
14 };
15
16 static vector<pvsnode> origpvsnodes;
17
mergepvsnodes(pvsnode & p,pvsnode * children)18 static bool mergepvsnodes(pvsnode &p, pvsnode *children)
19 {
20 loopi(7) if(children[i].flags!=children[7].flags) return false;
21 bvec bbs[4];
22 loop(x, 2) loop(y, 2)
23 {
24 const bvec &lo = children[octaindex(2, x, y, 0)].edges,
25 &hi = children[octaindex(2, x, y, 1)].edges;
26 if(lo.x!=0xFF && (lo.x&0x11 || lo.y&0x11 || lo.z&0x11)) return false;
27 if(hi.x!=0xFF && (hi.x&0x11 || hi.y&0x11 || hi.z&0x11)) return false;
28
29 #define MERGEBBS(res, coord, row, col) \
30 if(lo.coord==0xFF) \
31 { \
32 if(hi.coord!=0xFF) \
33 { \
34 res.coord = ((hi.coord&~0x11)>>1) + 0x44; \
35 res.row = hi.row; \
36 res.col = hi.col; \
37 } \
38 } \
39 else if(hi.coord==0xFF) \
40 { \
41 res.coord = (lo.coord&0xEE)>>1; \
42 res.row = lo.row; \
43 res.col = lo.col; \
44 } \
45 else if(lo.row!=hi.row || lo.col!=hi.col || (lo.coord&0xF0)!=0x80 || (hi.coord&0xF)!=0) return false; \
46 else \
47 { \
48 res.coord = ((lo.coord&~0xF1)>>1) | (((hi.coord&~0x1F)>>1) + 0x40); \
49 res.row = lo.row; \
50 res.col = lo.col; \
51 }
52
53 bvec &res = bbs[x + 2*y];
54 MERGEBBS(res, z, x, y);
55 res.x = lo.x;
56 res.y = lo.y;
57 }
58 loop(x, 2)
59 {
60 bvec &lo = bbs[x], &hi = bbs[x+2];
61 MERGEBBS(lo, y, x, z);
62 }
63 bvec &lo = bbs[0], &hi = bbs[1];
64 MERGEBBS(p.edges, x, y, z);
65
66 return true;
67 }
68
genpvsnodes(cube * c,int parent=0,const ivec & co=ivec (0,0,0),int size=worldsize/2)69 static void genpvsnodes(cube *c, int parent = 0, const ivec &co = ivec(0, 0, 0), int size = worldsize/2)
70 {
71 int index = origpvsnodes.length();
72 loopi(8)
73 {
74 ivec o(i, co, size);
75 pvsnode &n = origpvsnodes.add();
76 n.flags = 0;
77 n.children = 0;
78 if(c[i].children || isempty(c[i]) || c[i].material&MAT_ALPHA) memset(n.edges.v, 0xFF, 3);
79 else loopk(3)
80 {
81 uint face = c[i].faces[k];
82 if(face==F_SOLID) n.edges[k] = 0x80;
83 else
84 {
85 uchar low = max(max(face&0xF, (face>>8)&0xF), max((face>>16)&0xF, (face>>24)&0xF)),
86 high = min(min((face>>4)&0xF, (face>>12)&0xF), min((face>>20)&0xF, (face>>28)&0xF));
87 if(size<8)
88 {
89 if(low&((8/size)-1)) { low += 8/size - (low&((8/size)-1)); }
90 if(high&((8/size)-1)) high &= ~(8/size-1);
91 }
92 if(low >= high) { memset(n.edges.v, 0xFF, 3); break; }
93 n.edges[k] = low | (high<<4);
94 }
95 }
96 }
97 int branches = 0;
98 loopi(8) if(c[i].children)
99 {
100 ivec o(i, co, size);
101 genpvsnodes(c[i].children, index+i, o, size>>1);
102 if(origpvsnodes[index+i].children) branches++;
103 }
104 if(!branches && mergepvsnodes(origpvsnodes[parent], &origpvsnodes[index])) origpvsnodes.setsize(index);
105 else origpvsnodes[parent].children = index;
106 }
107
108 struct shaftplane
109 {
110 float r, c, offset;
111 uchar rnear, cnear, rfar, cfar;
112 };
113
114 struct shaftbb
115 {
116 union
117 {
118 ushort v[6];
119 struct { usvec min, max; };
120 };
121
shaftbbshaftbb122 shaftbb() {}
shaftbbshaftbb123 shaftbb(const ivec &o, int size)
124 {
125 min.x = o.x;
126 min.y = o.y;
127 min.z = o.z;
128 max.x = o.x + size;
129 max.y = o.y + size;
130 max.z = o.z + size;
131 }
shaftbbshaftbb132 shaftbb(const ivec &o, int size, const bvec &edges)
133 {
134 min.x = o.x + (size*(edges.x&0xF))/8;
135 min.y = o.y + (size*(edges.y&0xF))/8;
136 min.z = o.z + (size*(edges.z&0xF))/8;
137 max.x = o.x + (size*(edges.x>>4))/8;
138 max.y = o.y + (size*(edges.y>>4))/8;
139 max.z = o.z + (size*(edges.z>>4))/8;
140 }
141
operator []shaftbb142 ushort &operator[](int i) { return v[i]; }
operator []shaftbb143 ushort operator[](int i) const { return v[i]; }
144
containsshaftbb145 bool contains(const shaftbb &o) const
146 {
147 return min.x<=o.min.x && min.y<=o.min.y && min.z<=o.min.z &&
148 max.x>=o.max.x && max.y>=o.max.y && max.z>=o.max.z;
149 }
150
outsideshaftbb151 bool outside(const ivec &o, int size) const
152 {
153 return o.x>=max.x || o.y>=max.y || o.z>=max.z ||
154 o.x+size<=min.x || o.y+size<=min.y || o.z+size<=min.z;
155 }
156
outsideshaftbb157 bool outside(const shaftbb &o) const
158 {
159 return o.min.x>max.x || o.min.y>max.y || o.min.z>max.z ||
160 o.max.x<min.x || o.max.y<min.y || o.max.z<min.z;
161 }
162
notinsideshaftbb163 bool notinside(const shaftbb &o) const
164 {
165 return o.min.x<min.x || o.min.y<min.y || o.min.z<min.z ||
166 o.max.x>max.x || o.max.y>max.y || o.max.z>max.z;
167 }
168 };
169
170 struct shaft
171 {
172 shaftbb bounds;
173 shaftplane planes[8];
174 int numplanes;
175
shaftshaft176 shaft(const shaftbb &from, const shaftbb &to)
177 {
178 calcshaft(from, to);
179 }
180
calcshaftshaft181 void calcshaft(const shaftbb &from, const shaftbb &to)
182 {
183 uchar match = 0, color = 0;
184 loopi(3)
185 {
186 if(to.min[i] < from.min[i]) { color |= 1<<i; bounds.min[i] = 0; }
187 else if(to.min[i] > from.min[i]) bounds.min[i] = to.min[i]+1;
188 else { match |= 1<<i; bounds.min[i] = to.min[i]; }
189
190 if(to.max[i] > from.max[i]) { color |= 8<<i; bounds.max[i] = USHRT_MAX; }
191 else if(to.max[i] < from.max[i]) bounds.max[i] = to.max[i]-1;
192 else { match |= 8<<i; bounds.max[i] = to.max[i]; }
193 }
194 numplanes = 0;
195 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)
196 {
197 int r = i%3, c = j%3, d = (r+1)%3;
198 if(d==c) d = (c+1)%3;
199 shaftplane &p = planes[numplanes++];
200 p.r = from[j] - to[j];
201 if(i<3 ? p.r >= 0 : p.r < 0)
202 {
203 p.r = -p.r;
204 p.c = from[i] - to[i];
205 }
206 else p.c = to[i] - from[i];
207 p.offset = -(from[i]*p.r + from[j]*p.c);
208 p.rnear = p.r >= 0 ? r : 3+r;
209 p.cnear = p.c >= 0 ? c : 3+c;
210 p.rfar = p.r < 0 ? r : 3+r;
211 p.cfar = p.c < 0 ? c : 3+c;
212 }
213 }
214
outsideshaft215 bool outside(const shaftbb &o) const
216 {
217 if(bounds.outside(o)) return true;
218
219 for(const shaftplane *p = planes; p < &planes[numplanes]; p++)
220 {
221 if(o[p->rnear]*p->r + o[p->cnear]*p->c + p->offset > 0) return true;
222 }
223 return false;
224 }
225
insideshaft226 bool inside(const shaftbb &o) const
227 {
228 if(bounds.notinside(o)) return false;
229
230 for(const shaftplane *p = planes; p < &planes[numplanes]; p++)
231 {
232 if(o[p->rfar]*p->r + o[p->cfar]*p->c + p->offset > 0) return false;
233 }
234 return true;
235 }
236 };
237
238 struct pvsdata
239 {
240 int offset, len;
241
pvsdatapvsdata242 pvsdata() {}
pvsdatapvsdata243 pvsdata(int offset, int len) : offset(offset), len(len) {}
244 };
245
246 static vector<uchar> pvsbuf;
247
hthash(const pvsdata & k)248 static inline uint hthash(const pvsdata &k)
249 {
250 uint h = 5381;
251 loopi(k.len) h = ((h<<5)+h)^pvsbuf[k.offset+i];
252 return h;
253 }
254
htcmp(const pvsdata & x,const pvsdata & y)255 static inline bool htcmp(const pvsdata &x, const pvsdata &y)
256 {
257 return x.len==y.len && !memcmp(&pvsbuf[x.offset], &pvsbuf[y.offset], x.len);
258 }
259
260 static SDL_mutex *pvsmutex = NULL;
261 static hashtable<pvsdata, int> pvscompress;
262 static vector<pvsdata> pvs;
263
264 static SDL_mutex *viewcellmutex = NULL;
265 struct viewcellrequest
266 {
267 int *result;
268 ivec o;
269 int size;
270 };
271 static vector<viewcellrequest> viewcellrequests;
272
273 static bool genpvs_canceled = false;
274 static int numviewcells = 0;
275
276 VAR(maxpvsblocker, 1, 512, 1<<16);
277 VAR(pvsleafsize, 1, 64, 1024);
278
279 #define MAXWATERPVS 32
280
281 static struct
282 {
283 int height;
284 vector<materialsurface *> matsurfs;
285 } waterplanes[MAXWATERPVS];
286 static vector<materialsurface *> waterfalls;
287 uint numwaterplanes = 0;
288
289 struct pvsworker
290 {
pvsworkerpvsworker291 pvsworker() : thread(NULL), pvsnodes(new pvsnode[origpvsnodes.length()])
292 {
293 }
~pvsworkerpvsworker294 ~pvsworker()
295 {
296 delete[] pvsnodes;
297 }
298
299 SDL_Thread *thread;
300 pvsnode *pvsnodes;
301
302 shaftbb viewcellbb;
303
304 pvsnode *levels[32];
305 int curlevel;
306 ivec origin;
307
resetlevelspvsworker308 void resetlevels()
309 {
310 curlevel = worldscale;
311 levels[curlevel] = &pvsnodes[0];
312 origin = ivec(0, 0, 0);
313 }
314
hasvoxelpvsworker315 int hasvoxel(const ivec &p, int coord, int dir, int ocoord = 0, int odir = 0, int *omin = NULL)
316 {
317 uint diff = (origin.x^p.x)|(origin.y^p.y)|(origin.z^p.z);
318 if(diff >= uint(worldsize)) return 0;
319 diff >>= curlevel;
320 while(diff)
321 {
322 curlevel++;
323 diff >>= 1;
324 }
325
326 pvsnode *cur = levels[curlevel];
327 while(cur->children && !(cur->flags&PVS_HIDE_BB))
328 {
329 cur = &pvsnodes[cur->children];
330 curlevel--;
331 cur += ((p.z>>(curlevel-2))&4) | ((p.y>>(curlevel-1))&2) | ((p.x>>curlevel)&1);
332 levels[curlevel] = cur;
333 }
334
335 origin = ivec(p.x&(~0<<curlevel), p.y&(~0<<curlevel), p.z&(~0<<curlevel));
336
337 if(cur->flags&PVS_HIDE_BB || cur->edges==bvec(0x80, 0x80, 0x80))
338 {
339 if(omin)
340 {
341 int step = origin[ocoord] + (odir<<curlevel) - p[ocoord] + odir - 1;
342 if(odir ? step < *omin : step > *omin) *omin = step;
343 }
344 return origin[coord] + (dir<<curlevel) - p[coord] + dir - 1;
345 }
346
347 if(cur->edges.x==0xFF) return 0;
348 ivec bbp(p);
349 bbp.sub(origin);
350 ivec bbmin, bbmax;
351 bbmin.x = ((cur->edges.x&0xF)<<curlevel)/8;
352 if(bbp.x < bbmin.x) return 0;
353 bbmax.x = ((cur->edges.x>>4)<<curlevel)/8;
354 if(bbp.x >= bbmax.x) return 0;
355 bbmin.y = ((cur->edges.y&0xF)<<curlevel)/8;
356 if(bbp.y < bbmin.y) return 0;
357 bbmax.y = ((cur->edges.y>>4)<<curlevel)/8;
358 if(bbp.y >= bbmax.y) return 0;
359 bbmin.z = ((cur->edges.z&0xF)<<curlevel)/8;
360 if(bbp.z < bbmin.z) return 0;
361 bbmax.z = ((cur->edges.z>>4)<<curlevel)/8;
362 if(bbp.z >= bbmax.z) return 0;
363
364 if(omin)
365 {
366 int step = (odir ? bbmax[ocoord] : bbmin[ocoord]) - bbp[ocoord] + (odir - 1);
367 if(odir ? step < *omin : step > *omin) *omin = step;
368 }
369 return (dir ? bbmax[coord] : bbmin[coord]) - bbp[coord] + (dir - 1);
370 }
371
hidepvspvsworker372 void hidepvs(pvsnode &p)
373 {
374 if(p.children)
375 {
376 pvsnode *children = &pvsnodes[p.children];
377 loopi(8) hidepvs(children[i]);
378 p.flags |= PVS_HIDE_BB;
379 return;
380 }
381 p.flags |= PVS_HIDE_BB;
382 if(p.edges.x!=0xFF) p.flags |= PVS_HIDE_GEOM;
383 }
384
shaftcullpvspvsworker385 void shaftcullpvs(shaft &s, pvsnode &p, const ivec &co = ivec(0, 0, 0), int size = worldsize)
386 {
387 if(p.flags&PVS_HIDE_BB) return;
388 shaftbb bb(co, size);
389 if(s.outside(bb)) return;
390 if(s.inside(bb)) { hidepvs(p); return; }
391 if(p.children)
392 {
393 pvsnode *children = &pvsnodes[p.children];
394 uchar flags = 0xFF;
395 loopi(8)
396 {
397 ivec o(i, co, size>>1);
398 shaftcullpvs(s, children[i], o, size>>1);
399 flags &= children[i].flags;
400 }
401 if(flags & PVS_HIDE_BB) p.flags |= PVS_HIDE_BB;
402 return;
403 }
404 if(p.edges.x==0xFF) return;
405 shaftbb geom(co, size, p.edges);
406 if(s.inside(geom)) p.flags |= PVS_HIDE_GEOM;
407 }
408
409 queue<shaftbb, 32> prevblockers;
410
411 struct cullorder
412 {
413 int index, dist;
414
cullorderpvsworker::cullorder415 cullorder() {}
cullorderpvsworker::cullorder416 cullorder(int index, int dist) : index(index), dist(dist) {}
417 };
418
cullpvspvsworker419 void cullpvs(pvsnode &p, const ivec &co = ivec(0, 0, 0), int size = worldsize)
420 {
421 if(p.flags&(PVS_HIDE_BB | PVS_HIDE_GEOM) || genpvs_canceled) return;
422 if(p.children && !(p.flags&PVS_HIDE_BB))
423 {
424 pvsnode *children = &pvsnodes[p.children];
425 int csize = size>>1;
426 ivec dmin = ivec(co).add(csize>>1).sub(ivec(viewcellbb.min).add(ivec(viewcellbb.max)).shr(1)), dmax = ivec(dmin).add(csize);
427 dmin.mul(dmin);
428 dmax.mul(dmax);
429 ivec diff = ivec(dmax).sub(dmin);
430 cullorder order[8];
431 int dir = 0;
432 if(diff.x < 0) { diff.x = -diff.x; dir |= 1; }
433 if(diff.y < 0) { diff.y = -diff.y; dir |= 2; }
434 if(diff.z < 0) { diff.z = -diff.z; dir |= 4; }
435 order[0] = cullorder(0, 0);
436 order[7] = cullorder(7, diff.x + diff.y + diff.z);
437 order[1] = cullorder(1, diff.x);
438 order[2] = cullorder(2, diff.y);
439 order[3] = cullorder(4, diff.z);
440 if(order[2].dist < order[1].dist) swap(order[1], order[2]);
441 if(order[3].dist < order[2].dist) swap(order[2], order[3]);
442 if(order[2].dist < order[1].dist) swap(order[1], order[2]);
443 cullorder dxy(order[1].index|order[2].index, order[1].dist+order[2].dist),
444 dxz(order[1].index|order[3].index, order[1].dist+order[3].dist),
445 dyz(order[2].index|order[3].index, order[2].dist+order[3].dist);
446 int j;
447 for(j = 4; j > 0 && dxy.dist < order[j-1].dist; --j) order[j] = order[j-1]; order[j] = dxy;
448 for(j = 5; j > 0 && dxz.dist < order[j-1].dist; --j) order[j] = order[j-1]; order[j] = dxz;
449 for(j = 6; j > 0 && dyz.dist < order[j-1].dist; --j) order[j] = order[j-1]; order[j] = dyz;
450 loopi(8)
451 {
452 int index = order[i].index^dir;
453 ivec o(index, co, csize);
454 cullpvs(children[index], o, csize);
455 }
456 if(!(p.flags & PVS_HIDE_BB)) return;
457 }
458 bvec edges = p.children ? bvec(0x80, 0x80, 0x80) : p.edges;
459 if(edges.x==0xFF) return;
460 shaftbb geom(co, size, edges);
461 ivec diff = ivec(geom.max).sub(ivec(viewcellbb.min)).abs();
462 cullorder order[3] = { cullorder(0, diff.x), cullorder(1, diff.y), cullorder(2, diff.z) };
463 if(order[1].dist > order[0].dist) swap(order[0], order[1]);
464 if(order[2].dist > order[1].dist) swap(order[1], order[2]);
465 if(order[1].dist > order[0].dist) swap(order[0], order[1]);
466 loopi(6)
467 {
468 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];
469 int ccenter = geom.min[c];
470 if(geom.min[r]==geom.max[r] || geom.min[c]==geom.max[c]) continue;
471 while(ccenter < geom.max[c])
472 {
473 ivec rmin;
474 rmin[dim] = geom[dim + 3*dc] + (dc ? -1 : 0);
475 rmin[r] = geom.min[r];
476 rmin[c] = ccenter;
477 ivec rmax = rmin;
478 rmax[r] = geom.max[r] - 1;
479 int rcenter = (rmin[r] + rmax[r])/2;
480 resetlevels();
481 for(int minstep = -1, maxstep = 1; (minstep || maxstep) && rmax[r] - rmin[r] < maxpvsblocker;)
482 {
483 if(minstep) minstep = hasvoxel(rmin, r, 0);
484 if(maxstep) maxstep = hasvoxel(rmax, r, 1);
485 rmin[r] += minstep;
486 rmax[r] += maxstep;
487 }
488 rmin[r] = rcenter + (rmin[r] - rcenter)/2;
489 rmax[r] = rcenter + (rmax[r] - rcenter)/2;
490 if(rmin[r]>=geom.min[r] && rmax[r]<geom.max[r]) { rmin[r] = geom.min[r]; rmax[r] = geom.max[r] - 1; }
491 ivec cmin = rmin, cmax = rmin;
492 if(rmin[r]>=geom.min[r] && rmax[r]<geom.max[r])
493 {
494 cmin[c] = geom.min[c];
495 cmax[c] = geom.max[c]-1;
496 }
497 int cminstep = -1, cmaxstep = 1;
498 for(; (cminstep || cmaxstep) && cmax[c] - cmin[c] < maxpvsblocker;)
499 {
500 if(cminstep)
501 {
502 cmin[c] += cminstep; cminstep = INT_MIN;
503 cmin[r] = rmin[r];
504 resetlevels();
505 for(int rstep = 1; rstep && cmin[r] <= rmax[r];)
506 {
507 rstep = hasvoxel(cmin, r, 1, c, 0, &cminstep);
508 cmin[r] += rstep;
509 }
510 if(cmin[r] <= rmax[r]) cminstep = 0;
511 }
512 if(cmaxstep)
513 {
514 cmax[c] += cmaxstep; cmaxstep = INT_MAX;
515 cmax[r] = rmin[r];
516 resetlevels();
517 for(int rstep = 1; rstep && cmax[r] <= rmax[r];)
518 {
519 rstep = hasvoxel(cmax, r, 1, c, 1, &cmaxstep);
520 cmax[r] += rstep;
521 }
522 if(cmax[r] <= rmax[r]) cmaxstep = 0;
523 }
524 }
525 if(!cminstep) cmin[c]++;
526 if(!cmaxstep) cmax[c]--;
527 ivec emin = rmin, emax = rmax;
528 if(cmin[c]>=geom.min[c] && cmax[c]<geom.max[c])
529 {
530 if(emin[r]>geom.min[r]) emin[r] = geom.min[r];
531 if(emax[r]<geom.max[r]-1) emax[r] = geom.max[r]-1;
532 }
533 int rminstep = -1, rmaxstep = 1;
534 for(; (rminstep || rmaxstep) && emax[r] - emin[r] < maxpvsblocker;)
535 {
536 if(rminstep)
537 {
538 emin[r] += -1; rminstep = INT_MIN;
539 emin[c] = cmin[c];
540 resetlevels();
541 for(int cstep = 1; cstep && emin[c] <= cmax[c];)
542 {
543 cstep = hasvoxel(emin, c, 1, r, 0, &rminstep);
544 emin[c] += cstep;
545 }
546 if(emin[c] <= cmax[c]) rminstep = 0;
547 }
548 if(rmaxstep)
549 {
550 emax[r] += 1; rmaxstep = INT_MAX;
551 emax[c] = cmin[c];
552 resetlevels();
553 for(int cstep = 1; cstep && emax[c] <= cmax[c];)
554 {
555 cstep = hasvoxel(emax, c, 1, r, 1, &rmaxstep);
556 emax[c] += cstep;
557 }
558 if(emax[c] <= cmax[c]) rmaxstep = 0;
559 }
560 }
561 if(!rminstep) emin[r]++;
562 if(!rmaxstep) emax[r]--;
563 shaftbb bb;
564 bb.min[dim] = rmin[dim];
565 bb.max[dim] = rmin[dim]+1;
566 bb.min[r] = emin[r];
567 bb.max[r] = emax[r]+1;
568 bb.min[c] = cmin[c];
569 bb.max[c] = cmax[c]+1;
570 if(bb.min[dim] >= viewcellbb.max[dim] || bb.max[dim] <= viewcellbb.min[dim])
571 {
572 int ddir = bb.min[dim] >= viewcellbb.max[dim] ? 1 : -1,
573 dval = ddir>0 ? USHRT_MAX-1 : 0,
574 dlimit = maxpvsblocker,
575 numsides = 0;
576 loopj(4)
577 {
578 ivec dmax;
579 int odim = j < 2 ? c : r;
580 if(j&1)
581 {
582 if(bb.max[odim] >= viewcellbb.max[odim]) continue;
583 dmax[odim] = bb.max[odim]-1;
584 }
585 else
586 {
587 if(bb.min[odim] <= viewcellbb.min[odim]) continue;
588 dmax[odim] = bb.min[odim];
589 }
590 numsides++;
591 dmax[dim] = bb.min[dim];
592 int stepdim = j < 2 ? r : c, stepstart = bb.min[stepdim], stepend = bb.max[stepdim];
593 int dstep = ddir;
594 for(; dstep && ddir*(dmax[dim] - (int)bb.min[dim]) < dlimit;)
595 {
596 dmax[dim] += dstep; dstep = ddir > 0 ? INT_MAX : INT_MIN;
597 dmax[stepdim] = stepstart;
598 resetlevels();
599 for(int step = 1; step && dmax[stepdim] < stepend;)
600 {
601 step = hasvoxel(dmax, stepdim, 1, dim, (ddir+1)/2, &dstep);
602 dmax[stepdim] += step;
603 }
604 if(dmax[stepdim] < stepend) dstep = 0;
605 }
606 dlimit = min(dlimit, ddir*(dmax[dim] - (int)bb.min[dim]));
607 if(!dstep) dmax[dim] -= ddir;
608 if(ddir>0) dval = min(dval, dmax[dim]);
609 else dval = max(dval, dmax[dim]);
610 }
611 if(numsides>0)
612 {
613 if(ddir>0) bb.max[dim] = dval+1;
614 else bb.min[dim] = dval;
615 }
616 //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);
617 }
618 bool dup = false;
619 loopvj(prevblockers)
620 {
621 if(prevblockers[j].contains(bb)) { dup = true; break; }
622 }
623 if(!dup)
624 {
625 shaft s(viewcellbb, bb);
626 shaftcullpvs(s, pvsnodes[0]);
627 prevblockers.add(bb);
628 }
629 if(bb.contains(geom)) return;
630 ccenter = cmax[c] + 1;
631 }
632 }
633 }
634
compresspvspvsworker635 bool compresspvs(pvsnode &p, int size, int threshold)
636 {
637 if(!p.children) return true;
638 if(p.flags&PVS_HIDE_BB) { p.children = 0; return true; }
639 pvsnode *children = &pvsnodes[p.children];
640 bool canreduce = true;
641 loopi(8)
642 {
643 if(!compresspvs(children[i], size/2, threshold)) canreduce = false;
644 }
645 if(canreduce)
646 {
647 int hide = children[7].flags&PVS_HIDE_BB;
648 loopi(7) if((children[i].flags&PVS_HIDE_BB)!=hide) canreduce = false;
649 if(canreduce)
650 {
651 p.flags = (p.flags & ~PVS_HIDE_BB) | hide;
652 p.children = 0;
653 return true;
654 }
655 }
656 if(size <= threshold)
657 {
658 p.children = 0;
659 return true;
660 }
661 return false;
662 }
663
664 vector<uchar> outbuf;
665
serializepvspvsworker666 bool serializepvs(pvsnode &p, int storage = -1)
667 {
668 if(!p.children)
669 {
670 outbuf.add(0xFF);
671 loopi(8) outbuf.add(p.flags&PVS_HIDE_BB ? 0xFF : 0);
672 return true;
673 }
674 int index = outbuf.length();
675 pvsnode *children = &pvsnodes[p.children];
676 int i = 0;
677 uchar leafvalues = 0;
678 if(storage>=0)
679 {
680 for(; i < 8; i++)
681 {
682 pvsnode &child = children[i];
683 if(child.flags&PVS_HIDE_BB) leafvalues |= 1<<i;
684 else if(child.children) break;
685 }
686 if(i==8) { outbuf[storage] = leafvalues; return false; }
687 // if offset won't fit, just mark the space as a visible to avoid problems
688 int offset = (index - storage + 8)/9;
689 if(offset>255) { outbuf[storage] = 0; return false; }
690 outbuf[storage] = uchar(offset);
691 }
692 outbuf.add(0);
693 loopj(8) outbuf.add(leafvalues&(1<<j) ? 0xFF : 0);
694 uchar leafmask = (1<<i)-1;
695 for(; i < 8; i++)
696 {
697 pvsnode &child = children[i];
698 if(child.children) { if(!serializepvs(child, index+1+i)) leafmask |= 1<<i; }
699 else { leafmask |= 1<<i; outbuf[index+1+i] = child.flags&PVS_HIDE_BB ? 0xFF : 0; }
700 }
701 outbuf[index] = leafmask;
702 return true;
703 }
704
materialoccludedpvsworker705 bool materialoccluded(pvsnode &p, const ivec &co, int size, const ivec &bbmin, const ivec &bbmax)
706 {
707 pvsnode *children = &pvsnodes[p.children];
708 loopoctabox(co, size, bbmin, bbmax)
709 {
710 ivec o(i, co, size);
711 if(children[i].flags & PVS_HIDE_BB) continue;
712 if(!children[i].children || !materialoccluded(children[i], o, size/2, bbmin, bbmax)) return false;
713 }
714 return true;
715 }
716
materialoccludedpvsworker717 bool materialoccluded(vector<materialsurface *> &matsurfs)
718 {
719 if(pvsnodes[0].flags & PVS_HIDE_BB) return true;
720 if(!pvsnodes[0].children) return false;
721 loopv(matsurfs)
722 {
723 materialsurface &m = *matsurfs[i];
724 ivec bbmin(m.o), bbmax(m.o);
725 int dim = dimension(m.orient);
726 bbmin[dim] += dimcoord(m.orient) ? -2 : 2;
727 bbmax[C[dim]] += m.csize;
728 bbmax[R[dim]] += m.rsize;
729 if(!materialoccluded(pvsnodes[0], vec(0, 0, 0), worldsize/2, bbmin, bbmax)) return false;
730 }
731 return true;
732 }
733
734 int wateroccluded, waterbytes;
735
calcpvspvsworker736 void calcpvs(const ivec &co, int size)
737 {
738 loopk(3)
739 {
740 viewcellbb.min[k] = co[k];
741 viewcellbb.max[k] = co[k]+size;
742 }
743 memcpy(pvsnodes, origpvsnodes.getbuf(), origpvsnodes.length()*sizeof(pvsnode));
744 prevblockers.clear();
745 cullpvs(pvsnodes[0]);
746
747 wateroccluded = 0;
748 loopi(numwaterplanes)
749 {
750 if(waterplanes[i].height < 0)
751 {
752 if(waterfalls.length() && materialoccluded(waterfalls)) wateroccluded |= 1<<i;
753 }
754 else if(waterplanes[i].matsurfs.length() && materialoccluded(waterplanes[i].matsurfs)) wateroccluded |= 1<<i;
755 }
756 waterbytes = 0;
757 loopi(4) if(wateroccluded&(0xFF<<(i*8))) waterbytes = i+1;
758
759 compresspvs(pvsnodes[0], worldsize, pvsleafsize);
760 outbuf.setsize(0);
761 serializepvs(pvsnodes[0]);
762 }
763
testviewcellpvsworker764 uchar *testviewcell(const ivec &co, int size, int *waterpvs = NULL, int *len = NULL)
765 {
766 calcpvs(co, size);
767
768 uchar *buf = new uchar[outbuf.length()];
769 memcpy(buf, outbuf.getbuf(), outbuf.length());
770 if(waterpvs) *waterpvs = wateroccluded;
771 if(len) *len = outbuf.length();
772 return buf;
773 }
774
genviewcellpvsworker775 int genviewcell(const ivec &co, int size)
776 {
777 calcpvs(co, size);
778
779 if(pvsmutex) SDL_LockMutex(pvsmutex);
780 numviewcells++;
781 pvsdata key(pvsbuf.length(), waterbytes + outbuf.length());
782 loopi(waterbytes) pvsbuf.add((wateroccluded>>(i*8))&0xFF);
783 pvsbuf.put(outbuf.getbuf(), outbuf.length());
784 int *val = pvscompress.access(key);
785 if(val) pvsbuf.setsize(key.offset);
786 else
787 {
788 val = &pvscompress[key];
789 *val = pvs.length();
790 pvs.add(key);
791 }
792 if(pvsmutex) SDL_UnlockMutex(pvsmutex);
793 return *val;
794 }
795
runpvsworker796 static int run(void *data)
797 {
798 pvsworker *w = (pvsworker *)data;
799 SDL_LockMutex(viewcellmutex);
800 while(viewcellrequests.length())
801 {
802 viewcellrequest req = viewcellrequests.pop();
803 SDL_UnlockMutex(viewcellmutex);
804 int result = w->genviewcell(req.o, req.size);
805 SDL_LockMutex(viewcellmutex);
806 *req.result = result;
807 }
808 SDL_UnlockMutex(viewcellmutex);
809 return 0;
810 }
811 };
812
813 struct viewcellnode
814 {
815 uchar leafmask;
816 union viewcellchild
817 {
818 int pvs;
819 viewcellnode *node;
820 } children[8];
821
viewcellnodeviewcellnode822 viewcellnode() : leafmask(0xFF)
823 {
824 loopi(8) children[i].pvs = -1;
825 }
~viewcellnodeviewcellnode826 ~viewcellnode()
827 {
828 loopi(8) if(!(leafmask&(1<<i))) delete children[i].node;
829 }
830 };
831
832 VARP(pvsthreads, 0, 0, 16);
833 static vector<pvsworker *> pvsworkers;
834
835 static volatile bool check_genpvs_progress = false;
836
genpvs_timer(Uint32 interval,void * param)837 static Uint32 genpvs_timer(Uint32 interval, void *param)
838 {
839 check_genpvs_progress = true;
840 return interval;
841 }
842
843 static int totalviewcells = 0;
844
show_genpvs_progress(int unique=pvs.length (),int processed=numviewcells)845 static void show_genpvs_progress(int unique = pvs.length(), int processed = numviewcells)
846 {
847 float bar1 = float(processed) / float(totalviewcells>0 ? totalviewcells : 1);
848
849 defformatstring(text1, "%d%% - %d of %d view cells (%d unique)", int(bar1 * 100), processed, totalviewcells, unique);
850
851 renderprogress(bar1, text1);
852
853 if(interceptkey(SDLK_ESCAPE)) genpvs_canceled = true;
854 check_genpvs_progress = false;
855 }
856
857 static shaftbb pvsbounds;
858
calcpvsbounds()859 static void calcpvsbounds()
860 {
861 loopk(3) pvsbounds.min[k] = USHRT_MAX;
862 loopk(3) pvsbounds.max[k] = 0;
863 extern vector<vtxarray *> valist;
864 loopv(valist)
865 {
866 vtxarray *va = valist[i];
867 loopk(3)
868 {
869 if(va->geommin[k]>va->geommax[k]) continue;
870 pvsbounds.min[k] = min(pvsbounds.min[k], (ushort)va->geommin[k]);
871 pvsbounds.max[k] = max(pvsbounds.max[k], (ushort)va->geommax[k]);
872 }
873 }
874 }
875
isallclip(cube * c)876 static inline bool isallclip(cube *c)
877 {
878 loopi(8)
879 {
880 cube &h = c[i];
881 if(h.children ? !isallclip(h.children) : (!isentirelysolid(h) && (h.material&MATF_CLIP)!=MAT_CLIP))
882 return false;
883 }
884 return true;
885 }
886
countviewcells(cube * c,const ivec & co,int size,int threshold)887 static int countviewcells(cube *c, const ivec &co, int size, int threshold)
888 {
889 int count = 0;
890 loopi(8)
891 {
892 ivec o(i, co, size);
893 if(pvsbounds.outside(o, size)) continue;
894 cube &h = c[i];
895 if(h.children)
896 {
897 if(size>threshold)
898 {
899 count += countviewcells(h.children, o, size>>1, threshold);
900 continue;
901 }
902 if(isallclip(h.children)) continue;
903 }
904 else if(isentirelysolid(h) || (h.material&MATF_CLIP)==MAT_CLIP) continue;
905 count++;
906 }
907 return count;
908 }
909
genviewcells(viewcellnode & p,cube * c,const ivec & co,int size,int threshold)910 static void genviewcells(viewcellnode &p, cube *c, const ivec &co, int size, int threshold)
911 {
912 if(genpvs_canceled) return;
913 loopi(8)
914 {
915 ivec o(i, co, size);
916 if(pvsbounds.outside(o, size)) continue;
917 cube &h = c[i];
918 if(h.children)
919 {
920 if(size>threshold)
921 {
922 p.leafmask &= ~(1<<i);
923 p.children[i].node = new viewcellnode;
924 genviewcells(*p.children[i].node, h.children, o, size>>1, threshold);
925 continue;
926 }
927 if(isallclip(h.children)) continue;
928 }
929 else if(isentirelysolid(h) || (h.material&MATF_CLIP)==MAT_CLIP) continue;
930 if(pvsworkers.length())
931 {
932 if(genpvs_canceled) return;
933 p.children[i].pvs = pvsworkers[0]->genviewcell(o, size);
934 if(check_genpvs_progress) show_genpvs_progress();
935 }
936 else
937 {
938 viewcellrequest &req = viewcellrequests.add();
939 req.result = &p.children[i].pvs;
940 req.o = o;
941 req.size = size;
942 }
943 }
944 }
945
946 static viewcellnode *viewcells = NULL;
947 static int lockedwaterplanes[MAXWATERPVS];
948 static uchar *curpvs = NULL, *lockedpvs = NULL;
949 static int curwaterpvs = 0, lockedwaterpvs = 0;
950
lookupviewcell(const vec & p)951 static inline pvsdata *lookupviewcell(const vec &p)
952 {
953 uint x = uint(floor(p.x)), y = uint(floor(p.y)), z = uint(floor(p.z));
954 if(!viewcells || (x|y|z)>=uint(worldsize)) return NULL;
955 viewcellnode *vc = viewcells;
956 for(int scale = worldscale-1; scale>=0; scale--)
957 {
958 int i = octastep(x, y, z, scale);
959 if(vc->leafmask&(1<<i))
960 {
961 return vc->children[i].pvs>=0 ? &pvs[vc->children[i].pvs] : NULL;
962 }
963 vc = vc->children[i].node;
964 }
965 return NULL;
966 }
967
lockpvs_(bool lock)968 static void lockpvs_(bool lock)
969 {
970 if(lockedpvs) DELETEA(lockedpvs);
971 if(!lock) return;
972 pvsdata *d = lookupviewcell(camera1->o);
973 if(!d) return;
974 int wbytes = d->len%9, len = d->len - wbytes;
975 lockedpvs = new uchar[len];
976 memcpy(lockedpvs, &pvsbuf[d->offset + wbytes], len);
977 lockedwaterpvs = 0;
978 loopi(wbytes) lockedwaterpvs |= pvsbuf[d->offset + i] << (i*8);
979 loopi(MAXWATERPVS) lockedwaterplanes[i] = waterplanes[i].height;
980 conoutf("locked view cell at %.1f, %.1f, %.1f", camera1->o.x, camera1->o.y, camera1->o.z);
981 }
982
983 VARF(lockpvs, 0, 0, 1, lockpvs_(lockpvs!=0));
984
985 VARN(pvs, usepvs, 0, 1, 1);
986 VARN(waterpvs, usewaterpvs, 0, 1, 1);
987
setviewcell(const vec & p)988 void setviewcell(const vec &p)
989 {
990 if(!usepvs) curpvs = NULL;
991 else if(lockedpvs)
992 {
993 curpvs = lockedpvs;
994 curwaterpvs = lockedwaterpvs;
995 }
996 else
997 {
998 pvsdata *d = lookupviewcell(p);
999 curpvs = d ? &pvsbuf[d->offset] : NULL;
1000 curwaterpvs = 0;
1001 if(d)
1002 {
1003 loopi(d->len%9) curwaterpvs |= *curpvs++ << (i*8);
1004 }
1005 }
1006 if(!usepvs || !usewaterpvs) curwaterpvs = 0;
1007 }
1008
clearpvs()1009 void clearpvs()
1010 {
1011 DELETEP(viewcells);
1012 pvs.setsize(0);
1013 pvsbuf.setsize(0);
1014 curpvs = NULL;
1015 numwaterplanes = 0;
1016 lockpvs = 0;
1017 lockpvs_(false);
1018 }
1019
1020 COMMAND(clearpvs, "");
1021
findwaterplanes()1022 static void findwaterplanes()
1023 {
1024 extern vector<vtxarray *> valist;
1025 loopi(MAXWATERPVS)
1026 {
1027 waterplanes[i].height = -1;
1028 waterplanes[i].matsurfs.setsize(0);
1029 }
1030 waterfalls.setsize(0);
1031 numwaterplanes = 0;
1032 loopv(valist)
1033 {
1034 vtxarray *va = valist[i];
1035 loopj(va->matsurfs)
1036 {
1037 materialsurface &m = va->matbuf[j];
1038 if((m.material&MATF_VOLUME)!=MAT_WATER || m.orient==O_BOTTOM) { j += m.skip; continue; }
1039 if(m.orient!=O_TOP)
1040 {
1041 waterfalls.add(&m);
1042 continue;
1043 }
1044 loopk(numwaterplanes) if(waterplanes[k].height == m.o.z)
1045 {
1046 waterplanes[k].matsurfs.add(&m);
1047 goto nextmatsurf;
1048 }
1049 if(numwaterplanes < MAXWATERPVS)
1050 {
1051 waterplanes[numwaterplanes].height = m.o.z;
1052 waterplanes[numwaterplanes].matsurfs.add(&m);
1053 numwaterplanes++;
1054 }
1055 nextmatsurf:;
1056 }
1057 }
1058 if(waterfalls.length() > 0 && numwaterplanes < MAXWATERPVS) numwaterplanes++;
1059 }
1060
testpvs(int * vcsize)1061 void testpvs(int *vcsize)
1062 {
1063 lockpvs_(false);
1064
1065 uint oldnumwaterplanes = numwaterplanes;
1066 int oldwaterplanes[MAXWATERPVS];
1067 loopi(numwaterplanes) oldwaterplanes[i] = waterplanes[i].height;
1068
1069 findwaterplanes();
1070
1071 pvsnode &root = origpvsnodes.add();
1072 memset(root.edges.v, 0xFF, 3);
1073 root.flags = 0;
1074 root.children = 0;
1075 genpvsnodes(worldroot);
1076
1077 genpvs_canceled = false;
1078 check_genpvs_progress = false;
1079
1080 int size = *vcsize>0 ? *vcsize : 32;
1081 for(int mask = 1; mask < size; mask <<= 1) size &= ~mask;
1082
1083 ivec o = camera1->o;
1084 o.mask(~(size-1));
1085 pvsworker w;
1086 int len;
1087 lockedpvs = w.testviewcell(o, size, &lockedwaterpvs, &len);
1088 loopi(MAXWATERPVS) lockedwaterplanes[i] = waterplanes[i].height;
1089 lockpvs = 1;
1090 conoutf("generated test view cell of size %d at %.1f, %.1f, %.1f (%d B)", size, camera1->o.x, camera1->o.y, camera1->o.z, len);
1091
1092 origpvsnodes.setsize(0);
1093 numwaterplanes = oldnumwaterplanes;
1094 loopi(numwaterplanes) waterplanes[i].height = oldwaterplanes[i];
1095 }
1096
1097 COMMAND(testpvs, "i");
1098
genpvs(int * viewcellsize)1099 void genpvs(int *viewcellsize)
1100 {
1101 if(worldsize > 1<<15)
1102 {
1103 conoutf(CON_ERROR, "map is too large for PVS");
1104 return;
1105 }
1106
1107 renderbackground("generating PVS (esc to abort)");
1108 genpvs_canceled = false;
1109 Uint32 start = SDL_GetTicks();
1110
1111 renderprogress(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), 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), worldsize>>1, *viewcellsize>0 ? *viewcellsize : 32);
1136 if(numthreads<=1)
1137 {
1138 SDL_RemoveTimer(timer);
1139 }
1140 else
1141 {
1142 renderprogress(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("genpvs aborted");
1175 }
1176 else conoutf("generated %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(genpvs, "i");
1181
pvsstats()1182 void pvsstats()
1183 {
1184 conoutf("%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(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,int numpvs)1293 void loadpvs(stream *f, int numpvs)
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(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