1 struct skelbih
2 {
3 struct node
4 {
5 short split[2];
6 ushort child[2];
7
axisskelbih::node8 int axis() const { return child[0]>>14; }
childindexskelbih::node9 int childindex(int which) const { return child[which]&0x3FFF; }
isleafskelbih::node10 bool isleaf(int which) const { return (child[1]&(1<<(14+which)))!=0; }
11 };
12
13 struct tri : skelmodel::tri
14 {
15 uchar mesh, id;
16 };
17
18 node *nodes;
19 int numnodes;
20 tri *tris;
21
22 vec bbmin, bbmax;
23
24 skelbih(skelmodel::skelmeshgroup *m, int numtris, tri *tris);
25
~skelbihskelbih26 ~skelbih()
27 {
28 DELETEA(nodes);
29 }
30
31 bool triintersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, int tidx, const vec &o, const vec &ray);
32
33 void build(skelmodel::skelmeshgroup *m, ushort *indices, int numindices, const vec &vmin, const vec &vmax);
34
35 void intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const vec &o, const vec &ray, const vec &invray, node *curnode, float tmin, float tmax);
36 void intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const vec &o, const vec &ray);
37
calccenterskelbih38 vec calccenter() const
39 {
40 return vec(bbmin).add(bbmax).mul(0.5f);
41 }
42
calcradiusskelbih43 float calcradius() const
44 {
45 return vec(bbmax).sub(bbmin).mul(0.5f).magnitude();
46 }
47 };
48
49 #define SKELTRIINTERSECT(a, b, c) \
50 vec eb = vec(b).sub(a), ec = vec(c).sub(a); \
51 vec p; \
52 p.cross(ray, ec); \
53 float det = eb.dot(p); \
54 if(det == 0) return false; \
55 vec r = vec(o).sub(a); \
56 float u = r.dot(p) / det; \
57 if(u < 0 || u > 1) return false; \
58 vec q; \
59 q.cross(r, eb); \
60 float v = ray.dot(q) / det; \
61 if(v < 0 || u + v > 1) return false; \
62 float f = ec.dot(q) / det; \
63 if(f < 0 || f*skelmodel::intersectscale > skelmodel::intersectdist) return false; \
64 if(!(skelmodel::intersectmode&RAY_SHADOW) && tm->noclip) return false; \
65 if((skelmodel::intersectmode&RAY_ALPHAPOLY)==RAY_ALPHAPOLY) \
66 { \
67 Texture *tex = s[t.mesh].tex; \
68 if(tex->type&Texture::ALPHA && (tex->alphamask || loadalphamask(tex))) \
69 { \
70 int si = clamp(int(tex->xs * (va.tc.x + u*(vb.tc.x - va.tc.x) + v*(vc.tc.x - va.tc.x))), 0, tex->xs-1), \
71 ti = clamp(int(tex->ys * (va.tc.y + u*(vb.tc.y - va.tc.y) + v*(vc.tc.y - va.tc.y))), 0, tex->ys-1); \
72 if(!(tex->alphamask[ti*((tex->xs+7)/8) + si/8] & (1<<(si%8)))) return false; \
73 } \
74 } \
75 skelmodel::intersectdist = f*skelmodel::intersectscale; \
76 skelmodel::intersectresult = t.id&0x80 ? -1 : t.id; \
77 return true;
78
triintersect(skelmodel::skelmeshgroup * m,skelmodel::skin * s,int tidx,const vec & o,const vec & ray)79 bool skelbih::triintersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, int tidx, const vec &o, const vec &ray)
80 {
81 const tri &t = tris[tidx];
82 skelmodel::skelmesh *tm = (skelmodel::skelmesh *)m->meshes[t.mesh];
83 const skelmodel::vert &va = tm->verts[t.vert[0]], &vb = tm->verts[t.vert[1]], &vc = tm->verts[t.vert[2]];
84 SKELTRIINTERSECT(va.pos, vb.pos, vc.pos)
85 }
86
87 struct skelbihstack
88 {
89 skelbih::node *node;
90 float tmin, tmax;
91 };
92
intersect(skelmodel::skelmeshgroup * m,skelmodel::skin * s,const vec & o,const vec & ray,const vec & invray,node * curnode,float smin,float smax)93 inline void skelbih::intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const vec &o, const vec &ray, const vec &invray, node *curnode, float smin, float smax)
94 {
95 skelbihstack stack[128];
96 int stacksize = 0;
97 ivec order(ray.x>0 ? 0 : 1, ray.y>0 ? 0 : 1, ray.z>0 ? 0 : 1);
98 float tmin = smin, tmax = smax;
99 for(;;)
100 {
101 int axis = curnode->axis();
102 int nearidx = order[axis], faridx = nearidx^1;
103 float nearsplit = (curnode->split[nearidx] - o[axis])*invray[axis],
104 farsplit = (curnode->split[faridx] - o[axis])*invray[axis];
105
106 if(nearsplit <= tmin)
107 {
108 if(farsplit < tmax)
109 {
110 if(!curnode->isleaf(faridx))
111 {
112 curnode += curnode->childindex(faridx);
113 tmin = max(tmin, farsplit);
114 continue;
115 }
116 else if(triintersect(m, s, curnode->childindex(faridx), o, ray))
117 smax = min(smax, skelmodel::intersectdist/skelmodel::intersectscale);
118 }
119 }
120 else if(curnode->isleaf(nearidx))
121 {
122 if(triintersect(m, s, curnode->childindex(nearidx), o, ray))
123 {
124 smax = min(smax, skelmodel::intersectdist/skelmodel::intersectscale);
125 tmax = min(tmax, smax);
126 }
127 if(farsplit < tmax)
128 {
129 if(!curnode->isleaf(faridx))
130 {
131 curnode += curnode->childindex(faridx);
132 tmin = max(tmin, farsplit);
133 continue;
134 }
135 else if(triintersect(m, s, curnode->childindex(faridx), o, ray))
136 smax = min(smax, skelmodel::intersectdist/skelmodel::intersectscale);
137 }
138 }
139 else
140 {
141 if(farsplit < tmax)
142 {
143 if(!curnode->isleaf(faridx))
144 {
145 if(stacksize < int(sizeof(stack)/sizeof(stack[0])))
146 {
147 skelbihstack &save = stack[stacksize++];
148 save.node = curnode + curnode->childindex(faridx);
149 save.tmin = max(tmin, farsplit);
150 save.tmax = tmax;
151 }
152 else
153 {
154 intersect(m, s, o, ray, invray, curnode + curnode->childindex(nearidx), tmin, tmax);
155 curnode += curnode->childindex(faridx);
156 tmin = max(tmin, farsplit);
157 }
158 }
159 else if(triintersect(m, s, curnode->childindex(faridx), o, ray))
160 {
161 smax = min(smax, skelmodel::intersectdist/skelmodel::intersectscale);
162 tmax = min(tmax, smax);
163 }
164 }
165 curnode += curnode->childindex(nearidx);
166 tmax = min(tmax, nearsplit);
167 continue;
168 }
169 if(stacksize <= 0) return;
170 skelbihstack &restore = stack[--stacksize];
171 curnode = restore.node;
172 tmin = restore.tmin;
173 tmax = min(restore.tmax, smax);
174 }
175 }
176
intersect(skelmodel::skelmeshgroup * m,skelmodel::skin * s,const vec & o,const vec & ray)177 void skelbih::intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const vec &o, const vec &ray)
178 {
179 vec invray(ray.x ? 1/ray.x : 1e16f, ray.y ? 1/ray.y : 1e16f, ray.z ? 1/ray.z : 1e16f);
180 float tmin, tmax;
181 float t1 = (bbmin.x - o.x)*invray.x,
182 t2 = (bbmax.x - o.x)*invray.x;
183 if(invray.x > 0) { tmin = t1; tmax = t2; } else { tmin = t2; tmax = t1; }
184 t1 = (bbmin.y - o.y)*invray.y;
185 t2 = (bbmax.y - o.y)*invray.y;
186 if(invray.y > 0) { tmin = max(tmin, t1); tmax = min(tmax, t2); } else { tmin = max(tmin, t2); tmax = min(tmax, t1); }
187 t1 = (bbmin.z - o.z)*invray.z;
188 t2 = (bbmax.z - o.z)*invray.z;
189 if(invray.z > 0) { tmin = max(tmin, t1); tmax = min(tmax, t2); } else { tmin = max(tmin, t2); tmax = min(tmax, t1); }
190 tmax = min(tmax, skelmodel::intersectdist/skelmodel::intersectscale);
191 if(tmin >= tmax) return;
192
193 if(nodes) intersect(m, s, o, ray, invray, nodes, tmin, tmax);
194 else triintersect(m, s, 0, o, ray);
195 }
196
build(skelmodel::skelmeshgroup * m,ushort * indices,int numindices,const vec & vmin,const vec & vmax)197 void skelbih::build(skelmodel::skelmeshgroup *m, ushort *indices, int numindices, const vec &vmin, const vec &vmax)
198 {
199 int axis = 2;
200 loopk(2) if(vmax[k] - vmin[k] > vmax[axis] - vmin[axis]) axis = k;
201
202 vec leftmin, leftmax, rightmin, rightmax;
203 float splitleft, splitright;
204 int left, right;
205 loopk(3)
206 {
207 leftmin = rightmin = vec(1e16f, 1e16f, 1e16f);
208 leftmax = rightmax = vec(-1e16f, -1e16f, -1e16f);
209 float split = 0.5f*(vmax[axis] + vmin[axis]);
210 for(left = 0, right = numindices, splitleft = SHRT_MIN, splitright = SHRT_MAX; left < right;)
211 {
212 tri &tri = tris[indices[left]];
213 skelmodel::skelmesh *tm = (skelmodel::skelmesh *)m->meshes[tri.mesh];
214 const vec &ta = tm->verts[tri.vert[0]].pos, &tb = tm->verts[tri.vert[1]].pos, &tc = tm->verts[tri.vert[2]].pos;
215 vec trimin = vec(ta).min(tb).min(tc), trimax = vec(ta).max(tb).max(tc);
216 float amin = trimin[axis], amax = trimax[axis];
217 if(max(split - amin, 0.0f) > max(amax - split, 0.0f))
218 {
219 ++left;
220 splitleft = max(splitleft, amax);
221 leftmin.min(trimin);
222 leftmax.max(trimax);
223 }
224 else
225 {
226 --right;
227 swap(indices[left], indices[right]);
228 splitright = min(splitright, amin);
229 rightmin.min(trimin);
230 rightmax.max(trimax);
231 }
232 }
233 if(left > 0 && right < numindices) break;
234 axis = (axis+1)%3;
235 }
236
237 if(!left || right==numindices)
238 {
239 leftmin = rightmin = vec(1e16f, 1e16f, 1e16f);
240 leftmax = rightmax = vec(-1e16f, -1e16f, -1e16f);
241 left = right = numindices/2;
242 splitleft = SHRT_MIN;
243 splitright = SHRT_MAX;
244 loopi(numindices)
245 {
246 tri &tri = tris[indices[i]];
247 skelmodel::skelmesh *tm = (skelmodel::skelmesh *)m->meshes[tri.mesh];
248 const vec &ta = tm->verts[tri.vert[0]].pos, &tb = tm->verts[tri.vert[1]].pos, &tc = tm->verts[tri.vert[2]].pos;
249 vec trimin = vec(ta).min(tb).min(tc), trimax = vec(ta).max(tb).max(tc);
250 if(i < left)
251 {
252 splitleft = max(splitleft, trimax[axis]);
253 leftmin.min(trimin);
254 leftmax.max(trimax);
255 }
256 else
257 {
258 splitright = min(splitright, trimin[axis]);
259 rightmin.min(trimin);
260 rightmax.max(trimax);
261 }
262 }
263 }
264
265 int offset = numnodes++;
266 node &curnode = nodes[offset];
267 curnode.split[0] = short(ceil(splitleft));
268 curnode.split[1] = short(floor(splitright));
269
270 if(left==1) curnode.child[0] = (axis<<14) | indices[0];
271 else
272 {
273 curnode.child[0] = (axis<<14) | (numnodes - offset);
274 build(m, indices, left, leftmin, leftmax);
275 }
276
277 if(numindices-right==1) curnode.child[1] = (1<<15) | (left==1 ? 1<<14 : 0) | indices[right];
278 else
279 {
280 curnode.child[1] = (left==1 ? 1<<14 : 0) | (numnodes - offset);
281 build(m, &indices[right], numindices-right, rightmin, rightmax);
282 }
283 }
284
skelbih(skelmodel::skelmeshgroup * m,int numtris,tri * tris)285 skelbih::skelbih(skelmodel::skelmeshgroup *m, int numtris, tri *tris)
286 : nodes(NULL), numnodes(0), tris(tris), bbmin(1e16f, 1e16f, 1e16f), bbmax(-1e16f, -1e16f, -1e16f)
287 {
288 loopi(numtris)
289 {
290 tri &tri = tris[i];
291 skelmodel::skelmesh *tm = (skelmodel::skelmesh *)m->meshes[tri.mesh];
292 const vec &ta = tm->verts[tri.vert[0]].pos, &tb = tm->verts[tri.vert[1]].pos, &tc = tm->verts[tri.vert[2]].pos;
293 bbmin.min(ta).min(tb).min(tc);
294 bbmax.max(ta).max(tb).max(tc);
295 }
296 if(numtris > 1)
297 {
298 nodes = new node[numtris];
299 ushort *indices = new ushort[numtris];
300 loopi(numtris) indices[i] = i;
301 build(m, indices, numtris, bbmin, bbmax);
302 delete[] indices;
303 }
304 }
305
306 struct skelhitzone
307 {
308 typedef skelbih::tri tri;
309
310 int numparents, numchildren;
311 skelhitzone **parents, **children;
312 vec center, animcenter;
313 float radius;
314 int visited;
315 union
316 {
317 int blend;
318 int numtris;
319 };
320 union
321 {
322 tri *tris;
323 skelbih *bih;
324 };
325
skelhitzoneskelhitzone326 skelhitzone() : numparents(0), numchildren(0), parents(NULL), children(NULL), center(0, 0, 0), animcenter(0, 0, 0), radius(0), visited(-1)
327 {
328 blend = -1;
329 bih = NULL;
330 }
331
~skelhitzoneskelhitzone332 ~skelhitzone()
333 {
334 if(!numchildren) { DELETEP(bih); }
335 else { DELETEA(tris); }
336 }
337
338 static bool triintersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const dualquat *bdata1, const dualquat *bdata2, int numblends, const tri &t, const vec &o, const vec &ray);
339
shellintersectskelhitzone340 bool shellintersect(const vec &o, const vec &ray)
341 {
342 vec c(animcenter);
343 c.sub(o);
344 float v = c.dot(ray), inside = radius*radius - c.squaredlen();
345 if(inside < 0 && v < 0) return false;
346 float d = inside + v*v;
347 if(d < 0) return false;
348 v -= skelmodel::intersectdist/skelmodel::intersectscale;
349 return v < 0 || d >= v*v;
350 }
351
intersectskelhitzone352 void intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const dualquat *bdata1, const dualquat *bdata2, int numblends, const vec &o, const vec &ray)
353 {
354 if(!numchildren)
355 {
356 if(bih)
357 {
358 const dualquat &b = blend < numblends ? bdata2[blend] : bdata1[m->skel->bones[blend - numblends].interpindex];
359 vec bo = b.transposedtransform(o), bray = b.transposedtransformnormal(ray);
360 bih->intersect(m, s, bo, bray);
361 }
362 }
363 else if(shellintersect(o, ray))
364 {
365 loopi(numtris) triintersect(m, s, bdata1, bdata2, numblends, tris[i], o, ray);
366 loopi(numchildren) if(children[i]->visited != visited)
367 {
368 children[i]->visited = visited;
369 children[i]->intersect(m, s, bdata1, bdata2, numblends, o, ray);
370 }
371 }
372 }
373
propagateskelhitzone374 void propagate(skelmodel::skelmeshgroup *m, const dualquat *bdata1, const dualquat *bdata2, int numblends)
375 {
376 if(!numchildren)
377 {
378 const dualquat &b = blend < numblends ? bdata2[blend] : bdata1[m->skel->bones[blend - numblends].interpindex];
379 animcenter = b.transform(center);
380 }
381 else
382 {
383 animcenter = children[numchildren-1]->animcenter;
384 radius = children[numchildren-1]->radius;
385 loopi(numchildren-1)
386 {
387 skelhitzone *child = children[i];
388 vec n = child->animcenter;
389 n.sub(animcenter);
390 float dist = n.magnitude();
391 if(child->radius >= dist + radius)
392 {
393 animcenter = child->animcenter;
394 radius = child->radius;
395 }
396 else if(radius < dist + child->radius)
397 {
398 float newradius = 0.5f*(radius + dist + child->radius);
399 animcenter.add(n.mul((newradius - radius)/dist));
400 radius = newradius;
401 }
402 }
403 }
404 }
405 };
406
triintersect(skelmodel::skelmeshgroup * m,skelmodel::skin * s,const dualquat * bdata1,const dualquat * bdata2,int numblends,const tri & t,const vec & o,const vec & ray)407 bool skelhitzone::triintersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const dualquat *bdata1, const dualquat *bdata2, int numblends, const tri &t, const vec &o, const vec &ray)
408 {
409 skelmodel::skelmesh *tm = (skelmodel::skelmesh *)m->meshes[t.mesh];
410 const skelmodel::vert &va = tm->verts[t.vert[0]], &vb = tm->verts[t.vert[1]], &vc = tm->verts[t.vert[2]];
411 vec a = (va.blend < numblends ? bdata2[va.blend] : bdata1[m->blendcombos[va.blend].interpbones[0]]).transform(va.pos),
412 b = (vb.blend < numblends ? bdata2[vb.blend] : bdata1[m->blendcombos[vb.blend].interpbones[0]]).transform(vb.pos),
413 c = (vc.blend < numblends ? bdata2[vc.blend] : bdata1[m->blendcombos[vc.blend].interpbones[0]]).transform(vc.pos);
414 SKELTRIINTERSECT(a, b, c);
415 }
416
417 struct skelzonekey
418 {
419 int blend;
420 uchar bones[12];
421
skelzonekeyskelzonekey422 skelzonekey() : blend(-1) { memset(bones, 0xFF, sizeof(bones)); }
skelzonekeyskelzonekey423 skelzonekey(int bone) : blend(INT_MAX) { bones[0] = bone; memset(&bones[1], 0xFF, sizeof(bones)-1); }
skelzonekeyskelzonekey424 skelzonekey(skelmodel::skelmesh *m, const skelmodel::tri &t)
425 : blend(-1)
426 {
427 memset(bones, 0xFF, sizeof(bones));
428 addbones(m, t);
429 }
430
includesskelzonekey431 bool includes(const skelzonekey &o)
432 {
433 int j = 0;
434 loopi(sizeof(bones))
435 {
436 if(bones[i] > o.bones[j]) return false;
437 if(bones[i] == o.bones[j]) j++;
438 }
439 return j < (int)sizeof(bones) ? o.bones[j] == 0xFF : blend < 0 || blend == o.blend;
440 }
441
subtractskelzonekey442 void subtract(const skelzonekey &o)
443 {
444 int len = 0, j = 0;
445 loopi(sizeof(bones))
446 {
447 retry:
448 if(j >= (int)sizeof(o.bones) || bones[i] < o.bones[j]) { bones[len++] = bones[i]; continue; }
449 if(bones[i] == o.bones[j]) { j++; continue; }
450 do j++; while(j < (int)sizeof(o.bones) && bones[i] > o.bones[j]);
451 goto retry;
452 }
453 memset(&bones[len], 0xFF, sizeof(bones) - len);
454 }
455
hasboneskelzonekey456 bool hasbone(int n)
457 {
458 loopi(sizeof(bones))
459 {
460 if(bones[i] == n) return true;
461 if(bones[i] == 0xFF) break;
462 }
463 return false;
464 }
465
numbonesskelzonekey466 int numbones()
467 {
468 loopi(sizeof(bones)) if(bones[i] == 0xFF) return i;
469 return sizeof(bones);
470 }
471
addboneskelzonekey472 void addbone(int n)
473 {
474 loopi(sizeof(bones))
475 {
476 if(n <= bones[i])
477 {
478 if(n < bones[i])
479 {
480 memmove(&bones[i+1], &bones[i], sizeof(bones) - (i+1));
481 bones[i] = n;
482 }
483 return;
484 }
485 }
486 }
487
addbonesskelzonekey488 void addbones(skelmodel::skelmesh *m, const skelmodel::tri &t)
489 {
490 skelmodel::skelmeshgroup *g = (skelmodel::skelmeshgroup *)m->group;
491 int b0 = m->verts[t.vert[0]].blend, b1 = m->verts[t.vert[1]].blend, b2 = m->verts[t.vert[1]].blend;
492 const skelmodel::blendcombo &c0 = g->blendcombos[b0];
493 loopi(4) if(c0.weights[i]) addbone(c0.bones[i]);
494 if(b0 != b1 || b0 != b2)
495 {
496 const skelmodel::blendcombo &c1 = g->blendcombos[b1];
497 loopi(4) if(c1.weights[i]) addbone(c1.bones[i]);
498 const skelmodel::blendcombo &c2 = g->blendcombos[b2];
499 loopi(4) if(c2.weights[i]) addbone(c2.bones[i]);
500 }
501 else blend = b0;
502 }
503 };
504
505 struct skelzonebounds
506 {
507 int owner;
508 vec bbmin, bbmax;
509
skelzoneboundsskelzonebounds510 skelzonebounds() : owner(-1), bbmin(1e16f, 1e16f, 1e16f), bbmax(-1e16f, -1e16f, -1e16f) {}
511
addvertskelzonebounds512 void addvert(const vec &p)
513 {
514 bbmin.x = min(bbmin.x, p.x);
515 bbmin.y = min(bbmin.y, p.y);
516 bbmin.z = min(bbmin.z, p.z);
517 bbmax.x = max(bbmax.x, p.x);
518 bbmax.y = max(bbmax.y, p.y);
519 bbmax.z = max(bbmax.z, p.z);
520 }
521
emptyskelzonebounds522 bool empty() const { return bbmin.x > bbmax.x; }
523
calccenterskelzonebounds524 vec calccenter() const
525 {
526 return vec(bbmin).add(bbmax).mul(0.5f);
527 }
528
calcradiusskelzonebounds529 float calcradius() const
530 {
531 return vec(bbmax).sub(bbmin).mul(0.5f).magnitude();
532 }
533 };
534
535 struct skelzoneinfo
536 {
537 int index, parents, conflicts;
538 skelzonekey key;
539 vector<skelzoneinfo *> children;
540 vector<skelhitzone::tri> tris;
541
skelzoneinfoskelzoneinfo542 skelzoneinfo() : index(-1), parents(0), conflicts(0) {}
skelzoneinfoskelzoneinfo543 skelzoneinfo(const skelzonekey &key) : index(-1), parents(0), conflicts(0), key(key) {}
544 };
545
htcmp(const skelzonekey & x,const skelzoneinfo & y)546 static inline bool htcmp(const skelzonekey &x, const skelzoneinfo &y) { return !memcmp(x.bones, y.key.bones, sizeof(x.bones)) && (x.bones[1] == 0xFF || x.blend == y.key.blend); }
547
hthash(const skelzonekey & k)548 static inline uint hthash(const skelzonekey &k)
549 {
550 union { uint i[3]; uchar b[12]; } conv;
551 memcpy(conv.b, k.bones, sizeof(conv.b));
552 return conv.i[0]^conv.i[1]^conv.i[2];
553 }
554
555 struct skelhitdata
556 {
557 int numzones, rootzones, visited;
558 skelhitzone *zones;
559 skelhitzone **links;
560 skelhitzone::tri *tris;
561 int numblends;
562 skelmodel::blendcacheentry blendcache;
563
skelhitdataskelhitdata564 skelhitdata() : numzones(0), rootzones(0), visited(0), zones(NULL), links(NULL), tris(NULL), numblends(0) {}
~skelhitdataskelhitdata565 ~skelhitdata()
566 {
567 DELETEA(zones);
568 DELETEA(links);
569 DELETEA(tris);
570 DELETEA(blendcache.bdata);
571 }
572
573 uchar chooseid(skelmodel::skelmeshgroup *g, skelmodel::skelmesh *m, const skelmodel::tri &t, const uchar *ids);
574 void build(skelmodel::skelmeshgroup *g, const uchar *ids);
575
cleanupskelhitdata576 void cleanup()
577 {
578 blendcache.owner = -1;
579 }
580
propagateskelhitdata581 void propagate(skelmodel::skelmeshgroup *m, const dualquat *bdata1, dualquat *bdata2)
582 {
583 visited = 0;
584 loopi(numzones)
585 {
586 zones[i].visited = -1;
587 zones[i].propagate(m, bdata1, bdata2, numblends);
588 }
589 }
590
intersectskelhitdata591 void intersect(skelmodel::skelmeshgroup *m, skelmodel::skin *s, const dualquat *bdata1, dualquat *bdata2, const vec &o, const vec &ray)
592 {
593 if(++visited < 0)
594 {
595 visited = 0;
596 loopi(numzones) zones[i].visited = -1;
597 }
598 for(int i = numzones - rootzones; i < numzones; i++)
599 {
600 zones[i].visited = visited;
601 zones[i].intersect(m, s, bdata1, bdata2, numblends, o, ray);
602 }
603 }
604 };
605
cleanuphitdata()606 void skelmodel::skelmeshgroup::cleanuphitdata()
607 {
608 if(hitdata) hitdata->cleanup();
609 }
610
deletehitdata()611 void skelmodel::skelmeshgroup::deletehitdata()
612 {
613 DELETEP(hitdata);
614 }
615
intersect(skelhitdata * z,part * p,const skelmodel::skelcacheentry & sc,const vec & o,const vec & ray)616 void skelmodel::skelmeshgroup::intersect(skelhitdata *z, part *p, const skelmodel::skelcacheentry &sc, const vec &o, const vec &ray)
617 {
618 int owner = &sc - &skel->skelcache[0];
619 skelmodel::blendcacheentry &bc = z->blendcache;
620 if(bc.owner != owner || bc != sc)
621 {
622 bc.owner = owner;
623 bc.millis = lastmillis;
624 (animcacheentry &)bc = sc;
625 blendbones(sc.bdata, bc.bdata, blendcombos.getbuf(), z->numblends);
626 z->propagate(this, sc.bdata, bc.bdata);
627 }
628 z->intersect(this, p->skins.getbuf(), sc.bdata, bc.bdata, o, ray);
629 }
630
chooseid(skelmodel::skelmeshgroup * g,skelmodel::skelmesh * m,const skelmodel::tri & t,const uchar * ids)631 uchar skelhitdata::chooseid(skelmodel::skelmeshgroup *g, skelmodel::skelmesh *m, const skelmodel::tri &t, const uchar *ids)
632 {
633 int numused = 0;
634 uchar used[12];
635 float weights[12];
636 loopk(3)
637 {
638 const skelmodel::vert &v = m->verts[t.vert[k]];
639 const skelmodel::blendcombo &c = g->blendcombos[v.blend];
640 loopl(4) if(c.weights[l])
641 {
642 uchar id = ids[c.bones[l]];
643 loopi(numused) if(used[i] == id) { weights[i] += c.weights[l]; goto nextbone; }
644 used[numused] = id;
645 weights[numused] = c.weights[l];
646 numused++;
647 nextbone:;
648 }
649 }
650 uchar bestid = 0xFF;
651 float bestweight = 0;
652 loopi(numused) if(weights[i] > bestweight || (weights[i] == bestweight && used[i] < bestid))
653 {
654 bestid = used[i];
655 bestweight = weights[i];
656 }
657 return bestid;
658 }
659
build(skelmodel::skelmeshgroup * g,const uchar * ids)660 void skelhitdata::build(skelmodel::skelmeshgroup *g, const uchar *ids)
661 {
662 if(numzones) return;
663
664 hashset<skelzoneinfo> infomap(256);
665 vector<skelzoneinfo *> info;
666 skelzonebounds *bounds = new skelzonebounds[g->skel->numbones];
667 numblends = g->blendcombos.length();
668 loopv(g->blendcombos) if(!g->blendcombos[i].weights[1]) { numblends = i; break; }
669 blendcache.bdata = numblends > 0 ? new dualquat[numblends] : NULL;
670 loopi(min(g->meshes.length(), 0x100))
671 {
672 skelmodel::skelmesh *m = (skelmodel::skelmesh *)g->meshes[i];
673 loopj(m->numtris)
674 {
675 const skelmodel::tri &t = m->tris[j];
676 loopk(3)
677 {
678 const skelmodel::vert &v = m->verts[t.vert[k]];
679 const skelmodel::blendcombo &c = g->blendcombos[v.blend];
680 loopl(4) if(c.weights[l]) bounds[c.bones[l]].addvert(v.pos);
681 }
682 skelzonekey key(m, t);
683 skelzoneinfo &zi = infomap.access(key, key);
684 if(key.blend >= numblends && zi.index < 0)
685 {
686 bounds[key.bones[0]].owner = zi.index = info.length();
687 info.add(&zi);
688 }
689 skelhitzone::tri &zt = zi.tris.add();
690 zt.mesh = i;
691 zt.id = chooseid(g, m, t, ids);
692 memcpy(zt.vert, t.vert, sizeof(zt.vert));
693 }
694 }
695 loopi(g->skel->numbones)
696 {
697 if(bounds[i].empty() || bounds[i].owner >= 0) continue;
698 skelzonekey key(i);
699 skelzoneinfo &zi = infomap.access(key, key);
700 zi.index = info.length();
701 info.add(&zi);
702 }
703 int leafzones = info.length();
704 enumerate(infomap, skelzoneinfo, zi, { if(zi.index < 0) info.add(&zi); });
705 for(int i = leafzones; i < info.length(); i++)
706 {
707 skelzoneinfo &zi = *info[i];
708 if(zi.key.blend >= 0) continue;
709 loopvj(info) if(i != j && zi.key.includes(info[j]->key))
710 {
711 skelzoneinfo &zj = *info[j];
712 loopvk(zi.children)
713 {
714 skelzoneinfo &zk = *zi.children[k];
715 if(zk.key.includes(zj.key)) goto nextzone;
716 if(zj.key.includes(zk.key))
717 {
718 zk.parents--;
719 zj.parents++;
720 zi.children[k] = &zj;
721 while(++k < zi.children.length()) if(zj.key.includes(zi.children[k]->key)) { zi.children[k]->parents--; zi.children.removeunordered(k--); }
722 goto nextzone;
723 }
724 }
725 zj.parents++;
726 zi.children.add(&zj);
727 nextzone:;
728 }
729 skelzonekey deps = zi.key;
730 loopvj(zi.children)
731 {
732 skelzoneinfo &zj = *zi.children[j];
733 if(zj.key.blend < 0 || zj.key.blend >= numblends) deps.subtract(zj.key);
734 }
735 loopj(sizeof(deps.bones))
736 {
737 if(deps.bones[j]==0xFF) break;
738 skelzonekey dep(deps.bones[j]);
739 skelzoneinfo &zj = infomap.access(dep, dep);
740 zj.parents++;
741 zi.children.add(&zj);
742 }
743 }
744 for(int i = leafzones; i < info.length(); i++)
745 {
746 skelzoneinfo &zi = *info[i];
747 loopvj(zi.children)
748 {
749 skelzoneinfo &zj = *zi.children[j];
750 if(zj.tris.length() <= 2 && zj.parents == 1)
751 {
752 zi.tris.put(zj.tris.getbuf(), zj.tris.length());
753 zj.tris.setsize(0);
754 if(zj.index < 0)
755 {
756 zj.parents = 0;
757 zi.children.removeunordered(j--);
758 }
759 zi.children.put(zj.children.getbuf(), zj.children.length());
760 zj.children.setsize(0);
761 }
762 }
763 }
764 int numlinks = 0, numtris = 0;
765 loopvrev(info)
766 {
767 skelzoneinfo &zi = *info[i];
768 if(zi.parents || zi.tris.empty()) info.removeunordered(i);
769 zi.conflicts = zi.parents;
770 numlinks += zi.parents + zi.children.length();
771 numtris += zi.tris.length();
772 }
773 rootzones = info.length();
774 loopv(info)
775 {
776 skelzoneinfo &zi = *info[i];
777 zi.index = i;
778 loopvj(zi.children)
779 {
780 skelzoneinfo &zj = *zi.children[j];
781 if(!--zj.conflicts) info.add(&zj);
782 }
783 }
784 numzones = info.length();
785 zones = new skelhitzone[numzones];
786 links = numlinks ? new skelhitzone *[numlinks] : NULL;
787 tris = new skelhitzone::tri[numtris];
788 skelhitzone **curlink = links;
789 skelhitzone::tri *curtris = tris;
790 loopi(numzones)
791 {
792 skelhitzone &z = zones[i];
793 skelzoneinfo &zi = *info[info.length()-1 - i];
794 memcpy(curtris, zi.tris.getbuf(), zi.tris.length()*sizeof(skelhitzone::tri));
795 if(zi.key.blend >= numblends)
796 {
797 z.blend = zi.key.bones[0] + numblends;
798 if(zi.tris.length()) z.bih = new skelbih(g, zi.tris.length(), curtris);
799 const skelzonebounds &b = bounds[zi.key.bones[0]];
800 z.center = b.calccenter();
801 z.radius = b.calcradius();
802 }
803 else if(zi.key.blend >= 0)
804 {
805 z.blend = zi.key.blend;
806 z.bih = new skelbih(g, zi.tris.length(), curtris);
807 z.center = z.bih->calccenter();
808 z.radius = z.bih->calcradius();
809 }
810 else
811 {
812 z.numtris = zi.tris.length();
813 z.tris = curtris;
814 }
815 curtris += zi.tris.length();
816 z.parents = curlink;
817 curlink += zi.parents;
818 z.numchildren = zi.children.length();
819 z.children = curlink;
820 loopvj(zi.children) z.children[j] = &zones[info.length()-1 - zi.children[j]->index];
821 curlink += zi.children.length();
822 }
823 loopi(numzones)
824 {
825 skelhitzone &z = zones[i];
826 loopj(z.numchildren) z.children[j]->parents[z.children[j]->numparents++] = &z;
827 }
828 delete[] bounds;
829 }
830
buildhitdata(const uchar * hitzones)831 void skelmodel::skelmeshgroup::buildhitdata(const uchar *hitzones)
832 {
833 if(hitdata) return;
834 hitdata = new skelhitdata;
835 hitdata->build(this, hitzones);
836 }
837
838