neo/cm/CollisionModel_load.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 /*
  30 ===============================================================================
  31
  32         Trace model vs. polygonal model collision detection.
  33
  34         It is more important to minimize the number of collision polygons
  35         than it is to minimize the number of edges used for collision
  36         detection (total edges - internal edges).
  37
  38         Stitching the world tends to minimize the number of edges used
  39         for collision detection (more internal edges). However stitching
  40         also results in more collision polygons which usually makes a
  41         stitched world slower.
  42
  43         In an average map over 30% of all edges is internal.
  44
  45 ===============================================================================
  46 */
  47
  48 #include "../idlib/precompiled.h"
  49 #pragma hdrstop
  50
  51 #include "CollisionModel_local.h"
  52
  53
  54 idCollisionModelManagerLocal    collisionModelManagerLocal;
  55 idCollisionModelManager *               collisionModelManager = &collisionModelManagerLocal;
  56
  57 cm_windingList_t *                              cm_windingList;
  58 cm_windingList_t *                              cm_outList;
  59 cm_windingList_t *                              cm_tmpList;
  60
  61 idHashIndex *                                   cm_vertexHash;
  62 idHashIndex *                                   cm_edgeHash;
  63
  64 idBounds                                                cm_modelBounds;
  65 int                                                             cm_vertexShift;
  66
  67
  68 /*
  69 ===============================================================================
  70
  71 Proc BSP tree for data pruning
  72
  73 ===============================================================================
  74 */
  75
  76 /*
  77 ================
  78 idCollisionModelManagerLocal::ParseProcNodes
  79 ================
  80 */
  81 void idCollisionModelManagerLocal::ParseProcNodes( idLexer *src ) {
  82         int i;
  83
  84         src->ExpectTokenString( "{" );
  85
  86         numProcNodes = src->ParseInt();
  87         if ( numProcNodes < 0 ) {
  88                 src->Error( "ParseProcNodes: bad numProcNodes" );
  89         }
  90         procNodes = (cm_procNode_t *)Mem_ClearedAlloc( numProcNodes * sizeof( cm_procNode_t ) );
  91
  92         for ( i = 0; i < numProcNodes; i++ ) {
  93                 cm_procNode_t *node;
  94
  95                 node = &procNodes[i];
  96
  97                 src->Parse1DMatrix( 4, node->plane.ToFloatPtr() );
  98                 node->children[0] = src->ParseInt();
  99                 node->children[1] = src->ParseInt();
 100         }
 101
 102         src->ExpectTokenString( "}" );
 103 }
 104
 105 /*
 106 ================
 107 idCollisionModelManagerLocal::LoadProcBSP
 108
 109   FIXME: if the nodes would be at the start of the .proc file it would speed things up considerably
 110 ================
 111 */
 112 void idCollisionModelManagerLocal::LoadProcBSP( const char *name ) {
 113         idStr filename;
 114         idToken token;
 115         idLexer *src;
 116
 117         // load it
 118         filename = name;
 119         filename.SetFileExtension( PROC_FILE_EXT );
 120         src = new idLexer( filename, LEXFL_NOSTRINGCONCAT | LEXFL_NODOLLARPRECOMPILE );
 121         if ( !src->IsLoaded() ) {
 122                 common->Warning( "idCollisionModelManagerLocal::LoadProcBSP: couldn't load %s", filename.c_str() );
 123                 delete src;
 124                 return;
 125         }
 126
 127         if ( !src->ReadToken( &token ) || token.Icmp( PROC_FILE_ID ) ) {
 128                 common->Warning( "idCollisionModelManagerLocal::LoadProcBSP: bad id '%s' instead of '%s'", token.c_str(), PROC_FILE_ID );
 129                 delete src;
 130                 return;
 131         }
 132
 133         // parse the file
 134         while ( 1 ) {
 135                 if ( !src->ReadToken( &token ) ) {
 136                         break;
 137                 }
 138
 139                 if ( token == "model" ) {
 140                         src->SkipBracedSection();
 141                         continue;
 142                 }
 143
 144                 if ( token == "shadowModel" ) {
 145                         src->SkipBracedSection();
 146                         continue;
 147                 }
 148
 149                 if ( token == "interAreaPortals" ) {
 150                         src->SkipBracedSection();
 151                         continue;
 152                 }
 153
 154                 if ( token == "nodes" ) {
 155                         ParseProcNodes( src );
 156                         break;
 157                 }
 158
 159                 src->Error( "idCollisionModelManagerLocal::LoadProcBSP: bad token \"%s\"", token.c_str() );
 160         }
 161
 162         delete src;
 163 }
 164
 165 /*
 166 ===============================================================================
 167
 168 Free map
 169
 170 ===============================================================================
 171 */
 172
 173 /*
 174 ================
 175 idCollisionModelManagerLocal::Clear
 176 ================
 177 */
 178 void idCollisionModelManagerLocal::Clear( void ) {
 179         mapName.Clear();
 180         mapFileTime = 0;
 181         loaded = 0;
 182         checkCount = 0;
 183         maxModels = 0;
 184         numModels = 0;
 185         models = NULL;
 186         memset( trmPolygons, 0, sizeof( trmPolygons ) );
 187         trmBrushes[0] = NULL;
 188         trmMaterial = NULL;
 189         numProcNodes = 0;
 190         procNodes = NULL;
 191         getContacts = false;
 192         contacts = NULL;
 193         maxContacts = 0;
 194         numContacts = 0;
 195 }
 196
 197 /*
 198 ================
 199 idCollisionModelManagerLocal::RemovePolygonReferences_r
 200 ================
 201 */
 202 void idCollisionModelManagerLocal::RemovePolygonReferences_r( cm_node_t *node, cm_polygon_t *p ) {
 203         cm_polygonRef_t *pref;
 204
 205         while( node ) {
 206                 for ( pref = node->polygons; pref; pref = pref->next ) {
 207                         if ( pref->p == p ) {
 208                                 pref->p = NULL;
 209                                 // cannot return here because we can have links down the tree due to polygon merging
 210                                 //return;
 211                         }
 212                 }
 213                 // if leaf node
 214                 if ( node->planeType == -1 ) {
 215                         break;
 216                 }
 217                 if ( p->bounds[0][node->planeType] > node->planeDist ) {
 218                         node = node->children[0];
 219                 }
 220                 else if ( p->bounds[1][node->planeType] < node->planeDist ) {
 221                         node = node->children[1];
 222                 }
 223                 else {
 224                         RemovePolygonReferences_r( node->children[1], p );
 225                         node = node->children[0];
 226                 }
 227         }
 228 }
 229
 230 /*
 231 ================
 232 idCollisionModelManagerLocal::RemoveBrushReferences_r
 233 ================
 234 */
 235 void idCollisionModelManagerLocal::RemoveBrushReferences_r( cm_node_t *node, cm_brush_t *b ) {
 236         cm_brushRef_t *bref;
 237
 238         while( node ) {
 239                 for ( bref = node->brushes; bref; bref = bref->next ) {
 240                         if ( bref->b == b ) {
 241                                 bref->b = NULL;
 242                                 return;
 243                         }
 244                 }
 245                 // if leaf node
 246                 if ( node->planeType == -1 ) {
 247                         break;
 248                 }
 249                 if ( b->bounds[0][node->planeType] > node->planeDist ) {
 250                         node = node->children[0];
 251                 }
 252                 else if ( b->bounds[1][node->planeType] < node->planeDist ) {
 253                         node = node->children[1];
 254                 }
 255                 else {
 256                         RemoveBrushReferences_r( node->children[1], b );
 257                         node = node->children[0];
 258                 }
 259         }
 260 }
 261
 262 /*
 263 ================
 264 idCollisionModelManagerLocal::FreeNode
 265 ================
 266 */
 267 void idCollisionModelManagerLocal::FreeNode( cm_node_t *node ) {
 268         // don't free the node here
 269         // the nodes are allocated in blocks which are freed when the model is freed
 270 }
 271
 272 /*
 273 ================
 274 idCollisionModelManagerLocal::FreePolygonReference
 275 ================
 276 */
 277 void idCollisionModelManagerLocal::FreePolygonReference( cm_polygonRef_t *pref ) {
 278         // don't free the polygon reference here
 279         // the polygon references are allocated in blocks which are freed when the model is freed
 280 }
 281
 282 /*
 283 ================
 284 idCollisionModelManagerLocal::FreeBrushReference
 285 ================
 286 */
 287 void idCollisionModelManagerLocal::FreeBrushReference( cm_brushRef_t *bref ) {
 288         // don't free the brush reference here
 289         // the brush references are allocated in blocks which are freed when the model is freed
 290 }
 291
 292 /*
 293 ================
 294 idCollisionModelManagerLocal::FreePolygon
 295 ================
 296 */
 297 void idCollisionModelManagerLocal::FreePolygon( cm_model_t *model, cm_polygon_t *poly ) {
 298         model->numPolygons--;
 299         model->polygonMemory -= sizeof( cm_polygon_t ) + ( poly->numEdges - 1 ) * sizeof( poly->edges[0] );
 300         if ( model->polygonBlock == NULL ) {
 301                 Mem_Free( poly );
 302         }
 303 }
 304
 305 /*
 306 ================
 307 idCollisionModelManagerLocal::FreeBrush
 308 ================
 309 */
 310 void idCollisionModelManagerLocal::FreeBrush( cm_model_t *model, cm_brush_t *brush ) {
 311         model->numBrushes--;
 312         model->brushMemory -= sizeof( cm_brush_t ) + ( brush->numPlanes - 1 ) * sizeof( brush->planes[0] );
 313         if ( model->brushBlock == NULL ) {
 314                 Mem_Free( brush );
 315         }
 316 }
 317
 318 /*
 319 ================
 320 idCollisionModelManagerLocal::FreeTree_r
 321 ================
 322 */
 323 void idCollisionModelManagerLocal::FreeTree_r( cm_model_t *model, cm_node_t *headNode, cm_node_t *node ) {
 324         cm_polygonRef_t *pref;
 325         cm_polygon_t *p;
 326         cm_brushRef_t *bref;
 327         cm_brush_t *b;
 328
 329         // free all polygons at this node
 330         for ( pref = node->polygons; pref; pref = node->polygons ) {
 331                 p = pref->p;
 332                 if ( p ) {
 333                         // remove all other references to this polygon
 334                         RemovePolygonReferences_r( headNode, p );
 335                         FreePolygon( model, p );
 336                 }
 337                 node->polygons = pref->next;
 338                 FreePolygonReference( pref );
 339         }
 340         // free all brushes at this node
 341         for ( bref = node->brushes; bref; bref = node->brushes ) {
 342                 b = bref->b;
 343                 if ( b ) {
 344                         // remove all other references to this brush
 345                         RemoveBrushReferences_r( headNode, b );
 346                         FreeBrush( model, b );
 347                 }
 348                 node->brushes = bref->next;
 349                 FreeBrushReference( bref );
 350         }
 351         // recurse down the tree
 352         if ( node->planeType != -1 ) {
 353                 FreeTree_r( model, headNode, node->children[0] );
 354                 node->children[0] = NULL;
 355                 FreeTree_r( model, headNode, node->children[1] );
 356                 node->children[1] = NULL;
 357         }
 358         FreeNode( node );
 359 }
 360
 361 /*
 362 ================
 363 idCollisionModelManagerLocal::FreeModel
 364 ================
 365 */
 366 void idCollisionModelManagerLocal::FreeModel( cm_model_t *model ) {
 367         cm_polygonRefBlock_t *polygonRefBlock, *nextPolygonRefBlock;
 368         cm_brushRefBlock_t *brushRefBlock, *nextBrushRefBlock;
 369         cm_nodeBlock_t *nodeBlock, *nextNodeBlock;
 370
 371         // free the tree structure
 372         if ( model->node ) {
 373                 FreeTree_r( model, model->node, model->node );
 374         }
 375         // free blocks with polygon references
 376         for ( polygonRefBlock = model->polygonRefBlocks; polygonRefBlock; polygonRefBlock = nextPolygonRefBlock ) {
 377                 nextPolygonRefBlock = polygonRefBlock->next;
 378                 Mem_Free( polygonRefBlock );
 379         }
 380         // free blocks with brush references
 381         for ( brushRefBlock = model->brushRefBlocks; brushRefBlock; brushRefBlock = nextBrushRefBlock ) {
 382                 nextBrushRefBlock = brushRefBlock->next;
 383                 Mem_Free( brushRefBlock );
 384         }
 385         // free blocks with nodes
 386         for ( nodeBlock = model->nodeBlocks; nodeBlock; nodeBlock = nextNodeBlock ) {
 387                 nextNodeBlock = nodeBlock->next;
 388                 Mem_Free( nodeBlock );
 389         }
 390         // free block allocated polygons
 391         Mem_Free( model->polygonBlock );
 392         // free block allocated brushes
 393         Mem_Free( model->brushBlock );
 394         // free edges
 395         Mem_Free( model->edges );
 396         // free vertices
 397         Mem_Free( model->vertices );
 398         // free the model
 399         delete model;
 400 }
 401
 402 /*
 403 ================
 404 idCollisionModelManagerLocal::FreeMap
 405 ================
 406 */
 407 void idCollisionModelManagerLocal::FreeMap( void ) {
 408         int i;
 409
 410         if ( !loaded ) {
 411                 Clear();
 412                 return;
 413         }
 414
 415         for ( i = 0; i < maxModels; i++ ) {
 416                 if ( !models[i] ) {
 417                         continue;
 418                 }
 419                 FreeModel( models[i] );
 420         }
 421
 422         FreeTrmModelStructure();
 423
 424         Mem_Free( models );
 425
 426         Clear();
 427
 428         ShutdownHash();
 429 }
 430
 431 /*
 432 ================
 433 idCollisionModelManagerLocal::FreeTrmModelStructure
 434 ================
 435 */
 436 void idCollisionModelManagerLocal::FreeTrmModelStructure( void ) {
 437         int i;
 438
 439         assert( models );
 440         if ( !models[MAX_SUBMODELS] ) {
 441                 return;
 442         }
 443
 444         for ( i = 0; i < MAX_TRACEMODEL_POLYS; i++ ) {
 445                 FreePolygon( models[MAX_SUBMODELS], trmPolygons[i]->p );
 446         }
 447         FreeBrush( models[MAX_SUBMODELS], trmBrushes[0]->b );
 448
 449         models[MAX_SUBMODELS]->node->polygons = NULL;
 450         models[MAX_SUBMODELS]->node->brushes = NULL;
 451         FreeModel( models[MAX_SUBMODELS] );
 452 }
 453
 454
 455 /*
 456 ===============================================================================
 457
 458 Edge normals
 459
 460 ===============================================================================
 461 */
 462
 463 /*
 464 ================
 465 idCollisionModelManagerLocal::CalculateEdgeNormals
 466 ================
 467 */
 468 #define SHARP_EDGE_DOT  -0.7f
 469
 470 void idCollisionModelManagerLocal::CalculateEdgeNormals( cm_model_t *model, cm_node_t *node ) {
 471         cm_polygonRef_t *pref;
 472         cm_polygon_t *p;
 473         cm_edge_t *edge;
 474         float dot, s;
 475         int i, edgeNum;
 476         idVec3 dir;
 477
 478         while( 1 ) {
 479                 for ( pref = node->polygons; pref; pref = pref->next ) {
 480                         p = pref->p;
 481                         // if we checked this polygon already
 482                         if ( p->checkcount == checkCount ) {
 483                                 continue;
 484                         }
 485                         p->checkcount = checkCount;
 486
 487                         for ( i = 0; i < p->numEdges; i++ ) {
 488                                 edgeNum = p->edges[i];
 489                                 edge = model->edges + abs( edgeNum );
 490                                 if ( edge->normal[0] == 0.0f && edge->normal[1] == 0.0f && edge->normal[2] == 0.0f ) {
 491                                         // if the edge is only used by this polygon
 492                                         if ( edge->numUsers == 1 ) {
 493                                                 dir = model->vertices[ edge->vertexNum[edgeNum < 0]].p - model->vertices[ edge->vertexNum[edgeNum > 0]].p;
 494                                                 edge->normal = p->plane.Normal().Cross( dir );
 495                                                 edge->normal.Normalize();
 496                                         } else {
 497                                                 // the edge is used by more than one polygon
 498                                                 edge->normal = p->plane.Normal();
 499                                         }
 500                                 } else {
 501                                         dot = edge->normal * p->plane.Normal();
 502                                         // if the two planes make a very sharp edge
 503                                         if ( dot < SHARP_EDGE_DOT ) {
 504                                                 // max length normal pointing outside both polygons
 505                                                 dir = model->vertices[ edge->vertexNum[edgeNum > 0]].p - model->vertices[ edge->vertexNum[edgeNum < 0]].p;
 506                                                 edge->normal = edge->normal.Cross( dir ) + p->plane.Normal().Cross( -dir );
 507                                                 edge->normal *= ( 0.5f / ( 0.5f + 0.5f * SHARP_EDGE_DOT ) ) / edge->normal.Length();
 508                                                 model->numSharpEdges++;
 509                                         } else {
 510                                                 s = 0.5f / ( 0.5f + 0.5f * dot );
 511                                                 edge->normal = s * ( edge->normal + p->plane.Normal() );
 512                                         }
 513                                 }
 514                         }
 515                 }
 516                 // if leaf node
 517                 if ( node->planeType == -1 ) {
 518                         break;
 519                 }
 520                 CalculateEdgeNormals( model, node->children[1] );
 521                 node = node->children[0];
 522         }
 523 }
 524
 525 /*
 526 ===============================================================================
 527
 528 Trace model to general collision model
 529
 530 ===============================================================================
 531 */
 532
 533 /*
 534 ================
 535 idCollisionModelManagerLocal::AllocModel
 536 ================
 537 */
 538 cm_model_t *idCollisionModelManagerLocal::AllocModel( void ) {
 539         cm_model_t *model;
 540
 541         model = new cm_model_t;
 542         model->contents = 0;
 543         model->isConvex = false;
 544         model->maxVertices = 0;
 545         model->numVertices = 0;
 546         model->vertices = NULL;
 547         model->maxEdges = 0;
 548         model->numEdges = 0;
 549         model->edges= NULL;
 550         model->node = NULL;
 551         model->nodeBlocks = NULL;
 552         model->polygonRefBlocks = NULL;
 553         model->brushRefBlocks = NULL;
 554         model->polygonBlock = NULL;
 555         model->brushBlock = NULL;
 556         model->numPolygons = model->polygonMemory =
 557         model->numBrushes = model->brushMemory =
 558         model->numNodes = model->numBrushRefs =
 559         model->numPolygonRefs = model->numInternalEdges =
 560         model->numSharpEdges = model->numRemovedPolys =
 561         model->numMergedPolys = model->usedMemory = 0;
 562
 563         return model;
 564 }
 565
 566 /*
 567 ================
 568 idCollisionModelManagerLocal::AllocNode
 569 ================
 570 */
 571 cm_node_t *idCollisionModelManagerLocal::AllocNode( cm_model_t *model, int blockSize ) {
 572         int i;
 573         cm_node_t *node;
 574         cm_nodeBlock_t *nodeBlock;
 575
 576         if ( !model->nodeBlocks || !model->nodeBlocks->nextNode ) {
 577                 nodeBlock = (cm_nodeBlock_t *) Mem_ClearedAlloc( sizeof( cm_nodeBlock_t ) + blockSize * sizeof(cm_node_t) );
 578                 nodeBlock->nextNode = (cm_node_t *) ( ( (byte *) nodeBlock ) + sizeof( cm_nodeBlock_t ) );
 579                 nodeBlock->next = model->nodeBlocks;
 580                 model->nodeBlocks = nodeBlock;
 581                 node = nodeBlock->nextNode;
 582                 for ( i = 0; i < blockSize - 1; i++ ) {
 583                         node->parent = node + 1;
 584                         node = node->parent;
 585                 }
 586                 node->parent = NULL;
 587         }
 588
 589         node = model->nodeBlocks->nextNode;
 590         model->nodeBlocks->nextNode = node->parent;
 591         node->parent = NULL;
 592
 593         return node;
 594 }
 595
 596 /*
 597 ================
 598 idCollisionModelManagerLocal::AllocPolygonReference
 599 ================
 600 */
 601 cm_polygonRef_t *idCollisionModelManagerLocal::AllocPolygonReference( cm_model_t *model, int blockSize ) {
 602         int i;
 603         cm_polygonRef_t *pref;
 604         cm_polygonRefBlock_t *prefBlock;
 605
 606         if ( !model->polygonRefBlocks || !model->polygonRefBlocks->nextRef ) {
 607                 prefBlock = (cm_polygonRefBlock_t *) Mem_Alloc( sizeof( cm_polygonRefBlock_t ) + blockSize * sizeof(cm_polygonRef_t) );
 608                 prefBlock->nextRef = (cm_polygonRef_t *) ( ( (byte *) prefBlock ) + sizeof( cm_polygonRefBlock_t ) );
 609                 prefBlock->next = model->polygonRefBlocks;
 610                 model->polygonRefBlocks = prefBlock;
 611                 pref = prefBlock->nextRef;
 612                 for ( i = 0; i < blockSize - 1; i++ ) {
 613                         pref->next = pref + 1;
 614                         pref = pref->next;
 615                 }
 616                 pref->next = NULL;
 617         }
 618
 619         pref = model->polygonRefBlocks->nextRef;
 620         model->polygonRefBlocks->nextRef = pref->next;
 621
 622         return pref;
 623 }
 624
 625 /*
 626 ================
 627 idCollisionModelManagerLocal::AllocBrushReference
 628 ================
 629 */
 630 cm_brushRef_t *idCollisionModelManagerLocal::AllocBrushReference( cm_model_t *model, int blockSize ) {
 631         int i;
 632         cm_brushRef_t *bref;
 633         cm_brushRefBlock_t *brefBlock;
 634
 635         if ( !model->brushRefBlocks || !model->brushRefBlocks->nextRef ) {
 636                 brefBlock = (cm_brushRefBlock_t *) Mem_Alloc( sizeof(cm_brushRefBlock_t) + blockSize * sizeof(cm_brushRef_t) );
 637                 brefBlock->nextRef = (cm_brushRef_t *) ( ( (byte *) brefBlock ) + sizeof(cm_brushRefBlock_t) );
 638                 brefBlock->next = model->brushRefBlocks;
 639                 model->brushRefBlocks = brefBlock;
 640                 bref = brefBlock->nextRef;
 641                 for ( i = 0; i < blockSize - 1; i++ ) {
 642                         bref->next = bref + 1;
 643                         bref = bref->next;
 644                 }
 645                 bref->next = NULL;
 646         }
 647
 648         bref = model->brushRefBlocks->nextRef;
 649         model->brushRefBlocks->nextRef = bref->next;
 650
 651         return bref;
 652 }
 653
 654 /*
 655 ================
 656 idCollisionModelManagerLocal::AllocPolygon
 657 ================
 658 */
 659 cm_polygon_t *idCollisionModelManagerLocal::AllocPolygon( cm_model_t *model, int numEdges ) {
 660         cm_polygon_t *poly;
 661         int size;
 662
 663         size = sizeof( cm_polygon_t ) + ( numEdges - 1 ) * sizeof( poly->edges[0] );
 664         model->numPolygons++;
 665         model->polygonMemory += size;
 666         if ( model->polygonBlock && model->polygonBlock->bytesRemaining >= size ) {
 667                 poly = (cm_polygon_t *) model->polygonBlock->next;
 668                 model->polygonBlock->next += size;
 669                 model->polygonBlock->bytesRemaining -= size;
 670         } else {
 671                 poly = (cm_polygon_t *) Mem_Alloc( size );
 672         }
 673         return poly;
 674 }
 675
 676 /*
 677 ================
 678 idCollisionModelManagerLocal::AllocBrush
 679 ================
 680 */
 681 cm_brush_t *idCollisionModelManagerLocal::AllocBrush( cm_model_t *model, int numPlanes ) {
 682         cm_brush_t *brush;
 683         int size;
 684
 685         size = sizeof( cm_brush_t ) + ( numPlanes - 1 ) * sizeof( brush->planes[0] );
 686         model->numBrushes++;
 687         model->brushMemory += size;
 688         if ( model->brushBlock && model->brushBlock->bytesRemaining >= size ) {
 689                 brush = (cm_brush_t *) model->brushBlock->next;
 690                 model->brushBlock->next += size;
 691                 model->brushBlock->bytesRemaining -= size;
 692         } else {
 693                 brush = (cm_brush_t *) Mem_Alloc( size );
 694         }
 695         return brush;
 696 }
 697
 698 /*
 699 ================
 700 idCollisionModelManagerLocal::AddPolygonToNode
 701 ================
 702 */
 703 void idCollisionModelManagerLocal::AddPolygonToNode( cm_model_t *model, cm_node_t *node, cm_polygon_t *p ) {
 704         cm_polygonRef_t *pref;
 705
 706         pref = AllocPolygonReference( model, model->numPolygonRefs < REFERENCE_BLOCK_SIZE_SMALL ? REFERENCE_BLOCK_SIZE_SMALL : REFERENCE_BLOCK_SIZE_LARGE );
 707         pref->p = p;
 708         pref->next = node->polygons;
 709         node->polygons = pref;
 710         model->numPolygonRefs++;
 711 }
 712
 713 /*
 714 ================
 715 idCollisionModelManagerLocal::AddBrushToNode
 716 ================
 717 */
 718 void idCollisionModelManagerLocal::AddBrushToNode( cm_model_t *model, cm_node_t *node, cm_brush_t *b ) {
 719         cm_brushRef_t *bref;
 720
 721         bref = AllocBrushReference( model, model->numBrushRefs < REFERENCE_BLOCK_SIZE_SMALL ? REFERENCE_BLOCK_SIZE_SMALL : REFERENCE_BLOCK_SIZE_LARGE );
 722         bref->b = b;
 723         bref->next = node->brushes;
 724         node->brushes = bref;
 725         model->numBrushRefs++;
 726 }
 727
 728 /*
 729 ================
 730 idCollisionModelManagerLocal::SetupTrmModelStructure
 731 ================
 732 */
 733 void idCollisionModelManagerLocal::SetupTrmModelStructure( void ) {
 734         int i;
 735         cm_node_t *node;
 736         cm_model_t *model;
 737
 738         // setup model
 739         model = AllocModel();
 740
 741         assert( models );
 742         models[MAX_SUBMODELS] = model;
 743         // create node to hold the collision data
 744         node = (cm_node_t *) AllocNode( model, 1 );
 745         node->planeType = -1;
 746         model->node = node;
 747         // allocate vertex and edge arrays
 748         model->numVertices = 0;
 749         model->maxVertices = MAX_TRACEMODEL_VERTS;
 750         model->vertices = (cm_vertex_t *) Mem_ClearedAlloc( model->maxVertices * sizeof(cm_vertex_t) );
 751         model->numEdges = 0;
 752         model->maxEdges = MAX_TRACEMODEL_EDGES+1;
 753         model->edges = (cm_edge_t *) Mem_ClearedAlloc( model->maxEdges * sizeof(cm_edge_t) );
 754         // create a material for the trace model polygons
 755         trmMaterial = declManager->FindMaterial( "_tracemodel", false );
 756         if ( !trmMaterial ) {
 757                 common->FatalError( "_tracemodel material not found" );
 758         }
 759
 760         // allocate polygons
 761         for ( i = 0; i < MAX_TRACEMODEL_POLYS; i++ ) {
 762                 trmPolygons[i] = AllocPolygonReference( model, MAX_TRACEMODEL_POLYS );
 763                 trmPolygons[i]->p = AllocPolygon( model, MAX_TRACEMODEL_POLYEDGES );
 764                 trmPolygons[i]->p->bounds.Clear();
 765                 trmPolygons[i]->p->plane.Zero();
 766                 trmPolygons[i]->p->checkcount = 0;
 767                 trmPolygons[i]->p->contents = -1;               // all contents
 768                 trmPolygons[i]->p->material = trmMaterial;
 769                 trmPolygons[i]->p->numEdges = 0;
 770         }
 771         // allocate brush for position test
 772         trmBrushes[0] = AllocBrushReference( model, 1 );
 773         trmBrushes[0]->b = AllocBrush( model, MAX_TRACEMODEL_POLYS );
 774         trmBrushes[0]->b->primitiveNum = 0;
 775         trmBrushes[0]->b->bounds.Clear();
 776         trmBrushes[0]->b->checkcount = 0;
 777         trmBrushes[0]->b->contents = -1;                // all contents
 778         trmBrushes[0]->b->numPlanes = 0;
 779 }
 780
 781 /*
 782 ================
 783 idCollisionModelManagerLocal::SetupTrmModel
 784
 785 Trace models (item boxes, etc) are converted to collision models on the fly, using the last model slot
 786 as a reusable temporary buffer
 787 ================
 788 */
 789 cmHandle_t idCollisionModelManagerLocal::SetupTrmModel( const idTraceModel &trm, const idMaterial *material ) {
 790         int i, j;
 791         cm_vertex_t *vertex;
 792         cm_edge_t *edge;
 793         cm_polygon_t *poly;
 794         cm_model_t *model;
 795         const traceModelVert_t *trmVert;
 796         const traceModelEdge_t *trmEdge;
 797         const traceModelPoly_t *trmPoly;
 798
 799         assert( models );
 800
 801         if ( material == NULL ) {
 802                 material = trmMaterial;
 803         }
 804
 805         model = models[MAX_SUBMODELS];
 806         model->node->brushes = NULL;
 807         model->node->polygons = NULL;
 808         // if not a valid trace model
 809         if ( trm.type == TRM_INVALID || !trm.numPolys ) {
 810                 return TRACE_MODEL_HANDLE;
 811         }
 812         // vertices
 813         model->numVertices = trm.numVerts;
 814         vertex = model->vertices;
 815         trmVert = trm.verts;
 816         for ( i = 0; i < trm.numVerts; i++, vertex++, trmVert++ ) {
 817                 vertex->p = *trmVert;
 818                 vertex->sideSet = 0;
 819         }
 820         // edges
 821         model->numEdges = trm.numEdges;
 822         edge = model->edges + 1;
 823         trmEdge = trm.edges + 1;
 824         for ( i = 0; i < trm.numEdges; i++, edge++, trmEdge++ ) {
 825                 edge->vertexNum[0] = trmEdge->v[0];
 826                 edge->vertexNum[1] = trmEdge->v[1];
 827                 edge->normal = trmEdge->normal;
 828                 edge->internal = false;
 829                 edge->sideSet = 0;
 830         }
 831         // polygons
 832         model->numPolygons = trm.numPolys;
 833         trmPoly = trm.polys;
 834         for ( i = 0; i < trm.numPolys; i++, trmPoly++ ) {
 835                 poly = trmPolygons[i]->p;
 836                 poly->numEdges = trmPoly->numEdges;
 837                 for ( j = 0; j < trmPoly->numEdges; j++ ) {
 838                         poly->edges[j] = trmPoly->edges[j];
 839                 }
 840                 poly->plane.SetNormal( trmPoly->normal );
 841                 poly->plane.SetDist( trmPoly->dist );
 842                 poly->bounds = trmPoly->bounds;
 843                 poly->material = material;
 844                 // link polygon at node
 845                 trmPolygons[i]->next = model->node->polygons;
 846                 model->node->polygons = trmPolygons[i];
 847         }
 848         // if the trace model is convex
 849         if ( trm.isConvex ) {
 850                 // setup brush for position test
 851                 trmBrushes[0]->b->numPlanes = trm.numPolys;
 852                 for ( i = 0; i < trm.numPolys; i++ ) {
 853                         trmBrushes[0]->b->planes[i] = trmPolygons[i]->p->plane;
 854                 }
 855                 trmBrushes[0]->b->bounds = trm.bounds;
 856                 // link brush at node
 857                 trmBrushes[0]->next = model->node->brushes;
 858                 model->node->brushes = trmBrushes[0];
 859         }
 860         // model bounds
 861         model->bounds = trm.bounds;
 862         // convex
 863         model->isConvex = trm.isConvex;
 864
 865         return TRACE_MODEL_HANDLE;
 866 }
 867
 868 /*
 869 ===============================================================================
 870
 871 Optimisation, removal of polygons contained within brushes or solid
 872
 873 ===============================================================================
 874 */
 875
 876 /*
 877 ============
 878 idCollisionModelManagerLocal::R_ChoppedAwayByProcBSP
 879 ============
 880 */
 881 int idCollisionModelManagerLocal::R_ChoppedAwayByProcBSP( int nodeNum, idFixedWinding *w, const idVec3 &normal, const idVec3 &origin, const float radius ) {
 882         int res;
 883         idFixedWinding back;
 884         cm_procNode_t *node;
 885         float dist;
 886
 887         do {
 888                 node = procNodes + nodeNum;
 889                 dist = node->plane.Normal() * origin + node->plane[3];
 890                 if ( dist > radius ) {
 891                         res = SIDE_FRONT;
 892                 }
 893                 else if ( dist < -radius ) {
 894                         res = SIDE_BACK;
 895                 }
 896                 else {
 897                         res = w->Split( &back, node->plane, CHOP_EPSILON );
 898                 }
 899                 if ( res == SIDE_FRONT ) {
 900                         nodeNum = node->children[0];
 901                 }
 902                 else if ( res == SIDE_BACK ) {
 903                         nodeNum = node->children[1];
 904                 }
 905                 else if ( res == SIDE_ON ) {
 906                         // continue with the side the winding faces
 907                         if ( node->plane.Normal() * normal > 0.0f ) {
 908                                 nodeNum = node->children[0];
 909                         }
 910                         else {
 911                                 nodeNum = node->children[1];
 912                         }
 913                 }
 914                 else {
 915                         // if either node is not solid
 916                         if ( node->children[0] < 0 || node->children[1] < 0 ) {
 917                                 return false;
 918                         }
 919                         // only recurse if the node is not solid
 920                         if ( node->children[1] > 0 ) {
 921                                 if ( !R_ChoppedAwayByProcBSP( node->children[1], &back, normal, origin, radius ) ) {
 922                                         return false;
 923                                 }
 924                         }
 925                         nodeNum = node->children[0];
 926                 }
 927         } while ( nodeNum > 0 );
 928         if ( nodeNum < 0 ) {
 929                 return false;
 930         }
 931         return true;
 932 }
 933
 934 /*
 935 ============
 936 idCollisionModelManagerLocal::ChoppedAwayByProcBSP
 937 ============
 938 */
 939 int idCollisionModelManagerLocal::ChoppedAwayByProcBSP( const idFixedWinding &w, const idPlane &plane, int contents ) {
 940         idFixedWinding neww;
 941         idBounds bounds;
 942         float radius;
 943         idVec3 origin;
 944
 945         // if the .proc file has no BSP tree
 946         if ( procNodes == NULL ) {
 947                 return false;
 948         }
 949         // don't chop if the polygon is not solid
 950         if ( !(contents & CONTENTS_SOLID) ) {
 951                 return false;
 952         }
 953         // make a local copy of the winding
 954         neww = w;
 955         neww.GetBounds( bounds );
 956         origin = (bounds[1] - bounds[0]) * 0.5f;
 957         radius = origin.Length() + CHOP_EPSILON;
 958         origin = bounds[0] + origin;
 959         //
 960         return R_ChoppedAwayByProcBSP( 0, &neww, plane.Normal(), origin, radius );
 961 }
 962
 963 /*
 964 =============
 965 idCollisionModelManagerLocal::ChopWindingWithBrush
 966
 967   returns the least number of winding fragments outside the brush
 968 =============
 969 */
 970 void idCollisionModelManagerLocal::ChopWindingListWithBrush( cm_windingList_t *list, cm_brush_t *b ) {
 971         int i, k, res, startPlane, planeNum, bestNumWindings;
 972         idFixedWinding back, front;
 973         idPlane plane;
 974         bool chopped;
 975         int sidedness[MAX_POINTS_ON_WINDING];
 976         float dist;
 977
 978         if ( b->numPlanes > MAX_POINTS_ON_WINDING ) {
 979                 return;
 980         }
 981
 982         // get sidedness for the list of windings
 983         for ( i = 0; i < b->numPlanes; i++ ) {
 984                 plane = -b->planes[i];
 985
 986                 dist = plane.Distance( list->origin );
 987                 if ( dist > list->radius ) {
 988                         sidedness[i] = SIDE_FRONT;
 989                 }
 990                 else if ( dist < -list->radius ) {
 991                         sidedness[i] = SIDE_BACK;
 992                 }
 993                 else {
 994                         sidedness[i] = list->bounds.PlaneSide( plane );
 995                         if ( sidedness[i] == PLANESIDE_FRONT ) {
 996                                 sidedness[i] = SIDE_FRONT;
 997                         }
 998                         else if ( sidedness[i] == PLANESIDE_BACK ) {
 999                                 sidedness[i] = SIDE_BACK;
1000                         }
1001                         else {
1002                                 sidedness[i] = SIDE_CROSS;
1003                         }
1004                 }
1005         }
1006
1007         cm_outList->numWindings = 0;
1008         for ( k = 0; k < list->numWindings; k++ ) {
1009                 //
1010                 startPlane = 0;
1011                 bestNumWindings = 1 + b->numPlanes;
1012                 chopped = false;
1013                 do {
1014                         front = list->w[k];
1015                         cm_tmpList->numWindings = 0;
1016                         for ( planeNum = startPlane, i = 0; i < b->numPlanes; i++, planeNum++ ) {
1017
1018                                 if ( planeNum >= b->numPlanes ) {
1019                                         planeNum = 0;
1020                                 }
1021
1022                                 res = sidedness[planeNum];
1023
1024                                 if ( res == SIDE_CROSS ) {
1025                                         plane = -b->planes[planeNum];
1026                                         res = front.Split( &back, plane, CHOP_EPSILON );
1027                                 }
1028
1029                                 // NOTE:        disabling this can create gaps at places where Z-fighting occurs
1030                                 //                      Z-fighting should not occur but what if there is a decal brush side
1031                                 //                      with exactly the same size as another brush side ?
1032                                 // only leave windings on a brush if the winding plane and brush side plane face the same direction
1033                                 if ( res == SIDE_ON && list->primitiveNum >= 0 && (list->normal * b->planes[planeNum].Normal()) > 0 ) {
1034                                         // return because all windings in the list will be on this brush side plane
1035                                         return;
1036                                 }
1037
1038                                 if ( res == SIDE_BACK ) {
1039                                         if ( cm_outList->numWindings >= MAX_WINDING_LIST ) {
1040                                                 common->Warning( "idCollisionModelManagerLocal::ChopWindingWithBrush: primitive %d more than %d windings", list->primitiveNum, MAX_WINDING_LIST );
1041                                                 return;
1042                                         }
1043                                         // winding and brush didn't intersect, store the original winding
1044                                         cm_outList->w[cm_outList->numWindings] = list->w[k];
1045                                         cm_outList->numWindings++;
1046                                         chopped = false;
1047                                         break;
1048                                 }
1049
1050                                 if ( res == SIDE_CROSS ) {
1051                                         if ( cm_tmpList->numWindings >= MAX_WINDING_LIST ) {
1052                                                 common->Warning( "idCollisionModelManagerLocal::ChopWindingWithBrush: primitive %d more than %d windings", list->primitiveNum, MAX_WINDING_LIST );
1053                                                 return;
1054                                         }
1055                                         // store the front winding in the temporary list
1056                                         cm_tmpList->w[cm_tmpList->numWindings] = back;
1057                                         cm_tmpList->numWindings++;
1058                                         chopped = true;
1059                                 }
1060
1061                                 // if already found a start plane which generates less fragments
1062                                 if ( cm_tmpList->numWindings >= bestNumWindings ) {
1063                                         break;
1064                                 }
1065                         }
1066
1067                         // find the best start plane to get the least number of fragments outside the brush
1068                         if ( cm_tmpList->numWindings < bestNumWindings ) {
1069                                 bestNumWindings = cm_tmpList->numWindings;
1070                                 // store windings from temporary list in the out list
1071                                 for ( i = 0; i < cm_tmpList->numWindings; i++ ) {
1072                                         if ( cm_outList->numWindings + i >= MAX_WINDING_LIST ) {
1073                                                 common->Warning( "idCollisionModelManagerLocal::ChopWindingWithBrush: primitive %d more than %d windings", list->primitiveNum, MAX_WINDING_LIST );
1074                                                 return;
1075                                         }
1076                                         cm_outList->w[cm_outList->numWindings+i] = cm_tmpList->w[i];
1077                                 }
1078                                 // if only one winding left then we can't do any better
1079                                 if ( bestNumWindings == 1 ) {
1080                                         break;
1081                                 }
1082                         }
1083
1084                         // try the next start plane
1085                         startPlane++;
1086
1087                 } while ( chopped && startPlane < b->numPlanes );
1088                 //
1089                 if ( chopped ) {
1090                         cm_outList->numWindings += bestNumWindings;
1091                 }
1092         }
1093         for ( k = 0; k < cm_outList->numWindings; k++ ) {
1094                 list->w[k] = cm_outList->w[k];
1095         }
1096         list->numWindings = cm_outList->numWindings;
1097 }
1098
1099 /*
1100 ============
1101 idCollisionModelManagerLocal::R_ChopWindingListWithTreeBrushes
1102 ============
1103 */
1104 void idCollisionModelManagerLocal::R_ChopWindingListWithTreeBrushes( cm_windingList_t *list, cm_node_t *node ) {
1105         int i;
1106         cm_brushRef_t *bref;
1107         cm_brush_t *b;
1108
1109         while( 1 ) {
1110                 for ( bref = node->brushes; bref; bref = bref->next ) {
1111                         b = bref->b;
1112                         // if we checked this brush already
1113                         if ( b->checkcount == checkCount ) {
1114                                 continue;
1115                         }
1116                         b->checkcount = checkCount;
1117                         // if the windings in the list originate from this brush
1118                         if ( b->primitiveNum == list->primitiveNum ) {
1119                                 continue;
1120                         }
1121                         // if brush has a different contents
1122                         if ( b->contents != list->contents ) {
1123                                 continue;
1124                         }
1125                         // brush bounds and winding list bounds should overlap
1126                         for ( i = 0; i < 3; i++ ) {
1127                                 if ( list->bounds[0][i] > b->bounds[1][i] ) {
1128                                         break;
1129                                 }
1130                                 if ( list->bounds[1][i] < b->bounds[0][i] ) {
1131                                         break;
1132                                 }
1133                         }
1134                         if ( i < 3 ) {
1135                                 continue;
1136                         }
1137                         // chop windings in the list with brush
1138                         ChopWindingListWithBrush( list, b );
1139                         // if all windings are chopped away we're done
1140                         if ( !list->numWindings ) {
1141                                 return;
1142                         }
1143                 }
1144                 // if leaf node
1145                 if ( node->planeType == -1 ) {
1146                         break;
1147                 }
1148                 if ( list->bounds[0][node->planeType] > node->planeDist ) {
1149                         node = node->children[0];
1150                 }
1151                 else if ( list->bounds[1][node->planeType] < node->planeDist ) {
1152                         node = node->children[1];
1153                 }
1154                 else {
1155                         R_ChopWindingListWithTreeBrushes( list, node->children[1] );
1156                         if ( !list->numWindings ) {
1157                                 return;
1158                         }
1159                         node = node->children[0];
1160                 }
1161         }
1162 }
1163
1164 /*
1165 ============
1166 idCollisionModelManagerLocal::WindingOutsideBrushes
1167
1168   Returns one winding which is not fully contained in brushes.
1169   We always favor less polygons over a stitched world.
1170   If the winding is partly contained and the contained pieces can be chopped off
1171   without creating multiple winding fragments then the chopped winding is returned.
1172 ============
1173 */
1174 idFixedWinding *idCollisionModelManagerLocal::WindingOutsideBrushes( idFixedWinding *w, const idPlane &plane, int contents, int primitiveNum, cm_node_t *headNode ) {
1175         int i, windingLeft;
1176
1177         cm_windingList->bounds.Clear();
1178         for ( i = 0; i < w->GetNumPoints(); i++ ) {
1179                 cm_windingList->bounds.AddPoint( (*w)[i].ToVec3() );
1180         }
1181
1182         cm_windingList->origin = (cm_windingList->bounds[1] - cm_windingList->bounds[0]) * 0.5;
1183         cm_windingList->radius = cm_windingList->origin.Length() + CHOP_EPSILON;
1184         cm_windingList->origin = cm_windingList->bounds[0] + cm_windingList->origin;
1185         cm_windingList->bounds[0] -= idVec3( CHOP_EPSILON, CHOP_EPSILON, CHOP_EPSILON );
1186         cm_windingList->bounds[1] += idVec3( CHOP_EPSILON, CHOP_EPSILON, CHOP_EPSILON );
1187
1188         cm_windingList->w[0] = *w;
1189         cm_windingList->numWindings = 1;
1190         cm_windingList->normal = plane.Normal();
1191         cm_windingList->contents = contents;
1192         cm_windingList->primitiveNum = primitiveNum;
1193         //
1194         checkCount++;
1195         R_ChopWindingListWithTreeBrushes( cm_windingList, headNode );
1196         //
1197         if ( !cm_windingList->numWindings ) {
1198                 return NULL;
1199         }
1200         if ( cm_windingList->numWindings == 1 ) {
1201                 return &cm_windingList->w[0];
1202         }
1203         // if not the world model
1204         if ( numModels != 0 ) {
1205                 return w;
1206         }
1207         // check if winding fragments would be chopped away by the proc BSP tree
1208         windingLeft = -1;
1209         for ( i = 0; i < cm_windingList->numWindings; i++ ) {
1210                 if ( !ChoppedAwayByProcBSP( cm_windingList->w[i], plane, contents ) ) {
1211                         if ( windingLeft >= 0 ) {
1212                                 return w;
1213                         }
1214                         windingLeft = i;
1215                 }
1216         }
1217         if ( windingLeft >= 0 ) {
1218                 return &cm_windingList->w[windingLeft];
1219         }
1220         return NULL;
1221 }
1222
1223 /*
1224 ===============================================================================
1225
1226 Merging polygons
1227
1228 ===============================================================================
1229 */
1230
1231 /*
1232 =============
1233 idCollisionModelManagerLocal::ReplacePolygons
1234
1235   does not allow for a node to have multiple references to the same polygon
1236 =============
1237 */
1238 void idCollisionModelManagerLocal::ReplacePolygons( cm_model_t *model, cm_node_t *node, cm_polygon_t *p1, cm_polygon_t *p2, cm_polygon_t *newp ) {
1239         cm_polygonRef_t *pref, *lastpref, *nextpref;
1240         cm_polygon_t *p;
1241         bool linked;
1242
1243         while( 1 ) {
1244                 linked = false;
1245                 lastpref = NULL;
1246                 for ( pref = node->polygons; pref; pref = nextpref ) {
1247                         nextpref = pref->next;
1248                         //
1249                         p = pref->p;
1250                         // if this polygon reference should change
1251                         if ( p == p1 || p == p2 ) {
1252                                 // if the new polygon is already linked at this node
1253                                 if ( linked ) {
1254                                         if ( lastpref ) {
1255                                                 lastpref->next = nextpref;
1256                                         }
1257                                         else {
1258                                                 node->polygons = nextpref;
1259                                         }
1260                                         FreePolygonReference( pref );
1261                                         model->numPolygonRefs--;
1262                                 }
1263                                 else {
1264                                         pref->p = newp;
1265                                         linked = true;
1266                                         lastpref = pref;
1267                                 }
1268                         }
1269                         else {
1270                                 lastpref = pref;
1271                         }
1272                 }
1273                 // if leaf node
1274                 if ( node->planeType == -1 ) {
1275                         break;
1276                 }
1277                 if ( p1->bounds[0][node->planeType] > node->planeDist && p2->bounds[0][node->planeType] > node->planeDist ) {
1278                         node = node->children[0];
1279                 }
1280                 else if ( p1->bounds[1][node->planeType] < node->planeDist && p2->bounds[1][node->planeType] < node->planeDist ) {
1281                         node = node->children[1];
1282                 }
1283                 else {
1284                         ReplacePolygons( model, node->children[1], p1, p2, newp );
1285                         node = node->children[0];
1286                 }
1287         }
1288 }
1289
1290 /*
1291 =============
1292 idCollisionModelManagerLocal::TryMergePolygons
1293 =============
1294 */
1295 #define CONTINUOUS_EPSILON      0.005f
1296 #define NORMAL_EPSILON          0.01f
1297
1298 cm_polygon_t *idCollisionModelManagerLocal::TryMergePolygons( cm_model_t *model, cm_polygon_t *p1, cm_polygon_t *p2 ) {
1299         int i, j, nexti, prevj;
1300         int p1BeforeShare, p1AfterShare, p2BeforeShare, p2AfterShare;
1301         int newEdges[CM_MAX_POLYGON_EDGES], newNumEdges;
1302         int edgeNum, edgeNum1, edgeNum2, newEdgeNum1, newEdgeNum2;
1303         cm_edge_t *edge;
1304         cm_polygon_t *newp;
1305         idVec3 delta, normal;
1306         float dot;
1307         bool keep1, keep2;
1308
1309         if ( p1->material != p2->material ) {
1310                 return NULL;
1311         }
1312         if ( idMath::Fabs( p1->plane.Dist() - p2->plane.Dist() ) > NORMAL_EPSILON ) {
1313                 return NULL;
1314         }
1315         for ( i = 0; i < 3; i++ ) {
1316                 if ( idMath::Fabs( p1->plane.Normal()[i] - p2->plane.Normal()[i] ) > NORMAL_EPSILON ) {
1317                         return NULL;
1318                 }
1319                 if ( p1->bounds[0][i] > p2->bounds[1][i] ) {
1320                         return NULL;
1321                 }
1322                 if ( p1->bounds[1][i] < p2->bounds[0][i] ) {
1323                         return NULL;
1324                 }
1325         }
1326         // this allows for merging polygons with multiple shared edges
1327         // polygons with multiple shared edges probably never occur tho ;)
1328         p1BeforeShare = p1AfterShare = p2BeforeShare = p2AfterShare = -1;
1329         for ( i = 0; i < p1->numEdges; i++ ) {
1330                 nexti = (i+1)%p1->numEdges;
1331                 for ( j = 0; j < p2->numEdges; j++ ) {
1332                         prevj = (j+p2->numEdges-1)%p2->numEdges;
1333                         //
1334                         if ( abs(p1->edges[i]) != abs(p2->edges[j]) ) {
1335                                 // if the next edge of p1 and the previous edge of p2 are the same
1336                                 if ( abs(p1->edges[nexti]) == abs(p2->edges[prevj]) ) {
1337                                         // if both polygons don't use the edge in the same direction
1338                                         if ( p1->edges[nexti] != p2->edges[prevj] ) {
1339                                                 p1BeforeShare = i;
1340                                                 p2AfterShare = j;
1341                                         }
1342                                         break;
1343                                 }
1344                         }
1345                         // if both polygons don't use the edge in the same direction
1346                         else if ( p1->edges[i] != p2->edges[j] ) {
1347                                 // if the next edge of p1 and the previous edge of p2 are not the same
1348                                 if ( abs(p1->edges[nexti]) != abs(p2->edges[prevj]) ) {
1349                                         p1AfterShare = nexti;
1350                                         p2BeforeShare = prevj;
1351                                         break;
1352                                 }
1353                         }
1354                 }
1355         }
1356         if ( p1BeforeShare < 0 || p1AfterShare < 0 || p2BeforeShare < 0 || p2AfterShare < 0 ) {
1357                 return NULL;
1358         }
1359
1360         // check if the new polygon would still be convex
1361         edgeNum = p1->edges[p1BeforeShare];
1362         edge = model->edges + abs(edgeNum);
1363         delta = model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p -
1364                                         model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1365         normal = p1->plane.Normal().Cross( delta );
1366         normal.Normalize();
1367
1368         edgeNum = p2->edges[p2AfterShare];
1369         edge = model->edges + abs(edgeNum);
1370         delta = model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p -
1371                                         model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1372
1373         dot = delta * normal;
1374         if (dot < -CONTINUOUS_EPSILON)
1375                 return NULL;                    // not a convex polygon
1376         keep1 = (bool)(dot > CONTINUOUS_EPSILON);
1377
1378         edgeNum = p2->edges[p2BeforeShare];
1379         edge = model->edges + abs(edgeNum);
1380         delta = model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p -
1381                                         model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1382         normal = p1->plane.Normal().Cross( delta );
1383         normal.Normalize();
1384
1385         edgeNum = p1->edges[p1AfterShare];
1386         edge = model->edges + abs(edgeNum);
1387         delta = model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p -
1388                                         model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1389
1390         dot = delta * normal;
1391         if (dot < -CONTINUOUS_EPSILON)
1392                 return NULL;                    // not a convex polygon
1393         keep2 = (bool)(dot > CONTINUOUS_EPSILON);
1394
1395         newEdgeNum1 = newEdgeNum2 = 0;
1396         // get new edges if we need to replace colinear ones
1397         if ( !keep1 ) {
1398                 edgeNum1 = p1->edges[p1BeforeShare];
1399                 edgeNum2 = p2->edges[p2AfterShare];
1400                 GetEdge( model, model->vertices[model->edges[abs(edgeNum1)].vertexNum[INTSIGNBITSET(edgeNum1)]].p,
1401                                         model->vertices[model->edges[abs(edgeNum2)].vertexNum[INTSIGNBITNOTSET(edgeNum2)]].p,
1402                                                 &newEdgeNum1, -1 );
1403                 if ( newEdgeNum1 == 0 ) {
1404                         keep1 = true;
1405                 }
1406         }
1407         if ( !keep2 ) {
1408                 edgeNum1 = p2->edges[p2BeforeShare];
1409                 edgeNum2 = p1->edges[p1AfterShare];
1410                 GetEdge( model, model->vertices[model->edges[abs(edgeNum1)].vertexNum[INTSIGNBITSET(edgeNum1)]].p,
1411                                         model->vertices[model->edges[abs(edgeNum2)].vertexNum[INTSIGNBITNOTSET(edgeNum2)]].p,
1412                                                 &newEdgeNum2, -1 );
1413                 if ( newEdgeNum2 == 0 ) {
1414                         keep2 = true;
1415                 }
1416         }
1417         // set edges for new polygon
1418         newNumEdges = 0;
1419         if ( !keep2 ) {
1420                 newEdges[newNumEdges++] = newEdgeNum2;
1421         }
1422         if ( p1AfterShare < p1BeforeShare ) {
1423                 for ( i = p1AfterShare + (!keep2); i <= p1BeforeShare - (!keep1); i++ ) {
1424                         newEdges[newNumEdges++] = p1->edges[i];
1425                 }
1426         }
1427         else {
1428                 for ( i = p1AfterShare + (!keep2); i < p1->numEdges; i++ ) {
1429                         newEdges[newNumEdges++] = p1->edges[i];
1430                 }
1431                 for ( i = 0; i <= p1BeforeShare - (!keep1); i++ ) {
1432                         newEdges[newNumEdges++] = p1->edges[i];
1433                 }
1434         }
1435         if ( !keep1 ) {
1436                 newEdges[newNumEdges++] = newEdgeNum1;
1437         }
1438         if ( p2AfterShare < p2BeforeShare ) {
1439                 for ( i = p2AfterShare + (!keep1); i <= p2BeforeShare - (!keep2); i++ ) {
1440                         newEdges[newNumEdges++] = p2->edges[i];
1441                 }
1442         }
1443         else {
1444                 for ( i = p2AfterShare + (!keep1); i < p2->numEdges; i++ ) {
1445                         newEdges[newNumEdges++] = p2->edges[i];
1446                 }
1447                 for ( i = 0; i <= p2BeforeShare - (!keep2); i++ ) {
1448                         newEdges[newNumEdges++] = p2->edges[i];
1449                 }
1450         }
1451
1452         newp = AllocPolygon( model, newNumEdges );
1453         memcpy( newp, p1, sizeof(cm_polygon_t) );
1454         memcpy( newp->edges, newEdges, newNumEdges * sizeof(int) );
1455         newp->numEdges = newNumEdges;
1456         newp->checkcount = 0;
1457         // increase usage count for the edges of this polygon
1458         for ( i = 0; i < newp->numEdges; i++ ) {
1459                 if ( !keep1 && newp->edges[i] == newEdgeNum1 ) {
1460                         continue;
1461                 }
1462                 if ( !keep2 && newp->edges[i] == newEdgeNum2 ) {
1463                         continue;
1464                 }
1465                 model->edges[abs(newp->edges[i])].numUsers++;
1466         }
1467         // create new bounds from the merged polygons
1468         newp->bounds = p1->bounds + p2->bounds;
1469
1470         return newp;
1471 }
1472
1473 /*
1474 =============
1475 idCollisionModelManagerLocal::MergePolygonWithTreePolygons
1476 =============
1477 */
1478 bool idCollisionModelManagerLocal::MergePolygonWithTreePolygons( cm_model_t *model, cm_node_t *node, cm_polygon_t *polygon ) {
1479         int i;
1480         cm_polygonRef_t *pref;
1481         cm_polygon_t *p, *newp;
1482
1483         while( 1 ) {
1484                 for ( pref = node->polygons; pref; pref = pref->next ) {
1485                         p = pref->p;
1486                         //
1487                         if ( p == polygon ) {
1488                                 continue;
1489                         }
1490                         //
1491                         newp = TryMergePolygons( model, polygon, p );
1492                         // if polygons were merged
1493                         if ( newp ) {
1494                                 model->numMergedPolys++;
1495                                 // replace links to the merged polygons with links to the new polygon
1496                                 ReplacePolygons( model, model->node, polygon, p, newp );
1497                                 // decrease usage count for edges of both merged polygons
1498                                 for ( i = 0; i < polygon->numEdges; i++ ) {
1499                                         model->edges[abs(polygon->edges[i])].numUsers--;
1500                                 }
1501                                 for ( i = 0; i < p->numEdges; i++ ) {
1502                                         model->edges[abs(p->edges[i])].numUsers--;
1503                                 }
1504                                 // free merged polygons
1505                                 FreePolygon( model, polygon );
1506                                 FreePolygon( model, p );
1507
1508                                 return true;
1509                         }
1510                 }
1511                 // if leaf node
1512                 if ( node->planeType == -1 ) {
1513                         break;
1514                 }
1515                 if ( polygon->bounds[0][node->planeType] > node->planeDist ) {
1516                         node = node->children[0];
1517                 }
1518                 else if ( polygon->bounds[1][node->planeType] < node->planeDist ) {
1519                         node = node->children[1];
1520                 }
1521                 else {
1522                         if ( MergePolygonWithTreePolygons( model, node->children[1], polygon ) ) {
1523                                 return true;
1524                         }
1525                         node = node->children[0];
1526                 }
1527         }
1528         return false;
1529 }
1530
1531 /*
1532 =============
1533 idCollisionModelManagerLocal::MergeTreePolygons
1534
1535   try to merge any two polygons with the same surface flags and the same contents
1536 =============
1537 */
1538 void idCollisionModelManagerLocal::MergeTreePolygons( cm_model_t *model, cm_node_t *node ) {
1539         cm_polygonRef_t *pref;
1540         cm_polygon_t *p;
1541         bool merge;
1542
1543         while( 1 ) {
1544                 do {
1545                         merge = false;
1546                         for ( pref = node->polygons; pref; pref = pref->next ) {
1547                                 p = pref->p;
1548                                 // if we checked this polygon already
1549                                 if ( p->checkcount == checkCount ) {
1550                                         continue;
1551                                 }
1552                                 p->checkcount = checkCount;
1553                                 // try to merge this polygon with other polygons in the tree
1554                                 if ( MergePolygonWithTreePolygons( model, model->node, p ) ) {
1555                                         merge = true;
1556                                         break;
1557                                 }
1558                         }
1559                 } while (merge);
1560                 // if leaf node
1561                 if ( node->planeType == -1 ) {
1562                         break;
1563                 }
1564                 MergeTreePolygons( model, node->children[1] );
1565                 node = node->children[0];
1566         }
1567 }
1568
1569 /*
1570 ===============================================================================
1571
1572 Find internal edges
1573
1574 ===============================================================================
1575 */
1576
1577 /*
1578
1579         if (two polygons have the same contents)
1580                 if (the normals of the two polygon planes face towards each other)
1581                         if (an edge is shared between the polygons)
1582                                 if (the edge is not shared in the same direction)
1583                                         then this is an internal edge
1584                         else
1585                                 if (this edge is on the plane of the other polygon)
1586                                         if (this edge if fully inside the winding of the other polygon)
1587                                                 then this edge is an internal edge
1588
1589 */
1590
1591 /*
1592 =============
1593 idCollisionModelManagerLocal::PointInsidePolygon
1594 =============
1595 */
1596 bool idCollisionModelManagerLocal::PointInsidePolygon( cm_model_t *model, cm_polygon_t *p, idVec3 &v ) {
1597         int i, edgeNum;
1598         idVec3 *v1, *v2, dir1, dir2, vec;
1599         cm_edge_t *edge;
1600
1601         for ( i = 0; i < p->numEdges; i++ ) {
1602                 edgeNum = p->edges[i];
1603                 edge = model->edges + abs(edgeNum);
1604                 //
1605                 v1 = &model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1606                 v2 = &model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p;
1607                 dir1 = (*v2) - (*v1);
1608                 vec = v - (*v1);
1609                 dir2 = dir1.Cross( p->plane.Normal() );
1610                 if ( vec * dir2 > VERTEX_EPSILON ) {
1611                         return false;
1612                 }
1613         }
1614         return true;
1615 }
1616
1617 /*
1618 =============
1619 idCollisionModelManagerLocal::FindInternalEdgesOnPolygon
1620 =============
1621 */
1622 void idCollisionModelManagerLocal::FindInternalEdgesOnPolygon( cm_model_t *model, cm_polygon_t *p1, cm_polygon_t *p2 ) {
1623         int i, j, k, edgeNum;
1624         cm_edge_t *edge;
1625         idVec3 *v1, *v2, dir1, dir2;
1626         float d;
1627
1628         // bounds of polygons should overlap or touch
1629         for ( i = 0; i < 3; i++ ) {
1630                 if ( p1->bounds[0][i] > p2->bounds[1][i] ) {
1631                         return;
1632                 }
1633                 if ( p1->bounds[1][i] < p2->bounds[0][i] ) {
1634                         return;
1635                 }
1636         }
1637         //
1638         // FIXME: doubled geometry causes problems
1639         //
1640         for ( i = 0; i < p1->numEdges; i++ ) {
1641                 edgeNum = p1->edges[i];
1642                 edge = model->edges + abs(edgeNum);
1643                 // if already an internal edge
1644                 if ( edge->internal ) {
1645                         continue;
1646                 }
1647                 //
1648                 v1 = &model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1649                 v2 = &model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p;
1650                 // if either of the two vertices is outside the bounds of the other polygon
1651                 for ( k = 0; k < 3; k++ ) {
1652                         d = p2->bounds[1][k] + VERTEX_EPSILON;
1653                         if ( (*v1)[k] > d || (*v2)[k] > d ) {
1654                                 break;
1655                         }
1656                         d = p2->bounds[0][k] - VERTEX_EPSILON;
1657                         if ( (*v1)[k] < d || (*v2)[k] < d ) {
1658                                 break;
1659                         }
1660                 }
1661                 if ( k < 3 ) {
1662                         continue;
1663                 }
1664                 //
1665                 k = abs(edgeNum);
1666                 for ( j = 0; j < p2->numEdges; j++ ) {
1667                         if ( k == abs(p2->edges[j]) ) {
1668                                 break;
1669                         }
1670                 }
1671                 // if the edge is shared between the two polygons
1672                 if ( j < p2->numEdges ) {
1673                         // if the edge is used by more than 2 polygons
1674                         if ( edge->numUsers > 2 ) {
1675                                 // could still be internal but we'd have to test all polygons using the edge
1676                                 continue;
1677                         }
1678                         // if the edge goes in the same direction for both polygons
1679                         if ( edgeNum == p2->edges[j] ) {
1680                                 // the polygons can lay ontop of each other or one can obscure the other
1681                                 continue;
1682                         }
1683                 }
1684                 // the edge was not shared
1685                 else {
1686                         // both vertices should be on the plane of the other polygon
1687                         d = p2->plane.Distance( *v1 );
1688                         if ( idMath::Fabs(d) > VERTEX_EPSILON ) {
1689                                 continue;
1690                         }
1691                         d = p2->plane.Distance( *v2 );
1692                         if ( idMath::Fabs(d) > VERTEX_EPSILON ) {
1693                                 continue;
1694                         }
1695                 }
1696                 // the two polygon plane normals should face towards each other
1697                 dir1 = (*v2) - (*v1);
1698                 dir2 = p1->plane.Normal().Cross( dir1 );
1699                 if ( p2->plane.Normal() * dir2 < 0 ) {
1700                         //continue;
1701                         break;
1702                 }
1703                 // if the edge was not shared
1704                 if ( j >= p2->numEdges ) {
1705                         // both vertices of the edge should be inside the winding of the other polygon
1706                         if ( !PointInsidePolygon( model, p2, *v1 ) ) {
1707                                 continue;
1708                         }
1709                         if ( !PointInsidePolygon( model, p2, *v2 ) ) {
1710                                 continue;
1711                         }
1712                 }
1713                 // we got another internal edge
1714                 edge->internal = true;
1715                 model->numInternalEdges++;
1716         }
1717 }
1718
1719 /*
1720 =============
1721 idCollisionModelManagerLocal::FindInternalPolygonEdges
1722 =============
1723 */
1724 void idCollisionModelManagerLocal::FindInternalPolygonEdges( cm_model_t *model, cm_node_t *node, cm_polygon_t *polygon ) {
1725         cm_polygonRef_t *pref;
1726         cm_polygon_t *p;
1727
1728         if ( polygon->material->GetCullType() == CT_TWO_SIDED || polygon->material->ShouldCreateBackSides() ) {
1729                 return;
1730         }
1731
1732         while( 1 ) {
1733                 for ( pref = node->polygons; pref; pref = pref->next ) {
1734                         p = pref->p;
1735                         //
1736                         // FIXME: use some sort of additional checkcount because currently
1737                         //                      polygons can be checked multiple times
1738                         //
1739                         // if the polygons don't have the same contents
1740                         if ( p->contents != polygon->contents ) {
1741                                 continue;
1742                         }
1743                         if ( p == polygon ) {
1744                                 continue;
1745                         }
1746                         FindInternalEdgesOnPolygon( model, polygon, p );
1747                 }
1748                 // if leaf node
1749                 if ( node->planeType == -1 ) {
1750                         break;
1751                 }
1752                 if ( polygon->bounds[0][node->planeType] > node->planeDist ) {
1753                         node = node->children[0];
1754                 }
1755                 else if ( polygon->bounds[1][node->planeType] < node->planeDist ) {
1756                         node = node->children[1];
1757                 }
1758                 else {
1759                         FindInternalPolygonEdges( model, node->children[1], polygon );
1760                         node = node->children[0];
1761                 }
1762         }
1763 }
1764
1765 /*
1766 =============
1767 idCollisionModelManagerLocal::FindContainedEdges
1768 =============
1769 */
1770 void idCollisionModelManagerLocal::FindContainedEdges( cm_model_t *model, cm_polygon_t *p ) {
1771         int i, edgeNum;
1772         cm_edge_t *edge;
1773         idFixedWinding w;
1774
1775         for ( i = 0; i < p->numEdges; i++ ) {
1776                 edgeNum = p->edges[i];
1777                 edge = model->edges + abs(edgeNum);
1778                 if ( edge->internal ) {
1779                         continue;
1780                 }
1781                 w.Clear();
1782                 w += model->vertices[edge->vertexNum[INTSIGNBITSET(edgeNum)]].p;
1783                 w += model->vertices[edge->vertexNum[INTSIGNBITNOTSET(edgeNum)]].p;
1784                 if ( ChoppedAwayByProcBSP( w, p->plane, p->contents ) ) {
1785                         edge->internal = true;
1786                 }
1787         }
1788 }
1789
1790 /*
1791 =============
1792 idCollisionModelManagerLocal::FindInternalEdges
1793 =============
1794 */
1795 void idCollisionModelManagerLocal::FindInternalEdges( cm_model_t *model, cm_node_t *node ) {
1796         cm_polygonRef_t *pref;
1797         cm_polygon_t *p;
1798
1799         while( 1 ) {
1800                 for ( pref = node->polygons; pref; pref = pref->next ) {
1801                         p = pref->p;
1802                         // if we checked this polygon already
1803                         if ( p->checkcount == checkCount ) {
1804                                 continue;
1805                         }
1806                         p->checkcount = checkCount;
1807
1808                         FindInternalPolygonEdges( model, model->node, p );
1809
1810                         //FindContainedEdges( model, p );
1811                 }
1812                 // if leaf node
1813                 if ( node->planeType == -1 ) {
1814                         break;
1815                 }
1816                 FindInternalEdges( model, node->children[1] );
1817                 node = node->children[0];
1818         }
1819 }
1820
1821 /*
1822 ===============================================================================
1823
1824 Spatial subdivision
1825
1826 ===============================================================================
1827 */
1828
1829 /*
1830 ================
1831 CM_FindSplitter
1832 ================
1833 */
1834 static int CM_FindSplitter( const cm_node_t *node, const idBounds &bounds, int *planeType, float *planeDist ) {
1835         int i, j, type, axis[3], polyCount;
1836         float dist, t, bestt, size[3];
1837         cm_brushRef_t *bref;
1838         cm_polygonRef_t *pref;
1839         const cm_node_t *n;
1840         bool forceSplit = false;
1841
1842         for ( i = 0; i < 3; i++ ) {
1843                 size[i] = bounds[1][i] - bounds[0][i];
1844                 axis[i] = i;
1845         }
1846         // sort on largest axis
1847         for ( i = 0; i < 2; i++ ) {
1848                 if ( size[i] < size[i+1] ) {
1849                         t = size[i];
1850                         size[i] = size[i+1];
1851                         size[i+1] = t;
1852                         j = axis[i];
1853                         axis[i] = axis[i+1];
1854                         axis[i+1] = j;
1855                         i = -1;
1856                 }
1857         }
1858         // if the node is too small for further splits
1859         if ( size[0] < MIN_NODE_SIZE ) {
1860                 polyCount = 0;
1861                 for ( pref = node->polygons; pref; pref = pref->next) {
1862                         polyCount++;
1863                 }
1864                 if ( polyCount > MAX_NODE_POLYGONS ) {
1865                         forceSplit = true;
1866                 }
1867         }
1868         // find an axial aligned splitter
1869         for ( i = 0; i < 3; i++ ) {
1870                 // start with the largest axis first
1871                 type = axis[i];
1872                 bestt = size[i];
1873                 // if the node is small anough in this axis direction
1874                 if ( !forceSplit && bestt < MIN_NODE_SIZE ) {
1875                         break;
1876                 }
1877                 // find an axial splitter from the brush bounding boxes
1878                 // also try brushes from parent nodes
1879                 for ( n = node; n; n = n->parent ) {
1880                         for ( bref = n->brushes; bref; bref = bref->next) {
1881                                 for ( j = 0; j < 2; j++ ) {
1882                                         dist = bref->b->bounds[j][type];
1883                                         // if the splitter is already used or outside node bounds
1884                                         if ( dist >= bounds[1][type] || dist <= bounds[0][type] ) {
1885                                                 continue;
1886                                         }
1887                                         // find the most centered splitter
1888                                         t = abs((bounds[1][type] - dist) - (dist - bounds[0][type]));
1889                                         if ( t < bestt ) {
1890                                                 bestt = t;
1891                                                 *planeType = type;
1892                                                 *planeDist = dist;
1893                                         }
1894                                 }
1895                         }
1896                 }
1897                 // find an axial splitter from the polygon bounding boxes
1898                 // also try brushes from parent nodes
1899                 for ( n = node; n; n = n->parent ) {
1900                         for ( pref = n->polygons; pref; pref = pref->next) {
1901                                 for ( j = 0; j < 2; j++ ) {
1902                                         dist = pref->p->bounds[j][type];
1903                                         // if the splitter is already used or outside node bounds
1904                                         if ( dist >= bounds[1][type] || dist <= bounds[0][type] ) {
1905                                                 continue;
1906                                         }
1907                                         // find the most centered splitter
1908                                         t = abs((bounds[1][type] - dist) - (dist - bounds[0][type]));
1909                                         if ( t < bestt ) {
1910                                                 bestt = t;
1911                                                 *planeType = type;
1912                                                 *planeDist = dist;
1913                                         }
1914                                 }
1915                         }
1916                 }
1917                 // if we found a splitter on the largest axis
1918                 if ( bestt < size[i] ) {
1919                         // if forced split due to lots of polygons
1920                         if ( forceSplit ) {
1921                                 return true;
1922                         }
1923                         // don't create splitters real close to the bounds
1924                         if ( bounds[1][type] - *planeDist > (MIN_NODE_SIZE*0.5f) &&
1925                                 *planeDist - bounds[0][type] > (MIN_NODE_SIZE*0.5f) ) {
1926                                 return true;
1927                         }
1928                 }
1929         }
1930         return false;
1931 }
1932
1933 /*
1934 ================
1935 CM_R_InsideAllChildren
1936 ================
1937 */
1938 static int CM_R_InsideAllChildren( cm_node_t *node, const idBounds &bounds ) {
1939         assert(node != NULL);
1940         if ( node->planeType != -1 ) {
1941                 if ( bounds[0][node->planeType] >= node->planeDist ) {
1942                         return false;
1943                 }
1944                 if ( bounds[1][node->planeType] <= node->planeDist ) {
1945                         return false;
1946                 }
1947                 if ( !CM_R_InsideAllChildren( node->children[0], bounds ) ) {
1948                         return false;
1949                 }
1950                 if ( !CM_R_InsideAllChildren( node->children[1], bounds ) ) {
1951                         return false;
1952                 }
1953         }
1954         return true;
1955 }
1956
1957 /*
1958 ================
1959 idCollisionModelManagerLocal::R_FilterPolygonIntoTree
1960 ================
1961 */
1962 void idCollisionModelManagerLocal::R_FilterPolygonIntoTree( cm_model_t *model, cm_node_t *node, cm_polygonRef_t *pref, cm_polygon_t *p ) {
1963         assert(node != NULL);
1964         while ( node->planeType != -1 ) {
1965                 if ( CM_R_InsideAllChildren( node, p->bounds ) ) {
1966                         break;
1967                 }
1968                 if ( p->bounds[0][node->planeType] >= node->planeDist ) {
1969                         node = node->children[0];
1970                 }
1971                 else if ( p->bounds[1][node->planeType] <= node->planeDist ) {
1972                         node = node->children[1];
1973                 }
1974                 else {
1975                         R_FilterPolygonIntoTree( model, node->children[1], NULL, p );
1976                         node = node->children[0];
1977                 }
1978         }
1979         if ( pref ) {
1980                 pref->next = node->polygons;
1981                 node->polygons = pref;
1982         }
1983         else {
1984                 AddPolygonToNode( model, node, p );
1985         }
1986 }
1987
1988 /*
1989 ================
1990 idCollisionModelManagerLocal::R_FilterBrushIntoTree
1991 ================
1992 */
1993 void idCollisionModelManagerLocal::R_FilterBrushIntoTree( cm_model_t *model, cm_node_t *node, cm_brushRef_t *pref, cm_brush_t *b ) {
1994         assert(node != NULL);
1995         while ( node->planeType != -1 ) {
1996                 if ( CM_R_InsideAllChildren( node, b->bounds ) ) {
1997                         break;
1998                 }
1999                 if ( b->bounds[0][node->planeType] >= node->planeDist ) {
2000                         node = node->children[0];
2001                 }
2002                 else if ( b->bounds[1][node->planeType] <= node->planeDist ) {
2003                         node = node->children[1];
2004                 }
2005                 else {
2006                         R_FilterBrushIntoTree( model, node->children[1], NULL, b );
2007                         node = node->children[0];
2008                 }
2009         }
2010         if ( pref ) {
2011                 pref->next = node->brushes;
2012                 node->brushes = pref;
2013         }
2014         else {
2015                 AddBrushToNode( model, node, b );
2016         }
2017 }
2018
2019 /*
2020 ================
2021 idCollisionModelManagerLocal::R_CreateAxialBSPTree
2022
2023   a brush or polygon is linked in the node closest to the root where
2024   the brush or polygon is inside all children
2025 ================
2026 */
2027 cm_node_t *idCollisionModelManagerLocal::R_CreateAxialBSPTree( cm_model_t *model, cm_node_t *node, const idBounds &bounds ) {
2028         int planeType;
2029         float planeDist;
2030         cm_polygonRef_t *pref, *nextpref, *prevpref;
2031         cm_brushRef_t *bref, *nextbref, *prevbref;
2032         cm_node_t *frontNode, *backNode, *n;
2033         idBounds frontBounds, backBounds;
2034
2035         if ( !CM_FindSplitter( node, bounds, &planeType, &planeDist ) ) {
2036                 node->planeType = -1;
2037                 return node;
2038         }
2039         // create two child nodes
2040         frontNode = AllocNode( model, NODE_BLOCK_SIZE_LARGE );
2041         memset( frontNode, 0, sizeof(cm_node_t) );
2042         frontNode->parent = node;
2043         frontNode->planeType = -1;
2044         //
2045         backNode = AllocNode( model, NODE_BLOCK_SIZE_LARGE );
2046         memset( backNode, 0, sizeof(cm_node_t) );
2047         backNode->parent = node;
2048         backNode->planeType = -1;
2049         //
2050         model->numNodes += 2;
2051         // set front node bounds
2052         frontBounds = bounds;
2053         frontBounds[0][planeType] = planeDist;
2054         // set back node bounds
2055         backBounds = bounds;
2056         backBounds[1][planeType] = planeDist;
2057         //
2058         node->planeType = planeType;
2059         node->planeDist = planeDist;
2060         node->children[0] = frontNode;
2061         node->children[1] = backNode;
2062         // filter polygons and brushes down the tree if necesary
2063         for ( n = node; n; n = n->parent ) {
2064                 prevpref = NULL;
2065                 for ( pref = n->polygons; pref; pref = nextpref) {
2066                         nextpref = pref->next;
2067                         // if polygon is not inside all children
2068                         if ( !CM_R_InsideAllChildren( n, pref->p->bounds ) ) {
2069                                 // filter polygon down the tree
2070                                 R_FilterPolygonIntoTree( model, n, pref, pref->p );
2071                                 if ( prevpref ) {
2072                                         prevpref->next = nextpref;
2073                                 }
2074                                 else {
2075                                         n->polygons = nextpref;
2076                                 }
2077                         }
2078                         else {
2079                                 prevpref = pref;
2080                         }
2081                 }
2082                 prevbref = NULL;
2083                 for ( bref = n->brushes; bref; bref = nextbref) {
2084                         nextbref = bref->next;
2085                         // if brush is not inside all children
2086                         if ( !CM_R_InsideAllChildren( n, bref->b->bounds ) ) {
2087                                 // filter brush down the tree
2088                                 R_FilterBrushIntoTree( model, n, bref, bref->b );
2089                                 if ( prevbref ) {
2090                                         prevbref->next = nextbref;
2091                                 }
2092                                 else {
2093                                         n->brushes = nextbref;
2094                                 }
2095                         }
2096                         else {
2097                                 prevbref = bref;
2098                         }
2099                 }
2100         }
2101         R_CreateAxialBSPTree( model, frontNode, frontBounds );
2102         R_CreateAxialBSPTree( model, backNode, backBounds );
2103         return node;
2104 }
2105
2106 /*
2107 int cm_numSavedPolygonLinks;
2108 int cm_numSavedBrushLinks;
2109
2110 int CM_R_CountChildren( cm_node_t *node ) {
2111         if ( node->planeType == -1 ) {
2112                 return 0;
2113         }
2114         return 2 + CM_R_CountChildren(node->children[0]) + CM_R_CountChildren(node->children[1]);
2115 }
2116
2117 void CM_R_TestOptimisation( cm_node_t *node ) {
2118         int polyCount, brushCount, numChildren;
2119         cm_polygonRef_t *pref;
2120         cm_brushRef_t *bref;
2121
2122         if ( node->planeType == -1 ) {
2123                 return;
2124         }
2125         polyCount = 0;
2126         for ( pref = node->polygons; pref; pref = pref->next) {
2127                 polyCount++;
2128         }
2129         brushCount = 0;
2130         for ( bref = node->brushes; bref; bref = bref->next) {
2131                 brushCount++;
2132         }
2133         if ( polyCount || brushCount ) {
2134                 numChildren = CM_R_CountChildren( node );
2135                 cm_numSavedPolygonLinks += (numChildren - 1) * polyCount;
2136                 cm_numSavedBrushLinks += (numChildren - 1) * brushCount;
2137         }
2138         CM_R_TestOptimisation( node->children[0] );
2139         CM_R_TestOptimisation( node->children[1] );
2140 }
2141 */
2142
2143 /*
2144 ================
2145 idCollisionModelManagerLocal::CreateAxialBSPTree
2146 ================
2147 */
2148 cm_node_t *idCollisionModelManagerLocal::CreateAxialBSPTree( cm_model_t *model, cm_node_t *node ) {
2149         cm_polygonRef_t *pref;
2150         cm_brushRef_t *bref;
2151         idBounds bounds;
2152
2153         // get head node bounds
2154         bounds.Clear();
2155         for ( pref = node->polygons; pref; pref = pref->next) {
2156                 bounds += pref->p->bounds;
2157         }
2158         for ( bref = node->brushes; bref; bref = bref->next) {
2159                 bounds += bref->b->bounds;
2160         }
2161
2162         // create axial BSP tree from head node
2163         node = R_CreateAxialBSPTree( model, node, bounds );
2164
2165         return node;
2166 }
2167
2168 /*
2169 ===============================================================================
2170
2171 Raw polygon and brush data
2172
2173 ===============================================================================
2174 */
2175
2176 /*
2177 ================
2178 idCollisionModelManagerLocal::SetupHash
2179 ================
2180 */
2181 void idCollisionModelManagerLocal::SetupHash( void ) {
2182         if ( !cm_vertexHash ) {
2183                 cm_vertexHash = new idHashIndex( VERTEX_HASH_SIZE, 1024 );
2184         }
2185         if ( !cm_edgeHash ) {
2186                 cm_edgeHash = new idHashIndex( EDGE_HASH_SIZE, 1024 );
2187         }
2188         // init variables used during loading and optimization
2189         if ( !cm_windingList ) {
2190                 cm_windingList = new cm_windingList_t;
2191         }
2192         if ( !cm_outList ) {
2193                 cm_outList = new cm_windingList_t;
2194         }
2195         if ( !cm_tmpList ) {
2196                 cm_tmpList = new cm_windingList_t;
2197         }
2198 }
2199
2200 /*
2201 ================
2202 idCollisionModelManagerLocal::ShutdownHash
2203 ================
2204 */
2205 void idCollisionModelManagerLocal::ShutdownHash( void ) {
2206         delete cm_vertexHash;
2207         cm_vertexHash = NULL;
2208         delete cm_edgeHash;
2209         cm_edgeHash = NULL;
2210         delete cm_tmpList;
2211         cm_tmpList = NULL;
2212         delete cm_outList;
2213         cm_outList = NULL;
2214         delete cm_windingList;
2215         cm_windingList = NULL;
2216 }
2217
2218 /*
2219 ================
2220 idCollisionModelManagerLocal::ClearHash
2221 ================
2222 */
2223 void idCollisionModelManagerLocal::ClearHash( idBounds &bounds ) {
2224         int i;
2225         float f, max;
2226
2227         cm_vertexHash->Clear();
2228         cm_edgeHash->Clear();
2229
2230         cm_modelBounds = bounds;
2231         max = bounds[1].x - bounds[0].x;
2232         f = bounds[1].y - bounds[0].y;
2233         if ( f > max ) {
2234                 max = f;
2235         }
2236         cm_vertexShift = (float) max / VERTEX_HASH_BOXSIZE;
2237         for ( i = 0; (1<<i) < cm_vertexShift; i++ ) {
2238         }
2239         if ( i == 0 ) {
2240                 cm_vertexShift = 1;
2241         }
2242         else {
2243                 cm_vertexShift = i;
2244         }
2245 }
2246
2247 /*
2248 ================
2249 idCollisionModelManagerLocal::HashVec
2250 ================
2251 */
2252 ID_INLINE int idCollisionModelManagerLocal::HashVec(const idVec3 &vec) {
2253         /*
2254         int x, y;
2255
2256         x = (((int)(vec[0] - cm_modelBounds[0].x + 0.5 )) >> cm_vertexShift) & (VERTEX_HASH_BOXSIZE-1);
2257         y = (((int)(vec[1] - cm_modelBounds[0].y + 0.5 )) >> cm_vertexShift) & (VERTEX_HASH_BOXSIZE-1);
2258
2259         assert (x >= 0 && x < VERTEX_HASH_BOXSIZE && y >= 0 && y < VERTEX_HASH_BOXSIZE);
2260
2261         return y * VERTEX_HASH_BOXSIZE + x;
2262         */
2263         int x, y, z;
2264
2265         x = (((int) (vec[0] - cm_modelBounds[0].x + 0.5)) + 2) >> 2;
2266         y = (((int) (vec[1] - cm_modelBounds[0].y + 0.5)) + 2) >> 2;
2267         z = (((int) (vec[2] - cm_modelBounds[0].z + 0.5)) + 2) >> 2;
2268         return (x + y * VERTEX_HASH_BOXSIZE + z) & (VERTEX_HASH_SIZE-1);
2269 }
2270
2271 /*
2272 ================
2273 idCollisionModelManagerLocal::GetVertex
2274 ================
2275 */
2276 int idCollisionModelManagerLocal::GetVertex( cm_model_t *model, const idVec3 &v, int *vertexNum ) {
2277         int i, hashKey, vn;
2278         idVec3 vert, *p;
2279
2280         for (i = 0; i < 3; i++) {
2281                 if ( idMath::Fabs(v[i] - idMath::Rint(v[i])) < INTEGRAL_EPSILON )
2282                         vert[i] = idMath::Rint(v[i]);
2283                 else
2284                         vert[i] = v[i];
2285         }
2286
2287         hashKey = HashVec( vert );
2288
2289         for (vn = cm_vertexHash->First( hashKey ); vn >= 0; vn = cm_vertexHash->Next( vn ) ) {
2290                 p = &model->vertices[vn].p;
2291                 // first compare z-axis because hash is based on x-y plane
2292                 if (idMath::Fabs(vert[2] - (*p)[2]) < VERTEX_EPSILON &&
2293                         idMath::Fabs(vert[0] - (*p)[0]) < VERTEX_EPSILON &&
2294                         idMath::Fabs(vert[1] - (*p)[1]) < VERTEX_EPSILON )
2295                 {
2296                         *vertexNum = vn;
2297                         return true;
2298                 }
2299         }
2300
2301         if ( model->numVertices >= model->maxVertices ) {
2302                 cm_vertex_t *oldVertices;
2303
2304                 // resize vertex array
2305                 model->maxVertices = (float) model->maxVertices * 1.5f + 1;
2306                 oldVertices = model->vertices;
2307                 model->vertices = (cm_vertex_t *) Mem_ClearedAlloc( model->maxVertices * sizeof(cm_vertex_t) );
2308                 memcpy( model->vertices, oldVertices, model->numVertices * sizeof(cm_vertex_t) );
2309                 Mem_Free( oldVertices );
2310
2311                 cm_vertexHash->ResizeIndex( model->maxVertices );
2312         }
2313         model->vertices[model->numVertices].p = vert;
2314         model->vertices[model->numVertices].checkcount = 0;
2315         *vertexNum = model->numVertices;
2316         // add vertice to hash
2317         cm_vertexHash->Add( hashKey, model->numVertices );
2318         //
2319         model->numVertices++;
2320         return false;
2321 }
2322
2323 /*
2324 ================
2325 idCollisionModelManagerLocal::GetEdge
2326 ================
2327 */
2328 int idCollisionModelManagerLocal::GetEdge( cm_model_t *model, const idVec3 &v1, const idVec3 &v2, int *edgeNum, int v1num ) {
2329         int v2num, hashKey, e;
2330         int found, *vertexNum;
2331
2332         // the first edge is a dummy
2333         if ( model->numEdges == 0 ) {
2334                 model->numEdges = 1;
2335         }
2336
2337         if ( v1num != -1 ) {
2338                 found = 1;
2339         }
2340         else {
2341                 found = GetVertex( model, v1, &v1num );
2342         }
2343         found &= GetVertex( model, v2, &v2num );
2344         // if both vertices are the same or snapped onto each other
2345         if ( v1num == v2num ) {
2346                 *edgeNum = 0;
2347                 return true;
2348         }
2349         hashKey = cm_edgeHash->GenerateKey( v1num, v2num );
2350         // if both vertices where already stored
2351         if (found) {
2352                 for (e = cm_edgeHash->First( hashKey ); e >= 0; e = cm_edgeHash->Next( e ) )
2353                 {
2354                         // NOTE: only allow at most two users that use the edge in opposite direction
2355                         if ( model->edges[e].numUsers != 1 ) {
2356                                 continue;
2357                         }
2358
2359                         vertexNum = model->edges[e].vertexNum;
2360                         if ( vertexNum[0] == v2num ) {
2361                                 if ( vertexNum[1] == v1num ) {
2362                                         // negative for a reversed edge
2363                                         *edgeNum = -e;
2364                                         break;
2365                                 }
2366                         }
2367                         /*
2368                         else if ( vertexNum[0] == v1num ) {
2369                                 if ( vertexNum[1] == v2num ) {
2370                                         *edgeNum = e;
2371                                         break;
2372                                 }
2373                         }
2374                         */
2375                 }
2376                 // if edge found in hash
2377                 if ( e >= 0 ) {
2378                         model->edges[e].numUsers++;
2379                         return true;
2380                 }
2381         }
2382         if ( model->numEdges >= model->maxEdges ) {
2383                 cm_edge_t *oldEdges;
2384
2385                 // resize edge array
2386                 model->maxEdges = (float) model->maxEdges * 1.5f + 1;
2387                 oldEdges = model->edges;
2388                 model->edges = (cm_edge_t *) Mem_ClearedAlloc( model->maxEdges * sizeof(cm_edge_t) );
2389                 memcpy( model->edges, oldEdges, model->numEdges * sizeof(cm_edge_t) );
2390                 Mem_Free( oldEdges );
2391
2392                 cm_edgeHash->ResizeIndex( model->maxEdges );
2393         }
2394         // setup edge
2395         model->edges[model->numEdges].vertexNum[0] = v1num;
2396         model->edges[model->numEdges].vertexNum[1] = v2num;
2397         model->edges[model->numEdges].internal = false;
2398         model->edges[model->numEdges].checkcount = 0;
2399         model->edges[model->numEdges].numUsers = 1; // used by one polygon atm
2400         model->edges[model->numEdges].normal.Zero();
2401         //
2402         *edgeNum = model->numEdges;
2403         // add edge to hash
2404         cm_edgeHash->Add( hashKey, model->numEdges );
2405
2406         model->numEdges++;
2407
2408         return false;
2409 }
2410
2411 /*
2412 ================
2413 idCollisionModelManagerLocal::CreatePolygon
2414 ================
2415 */
2416 void idCollisionModelManagerLocal::CreatePolygon( cm_model_t *model, idFixedWinding *w, const idPlane &plane, const idMaterial *material, int primitiveNum ) {
2417         int i, j, edgeNum, v1num;
2418         int numPolyEdges, polyEdges[MAX_POINTS_ON_WINDING];
2419         idBounds bounds;
2420         cm_polygon_t *p;
2421
2422         // turn the winding into a sequence of edges
2423         numPolyEdges = 0;
2424         v1num = -1;             // first vertex unknown
2425         for ( i = 0, j = 1; i < w->GetNumPoints(); i++, j++ ) {
2426                 if ( j >= w->GetNumPoints() ) {
2427                         j = 0;
2428                 }
2429                 GetEdge( model, (*w)[i].ToVec3(), (*w)[j].ToVec3(), &polyEdges[numPolyEdges], v1num );
2430                 if ( polyEdges[numPolyEdges] ) {
2431                         // last vertex of this edge is the first vertex of the next edge
2432                         v1num = model->edges[ abs(polyEdges[numPolyEdges]) ].vertexNum[ INTSIGNBITNOTSET(polyEdges[numPolyEdges]) ];
2433                         // this edge is valid so keep it
2434                         numPolyEdges++;
2435                 }
2436         }
2437         // should have at least 3 edges
2438         if ( numPolyEdges < 3 ) {
2439                 return;
2440         }
2441         // the polygon is invalid if some edge is found twice
2442         for ( i = 0; i < numPolyEdges; i++ ) {
2443                 for ( j = i+1; j < numPolyEdges; j++ ) {
2444                         if ( abs(polyEdges[i]) == abs(polyEdges[j]) ) {
2445                                 return;
2446                         }
2447                 }
2448         }
2449         // don't overflow max edges
2450         if ( numPolyEdges > CM_MAX_POLYGON_EDGES ) {
2451                 common->Warning( "idCollisionModelManagerLocal::CreatePolygon: polygon has more than %d edges", numPolyEdges );
2452                 numPolyEdges = CM_MAX_POLYGON_EDGES;
2453         }
2454
2455         w->GetBounds( bounds );
2456
2457         p = AllocPolygon( model, numPolyEdges );
2458         p->numEdges = numPolyEdges;
2459         p->contents = material->GetContentFlags();
2460         p->material = material;
2461         p->checkcount = 0;
2462         p->plane = plane;
2463         p->bounds = bounds;
2464         for ( i = 0; i < numPolyEdges; i++ ) {
2465                 edgeNum = polyEdges[i];
2466                 p->edges[i] = edgeNum;
2467         }
2468         R_FilterPolygonIntoTree( model, model->node, NULL, p );
2469 }
2470
2471 /*
2472 ================
2473 idCollisionModelManagerLocal::PolygonFromWinding
2474
2475   NOTE: for patches primitiveNum < 0 and abs(primitiveNum) is the real number
2476 ================
2477 */
2478 void idCollisionModelManagerLocal::PolygonFromWinding( cm_model_t *model, idFixedWinding *w, const idPlane &plane, const idMaterial *material, int primitiveNum ) {
2479         int contents;
2480
2481         contents = material->GetContentFlags();
2482
2483         // if this polygon is part of the world model
2484         if ( numModels == 0 ) {
2485                 // if the polygon is fully chopped away by the proc bsp tree
2486                 if ( ChoppedAwayByProcBSP( *w, plane, contents ) ) {
2487                         model->numRemovedPolys++;
2488                         return;
2489                 }
2490         }
2491
2492         // get one winding that is not or only partly contained in brushes
2493         w = WindingOutsideBrushes( w, plane, contents, primitiveNum, model->node );
2494
2495         // if the polygon is fully contained within a brush
2496         if ( !w ) {
2497                 model->numRemovedPolys++;
2498                 return;
2499         }
2500
2501         if ( w->IsHuge() ) {
2502                 common->Warning( "idCollisionModelManagerLocal::PolygonFromWinding: model %s primitive %d is degenerate", model->name.c_str(), abs(primitiveNum) );
2503                 return;
2504         }
2505
2506         CreatePolygon( model, w, plane, material, primitiveNum );
2507
2508         if ( material->GetCullType() == CT_TWO_SIDED || material->ShouldCreateBackSides() ) {
2509                 w->ReverseSelf();
2510                 CreatePolygon( model, w, -plane, material, primitiveNum );
2511         }
2512 }
2513
2514 /*
2515 =================
2516 idCollisionModelManagerLocal::CreatePatchPolygons
2517 =================
2518 */
2519 void idCollisionModelManagerLocal::CreatePatchPolygons( cm_model_t *model, idSurface_Patch &mesh, const idMaterial *material, int primitiveNum ) {
2520         int i, j;
2521         float dot;
2522         int v1, v2, v3, v4;
2523         idFixedWinding w;
2524         idPlane plane;
2525         idVec3 d1, d2;
2526
2527         for ( i = 0; i < mesh.GetWidth() - 1; i++ ) {
2528                 for ( j = 0; j < mesh.GetHeight() - 1; j++ ) {
2529
2530                         v1 = j * mesh.GetWidth() + i;
2531                         v2 = v1 + 1;
2532                         v3 = v1 + mesh.GetWidth() + 1;
2533                         v4 = v1 + mesh.GetWidth();
2534
2535                         d1 = mesh[v2].xyz - mesh[v1].xyz;
2536                         d2 = mesh[v3].xyz - mesh[v1].xyz;
2537                         plane.SetNormal( d1.Cross(d2) );
2538                         if ( plane.Normalize() != 0.0f ) {
2539                                 plane.FitThroughPoint( mesh[v1].xyz );
2540                                 dot = plane.Distance( mesh[v4].xyz );
2541                                 // if we can turn it into a quad
2542                                 if ( idMath::Fabs(dot) < 0.1f ) {
2543                                         w.Clear();
2544                                         w += mesh[v1].xyz;
2545                                         w += mesh[v2].xyz;
2546                                         w += mesh[v3].xyz;
2547                                         w += mesh[v4].xyz;
2548
2549                                         PolygonFromWinding( model, &w, plane, material, -primitiveNum );
2550                                         continue;
2551                                 }
2552                                 else {
2553                                         // create one of the triangles
2554                                         w.Clear();
2555                                         w += mesh[v1].xyz;
2556                                         w += mesh[v2].xyz;
2557                                         w += mesh[v3].xyz;
2558
2559                                         PolygonFromWinding( model, &w, plane, material, -primitiveNum );
2560                                 }
2561                         }
2562                         // create the other triangle
2563                         d1 = mesh[v3].xyz - mesh[v1].xyz;
2564                         d2 = mesh[v4].xyz - mesh[v1].xyz;
2565                         plane.SetNormal( d1.Cross(d2) );
2566                         if ( plane.Normalize() != 0.0f ) {
2567                                 plane.FitThroughPoint( mesh[v1].xyz );
2568
2569                                 w.Clear();
2570                                 w += mesh[v1].xyz;
2571                                 w += mesh[v3].xyz;
2572                                 w += mesh[v4].xyz;
2573
2574                                 PolygonFromWinding( model, &w, plane, material, -primitiveNum );
2575                         }
2576                 }
2577         }
2578 }
2579
2580 /*
2581 =================
2582 CM_EstimateVertsAndEdges
2583 =================
2584 */
2585 static void CM_EstimateVertsAndEdges( const idMapEntity *mapEnt, int *numVerts, int *numEdges ) {
2586         int j, width, height;
2587
2588         *numVerts = *numEdges = 0;
2589         for ( j = 0; j < mapEnt->GetNumPrimitives(); j++ ) {
2590                 const idMapPrimitive *mapPrim;
2591                 mapPrim = mapEnt->GetPrimitive(j);
2592                 if ( mapPrim->GetType() == idMapPrimitive::TYPE_PATCH ) {
2593                         // assume maximum tesselation without adding verts
2594                         width = static_cast<const idMapPatch*>(mapPrim)->GetWidth();
2595                         height = static_cast<const idMapPatch*>(mapPrim)->GetHeight();
2596                         *numVerts += width * height;
2597                         *numEdges += (width-1) * height + width * (height-1) + (width-1) * (height-1);
2598                         continue;
2599                 }
2600                 if ( mapPrim->GetType() == idMapPrimitive::TYPE_BRUSH ) {
2601                         // assume cylinder with a polygon with (numSides - 2) edges ontop and on the bottom
2602                         *numVerts += (static_cast<const idMapBrush*>(mapPrim)->GetNumSides() - 2) * 2;
2603                         *numEdges += (static_cast<const idMapBrush*>(mapPrim)->GetNumSides() - 2) * 3;
2604                         continue;
2605                 }
2606         }
2607 }
2608
2609 /*
2610 =================
2611 idCollisionModelManagerLocal::ConverPatch
2612 =================
2613 */
2614 void idCollisionModelManagerLocal::ConvertPatch( cm_model_t *model, const idMapPatch *patch, int primitiveNum ) {
2615         const idMaterial *material;
2616         idSurface_Patch *cp;
2617
2618         material = declManager->FindMaterial( patch->GetMaterial() );
2619         if ( !( material->GetContentFlags() & CONTENTS_REMOVE_UTIL ) ) {
2620                 return;
2621         }
2622
2623         // copy the patch
2624         cp = new idSurface_Patch( *patch );
2625
2626         // if the patch has an explicit number of subdivisions use it to avoid cracks
2627         if ( patch->GetExplicitlySubdivided() ) {
2628                 cp->SubdivideExplicit( patch->GetHorzSubdivisions(), patch->GetVertSubdivisions(), false, true );
2629         } else {
2630                 cp->Subdivide( DEFAULT_CURVE_MAX_ERROR_CD, DEFAULT_CURVE_MAX_ERROR_CD, DEFAULT_CURVE_MAX_LENGTH_CD, false );
2631         }
2632
2633         // create collision polygons for the patch
2634         CreatePatchPolygons( model, *cp, material, primitiveNum );
2635
2636         delete cp;
2637 }
2638
2639 /*
2640 ================
2641 idCollisionModelManagerLocal::ConvertBrushSides
2642 ================
2643 */
2644 void idCollisionModelManagerLocal::ConvertBrushSides( cm_model_t *model, const idMapBrush *mapBrush, int primitiveNum ) {
2645         int i, j;
2646         idMapBrushSide *mapSide;
2647         idFixedWinding w;
2648         idPlane *planes;
2649         const idMaterial *material;
2650
2651         // fix degenerate planes
2652         planes = (idPlane *) _alloca16( mapBrush->GetNumSides() * sizeof( planes[0] ) );
2653         for ( i = 0; i < mapBrush->GetNumSides(); i++ ) {
2654                 planes[i] = mapBrush->GetSide(i)->GetPlane();
2655                 planes[i].FixDegeneracies( DEGENERATE_DIST_EPSILON );
2656         }
2657
2658         // create a collision polygon for each brush side
2659         for ( i = 0; i < mapBrush->GetNumSides(); i++ ) {
2660                 mapSide = mapBrush->GetSide(i);
2661                 material = declManager->FindMaterial( mapSide->GetMaterial() );
2662                 if ( !( material->GetContentFlags() & CONTENTS_REMOVE_UTIL ) ) {
2663                         continue;
2664                 }
2665                 w.BaseForPlane( -planes[i] );
2666                 for ( j = 0; j < mapBrush->GetNumSides() && w.GetNumPoints(); j++ ) {
2667                         if ( i == j ) {
2668                                 continue;
2669                         }
2670                         w.ClipInPlace( -planes[j], 0 );
2671                 }
2672
2673                 if ( w.GetNumPoints() ) {
2674                         PolygonFromWinding( model, &w, planes[i], material, primitiveNum );
2675                 }
2676         }
2677 }
2678
2679 /*
2680 ================
2681 idCollisionModelManagerLocal::ConvertBrush
2682 ================
2683 */
2684 void idCollisionModelManagerLocal::ConvertBrush( cm_model_t *model, const idMapBrush *mapBrush, int primitiveNum ) {
2685         int i, j, contents;
2686         idBounds bounds;
2687         idMapBrushSide *mapSide;
2688         cm_brush_t *brush;
2689         idPlane *planes;
2690         idFixedWinding w;
2691         const idMaterial *material = NULL;
2692
2693         contents = 0;
2694         bounds.Clear();
2695
2696         // fix degenerate planes
2697         planes = (idPlane *) _alloca16( mapBrush->GetNumSides() * sizeof( planes[0] ) );
2698         for ( i = 0; i < mapBrush->GetNumSides(); i++ ) {
2699                 planes[i] = mapBrush->GetSide(i)->GetPlane();
2700                 planes[i].FixDegeneracies( DEGENERATE_DIST_EPSILON );
2701         }
2702
2703         // we are only getting the bounds for the brush so there's no need
2704         // to create a winding for the last brush side
2705         for ( i = 0; i < mapBrush->GetNumSides() - 1; i++ ) {
2706                 mapSide = mapBrush->GetSide(i);
2707                 material = declManager->FindMaterial( mapSide->GetMaterial() );
2708                 contents |= ( material->GetContentFlags() & CONTENTS_REMOVE_UTIL );
2709                 w.BaseForPlane( -planes[i] );
2710                 for ( j = 0; j < mapBrush->GetNumSides() && w.GetNumPoints(); j++ ) {
2711                         if ( i == j ) {
2712                                 continue;
2713                         }
2714                         w.ClipInPlace( -planes[j], 0 );
2715                 }
2716
2717                 for ( j = 0; j < w.GetNumPoints(); j++ ) {
2718                         bounds.AddPoint( w[j].ToVec3() );
2719                 }
2720         }
2721         if ( !contents ) {
2722                 return;
2723         }
2724         // create brush for position test
2725         brush = AllocBrush( model, mapBrush->GetNumSides() );
2726         brush->checkcount = 0;
2727         brush->contents = contents;
2728         brush->material = material;
2729         brush->primitiveNum = primitiveNum;
2730         brush->bounds = bounds;
2731         brush->numPlanes = mapBrush->GetNumSides();
2732         for (i = 0; i < mapBrush->GetNumSides(); i++) {
2733                 brush->planes[i] = planes[i];
2734         }
2735         AddBrushToNode( model, model->node, brush );
2736 }
2737
2738 /*
2739 ================
2740 CM_CountNodeBrushes
2741 ================
2742 */
2743 static int CM_CountNodeBrushes( const cm_node_t *node ) {
2744         int count;
2745         cm_brushRef_t *bref;
2746
2747         count = 0;
2748         for ( bref = node->brushes; bref; bref = bref->next ) {
2749                 count++;
2750         }
2751         return count;
2752 }
2753
2754 /*
2755 ================
2756 CM_R_GetModelBounds
2757 ================
2758 */
2759 static void CM_R_GetNodeBounds( idBounds *bounds, cm_node_t *node ) {
2760         cm_polygonRef_t *pref;
2761         cm_brushRef_t *bref;
2762
2763         while ( 1 ) {
2764                 for ( pref = node->polygons; pref; pref = pref->next ) {
2765                         bounds->AddPoint( pref->p->bounds[0] );
2766                         bounds->AddPoint( pref->p->bounds[1] );
2767                 }
2768                 for ( bref = node->brushes; bref; bref = bref->next ) {
2769                         bounds->AddPoint( bref->b->bounds[0] );
2770                         bounds->AddPoint( bref->b->bounds[1] );
2771                 }
2772                 if ( node->planeType == -1 ) {
2773                         break;
2774                 }
2775                 CM_R_GetNodeBounds( bounds, node->children[1] );
2776                 node = node->children[0];
2777         }
2778 }
2779
2780 /*
2781 ================
2782 CM_GetNodeBounds
2783 ================
2784 */
2785 void CM_GetNodeBounds( idBounds *bounds, cm_node_t *node ) {
2786         bounds->Clear();
2787         CM_R_GetNodeBounds( bounds, node );
2788         if ( bounds->IsCleared() ) {
2789                 bounds->Zero();
2790         }
2791 }
2792
2793 /*
2794 ================
2795 CM_GetNodeContents
2796 ================
2797 */
2798 int CM_GetNodeContents( cm_node_t *node ) {
2799         int contents;
2800         cm_polygonRef_t *pref;
2801         cm_brushRef_t *bref;
2802
2803         contents = 0;
2804         while ( 1 ) {
2805                 for ( pref = node->polygons; pref; pref = pref->next ) {
2806                         contents |= pref->p->contents;
2807                 }
2808                 for ( bref = node->brushes; bref; bref = bref->next ) {
2809                         contents |= bref->b->contents;
2810                 }
2811                 if ( node->planeType == -1 ) {
2812                         break;
2813                 }
2814                 contents |= CM_GetNodeContents( node->children[1] );
2815                 node = node->children[0];
2816         }
2817         return contents;
2818 }
2819
2820 /*
2821 ==================
2822 idCollisionModelManagerLocal::RemapEdges
2823 ==================
2824 */
2825 void idCollisionModelManagerLocal::RemapEdges( cm_node_t *node, int *edgeRemap ) {
2826         cm_polygonRef_t *pref;
2827         cm_polygon_t *p;
2828         int i;
2829
2830         while ( 1 ) {
2831                 for ( pref = node->polygons; pref; pref = pref->next ) {
2832                         p = pref->p;
2833                         // if we checked this polygon already
2834                         if ( p->checkcount == checkCount ) {
2835                                 continue;
2836                         }
2837                         p->checkcount = checkCount;
2838                         for ( i = 0; i < p->numEdges; i++ ) {
2839                                 if ( p->edges[i] < 0 ) {
2840                                         p->edges[i] = -edgeRemap[ abs(p->edges[i]) ];
2841                                 }
2842                                 else {
2843                                         p->edges[i] = edgeRemap[ p->edges[i] ];
2844                                 }
2845                         }
2846                 }
2847                 if ( node->planeType == -1 ) {
2848                         break;
2849                 }
2850
2851                 RemapEdges( node->children[1], edgeRemap );
2852                 node = node->children[0];
2853         }
2854 }
2855
2856 /*
2857 ==================
2858 idCollisionModelManagerLocal::OptimizeArrays
2859
2860   due to polygon merging and polygon removal the vertex and edge array
2861   can have a lot of unused entries.
2862 ==================
2863 */
2864 void idCollisionModelManagerLocal::OptimizeArrays( cm_model_t *model ) {
2865         int i, newNumVertices, newNumEdges, *v;
2866         int *remap;
2867         cm_edge_t *oldEdges;
2868         cm_vertex_t *oldVertices;
2869
2870         remap = (int *) Mem_ClearedAlloc( Max( model->numVertices, model->numEdges ) * sizeof( int ) );
2871         // get all used vertices
2872         for ( i = 0; i < model->numEdges; i++ ) {
2873                 remap[ model->edges[i].vertexNum[0] ] = true;
2874                 remap[ model->edges[i].vertexNum[1] ] = true;
2875         }
2876         // create remap index and move vertices
2877         newNumVertices = 0;
2878         for ( i = 0; i < model->numVertices; i++ ) {
2879                 if ( remap[ i ] ) {
2880                         remap[ i ] = newNumVertices;
2881                         model->vertices[ newNumVertices ] = model->vertices[ i ];
2882                         newNumVertices++;
2883                 }
2884         }
2885         model->numVertices = newNumVertices;
2886         // change edge vertex indexes
2887         for ( i = 1; i < model->numEdges; i++ ) {
2888                 v = model->edges[i].vertexNum;
2889                 v[0] = remap[ v[0] ];
2890                 v[1] = remap[ v[1] ];
2891         }
2892
2893         // create remap index and move edges
2894         newNumEdges = 1;
2895         for ( i = 1; i < model->numEdges; i++ ) {
2896                 // if the edge is used
2897                 if ( model->edges[ i ].numUsers ) {
2898                         remap[ i ] = newNumEdges;
2899                         model->edges[ newNumEdges ] = model->edges[ i ];
2900                         newNumEdges++;
2901                 }
2902         }
2903         // change polygon edge indexes
2904         checkCount++;
2905         RemapEdges( model->node, remap );
2906         model->numEdges = newNumEdges;
2907
2908         Mem_Free( remap );
2909
2910         // realloc vertices
2911         oldVertices = model->vertices;
2912         if ( oldVertices ) {
2913                 model->vertices = (cm_vertex_t *) Mem_ClearedAlloc( model->numVertices * sizeof(cm_vertex_t) );
2914                 memcpy( model->vertices, oldVertices, model->numVertices * sizeof(cm_vertex_t) );
2915                 Mem_Free( oldVertices );
2916         }
2917
2918         // realloc edges
2919         oldEdges = model->edges;
2920         if ( oldEdges ) {
2921                 model->edges = (cm_edge_t *) Mem_ClearedAlloc( model->numEdges * sizeof(cm_edge_t) );
2922                 memcpy( model->edges, oldEdges, model->numEdges * sizeof(cm_edge_t) );
2923                 Mem_Free( oldEdges );
2924         }
2925 }
2926
2927 /*
2928 ================
2929 idCollisionModelManagerLocal::FinishModel
2930 ================
2931 */
2932 void idCollisionModelManagerLocal::FinishModel( cm_model_t *model ) {
2933         // try to merge polygons
2934         checkCount++;
2935         MergeTreePolygons( model, model->node );
2936         // find internal edges (no mesh can ever collide with internal edges)
2937         checkCount++;
2938         FindInternalEdges( model, model->node );
2939         // calculate edge normals
2940         checkCount++;
2941         CalculateEdgeNormals( model, model->node );
2942
2943         //common->Printf( "%s vertex hash spread is %d\n", model->name.c_str(), cm_vertexHash->GetSpread() );
2944         //common->Printf( "%s edge hash spread is %d\n", model->name.c_str(), cm_edgeHash->GetSpread() );
2945
2946         // remove all unused vertices and edges
2947         OptimizeArrays( model );
2948         // get model bounds from brush and polygon bounds
2949         CM_GetNodeBounds( &model->bounds, model->node );
2950         // get model contents
2951         model->contents = CM_GetNodeContents( model->node );
2952         // total memory used by this model
2953         model->usedMemory = model->numVertices * sizeof(cm_vertex_t) +
2954                                                 model->numEdges * sizeof(cm_edge_t) +
2955                                                 model->polygonMemory +
2956                                                 model->brushMemory +
2957                                                 model->numNodes * sizeof(cm_node_t) +
2958                                                 model->numPolygonRefs * sizeof(cm_polygonRef_t) +
2959                                                 model->numBrushRefs * sizeof(cm_brushRef_t);
2960 }
2961
2962 /*
2963 ================
2964 idCollisionModelManagerLocal::LoadRenderModel
2965 ================
2966 */
2967 cm_model_t *idCollisionModelManagerLocal::LoadRenderModel( const char *fileName ) {
2968         int i, j;
2969         idRenderModel *renderModel;
2970         const modelSurface_t *surf;
2971         idFixedWinding w;
2972         cm_node_t *node;
2973         cm_model_t *model;
2974         idPlane plane;
2975         idBounds bounds;
2976         bool collisionSurface;
2977         idStr extension;
2978
2979         // only load ASE and LWO models
2980         idStr( fileName ).ExtractFileExtension( extension );
2981         if ( ( extension.Icmp( "ase" ) != 0 ) && ( extension.Icmp( "lwo" ) != 0 ) && ( extension.Icmp( "ma" ) != 0 ) ) {
2982                 return NULL;
2983         }
2984
2985         if ( !renderModelManager->CheckModel( fileName ) ) {
2986                 return NULL;
2987         }
2988
2989         renderModel = renderModelManager->FindModel( fileName );
2990
2991         model = AllocModel();
2992         model->name = fileName;
2993         node = AllocNode( model, NODE_BLOCK_SIZE_SMALL );
2994         node->planeType = -1;
2995         model->node = node;
2996
2997         model->maxVertices = 0;
2998         model->numVertices = 0;
2999         model->maxEdges = 0;
3000         model->numEdges = 0;
3001
3002         bounds = renderModel->Bounds( NULL );
3003
3004         collisionSurface = false;
3005         for ( i = 0; i < renderModel->NumSurfaces(); i++ ) {
3006                 surf = renderModel->Surface( i );
3007                 if ( surf->shader->GetSurfaceFlags() & SURF_COLLISION ) {
3008                         collisionSurface = true;
3009                 }
3010         }
3011
3012         for ( i = 0; i < renderModel->NumSurfaces(); i++ ) {
3013                 surf = renderModel->Surface( i );
3014                 // if this surface has no contents
3015                 if ( ! ( surf->shader->GetContentFlags() & CONTENTS_REMOVE_UTIL ) ) {
3016                         continue;
3017                 }
3018                 // if the model has a collision surface and this surface is not a collision surface
3019                 if ( collisionSurface && !( surf->shader->GetSurfaceFlags() & SURF_COLLISION ) ) {
3020                         continue;
3021                 }
3022                 // get max verts and edges
3023                 model->maxVertices += surf->geometry->numVerts;
3024                 model->maxEdges += surf->geometry->numIndexes;
3025         }
3026
3027         model->vertices = (cm_vertex_t *) Mem_ClearedAlloc( model->maxVertices * sizeof(cm_vertex_t) );
3028         model->edges = (cm_edge_t *) Mem_ClearedAlloc( model->maxEdges * sizeof(cm_edge_t) );
3029
3030         // setup hash to speed up finding shared vertices and edges
3031         SetupHash();
3032
3033         cm_vertexHash->ResizeIndex( model->maxVertices );
3034         cm_edgeHash->ResizeIndex( model->maxEdges );
3035
3036         ClearHash( bounds );
3037
3038         for ( i = 0; i < renderModel->NumSurfaces(); i++ ) {
3039                 surf = renderModel->Surface( i );
3040                 // if this surface has no contents
3041                 if ( ! ( surf->shader->GetContentFlags() & CONTENTS_REMOVE_UTIL ) ) {
3042                         continue;
3043                 }
3044                 // if the model has a collision surface and this surface is not a collision surface
3045                 if ( collisionSurface && !( surf->shader->GetSurfaceFlags() & SURF_COLLISION ) ) {
3046                         continue;
3047                 }
3048
3049                 for ( j = 0; j < surf->geometry->numIndexes; j += 3 ) {
3050                         w.Clear();
3051                         w += surf->geometry->verts[ surf->geometry->indexes[ j + 2 ] ].xyz;
3052                         w += surf->geometry->verts[ surf->geometry->indexes[ j + 1 ] ].xyz;
3053                         w += surf->geometry->verts[ surf->geometry->indexes[ j + 0 ] ].xyz;
3054                         w.GetPlane( plane );
3055                         plane = -plane;
3056                         PolygonFromWinding( model, &w, plane, surf->shader, 1 );
3057                 }
3058         }
3059
3060         // create a BSP tree for the model
3061         model->node = CreateAxialBSPTree( model, model->node );
3062
3063         model->isConvex = false;
3064
3065         FinishModel( model );
3066
3067         // shutdown the hash
3068         ShutdownHash();
3069
3070         common->Printf( "loaded collision model %s\n", model->name.c_str() );
3071
3072         return model;
3073 }
3074
3075 /*
3076 ================
3077 idCollisionModelManagerLocal::CollisionModelForMapEntity
3078 ================
3079 */
3080 cm_model_t *idCollisionModelManagerLocal::CollisionModelForMapEntity( const idMapEntity *mapEnt ) {
3081         cm_model_t *model;
3082         idBounds bounds;
3083         const char *name;
3084         int i, brushCount;
3085
3086         // if the entity has no primitives
3087         if ( mapEnt->GetNumPrimitives() < 1 ) {
3088                 return NULL;
3089         }
3090
3091         // get a name for the collision model
3092         mapEnt->epairs.GetString( "model", "", &name );
3093         if ( !name[0] ) {
3094                 mapEnt->epairs.GetString( "name", "", &name );
3095                 if ( !name[0] ) {
3096                         if ( !numModels ) {
3097                                 // first model is always the world
3098                                 name = "worldMap";
3099                         }
3100                         else {
3101                                 name = "unnamed inline model";
3102                         }
3103                 }
3104         }
3105
3106         model = AllocModel();
3107         model->node = AllocNode( model, NODE_BLOCK_SIZE_SMALL );
3108
3109         CM_EstimateVertsAndEdges( mapEnt, &model->maxVertices, &model->maxEdges );
3110         model->numVertices = 0;
3111         model->numEdges = 0;
3112         model->vertices = (cm_vertex_t *) Mem_ClearedAlloc( model->maxVertices * sizeof(cm_vertex_t) );
3113         model->edges = (cm_edge_t *) Mem_ClearedAlloc( model->maxEdges * sizeof(cm_edge_t) );
3114
3115         cm_vertexHash->ResizeIndex( model->maxVertices );
3116         cm_edgeHash->ResizeIndex( model->maxEdges );
3117
3118         model->name = name;
3119         model->isConvex = false;
3120
3121         // convert brushes
3122         for ( i = 0; i < mapEnt->GetNumPrimitives(); i++ ) {
3123                 idMapPrimitive  *mapPrim;
3124
3125                 mapPrim = mapEnt->GetPrimitive(i);
3126                 if ( mapPrim->GetType() == idMapPrimitive::TYPE_BRUSH ) {
3127                         ConvertBrush( model, static_cast<idMapBrush*>(mapPrim), i );
3128                         continue;
3129                 }
3130         }
3131
3132         // create an axial bsp tree for the model if it has more than just a bunch brushes
3133         brushCount = CM_CountNodeBrushes( model->node );
3134         if ( brushCount > 4 ) {
3135                 model->node = CreateAxialBSPTree( model, model->node );
3136         } else {
3137                 model->node->planeType = -1;
3138         }
3139
3140         // get bounds for hash
3141         if ( brushCount ) {
3142                 CM_GetNodeBounds( &bounds, model->node );
3143         } else {
3144                 bounds[0].Set( -256, -256, -256 );
3145                 bounds[1].Set( 256, 256, 256 );
3146         }
3147
3148         // different models do not share edges and vertices with each other, so clear the hash
3149         ClearHash( bounds );
3150
3151         // create polygons from patches and brushes
3152         for ( i = 0; i < mapEnt->GetNumPrimitives(); i++ ) {
3153                 idMapPrimitive  *mapPrim;
3154
3155                 mapPrim = mapEnt->GetPrimitive(i);
3156                 if ( mapPrim->GetType() == idMapPrimitive::TYPE_PATCH ) {
3157                         ConvertPatch( model, static_cast<idMapPatch*>(mapPrim), i );
3158                         continue;
3159                 }
3160                 if ( mapPrim->GetType() == idMapPrimitive::TYPE_BRUSH ) {
3161                         ConvertBrushSides( model, static_cast<idMapBrush*>(mapPrim), i );
3162                         continue;
3163                 }
3164         }
3165
3166         FinishModel( model );
3167
3168         return model;
3169 }
3170
3171 /*
3172 ================
3173 idCollisionModelManagerLocal::FindModel
3174 ================
3175 */
3176 cmHandle_t idCollisionModelManagerLocal::FindModel( const char *name ) {
3177         int i;
3178
3179         // check if this model is already loaded
3180         for ( i = 0; i < numModels; i++ ) {
3181                 if ( !models[i]->name.Icmp( name ) ) {
3182                         break;
3183                 }
3184         }
3185         // if the model is already loaded
3186         if ( i < numModels ) {
3187                 return i;
3188         }
3189         return -1;
3190 }
3191
3192 /*
3193 ==================
3194 idCollisionModelManagerLocal::PrintModelInfo
3195 ==================
3196 */
3197 void idCollisionModelManagerLocal::PrintModelInfo( const cm_model_t *model ) {
3198         common->Printf( "%6i vertices (%i KB)\n", model->numVertices, (model->numVertices * sizeof(cm_vertex_t))>>10 );
3199         common->Printf( "%6i edges (%i KB)\n", model->numEdges, (model->numEdges * sizeof(cm_edge_t))>>10 );
3200         common->Printf( "%6i polygons (%i KB)\n", model->numPolygons, model->polygonMemory>>10 );
3201         common->Printf( "%6i brushes (%i KB)\n", model->numBrushes, model->brushMemory>>10 );
3202         common->Printf( "%6i nodes (%i KB)\n", model->numNodes, (model->numNodes * sizeof(cm_node_t))>>10 );
3203         common->Printf( "%6i polygon refs (%i KB)\n", model->numPolygonRefs, (model->numPolygonRefs * sizeof(cm_polygonRef_t))>>10 );
3204         common->Printf( "%6i brush refs (%i KB)\n", model->numBrushRefs, (model->numBrushRefs * sizeof(cm_brushRef_t))>>10 );
3205         common->Printf( "%6i internal edges\n", model->numInternalEdges );
3206         common->Printf( "%6i sharp edges\n", model->numSharpEdges );
3207         common->Printf( "%6i contained polygons removed\n", model->numRemovedPolys );
3208         common->Printf( "%6i polygons merged\n", model->numMergedPolys );
3209         common->Printf( "%6i KB total memory used\n", model->usedMemory>>10 );
3210 }
3211
3212 /*
3213 ================
3214 idCollisionModelManagerLocal::AccumulateModelInfo
3215 ================
3216 */
3217 void idCollisionModelManagerLocal::AccumulateModelInfo( cm_model_t *model ) {
3218         int i;
3219
3220         memset( model, 0, sizeof( *model ) );
3221         // accumulate statistics of all loaded models
3222         for ( i = 0; i < numModels; i++ ) {
3223                 model->numVertices += models[i]->numVertices;
3224                 model->numEdges += models[i]->numEdges;
3225                 model->numPolygons += models[i]->numPolygons;
3226                 model->polygonMemory += models[i]->polygonMemory;
3227                 model->numBrushes += models[i]->numBrushes;
3228                 model->brushMemory += models[i]->brushMemory;
3229                 model->numNodes += models[i]->numNodes;
3230                 model->numBrushRefs += models[i]->numBrushRefs;
3231                 model->numPolygonRefs += models[i]->numPolygonRefs;
3232                 model->numInternalEdges += models[i]->numInternalEdges;
3233                 model->numSharpEdges += models[i]->numSharpEdges;
3234                 model->numRemovedPolys += models[i]->numRemovedPolys;
3235                 model->numMergedPolys += models[i]->numMergedPolys;
3236                 model->usedMemory += models[i]->usedMemory;
3237         }
3238 }
3239
3240 /*
3241 ================
3242 idCollisionModelManagerLocal::ModelInfo
3243 ================
3244 */
3245 void idCollisionModelManagerLocal::ModelInfo( cmHandle_t model ) {
3246         cm_model_t modelInfo;
3247
3248         if ( model == -1 ) {
3249                 AccumulateModelInfo( &modelInfo );
3250                 PrintModelInfo( &modelInfo );
3251                 return;
3252         }
3253         if ( model < 0 || model > MAX_SUBMODELS || model > maxModels ) {
3254                 common->Printf( "idCollisionModelManagerLocal::ModelInfo: invalid model handle\n" );
3255                 return;
3256         }
3257         if ( !models[model] ) {
3258                 common->Printf( "idCollisionModelManagerLocal::ModelInfo: invalid model\n" );
3259                 return;
3260         }
3261
3262         PrintModelInfo( models[model] );
3263 }
3264
3265 /*
3266 ================
3267 idCollisionModelManagerLocal::ListModels
3268 ================
3269 */
3270 void idCollisionModelManagerLocal::ListModels( void ) {
3271         int i, totalMemory;
3272
3273         totalMemory = 0;
3274         for ( i = 0; i < numModels; i++ ) {
3275                 common->Printf( "%4d: %5d KB   %s\n", i, (models[i]->usedMemory>>10), models[i]->name.c_str() );
3276                 totalMemory += models[i]->usedMemory;
3277         }
3278         common->Printf( "%4d KB in %d models\n", (totalMemory>>10), numModels );
3279 }
3280
3281 /*
3282 ================
3283 idCollisionModelManagerLocal::BuildModels
3284 ================
3285 */
3286 void idCollisionModelManagerLocal::BuildModels( const idMapFile *mapFile ) {
3287         int i;
3288         const idMapEntity *mapEnt;
3289
3290         idTimer timer;
3291         timer.Start();
3292
3293         if ( !LoadCollisionModelFile( mapFile->GetName(), mapFile->GetGeometryCRC() ) ) {
3294
3295                 if ( !mapFile->GetNumEntities() ) {
3296                         return;
3297                 }
3298
3299                 // load the .proc file bsp for data optimisation
3300                 LoadProcBSP( mapFile->GetName() );
3301
3302                 // convert brushes and patches to collision data
3303                 for ( i = 0; i < mapFile->GetNumEntities(); i++ ) {
3304                         mapEnt = mapFile->GetEntity(i);
3305
3306                         if ( numModels >= MAX_SUBMODELS ) {
3307                                 common->Error( "idCollisionModelManagerLocal::BuildModels: more than %d collision models", MAX_SUBMODELS );
3308                                 break;
3309                         }
3310                         models[numModels] = CollisionModelForMapEntity( mapEnt );
3311                         if ( models[ numModels] ) {
3312                                 numModels++;
3313                         }
3314                 }
3315
3316                 // free the proc bsp which is only used for data optimization
3317                 Mem_Free( procNodes );
3318                 procNodes = NULL;
3319
3320                 // write the collision models to a file
3321                 WriteCollisionModelsToFile( mapFile->GetName(), 0, numModels, mapFile->GetGeometryCRC() );
3322         }
3323
3324         timer.Stop();
3325
3326         // print statistics on collision data
3327         cm_model_t model;
3328         AccumulateModelInfo( &model );
3329         common->Printf( "collision data:\n" );
3330         common->Printf( "%6i models\n", numModels );
3331         PrintModelInfo( &model );
3332         common->Printf( "%.0f msec to load collision data.\n", timer.Milliseconds() );
3333 }
3334
3335
3336 /*
3337 ================
3338 idCollisionModelManagerLocal::LoadMap
3339 ================
3340 */
3341 void idCollisionModelManagerLocal::LoadMap( const idMapFile *mapFile ) {
3342
3343         if ( mapFile == NULL ) {
3344                 common->Error( "idCollisionModelManagerLocal::LoadMap: NULL mapFile" );
3345         }
3346
3347         // check whether we can keep the current collision map based on the mapName and mapFileTime
3348         if ( loaded ) {
3349                 if ( mapName.Icmp( mapFile->GetName() ) == 0 ) {
3350                         if ( mapFile->GetFileTime() == mapFileTime ) {
3351                                 common->DPrintf( "Using loaded version\n" );
3352                                 return;
3353                         }
3354                         common->DPrintf( "Reloading modified map\n" );
3355                 }
3356                 FreeMap();
3357         }
3358
3359         // clear the collision map
3360         Clear();
3361
3362         // models
3363         maxModels = MAX_SUBMODELS;
3364         numModels = 0;
3365         models = (cm_model_t **) Mem_ClearedAlloc( (maxModels+1) * sizeof(cm_model_t *) );
3366
3367         // setup hash to speed up finding shared vertices and edges
3368         SetupHash();
3369
3370         // setup trace model structure
3371         SetupTrmModelStructure();
3372
3373         // build collision models
3374         BuildModels( mapFile );
3375
3376         // save name and time stamp
3377         mapName = mapFile->GetName();
3378         mapFileTime = mapFile->GetFileTime();
3379         loaded = true;
3380
3381         // shutdown the hash
3382         ShutdownHash();
3383 }
3384
3385 /*
3386 ===================
3387 idCollisionModelManagerLocal::GetModelName
3388 ===================
3389 */
3390 const char *idCollisionModelManagerLocal::GetModelName( cmHandle_t model ) const {
3391         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3392                 common->Printf( "idCollisionModelManagerLocal::GetModelBounds: invalid model handle\n" );
3393                 return "";
3394         }
3395         return models[model]->name.c_str();
3396 }
3397
3398 /*
3399 ===================
3400 idCollisionModelManagerLocal::GetModelBounds
3401 ===================
3402 */
3403 bool idCollisionModelManagerLocal::GetModelBounds( cmHandle_t model, idBounds &bounds ) const {
3404
3405         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3406                 common->Printf( "idCollisionModelManagerLocal::GetModelBounds: invalid model handle\n" );
3407                 return false;
3408         }
3409
3410         bounds = models[model]->bounds;
3411         return true;
3412 }
3413
3414 /*
3415 ===================
3416 idCollisionModelManagerLocal::GetModelContents
3417 ===================
3418 */
3419 bool idCollisionModelManagerLocal::GetModelContents( cmHandle_t model, int &contents ) const {
3420         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3421                 common->Printf( "idCollisionModelManagerLocal::GetModelContents: invalid model handle\n" );
3422                 return false;
3423         }
3424
3425         contents = models[model]->contents;
3426
3427         return true;
3428 }
3429
3430 /*
3431 ===================
3432 idCollisionModelManagerLocal::GetModelVertex
3433 ===================
3434 */
3435 bool idCollisionModelManagerLocal::GetModelVertex( cmHandle_t model, int vertexNum, idVec3 &vertex ) const {
3436         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3437                 common->Printf( "idCollisionModelManagerLocal::GetModelVertex: invalid model handle\n" );
3438                 return false;
3439         }
3440
3441         if ( vertexNum < 0 || vertexNum >= models[model]->numVertices ) {
3442                 common->Printf( "idCollisionModelManagerLocal::GetModelVertex: invalid vertex number\n" );
3443                 return false;
3444         }
3445
3446         vertex = models[model]->vertices[vertexNum].p;
3447
3448         return true;
3449 }
3450
3451 /*
3452 ===================
3453 idCollisionModelManagerLocal::GetModelEdge
3454 ===================
3455 */
3456 bool idCollisionModelManagerLocal::GetModelEdge( cmHandle_t model, int edgeNum, idVec3 &start, idVec3 &end ) const {
3457         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3458                 common->Printf( "idCollisionModelManagerLocal::GetModelEdge: invalid model handle\n" );
3459                 return false;
3460         }
3461
3462         edgeNum = abs( edgeNum );
3463         if ( edgeNum >= models[model]->numEdges ) {
3464                 common->Printf( "idCollisionModelManagerLocal::GetModelEdge: invalid edge number\n" );
3465                 return false;
3466         }
3467
3468         start = models[model]->vertices[models[model]->edges[edgeNum].vertexNum[0]].p;
3469         end = models[model]->vertices[models[model]->edges[edgeNum].vertexNum[1]].p;
3470
3471         return true;
3472 }
3473
3474 /*
3475 ===================
3476 idCollisionModelManagerLocal::GetModelPolygon
3477 ===================
3478 */
3479 bool idCollisionModelManagerLocal::GetModelPolygon( cmHandle_t model, int polygonNum, idFixedWinding &winding ) const {
3480         int i, edgeNum;
3481         cm_polygon_t *poly;
3482
3483         if ( model < 0 || model > MAX_SUBMODELS || model >= numModels || !models[model] ) {
3484                 common->Printf( "idCollisionModelManagerLocal::GetModelPolygon: invalid model handle\n" );
3485                 return false;
3486         }
3487
3488         poly = *reinterpret_cast<cm_polygon_t **>(&polygonNum);
3489         winding.Clear();
3490         for ( i = 0; i < poly->numEdges; i++ ) {
3491                 edgeNum = poly->edges[i];
3492                 winding += models[model]->vertices[ models[model]->edges[abs(edgeNum)].vertexNum[INTSIGNBITSET(edgeNum)] ].p;
3493         }
3494
3495         return true;
3496 }
3497
3498 /*
3499 ==================
3500 idCollisionModelManagerLocal::LoadModel
3501 ==================
3502 */
3503 cmHandle_t idCollisionModelManagerLocal::LoadModel( const char *modelName, const bool precache ) {
3504         int handle;
3505
3506         handle = FindModel( modelName );
3507         if ( handle >= 0 ) {
3508                 return handle;
3509         }
3510
3511         if ( numModels >= MAX_SUBMODELS ) {
3512                 common->Error( "idCollisionModelManagerLocal::LoadModel: no free slots\n" );
3513                 return 0;
3514         }
3515
3516         // try to load a .cm file
3517         if ( LoadCollisionModelFile( modelName, 0 ) ) {
3518                 handle = FindModel( modelName );
3519                 if ( handle >= 0 ) {
3520                         return handle;
3521                 } else {
3522                         common->Warning( "idCollisionModelManagerLocal::LoadModel: collision file for '%s' contains different model", modelName );
3523                 }
3524         }
3525
3526         // if only precaching .cm files do not waste memory converting render models
3527         if ( precache ) {
3528                 return 0;
3529         }
3530
3531         // try to load a .ASE or .LWO model and convert it to a collision model
3532         models[numModels] = LoadRenderModel( modelName );
3533         if ( models[numModels] != NULL ) {
3534                 numModels++;
3535                 return ( numModels - 1 );
3536         }
3537
3538         return 0;
3539 }
3540
3541 /*
3542 ==================
3543 idCollisionModelManagerLocal::TrmFromModel_r
3544 ==================
3545 */
3546 bool idCollisionModelManagerLocal::TrmFromModel_r( idTraceModel &trm, cm_node_t *node ) {
3547         cm_polygonRef_t *pref;
3548         cm_polygon_t *p;
3549         int i;
3550
3551         while ( 1 ) {
3552                 for ( pref = node->polygons; pref; pref = pref->next ) {
3553                         p = pref->p;
3554
3555                         if ( p->checkcount == checkCount ) {
3556                                 continue;
3557                         }
3558
3559                         p->checkcount = checkCount;
3560
3561                         if ( trm.numPolys >= MAX_TRACEMODEL_POLYS ) {
3562                                 return false;
3563                         }
3564                         // copy polygon properties
3565                         trm.polys[ trm.numPolys ].bounds = p->bounds;
3566                         trm.polys[ trm.numPolys ].normal = p->plane.Normal();
3567                         trm.polys[ trm.numPolys ].dist = p->plane.Dist();
3568                         trm.polys[ trm.numPolys ].numEdges = p->numEdges;
3569                         // copy edge index
3570                         for ( i = 0; i < p->numEdges; i++ ) {
3571                                 trm.polys[ trm.numPolys ].edges[ i ] = p->edges[ i ];
3572                         }
3573                         trm.numPolys++;
3574                 }
3575                 if ( node->planeType == -1 ) {
3576                         break;
3577                 }
3578                 if ( !TrmFromModel_r( trm, node->children[1] ) ) {
3579                         return false;
3580                 }
3581                 node = node->children[0];
3582         }
3583         return true;
3584 }
3585
3586 /*
3587 ==================
3588 idCollisionModelManagerLocal::TrmFromModel
3589
3590   NOTE: polygon merging can merge colinear edges and as such might cause dangling edges.
3591 ==================
3592 */
3593 bool idCollisionModelManagerLocal::TrmFromModel( const cm_model_t *model, idTraceModel &trm ) {
3594         int i, j, numEdgeUsers[MAX_TRACEMODEL_EDGES+1];
3595
3596         // if the model has too many vertices to fit in a trace model
3597         if ( model->numVertices > MAX_TRACEMODEL_VERTS ) {
3598                 common->Printf( "idCollisionModelManagerLocal::TrmFromModel: model %s has too many vertices.\n", model->name.c_str() );
3599                 PrintModelInfo( model );
3600                 return false;
3601         }
3602
3603         // plus one because the collision model accounts for the first unused edge
3604         if ( model->numEdges > MAX_TRACEMODEL_EDGES+1 ) {
3605                 common->Printf( "idCollisionModelManagerLocal::TrmFromModel: model %s has too many edges.\n", model->name.c_str() );
3606                 PrintModelInfo( model );
3607                 return false;
3608         }
3609
3610         trm.type = TRM_CUSTOM;
3611         trm.numVerts = 0;
3612         trm.numEdges = 1;
3613         trm.numPolys = 0;
3614         trm.bounds.Clear();
3615
3616         // copy polygons
3617         checkCount++;
3618         if ( !TrmFromModel_r( trm, model->node ) ) {
3619                 common->Printf( "idCollisionModelManagerLocal::TrmFromModel: model %s has too many polygons.\n", model->name.c_str() );
3620                 PrintModelInfo( model );
3621                 return false;
3622         }
3623
3624         // copy vertices
3625         for ( i = 0; i < model->numVertices; i++ ) {
3626                 trm.verts[ i ] = model->vertices[ i ].p;
3627                 trm.bounds.AddPoint( trm.verts[ i ] );
3628         }
3629         trm.numVerts = model->numVertices;
3630
3631         // copy edges
3632         for ( i = 0; i < model->numEdges; i++ ) {
3633                 trm.edges[ i ].v[0] = model->edges[ i ].vertexNum[0];
3634                 trm.edges[ i ].v[1] = model->edges[ i ].vertexNum[1];
3635         }
3636         // minus one because the collision model accounts for the first unused edge
3637         trm.numEdges = model->numEdges - 1;
3638
3639         // each edge should be used exactly twice
3640         memset( numEdgeUsers, 0, sizeof(numEdgeUsers) );
3641         for ( i = 0; i < trm.numPolys; i++ ) {
3642                 for ( j = 0; j < trm.polys[i].numEdges; j++ ) {
3643                         numEdgeUsers[ abs( trm.polys[i].edges[j] ) ]++;
3644                 }
3645         }
3646         for ( i = 1; i <= trm.numEdges; i++ ) {
3647                 if ( numEdgeUsers[i] != 2 ) {
3648                         common->Printf( "idCollisionModelManagerLocal::TrmFromModel: model %s has dangling edges, the model has to be an enclosed hull.\n", model->name.c_str() );
3649                         PrintModelInfo( model );
3650                         return false;
3651                 }
3652         }
3653
3654         // assume convex
3655         trm.isConvex = true;
3656         // check if really convex
3657         for ( i = 0; i < trm.numPolys; i++ ) {
3658                 // to be convex no vertices should be in front of any polygon plane
3659                 for ( j = 0; j < trm.numVerts; j++ ) {
3660                         if ( trm.polys[ i ].normal * trm.verts[ j ] - trm.polys[ i ].dist > 0.01f ) {
3661                                 trm.isConvex = false;
3662                                 break;
3663                         }
3664                 }
3665                 if ( j < trm.numVerts ) {
3666                         break;
3667                 }
3668         }
3669
3670         // offset to center of model
3671         trm.offset = trm.bounds.GetCenter();
3672
3673         trm.GenerateEdgeNormals();
3674
3675         return true;
3676 }
3677
3678 /*
3679 ==================
3680 idCollisionModelManagerLocal::TrmFromModel
3681 ==================
3682 */
3683 bool idCollisionModelManagerLocal::TrmFromModel( const char *modelName, idTraceModel &trm ) {
3684         cmHandle_t handle;
3685
3686         handle = LoadModel( modelName, false );
3687         if ( !handle ) {
3688                 common->Printf( "idCollisionModelManagerLocal::TrmFromModel: model %s not found.\n", modelName );
3689                 return false;
3690         }
3691
3692         return TrmFromModel( models[ handle ], trm );
3693 }