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