1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 #include "sys/platform.h"
30 #include "framework/Common.h"
31
32 #include "idlib/geometry/TraceModel.h"
33
34 /*
35 ============
36 idTraceModel::SetupBox
37 ============
38 */
SetupBox(const idBounds & boxBounds)39 void idTraceModel::SetupBox( const idBounds &boxBounds ) {
40 int i;
41
42 if ( type != TRM_BOX ) {
43 InitBox();
44 }
45 // offset to center
46 offset = ( boxBounds[0] + boxBounds[1] ) * 0.5f;
47 // set box vertices
48 for ( i = 0; i < 8; i++ ) {
49 verts[i][0] = boxBounds[(i^(i>>1))&1][0];
50 verts[i][1] = boxBounds[(i>>1)&1][1];
51 verts[i][2] = boxBounds[(i>>2)&1][2];
52 }
53 // set polygon plane distances
54 polys[0].dist = -boxBounds[0][2];
55 polys[1].dist = boxBounds[1][2];
56 polys[2].dist = -boxBounds[0][1];
57 polys[3].dist = boxBounds[1][0];
58 polys[4].dist = boxBounds[1][1];
59 polys[5].dist = -boxBounds[0][0];
60 // set polygon bounds
61 for ( i = 0; i < 6; i++ ) {
62 polys[i].bounds = boxBounds;
63 }
64 polys[0].bounds[1][2] = boxBounds[0][2];
65 polys[1].bounds[0][2] = boxBounds[1][2];
66 polys[2].bounds[1][1] = boxBounds[0][1];
67 polys[3].bounds[0][0] = boxBounds[1][0];
68 polys[4].bounds[0][1] = boxBounds[1][1];
69 polys[5].bounds[1][0] = boxBounds[0][0];
70
71 bounds = boxBounds;
72 }
73
74 /*
75 ============
76 idTraceModel::SetupBox
77
78 The origin is placed at the center of the cube.
79 ============
80 */
SetupBox(const float size)81 void idTraceModel::SetupBox( const float size ) {
82 idBounds boxBounds;
83 float halfSize;
84
85 halfSize = size * 0.5f;
86 boxBounds[0].Set( -halfSize, -halfSize, -halfSize );
87 boxBounds[1].Set( halfSize, halfSize, halfSize );
88 SetupBox( boxBounds );
89 }
90
91 /*
92 ============
93 idTraceModel::InitBox
94
95 Initialize size independent box.
96 ============
97 */
InitBox(void)98 void idTraceModel::InitBox( void ) {
99 int i;
100
101 type = TRM_BOX;
102 numVerts = 8;
103 numEdges = 12;
104 numPolys = 6;
105
106 // set box edges
107 for ( i = 0; i < 4; i++ ) {
108 edges[ i + 1 ].v[0] = i;
109 edges[ i + 1 ].v[1] = (i + 1) & 3;
110 edges[ i + 5 ].v[0] = 4 + i;
111 edges[ i + 5 ].v[1] = 4 + ((i + 1) & 3);
112 edges[ i + 9 ].v[0] = i;
113 edges[ i + 9 ].v[1] = 4 + i;
114 }
115
116 // all edges of a polygon go counter clockwise
117 polys[0].numEdges = 4;
118 polys[0].edges[0] = -4;
119 polys[0].edges[1] = -3;
120 polys[0].edges[2] = -2;
121 polys[0].edges[3] = -1;
122 polys[0].normal.Set( 0.0f, 0.0f, -1.0f );
123
124 polys[1].numEdges = 4;
125 polys[1].edges[0] = 5;
126 polys[1].edges[1] = 6;
127 polys[1].edges[2] = 7;
128 polys[1].edges[3] = 8;
129 polys[1].normal.Set( 0.0f, 0.0f, 1.0f );
130
131 polys[2].numEdges = 4;
132 polys[2].edges[0] = 1;
133 polys[2].edges[1] = 10;
134 polys[2].edges[2] = -5;
135 polys[2].edges[3] = -9;
136 polys[2].normal.Set( 0.0f, -1.0f, 0.0f );
137
138 polys[3].numEdges = 4;
139 polys[3].edges[0] = 2;
140 polys[3].edges[1] = 11;
141 polys[3].edges[2] = -6;
142 polys[3].edges[3] = -10;
143 polys[3].normal.Set( 1.0f, 0.0f, 0.0f );
144
145 polys[4].numEdges = 4;
146 polys[4].edges[0] = 3;
147 polys[4].edges[1] = 12;
148 polys[4].edges[2] = -7;
149 polys[4].edges[3] = -11;
150 polys[4].normal.Set( 0.0f, 1.0f, 0.0f );
151
152 polys[5].numEdges = 4;
153 polys[5].edges[0] = 4;
154 polys[5].edges[1] = 9;
155 polys[5].edges[2] = -8;
156 polys[5].edges[3] = -12;
157 polys[5].normal.Set( -1.0f, 0.0f, 0.0f );
158
159 // convex model
160 isConvex = true;
161
162 GenerateEdgeNormals();
163 }
164
165 /*
166 ============
167 idTraceModel::SetupOctahedron
168 ============
169 */
SetupOctahedron(const idBounds & octBounds)170 void idTraceModel::SetupOctahedron( const idBounds &octBounds ) {
171 int i, e0, e1, v0, v1, v2;
172 idVec3 v;
173
174 if ( type != TRM_OCTAHEDRON ) {
175 InitOctahedron();
176 }
177
178 offset = ( octBounds[0] + octBounds[1] ) * 0.5f;
179 v[0] = octBounds[1][0] - offset[0];
180 v[1] = octBounds[1][1] - offset[1];
181 v[2] = octBounds[1][2] - offset[2];
182
183 // set vertices
184 verts[0].Set( offset.x + v[0], offset.y, offset.z );
185 verts[1].Set( offset.x - v[0], offset.y, offset.z );
186 verts[2].Set( offset.x, offset.y + v[1], offset.z );
187 verts[3].Set( offset.x, offset.y - v[1], offset.z );
188 verts[4].Set( offset.x, offset.y, offset.z + v[2] );
189 verts[5].Set( offset.x, offset.y, offset.z - v[2] );
190
191 // set polygons
192 for ( i = 0; i < numPolys; i++ ) {
193 e0 = polys[i].edges[0];
194 e1 = polys[i].edges[1];
195 v0 = edges[abs(e0)].v[INTSIGNBITSET(e0)];
196 v1 = edges[abs(e0)].v[INTSIGNBITNOTSET(e0)];
197 v2 = edges[abs(e1)].v[INTSIGNBITNOTSET(e1)];
198 // polygon plane
199 polys[i].normal = ( verts[v1] - verts[v0] ).Cross( verts[v2] - verts[v0] );
200 polys[i].normal.Normalize();
201 polys[i].dist = polys[i].normal * verts[v0];
202 // polygon bounds
203 polys[i].bounds[0] = polys[i].bounds[1] = verts[v0];
204 polys[i].bounds.AddPoint( verts[v1] );
205 polys[i].bounds.AddPoint( verts[v2] );
206 }
207
208 // trm bounds
209 bounds = octBounds;
210
211 GenerateEdgeNormals();
212 }
213
214 /*
215 ============
216 idTraceModel::SetupOctahedron
217
218 The origin is placed at the center of the octahedron.
219 ============
220 */
SetupOctahedron(const float size)221 void idTraceModel::SetupOctahedron( const float size ) {
222 idBounds octBounds;
223 float halfSize;
224
225 halfSize = size * 0.5f;
226 octBounds[0].Set( -halfSize, -halfSize, -halfSize );
227 octBounds[1].Set( halfSize, halfSize, halfSize );
228 SetupOctahedron( octBounds );
229 }
230
231 /*
232 ============
233 idTraceModel::InitOctahedron
234
235 Initialize size independent octahedron.
236 ============
237 */
InitOctahedron(void)238 void idTraceModel::InitOctahedron( void ) {
239
240 type = TRM_OCTAHEDRON;
241 numVerts = 6;
242 numEdges = 12;
243 numPolys = 8;
244
245 // set edges
246 edges[ 1].v[0] = 4; edges[ 1].v[1] = 0;
247 edges[ 2].v[0] = 0; edges[ 2].v[1] = 2;
248 edges[ 3].v[0] = 2; edges[ 3].v[1] = 4;
249 edges[ 4].v[0] = 2; edges[ 4].v[1] = 1;
250 edges[ 5].v[0] = 1; edges[ 5].v[1] = 4;
251 edges[ 6].v[0] = 1; edges[ 6].v[1] = 3;
252 edges[ 7].v[0] = 3; edges[ 7].v[1] = 4;
253 edges[ 8].v[0] = 3; edges[ 8].v[1] = 0;
254 edges[ 9].v[0] = 5; edges[ 9].v[1] = 2;
255 edges[10].v[0] = 0; edges[10].v[1] = 5;
256 edges[11].v[0] = 5; edges[11].v[1] = 1;
257 edges[12].v[0] = 5; edges[12].v[1] = 3;
258
259 // all edges of a polygon go counter clockwise
260 polys[0].numEdges = 3;
261 polys[0].edges[0] = 1;
262 polys[0].edges[1] = 2;
263 polys[0].edges[2] = 3;
264
265 polys[1].numEdges = 3;
266 polys[1].edges[0] = -3;
267 polys[1].edges[1] = 4;
268 polys[1].edges[2] = 5;
269
270 polys[2].numEdges = 3;
271 polys[2].edges[0] = -5;
272 polys[2].edges[1] = 6;
273 polys[2].edges[2] = 7;
274
275 polys[3].numEdges = 3;
276 polys[3].edges[0] = -7;
277 polys[3].edges[1] = 8;
278 polys[3].edges[2] = -1;
279
280 polys[4].numEdges = 3;
281 polys[4].edges[0] = 9;
282 polys[4].edges[1] = -2;
283 polys[4].edges[2] = 10;
284
285 polys[5].numEdges = 3;
286 polys[5].edges[0] = 11;
287 polys[5].edges[1] = -4;
288 polys[5].edges[2] = -9;
289
290 polys[6].numEdges = 3;
291 polys[6].edges[0] = 12;
292 polys[6].edges[1] = -6;
293 polys[6].edges[2] = -11;
294
295 polys[7].numEdges = 3;
296 polys[7].edges[0] = -10;
297 polys[7].edges[1] = -8;
298 polys[7].edges[2] = -12;
299
300 // convex model
301 isConvex = true;
302 }
303
304 /*
305 ============
306 idTraceModel::SetupDodecahedron
307 ============
308 */
SetupDodecahedron(const idBounds & dodBounds)309 void idTraceModel::SetupDodecahedron( const idBounds &dodBounds ) {
310 int i, e0, e1, e2, e3, v0, v1, v2, v3, v4;
311 float s, d;
312 idVec3 a, b, c;
313
314 if ( type != TRM_DODECAHEDRON ) {
315 InitDodecahedron();
316 }
317
318 a[0] = a[1] = a[2] = 0.5773502691896257f; // 1.0f / ( 3.0f ) ^ 0.5f;
319 b[0] = b[1] = b[2] = 0.3568220897730899f; // ( ( 3.0f - ( 5.0f ) ^ 0.5f ) / 6.0f ) ^ 0.5f;
320 c[0] = c[1] = c[2] = 0.9341723589627156f; // ( ( 3.0f + ( 5.0f ) ^ 0.5f ) / 6.0f ) ^ 0.5f;
321 d = 0.5f / c[0];
322 s = ( dodBounds[1][0] - dodBounds[0][0] ) * d;
323 a[0] *= s;
324 b[0] *= s;
325 c[0] *= s;
326 s = ( dodBounds[1][1] - dodBounds[0][1] ) * d;
327 a[1] *= s;
328 b[1] *= s;
329 c[1] *= s;
330 s = ( dodBounds[1][2] - dodBounds[0][2] ) * d;
331 a[2] *= s;
332 b[2] *= s;
333 c[2] *= s;
334
335 offset = ( dodBounds[0] + dodBounds[1] ) * 0.5f;
336
337 // set vertices
338 verts[ 0].Set( offset.x + a[0], offset.y + a[1], offset.z + a[2] );
339 verts[ 1].Set( offset.x + a[0], offset.y + a[1], offset.z - a[2] );
340 verts[ 2].Set( offset.x + a[0], offset.y - a[1], offset.z + a[2] );
341 verts[ 3].Set( offset.x + a[0], offset.y - a[1], offset.z - a[2] );
342 verts[ 4].Set( offset.x - a[0], offset.y + a[1], offset.z + a[2] );
343 verts[ 5].Set( offset.x - a[0], offset.y + a[1], offset.z - a[2] );
344 verts[ 6].Set( offset.x - a[0], offset.y - a[1], offset.z + a[2] );
345 verts[ 7].Set( offset.x - a[0], offset.y - a[1], offset.z - a[2] );
346 verts[ 8].Set( offset.x + b[0], offset.y + c[1], offset.z );
347 verts[ 9].Set( offset.x - b[0], offset.y + c[1], offset.z );
348 verts[10].Set( offset.x + b[0], offset.y - c[1], offset.z );
349 verts[11].Set( offset.x - b[0], offset.y - c[1], offset.z );
350 verts[12].Set( offset.x + c[0], offset.y , offset.z + b[2] );
351 verts[13].Set( offset.x + c[0], offset.y , offset.z - b[2] );
352 verts[14].Set( offset.x - c[0], offset.y , offset.z + b[2] );
353 verts[15].Set( offset.x - c[0], offset.y , offset.z - b[2] );
354 verts[16].Set( offset.x , offset.y + b[1], offset.z + c[2] );
355 verts[17].Set( offset.x , offset.y - b[1], offset.z + c[2] );
356 verts[18].Set( offset.x , offset.y + b[1], offset.z - c[2] );
357 verts[19].Set( offset.x , offset.y - b[1], offset.z - c[2] );
358
359 // set polygons
360 for ( i = 0; i < numPolys; i++ ) {
361 e0 = polys[i].edges[0];
362 e1 = polys[i].edges[1];
363 e2 = polys[i].edges[2];
364 e3 = polys[i].edges[3];
365 v0 = edges[abs(e0)].v[INTSIGNBITSET(e0)];
366 v1 = edges[abs(e0)].v[INTSIGNBITNOTSET(e0)];
367 v2 = edges[abs(e1)].v[INTSIGNBITNOTSET(e1)];
368 v3 = edges[abs(e2)].v[INTSIGNBITNOTSET(e2)];
369 v4 = edges[abs(e3)].v[INTSIGNBITNOTSET(e3)];
370 // polygon plane
371 polys[i].normal = ( verts[v1] - verts[v0] ).Cross( verts[v2] - verts[v0] );
372 polys[i].normal.Normalize();
373 polys[i].dist = polys[i].normal * verts[v0];
374 // polygon bounds
375 polys[i].bounds[0] = polys[i].bounds[1] = verts[v0];
376 polys[i].bounds.AddPoint( verts[v1] );
377 polys[i].bounds.AddPoint( verts[v2] );
378 polys[i].bounds.AddPoint( verts[v3] );
379 polys[i].bounds.AddPoint( verts[v4] );
380 }
381
382 // trm bounds
383 bounds = dodBounds;
384
385 GenerateEdgeNormals();
386 }
387
388 /*
389 ============
390 idTraceModel::SetupDodecahedron
391
392 The origin is placed at the center of the octahedron.
393 ============
394 */
SetupDodecahedron(const float size)395 void idTraceModel::SetupDodecahedron( const float size ) {
396 idBounds dodBounds;
397 float halfSize;
398
399 halfSize = size * 0.5f;
400 dodBounds[0].Set( -halfSize, -halfSize, -halfSize );
401 dodBounds[1].Set( halfSize, halfSize, halfSize );
402 SetupDodecahedron( dodBounds );
403 }
404
405 /*
406 ============
407 idTraceModel::InitDodecahedron
408
409 Initialize size independent dodecahedron.
410 ============
411 */
InitDodecahedron(void)412 void idTraceModel::InitDodecahedron( void ) {
413
414 type = TRM_DODECAHEDRON;
415 numVerts = 20;
416 numEdges = 30;
417 numPolys = 12;
418
419 // set edges
420 edges[ 1].v[0] = 0; edges[ 1].v[1] = 8;
421 edges[ 2].v[0] = 8; edges[ 2].v[1] = 9;
422 edges[ 3].v[0] = 9; edges[ 3].v[1] = 4;
423 edges[ 4].v[0] = 4; edges[ 4].v[1] = 16;
424 edges[ 5].v[0] = 16; edges[ 5].v[1] = 0;
425 edges[ 6].v[0] = 16; edges[ 6].v[1] = 17;
426 edges[ 7].v[0] = 17; edges[ 7].v[1] = 2;
427 edges[ 8].v[0] = 2; edges[ 8].v[1] = 12;
428 edges[ 9].v[0] = 12; edges[ 9].v[1] = 0;
429 edges[10].v[0] = 2; edges[10].v[1] = 10;
430 edges[11].v[0] = 10; edges[11].v[1] = 3;
431 edges[12].v[0] = 3; edges[12].v[1] = 13;
432 edges[13].v[0] = 13; edges[13].v[1] = 12;
433 edges[14].v[0] = 9; edges[14].v[1] = 5;
434 edges[15].v[0] = 5; edges[15].v[1] = 15;
435 edges[16].v[0] = 15; edges[16].v[1] = 14;
436 edges[17].v[0] = 14; edges[17].v[1] = 4;
437 edges[18].v[0] = 3; edges[18].v[1] = 19;
438 edges[19].v[0] = 19; edges[19].v[1] = 18;
439 edges[20].v[0] = 18; edges[20].v[1] = 1;
440 edges[21].v[0] = 1; edges[21].v[1] = 13;
441 edges[22].v[0] = 7; edges[22].v[1] = 11;
442 edges[23].v[0] = 11; edges[23].v[1] = 6;
443 edges[24].v[0] = 6; edges[24].v[1] = 14;
444 edges[25].v[0] = 15; edges[25].v[1] = 7;
445 edges[26].v[0] = 1; edges[26].v[1] = 8;
446 edges[27].v[0] = 18; edges[27].v[1] = 5;
447 edges[28].v[0] = 6; edges[28].v[1] = 17;
448 edges[29].v[0] = 11; edges[29].v[1] = 10;
449 edges[30].v[0] = 19; edges[30].v[1] = 7;
450
451 // all edges of a polygon go counter clockwise
452 polys[0].numEdges = 5;
453 polys[0].edges[0] = 1;
454 polys[0].edges[1] = 2;
455 polys[0].edges[2] = 3;
456 polys[0].edges[3] = 4;
457 polys[0].edges[4] = 5;
458
459 polys[1].numEdges = 5;
460 polys[1].edges[0] = -5;
461 polys[1].edges[1] = 6;
462 polys[1].edges[2] = 7;
463 polys[1].edges[3] = 8;
464 polys[1].edges[4] = 9;
465
466 polys[2].numEdges = 5;
467 polys[2].edges[0] = -8;
468 polys[2].edges[1] = 10;
469 polys[2].edges[2] = 11;
470 polys[2].edges[3] = 12;
471 polys[2].edges[4] = 13;
472
473 polys[3].numEdges = 5;
474 polys[3].edges[0] = 14;
475 polys[3].edges[1] = 15;
476 polys[3].edges[2] = 16;
477 polys[3].edges[3] = 17;
478 polys[3].edges[4] = -3;
479
480 polys[4].numEdges = 5;
481 polys[4].edges[0] = 18;
482 polys[4].edges[1] = 19;
483 polys[4].edges[2] = 20;
484 polys[4].edges[3] = 21;
485 polys[4].edges[4] = -12;
486
487 polys[5].numEdges = 5;
488 polys[5].edges[0] = 22;
489 polys[5].edges[1] = 23;
490 polys[5].edges[2] = 24;
491 polys[5].edges[3] = -16;
492 polys[5].edges[4] = 25;
493
494 polys[6].numEdges = 5;
495 polys[6].edges[0] = -9;
496 polys[6].edges[1] = -13;
497 polys[6].edges[2] = -21;
498 polys[6].edges[3] = 26;
499 polys[6].edges[4] = -1;
500
501 polys[7].numEdges = 5;
502 polys[7].edges[0] = -26;
503 polys[7].edges[1] = -20;
504 polys[7].edges[2] = 27;
505 polys[7].edges[3] = -14;
506 polys[7].edges[4] = -2;
507
508 polys[8].numEdges = 5;
509 polys[8].edges[0] = -4;
510 polys[8].edges[1] = -17;
511 polys[8].edges[2] = -24;
512 polys[8].edges[3] = 28;
513 polys[8].edges[4] = -6;
514
515 polys[9].numEdges = 5;
516 polys[9].edges[0] = -23;
517 polys[9].edges[1] = 29;
518 polys[9].edges[2] = -10;
519 polys[9].edges[3] = -7;
520 polys[9].edges[4] = -28;
521
522 polys[10].numEdges = 5;
523 polys[10].edges[0] = -25;
524 polys[10].edges[1] = -15;
525 polys[10].edges[2] = -27;
526 polys[10].edges[3] = -19;
527 polys[10].edges[4] = 30;
528
529 polys[11].numEdges = 5;
530 polys[11].edges[0] = -30;
531 polys[11].edges[1] = -18;
532 polys[11].edges[2] = -11;
533 polys[11].edges[3] = -29;
534 polys[11].edges[4] = -22;
535
536 // convex model
537 isConvex = true;
538 }
539
540 /*
541 ============
542 idTraceModel::SetupCylinder
543 ============
544 */
SetupCylinder(const idBounds & cylBounds,const int numSides)545 void idTraceModel::SetupCylinder( const idBounds &cylBounds, const int numSides ) {
546 int i, n, ii, n2;
547 float angle;
548 idVec3 halfSize;
549
550 n = numSides;
551 if ( n < 3 ) {
552 n = 3;
553 }
554 if ( n * 2 > MAX_TRACEMODEL_VERTS ) {
555 idLib::common->Printf( "WARNING: idTraceModel::SetupCylinder: too many vertices\n" );
556 n = MAX_TRACEMODEL_VERTS / 2;
557 }
558 if ( n * 3 > MAX_TRACEMODEL_EDGES ) {
559 idLib::common->Printf( "WARNING: idTraceModel::SetupCylinder: too many sides\n" );
560 n = MAX_TRACEMODEL_EDGES / 3;
561 }
562 if ( n + 2 > MAX_TRACEMODEL_POLYS ) {
563 idLib::common->Printf( "WARNING: idTraceModel::SetupCylinder: too many polygons\n" );
564 n = MAX_TRACEMODEL_POLYS - 2;
565 }
566
567 type = TRM_CYLINDER;
568 numVerts = n * 2;
569 numEdges = n * 3;
570 numPolys = n + 2;
571 offset = ( cylBounds[0] + cylBounds[1] ) * 0.5f;
572 halfSize = cylBounds[1] - offset;
573 for ( i = 0; i < n; i++ ) {
574 // verts
575 angle = idMath::TWO_PI * i / n;
576 verts[i].x = cos( angle ) * halfSize.x + offset.x;
577 verts[i].y = sin( angle ) * halfSize.y + offset.y;
578 verts[i].z = -halfSize.z + offset.z;
579 verts[n+i].x = verts[i].x;
580 verts[n+i].y = verts[i].y;
581 verts[n+i].z = halfSize.z + offset.z;
582 // edges
583 ii = i + 1;
584 n2 = n << 1;
585 edges[ii].v[0] = i;
586 edges[ii].v[1] = ii % n;
587 edges[n+ii].v[0] = edges[ii].v[0] + n;
588 edges[n+ii].v[1] = edges[ii].v[1] + n;
589 edges[n2+ii].v[0] = i;
590 edges[n2+ii].v[1] = n + i;
591 // vertical polygon edges
592 polys[i].numEdges = 4;
593 polys[i].edges[0] = ii;
594 polys[i].edges[1] = n2 + (ii % n) + 1;
595 polys[i].edges[2] = -(n + ii);
596 polys[i].edges[3] = -(n2 + ii);
597 // bottom and top polygon edges
598 polys[n].edges[i] = -(n - i);
599 polys[n+1].edges[i] = n + ii;
600 }
601 // bottom and top polygon numEdges
602 polys[n].numEdges = n;
603 polys[n+1].numEdges = n;
604 // polygons
605 for ( i = 0; i < n; i++ ) {
606 // vertical polygon plane
607 polys[i].normal = (verts[(i+1)%n] - verts[i]).Cross( verts[n+i] - verts[i] );
608 polys[i].normal.Normalize();
609 polys[i].dist = polys[i].normal * verts[i];
610 // vertical polygon bounds
611 polys[i].bounds.Clear();
612 polys[i].bounds.AddPoint( verts[i] );
613 polys[i].bounds.AddPoint( verts[(i+1)%n] );
614 polys[i].bounds[0][2] = -halfSize.z + offset.z;
615 polys[i].bounds[1][2] = halfSize.z + offset.z;
616 }
617 // bottom and top polygon plane
618 polys[n].normal.Set( 0.0f, 0.0f, -1.0f );
619 polys[n].dist = -cylBounds[0][2];
620 polys[n+1].normal.Set( 0.0f, 0.0f, 1.0f );
621 polys[n+1].dist = cylBounds[1][2];
622 // trm bounds
623 bounds = cylBounds;
624 // bottom and top polygon bounds
625 polys[n].bounds = bounds;
626 polys[n].bounds[1][2] = bounds[0][2];
627 polys[n+1].bounds = bounds;
628 polys[n+1].bounds[0][2] = bounds[1][2];
629 // convex model
630 isConvex = true;
631
632 GenerateEdgeNormals();
633 }
634
635 /*
636 ============
637 idTraceModel::SetupCylinder
638
639 The origin is placed at the center of the cylinder.
640 ============
641 */
SetupCylinder(const float height,const float width,const int numSides)642 void idTraceModel::SetupCylinder( const float height, const float width, const int numSides ) {
643 idBounds cylBounds;
644 float halfHeight, halfWidth;
645
646 halfHeight = height * 0.5f;
647 halfWidth = width * 0.5f;
648 cylBounds[0].Set( -halfWidth, -halfWidth, -halfHeight );
649 cylBounds[1].Set( halfWidth, halfWidth, halfHeight );
650 SetupCylinder( cylBounds, numSides );
651 }
652
653 /*
654 ============
655 idTraceModel::SetupCone
656 ============
657 */
SetupCone(const idBounds & coneBounds,const int numSides)658 void idTraceModel::SetupCone( const idBounds &coneBounds, const int numSides ) {
659 int i, n, ii;
660 float angle;
661 idVec3 halfSize;
662
663 n = numSides;
664 if ( n < 2 ) {
665 n = 3;
666 }
667 if ( n + 1 > MAX_TRACEMODEL_VERTS ) {
668 idLib::common->Printf( "WARNING: idTraceModel::SetupCone: too many vertices\n" );
669 n = MAX_TRACEMODEL_VERTS - 1;
670 }
671 if ( n * 2 > MAX_TRACEMODEL_EDGES ) {
672 idLib::common->Printf( "WARNING: idTraceModel::SetupCone: too many edges\n" );
673 n = MAX_TRACEMODEL_EDGES / 2;
674 }
675 if ( n + 1 > MAX_TRACEMODEL_POLYS ) {
676 idLib::common->Printf( "WARNING: idTraceModel::SetupCone: too many polygons\n" );
677 n = MAX_TRACEMODEL_POLYS - 1;
678 }
679
680 type = TRM_CONE;
681 numVerts = n + 1;
682 numEdges = n * 2;
683 numPolys = n + 1;
684 offset = ( coneBounds[0] + coneBounds[1] ) * 0.5f;
685 halfSize = coneBounds[1] - offset;
686 verts[n].Set( 0.0f, 0.0f, halfSize.z + offset.z );
687 for ( i = 0; i < n; i++ ) {
688 // verts
689 angle = idMath::TWO_PI * i / n;
690 verts[i].x = cos( angle ) * halfSize.x + offset.x;
691 verts[i].y = sin( angle ) * halfSize.y + offset.y;
692 verts[i].z = -halfSize.z + offset.z;
693 // edges
694 ii = i + 1;
695 edges[ii].v[0] = i;
696 edges[ii].v[1] = ii % n;
697 edges[n+ii].v[0] = i;
698 edges[n+ii].v[1] = n;
699 // vertical polygon edges
700 polys[i].numEdges = 3;
701 polys[i].edges[0] = ii;
702 polys[i].edges[1] = n + (ii % n) + 1;
703 polys[i].edges[2] = -(n + ii);
704 // bottom polygon edges
705 polys[n].edges[i] = -(n - i);
706 }
707 // bottom polygon numEdges
708 polys[n].numEdges = n;
709
710 // polygons
711 for ( i = 0; i < n; i++ ) {
712 // polygon plane
713 polys[i].normal = (verts[(i+1)%n] - verts[i]).Cross( verts[n] - verts[i] );
714 polys[i].normal.Normalize();
715 polys[i].dist = polys[i].normal * verts[i];
716 // polygon bounds
717 polys[i].bounds.Clear();
718 polys[i].bounds.AddPoint( verts[i] );
719 polys[i].bounds.AddPoint( verts[(i+1)%n] );
720 polys[i].bounds.AddPoint( verts[n] );
721 }
722 // bottom polygon plane
723 polys[n].normal.Set( 0.0f, 0.0f, -1.0f );
724 polys[n].dist = -coneBounds[0][2];
725 // trm bounds
726 bounds = coneBounds;
727 // bottom polygon bounds
728 polys[n].bounds = bounds;
729 polys[n].bounds[1][2] = bounds[0][2];
730 // convex model
731 isConvex = true;
732
733 GenerateEdgeNormals();
734 }
735
736 /*
737 ============
738 idTraceModel::SetupCone
739
740 The origin is placed at the apex of the cone.
741 ============
742 */
SetupCone(const float height,const float width,const int numSides)743 void idTraceModel::SetupCone( const float height, const float width, const int numSides ) {
744 idBounds coneBounds;
745 float halfWidth;
746
747 halfWidth = width * 0.5f;
748 coneBounds[0].Set( -halfWidth, -halfWidth, -height );
749 coneBounds[1].Set( halfWidth, halfWidth, 0.0f );
750 SetupCone( coneBounds, numSides );
751 }
752
753 /*
754 ============
755 idTraceModel::SetupBone
756
757 The origin is placed at the center of the bone.
758 ============
759 */
SetupBone(const float length,const float width)760 void idTraceModel::SetupBone( const float length, const float width ) {
761 int i, j, edgeNum;
762 float halfLength = length * 0.5f;
763
764 if ( type != TRM_BONE ) {
765 InitBone();
766 }
767 // offset to center
768 offset.Set( 0.0f, 0.0f, 0.0f );
769 // set vertices
770 verts[0].Set( 0.0f, 0.0f, -halfLength );
771 verts[1].Set( 0.0f, width * -0.5f, 0.0f );
772 verts[2].Set( width * 0.5f, width * 0.25f, 0.0f );
773 verts[3].Set( width * -0.5f, width * 0.25f, 0.0f );
774 verts[4].Set( 0.0f, 0.0f, halfLength );
775 // set bounds
776 bounds[0].Set( width * -0.5f, width * -0.5f, -halfLength );
777 bounds[1].Set( width * 0.5f, width * 0.25f, halfLength );
778 // poly plane normals
779 polys[0].normal = ( verts[2] - verts[0] ).Cross( verts[1] - verts[0] );
780 polys[0].normal.Normalize();
781 polys[2].normal.Set( -polys[0].normal[0], polys[0].normal[1], polys[0].normal[2] );
782 polys[3].normal.Set( polys[0].normal[0], polys[0].normal[1], -polys[0].normal[2] );
783 polys[5].normal.Set( -polys[0].normal[0], polys[0].normal[1], -polys[0].normal[2] );
784 polys[1].normal = (verts[3] - verts[0]).Cross(verts[2] - verts[0]);
785 polys[1].normal.Normalize();
786 polys[4].normal.Set( polys[1].normal[0], polys[1].normal[1], -polys[1].normal[2] );
787 // poly plane distances
788 for ( i = 0; i < 6; i++ ) {
789 polys[i].dist = polys[i].normal * verts[ edges[ abs(polys[i].edges[0]) ].v[0] ];
790 polys[i].bounds.Clear();
791 for ( j = 0; j < 3; j++ ) {
792 edgeNum = polys[i].edges[ j ];
793 polys[i].bounds.AddPoint( verts[ edges[abs(edgeNum)].v[edgeNum < 0] ] );
794 }
795 }
796
797 GenerateEdgeNormals();
798 }
799
800 /*
801 ============
802 idTraceModel::InitBone
803
804 Initialize size independent bone.
805 ============
806 */
InitBone(void)807 void idTraceModel::InitBone( void ) {
808 int i;
809
810 type = TRM_BONE;
811 numVerts = 5;
812 numEdges = 9;
813 numPolys = 6;
814
815 // set bone edges
816 for ( i = 0; i < 3; i++ ) {
817 edges[ i + 1 ].v[0] = 0;
818 edges[ i + 1 ].v[1] = i + 1;
819 edges[ i + 4 ].v[0] = 1 + i;
820 edges[ i + 4 ].v[1] = 1 + ((i + 1) % 3);
821 edges[ i + 7 ].v[0] = i + 1;
822 edges[ i + 7 ].v[1] = 4;
823 }
824
825 // all edges of a polygon go counter clockwise
826 polys[0].numEdges = 3;
827 polys[0].edges[0] = 2;
828 polys[0].edges[1] = -4;
829 polys[0].edges[2] = -1;
830
831 polys[1].numEdges = 3;
832 polys[1].edges[0] = 3;
833 polys[1].edges[1] = -5;
834 polys[1].edges[2] = -2;
835
836 polys[2].numEdges = 3;
837 polys[2].edges[0] = 1;
838 polys[2].edges[1] = -6;
839 polys[2].edges[2] = -3;
840
841 polys[3].numEdges = 3;
842 polys[3].edges[0] = 4;
843 polys[3].edges[1] = 8;
844 polys[3].edges[2] = -7;
845
846 polys[4].numEdges = 3;
847 polys[4].edges[0] = 5;
848 polys[4].edges[1] = 9;
849 polys[4].edges[2] = -8;
850
851 polys[5].numEdges = 3;
852 polys[5].edges[0] = 6;
853 polys[5].edges[1] = 7;
854 polys[5].edges[2] = -9;
855
856 // convex model
857 isConvex = true;
858 }
859
860 /*
861 ============
862 idTraceModel::SetupPolygon
863 ============
864 */
SetupPolygon(const idVec3 * v,const int count)865 void idTraceModel::SetupPolygon( const idVec3 *v, const int count ) {
866 int i, j;
867 idVec3 mid;
868
869 type = TRM_POLYGON;
870 numVerts = count;
871 // times three because we need to be able to turn the polygon into a volume
872 if ( numVerts * 3 > MAX_TRACEMODEL_EDGES ) {
873 idLib::common->Printf( "WARNING: idTraceModel::SetupPolygon: too many vertices\n" );
874 numVerts = MAX_TRACEMODEL_EDGES / 3;
875 }
876
877 numEdges = numVerts;
878 numPolys = 2;
879 // set polygon planes
880 polys[0].numEdges = numEdges;
881 polys[0].normal = ( v[1] - v[0] ).Cross( v[2] - v[0] );
882 polys[0].normal.Normalize();
883 polys[0].dist = polys[0].normal * v[0];
884 polys[1].numEdges = numEdges;
885 polys[1].normal = -polys[0].normal;
886 polys[1].dist = -polys[0].dist;
887 // setup verts, edges and polygons
888 polys[0].bounds.Clear();
889 mid = vec3_origin;
890 for ( i = 0, j = 1; i < numVerts; i++, j++ ) {
891 if ( j >= numVerts ) {
892 j = 0;
893 }
894 verts[i] = v[i];
895 edges[i+1].v[0] = i;
896 edges[i+1].v[1] = j;
897 edges[i+1].normal = polys[0].normal.Cross( v[i] - v[j] );
898 edges[i+1].normal.Normalize();
899 polys[0].edges[i] = i + 1;
900 polys[1].edges[i] = -(numVerts - i);
901 polys[0].bounds.AddPoint( verts[i] );
902 mid += v[i];
903 }
904 polys[1].bounds = polys[0].bounds;
905 // offset to center
906 offset = mid * (1.0f / numVerts);
907 // total bounds
908 bounds = polys[0].bounds;
909 // considered non convex because the model has no volume
910 isConvex = false;
911 }
912
913 /*
914 ============
915 idTraceModel::SetupPolygon
916 ============
917 */
SetupPolygon(const idWinding & w)918 void idTraceModel::SetupPolygon( const idWinding &w ) {
919 int i;
920 idVec3 *verts;
921
922 verts = (idVec3 *) _alloca16( w.GetNumPoints() * sizeof( idVec3 ) );
923 for ( i = 0; i < w.GetNumPoints(); i++ ) {
924 verts[i] = w[i].ToVec3();
925 }
926 SetupPolygon( verts, w.GetNumPoints() );
927 }
928
929 /*
930 ============
931 idTraceModel::VolumeFromPolygon
932 ============
933 */
VolumeFromPolygon(idTraceModel & trm,float thickness) const934 void idTraceModel::VolumeFromPolygon( idTraceModel &trm, float thickness ) const {
935 int i;
936
937 trm = *this;
938 trm.type = TRM_POLYGONVOLUME;
939 trm.numVerts = numVerts * 2;
940 trm.numEdges = numEdges * 3;
941 trm.numPolys = numEdges + 2;
942 for ( i = 0; i < numEdges; i++ ) {
943 trm.verts[ numVerts + i ] = verts[i] - thickness * polys[0].normal;
944 trm.edges[ numEdges + i + 1 ].v[0] = numVerts + i;
945 trm.edges[ numEdges + i + 1 ].v[1] = numVerts + (i+1) % numVerts;
946 trm.edges[ numEdges * 2 + i + 1 ].v[0] = i;
947 trm.edges[ numEdges * 2 + i + 1 ].v[1] = numVerts + i;
948 trm.polys[1].edges[i] = -(numEdges + i + 1);
949 trm.polys[2+i].numEdges = 4;
950 trm.polys[2+i].edges[0] = -(i + 1);
951 trm.polys[2+i].edges[1] = numEdges*2 + i + 1;
952 trm.polys[2+i].edges[2] = numEdges + i + 1;
953 trm.polys[2+i].edges[3] = -(numEdges*2 + (i+1) % numEdges + 1);
954 trm.polys[2+i].normal = (verts[(i + 1) % numVerts] - verts[i]).Cross( polys[0].normal );
955 trm.polys[2+i].normal.Normalize();
956 trm.polys[2+i].dist = trm.polys[2+i].normal * verts[i];
957 }
958 trm.polys[1].dist = trm.polys[1].normal * trm.verts[ numEdges ];
959
960 trm.GenerateEdgeNormals();
961 }
962
963 /*
964 ============
965 idTraceModel::GenerateEdgeNormals
966 ============
967 */
968 #define SHARP_EDGE_DOT -0.7f
969
GenerateEdgeNormals(void)970 int idTraceModel::GenerateEdgeNormals( void ) {
971 int i, j, edgeNum, numSharpEdges;
972 float dot;
973 idVec3 dir;
974 traceModelPoly_t *poly;
975 traceModelEdge_t *edge;
976
977 for ( i = 0; i <= numEdges; i++ ) {
978 edges[i].normal.Zero();
979 }
980
981 numSharpEdges = 0;
982 for ( i = 0; i < numPolys; i++ ) {
983 poly = polys + i;
984 for ( j = 0; j < poly->numEdges; j++ ) {
985 edgeNum = poly->edges[j];
986 edge = edges + abs( edgeNum );
987 if ( edge->normal[0] == 0.0f && edge->normal[1] == 0.0f && edge->normal[2] == 0.0f ) {
988 edge->normal = poly->normal;
989 }
990 else {
991 dot = edge->normal * poly->normal;
992 // if the two planes make a very sharp edge
993 if ( dot < SHARP_EDGE_DOT ) {
994 // max length normal pointing outside both polygons
995 dir = verts[ edge->v[edgeNum > 0]] - verts[ edge->v[edgeNum < 0]];
996 edge->normal = edge->normal.Cross( dir ) + poly->normal.Cross( -dir );
997 edge->normal *= ( 0.5f / ( 0.5f + 0.5f * SHARP_EDGE_DOT ) ) / edge->normal.Length();
998 numSharpEdges++;
999 }
1000 else {
1001 edge->normal = ( 0.5f / ( 0.5f + 0.5f * dot ) ) * ( edge->normal + poly->normal );
1002 }
1003 }
1004 }
1005 }
1006 return numSharpEdges;
1007 }
1008
1009 /*
1010 ============
1011 idTraceModel::Translate
1012 ============
1013 */
Translate(const idVec3 & translation)1014 void idTraceModel::Translate( const idVec3 &translation ) {
1015 int i;
1016
1017 for ( i = 0; i < numVerts; i++ ) {
1018 verts[i] += translation;
1019 }
1020 for ( i = 0; i < numPolys; i++ ) {
1021 polys[i].dist += polys[i].normal * translation;
1022 polys[i].bounds[0] += translation;
1023 polys[i].bounds[1] += translation;
1024 }
1025 offset += translation;
1026 bounds[0] += translation;
1027 bounds[1] += translation;
1028 }
1029
1030 /*
1031 ============
1032 idTraceModel::Rotate
1033 ============
1034 */
Rotate(const idMat3 & rotation)1035 void idTraceModel::Rotate( const idMat3 &rotation ) {
1036 int i, j, edgeNum;
1037
1038 for ( i = 0; i < numVerts; i++ ) {
1039 verts[i] *= rotation;
1040 }
1041
1042 bounds.Clear();
1043 for ( i = 0; i < numPolys; i++ ) {
1044 polys[i].normal *= rotation;
1045 polys[i].bounds.Clear();
1046 edgeNum = 0;
1047 for ( j = 0; j < polys[i].numEdges; j++ ) {
1048 edgeNum = polys[i].edges[j];
1049 polys[i].bounds.AddPoint( verts[edges[abs(edgeNum)].v[INTSIGNBITSET(edgeNum)]] );
1050 }
1051 polys[i].dist = polys[i].normal * verts[edges[abs(edgeNum)].v[INTSIGNBITSET(edgeNum)]];
1052 bounds += polys[i].bounds;
1053 }
1054
1055 GenerateEdgeNormals();
1056 }
1057
1058 /*
1059 ============
1060 idTraceModel::Shrink
1061 ============
1062 */
Shrink(const float m)1063 void idTraceModel::Shrink( const float m ) {
1064 int i, j, edgeNum;
1065 traceModelEdge_t *edge;
1066 idVec3 dir;
1067
1068 if ( type == TRM_POLYGON ) {
1069 for ( i = 0; i < numEdges; i++ ) {
1070 edgeNum = polys[0].edges[i];
1071 edge = &edges[abs(edgeNum)];
1072 dir = verts[ edge->v[ INTSIGNBITSET(edgeNum) ] ] - verts[ edge->v[ INTSIGNBITNOTSET(edgeNum) ] ];
1073 if ( dir.Normalize() < 2.0f * m ) {
1074 continue;
1075 }
1076 dir *= m;
1077 verts[ edge->v[ 0 ] ] -= dir;
1078 verts[ edge->v[ 1 ] ] += dir;
1079 }
1080 return;
1081 }
1082
1083 for ( i = 0; i < numPolys; i++ ) {
1084 polys[i].dist -= m;
1085
1086 for ( j = 0; j < polys[i].numEdges; j++ ) {
1087 edgeNum = polys[i].edges[j];
1088 edge = &edges[abs(edgeNum)];
1089 verts[ edge->v[ INTSIGNBITSET(edgeNum) ] ] -= polys[i].normal * m;
1090 }
1091 }
1092 }
1093
1094 /*
1095 ============
1096 idTraceModel::Compare
1097 ============
1098 */
Compare(const idTraceModel & trm) const1099 bool idTraceModel::Compare( const idTraceModel &trm ) const {
1100 int i;
1101
1102 if ( type != trm.type || numVerts != trm.numVerts ||
1103 numEdges != trm.numEdges || numPolys != trm.numPolys ) {
1104 return false;
1105 }
1106 if ( bounds != trm.bounds || offset != trm.offset ) {
1107 return false;
1108 }
1109
1110 switch( type ) {
1111 case TRM_INVALID:
1112 case TRM_BOX:
1113 case TRM_OCTAHEDRON:
1114 case TRM_DODECAHEDRON:
1115 case TRM_CYLINDER:
1116 case TRM_CONE:
1117 break;
1118 case TRM_BONE:
1119 case TRM_POLYGON:
1120 case TRM_POLYGONVOLUME:
1121 case TRM_CUSTOM:
1122 for ( i = 0; i < trm.numVerts; i++ ) {
1123 if ( verts[i] != trm.verts[i] ) {
1124 return false;
1125 }
1126 }
1127 break;
1128 }
1129 return true;
1130 }
1131
1132 /*
1133 ============
1134 idTraceModel::GetPolygonArea
1135 ============
1136 */
GetPolygonArea(int polyNum) const1137 float idTraceModel::GetPolygonArea( int polyNum ) const {
1138 int i;
1139 idVec3 base, v1, v2, cross;
1140 float total;
1141 const traceModelPoly_t *poly;
1142
1143 if ( polyNum < 0 || polyNum >= numPolys ) {
1144 return 0.0f;
1145 }
1146 poly = &polys[polyNum];
1147 total = 0.0f;
1148 base = verts[ edges[ abs(poly->edges[0]) ].v[ INTSIGNBITSET( poly->edges[0] ) ] ];
1149 for ( i = 0; i < poly->numEdges; i++ ) {
1150 v1 = verts[ edges[ abs(poly->edges[i]) ].v[ INTSIGNBITSET( poly->edges[i] ) ] ] - base;
1151 v2 = verts[ edges[ abs(poly->edges[i]) ].v[ INTSIGNBITNOTSET( poly->edges[i] ) ] ] - base;
1152 cross = v1.Cross( v2 );
1153 total += cross.Length();
1154 }
1155 return total * 0.5f;
1156 }
1157
1158 /*
1159 ============
1160 idTraceModel::GetOrderedSilhouetteEdges
1161 ============
1162 */
GetOrderedSilhouetteEdges(const int edgeIsSilEdge[MAX_TRACEMODEL_EDGES+1],int silEdges[MAX_TRACEMODEL_EDGES]) const1163 int idTraceModel::GetOrderedSilhouetteEdges( const int edgeIsSilEdge[MAX_TRACEMODEL_EDGES+1], int silEdges[MAX_TRACEMODEL_EDGES] ) const {
1164 int i, j, edgeNum, numSilEdges, nextSilVert;
1165 int unsortedSilEdges[MAX_TRACEMODEL_EDGES];
1166
1167 numSilEdges = 0;
1168 for ( i = 1; i <= numEdges; i++ ) {
1169 if ( edgeIsSilEdge[i] ) {
1170 unsortedSilEdges[numSilEdges++] = i;
1171 }
1172 }
1173
1174 silEdges[0] = unsortedSilEdges[0];
1175 unsortedSilEdges[0] = -1;
1176 nextSilVert = edges[silEdges[0]].v[0];
1177 for ( i = 1; i < numSilEdges; i++ ) {
1178 for ( j = 1; j < numSilEdges; j++ ) {
1179 edgeNum = unsortedSilEdges[j];
1180 if ( edgeNum >= 0 ) {
1181 if ( edges[edgeNum].v[0] == nextSilVert ) {
1182 nextSilVert = edges[edgeNum].v[1];
1183 silEdges[i] = edgeNum;
1184 break;
1185 }
1186 if ( edges[edgeNum].v[1] == nextSilVert ) {
1187 nextSilVert = edges[edgeNum].v[0];
1188 silEdges[i] = -edgeNum;
1189 break;
1190 }
1191 }
1192 }
1193 if ( j >= numSilEdges ) {
1194 silEdges[i] = 1; // shouldn't happen
1195 }
1196 unsortedSilEdges[j] = -1;
1197 }
1198 return numSilEdges;
1199 }
1200
1201 /*
1202 ============
1203 idTraceModel::GetProjectionSilhouetteEdges
1204 ============
1205 */
GetProjectionSilhouetteEdges(const idVec3 & projectionOrigin,int silEdges[MAX_TRACEMODEL_EDGES]) const1206 int idTraceModel::GetProjectionSilhouetteEdges( const idVec3 &projectionOrigin, int silEdges[MAX_TRACEMODEL_EDGES] ) const {
1207 int i, j, edgeNum;
1208 int edgeIsSilEdge[MAX_TRACEMODEL_EDGES+1];
1209 const traceModelPoly_t *poly;
1210 idVec3 dir;
1211
1212 memset( edgeIsSilEdge, 0, sizeof( edgeIsSilEdge ) );
1213
1214 for ( i = 0; i < numPolys; i++ ) {
1215 poly = &polys[i];
1216 edgeNum = poly->edges[0];
1217 dir = verts[ edges[abs(edgeNum)].v[ INTSIGNBITSET(edgeNum) ] ] - projectionOrigin;
1218 if ( dir * poly->normal < 0.0f ) {
1219 for ( j = 0; j < poly->numEdges; j++ ) {
1220 edgeNum = poly->edges[j];
1221 edgeIsSilEdge[abs(edgeNum)] ^= 1;
1222 }
1223 }
1224 }
1225
1226 return GetOrderedSilhouetteEdges( edgeIsSilEdge, silEdges );
1227 }
1228
1229 /*
1230 ============
1231 idTraceModel::GetParallelProjectionSilhouetteEdges
1232 ============
1233 */
GetParallelProjectionSilhouetteEdges(const idVec3 & projectionDir,int silEdges[MAX_TRACEMODEL_EDGES]) const1234 int idTraceModel::GetParallelProjectionSilhouetteEdges( const idVec3 &projectionDir, int silEdges[MAX_TRACEMODEL_EDGES] ) const {
1235 int i, j, edgeNum;
1236 int edgeIsSilEdge[MAX_TRACEMODEL_EDGES+1];
1237 const traceModelPoly_t *poly;
1238
1239 memset( edgeIsSilEdge, 0, sizeof( edgeIsSilEdge ) );
1240
1241 for ( i = 0; i < numPolys; i++ ) {
1242 poly = &polys[i];
1243 if ( projectionDir * poly->normal < 0.0f ) {
1244 for ( j = 0; j < poly->numEdges; j++ ) {
1245 edgeNum = poly->edges[j];
1246 edgeIsSilEdge[abs(edgeNum)] ^= 1;
1247 }
1248 }
1249 }
1250
1251 return GetOrderedSilhouetteEdges( edgeIsSilEdge, silEdges );
1252 }
1253
1254
1255 /*
1256
1257 credits to Brian Mirtich for his paper "Fast and Accurate Computation of Polyhedral Mass Properties"
1258
1259 */
1260
1261 typedef struct projectionIntegrals_s {
1262 float P1;
1263 float Pa, Pb;
1264 float Paa, Pab, Pbb;
1265 float Paaa, Paab, Pabb, Pbbb;
1266 } projectionIntegrals_t;
1267
1268 /*
1269 ============
1270 idTraceModel::ProjectionIntegrals
1271 ============
1272 */
ProjectionIntegrals(int polyNum,int a,int b,struct projectionIntegrals_s & integrals) const1273 void idTraceModel::ProjectionIntegrals( int polyNum, int a, int b, struct projectionIntegrals_s &integrals ) const {
1274 const traceModelPoly_t *poly;
1275 int i, edgeNum;
1276 idVec3 v1, v2;
1277 float a0, a1, da;
1278 float b0, b1, db;
1279 float a0_2, a0_3, a0_4, b0_2, b0_3, b0_4;
1280 float a1_2, a1_3, b1_2, b1_3;
1281 float C1, Ca, Caa, Caaa, Cb, Cbb, Cbbb;
1282 float Cab, Kab, Caab, Kaab, Cabb, Kabb;
1283
1284 memset(&integrals, 0, sizeof(projectionIntegrals_t));
1285 poly = &polys[polyNum];
1286 for ( i = 0; i < poly->numEdges; i++ ) {
1287 edgeNum = poly->edges[i];
1288 v1 = verts[ edges[ abs(edgeNum) ].v[ edgeNum < 0 ] ];
1289 v2 = verts[ edges[ abs(edgeNum) ].v[ edgeNum > 0 ] ];
1290 a0 = v1[a];
1291 b0 = v1[b];
1292 a1 = v2[a];
1293 b1 = v2[b];
1294 da = a1 - a0;
1295 db = b1 - b0;
1296 a0_2 = a0 * a0;
1297 a0_3 = a0_2 * a0;
1298 a0_4 = a0_3 * a0;
1299 b0_2 = b0 * b0;
1300 b0_3 = b0_2 * b0;
1301 b0_4 = b0_3 * b0;
1302 a1_2 = a1 * a1;
1303 a1_3 = a1_2 * a1;
1304 b1_2 = b1 * b1;
1305 b1_3 = b1_2 * b1;
1306
1307 C1 = a1 + a0;
1308 Ca = a1 * C1 + a0_2;
1309 Caa = a1 * Ca + a0_3;
1310 Caaa = a1 * Caa + a0_4;
1311 Cb = b1 * (b1 + b0) + b0_2;
1312 Cbb = b1 * Cb + b0_3;
1313 Cbbb = b1 * Cbb + b0_4;
1314 Cab = 3 * a1_2 + 2 * a1 * a0 + a0_2;
1315 Kab = a1_2 + 2 * a1 * a0 + 3 * a0_2;
1316 Caab = a0 * Cab + 4 * a1_3;
1317 Kaab = a1 * Kab + 4 * a0_3;
1318 Cabb = 4 * b1_3 + 3 * b1_2 * b0 + 2 * b1 * b0_2 + b0_3;
1319 Kabb = b1_3 + 2 * b1_2 * b0 + 3 * b1 * b0_2 + 4 * b0_3;
1320
1321 integrals.P1 += db * C1;
1322 integrals.Pa += db * Ca;
1323 integrals.Paa += db * Caa;
1324 integrals.Paaa += db * Caaa;
1325 integrals.Pb += da * Cb;
1326 integrals.Pbb += da * Cbb;
1327 integrals.Pbbb += da * Cbbb;
1328 integrals.Pab += db * (b1 * Cab + b0 * Kab);
1329 integrals.Paab += db * (b1 * Caab + b0 * Kaab);
1330 integrals.Pabb += da * (a1 * Cabb + a0 * Kabb);
1331 }
1332
1333 integrals.P1 *= (1.0f / 2.0f);
1334 integrals.Pa *= (1.0f / 6.0f);
1335 integrals.Paa *= (1.0f / 12.0f);
1336 integrals.Paaa *= (1.0f / 20.0f);
1337 integrals.Pb *= (1.0f / -6.0f);
1338 integrals.Pbb *= (1.0f / -12.0f);
1339 integrals.Pbbb *= (1.0f / -20.0f);
1340 integrals.Pab *= (1.0f / 24.0f);
1341 integrals.Paab *= (1.0f / 60.0f);
1342 integrals.Pabb *= (1.0f / -60.0f);
1343 }
1344
1345 typedef struct polygonIntegrals_s {
1346 float Fa, Fb, Fc;
1347 float Faa, Fbb, Fcc;
1348 float Faaa, Fbbb, Fccc;
1349 float Faab, Fbbc, Fcca;
1350 } polygonIntegrals_t;
1351
1352 /*
1353 ============
1354 idTraceModel::PolygonIntegrals
1355 ============
1356 */
PolygonIntegrals(int polyNum,int a,int b,int c,struct polygonIntegrals_s & integrals) const1357 void idTraceModel::PolygonIntegrals( int polyNum, int a, int b, int c, struct polygonIntegrals_s &integrals ) const {
1358 projectionIntegrals_t pi;
1359 idVec3 n;
1360 float w;
1361 float k1, k2, k3, k4;
1362
1363 ProjectionIntegrals( polyNum, a, b, pi );
1364
1365 n = polys[polyNum].normal;
1366 w = -polys[polyNum].dist;
1367 k1 = 1 / n[c];
1368 k2 = k1 * k1;
1369 k3 = k2 * k1;
1370 k4 = k3 * k1;
1371
1372 integrals.Fa = k1 * pi.Pa;
1373 integrals.Fb = k1 * pi.Pb;
1374 integrals.Fc = -k2 * (n[a] * pi.Pa + n[b] * pi.Pb + w * pi.P1);
1375
1376 integrals.Faa = k1 * pi.Paa;
1377 integrals.Fbb = k1 * pi.Pbb;
1378 integrals.Fcc = k3 * (Square(n[a]) * pi.Paa + 2 * n[a] * n[b] * pi.Pab + Square(n[b]) * pi.Pbb
1379 + w * (2 * (n[a] * pi.Pa + n[b] * pi.Pb) + w * pi.P1));
1380
1381 integrals.Faaa = k1 * pi.Paaa;
1382 integrals.Fbbb = k1 * pi.Pbbb;
1383 integrals.Fccc = -k4 * (Cube(n[a]) * pi.Paaa + 3 * Square(n[a]) * n[b] * pi.Paab
1384 + 3 * n[a] * Square(n[b]) * pi.Pabb + Cube(n[b]) * pi.Pbbb
1385 + 3 * w * (Square(n[a]) * pi.Paa + 2 * n[a] * n[b] * pi.Pab + Square(n[b]) * pi.Pbb)
1386 + w * w * (3 * (n[a] * pi.Pa + n[b] * pi.Pb) + w * pi.P1));
1387
1388 integrals.Faab = k1 * pi.Paab;
1389 integrals.Fbbc = -k2 * (n[a] * pi.Pabb + n[b] * pi.Pbbb + w * pi.Pbb);
1390 integrals.Fcca = k3 * (Square(n[a]) * pi.Paaa + 2 * n[a] * n[b] * pi.Paab + Square(n[b]) * pi.Pabb
1391 + w * (2 * (n[a] * pi.Paa + n[b] * pi.Pab) + w * pi.Pa));
1392 }
1393
1394 typedef struct volumeIntegrals_s {
1395 float T0;
1396 idVec3 T1;
1397 idVec3 T2;
1398 idVec3 TP;
1399 } volumeIntegrals_t;
1400
1401 /*
1402 ============
1403 idTraceModel::VolumeIntegrals
1404 ============
1405 */
VolumeIntegrals(struct volumeIntegrals_s & integrals) const1406 void idTraceModel::VolumeIntegrals( struct volumeIntegrals_s &integrals ) const {
1407 const traceModelPoly_t *poly;
1408 polygonIntegrals_t pi;
1409 int i, a, b, c;
1410 float nx, ny, nz;
1411
1412 memset( &integrals, 0, sizeof(volumeIntegrals_t) );
1413 for ( i = 0; i < numPolys; i++ ) {
1414 poly = &polys[i];
1415
1416 nx = idMath::Fabs( poly->normal[0] );
1417 ny = idMath::Fabs( poly->normal[1] );
1418 nz = idMath::Fabs( poly->normal[2] );
1419 if ( nx > ny && nx > nz ) {
1420 c = 0;
1421 }
1422 else {
1423 c = (ny > nz) ? 1 : 2;
1424 }
1425 a = (c + 1) % 3;
1426 b = (a + 1) % 3;
1427
1428 PolygonIntegrals( i, a, b, c, pi );
1429
1430 integrals.T0 += poly->normal[0] * ((a == 0) ? pi.Fa : ((b == 0) ? pi.Fb : pi.Fc));
1431
1432 integrals.T1[a] += poly->normal[a] * pi.Faa;
1433 integrals.T1[b] += poly->normal[b] * pi.Fbb;
1434 integrals.T1[c] += poly->normal[c] * pi.Fcc;
1435 integrals.T2[a] += poly->normal[a] * pi.Faaa;
1436 integrals.T2[b] += poly->normal[b] * pi.Fbbb;
1437 integrals.T2[c] += poly->normal[c] * pi.Fccc;
1438 integrals.TP[a] += poly->normal[a] * pi.Faab;
1439 integrals.TP[b] += poly->normal[b] * pi.Fbbc;
1440 integrals.TP[c] += poly->normal[c] * pi.Fcca;
1441 }
1442
1443 integrals.T1 *= 0.5f;
1444 integrals.T2 *= (1.0f / 3.0f);
1445 integrals.TP *= 0.5f;
1446 }
1447
1448 /*
1449 ============
1450 idTraceModel::GetMassProperties
1451 ============
1452 */
GetMassProperties(const float density,float & mass,idVec3 & centerOfMass,idMat3 & inertiaTensor) const1453 void idTraceModel::GetMassProperties( const float density, float &mass, idVec3 ¢erOfMass, idMat3 &inertiaTensor ) const {
1454 volumeIntegrals_t integrals;
1455
1456 // if polygon trace model
1457 if ( type == TRM_POLYGON ) {
1458 idTraceModel trm;
1459
1460 VolumeFromPolygon( trm, 1.0f );
1461 trm.GetMassProperties( density, mass, centerOfMass, inertiaTensor );
1462 return;
1463 }
1464
1465 VolumeIntegrals( integrals );
1466
1467 // if no volume
1468 if ( integrals.T0 == 0.0f ) {
1469 mass = 1.0f;
1470 centerOfMass.Zero();
1471 inertiaTensor.Identity();
1472 return;
1473 }
1474
1475 // mass of model
1476 mass = density * integrals.T0;
1477 // center of mass
1478 centerOfMass = integrals.T1 / integrals.T0;
1479 // compute inertia tensor
1480 inertiaTensor[0][0] = density * (integrals.T2[1] + integrals.T2[2]);
1481 inertiaTensor[1][1] = density * (integrals.T2[2] + integrals.T2[0]);
1482 inertiaTensor[2][2] = density * (integrals.T2[0] + integrals.T2[1]);
1483 inertiaTensor[0][1] = inertiaTensor[1][0] = - density * integrals.TP[0];
1484 inertiaTensor[1][2] = inertiaTensor[2][1] = - density * integrals.TP[1];
1485 inertiaTensor[2][0] = inertiaTensor[0][2] = - density * integrals.TP[2];
1486 // translate inertia tensor to center of mass
1487 inertiaTensor[0][0] -= mass * (centerOfMass[1]*centerOfMass[1] + centerOfMass[2]*centerOfMass[2]);
1488 inertiaTensor[1][1] -= mass * (centerOfMass[2]*centerOfMass[2] + centerOfMass[0]*centerOfMass[0]);
1489 inertiaTensor[2][2] -= mass * (centerOfMass[0]*centerOfMass[0] + centerOfMass[1]*centerOfMass[1]);
1490 inertiaTensor[0][1] = inertiaTensor[1][0] += mass * centerOfMass[0] * centerOfMass[1];
1491 inertiaTensor[1][2] = inertiaTensor[2][1] += mass * centerOfMass[1] * centerOfMass[2];
1492 inertiaTensor[2][0] = inertiaTensor[0][2] += mass * centerOfMass[2] * centerOfMass[0];
1493 }
1494