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