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