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 : /**
236 : * @brief Shadow optimized entity distance check
237 : *
238 : * @param oc octaentities object containing list of ent indices to use
239 : * @param o intersect start location
240 : * @param ray intersect ray direction
241 : * @param radius maximum radius
242 : * @param mode type of intersection to use (not necessarily Ray_Shadow)
243 : * @param t entity to exclude checking (e.g. self)
244 : *
245 : * @return distance to entity, or radius if distance out of bounds or no intersection
246 : */
247 0 : float shadowent(const octaentities *oc, const vec &o, const vec &ray, float radius, int mode, const extentity *t)
248 : {
249 0 : float dist = radius,
250 0 : f = 0.0f;
251 0 : const std::vector<extentity *> &ents = entities::getents();
252 0 : for(const int &i : oc->mapmodels)
253 : {
254 0 : const extentity &e = *ents[i];
255 0 : if(!(e.flags&EntFlag_Octa) || &e==t)
256 : {
257 0 : continue;
258 : }
259 0 : if(!mmintersect(e, o, ray, radius, mode, f))
260 : {
261 0 : continue;
262 : }
263 0 : if(f > 0 && f < dist)
264 : {
265 0 : dist = f;
266 : }
267 : }
268 0 : return dist;
269 : }
270 :
271 : /**
272 : * @brief Finds the closest value and returns it to ref parameters
273 : *
274 : * @param xval value to return if dx is smallest
275 : * @param yval value to return if dy is smallest
276 : * @param zval value to return if dz is smallest
277 : * @param lsizemask scale mask to shift
278 : * @param invray inverse of the ray to track (elementwise inverse)
279 : * @param lo origin of the coordinates
280 : * @param lshift shift factor for the sizemask
281 : * @param v returns sum of itself and ray scaled to dist value
282 : * @param dist returns sum of itself and whichever of dx/dy/dz returned
283 : * @param ray direction of value to add to v
284 : *
285 : * @return closest returns closest of xval, yval, zval
286 : */
287 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)
288 : {
289 0 : float dx = (lo.x+(lsizemask.x<<lshift)-v.x)*invray.x,
290 0 : dy = (lo.y+(lsizemask.y<<lshift)-v.y)*invray.y,
291 0 : dz = (lo.z+(lsizemask.z<<lshift)-v.z)*invray.z;
292 0 : float disttonext = dx;
293 0 : int closest = xval;
294 0 : if(dy < disttonext)
295 : {
296 0 : disttonext = dy;
297 0 : closest = yval;
298 : }
299 0 : if(dz < disttonext)
300 : {
301 0 : disttonext = dz;
302 0 : closest = zval;
303 : }
304 0 : disttonext += 0.1f;
305 0 : v.add(vec(ray).mul(disttonext));
306 0 : dist += disttonext;
307 0 : return closest;
308 : }
309 : }
310 :
311 : //externally relevant functionality
312 0 : bool insideworld(const vec &o)
313 : {
314 0 : return o.x>=0 && o.x<rootworld.mapsize() && o.y>=0 && o.y<rootworld.mapsize() && o.z>=0 && o.z<rootworld.mapsize();
315 : }
316 :
317 0 : bool insideworld(const ivec &o)
318 : {
319 0 : return static_cast<uint>(o.x) < static_cast<uint>(rootworld.mapsize()) &&
320 0 : static_cast<uint>(o.y) < static_cast<uint>(rootworld.mapsize()) &&
321 0 : static_cast<uint>(o.z) < static_cast<uint>(rootworld.mapsize());
322 : }
323 :
324 : vec hitsurface;
325 :
326 : //will only change &outrad and &dist if not inside the world
327 : //true if outside world, false if inside
328 0 : bool cubeworld::checkinsideworld(const vec &invray, float radius, float &outrad, const vec &o, vec &v, const vec& ray, float &dist) const
329 : {
330 0 : if(!insideworld(o))
331 : {
332 0 : float disttoworld = 0,
333 0 : exitworld = 1e16f;
334 0 : for(int i = 0; i < 3; ++i)
335 : {
336 0 : float c = v[i];
337 0 : if(c<0 || c>=mapsize())
338 : {
339 0 : float d = ((invray[i]>0?0:mapsize())-c)*invray[i];
340 0 : if(d<0)
341 : {
342 0 : outrad = radius>0 ? radius :-1;
343 0 : return true;
344 : }
345 0 : disttoworld = std::max(disttoworld, 0.1f + d);
346 : }
347 0 : float e = ((invray[i]>0?mapsize():0)-c)*invray[i];
348 0 : exitworld = std::min(exitworld, e);
349 : }
350 0 : if(disttoworld > exitworld)
351 : {
352 0 : outrad = (radius>0?radius:-1);
353 0 : return true;
354 : }
355 0 : v.add(vec(ray).mul(disttoworld));
356 0 : dist += disttoworld;
357 : }
358 0 : return false;
359 : }
360 :
361 0 : bool cubeworld::upoctree(const vec &v, int &x, int &y, int &z, const ivec &lo, int &lshift) const
362 : {
363 0 : x = static_cast<int>(v.x);
364 0 : y = static_cast<int>(v.y);
365 0 : z = static_cast<int>(v.z);
366 0 : uint diff = static_cast<uint>(lo.x^x)|static_cast<uint>(lo.y^y)|static_cast<uint>(lo.z^z);
367 0 : if(diff >= static_cast<uint>(mapsize()))
368 : {
369 0 : return true;
370 : }
371 0 : diff >>= lshift;
372 0 : if(!diff)
373 : {
374 0 : return true;
375 : }
376 : do
377 : {
378 0 : lshift++;
379 0 : diff >>= 1;
380 0 : } while(diff);
381 0 : return false;
382 : }
383 :
384 : //=================================================================== DOWNOCTREE
385 :
386 : #define DOWNOCTREE(disttoent, earlyexit) \
387 : cube *lc = r.levels[r.lshift]; \
388 : for(;;) \
389 : { \
390 : r.lshift--; \
391 : lc += OCTA_STEP(x, y, z, r.lshift); \
392 : if(lc->ext && lc->ext->ents && r.lshift < r.elvl) \
393 : { \
394 : float edist = disttoent(lc->ext->ents, o, ray, r.dent, mode, t); \
395 : if(edist < r.dent) \
396 : { \
397 : earlyexit return std::min(edist, r.dist); \
398 : r.elvl = r.lshift; \
399 : r.dent = std::min(r.dent, edist); \
400 : } \
401 : } \
402 : if(lc->children==nullptr) \
403 : { \
404 : break; \
405 : } \
406 : lc = &(*lc->children)[0]; \
407 : r.levels[r.lshift] = lc; \
408 : }
409 :
410 : struct raycubeinfo final
411 : {
412 : float dist,
413 : dent;
414 : vec v,
415 : invray;
416 : std::array<cube *, 20> levels; //NOTE: levels[20] magically assumes mapscale <20
417 : int lshift,
418 : elvl;
419 : ivec lsizemask;
420 :
421 0 : raycubeinfo(float radius, const vec &o, const vec &ray, int worldscale, int mode, cube *r)
422 0 : {
423 0 : dist = 0;
424 0 : dent = radius > 0 ? radius : 1e16f;
425 0 : v = o;
426 0 : invray = vec(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f);
427 0 : levels[worldscale] = r;
428 0 : lshift = worldscale;
429 0 : elvl = mode&Ray_BB ? worldscale : 0;
430 0 : lsizemask = ivec(invray.x>0 ? 1 : 0, invray.y>0 ? 1 : 0, invray.z>0 ? 1 : 0);
431 0 : }
432 : };
433 :
434 0 : float cubeworld::raycube(const vec &o, const vec &ray, float radius, int mode, int size, const extentity *t) const
435 : {
436 0 : if(ray.iszero())
437 : {
438 0 : return 0;
439 : }
440 0 : raycubeinfo r(radius, o, ray, worldscale, mode, &(*worldroot)[0]);
441 : //scope limiting brackets
442 : {
443 0 : float outrad = 0.f;
444 0 : if(checkinsideworld(r.invray, radius, outrad, o, r.v, ray, r.dist))
445 : {
446 0 : return outrad;
447 : }
448 : }
449 0 : int closest = -1,
450 0 : x = static_cast<int>(r.v.x),
451 0 : y = static_cast<int>(r.v.y),
452 0 : z = static_cast<int>(r.v.z);
453 : for(;;)
454 : {
455 0 : DOWNOCTREE(disttoent, if(mode&Ray_Shadow));
456 :
457 0 : int lsize = 1<<r.lshift;
458 :
459 0 : const cube &c = *lc;
460 0 : if((r.dist>0 || !(mode&Ray_SkipFirst)) &&
461 0 : (((mode&Ray_ClipMat) && IS_CLIPPED(c.material&MatFlag_Volume)) ||
462 0 : ((mode&Ray_EditMat) && c.material != Mat_Air) ||
463 0 : (!(mode&Ray_Pass) && lsize==size && !(c.isempty())) ||
464 0 : c.issolid() ||
465 0 : r.dent < r.dist) &&
466 0 : (!(mode&Ray_ClipMat) || (c.material&MatFlag_Clip)!=Mat_NoClip))
467 : {
468 0 : if(r.dist < r.dent)
469 : {
470 0 : if(closest < 0)
471 : {
472 0 : float dx = ((x&(~0U<<r.lshift))+(r.invray.x>0 ? 0 : 1<<r.lshift)-r.v.x)*r.invray.x,
473 0 : dy = ((y&(~0U<<r.lshift))+(r.invray.y>0 ? 0 : 1<<r.lshift)-r.v.y)*r.invray.y,
474 0 : dz = ((z&(~0U<<r.lshift))+(r.invray.z>0 ? 0 : 1<<r.lshift)-r.v.z)*r.invray.z;
475 0 : closest = dx > dy ? (dx > dz ? 0 : 2) : (dy > dz ? 1 : 2);
476 : }
477 0 : hitsurface = vec(0, 0, 0);
478 0 : hitsurface[closest] = ray[closest]>0 ? -1 : 1;
479 0 : return r.dist;
480 : }
481 0 : return r.dent;
482 : }
483 :
484 0 : const ivec lo(x&(~0U<<r.lshift), y&(~0U<<r.lshift), z&(~0U<<r.lshift));
485 :
486 0 : if(!(c.isempty()))
487 : {
488 0 : const clipplanes &p = getclipplanes(c, lo, lsize);
489 0 : float f = 0;
490 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))
491 : {
492 0 : return std::min(r.dent, r.dist+f);
493 : }
494 : }
495 0 : closest = findclosest(0, 1, 2, r.lsizemask, r.invray, lo, r.lshift, r.v, r.dist, ray);
496 0 : if(radius>0 && r.dist>=radius)
497 : {
498 0 : return std::min(r.dent, r.dist);
499 : }
500 0 : if(upoctree(r.v, x, y, z, lo, r.lshift))
501 : {
502 0 : return std::min(r.dent, radius>0 ? radius : r.dist);
503 : }
504 0 : }
505 : }
506 :
507 : // optimized version for light shadowing... every cycle here counts!!!
508 0 : float cubeworld::shadowray(const vec &o, const vec &ray, float radius, int mode, const extentity *t)
509 : {
510 0 : raycubeinfo r(radius, o, ray, worldscale, mode, &(*worldroot)[0]);
511 : //scope limiting brackets
512 : {
513 0 : float outrad = 0.f;
514 0 : if(checkinsideworld(r.invray, radius, outrad, o, r.v, ray, r.dist))
515 : {
516 0 : return outrad;
517 : }
518 : }
519 0 : int side = Orient_Bottom,
520 0 : x = static_cast<int>(r.v.x),
521 0 : y = static_cast<int>(r.v.y),
522 0 : z = static_cast<int>(r.v.z);
523 : for(;;)
524 : {
525 0 : DOWNOCTREE(shadowent, );
526 :
527 0 : const cube &c = *lc;
528 0 : ivec lo(x&(~0U<<r.lshift),
529 0 : y&(~0U<<r.lshift),
530 0 : z&(~0U<<r.lshift));
531 :
532 0 : if(!(c.isempty()) && !(c.material&Mat_Alpha))
533 : {
534 0 : if(c.issolid())
535 : {
536 0 : return c.texture[side]==Default_Sky && mode&Ray_SkipSky ? radius : r.dist;
537 : }
538 0 : const clipplanes &p = getclipplanes(c, lo, 1<<r.lshift);
539 0 : float enterdist = -1e16f,
540 0 : exitdist = 1e16f;
541 0 : int i = 0;
542 0 : bool intersected = intersectplanes(p, r.v, ray, enterdist, exitdist, i);
543 0 : side = p.side[i];
544 0 : if(!intersected)
545 : {
546 0 : goto nextcube;
547 : }
548 0 : intersected = intersectbox(p, r.v, ray, r.invray, enterdist, exitdist, i);
549 0 : side = (i<<1) + 1 - r.lsizemask[i];
550 0 : if(!intersected)
551 : {
552 0 : goto nextcube;
553 : }
554 0 : if(exitdist >= 0)
555 : {
556 0 : return c.texture[side]==Default_Sky && mode&Ray_SkipSky ? radius : r.dist+std::max(enterdist+0.1f, 0.0f);
557 : }
558 : }
559 :
560 0 : nextcube:
561 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);
562 0 : if(r.dist>=radius)
563 : {
564 0 : return r.dist;
565 : }
566 0 : if(upoctree(r.v, x, y, z, lo, r.lshift))
567 : {
568 0 : return radius;
569 : }
570 0 : }
571 : }
572 : #undef DOWNOCTREE
573 : //==============================================================================
574 0 : float rayent(const vec &o, const vec &ray, float radius, int mode, int size, int &orient, int &ent)
575 : {
576 0 : hitent = -1;
577 0 : hitentdist = radius;
578 0 : hitorient = -1;
579 0 : float dist = rootworld.raycube(o, ray, radius, mode, size);
580 0 : if((mode&Ray_Ents) == Ray_Ents)
581 : {
582 0 : float dent = disttooutsideent(o, ray, dist < 0 ? 1e16f : dist, nullptr);
583 0 : if(dent < 1e15f && (dist < 0 || dent < dist))
584 : {
585 0 : dist = dent;
586 : }
587 : }
588 0 : orient = hitorient;
589 0 : ent = hitentdist == dist ? hitent : -1;
590 0 : return dist;
591 : }
592 :
593 0 : float raycubepos(const vec &o, const vec &ray, vec &hitpos, float radius, int mode, int size)
594 : {
595 0 : hitpos = ray;
596 0 : float dist = rootworld.raycube(o, ray, radius, mode, size);
597 0 : if(radius>0 && dist>=radius)
598 : {
599 0 : dist = radius;
600 : }
601 0 : hitpos.mul(dist).add(o);
602 0 : return dist;
603 : }
604 :
605 0 : bool raycubelos(const vec &o, const vec &dest, vec &hitpos)
606 : {
607 0 : vec ray(dest);
608 0 : ray.sub(o);
609 0 : float mag = ray.magnitude();
610 0 : ray.mul(1/mag);
611 0 : float distance = raycubepos(o, ray, hitpos, mag, Ray_ClipMat|Ray_Poly);
612 0 : return distance >= mag;
613 : }
614 :
615 0 : float rayfloor(const vec &o, vec &floor, int mode, float radius)
616 : {
617 0 : if(o.z<=0)
618 : {
619 0 : return -1;
620 : }
621 0 : hitsurface = vec(0, 0, 1);
622 0 : float dist = rootworld.raycube(o, vec(0, 0, -1), radius, mode);
623 0 : if(dist<0 || (radius>0 && dist>=radius))
624 : {
625 0 : return dist;
626 : }
627 0 : floor = hitsurface;
628 0 : return dist;
629 : }
|
