From 0a1172b75f571685c264a8b9d8ee224bbf11381f Mon Sep 17 00:00:00 2001 From: xolatile Date: Wed, 6 Aug 2025 22:54:55 +0200 Subject: Please do not hate me, it makes sense... --- src/engine/bih.cpp | 129 +++++++++++++++++------------------------------------ 1 file changed, 40 insertions(+), 89 deletions(-) (limited to 'src/engine/bih.cpp') diff --git a/src/engine/bih.cpp b/src/engine/bih.cpp index c983805..e406008 100644 --- a/src/engine/bih.cpp +++ b/src/engine/bih.cpp @@ -1,13 +1,11 @@ #include "engine.h" -bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, float maxdist, float &dist, int mode) -{ +bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, float maxdist, float &dist, int mode) { const tri &t = m.tris[tidx]; vec a = m.getpos(t.vert[0]), b = m.getpos(t.vert[1]).sub(a), c = m.getpos(t.vert[2]).sub(a), n = vec().cross(b, c), r = vec(a).sub(mo), e = vec().cross(r, mray); float det = mray.dot(n), v, w, f; - if(det >= 0) - { + if(det >= 0) { if(!(mode&RAY_SHADOW) && m.flags&MESH_CULLFACE) return false; v = e.dot(c); if(v < 0 || v > det) return false; @@ -16,8 +14,7 @@ bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, f = r.dot(n)*m.scale; if(f < 0 || f > maxdist*det || !det) return false; } - else - { + else { v = e.dot(c); if(v > 0 || v < det) return false; w = -e.dot(b); @@ -26,8 +23,7 @@ bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, if(f > 0 || f < maxdist*det) return false; } float invdet = 1/det; - if(m.flags&MESH_ALPHA && (mode&RAY_ALPHAPOLY)==RAY_ALPHAPOLY && (m.tex->alphamask || (lightmapping <= 1 && loadalphamask(m.tex)))) - { + if(m.flags&MESH_ALPHA && (mode&RAY_ALPHAPOLY)==RAY_ALPHAPOLY && (m.tex->alphamask || (lightmapping <= 1 && loadalphamask(m.tex)))) { vec2 at = m.gettc(t.vert[0]), bt = m.gettc(t.vert[1]).sub(at).mul(v*invdet), ct = m.gettc(t.vert[2]).sub(at).mul(w*invdet); at.add(bt).add(ct); int si = clamp(int(m.tex->xs * at.x), 0, m.tex->xs-1), @@ -38,31 +34,24 @@ bool BIH::triintersect(const mesh &m, int tidx, const vec &mo, const vec &mray, return true; } -struct traversestate -{ +struct traversestate { BIH::node *node; float tmin, tmax; }; -inline bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec &invray, float maxdist, float &dist, int mode, node *curnode, float tmin, float tmax) -{ +inline bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec &invray, float maxdist, float &dist, int mode, node *curnode, float tmin, float tmax) { traversestate stack[128]; int stacksize = 0; ivec order(ray.x>0 ? 0 : 1, ray.y>0 ? 0 : 1, ray.z>0 ? 0 : 1); vec mo = m.invxform.transform(o), mray = m.invxformnorm.transform(ray); - for(;;) - { + for(;;) { int axis = curnode->axis(); int nearidx = order[axis], faridx = nearidx^1; float nearsplit = (curnode->split[nearidx] - o[axis])*invray[axis], farsplit = (curnode->split[faridx] - o[axis])*invray[axis]; - - if(nearsplit <= tmin) - { - if(farsplit < tmax) - { - if(!curnode->isleaf(faridx)) - { + if(nearsplit <= tmin) { + if(farsplit < tmax) { + if(!curnode->isleaf(faridx)) { curnode += curnode->childindex(faridx); tmin = max(tmin, farsplit); continue; @@ -70,13 +59,10 @@ inline bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec else if(triintersect(m, curnode->childindex(faridx), mo, mray, maxdist, dist, mode)) return true; } } - else if(curnode->isleaf(nearidx)) - { + else if(curnode->isleaf(nearidx)) { if(triintersect(m, curnode->childindex(nearidx), mo, mray, maxdist, dist, mode)) return true; - if(farsplit < tmax) - { - if(!curnode->isleaf(faridx)) - { + if(farsplit < tmax) { + if(!curnode->isleaf(faridx)) { curnode += curnode->childindex(faridx); tmin = max(tmin, farsplit); continue; @@ -84,21 +70,16 @@ inline bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec else if(triintersect(m, curnode->childindex(faridx), mo, mray, maxdist, dist, mode)) return true; } } - else - { - if(farsplit < tmax) - { - if(!curnode->isleaf(faridx)) - { - if(stacksize < int(sizeof(stack)/sizeof(stack[0]))) - { + else { + if(farsplit < tmax) { + if(!curnode->isleaf(faridx)) { + if(stacksize < int(sizeof(stack)/sizeof(stack[0]))) { traversestate &save = stack[stacksize++]; save.node = curnode + curnode->childindex(faridx); save.tmin = max(tmin, farsplit); save.tmax = tmax; } - else - { + else { if(traverse(m, o, ray, invray, maxdist, dist, mode, curnode + curnode->childindex(nearidx), tmin, min(tmax, nearsplit))) return true; curnode += curnode->childindex(faridx); tmin = max(tmin, farsplit); @@ -119,11 +100,9 @@ inline bool BIH::traverse(const mesh &m, const vec &o, const vec &ray, const vec } } -inline bool BIH::traverse(const vec &o, const vec &ray, float maxdist, float &dist, int mode) -{ +inline bool BIH::traverse(const vec &o, const vec &ray, float maxdist, float &dist, int mode) { vec invray(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f); - loopi(nummeshes) - { + loopi(nummeshes) { mesh &m = meshes[i]; if(!(mode&RAY_SHADOW) && m.flags&MESH_NOCLIP) continue; float t1 = (m.bbmin.x - o.x)*invray.x, @@ -142,34 +121,28 @@ inline bool BIH::traverse(const vec &o, const vec &ray, float maxdist, float &di return false; } -void BIH::build(mesh &m, ushort *indices, int numindices, const ivec &vmin, const ivec &vmax) -{ +void BIH::build(mesh &m, ushort *indices, int numindices, const ivec &vmin, const ivec &vmax) { int axis = 2; loopk(2) if(vmax[k] - vmin[k] > vmax[axis] - vmin[axis]) axis = k; - ivec leftmin, leftmax, rightmin, rightmax; int splitleft, splitright; int left, right; - loopk(3) - { + loopk(3) { leftmin = rightmin = ivec(INT_MAX, INT_MAX, INT_MAX); leftmax = rightmax = ivec(INT_MIN, INT_MIN, INT_MIN); int split = (vmax[axis] + vmin[axis])/2; - for(left = 0, right = numindices, splitleft = SHRT_MIN, splitright = SHRT_MAX; left < right;) - { + for(left = 0, right = numindices, splitleft = SHRT_MIN, splitright = SHRT_MAX; left < right;) { const tribb &tri = m.tribbs[indices[left]]; ivec trimin = ivec(tri.center).sub(ivec(tri.radius)), trimax = ivec(tri.center).add(ivec(tri.radius)); int amin = trimin[axis], amax = trimax[axis]; - if(max(split - amin, 0) > max(amax - split, 0)) - { + if(max(split - amin, 0) > max(amax - split, 0)) { ++left; splitleft = max(splitleft, amax); leftmin.min(trimin); leftmax.max(trimax); } - else - { + else { --right; swap(indices[left], indices[right]); splitright = min(splitright, amin); @@ -180,68 +153,55 @@ void BIH::build(mesh &m, ushort *indices, int numindices, const ivec &vmin, cons if(left > 0 && right < numindices) break; axis = (axis+1)%3; } - - if(!left || right==numindices) - { + if(!left || right==numindices) { leftmin = rightmin = ivec(INT_MAX, INT_MAX, INT_MAX); leftmax = rightmax = ivec(INT_MIN, INT_MIN, INT_MIN); left = right = numindices/2; splitleft = SHRT_MIN; splitright = SHRT_MAX; - loopi(numindices) - { + loopi(numindices) { const tribb &tri = m.tribbs[indices[i]]; ivec trimin = ivec(tri.center).sub(ivec(tri.radius)), trimax = ivec(tri.center).add(ivec(tri.radius)); - if(i < left) - { + if(i < left) { splitleft = max(splitleft, trimax[axis]); leftmin.min(trimin); leftmax.max(trimax); } - else - { + else { splitright = min(splitright, trimin[axis]); rightmin.min(trimin); rightmax.max(trimax); } } } - int offset = m.numnodes++; node &curnode = m.nodes[offset]; curnode.split[0] = short(splitleft); curnode.split[1] = short(splitright); - if(left==1) curnode.child[0] = (axis<<14) | indices[0]; - else - { + else { curnode.child[0] = (axis<<14) | (m.numnodes - offset); build(m, indices, left, leftmin, leftmax); } - if(numindices-right==1) curnode.child[1] = (1<<15) | (left==1 ? 1<<14 : 0) | indices[right]; - else - { + else { curnode.child[1] = (left==1 ? 1<<14 : 0) | (m.numnodes - offset); build(m, &indices[right], numindices-right, rightmin, rightmax); } } BIH::BIH(vector &buildmeshes) - : meshes(NULL), nummeshes(0), nodes(NULL), numnodes(0), tribbs(NULL), numtris(0), bbmin(1e16f, 1e16f, 1e16f), bbmax(-1e16f, -1e16f, -1e16f), center(0, 0, 0), radius(0), entradius(0) -{ + : meshes(NULL), nummeshes(0), nodes(NULL), numnodes(0), tribbs(NULL), numtris(0), bbmin(1e16f, 1e16f, 1e16f), bbmax(-1e16f, -1e16f, -1e16f), center(0, 0, 0), radius(0), entradius(0) { if(buildmeshes.empty()) return; loopv(buildmeshes) numtris += buildmeshes[i].numtris; if(!numtris) return; - nummeshes = buildmeshes.length(); meshes = new mesh[nummeshes]; memcpy(meshes, buildmeshes.getbuf(), sizeof(mesh)*buildmeshes.length()); tribbs = new tribb[numtris]; tribb *dsttri = tribbs; - loopi(nummeshes) - { + loopi(nummeshes) { mesh &m = meshes[i]; m.scale = m.xform.a.magnitude(); m.invscale = 1/m.scale; @@ -253,8 +213,7 @@ BIH::BIH(vector &buildmeshes) m.tribbs = dsttri; const tri *srctri = m.tris; vec mmin(1e16f, 1e16f, 1e16f), mmax(-1e16f, -1e16f, -1e16f); - loopj(m.numtris) - { + loopj(m.numtris) { vec s0 = m.getpos(srctri->vert[0]), s1 = m.getpos(srctri->vert[1]), s2 = m.getpos(srctri->vert[2]), v0 = m.xform.transform(s0), v1 = m.xform.transform(s1), v2 = m.xform.transform(s2), vmin = vec(v0).min(v1).min(v2), @@ -267,8 +226,7 @@ BIH::BIH(vector &buildmeshes) ++srctri; ++dsttri; } - loopk(3) if(fabs(mmax[k] - mmin[k]) < 0.125f) - { + loopk(3) if(fabs(mmax[k] - mmin[k]) < 0.125f) { float mid = (mmin[k] + mmax[k]) / 2; mmin[k] = mid - 0.0625f; mmax[k] = mid + 0.0625f; @@ -278,16 +236,13 @@ BIH::BIH(vector &buildmeshes) bbmin.min(mmin); bbmax.max(mmax); } - center = vec(bbmin).add(bbmax).mul(0.5f); radius = vec(bbmax).sub(bbmin).mul(0.5f).magnitude(); entradius = max(bbmin.squaredlen(), bbmax.squaredlen()); - nodes = new node[numtris]; node *curnode = nodes; ushort *indices = new ushort[numtris]; - loopi(nummeshes) - { + loopi(nummeshes) { mesh &m = meshes[i]; m.nodes = curnode; loopj(m.numtris) indices[j] = j; @@ -298,19 +253,16 @@ BIH::BIH(vector &buildmeshes) numnodes = int(curnode - nodes); } -BIH::~BIH() -{ +BIH::~BIH() { delete[] meshes; delete[] nodes; delete[] tribbs; } -bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist, int mode, float &dist) -{ +bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist, int mode, float &dist) { model *m = loadmapmodel(e.attr2); if(!m) return false; - if(mode&RAY_SHADOW) - { + if(mode&RAY_SHADOW) { if(!m->shadow || e.flags&EF_NOSHADOW) return false; } else if((mode&RAY_ENTS)!=RAY_ENTS && (!m->collide || e.flags&EF_NOCOLLIDE)) return false; @@ -319,8 +271,7 @@ bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist float v = mo.dot(mray), inside = m->bih->entradius - mo.squaredlen(); if((inside < 0 && v > 0) || inside + v*v < 0) return false; int yaw = e.attr1; - if(yaw != 0) - { + if(yaw != 0) { const vec2 &rot = sincosmod360(-yaw); mo.rotate_around_z(rot); mray.rotate_around_z(rot); -- cgit v1.2.3