Line data Source code
1 :
2 : ///////////////////////// ray - cube collision ///////////////////////////////////////////////
3 :
4 : //functions for finding where vectors hit world geometry on the octree
5 :
6 : /* Unlike vector geometry, finding collision with world surfaces has to interact with the
7 : * octree geometry. Octree geometry behaves differently for identifying collision due to
8 : * its recursive behavior, and as a result the algorithms for identifying collision with
9 : * the world looks different than other world geometry systems.
10 : *
11 : * Octree cube collision is necessary for physics (as players need to interact with the world geometry)
12 : * and for other world interaction by players (e.g. identifying where structure in the world is)
13 : */
14 : #include "../libprimis-headers/cube.h"
15 : #include "../../shared/geomexts.h"
16 :
17 : #include "bih.h"
18 : #include "entities.h"
19 : #include "octaworld.h"
20 : #include "raycube.h"
21 : #include "world/world.h"
22 :
23 : //internally relevant functionality
24 : namespace
25 : {
26 0 : clipplanes &getclipplanes(const cube &c, const ivec &o, int size)
27 : {
28 0 : clipplanes &p = rootworld.getclipbounds(c, o, size, c.visible&0x80 ? 2 : 0);
29 0 : if(p.visible&0x80)
30 : {
31 0 : genclipplanes(c, o, size, p, false, false);
32 : }
33 0 : return p;
34 : }
35 :
36 : //============================================================= INTERSECTBOX
37 :
38 0 : static bool intersectplanes(const clipplanes& p, const vec &v, const vec& ray, float &enterdist, float &exitdist, int &entry)
39 : {
40 0 : for(int i = 0; i < p.size; ++i)
41 : {
42 0 : float pdist = p.p[i].dist(v),
43 0 : facing = ray.dot(p.p[i]);
44 0 : if(facing < 0)
45 : {
46 0 : pdist /= -facing;
47 0 : if(pdist > enterdist)
48 : {
49 0 : if(pdist > exitdist)
50 : {
51 0 : return false;
52 : }
53 0 : enterdist = pdist;
54 0 : entry = i;
55 : }
56 : }
57 0 : else if(facing > 0)
58 : {
59 0 : pdist /= -facing;
60 0 : if(pdist < exitdist)
61 : {
62 0 : if(pdist < enterdist)
63 : {
64 0 : return false;
65 : }
66 0 : exitdist = pdist;
67 : }
68 : }
69 0 : else if(pdist > 0)
70 : {
71 0 : return false;
72 : }
73 : }
74 0 : return true;
75 : }
76 :
77 0 : static bool intersectbox(const clipplanes& p, const vec &v, const vec& ray, const vec& invray, float &enterdist, float &exitdist, int &entry)
78 : {
79 0 : for(int i = 0; i < 3; ++i)
80 : {
81 0 : if(ray[i])
82 : {
83 0 : float prad = std::fabs(p.r[i] * invray[i]),
84 0 : pdist = (p.o[i] - v[i]) * invray[i],
85 0 : pmin = pdist - prad,
86 0 : pmax = pdist + prad;
87 0 : if(pmin > enterdist)
88 : {
89 0 : if(pmin > exitdist)
90 : {
91 0 : return false;
92 : }
93 0 : enterdist = pmin;
94 0 : entry = i;
95 : }
96 0 : if(pmax < exitdist)
97 : {
98 0 : if(pmax < enterdist)
99 : {
100 0 : return false;
101 : }
102 0 : exitdist = pmax;
103 : }
104 : }
105 0 : else if(v[i] < p.o[i]-p.r[i] || v[i] > p.o[i]+p.r[i])
106 : {
107 0 : return false;
108 : }
109 : }
110 0 : return true;
111 : }
112 :
113 0 : bool raycubeintersect(const clipplanes &p, const vec &v, const vec &ray, const vec &invray, float maxdist, float &dist)
114 : {
115 0 : int entry = -1,
116 0 : bbentry = -1;
117 0 : float enterdist = -1e16f,
118 0 : exitdist = 1e16f;
119 0 : if(!intersectplanes(p, v, ray, enterdist, exitdist, entry))
120 : {
121 0 : return false;
122 : }
123 0 : if(!intersectbox(p, v, ray, invray, enterdist, exitdist, bbentry))
124 : {
125 0 : return false;
126 : }
127 0 : if(exitdist < 0)
128 : {
129 0 : return false;
130 : }
131 0 : dist = std::max(enterdist+0.1f, 0.0f);
132 0 : if(dist < maxdist)
133 : {
134 0 : if(bbentry>=0)
135 : {
136 0 : hitsurface = vec(0, 0, 0);
137 0 : hitsurface[bbentry] = ray[bbentry]>0 ? -1 : 1;
138 : }
139 : else
140 : {
141 0 : hitsurface = p.p[entry];
142 : }
143 : }
144 0 : return true;
145 : }
146 :
147 : float hitentdist;
148 : int hitent, hitorient;
149 :
150 0 : float disttoent(const octaentities *oc, const vec &o, const vec &ray, float radius, int mode, const extentity *t)
151 : {
152 0 : vec eo, es;
153 0 : int orient = -1;
154 0 : float dist = radius,
155 0 : f = 0.0f;
156 0 : const std::vector<extentity *> &ents = entities::getents();
157 : //=======ENT_SEL_INTERSECT ENT_INTERSECT
158 : #define ENT_INTERSECT(type, func) do { \
159 : for(size_t i = 0; i < oc->type.size(); i++) \
160 : { \
161 : extentity &e = *ents[oc->type[i]]; \
162 : if(!(e.flags&EntFlag_Octa) || &e==t) \
163 : { \
164 : continue; \
165 : } \
166 : func; \
167 : if(f < dist && f > 0 && vec(ray).mul(f).add(o).insidebb(oc->o, oc->size)) \
168 : { \
169 : hitentdist = dist = f; \
170 : hitent = oc->type[i]; \
171 : hitorient = orient; \
172 : } \
173 : } \
174 : } while(0)
175 :
176 0 : if((mode&Ray_Poly) == Ray_Poly)
177 : {
178 0 : ENT_INTERSECT(mapmodels,
179 : {
180 : if(!mmintersect(e, o, ray, radius, mode, f))
181 : {
182 : continue;
183 : }
184 : });
185 : }
186 :
187 : #define ENT_SEL_INTERSECT(type) ENT_INTERSECT(type, { \
188 : entselectionbox(e, eo, es); \
189 : if(!rayboxintersect(eo, es, o, ray, f, orient)) \
190 : { \
191 : continue; \
192 : } \
193 : })
194 :
195 0 : if((mode&Ray_Ents) == Ray_Ents)
196 : {
197 0 : ENT_SEL_INTERSECT(other);
198 0 : ENT_SEL_INTERSECT(mapmodels);
199 0 : ENT_SEL_INTERSECT(decals);
200 : }
201 :
202 0 : return dist;
203 : }
204 : #undef ENT_INTERSECT
205 : #undef ENT_SEL_INTERSECT
206 : //======================================
207 0 : float disttooutsideent(const vec &o, const vec &ray, float radius, const extentity *t)
208 : {
209 0 : vec eo, es;
210 : int orient;
211 0 : float dist = radius,
212 0 : f = 0.0f;
213 0 : const std::vector<extentity *> &ents = entities::getents();
214 0 : for(const int &i : outsideents)
215 : {
216 0 : const extentity &e = *ents[i];
217 0 : if(!(e.flags&EntFlag_Octa) || &e == t)
218 : {
219 0 : continue;
220 : }
221 0 : entselectionbox(e, eo, es);
222 0 : if(!rayboxintersect(eo, es, o, ray, f, orient))
223 : {
224 0 : continue;
225 : }
226 0 : if(f < dist && f > 0)
227 : {
228 0 : hitentdist = dist = f;
229 0 : hitent = outsideents[i];
230 0 : hitorient = orient;
231 : }
232 : }
233 0 : return dist;
234 : }
235 :
236 : // optimized shadow version
237 0 : float shadowent(const octaentities *oc, const vec &o, const vec &ray, float radius, int mode, const extentity *t)
238 : {
239 0 : float dist = radius,
240 0 : f = 0.0f;
241 0 : const std::vector<extentity *> &ents = entities::getents();
242 0 : for(const int &i : oc->mapmodels)
243 : {
244 0 : const extentity &e = *ents[i];
245 0 : if(!(e.flags&EntFlag_Octa) || &e==t)
246 : {
247 0 : continue;
248 : }
249 0 : if(!mmintersect(e, o, ray, radius, mode, f))
250 : {
251 0 : continue;
252 : }
253 0 : if(f > 0 && f < dist)
254 : {
255 0 : dist = f;
256 : }
257 : }
258 0 : return dist;
259 : }
260 : }
261 :
262 : //externally relevant functionality
263 0 : bool insideworld(const vec &o)
264 : {
265 0 : return o.x>=0 && o.x<rootworld.mapsize() && o.y>=0 && o.y<rootworld.mapsize() && o.z>=0 && o.z<rootworld.mapsize();
266 : }
267 :
268 0 : bool insideworld(const ivec &o)
269 : {
270 0 : return static_cast<uint>(o.x) < static_cast<uint>(rootworld.mapsize()) &&
271 0 : static_cast<uint>(o.y) < static_cast<uint>(rootworld.mapsize()) &&
272 0 : static_cast<uint>(o.z) < static_cast<uint>(rootworld.mapsize());
273 : }
274 :
275 : vec hitsurface;
276 :
277 : //will only change &outrad and &dist if not inside the world
278 : //true if outside world, false if inside
279 0 : bool cubeworld::checkinsideworld(const vec &invray, float radius, float &outrad, const vec &o, vec &v, const vec& ray, float &dist) const
280 : {
281 0 : if(!insideworld(o))
282 : {
283 0 : float disttoworld = 0,
284 0 : exitworld = 1e16f;
285 0 : for(int i = 0; i < 3; ++i)
286 : {
287 0 : float c = v[i];
288 0 : if(c<0 || c>=mapsize())
289 : {
290 0 : float d = ((invray[i]>0?0:mapsize())-c)*invray[i];
291 0 : if(d<0)
292 : {
293 0 : outrad = radius>0 ? radius :-1;
294 0 : return true;
295 : }
296 0 : disttoworld = std::max(disttoworld, 0.1f + d);
297 : }
298 0 : float e = ((invray[i]>0?mapsize():0)-c)*invray[i];
299 0 : exitworld = std::min(exitworld, e);
300 : }
301 0 : if(disttoworld > exitworld)
302 : {
303 0 : outrad = (radius>0?radius:-1);
304 0 : return true;
305 : }
306 0 : v.add(vec(ray).mul(disttoworld));
307 0 : dist += disttoworld;
308 : }
309 0 : return false;
310 : }
311 :
312 0 : static void findclosest(int &closest, int xval, int yval, int zval, const ivec &lsizemask, const vec &invray, const ivec &lo, const int &lshift, vec &v, float &dist, const vec& ray)
313 : {
314 0 : float dx = (lo.x+(lsizemask.x<<lshift)-v.x)*invray.x,
315 0 : dy = (lo.y+(lsizemask.y<<lshift)-v.y)*invray.y,
316 0 : dz = (lo.z+(lsizemask.z<<lshift)-v.z)*invray.z;
317 0 : float disttonext = dx;
318 0 : closest = xval;
319 0 : if(dy < disttonext)
320 : {
321 0 : disttonext = dy;
322 0 : closest = yval;
323 : }
324 0 : if(dz < disttonext)
325 : {
326 0 : disttonext = dz;
327 0 : closest = zval;
328 : }
329 0 : disttonext += 0.1f;
330 0 : v.add(vec(ray).mul(disttonext));
331 0 : dist += disttonext;
332 0 : }
333 :
334 0 : bool cubeworld::upoctree(const vec& v, int& x, int& y, int& z, const ivec& lo, int& lshift) const
335 : {
336 0 : x = static_cast<int>(v.x);
337 0 : y = static_cast<int>(v.y);
338 0 : z = static_cast<int>(v.z);
339 0 : uint diff = static_cast<uint>(lo.x^x)|static_cast<uint>(lo.y^y)|static_cast<uint>(lo.z^z);
340 0 : if(diff >= static_cast<uint>(mapsize()))
341 : {
342 0 : return true;
343 : }
344 0 : diff >>= lshift;
345 0 : if(!diff)
346 : {
347 0 : return true;
348 : }
349 : do
350 : {
351 0 : lshift++;
352 0 : diff >>= 1;
353 0 : } while(diff);
354 0 : return false;
355 : }
356 :
357 : //======================================================= DOWNOCTREE INITRAYCUBE
358 :
359 : #define DOWNOCTREE(disttoent, earlyexit) \
360 : cube *lc = r.levels[r.lshift]; \
361 : for(;;) \
362 : { \
363 : r.lshift--; \
364 : lc += OCTA_STEP(x, y, z, r.lshift); \
365 : if(lc->ext && lc->ext->ents && r.lshift < r.elvl) \
366 : { \
367 : float edist = disttoent(lc->ext->ents, o, ray, r.dent, mode, t); \
368 : if(edist < r.dent) \
369 : { \
370 : earlyexit return std::min(edist, r.dist); \
371 : r.elvl = r.lshift; \
372 : r.dent = std::min(r.dent, edist); \
373 : } \
374 : } \
375 : if(lc->children==nullptr) \
376 : { \
377 : break; \
378 : } \
379 : lc = &(*lc->children)[0]; \
380 : r.levels[r.lshift] = lc; \
381 : }
382 :
383 : //NOTE: levels[20] magically assumes mapscale <20
384 : #define INITRAYCUBE \
385 : float dist = 0, \
386 : dent = radius > 0 ? radius : 1e16f; \
387 : vec v(o), \
388 : invray(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f); \
389 : cube *levels[20]; \
390 : levels[worldscale] = &(*worldroot)[0]; \
391 : int lshift = worldscale, \
392 : elvl = mode&Ray_BB ? worldscale : 0; \
393 : ivec lsizemask(invray.x>0 ? 1 : 0, invray.y>0 ? 1 : 0, invray.z>0 ? 1 : 0);
394 :
395 : struct raycubeinfo
396 : {
397 : float dist,
398 : dent;
399 : vec v,
400 : invray;
401 : cube *levels[20];
402 : int lshift,
403 : elvl;
404 : ivec lsizemask;
405 :
406 0 : raycubeinfo(float radius, const vec &o, const vec &ray, int worldscale, int mode, cube *r)
407 0 : {
408 0 : dist = 0;
409 0 : dent = radius > 0 ? radius : 1e16f;
410 0 : v = o;
411 0 : invray = vec(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f);
412 0 : levels[worldscale] = r;
413 0 : lshift = worldscale;
414 0 : elvl = mode&Ray_BB ? worldscale : 0;
415 0 : lsizemask = ivec(invray.x>0 ? 1 : 0, invray.y>0 ? 1 : 0, invray.z>0 ? 1 : 0);
416 0 : }
417 : };
418 :
419 0 : float cubeworld::raycube(const vec &o, const vec &ray, float radius, int mode, int size, const extentity *t) const
420 : {
421 0 : if(ray.iszero())
422 : {
423 0 : return 0;
424 : }
425 0 : raycubeinfo r(radius, o, ray, worldscale, mode, &(*worldroot)[0]);
426 : //scope limiting brackets
427 : {
428 0 : float outrad = 0.f;
429 0 : if(checkinsideworld(r.invray, radius, outrad, o, r.v, ray, r.dist))
430 : {
431 0 : return outrad;
432 : }
433 : }
434 0 : int closest = -1,
435 0 : x = static_cast<int>(r.v.x),
436 0 : y = static_cast<int>(r.v.y),
437 0 : z = static_cast<int>(r.v.z);
438 : for(;;)
439 : {
440 0 : DOWNOCTREE(disttoent, if(mode&Ray_Shadow));
441 :
442 0 : int lsize = 1<<r.lshift;
443 :
444 0 : cube &c = *lc;
445 0 : if((r.dist>0 || !(mode&Ray_SkipFirst)) &&
446 0 : (((mode&Ray_ClipMat) && IS_CLIPPED(c.material&MatFlag_Volume)) ||
447 0 : ((mode&Ray_EditMat) && c.material != Mat_Air) ||
448 0 : (!(mode&Ray_Pass) && lsize==size && !(c.isempty())) ||
449 0 : c.issolid() ||
450 0 : r.dent < r.dist) &&
451 0 : (!(mode&Ray_ClipMat) || (c.material&MatFlag_Clip)!=Mat_NoClip))
452 : {
453 0 : if(r.dist < r.dent)
454 : {
455 0 : if(closest < 0)
456 : {
457 0 : float dx = ((x&(~0U<<r.lshift))+(r.invray.x>0 ? 0 : 1<<r.lshift)-r.v.x)*r.invray.x,
458 0 : dy = ((y&(~0U<<r.lshift))+(r.invray.y>0 ? 0 : 1<<r.lshift)-r.v.y)*r.invray.y,
459 0 : dz = ((z&(~0U<<r.lshift))+(r.invray.z>0 ? 0 : 1<<r.lshift)-r.v.z)*r.invray.z;
460 0 : closest = dx > dy ? (dx > dz ? 0 : 2) : (dy > dz ? 1 : 2);
461 : }
462 0 : hitsurface = vec(0, 0, 0);
463 0 : hitsurface[closest] = ray[closest]>0 ? -1 : 1;
464 0 : return r.dist;
465 : }
466 0 : return r.dent;
467 : }
468 :
469 0 : ivec lo(x&(~0U<<r.lshift),
470 0 : y&(~0U<<r.lshift),
471 0 : z&(~0U<<r.lshift));
472 :
473 0 : if(!(c.isempty()))
474 : {
475 0 : const clipplanes &p = getclipplanes(c, lo, lsize);
476 0 : float f = 0;
477 0 : if(raycubeintersect(p, r.v, ray, r.invray, r.dent-r.dist, f) && (r.dist+f>0 || !(mode&Ray_SkipFirst)) && (!(mode&Ray_ClipMat) || (c.material&MatFlag_Clip)!=Mat_NoClip))
478 : {
479 0 : return std::min(r.dent, r.dist+f);
480 : }
481 : }
482 0 : findclosest(closest, 0, 1, 2, r.lsizemask, r.invray, lo, r.lshift, r.v, r.dist, ray);
483 0 : if(radius>0 && r.dist>=radius)
484 : {
485 0 : return std::min(r.dent, r.dist);
486 : }
487 0 : if(upoctree(r.v, x, y, z, lo, r.lshift))
488 : {
489 0 : return std::min(r.dent, radius>0 ? radius : r.dist);
490 : }
491 0 : }
492 : }
493 :
494 : // optimized version for light shadowing... every cycle here counts!!!
495 0 : float cubeworld::shadowray(const vec &o, const vec &ray, float radius, int mode, const extentity *t)
496 : {
497 0 : raycubeinfo r(radius, o, ray, worldscale, mode, &(*worldroot)[0]);
498 : //scope limiting brackets
499 : {
500 0 : float outrad = 0.f;
501 0 : if(checkinsideworld(r.invray, radius, outrad, o, r.v, ray, r.dist))
502 : {
503 0 : return outrad;
504 : }
505 : }
506 0 : int side = Orient_Bottom,
507 0 : x = static_cast<int>(r.v.x),
508 0 : y = static_cast<int>(r.v.y),
509 0 : z = static_cast<int>(r.v.z);
510 : for(;;)
511 : {
512 0 : DOWNOCTREE(shadowent, );
513 :
514 0 : const cube &c = *lc;
515 0 : ivec lo(x&(~0U<<r.lshift),
516 0 : y&(~0U<<r.lshift),
517 0 : z&(~0U<<r.lshift));
518 :
519 0 : if(!(c.isempty()) && !(c.material&Mat_Alpha))
520 : {
521 0 : if(c.issolid())
522 : {
523 0 : return c.texture[side]==Default_Sky && mode&Ray_SkipSky ? radius : r.dist;
524 : }
525 0 : const clipplanes &p = getclipplanes(c, lo, 1<<r.lshift);
526 0 : float enterdist = -1e16f,
527 0 : exitdist = 1e16f;
528 0 : int i = 0;
529 0 : bool intersected = intersectplanes(p, r.v, ray, enterdist, exitdist, i);
530 0 : side = p.side[i];
531 0 : if(!intersected)
532 : {
533 0 : goto nextcube;
534 : }
535 0 : intersected = intersectbox(p, r.v, ray, r.invray, enterdist, exitdist, i);
536 0 : side = (i<<1) + 1 - r.lsizemask[i];
537 0 : if(!intersected)
538 : {
539 0 : goto nextcube;
540 : }
541 0 : if(exitdist >= 0)
542 : {
543 0 : return c.texture[side]==Default_Sky && mode&Ray_SkipSky ? radius : r.dist+std::max(enterdist+0.1f, 0.0f);
544 : }
545 : }
546 :
547 0 : nextcube:
548 0 : findclosest(side, Orient_Right - r.lsizemask.x, Orient_Front - r.lsizemask.y, Orient_Top - r.lsizemask.z, r.lsizemask, r.invray, lo, r.lshift, r.v, r.dist, ray);
549 0 : if(r.dist>=radius)
550 : {
551 0 : return r.dist;
552 : }
553 0 : if(upoctree(r.v, x, y, z, lo, r.lshift))
554 : {
555 0 : return radius;
556 : }
557 0 : }
558 : }
559 : #undef DOWNOCTREE
560 : //==============================================================================
561 0 : float rayent(const vec &o, const vec &ray, float radius, int mode, int size, int &orient, int &ent)
562 : {
563 0 : hitent = -1;
564 0 : hitentdist = radius;
565 0 : hitorient = -1;
566 0 : float dist = rootworld.raycube(o, ray, radius, mode, size);
567 0 : if((mode&Ray_Ents) == Ray_Ents)
568 : {
569 0 : float dent = disttooutsideent(o, ray, dist < 0 ? 1e16f : dist, nullptr);
570 0 : if(dent < 1e15f && (dist < 0 || dent < dist))
571 : {
572 0 : dist = dent;
573 : }
574 : }
575 0 : orient = hitorient;
576 0 : ent = hitentdist == dist ? hitent : -1;
577 0 : return dist;
578 : }
579 :
580 0 : float raycubepos(const vec &o, const vec &ray, vec &hitpos, float radius, int mode, int size)
581 : {
582 0 : hitpos = ray;
583 0 : float dist = rootworld.raycube(o, ray, radius, mode, size);
584 0 : if(radius>0 && dist>=radius)
585 : {
586 0 : dist = radius;
587 : }
588 0 : hitpos.mul(dist).add(o);
589 0 : return dist;
590 : }
591 :
592 0 : bool raycubelos(const vec &o, const vec &dest, vec &hitpos)
593 : {
594 0 : vec ray(dest);
595 0 : ray.sub(o);
596 0 : float mag = ray.magnitude();
597 0 : ray.mul(1/mag);
598 0 : float distance = raycubepos(o, ray, hitpos, mag, Ray_ClipMat|Ray_Poly);
599 0 : return distance >= mag;
600 : }
601 :
602 0 : float rayfloor(const vec &o, vec &floor, int mode, float radius)
603 : {
604 0 : if(o.z<=0)
605 : {
606 0 : return -1;
607 : }
608 0 : hitsurface = vec(0, 0, 1);
609 0 : float dist = rootworld.raycube(o, vec(0, 0, -1), radius, mode);
610 0 : if(dist<0 || (radius>0 && dist>=radius))
611 : {
612 0 : return dist;
613 : }
614 0 : floor = hitsurface;
615 0 : return dist;
616 : }
|
