Line data Source code
1 : /* bounding interval hierarchy (BIH)
2 : *
3 : * the BIH code is used to calculate the intersection of models with other models
4 : * and the world, specifically for physics collision calculations. BIH methods
5 : * are also used for the procedural ragdoll physics.
6 : */
7 : #include "../libprimis-headers/cube.h"
8 : #include "../../shared/geomexts.h"
9 : #include "../../shared/glexts.h"
10 :
11 : #include <memory>
12 : #include <optional>
13 :
14 : #include "entities.h"
15 : #include "physics.h"
16 : #include "raycube.h"
17 :
18 : #include "render/rendermodel.h"
19 : #include "render/shaderparam.h"
20 : #include "render/stain.h"
21 : #include "render/texture.h"
22 :
23 : #include "world/bih.h"
24 :
25 : #include "model/model.h"
26 :
27 0 : int BIH::node::axis() const
28 : {
29 0 : return child[0]>>14;
30 : }
31 :
32 0 : int BIH::node::childindex(int which) const
33 : {
34 0 : return child[which]&0x3FFF;
35 : }
36 :
37 0 : bool BIH::node::isleaf(int which) const
38 : {
39 0 : return (child[1]&(1<<(14+which)))!=0;
40 : }
41 :
42 0 : bool BIH::mesh::tribb::outside(const ivec &bo, const ivec &br) const
43 : {
44 0 : return std::abs(bo.x - center.coord.x) > br.x + radius.coord.x ||
45 0 : std::abs(bo.y - center.coord.y) > br.y + radius.coord.y ||
46 0 : std::abs(bo.z - center.coord.z) > br.z + radius.coord.z;
47 : }
48 :
49 0 : BIH::mesh::mesh() : numnodes(0), numtris(0), tex(nullptr), flags(0) {}
50 :
51 0 : vec BIH::mesh::getpos(int i) const
52 : {
53 0 : return *reinterpret_cast<const vec *>(pos + i*posstride);
54 : }
55 0 : vec2 BIH::mesh::gettc(int i) const
56 : {
57 0 : return *reinterpret_cast<const vec2 *>(tc + i*tcstride);
58 : }
59 :
60 0 : void BIH::mesh::setmesh(const tri *tris, int numtris,
61 : const uchar *pos, int posstride,
62 : const uchar *tc, int tcstride)
63 : {
64 0 : this->tris = tris;
65 0 : this->numtris = numtris;
66 0 : this->pos = pos;
67 0 : this->posstride = posstride;
68 0 : this->tc = tc;
69 0 : this->tcstride = tcstride;
70 0 : }
71 :
72 :
73 0 : matrix4x3 BIH::mesh::invxform() const
74 : {
75 0 : matrix4x3 ixf(xform);
76 0 : ixf.invert();
77 0 : return ixf;
78 : }
79 :
80 0 : matrix3 BIH::mesh::xformnorm() const
81 : {
82 0 : matrix3 xfn(xform);
83 0 : xfn.normalize();
84 0 : return xfn;
85 : }
86 :
87 0 : matrix3 BIH::mesh::invxformnorm() const
88 : {
89 0 : matrix3 ixfn(xformnorm());
90 0 : ixfn.invert();
91 0 : return ixfn;
92 : }
93 :
94 0 : float BIH::mesh::scale() const
95 : {
96 0 : return xform.a.magnitude();
97 : }
98 :
99 : /* diagram of a,b,c,n vectors
100 : * a is the vector between the origin and the point 0 indicated
101 : * n is the triangle normal
102 : * b,c are displacement vectors from 1->2
103 : * there is no explicit vector from points 1 to 2
104 : * → →
105 : * a n
106 : * 0—————————>
107 : * / \
108 : * → / \ →
109 : * b / \ c
110 : * / \
111 : * 1—————————2
112 : */
113 :
114 0 : bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, float maxdist, float &dist, int mode) const
115 : {
116 0 : const mesh::tri &t = m.tris[tidx];
117 0 : vec a = m.getpos(t.vert[0]), //position of vert 0
118 0 : b = m.getpos(t.vert[1]).sub(a), //displacement vector from vert 0->1
119 0 : c = m.getpos(t.vert[2]).sub(a), //displacement vector from vert 0->2
120 0 : n = vec().cross(b, c), //normal of the triangle
121 0 : r = vec(a).sub(mo), //mo is transform of o
122 0 : e = vec().cross(r, mray); //mray is transform of ray
123 0 : float det = mray.dot(n),
124 : v, w, f;
125 0 : if(det >= 0)
126 : {
127 0 : if(!(mode&Ray_Shadow) && m.flags&Mesh_CullFace)
128 : {
129 0 : return false;
130 : }
131 0 : v = e.dot(c);
132 0 : if(v < 0 || v > det)
133 : {
134 0 : return false;
135 : }
136 0 : w = -e.dot(b);
137 0 : if(w < 0 || v + w > det)
138 : {
139 0 : return false;
140 : }
141 0 : f = r.dot(n)*m.scale();
142 0 : if(f < 0 || f > maxdist*det || !det)
143 : {
144 0 : return false;
145 : }
146 : }
147 : else
148 : {
149 0 : v = e.dot(c);
150 0 : if(v > 0 || v < det)
151 : {
152 0 : return false;
153 : }
154 0 : w = -e.dot(b);
155 0 : if(w > 0 || v + w < det)
156 : {
157 0 : return false;
158 : }
159 0 : f = r.dot(n)*m.scale();
160 0 : if(f > 0 || f < maxdist*det)
161 : {
162 0 : return false;
163 : }
164 : }
165 0 : float invdet = 1/det;
166 0 : if(m.flags&Mesh_Alpha && (mode&Ray_Shadow)==Ray_Shadow && m.tex->alphamask)
167 : {
168 0 : vec2 at = m.gettc(t.vert[0]),
169 0 : bt = m.gettc(t.vert[1]).sub(at).mul(v*invdet),
170 0 : ct = m.gettc(t.vert[2]).sub(at).mul(w*invdet);
171 0 : at.add(bt).add(ct);
172 0 : int si = std::clamp(static_cast<int>(m.tex->xs * at.x), 0, m.tex->xs-1),
173 0 : ti = std::clamp(static_cast<int>(m.tex->ys * at.y), 0, m.tex->ys-1);
174 0 : if(!(m.tex->alphamask[ti*((m.tex->xs+7)/8) + si/8] & (1<<(si%8))))
175 : {
176 0 : return false;
177 : }
178 : }
179 0 : if(!(mode&Ray_Shadow))
180 : {
181 0 : hitsurface = m.xformnorm().transform(n).normalize();
182 : }
183 0 : dist = f*invdet;
184 0 : return true; //true if collided
185 : }
186 :
187 0 : bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec &invray, float maxdist, float &dist, int mode, const node *curnode, float tmin, float tmax) const
188 : {
189 : struct traversestate
190 : {
191 : const BIH::node *node;
192 : float tmin, tmax;
193 : };
194 : std::array<traversestate, 128> stack;
195 0 : size_t stacksize = 0;
196 0 : ivec order(ray.x>0 ? 0 : 1, ray.y>0 ? 0 : 1, ray.z>0 ? 0 : 1);
197 0 : vec mo = m.invxform().transform(o), //invxform is inverse transform 4x3 matrix; transform by vec o
198 0 : mray = m.invxformnorm().transform(ray);
199 : for(;;)
200 : {
201 0 : int axis = curnode->axis();
202 0 : int nearidx = order[axis],
203 0 : faridx = nearidx^1;
204 0 : float nearsplit = (curnode->split[nearidx] - o[axis])*invray[axis],
205 0 : farsplit = (curnode->split[faridx] - o[axis])*invray[axis];
206 0 : if(nearsplit <= tmin)
207 : {
208 0 : if(farsplit < tmax)
209 : {
210 0 : if(!curnode->isleaf(faridx))
211 : {
212 0 : curnode += curnode->childindex(faridx);
213 0 : tmin = std::max(tmin, farsplit);
214 0 : continue;
215 : }
216 0 : else if(triintersect(m, curnode->childindex(faridx), mo, mray, maxdist, dist, mode))
217 : {
218 0 : return true;
219 : }
220 : }
221 : }
222 0 : else if(curnode->isleaf(nearidx))
223 : {
224 0 : if(triintersect(m, curnode->childindex(nearidx), mo, mray, maxdist, dist, mode))
225 : {
226 0 : return true;
227 : }
228 0 : if(farsplit < tmax)
229 : {
230 0 : if(!curnode->isleaf(faridx))
231 : {
232 0 : curnode += curnode->childindex(faridx);
233 0 : tmin = std::max(tmin, farsplit);
234 0 : continue;
235 : }
236 0 : else if(triintersect(m, curnode->childindex(faridx), mo, mray, maxdist, dist, mode))
237 : {
238 0 : return true;
239 : }
240 : }
241 : }
242 : else
243 : {
244 0 : if(farsplit < tmax)
245 : {
246 0 : if(!curnode->isleaf(faridx))
247 : {
248 0 : if(stacksize < stack.size())
249 : {
250 0 : traversestate &save = stack[stacksize++];
251 0 : save.node = curnode + curnode->childindex(faridx);
252 0 : save.tmin = std::max(tmin, farsplit);
253 0 : save.tmax = tmax;
254 : }
255 : else
256 : {
257 0 : if(traverse(m, o, ray, invray, maxdist, dist, mode, curnode + curnode->childindex(nearidx), tmin, std::min(tmax, nearsplit)))
258 : {
259 0 : return true;
260 : }
261 0 : curnode += curnode->childindex(faridx);
262 0 : tmin = std::max(tmin, farsplit);
263 0 : continue;
264 : }
265 : }
266 0 : else if(triintersect(m, curnode->childindex(faridx), mo, mray, maxdist, dist, mode))
267 : {
268 0 : return true;
269 : }
270 : }
271 0 : curnode += curnode->childindex(nearidx);
272 0 : tmax = std::min(tmax, nearsplit);
273 0 : continue;
274 0 : }
275 0 : if(stacksize <= 0)
276 : {
277 0 : return false;
278 : }
279 0 : const traversestate &restore = stack[--stacksize];
280 0 : curnode = restore.node;
281 0 : tmin = restore.tmin;
282 0 : tmax = restore.tmax;
283 0 : }
284 : }
285 :
286 0 : bool BIH::traverse(const vec &o, const vec &ray, float maxdist, float &dist, int mode) const
287 : {
288 : //if components are zero, set component to large value: 1e16, else invert
289 0 : vec invray(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f);
290 0 : for(const mesh &m : meshes)
291 : {
292 0 : if(!(m.flags&Mesh_Render) || (!(mode&Ray_Shadow) && m.flags&Mesh_NoClip))
293 : {
294 0 : continue;
295 : }
296 0 : float t1 = (m.bbmin.x - o.x)*invray.x,
297 0 : t2 = (m.bbmax.x - o.x)*invray.x,
298 : tmin, tmax;
299 0 : if(invray.x > 0)
300 : {
301 0 : tmin = t1;
302 0 : tmax = t2;
303 : }
304 : else
305 : {
306 0 : tmin = t2;
307 0 : tmax = t1;
308 : }
309 0 : t1 = (m.bbmin.y - o.y)*invray.y;
310 0 : t2 = (m.bbmax.y - o.y)*invray.y;
311 0 : if(invray.y > 0)
312 : {
313 0 : tmin = std::max(tmin, t1);
314 0 : tmax = std::min(tmax, t2);
315 : }
316 : else
317 : {
318 0 : tmin = std::max(tmin, t2);
319 0 : tmax = std::min(tmax, t1);
320 : }
321 0 : t1 = (m.bbmin.z - o.z)*invray.z;
322 0 : t2 = (m.bbmax.z - o.z)*invray.z;
323 0 : if(invray.z > 0)
324 : {
325 0 : tmin = std::max(tmin, t1);
326 0 : tmax = std::min(tmax, t2);
327 : }
328 : else
329 : {
330 0 : tmin = std::max(tmin, t2);
331 0 : tmax = std::min(tmax, t1);
332 : }
333 0 : tmax = std::min(tmax, maxdist);
334 0 : if(tmin < tmax && traverse(m, o, ray, invray, maxdist, dist, mode, m.nodes, tmin, tmax))
335 : {
336 0 : return true;
337 : }
338 : }
339 0 : return false;
340 : }
341 :
342 0 : void BIH::build(mesh &m, uint *indices, int numindices, const ivec &vmin, const ivec &vmax) const
343 : {
344 0 : int axis = 2;
345 0 : for(int k = 0; k < 2; ++k)
346 : {
347 0 : if(vmax[k] - vmin[k] > vmax[axis] - vmin[axis])
348 : {
349 0 : axis = k;
350 : }
351 : }
352 0 : ivec leftmin,
353 0 : leftmax,
354 0 : rightmin,
355 0 : rightmax;
356 : int splitleft,
357 : splitright,
358 : left,
359 : right;
360 0 : for(int k = 0; k < 3; ++k)
361 : {
362 0 : leftmin = rightmin = ivec(INT_MAX, INT_MAX, INT_MAX);
363 0 : leftmax = rightmax = ivec(INT_MIN, INT_MIN, INT_MIN);
364 0 : int split = (vmax[axis] + vmin[axis])/2;
365 0 : for(left = 0, right = numindices, splitleft = SHRT_MIN, splitright = SHRT_MAX; left < right;)
366 : {
367 0 : const mesh::tribb &tri = m.tribbs[indices[left]];
368 0 : ivec trimin = ivec(tri.center).sub(ivec(tri.radius)),
369 0 : trimax = ivec(tri.center).add(ivec(tri.radius));
370 0 : int amin = trimin[axis],
371 0 : amax = trimax[axis];
372 0 : if(std::max(split - amin, 0) > std::max(amax - split, 0))
373 : {
374 0 : ++left;
375 0 : splitleft = std::max(splitleft, amax);
376 0 : leftmin.min(trimin);
377 0 : leftmax.max(trimax);
378 : }
379 : else
380 : {
381 0 : --right;
382 0 : std::swap(indices[left], indices[right]);
383 0 : splitright = std::min(splitright, amin);
384 0 : rightmin.min(trimin);
385 0 : rightmax.max(trimax);
386 : }
387 : }
388 0 : if(left > 0 && right < numindices)
389 : {
390 0 : break;
391 : }
392 0 : axis = (axis+1)%3;
393 : }
394 :
395 0 : if(!left || right==numindices)
396 : {
397 0 : leftmin = rightmin = ivec(INT_MAX, INT_MAX, INT_MAX);
398 0 : leftmax = rightmax = ivec(INT_MIN, INT_MIN, INT_MIN);
399 0 : left = right = numindices/2;
400 0 : splitleft = SHRT_MIN;
401 0 : splitright = SHRT_MAX;
402 0 : for(int i = 0; i < numindices; ++i)
403 : {
404 0 : const mesh::tribb &tri = m.tribbs[indices[i]];
405 0 : ivec trimin = static_cast<ivec>(tri.center).sub(static_cast<ivec>(tri.radius)),
406 0 : trimax = static_cast<ivec>(tri.center).add(static_cast<ivec>(tri.radius));
407 0 : if(i < left)
408 : {
409 0 : splitleft = std::max(splitleft, trimax[axis]);
410 0 : leftmin.min(trimin);
411 0 : leftmax.max(trimax);
412 : }
413 : else
414 : {
415 0 : splitright = std::min(splitright, trimin[axis]);
416 0 : rightmin.min(trimin);
417 0 : rightmax.max(trimax);
418 : }
419 : }
420 : }
421 :
422 0 : int offset = m.numnodes++;
423 0 : node &curnode = m.nodes[offset];
424 0 : curnode.split[0] = static_cast<short>(splitleft);
425 0 : curnode.split[1] = static_cast<short>(splitright);
426 :
427 0 : if(left==1)
428 : {
429 0 : curnode.child[0] = (axis<<14) | indices[0];
430 : }
431 : else
432 : {
433 0 : curnode.child[0] = (axis<<14) | (m.numnodes - offset);
434 0 : build(m, indices, left, leftmin, leftmax);
435 : }
436 :
437 0 : if(numindices-right==1)
438 : {
439 0 : curnode.child[1] = (1<<15) | (left==1 ? 1<<14 : 0) | indices[right];
440 : }
441 : else
442 : {
443 0 : curnode.child[1] = (left==1 ? 1<<14 : 0) | (m.numnodes - offset);
444 0 : build(m, &indices[right], numindices-right, rightmin, rightmax);
445 : }
446 0 : }
447 :
448 2 : BIH::BIH(const std::vector<mesh> &buildmeshes)
449 2 : : nodes(nullptr), numnodes(0), bbmin(1e16f, 1e16f, 1e16f), bbmax(-1e16f, -1e16f, -1e16f), center(0, 0, 0), radius(0)
450 : {
451 2 : mesh::tribb *tribbs = nullptr;
452 2 : int numtris = 0;
453 2 : if(buildmeshes.empty())
454 : {
455 2 : return;
456 : }
457 0 : for(const mesh &i : buildmeshes)
458 : {
459 0 : numtris += i.numtris;
460 : }
461 0 : if(!numtris)
462 : {
463 0 : return;
464 : }
465 0 : meshes.assign(buildmeshes.begin(), buildmeshes.end());
466 0 : tribbs = new mesh::tribb[numtris];
467 0 : mesh::tribb *dsttri = tribbs;
468 0 : for(mesh &m : meshes)
469 : {
470 0 : m.tribbs = dsttri;
471 0 : const mesh::tri *srctri = m.tris;
472 0 : vec mmin(1e16f, 1e16f, 1e16f), mmax(-1e16f, -1e16f, -1e16f);
473 0 : for(int j = 0; j < m.numtris; ++j)
474 : {
475 0 : vec s0 = m.getpos(srctri->vert[0]),
476 0 : s1 = m.getpos(srctri->vert[1]),
477 0 : s2 = m.getpos(srctri->vert[2]),
478 0 : v0 = m.xform.transform(s0),
479 0 : v1 = m.xform.transform(s1),
480 0 : v2 = m.xform.transform(s2),
481 0 : vmin = vec(v0).min(v1).min(v2),
482 0 : vmax = vec(v0).max(v1).max(v2);
483 0 : mmin.min(vmin);
484 0 : mmax.max(vmax);
485 0 : ivec imin = ivec::floor(vmin),
486 0 : imax = ivec::ceil(vmax);
487 0 : dsttri->center = static_cast<svec>(static_cast<ivec>(imin).add(imax).div(2));
488 0 : dsttri->radius = static_cast<svec>(static_cast<ivec>(imax).sub(imin).add(1).div(2));
489 0 : ++srctri;
490 0 : ++dsttri;
491 : }
492 0 : for(int k = 0; k < 3; ++k)
493 : {
494 0 : if(std::fabs(mmax[k] - mmin[k]) < 0.125f)
495 : {
496 0 : float mid = (mmin[k] + mmax[k]) / 2;
497 0 : mmin[k] = mid - 0.0625f;
498 0 : mmax[k] = mid + 0.0625f;
499 : }
500 : }
501 0 : m.bbmin = mmin;
502 0 : m.bbmax = mmax;
503 0 : bbmin.min(mmin);
504 0 : bbmax.max(mmax);
505 : }
506 :
507 0 : center = vec(bbmin).add(bbmax).mul(0.5f);
508 0 : radius = vec(bbmax).sub(bbmin).mul(0.5f).magnitude();
509 :
510 0 : nodes = new node[numtris];
511 0 : node *curnode = nodes;
512 0 : uint *indices = new uint[numtris];
513 0 : for(mesh &m : meshes)
514 : {
515 0 : m.nodes = curnode;
516 0 : for(int j = 0; j < m.numtris; ++j)
517 : {
518 0 : indices[j] = j;
519 : }
520 0 : build(m, indices, m.numtris, ivec::floor(m.bbmin), ivec::ceil(m.bbmax));
521 0 : curnode += m.numnodes;
522 : }
523 0 : delete[] indices;
524 0 : numnodes = static_cast<int>(curnode - nodes);
525 0 : }
526 :
527 2 : BIH::~BIH()
528 : {
529 2 : delete[] nodes;
530 2 : }
531 :
532 0 : bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist, int mode, float &dist)
533 : {
534 0 : model *m = loadmapmodel(e.attr1);
535 0 : if(!m)
536 : {
537 0 : return false;
538 : }
539 0 : if(mode&Ray_Shadow)
540 : {
541 0 : if(!m->shadow || e.flags&EntFlag_NoShadow)
542 : {
543 0 : return false;
544 : }
545 : }
546 0 : else if((mode&Ray_Ents)!=Ray_Ents && (!m->collide || e.flags&EntFlag_NoCollide))
547 : {
548 0 : return false;
549 : }
550 0 : m->setBIH();
551 0 : float scale = e.attr5 ? 100.0f/e.attr5 : 1.0f;
552 0 : vec mo = static_cast<vec>(o).sub(e.o).mul(scale), mray(ray);
553 0 : float v = mo.dot(mray),
554 0 : inside = m->bih->getentradius() - mo.squaredlen();
555 0 : if((inside < 0 && v > 0) || inside + v*v < 0)
556 : {
557 0 : return false;
558 : }
559 0 : int yaw = e.attr2,
560 0 : pitch = e.attr3,
561 0 : roll = e.attr4;
562 : //reorientation of rotated mmodels
563 0 : if(yaw != 0)
564 : {
565 0 : const vec2 &rot = sincosmod360(-yaw);
566 0 : mo.rotate_around_z(rot);
567 0 : mray.rotate_around_z(rot);
568 : }
569 0 : if(pitch != 0)
570 : {
571 0 : const vec2 &rot = sincosmod360(-pitch);
572 0 : mo.rotate_around_x(rot);
573 0 : mray.rotate_around_x(rot);
574 : }
575 0 : if(roll != 0)
576 : {
577 0 : const vec2 &rot = sincosmod360(roll);
578 0 : mo.rotate_around_y(-rot);
579 0 : mray.rotate_around_y(-rot);
580 : }
581 0 : if(m->bih->traverse(mo, mray, maxdist ? maxdist*scale : 1e16f, dist, mode))
582 : {
583 0 : dist /= scale;
584 0 : if(!(mode&Ray_Shadow))
585 : {
586 : //reorientation
587 0 : if(roll != 0)
588 : {
589 0 : hitsurface.rotate_around_y(sincosmod360(roll));
590 : }
591 0 : if(pitch != 0)
592 : {
593 0 : hitsurface.rotate_around_x(sincosmod360(pitch));
594 : }
595 0 : if(yaw != 0)
596 : {
597 0 : hitsurface.rotate_around_z(sincosmod360(yaw));
598 : }
599 : }
600 0 : return true;
601 : }
602 0 : return false;
603 : }
604 :
605 0 : static float segmentdistance(const vec &d1, const vec &d2, const vec &r)
606 : {
607 0 : float a = d1.squaredlen(),
608 0 : e = d2.squaredlen(),
609 0 : f = d2.dot(r),
610 : s, t;
611 0 : if(a <= 1e-4f)
612 : {
613 0 : if(e <= 1e-4f)
614 : {
615 0 : return r.squaredlen();
616 : }
617 0 : s = 0;
618 0 : t = std::clamp(-f / e, 0.0f, 1.0f);
619 : }
620 : else
621 : {
622 0 : float c = d1.dot(r);
623 0 : if(e <= 1e-4f)
624 : {
625 0 : t = 0;
626 0 : s = std::clamp(c / a, 0.0f, 1.0f);
627 : }
628 : else
629 : {
630 0 : float b = d1.dot(d2),
631 0 : denom = a*e - b*b;
632 0 : s = denom ? std::clamp((c*e - b*f) / denom, 0.0f, 1.0f) : 0.0f;
633 0 : t = b*s - f;
634 0 : if(t < 0)
635 : {
636 0 : t = 0;
637 0 : s = std::clamp(c / a, 0.0f, 1.0f);
638 : }
639 0 : else if(t > e)
640 : {
641 0 : t = 1;
642 0 : s = std::clamp((b + c) / a, 0.0f, 1.0f);
643 : }
644 : else
645 : {
646 0 : t /= e;
647 : }
648 : }
649 : }
650 0 : vec c1 = static_cast<vec>(d1).mul(s),
651 0 : c2 = static_cast<vec>(d2).mul(t);
652 0 : return vec(c2).sub(c1).add(r).squaredlen();
653 : }
654 :
655 0 : static float trisegmentdistance(const vec &a, const vec &b, const vec &c, const vec &p, const vec &q)
656 : {
657 : //displacement vectors
658 0 : vec pq = vec(q).sub(p),
659 0 : ab = vec(b).sub(a),
660 0 : bc = vec(c).sub(b),
661 0 : ca = vec(a).sub(c),
662 0 : ap = vec(p).sub(a),
663 0 : bp = vec(p).sub(b),
664 0 : cp = vec(p).sub(c),
665 0 : aq = vec(q).sub(a),
666 0 : bq = vec(q).sub(b);
667 0 : vec n, nab, nbc, nca;
668 0 : n.cross(ab, bc);
669 0 : nab.cross(n, ab);
670 0 : nbc.cross(n, bc);
671 0 : nca.cross(n, ca);
672 0 : float dp = n.dot(ap),
673 0 : dq = n.dot(aq),
674 : dist;
675 0 : if(ap.dot(nab) < 0) // P outside AB
676 : {
677 0 : dist = segmentdistance(ab, pq, ap);
678 0 : if(bq.dot(nbc) < 0)
679 : {
680 0 : dist = std::min(dist, segmentdistance(bc, pq, bp)); // Q outside BC
681 : }
682 0 : else if(aq.dot(nca) < 0)
683 : {
684 0 : dist = std::min(dist, segmentdistance(pq, ca, cp)); // Q outside CA
685 : }
686 0 : else if(aq.dot(nab) >= 0)
687 : {
688 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside AB
689 : }
690 : else
691 : {
692 0 : return dist;
693 : }
694 : }
695 0 : else if(bp.dot(nbc) < 0) // P outside BC
696 : {
697 0 : dist = segmentdistance(bc, pq, bp);
698 0 : if(aq.dot(nca) < 0)
699 : {
700 0 : dist = std::min(dist, segmentdistance(ca, pq, cp)); // Q outside CA
701 : }
702 0 : else if(aq.dot(nab) < 0)
703 : {
704 0 : dist = std::min(dist, segmentdistance(ab, pq, ap)); // Q outside AB
705 : }
706 0 : else if(bq.dot(nbc) >= 0)
707 : {
708 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside BC
709 : }
710 : else
711 : {
712 0 : return dist;
713 : }
714 : }
715 0 : else if(cp.dot(nca) < 0) // P outside CA
716 : {
717 0 : dist = segmentdistance(ca, pq, cp);
718 0 : if(aq.dot(nab) < 0)
719 : {
720 0 : dist = std::min(dist, segmentdistance(ab, pq, ap)); // Q outside AB
721 : }
722 0 : else if(bq.dot(nbc) < 0)
723 : {
724 0 : dist = std::min(dist, segmentdistance(bc, pq, bp)); // Q outside BC
725 : }
726 0 : else if(aq.dot(nca) >= 0)
727 : {
728 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside CA
729 : }
730 0 : else return dist;
731 : }
732 0 : else if(aq.dot(nab) < 0)
733 : {
734 0 : dist = std::min(segmentdistance(ab, pq, ap), dp); // Q outside AB
735 : }
736 0 : else if(bq.dot(nbc) < 0)
737 : {
738 0 : dist = std::min(segmentdistance(bc, pq, bp), dp); // Q outside BC
739 : }
740 0 : else if(aq.dot(nca) < 0)
741 : {
742 0 : dist = std::min(segmentdistance(ca, pq, cp), dp); // Q outside CA
743 : }
744 : else // both P and Q inside
745 : {
746 0 : if(dp > 0 ? dq <= 0 : dq >= 0)
747 : {
748 0 : return 0; // P and Q on different sides of triangle
749 : }
750 0 : dist = std::min(dp*dp, dq*dq)/n.squaredlen();
751 0 : return dist;
752 : }
753 0 : if(dp > 0 ? dq >= 0 : dq <= 0)
754 : {
755 0 : return dist; // both P and Q on same side of triangle
756 : }
757 0 : vec e = vec().cross(pq, ap);
758 0 : float det = std::fabs(dq - dp),
759 0 : v = ca.dot(e);
760 0 : if(v < 0 || v > det)
761 : {
762 0 : return dist;
763 : }
764 0 : float w = ab.dot(e);
765 0 : if(w < 0 || v + w > det)
766 : {
767 0 : return dist;
768 : }
769 0 : return 0; // segment intersects triangle
770 : }
771 :
772 0 : static bool triboxoverlap(const vec &radius, const vec &a, const vec &b, const vec &c)
773 : {
774 :
775 0 : static auto testaxis = [] (const vec &v0, const vec &v1, const vec &v2,
776 : const vec &e, const int &s, const int &t,
777 : const vec &radius)
778 : {
779 0 : float p = v0[s]*v1[t] - v0[t]*v1[s],
780 0 : q = v2[s]*e[t] - v2[t]*e[s],
781 0 : r = radius[s]*std::fabs(e[t]) + radius[t]*std::fabs(e[s]);
782 0 : if(p < q)
783 : {
784 0 : if(q < -r || p > r)
785 : {
786 0 : return false;
787 : }
788 : }
789 0 : else if(p < -r || q > r)
790 : {
791 0 : return false;
792 : }
793 0 : return true;
794 : };
795 :
796 0 : static auto testface = [] (const vec &a, const vec &b, const vec &c,
797 : const vec &ab, const vec &bc, const vec &ca,
798 : uint axis, const vec &radius)
799 : {
800 0 : if(a[axis] < b[axis])
801 : {
802 0 : if(b[axis] < c[axis])
803 : {
804 0 : if(c[axis] < -radius[axis] || a[axis] > radius[axis])
805 : {
806 0 : return false;
807 : }
808 : }
809 0 : else if(b[axis] < -radius[axis] || std::min(a[axis], c[axis]) > radius[axis])
810 : {
811 0 : return false;
812 : }
813 : }
814 0 : else if(a[axis] < c[axis])
815 : {
816 0 : if(c[axis] < -radius[axis] || b[axis] > radius[axis])
817 : {
818 0 : return false;
819 : }
820 : }
821 0 : else if(a[axis] < -radius[axis] || std::min(b[axis], c[axis]) > radius[axis])
822 : {
823 0 : return false;
824 : }
825 0 : return true;
826 : };
827 :
828 0 : vec ab = vec(b).sub(a),
829 0 : bc = vec(c).sub(b),
830 0 : ca = vec(a).sub(c);
831 :
832 0 : if(!testaxis(a, b, c, ab, 2, 1, radius)) {return false;};
833 0 : if(!testaxis(a, b, c, ab, 0, 2, radius)) {return false;};
834 0 : if(!testaxis(a, b, c, ab, 1, 0, radius)) {return false;};
835 :
836 0 : if(!testaxis(b, c, a, bc, 2, 1, radius)) {return false;};
837 0 : if(!testaxis(b, c, a, bc, 0, 2, radius)) {return false;};
838 0 : if(!testaxis(a, b, c, ab, 1, 0, radius)) {return false;};
839 :
840 0 : if(!testaxis(c, a, b, ca, 2, 1, radius)) {return false;};
841 0 : if(!testaxis(c, a, b, ca, 0, 2, radius)) {return false;};
842 0 : if(!testaxis(c, a, b, ca, 1, 0, radius)) {return false;};
843 :
844 0 : if(!testface(a, b, c, ab, bc, ca, 0, radius)) //x
845 : {
846 0 : return false;
847 : }
848 0 : else if(!testface(a, b, c, ab, bc, ca, 1, radius)) //y
849 : {
850 0 : return false;
851 : }
852 0 : else if(!testface(a, b, c, ab, bc, ca, 2, radius)) //z
853 : {
854 0 : return false;
855 : }
856 0 : return true;
857 : }
858 :
859 : //used in the tricollide templates below
860 : //returns true if physent is a player and passed vec is close enough to matter (determined by radius,pdist)
861 0 : bool BIH::playercollidecheck(const physent *d, float pdist, vec dir, vec n, vec radius) const
862 : {
863 0 : float a = 2*radius.z*(d->zmargin/(d->aboveeye+d->eyeheight)-(dir.z < 0 ? 1/3.0f : 1/4.0f)),
864 0 : b = (dir.x*n.x < 0 || dir.y*n.y < 0 ? -radius.x : 0);
865 0 : if(d->type==physent::PhysEnt_Player)
866 : {
867 0 : if(pdist < (dir.z*n.z < 0 ? a : b))
868 : {
869 0 : return true;
870 : }
871 : }
872 0 : return false;
873 : }
874 :
875 : template<>
876 0 : void BIH::tricollide<Collide_Ellipse>(const mesh &m, int tidx, const physent *d, const vec &dir, float cutoff, const vec &, const vec &radius, const matrix4x3 &orient, float &dist, const ivec &bo, const ivec &br) const
877 : {
878 0 : if(m.tribbs[tidx].outside(bo, br))
879 : {
880 0 : return;
881 : }
882 0 : const mesh::tri &t = m.tris[tidx];
883 0 : vec a = m.getpos(t.vert[0]),
884 0 : b = m.getpos(t.vert[1]),
885 0 : c = m.getpos(t.vert[2]),
886 0 : zdir = vec(orient.rowz()).mul((radius.z - radius.x)/(m.scale()*m.scale()));
887 0 : if(trisegmentdistance(a, b, c, vec(center).sub(zdir), vec(center).add(zdir)) > (radius.x*radius.x)/(m.scale()*m.scale()))
888 : {
889 0 : return;
890 : }
891 0 : vec n;
892 0 : n.cross(a, b, c).normalize();
893 0 : float pdist = (n.dot(vec(center).sub(a)) - std::fabs(n.dot(zdir)))*m.scale() - radius.x;
894 0 : if(pdist > 0 || pdist <= dist)
895 : {
896 0 : return;
897 : }
898 0 : collideinside = true;
899 0 : n = orient.transformnormal(n).div(m.scale());
900 0 : if(!dir.iszero())
901 : {
902 0 : if(n.dot(dir) >= -cutoff*dir.magnitude())
903 : {
904 0 : return;
905 : }
906 : //see playercollidecheck defined above
907 0 : if(playercollidecheck(d, pdist, dir, n, radius))
908 : {
909 0 : return;
910 : }
911 : }
912 0 : dist = pdist;
913 0 : collidewall = n;
914 : }
915 :
916 : template<>
917 0 : void BIH::tricollide<Collide_OrientedBoundingBox>(const mesh &m, int tidx, const physent *d, const vec &dir, float cutoff, const vec &, const vec &radius, const matrix4x3 &orient, float &dist, const ivec &bo, const ivec &br) const
918 : {
919 0 : if(m.tribbs[tidx].outside(bo, br))
920 : {
921 0 : return;
922 : }
923 0 : const mesh::tri &t = m.tris[tidx];
924 0 : vec a = orient.transform(m.getpos(t.vert[0])),
925 0 : b = orient.transform(m.getpos(t.vert[1])),
926 0 : c = orient.transform(m.getpos(t.vert[2]));
927 0 : if(!triboxoverlap(radius, a, b, c))
928 : {
929 0 : return;
930 : }
931 0 : vec n;
932 0 : n.cross(a, b, c).normalize();
933 0 : float pdist = -n.dot(a),
934 0 : r = radius.absdot(n);
935 0 : if(std::fabs(pdist) > r)
936 : {
937 0 : return;
938 : }
939 0 : pdist -= r;
940 0 : if(pdist <= dist)
941 : {
942 0 : return;
943 : }
944 0 : collideinside = true;
945 0 : if(!dir.iszero())
946 : {
947 0 : if(n.dot(dir) >= -cutoff*dir.magnitude())
948 : {
949 0 : return;
950 : }
951 0 : if(playercollidecheck(d, pdist, dir, n, radius))
952 : {
953 0 : return;
954 : }
955 : }
956 0 : dist = pdist;
957 0 : collidewall = n;
958 : }
959 :
960 : template<int C>
961 0 : void BIH::collide(const mesh &m, const physent *d, const vec &dir, float cutoff, const vec ¢er, const vec &radius, const matrix4x3 &orient, float &dist, node *curnode, const ivec &bo, const ivec &br) const
962 : {
963 : node *stack[128];
964 0 : int stacksize = 0;
965 0 : ivec bmin = ivec(bo).sub(br),
966 0 : bmax = ivec(bo).add(br);
967 0 : for(;;)
968 : {
969 0 : int axis = curnode->axis();
970 0 : const int nearidx = 0,
971 0 : faridx = nearidx^1;
972 0 : int nearsplit = bmin[axis] - curnode->split[nearidx],
973 0 : farsplit = curnode->split[faridx] - bmax[axis];
974 :
975 0 : if(nearsplit > 0)
976 : {
977 0 : if(farsplit <= 0)
978 : {
979 0 : if(!curnode->isleaf(faridx))
980 : {
981 0 : curnode += curnode->childindex(faridx);
982 0 : continue;
983 : }
984 : else
985 : {
986 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
987 : }
988 : }
989 : }
990 0 : else if(curnode->isleaf(nearidx))
991 : {
992 0 : tricollide<C>(m, curnode->childindex(nearidx), d, dir, cutoff, center, radius, orient, dist, bo, br);
993 0 : if(farsplit <= 0)
994 : {
995 0 : if(!curnode->isleaf(faridx))
996 : {
997 0 : curnode += curnode->childindex(faridx);
998 0 : continue;
999 : }
1000 : else
1001 : {
1002 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
1003 : }
1004 : }
1005 : }
1006 : else
1007 : {
1008 0 : if(farsplit <= 0)
1009 : {
1010 0 : if(!curnode->isleaf(faridx))
1011 : {
1012 0 : if(stacksize < static_cast<int>(sizeof(stack)/sizeof(stack[0])))
1013 : {
1014 0 : stack[stacksize++] = curnode + curnode->childindex(faridx);
1015 : }
1016 : else
1017 : {
1018 0 : collide<C>(m, d, dir, cutoff, center, radius, orient, dist, &nodes[curnode->childindex(nearidx)], bo, br);
1019 0 : curnode += curnode->childindex(faridx);
1020 0 : continue;
1021 : }
1022 : }
1023 : else
1024 : {
1025 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
1026 : }
1027 : }
1028 0 : curnode += curnode->childindex(nearidx);
1029 0 : continue;
1030 : }
1031 0 : if(stacksize <= 0)
1032 : {
1033 0 : return;
1034 : }
1035 0 : curnode = stack[--stacksize];
1036 : }
1037 : }
1038 :
1039 0 : bool BIH::ellipsecollide(const physent *d, const vec &dir, float cutoff, const vec &o, int yaw, int pitch, int roll, float scale) const
1040 : {
1041 0 : if(!numnodes)
1042 : {
1043 0 : return false;
1044 : }
1045 0 : vec center(d->o.x, d->o.y, d->o.z + 0.5f*(d->aboveeye - d->eyeheight)),
1046 0 : radius(d->radius, d->radius, 0.5f*(d->eyeheight + d->aboveeye));
1047 0 : center.sub(o);
1048 0 : if(scale != 1)
1049 : {
1050 0 : float invscale = 1/scale;
1051 0 : center.mul(invscale);
1052 0 : radius.mul(invscale);
1053 : }
1054 0 : matrix3 orient;
1055 0 : orient.identity();
1056 0 : if(yaw)
1057 : {
1058 0 : orient.rotate_around_z(sincosmod360(yaw));
1059 : }
1060 0 : if(pitch)
1061 : {
1062 0 : orient.rotate_around_x(sincosmod360(pitch));
1063 : }
1064 0 : if(roll)
1065 : {
1066 0 : orient.rotate_around_y(sincosmod360(-roll));
1067 : }
1068 0 : vec bo = orient.transposedtransform(center),
1069 0 : br = orient.abstransposedtransform(radius);
1070 0 : if(bo.x + br.x < bbmin.x || bo.y + br.y < bbmin.y || bo.z + br.z < bbmin.z ||
1071 0 : bo.x - br.x > bbmax.x || bo.y - br.y > bbmax.y || bo.z - br.z > bbmax.z)
1072 : {
1073 0 : return false;
1074 : }
1075 0 : ivec imin = ivec::floor(vec(bo).sub(br)),
1076 0 : imax = ivec::ceil(vec(bo).add(br)),
1077 0 : icenter = imin.add(imax).div(2),
1078 0 : iradius = imax.sub(imin).add(1).div(2);
1079 :
1080 0 : float dist = -1e10f;
1081 0 : for(const mesh &m : meshes)
1082 : {
1083 0 : if(!(m.flags&Mesh_Collide) || m.flags&Mesh_NoClip)
1084 : {
1085 0 : continue;
1086 : }
1087 0 : matrix4x3 morient;
1088 0 : morient.mul(orient, m.xform);
1089 0 : collide<Collide_Ellipse>(m, d, dir, cutoff, m.invxform().transform(bo), radius, morient, dist, m.nodes, icenter, iradius);
1090 : }
1091 0 : return dist > maxcollidedistance;
1092 : }
1093 :
1094 0 : bool BIH::boxcollide(const physent *d, const vec &dir, float cutoff, const vec &o, int yaw, int pitch, int roll, float scale) const
1095 : {
1096 0 : if(!numnodes)
1097 : {
1098 0 : return false;
1099 : }
1100 0 : vec center(d->o.x, d->o.y, d->o.z + 0.5f*(d->aboveeye - d->eyeheight)),
1101 0 : radius(d->xradius, d->yradius, 0.5f*(d->eyeheight + d->aboveeye));
1102 0 : center.sub(o);
1103 0 : if(scale != 1)
1104 : {
1105 0 : float invscale = 1/scale;
1106 0 : center.mul(invscale);
1107 0 : radius.mul(invscale);
1108 : }
1109 0 : matrix3 orient;
1110 0 : orient.identity();
1111 0 : if(yaw)
1112 : {
1113 0 : orient.rotate_around_z(sincosmod360(yaw));
1114 : }
1115 0 : if(pitch)
1116 : {
1117 0 : orient.rotate_around_x(sincosmod360(pitch));
1118 : }
1119 0 : if(roll)
1120 : {
1121 0 : orient.rotate_around_y(sincosmod360(-roll));
1122 : }
1123 0 : vec bo = orient.transposedtransform(center),
1124 0 : br = orient.abstransposedtransform(vec(d->radius, d->radius, radius.z));
1125 0 : if(bo.x + br.x < bbmin.x || bo.y + br.y < bbmin.y || bo.z + br.z < bbmin.z ||
1126 0 : bo.x - br.x > bbmax.x || bo.y - br.y > bbmax.y || bo.z - br.z > bbmax.z)
1127 : {
1128 0 : return false;
1129 : }
1130 0 : ivec imin = ivec::floor(vec(bo).sub(br)),
1131 0 : imax = ivec::ceil(vec(bo).add(br)),
1132 0 : icenter = ivec(imin).add(imax).div(2),
1133 0 : iradius = ivec(imax).sub(imin).add(1).div(2);
1134 0 : matrix3 drot, dorient;
1135 0 : drot.setyaw(d->yaw/RAD);
1136 0 : vec ddir = drot.transform(dir),
1137 0 : dcenter = drot.transform(center).neg();
1138 0 : dorient.mul(drot, orient);
1139 0 : float dist = -1e10f;
1140 0 : for(const mesh &m : meshes)
1141 : {
1142 0 : if(!(m.flags&Mesh_Collide) || m.flags&Mesh_NoClip)
1143 : {
1144 0 : continue;
1145 : }
1146 0 : matrix4x3 morient;
1147 0 : morient.mul(dorient, dcenter, m.xform);
1148 0 : collide<Collide_OrientedBoundingBox>(m, d, ddir, cutoff, center, radius, morient, dist, m.nodes, icenter, iradius);
1149 : }
1150 0 : if(dist > maxcollidedistance)
1151 : {
1152 0 : collidewall = drot.transposedtransform(collidewall);
1153 0 : return true;
1154 : }
1155 0 : return false;
1156 : }
1157 :
1158 0 : void BIH::genstaintris(std::vector<std::array<vec, 3>> &tris, const mesh &m, int tidx, const vec &, float, const matrix4x3 &orient, const ivec &bo, const ivec &br) const
1159 : {
1160 0 : if(m.tribbs[tidx].outside(bo, br))
1161 : {
1162 0 : return;
1163 : }
1164 0 : const mesh::tri &t = m.tris[tidx];
1165 : std::array<vec, 3> v =
1166 : {
1167 0 : orient.transform(m.getpos(t.vert[0])),
1168 0 : orient.transform(m.getpos(t.vert[1])),
1169 0 : orient.transform(m.getpos(t.vert[2]))
1170 : };
1171 0 : tris.push_back(v);
1172 : }
1173 :
1174 0 : void BIH::genstaintris(std::vector<std::array<vec, 3>> &tris, const mesh &m, const vec ¢er, float radius, const matrix4x3 &orient, node *curnode, const ivec &bo, const ivec &br) const
1175 : {
1176 0 : std::stack<node *> stack;
1177 0 : ivec bmin = static_cast<ivec>(bo).sub(br),
1178 0 : bmax = static_cast<ivec>(bo).add(br);
1179 : for(;;)
1180 : {
1181 0 : int axis = curnode->axis();
1182 0 : constexpr int nearidx = 0,
1183 0 : faridx = nearidx ^ 1; //xor last bit
1184 0 : int nearsplit = bmin[axis] - curnode->split[nearidx],
1185 0 : farsplit = curnode->split[faridx] - bmax[axis];
1186 0 : if(nearsplit > 0)
1187 : {
1188 0 : if(farsplit <= 0)
1189 : {
1190 0 : if(!curnode->isleaf(faridx))
1191 : {
1192 0 : curnode += curnode->childindex(faridx);
1193 0 : continue;
1194 : }
1195 : else
1196 : {
1197 0 : genstaintris(tris, m, curnode->childindex(faridx), center, radius, orient, bo, br);
1198 : }
1199 : }
1200 : }
1201 0 : else if(curnode->isleaf(nearidx))
1202 : {
1203 0 : genstaintris(tris, m, curnode->childindex(nearidx), center, radius, orient, bo, br);
1204 0 : if(farsplit <= 0)
1205 : {
1206 0 : if(!curnode->isleaf(faridx))
1207 : {
1208 0 : curnode += curnode->childindex(faridx);
1209 0 : continue;
1210 : }
1211 : else
1212 : {
1213 0 : genstaintris(tris, m, curnode->childindex(faridx), center, radius, orient, bo, br);
1214 : }
1215 : }
1216 : }
1217 : else
1218 : {
1219 0 : if(farsplit <= 0)
1220 : {
1221 0 : if(!curnode->isleaf(faridx))
1222 : {
1223 0 : if(stack.size() < 128)
1224 : {
1225 0 : stack.push(curnode + curnode->childindex(faridx));
1226 : }
1227 : else
1228 : {
1229 0 : genstaintris(tris, m, center, radius, orient, &nodes[curnode->childindex(nearidx)], bo, br);
1230 0 : curnode += curnode->childindex(faridx);
1231 0 : continue;
1232 : }
1233 : }
1234 : else
1235 : {
1236 0 : genstaintris(tris, m, curnode->childindex(faridx), center, radius, orient, bo, br);
1237 : }
1238 : }
1239 0 : curnode += curnode->childindex(nearidx);
1240 0 : continue;
1241 : }
1242 0 : if(stack.size() <= 0)
1243 : {
1244 0 : return;
1245 : }
1246 0 : curnode = stack.top();
1247 0 : stack.pop();
1248 0 : }
1249 0 : }
1250 :
1251 0 : void BIH::genstaintris(std::vector<std::array<vec, 3>> &tris, const vec &staincenter, float stainradius, const vec &o, int yaw, int pitch, int roll, float scale) const
1252 : {
1253 0 : if(!numnodes)
1254 : {
1255 0 : return;
1256 : }
1257 0 : vec center = vec(staincenter).sub(o);
1258 0 : float radius = stainradius;
1259 0 : if(scale != 1)
1260 : {
1261 0 : float invscale = 1/scale;
1262 0 : center.mul(invscale);
1263 0 : radius *= invscale;
1264 : }
1265 0 : matrix3 orient;
1266 0 : orient.identity();
1267 : //reorientation
1268 0 : if(yaw)
1269 : {
1270 0 : orient.rotate_around_z(sincosmod360(yaw));
1271 : }
1272 0 : if(pitch)
1273 : {
1274 0 : orient.rotate_around_x(sincosmod360(pitch));
1275 : }
1276 0 : if(roll)
1277 : {
1278 0 : orient.rotate_around_y(sincosmod360(-roll));
1279 : }
1280 0 : vec bo = orient.transposedtransform(center);
1281 0 : if(bo.x + radius < bbmin.x || bo.y + radius < bbmin.y || bo.z + radius < bbmin.z ||
1282 0 : bo.x - radius > bbmax.x || bo.y - radius > bbmax.y || bo.z - radius > bbmax.z)
1283 : {
1284 0 : return;
1285 : }
1286 0 : orient.scale(scale);
1287 0 : ivec imin = ivec::floor(vec(bo).sub(radius)),
1288 0 : imax = ivec::ceil(vec(bo).add(radius)),
1289 0 : icenter = ivec(imin).add(imax).div(2),
1290 0 : iradius = ivec(imax).sub(imin).add(1).div(2);
1291 0 : for(const mesh &m : meshes)
1292 : {
1293 0 : if(!(m.flags&Mesh_Render) || m.flags&Mesh_Alpha)
1294 : {
1295 0 : continue;
1296 : }
1297 0 : matrix4x3 morient;
1298 0 : morient.mul(orient, o, m.xform);
1299 0 : genstaintris(tris, m, m.invxform().transform(bo), radius, morient, m.nodes, icenter, iradius);
1300 : }
1301 : }
1302 :
1303 0 : float BIH::getentradius() const
1304 : {
1305 0 : return std::max(bbmin.squaredlen(), bbmax.squaredlen());
1306 : }
|
