src/engine/bih.cpp

   1 #include "pch.h"
   2 #include "engine.h"
   3
   4 bool BIH::triintersect(tri &tri, const vec &o, const vec &ray, float maxdist, float &dist, int mode)
   5 {
   6     vec p;
   7     p.cross(ray, tri.c);
   8     float det = tri.b.dot(p);
   9     if(det == 0) return false;
  10     vec r(o);
  11     r.sub(tri.a);
  12     float u = r.dot(p) / det;
  13     if(u < 0 || u > 1) return false;
  14     vec q;
  15     q.cross(r, tri.b);
  16     float v = ray.dot(q) / det;
  17     if(v < 0 || u + v > 1) return false;
  18     float f = tri.c.dot(q) / det;
  19     if(f < 0 || f > maxdist) return false;
  20     if(tri.tex && (mode&RAY_ALPHAPOLY)==RAY_ALPHAPOLY)
  21     {
  22         if(!tri.tex->alphamask)
  23         {
  24             loadalphamask(tri.tex);
  25             if(!tri.tex->alphamask) { dist = f; return true; }
  26         }
  27         float s = tri.tc[0] + u*(tri.tc[2] - tri.tc[0]) + v*(tri.tc[4] - tri.tc[0]),
  28               t = tri.tc[1] + u*(tri.tc[3] - tri.tc[1]) + v*(tri.tc[5] - tri.tc[1]);
  29         int si = int(s*tri.tex->xs), ti = int(t*tri.tex->ys);
  30         if(!(tri.tex->alphamask[ti*((tri.tex->xs+7)/8) + si/8] & (1<<(si%8)))) return false;
  31     }
  32     dist = f;
  33     return true;
  34 }
  35
  36 struct BIHStack
  37 {
  38     BIHNode *node;
  39     float tmin, tmax;
  40 };
  41
  42 bool BIH::traverse(const vec &o, const vec &ray, float maxdist, float &dist, int mode)
  43 {
  44     if(!numnodes) return false;
  45
  46     vec invray(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f);
  47     float tmin, tmax;
  48     float t1 = (bbmin.x - o.x)*invray.x,
  49           t2 = (bbmax.x - o.x)*invray.x;
  50     if(invray.x > 0) { tmin = t1; tmax = t2; } else { tmin = t2; tmax = t1; }
  51     t1 = (bbmin.y - o.y)*invray.y;
  52     t2 = (bbmax.y - o.y)*invray.y;
  53     if(invray.y > 0) { tmin = max(tmin, t1); tmax = min(tmax, t2); } else { tmin = max(tmin, t2); tmax = min(tmax, t1); }
  54     t1 = (bbmin.z - o.z)*invray.z;
  55     t2 = (bbmax.z - o.z)*invray.z;
  56     if(invray.z > 0) { tmin = max(tmin, t1); tmax = min(tmax, t2); } else { tmin = max(tmin, t2); tmax = min(tmax, t1); }
  57     if(tmin >= maxdist || tmin>=tmax) return false;
  58     tmax = min(tmax, maxdist);
  59
  60     static vector<BIHStack> stack;
  61     stack.setsizenodelete(0);
  62
  63     ivec order(ray.x>0 ? 0 : 1, ray.y>0 ? 0 : 1, ray.z>0 ? 0 : 1);
  64     BIHNode *curnode = &nodes[0];
  65     for(;;)
  66     {
  67         int axis = curnode->axis();
  68         int nearidx = order[axis], faridx = nearidx^1;
  69         float nearsplit = (curnode->split[nearidx] - o[axis])*invray[axis],
  70               farsplit = (curnode->split[faridx] - o[axis])*invray[axis];
  71
  72         if(nearsplit <= tmin)
  73         {
  74             if(farsplit < tmax)
  75             {
  76                 if(!curnode->isleaf(faridx))
  77                 {
  78                     curnode = &nodes[curnode->childindex(faridx)];
  79                     tmin = max(tmin, farsplit);
  80                     continue;
  81                 }
  82                 else if(triintersect(tris[curnode->childindex(faridx)], o, ray, maxdist, dist, mode)) return true;
  83             }
  84         }
  85         else if(curnode->isleaf(nearidx))
  86         {
  87             if(triintersect(tris[curnode->childindex(nearidx)], o, ray, maxdist, dist, mode)) return true;
  88             if(farsplit < tmax)
  89             {
  90                 if(!curnode->isleaf(faridx))
  91                 {
  92                     curnode = &nodes[curnode->childindex(faridx)];
  93                     tmin = max(tmin, farsplit);
  94                     continue;
  95                 }
  96                 else if(triintersect(tris[curnode->childindex(faridx)], o, ray, maxdist, dist, mode)) return true;
  97             }
  98         }
  99         else
 100         {
 101             if(farsplit < tmax)
 102             {
 103                 if(!curnode->isleaf(faridx))
 104                 {
 105                     BIHStack &save = stack.add();
 106                     save.node = &nodes[curnode->childindex(faridx)];
 107                     save.tmin = max(tmin, farsplit);
 108                     save.tmax = tmax;
 109                 }
 110                 else if(triintersect(tris[curnode->childindex(faridx)], o, ray, maxdist, dist, mode)) return true;
 111             }
 112             curnode = &nodes[curnode->childindex(nearidx)];
 113             tmax = min(tmax, nearsplit);
 114             continue;
 115         }
 116         if(stack.empty()) return false;
 117         BIHStack &restore = stack.pop();
 118         curnode = restore.node;
 119         tmin = restore.tmin;
 120         tmax = restore.tmax;
 121     }
 122 }
 123
 124 static BIH::tri *sorttris = NULL;
 125 static int sortaxis = 0;
 126
 127 static int bihsort(const ushort *x, const ushort *y)
 128 {
 129     BIH::tri &xtri = sorttris[*x], &ytri = sorttris[*y];
 130     float xmin = min(xtri.a[sortaxis], min(xtri.b[sortaxis], xtri.c[sortaxis])),
 131           ymin = min(ytri.a[sortaxis], min(ytri.b[sortaxis], ytri.c[sortaxis]));
 132     if(xmin < ymin) return -1;
 133     if(xmin > ymin) return 1;
 134     return 0;
 135 }
 136
 137 void BIH::build(vector<BIHNode> &buildnodes, ushort *indices, int numindices, int depth)
 138 {
 139     maxdepth = max(maxdepth, depth);
 140
 141     vec vmin(1e16f, 1e16f, 1e16f), vmax(-1e16f, -1e16f, -1e16f);
 142     loopi(numindices)
 143     {
 144         tri &tri = tris[indices[i]];
 145         loopk(3)
 146         {
 147             float amin = min(tri.a[k], min(tri.b[k], tri.c[k])),
 148                   amax = max(tri.a[k], max(tri.b[k], tri.c[k]));
 149             vmin[k] = min(vmin[k], amin);
 150             vmax[k] = max(vmax[k], amax);
 151         }
 152     }
 153     if(depth==1)
 154     {
 155         bbmin = vmin;
 156         bbmax = vmax;
 157     }
 158
 159     int axis = 2;
 160     loopk(2) if(vmax[k] - vmin[k] > vmax[axis] - vmin[axis]) axis = k;
 161
 162 /*
 163     sorttris = tris;
 164     sortaxis = axis;
 165     qsort(indices, numindices, sizeof(ushort), (int (__cdecl *)(const void *, const void *))bihsort);
 166     tri &median = tris[numindices/2];
 167     float split = min(median.a[axis], min(median.b[axis], median.c[axis]));
 168 */
 169
 170     float split = 0.5f*(vmax[axis] + vmin[axis]);
 171
 172     float splitleft = SHRT_MIN, splitright = SHRT_MAX;
 173     int left, right;
 174     for(left = 0, right = numindices; left < right;)
 175     {
 176         tri &tri = tris[indices[left]];
 177         float amin = min(tri.a[axis], min(tri.b[axis], tri.c[axis])),
 178               amax = max(tri.a[axis], max(tri.b[axis], tri.c[axis]));
 179         if(max(split - amin, 0) > max(amax - split, 0))
 180         {
 181             ++left;
 182             splitleft = max(splitleft, amax);
 183         }
 184         else
 185         {
 186             --right;
 187             swap(ushort, indices[left], indices[right]);
 188             splitright = min(splitright, amin);
 189         }
 190     }
 191
 192     if(!left || right==numindices)
 193     {
 194         sorttris = tris;
 195         sortaxis = axis;
 196         qsort(indices, numindices, sizeof(ushort), (int (__cdecl *)(const void *, const void *))bihsort);
 197
 198         left = right = numindices/2;
 199         splitleft = SHRT_MIN;
 200         splitright = SHRT_MAX;
 201         loopi(numindices)
 202         {
 203             tri &tri = tris[indices[i]];
 204             if(i < left) splitleft = max(splitleft, max(tri.a[axis], max(tri.b[axis], tri.c[axis])));
 205             else splitright = min(splitright, min(tri.a[axis], min(tri.b[axis], tri.c[axis])));
 206         }
 207     }
 208
 209     int node = buildnodes.length();
 210     buildnodes.add();
 211     buildnodes[node].split[0] = short(ceil(splitleft));
 212     buildnodes[node].split[1] = short(floor(splitright));
 213
 214     if(left==1) buildnodes[node].child[0] = (axis<<14) | indices[0];
 215     else
 216     {
 217         buildnodes[node].child[0] = (axis<<14) | buildnodes.length();
 218         build(buildnodes, indices, left, depth+1);
 219     }
 220
 221     if(numindices-right==1) buildnodes[node].child[1] = (1<<15) | (left==1 ? 1<<14 : 0) | indices[right];
 222     else
 223     {
 224         buildnodes[node].child[1] = (left==1 ? 1<<14 : 0) | buildnodes.length();
 225         build(buildnodes, &indices[right], numindices-right, depth+1);
 226     }
 227 }
 228
 229 BIH::BIH(int _numtris, tri *_tris)
 230 {
 231     numtris = _numtris;
 232     if(!numtris)
 233     {
 234         tris = NULL;
 235         numnodes = 0;
 236         nodes = NULL;
 237         maxdepth = 0;
 238         return;
 239     }
 240
 241     tris = new tri[numtris];
 242     memcpy(tris, _tris, numtris*sizeof(tri));
 243
 244     vector<BIHNode> buildnodes;
 245     ushort *indices = new ushort[numtris];
 246     loopi(numtris) indices[i] = i;
 247
 248     maxdepth = 0;
 249
 250     build(buildnodes, indices, numtris);
 251
 252     delete[] indices;
 253
 254     numnodes = buildnodes.length();
 255     nodes = new BIHNode[numnodes];
 256     memcpy(nodes, buildnodes.getbuf(), numnodes*sizeof(BIHNode));
 257
 258     // convert tri.b/tri.c to edges
 259     loopi(numtris)
 260     {
 261         tri &tri = tris[i];
 262         tri.b.sub(tri.a);
 263         tri.c.sub(tri.a);
 264     }
 265 }
 266
 267 static inline void yawray(vec &o, vec &ray, float angle)
 268 {
 269     angle *= RAD;
 270     float c = cosf(angle), s = sinf(angle),
 271           ox = o.x, oy = o.y,
 272           rx = ox+ray.x, ry = oy+ray.y;
 273     o.x = ox*c - oy*s;
 274     o.y = oy*c + ox*s;
 275     ray.x = rx*c - ry*s - o.x;
 276     ray.y = ry*c + rx*s - o.y;
 277     ray.normalize();
 278 }
 279
 280 bool mmintersect(const extentity &e, const vec &o, const vec &ray, float maxdist, int mode, float &dist)
 281 {
 282     model *m = loadmodel(NULL, e.attr2);
 283     if(!m) return false;
 284     if(mode&RAY_SHADOW)
 285     {
 286         if(!m->shadow || checktriggertype(e.attr3, TRIG_COLLIDE|TRIG_DISAPPEAR)) return false;
 287     }
 288     else if((mode&RAY_ENTS)!=RAY_ENTS && !m->collide) return false;
 289     if(!m->bih && !m->setBIH()) return false;
 290     if(!maxdist) maxdist = 1e16f;
 291     vec yo(o);
 292     yo.sub(e.o);
 293     float yaw = -180.0f-(float)((e.attr1+7)-(e.attr1+7)%15);
 294     vec yray(ray);
 295     if(yaw != 0) yawray(yo, yray, yaw);
 296     return m->bih->traverse(yo, yray, maxdist, dist, mode);
 297 }
 298