neo/idlib/geometry/TraceModel.cpp

   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
 163         GenerateEdgeNormals();
 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
 212         GenerateEdgeNormals();
 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 */
 239 void idTraceModel::InitOctahedron( void ) {
 240
 241         type = TRM_OCTAHEDRON;
 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 ) {
 316                 InitDodecahedron();
 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
 386         GenerateEdgeNormals();
 387 }
 388
 389 /*
 390 ============
 391 idTraceModel::SetupDodecahedron
 392
 393   The origin is placed at the center of the octahedron.
 394 ============
 395 */
 396 void idTraceModel::SetupDodecahedron( const float size ) {
 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 */
 413 void idTraceModel::InitDodecahedron( void ) {
 414
 415         type = TRM_DODECAHEDRON;
 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
 633         GenerateEdgeNormals();
 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
 734         GenerateEdgeNormals();
 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
 798         GenerateEdgeNormals();
 799 }
 800
 801 /*
 802 ============
 803 idTraceModel::InitBone
 804
 805   Initialize size independent bone.
 806 ============
 807 */
 808 void idTraceModel::InitBone( void ) {
 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" );
 875                 numVerts = MAX_TRACEMODEL_EDGES / 3;
 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 */
 919 void idTraceModel::SetupPolygon( const idWinding &w ) {
 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
 971 int idTraceModel::GenerateEdgeNormals( void ) {
 972         int i, j, edgeNum, numSharpEdges;
 973         float dot;
 974         idVec3 dir;
 975         traceModelPoly_t *poly;
 976         traceModelEdge_t *edge;
 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
1056         GenerateEdgeNormals();
1057 }
1058
1059 /*
1060 ============
1061 idTraceModel::Shrink
1062 ============
1063 */
1064 void idTraceModel::Shrink( const float m ) {
1065         int i, j, edgeNum;
1066         traceModelEdge_t *edge;
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;
1267 } projectionIntegrals_t;
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;
1351 } polygonIntegrals_t;
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 {
1359         projectionIntegrals_t pi;
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;
1397         idVec3 T1;
1398         idVec3 T2;
1399         idVec3 TP;
1400 } volumeIntegrals_t;
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 }