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