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