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.x) > br.x + radius.x ||
45 0 : std::abs(bo.y - center.y) > br.y + radius.y ||
46 0 : std::abs(bo.z - center.z) > br.z + radius.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 : if(!m->bih && !m->setBIH())
551 : {
552 0 : return false;
553 : }
554 0 : float scale = e.attr5 ? 100.0f/e.attr5 : 1.0f;
555 0 : vec mo = static_cast<vec>(o).sub(e.o).mul(scale), mray(ray);
556 0 : float v = mo.dot(mray),
557 0 : inside = m->bih->getentradius() - mo.squaredlen();
558 0 : if((inside < 0 && v > 0) || inside + v*v < 0)
559 : {
560 0 : return false;
561 : }
562 0 : int yaw = e.attr2,
563 0 : pitch = e.attr3,
564 0 : roll = e.attr4;
565 : //reorientation of rotated mmodels
566 0 : if(yaw != 0)
567 : {
568 0 : const vec2 &rot = sincosmod360(-yaw);
569 0 : mo.rotate_around_z(rot);
570 0 : mray.rotate_around_z(rot);
571 : }
572 0 : if(pitch != 0)
573 : {
574 0 : const vec2 &rot = sincosmod360(-pitch);
575 0 : mo.rotate_around_x(rot);
576 0 : mray.rotate_around_x(rot);
577 : }
578 0 : if(roll != 0)
579 : {
580 0 : const vec2 &rot = sincosmod360(roll);
581 0 : mo.rotate_around_y(-rot);
582 0 : mray.rotate_around_y(-rot);
583 : }
584 0 : if(m->bih->traverse(mo, mray, maxdist ? maxdist*scale : 1e16f, dist, mode))
585 : {
586 0 : dist /= scale;
587 0 : if(!(mode&Ray_Shadow))
588 : {
589 : //reorientation
590 0 : if(roll != 0)
591 : {
592 0 : hitsurface.rotate_around_y(sincosmod360(roll));
593 : }
594 0 : if(pitch != 0)
595 : {
596 0 : hitsurface.rotate_around_x(sincosmod360(pitch));
597 : }
598 0 : if(yaw != 0)
599 : {
600 0 : hitsurface.rotate_around_z(sincosmod360(yaw));
601 : }
602 : }
603 0 : return true;
604 : }
605 0 : return false;
606 : }
607 :
608 0 : static float segmentdistance(const vec &d1, const vec &d2, const vec &r)
609 : {
610 0 : float a = d1.squaredlen(),
611 0 : e = d2.squaredlen(),
612 0 : f = d2.dot(r),
613 : s, t;
614 0 : if(a <= 1e-4f)
615 : {
616 0 : if(e <= 1e-4f)
617 : {
618 0 : return r.squaredlen();
619 : }
620 0 : s = 0;
621 0 : t = std::clamp(-f / e, 0.0f, 1.0f);
622 : }
623 : else
624 : {
625 0 : float c = d1.dot(r);
626 0 : if(e <= 1e-4f)
627 : {
628 0 : t = 0;
629 0 : s = std::clamp(c / a, 0.0f, 1.0f);
630 : }
631 : else
632 : {
633 0 : float b = d1.dot(d2),
634 0 : denom = a*e - b*b;
635 0 : s = denom ? std::clamp((c*e - b*f) / denom, 0.0f, 1.0f) : 0.0f;
636 0 : t = b*s - f;
637 0 : if(t < 0)
638 : {
639 0 : t = 0;
640 0 : s = std::clamp(c / a, 0.0f, 1.0f);
641 : }
642 0 : else if(t > e)
643 : {
644 0 : t = 1;
645 0 : s = std::clamp((b + c) / a, 0.0f, 1.0f);
646 : }
647 : else
648 : {
649 0 : t /= e;
650 : }
651 : }
652 : }
653 0 : vec c1 = static_cast<vec>(d1).mul(s),
654 0 : c2 = static_cast<vec>(d2).mul(t);
655 0 : return vec(c2).sub(c1).add(r).squaredlen();
656 : }
657 :
658 0 : static float trisegmentdistance(const vec &a, const vec &b, const vec &c, const vec &p, const vec &q)
659 : {
660 : //displacement vectors
661 0 : vec pq = vec(q).sub(p),
662 0 : ab = vec(b).sub(a),
663 0 : bc = vec(c).sub(b),
664 0 : ca = vec(a).sub(c),
665 0 : ap = vec(p).sub(a),
666 0 : bp = vec(p).sub(b),
667 0 : cp = vec(p).sub(c),
668 0 : aq = vec(q).sub(a),
669 0 : bq = vec(q).sub(b);
670 0 : vec n, nab, nbc, nca;
671 0 : n.cross(ab, bc);
672 0 : nab.cross(n, ab);
673 0 : nbc.cross(n, bc);
674 0 : nca.cross(n, ca);
675 0 : float dp = n.dot(ap),
676 0 : dq = n.dot(aq),
677 : dist;
678 0 : if(ap.dot(nab) < 0) // P outside AB
679 : {
680 0 : dist = segmentdistance(ab, pq, ap);
681 0 : if(bq.dot(nbc) < 0)
682 : {
683 0 : dist = std::min(dist, segmentdistance(bc, pq, bp)); // Q outside BC
684 : }
685 0 : else if(aq.dot(nca) < 0)
686 : {
687 0 : dist = std::min(dist, segmentdistance(pq, ca, cp)); // Q outside CA
688 : }
689 0 : else if(aq.dot(nab) >= 0)
690 : {
691 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside AB
692 : }
693 : else
694 : {
695 0 : return dist;
696 : }
697 : }
698 0 : else if(bp.dot(nbc) < 0) // P outside BC
699 : {
700 0 : dist = segmentdistance(bc, pq, bp);
701 0 : if(aq.dot(nca) < 0)
702 : {
703 0 : dist = std::min(dist, segmentdistance(ca, pq, cp)); // Q outside CA
704 : }
705 0 : else if(aq.dot(nab) < 0)
706 : {
707 0 : dist = std::min(dist, segmentdistance(ab, pq, ap)); // Q outside AB
708 : }
709 0 : else if(bq.dot(nbc) >= 0)
710 : {
711 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside BC
712 : }
713 : else
714 : {
715 0 : return dist;
716 : }
717 : }
718 0 : else if(cp.dot(nca) < 0) // P outside CA
719 : {
720 0 : dist = segmentdistance(ca, pq, cp);
721 0 : if(aq.dot(nab) < 0)
722 : {
723 0 : dist = std::min(dist, segmentdistance(ab, pq, ap)); // Q outside AB
724 : }
725 0 : else if(bq.dot(nbc) < 0)
726 : {
727 0 : dist = std::min(dist, segmentdistance(bc, pq, bp)); // Q outside BC
728 : }
729 0 : else if(aq.dot(nca) >= 0)
730 : {
731 0 : dist = std::min(dist, dq*dq/n.squaredlen()); // Q inside CA
732 : }
733 0 : else return dist;
734 : }
735 0 : else if(aq.dot(nab) < 0)
736 : {
737 0 : dist = std::min(segmentdistance(ab, pq, ap), dp); // Q outside AB
738 : }
739 0 : else if(bq.dot(nbc) < 0)
740 : {
741 0 : dist = std::min(segmentdistance(bc, pq, bp), dp); // Q outside BC
742 : }
743 0 : else if(aq.dot(nca) < 0)
744 : {
745 0 : dist = std::min(segmentdistance(ca, pq, cp), dp); // Q outside CA
746 : }
747 : else // both P and Q inside
748 : {
749 0 : if(dp > 0 ? dq <= 0 : dq >= 0)
750 : {
751 0 : return 0; // P and Q on different sides of triangle
752 : }
753 0 : dist = std::min(dp*dp, dq*dq)/n.squaredlen();
754 0 : return dist;
755 : }
756 0 : if(dp > 0 ? dq >= 0 : dq <= 0)
757 : {
758 0 : return dist; // both P and Q on same side of triangle
759 : }
760 0 : vec e = vec().cross(pq, ap);
761 0 : float det = std::fabs(dq - dp),
762 0 : v = ca.dot(e);
763 0 : if(v < 0 || v > det)
764 : {
765 0 : return dist;
766 : }
767 0 : float w = ab.dot(e);
768 0 : if(w < 0 || v + w > det)
769 : {
770 0 : return dist;
771 : }
772 0 : return 0; // segment intersects triangle
773 : }
774 :
775 0 : static bool triboxoverlap(const vec &radius, const vec &a, const vec &b, const vec &c)
776 : {
777 :
778 0 : static auto testaxis = [] (const vec &v0, const vec &v1, const vec &v2,
779 : const vec &e, const int &s, const int &t,
780 : const vec &radius)
781 : {
782 0 : float p = v0[s]*v1[t] - v0[t]*v1[s],
783 0 : q = v2[s]*e[t] - v2[t]*e[s],
784 0 : r = radius[s]*std::fabs(e[t]) + radius[t]*std::fabs(e[s]);
785 0 : if(p < q)
786 : {
787 0 : if(q < -r || p > r)
788 : {
789 0 : return false;
790 : }
791 : }
792 0 : else if(p < -r || q > r)
793 : {
794 0 : return false;
795 : }
796 0 : return true;
797 : };
798 :
799 0 : static auto testface = [] (const vec &a, const vec &b, const vec &c,
800 : const vec &ab, const vec &bc, const vec &ca,
801 : uint axis, const vec &radius)
802 : {
803 0 : if(a.v[axis] < b.v[axis])
804 : {
805 0 : if(b.v[axis] < c.v[axis])
806 : {
807 0 : if(c.v[axis] < -radius.v[axis] || a.v[axis] > radius.v[axis])
808 : {
809 0 : return false;
810 : }
811 : }
812 0 : else if(b.v[axis] < -radius.v[axis] || std::min(a.v[axis], c.v[axis]) > radius.v[axis])
813 : {
814 0 : return false;
815 : }
816 : }
817 0 : else if(a.v[axis] < c.v[axis])
818 : {
819 0 : if(c.v[axis] < -radius.v[axis] || b.v[axis] > radius.v[axis])
820 : {
821 0 : return false;
822 : }
823 : }
824 0 : else if(a.v[axis] < -radius.v[axis] || std::min(b.v[axis], c.v[axis]) > radius.v[axis])
825 : {
826 0 : return false;
827 : }
828 0 : return true;
829 : };
830 :
831 0 : vec ab = vec(b).sub(a),
832 0 : bc = vec(c).sub(b),
833 0 : ca = vec(a).sub(c);
834 :
835 0 : if(!testaxis(a, b, c, ab, 2, 1, radius)) {return false;};
836 0 : if(!testaxis(a, b, c, ab, 0, 2, radius)) {return false;};
837 0 : if(!testaxis(a, b, c, ab, 1, 0, radius)) {return false;};
838 :
839 0 : if(!testaxis(b, c, a, bc, 2, 1, radius)) {return false;};
840 0 : if(!testaxis(b, c, a, bc, 0, 2, radius)) {return false;};
841 0 : if(!testaxis(a, b, c, ab, 1, 0, radius)) {return false;};
842 :
843 0 : if(!testaxis(c, a, b, ca, 2, 1, radius)) {return false;};
844 0 : if(!testaxis(c, a, b, ca, 0, 2, radius)) {return false;};
845 0 : if(!testaxis(c, a, b, ca, 1, 0, radius)) {return false;};
846 :
847 0 : if(!testface(a, b, c, ab, bc, ca, 0, radius)) //x
848 : {
849 0 : return false;
850 : }
851 0 : else if(!testface(a, b, c, ab, bc, ca, 1, radius)) //y
852 : {
853 0 : return false;
854 : }
855 0 : else if(!testface(a, b, c, ab, bc, ca, 2, radius)) //z
856 : {
857 0 : return false;
858 : }
859 0 : return true;
860 : }
861 :
862 : //used in the tricollide templates below
863 : //returns true if physent is a player and passed vec is close enough to matter (determined by radius,pdist)
864 0 : bool BIH::playercollidecheck(const physent *d, float pdist, vec dir, vec n, vec radius) const
865 : {
866 0 : float a = 2*radius.z*(d->zmargin/(d->aboveeye+d->eyeheight)-(dir.z < 0 ? 1/3.0f : 1/4.0f)),
867 0 : b = (dir.x*n.x < 0 || dir.y*n.y < 0 ? -radius.x : 0);
868 0 : if(d->type==physent::PhysEnt_Player)
869 : {
870 0 : if(pdist < (dir.z*n.z < 0 ? a : b))
871 : {
872 0 : return true;
873 : }
874 : }
875 0 : return false;
876 : }
877 :
878 : template<>
879 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
880 : {
881 0 : if(m.tribbs[tidx].outside(bo, br))
882 : {
883 0 : return;
884 : }
885 0 : const mesh::tri &t = m.tris[tidx];
886 0 : vec a = m.getpos(t.vert[0]),
887 0 : b = m.getpos(t.vert[1]),
888 0 : c = m.getpos(t.vert[2]),
889 0 : zdir = vec(orient.rowz()).mul((radius.z - radius.x)/(m.scale()*m.scale()));
890 0 : if(trisegmentdistance(a, b, c, vec(center).sub(zdir), vec(center).add(zdir)) > (radius.x*radius.x)/(m.scale()*m.scale()))
891 : {
892 0 : return;
893 : }
894 0 : vec n;
895 0 : n.cross(a, b, c).normalize();
896 0 : float pdist = (n.dot(vec(center).sub(a)) - std::fabs(n.dot(zdir)))*m.scale() - radius.x;
897 0 : if(pdist > 0 || pdist <= dist)
898 : {
899 0 : return;
900 : }
901 0 : collideinside = true;
902 0 : n = orient.transformnormal(n).div(m.scale());
903 0 : if(!dir.iszero())
904 : {
905 0 : if(n.dot(dir) >= -cutoff*dir.magnitude())
906 : {
907 0 : return;
908 : }
909 : //see playercollidecheck defined above
910 0 : if(playercollidecheck(d, pdist, dir, n, radius))
911 : {
912 0 : return;
913 : }
914 : }
915 0 : dist = pdist;
916 0 : collidewall = n;
917 : }
918 :
919 : template<>
920 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
921 : {
922 0 : if(m.tribbs[tidx].outside(bo, br))
923 : {
924 0 : return;
925 : }
926 0 : const mesh::tri &t = m.tris[tidx];
927 0 : vec a = orient.transform(m.getpos(t.vert[0])),
928 0 : b = orient.transform(m.getpos(t.vert[1])),
929 0 : c = orient.transform(m.getpos(t.vert[2]));
930 0 : if(!triboxoverlap(radius, a, b, c))
931 : {
932 0 : return;
933 : }
934 0 : vec n;
935 0 : n.cross(a, b, c).normalize();
936 0 : float pdist = -n.dot(a),
937 0 : r = radius.absdot(n);
938 0 : if(std::fabs(pdist) > r)
939 : {
940 0 : return;
941 : }
942 0 : pdist -= r;
943 0 : if(pdist <= dist)
944 : {
945 0 : return;
946 : }
947 0 : collideinside = true;
948 0 : if(!dir.iszero())
949 : {
950 0 : if(n.dot(dir) >= -cutoff*dir.magnitude())
951 : {
952 0 : return;
953 : }
954 0 : if(playercollidecheck(d, pdist, dir, n, radius))
955 : {
956 0 : return;
957 : }
958 : }
959 0 : dist = pdist;
960 0 : collidewall = n;
961 : }
962 :
963 : template<int C>
964 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
965 : {
966 : node *stack[128];
967 0 : int stacksize = 0;
968 0 : ivec bmin = ivec(bo).sub(br),
969 0 : bmax = ivec(bo).add(br);
970 0 : for(;;)
971 : {
972 0 : int axis = curnode->axis();
973 0 : const int nearidx = 0,
974 0 : faridx = nearidx^1;
975 0 : int nearsplit = bmin[axis] - curnode->split[nearidx],
976 0 : farsplit = curnode->split[faridx] - bmax[axis];
977 :
978 0 : if(nearsplit > 0)
979 : {
980 0 : if(farsplit <= 0)
981 : {
982 0 : if(!curnode->isleaf(faridx))
983 : {
984 0 : curnode += curnode->childindex(faridx);
985 0 : continue;
986 : }
987 : else
988 : {
989 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
990 : }
991 : }
992 : }
993 0 : else if(curnode->isleaf(nearidx))
994 : {
995 0 : tricollide<C>(m, curnode->childindex(nearidx), d, dir, cutoff, center, radius, orient, dist, bo, br);
996 0 : if(farsplit <= 0)
997 : {
998 0 : if(!curnode->isleaf(faridx))
999 : {
1000 0 : curnode += curnode->childindex(faridx);
1001 0 : continue;
1002 : }
1003 : else
1004 : {
1005 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
1006 : }
1007 : }
1008 : }
1009 : else
1010 : {
1011 0 : if(farsplit <= 0)
1012 : {
1013 0 : if(!curnode->isleaf(faridx))
1014 : {
1015 0 : if(stacksize < static_cast<int>(sizeof(stack)/sizeof(stack[0])))
1016 : {
1017 0 : stack[stacksize++] = curnode + curnode->childindex(faridx);
1018 : }
1019 : else
1020 : {
1021 0 : collide<C>(m, d, dir, cutoff, center, radius, orient, dist, &nodes[curnode->childindex(nearidx)], bo, br);
1022 0 : curnode += curnode->childindex(faridx);
1023 0 : continue;
1024 : }
1025 : }
1026 : else
1027 : {
1028 0 : tricollide<C>(m, curnode->childindex(faridx), d, dir, cutoff, center, radius, orient, dist, bo, br);
1029 : }
1030 : }
1031 0 : curnode += curnode->childindex(nearidx);
1032 0 : continue;
1033 : }
1034 0 : if(stacksize <= 0)
1035 : {
1036 0 : return;
1037 : }
1038 0 : curnode = stack[--stacksize];
1039 : }
1040 : }
1041 :
1042 0 : bool BIH::ellipsecollide(const physent *d, const vec &dir, float cutoff, const vec &o, int yaw, int pitch, int roll, float scale) const
1043 : {
1044 0 : if(!numnodes)
1045 : {
1046 0 : return false;
1047 : }
1048 0 : vec center(d->o.x, d->o.y, d->o.z + 0.5f*(d->aboveeye - d->eyeheight)),
1049 0 : radius(d->radius, d->radius, 0.5f*(d->eyeheight + d->aboveeye));
1050 0 : center.sub(o);
1051 0 : if(scale != 1)
1052 : {
1053 0 : float invscale = 1/scale;
1054 0 : center.mul(invscale);
1055 0 : radius.mul(invscale);
1056 : }
1057 0 : matrix3 orient;
1058 0 : orient.identity();
1059 0 : if(yaw)
1060 : {
1061 0 : orient.rotate_around_z(sincosmod360(yaw));
1062 : }
1063 0 : if(pitch)
1064 : {
1065 0 : orient.rotate_around_x(sincosmod360(pitch));
1066 : }
1067 0 : if(roll)
1068 : {
1069 0 : orient.rotate_around_y(sincosmod360(-roll));
1070 : }
1071 0 : vec bo = orient.transposedtransform(center),
1072 0 : br = orient.abstransposedtransform(radius);
1073 0 : if(bo.x + br.x < bbmin.x || bo.y + br.y < bbmin.y || bo.z + br.z < bbmin.z ||
1074 0 : bo.x - br.x > bbmax.x || bo.y - br.y > bbmax.y || bo.z - br.z > bbmax.z)
1075 : {
1076 0 : return false;
1077 : }
1078 0 : ivec imin = ivec::floor(vec(bo).sub(br)),
1079 0 : imax = ivec::ceil(vec(bo).add(br)),
1080 0 : icenter = imin.add(imax).div(2),
1081 0 : iradius = imax.sub(imin).add(1).div(2);
1082 :
1083 0 : float dist = -1e10f;
1084 0 : for(const mesh &m : meshes)
1085 : {
1086 0 : if(!(m.flags&Mesh_Collide) || m.flags&Mesh_NoClip)
1087 : {
1088 0 : continue;
1089 : }
1090 0 : matrix4x3 morient;
1091 0 : morient.mul(orient, m.xform);
1092 0 : collide<Collide_Ellipse>(m, d, dir, cutoff, m.invxform().transform(bo), radius, morient, dist, m.nodes, icenter, iradius);
1093 : }
1094 0 : return dist > maxcollidedistance;
1095 : }
1096 :
1097 0 : bool BIH::boxcollide(const physent *d, const vec &dir, float cutoff, const vec &o, int yaw, int pitch, int roll, float scale) const
1098 : {
1099 0 : if(!numnodes)
1100 : {
1101 0 : return false;
1102 : }
1103 0 : vec center(d->o.x, d->o.y, d->o.z + 0.5f*(d->aboveeye - d->eyeheight)),
1104 0 : radius(d->xradius, d->yradius, 0.5f*(d->eyeheight + d->aboveeye));
1105 0 : center.sub(o);
1106 0 : if(scale != 1)
1107 : {
1108 0 : float invscale = 1/scale;
1109 0 : center.mul(invscale);
1110 0 : radius.mul(invscale);
1111 : }
1112 0 : matrix3 orient;
1113 0 : orient.identity();
1114 0 : if(yaw)
1115 : {
1116 0 : orient.rotate_around_z(sincosmod360(yaw));
1117 : }
1118 0 : if(pitch)
1119 : {
1120 0 : orient.rotate_around_x(sincosmod360(pitch));
1121 : }
1122 0 : if(roll)
1123 : {
1124 0 : orient.rotate_around_y(sincosmod360(-roll));
1125 : }
1126 0 : vec bo = orient.transposedtransform(center),
1127 0 : br = orient.abstransposedtransform(vec(d->radius, d->radius, radius.z));
1128 0 : if(bo.x + br.x < bbmin.x || bo.y + br.y < bbmin.y || bo.z + br.z < bbmin.z ||
1129 0 : bo.x - br.x > bbmax.x || bo.y - br.y > bbmax.y || bo.z - br.z > bbmax.z)
1130 : {
1131 0 : return false;
1132 : }
1133 0 : ivec imin = ivec::floor(vec(bo).sub(br)),
1134 0 : imax = ivec::ceil(vec(bo).add(br)),
1135 0 : icenter = ivec(imin).add(imax).div(2),
1136 0 : iradius = ivec(imax).sub(imin).add(1).div(2);
1137 0 : matrix3 drot, dorient;
1138 0 : drot.setyaw(d->yaw/RAD);
1139 0 : vec ddir = drot.transform(dir),
1140 0 : dcenter = drot.transform(center).neg();
1141 0 : dorient.mul(drot, orient);
1142 0 : float dist = -1e10f;
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);
1152 : }
1153 0 : if(dist > maxcollidedistance)
1154 : {
1155 0 : collidewall = drot.transposedtransform(collidewall);
1156 0 : return true;
1157 : }
1158 0 : return false;
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 : }
|
