neo/cm/CollisionModel_local.h

   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 ===============================================================================
  35 */
  36
  37 #include "CollisionModel.h"
  38
  39 #define MIN_NODE_SIZE                                           64.0f
  40 #define MAX_NODE_POLYGONS                                       128
  41 #define CM_MAX_POLYGON_EDGES                            64
  42 #define CIRCLE_APPROXIMATION_LENGTH                     64.0f
  43
  44 #define MAX_SUBMODELS                                           2048
  45 #define TRACE_MODEL_HANDLE                                      MAX_SUBMODELS
  46
  47 #define VERTEX_HASH_BOXSIZE                                     (1<<6)  // must be power of 2
  48 #define VERTEX_HASH_SIZE                                        (VERTEX_HASH_BOXSIZE*VERTEX_HASH_BOXSIZE)
  49 #define EDGE_HASH_SIZE                                          (1<<14)
  50
  51 #define NODE_BLOCK_SIZE_SMALL                           8
  52 #define NODE_BLOCK_SIZE_LARGE                           256
  53 #define REFERENCE_BLOCK_SIZE_SMALL                      8
  54 #define REFERENCE_BLOCK_SIZE_LARGE                      256
  55
  56 #define MAX_WINDING_LIST                                        128             // quite a few are generated at times
  57 #define INTEGRAL_EPSILON                                        0.01f
  58 #define VERTEX_EPSILON                                          0.1f
  59 #define CHOP_EPSILON                                            0.1f
  60
  61
  62 typedef struct cm_windingList_s {
  63         int                                     numWindings;                    // number of windings
  64         idFixedWinding          w[MAX_WINDING_LIST];    // windings
  65         idVec3                          normal;                                 // normal for all windings
  66         idBounds                        bounds;                                 // bounds of all windings in list
  67         idVec3                          origin;                                 // origin for radius
  68         float                           radius;                                 // radius relative to origin for all windings
  69         int                                     contents;                               // winding surface contents
  70         int                                     primitiveNum;                   // number of primitive the windings came from
  71 } cm_windingList_t;
  72
  73 /*
  74 ===============================================================================
  75
  76 Collision model
  77
  78 ===============================================================================
  79 */
  80
  81 typedef struct cm_vertex_s {
  82         idVec3                                  p;                                      // vertex point
  83         int                                             checkcount;                     // for multi-check avoidance
  84         unsigned long                   side;                           // each bit tells at which side this vertex passes one of the trace model edges
  85         unsigned long                   sideSet;                        // each bit tells if sidedness for the trace model edge has been calculated yet
  86 } cm_vertex_t;
  87
  88 typedef struct cm_edge_s {
  89         int                                             checkcount;                     // for multi-check avoidance
  90         unsigned short                  internal;                       // a trace model can never collide with internal edges
  91         unsigned short                  numUsers;                       // number of polygons using this edge
  92         unsigned long                   side;                           // each bit tells at which side of this edge one of the trace model vertices passes
  93         unsigned long                   sideSet;                        // each bit tells if sidedness for the trace model vertex has been calculated yet
  94         int                                             vertexNum[2];           // start and end point of edge
  95         idVec3                                  normal;                         // edge normal
  96 } cm_edge_t;
  97
  98 typedef struct cm_polygonBlock_s {
  99         int                                             bytesRemaining;
 100         byte *                                  next;
 101 } cm_polygonBlock_t;
 102
 103 typedef struct cm_polygon_s {
 104         idBounds                                bounds;                         // polygon bounds
 105         int                                             checkcount;                     // for multi-check avoidance
 106         int                                             contents;                       // contents behind polygon
 107         const idMaterial *              material;                       // material
 108         idPlane                                 plane;                          // polygon plane
 109         int                                             numEdges;                       // number of edges
 110         int                                             edges[1];                       // variable sized, indexes into cm_edge_t list
 111 } cm_polygon_t;
 112
 113 typedef struct cm_polygonRef_s {
 114         cm_polygon_t *                  p;                                      // pointer to polygon
 115         struct cm_polygonRef_s *next;                           // next polygon in chain
 116 } cm_polygonRef_t;
 117
 118 typedef struct cm_polygonRefBlock_s {
 119         cm_polygonRef_t *               nextRef;                        // next polygon reference in block
 120         struct cm_polygonRefBlock_s *next;                      // next block with polygon references
 121 } cm_polygonRefBlock_t;
 122
 123 typedef struct cm_brushBlock_s {
 124         int                                             bytesRemaining;
 125         byte *                                  next;
 126 } cm_brushBlock_t;
 127
 128 typedef struct cm_brush_s {
 129         int                                             checkcount;                     // for multi-check avoidance
 130         idBounds                                bounds;                         // brush bounds
 131         int                                             contents;                       // contents of brush
 132         const idMaterial *              material;                       // material
 133         int                                             primitiveNum;           // number of brush primitive
 134         int                                             numPlanes;                      // number of bounding planes
 135         idPlane                                 planes[1];                      // variable sized
 136 } cm_brush_t;
 137
 138 typedef struct cm_brushRef_s {
 139         cm_brush_t *                    b;                                      // pointer to brush
 140         struct cm_brushRef_s *  next;                           // next brush in chain
 141 } cm_brushRef_t;
 142
 143 typedef struct cm_brushRefBlock_s {
 144         cm_brushRef_t *                 nextRef;                        // next brush reference in block
 145         struct cm_brushRefBlock_s *next;                        // next block with brush references
 146 } cm_brushRefBlock_t;
 147
 148 typedef struct cm_node_s {
 149         int                                             planeType;                      // node axial plane type
 150         float                                   planeDist;                      // node plane distance
 151         cm_polygonRef_t *               polygons;                       // polygons in node
 152         cm_brushRef_t *                 brushes;                        // brushes in node
 153         struct cm_node_s *              parent;                         // parent of this node
 154         struct cm_node_s *              children[2];            // node children
 155 } cm_node_t;
 156
 157 typedef struct cm_nodeBlock_s {
 158         cm_node_t *                             nextNode;                       // next node in block
 159         struct cm_nodeBlock_s *next;                            // next block with nodes
 160 } cm_nodeBlock_t;
 161
 162 typedef struct cm_model_s {
 163         idStr                                   name;                           // model name
 164         idBounds                                bounds;                         // model bounds
 165         int                                             contents;                       // all contents of the model ored together
 166         bool                                    isConvex;                       // set if model is convex
 167         // model geometry
 168         int                                             maxVertices;            // size of vertex array
 169         int                                             numVertices;            // number of vertices
 170         cm_vertex_t *                   vertices;                       // array with all vertices used by the model
 171         int                                             maxEdges;                       // size of edge array
 172         int                                             numEdges;                       // number of edges
 173         cm_edge_t *                             edges;                          // array with all edges used by the model
 174         cm_node_t *                             node;                           // first node of spatial subdivision
 175         // blocks with allocated memory
 176         cm_nodeBlock_t *                nodeBlocks;                     // list with blocks of nodes
 177         cm_polygonRefBlock_t *  polygonRefBlocks;       // list with blocks of polygon references
 178         cm_brushRefBlock_t *    brushRefBlocks;         // list with blocks of brush references
 179         cm_polygonBlock_t *             polygonBlock;           // memory block with all polygons
 180         cm_brushBlock_t *               brushBlock;                     // memory block with all brushes
 181         // statistics
 182         int                                             numPolygons;
 183         int                                             polygonMemory;
 184         int                                             numBrushes;
 185         int                                             brushMemory;
 186         int                                             numNodes;
 187         int                                             numBrushRefs;
 188         int                                             numPolygonRefs;
 189         int                                             numInternalEdges;
 190         int                                             numSharpEdges;
 191         int                                             numRemovedPolys;
 192         int                                             numMergedPolys;
 193         int                                             usedMemory;
 194 } cm_model_t;
 195
 196 /*
 197 ===============================================================================
 198
 199 Data used during collision detection calculations
 200
 201 ===============================================================================
 202 */
 203
 204 typedef struct cm_trmVertex_s {
 205         int used;                                                                               // true if this vertex is used for collision detection
 206         idVec3 p;                                                                               // vertex position
 207         idVec3 endp;                                                                    // end point of vertex after movement
 208         int polygonSide;                                                                // side of polygon this vertex is on (rotational collision)
 209         idPluecker pl;                                                                  // pluecker coordinate for vertex movement
 210         idVec3 rotationOrigin;                                                  // rotation origin for this vertex
 211         idBounds rotationBounds;                                                // rotation bounds for this vertex
 212 } cm_trmVertex_t;
 213
 214 typedef struct cm_trmEdge_s {
 215         int used;                                                                               // true when vertex is used for collision detection
 216         idVec3 start;                                                                   // start of edge
 217         idVec3 end;                                                                             // end of edge
 218         int vertexNum[2];                                                               // indexes into cm_traceWork_t->vertices
 219         idPluecker pl;                                                                  // pluecker coordinate for edge
 220         idVec3 cross;                                                                   // (z,-y,x) of cross product between edge dir and movement dir
 221         idBounds rotationBounds;                                                // rotation bounds for this edge
 222         idPluecker plzaxis;                                                             // pluecker coordinate for rotation about the z-axis
 223         unsigned short bitNum;                                                  // vertex bit number
 224 } cm_trmEdge_t;
 225
 226 typedef struct cm_trmPolygon_s {
 227         int used;
 228         idPlane plane;                                                                  // polygon plane
 229         int numEdges;                                                                   // number of edges
 230         int edges[MAX_TRACEMODEL_POLYEDGES];                    // index into cm_traceWork_t->edges
 231         idBounds rotationBounds;                                                // rotation bounds for this polygon
 232 } cm_trmPolygon_t;
 233
 234 typedef struct cm_traceWork_s {
 235         int numVerts;
 236         cm_trmVertex_t vertices[MAX_TRACEMODEL_VERTS];  // trm vertices
 237         int numEdges;
 238         cm_trmEdge_t edges[MAX_TRACEMODEL_EDGES+1];             // trm edges
 239         int numPolys;
 240         cm_trmPolygon_t polys[MAX_TRACEMODEL_POLYS];    // trm polygons
 241         cm_model_t *model;                                                              // model colliding with
 242         idVec3 start;                                                                   // start of trace
 243         idVec3 end;                                                                             // end of trace
 244         idVec3 dir;                                                                             // trace direction
 245         idBounds bounds;                                                                // bounds of full trace
 246         idBounds size;                                                                  // bounds of transformed trm relative to start
 247         idVec3 extents;                                                                 // largest of abs(size[0]) and abs(size[1]) for BSP trace
 248         int contents;                                                                   // ignore polygons that do not have any of these contents flags
 249         trace_t trace;                                                                  // collision detection result
 250
 251         bool rotation;                                                                  // true if calculating rotational collision
 252         bool pointTrace;                                                                // true if only tracing a point
 253         bool positionTest;                                                              // true if not tracing but doing a position test
 254         bool isConvex;                                                                  // true if the trace model is convex
 255         bool axisIntersectsTrm;                                                 // true if the rotation axis intersects the trace model
 256         bool getContacts;                                                               // true if retrieving contacts
 257         bool quickExit;                                                                 // set to quickly stop the collision detection calculations
 258
 259         idVec3 origin;                                                                  // origin of rotation in model space
 260         idVec3 axis;                                                                    // rotation axis in model space
 261         idMat3 matrix;                                                                  // rotates axis of rotation to the z-axis
 262         float angle;                                                                    // angle for rotational collision
 263         float maxTan;                                                                   // max tangent of half the positive angle used instead of fraction
 264         float radius;                                                                   // rotation radius of trm start
 265         idRotation modelVertexRotation;                                 // inverse rotation for model vertices
 266
 267         contactInfo_t *contacts;                                                // array with contacts
 268         int maxContacts;                                                                // max size of contact array
 269         int numContacts;                                                                // number of contacts found
 270
 271         idPlane heartPlane1;                                                    // polygons should be near anough the trace heart planes
 272         float maxDistFromHeartPlane1;
 273         idPlane heartPlane2;
 274         float maxDistFromHeartPlane2;
 275         idPluecker polygonEdgePlueckerCache[CM_MAX_POLYGON_EDGES];
 276         idPluecker polygonVertexPlueckerCache[CM_MAX_POLYGON_EDGES];
 277         idVec3 polygonRotationOriginCache[CM_MAX_POLYGON_EDGES];
 278 } cm_traceWork_t;
 279
 280 /*
 281 ===============================================================================
 282
 283 Collision Map
 284
 285 ===============================================================================
 286 */
 287
 288 typedef struct cm_procNode_s {
 289         idPlane plane;
 290         int children[2];                                // negative numbers are (-1 - areaNumber), 0 = solid
 291 } cm_procNode_t;
 292
 293 class idCollisionModelManagerLocal : public idCollisionModelManager {
 294 public:
 295         // load collision models from a map file
 296         void                    LoadMap( const idMapFile *mapFile );
 297         // frees all the collision models
 298         void                    FreeMap( void );
 299
 300         // get clip handle for model
 301         cmHandle_t              LoadModel( const char *modelName, const bool precache );
 302         // sets up a trace model for collision with other trace models
 303         cmHandle_t              SetupTrmModel( const idTraceModel &trm, const idMaterial *material );
 304         // create trace model from a collision model, returns true if succesfull
 305         bool                    TrmFromModel( const char *modelName, idTraceModel &trm );
 306
 307         // name of the model
 308         const char *    GetModelName( cmHandle_t model ) const;
 309         // bounds of the model
 310         bool                    GetModelBounds( cmHandle_t model, idBounds &bounds ) const;
 311         // all contents flags of brushes and polygons ored together
 312         bool                    GetModelContents( cmHandle_t model, int &contents ) const;
 313         // get the vertex of a model
 314         bool                    GetModelVertex( cmHandle_t model, int vertexNum, idVec3 &vertex ) const;
 315         // get the edge of a model
 316         bool                    GetModelEdge( cmHandle_t model, int edgeNum, idVec3 &start, idVec3 &end ) const;
 317         // get the polygon of a model
 318         bool                    GetModelPolygon( cmHandle_t model, int polygonNum, idFixedWinding &winding ) const;
 319
 320         // translates a trm and reports the first collision if any
 321         void                    Translation( trace_t *results, const idVec3 &start, const idVec3 &end,
 322                                                                 const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 323                                                                 cmHandle_t model, const idVec3 &modelOrigin, const idMat3 &modelAxis );
 324         // rotates a trm and reports the first collision if any
 325         void                    Rotation( trace_t *results, const idVec3 &start, const idRotation &rotation,
 326                                                                 const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 327                                                                 cmHandle_t model, const idVec3 &modelOrigin, const idMat3 &modelAxis );
 328         // returns the contents the trm is stuck in or 0 if the trm is in free space
 329         int                             Contents( const idVec3 &start,
 330                                                                 const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 331                                                                 cmHandle_t model, const idVec3 &modelOrigin, const idMat3 &modelAxis );
 332         // stores all contact points of the trm with the model, returns the number of contacts
 333         int                             Contacts( contactInfo_t *contacts, const int maxContacts, const idVec3 &start, const idVec6 &dir, const float depth,
 334                                                                 const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 335                                                                 cmHandle_t model, const idVec3 &modelOrigin, const idMat3 &modelAxis );
 336         // test collision detection
 337         void                    DebugOutput( const idVec3 &origin );
 338         // draw a model
 339         void                    DrawModel( cmHandle_t model, const idVec3 &origin, const idMat3 &axis,
 340                                                                                         const idVec3 &viewOrigin, const float radius );
 341         // print model information, use -1 handle for accumulated model info
 342         void                    ModelInfo( cmHandle_t model );
 343         // list all loaded models
 344         void                    ListModels( void );
 345         // write a collision model file for the map entity
 346         bool                    WriteCollisionModelForMapEntity( const idMapEntity *mapEnt, const char *filename, const bool testTraceModel = true );
 347
 348 private:                        // CollisionMap_translate.cpp
 349         int                             TranslateEdgeThroughEdge( idVec3 &cross, idPluecker &l1, idPluecker &l2, float *fraction );
 350         void                    TranslateTrmEdgeThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *poly, cm_trmEdge_t *trmEdge );
 351         void                    TranslateTrmVertexThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *poly, cm_trmVertex_t *v, int bitNum );
 352         void                    TranslatePointThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *poly, cm_trmVertex_t *v );
 353         void                    TranslateVertexThroughTrmPolygon( cm_traceWork_t *tw, cm_trmPolygon_t *trmpoly, cm_polygon_t *poly, cm_vertex_t *v, idVec3 &endp, idPluecker &pl );
 354         bool                    TranslateTrmThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *p );
 355         void                    SetupTranslationHeartPlanes( cm_traceWork_t *tw );
 356         void                    SetupTrm( cm_traceWork_t *tw, const idTraceModel *trm );
 357
 358 private:                        // CollisionMap_rotate.cpp
 359         int                             CollisionBetweenEdgeBounds( cm_traceWork_t *tw, const idVec3 &va, const idVec3 &vb,
 360                                                                                         const idVec3 &vc, const idVec3 &vd, float tanHalfAngle,
 361                                                                                         idVec3 &collisionPoint, idVec3 &collisionNormal );
 362         int                             RotateEdgeThroughEdge( cm_traceWork_t *tw, const idPluecker &pl1,
 363                                                                                         const idVec3 &vc, const idVec3 &vd,
 364                                                                                         const float minTan, float &tanHalfAngle );
 365         int                             EdgeFurthestFromEdge( cm_traceWork_t *tw, const idPluecker &pl1,
 366                                                                                         const idVec3 &vc, const idVec3 &vd,
 367                                                                                         float &tanHalfAngle, float &dir );
 368         void                    RotateTrmEdgeThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *poly, cm_trmEdge_t *trmEdge );
 369         int                             RotatePointThroughPlane( const cm_traceWork_t *tw, const idVec3 &point, const idPlane &plane,
 370                                                                                         const float angle, const float minTan, float &tanHalfAngle );
 371         int                             PointFurthestFromPlane( const cm_traceWork_t *tw, const idVec3 &point, const idPlane &plane,
 372                                                                                         const float angle, float &tanHalfAngle, float &dir );
 373         int                             RotatePointThroughEpsilonPlane( const cm_traceWork_t *tw, const idVec3 &point, const idVec3 &endPoint,
 374                                                                                         const idPlane &plane, const float angle, const idVec3 &origin,
 375                                                                                         float &tanHalfAngle, idVec3 &collisionPoint, idVec3 &endDir );
 376         void                    RotateTrmVertexThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *poly, cm_trmVertex_t *v, int vertexNum);
 377         void                    RotateVertexThroughTrmPolygon( cm_traceWork_t *tw, cm_trmPolygon_t *trmpoly, cm_polygon_t *poly,
 378                                                                                         cm_vertex_t *v, idVec3 &rotationOrigin );
 379         bool                    RotateTrmThroughPolygon( cm_traceWork_t *tw, cm_polygon_t *p );
 380         void                    BoundsForRotation( const idVec3 &origin, const idVec3 &axis, const idVec3 &start, const idVec3 &end, idBounds &bounds );
 381         void                    Rotation180( trace_t *results, const idVec3 &rorg, const idVec3 &axis,
 382                                                                         const float startAngle, const float endAngle, const idVec3 &start,
 383                                                                         const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 384                                                                         cmHandle_t model, const idVec3 &origin, const idMat3 &modelAxis );
 385
 386 private:                        // CollisionMap_contents.cpp
 387         bool                    TestTrmVertsInBrush( cm_traceWork_t *tw, cm_brush_t *b );
 388         bool                    TestTrmInPolygon( cm_traceWork_t *tw, cm_polygon_t *p );
 389         cm_node_t *             PointNode( const idVec3 &p, cm_model_t *model );
 390         int                             PointContents( const idVec3 p, cmHandle_t model );
 391         int                             TransformedPointContents( const idVec3 &p, cmHandle_t model, const idVec3 &origin, const idMat3 &modelAxis );
 392         int                             ContentsTrm( trace_t *results, const idVec3 &start,
 393                                                                         const idTraceModel *trm, const idMat3 &trmAxis, int contentMask,
 394                                                                         cmHandle_t model, const idVec3 &modelOrigin, const idMat3 &modelAxis );
 395
 396 private:                        // CollisionMap_trace.cpp
 397         void                    TraceTrmThroughNode( cm_traceWork_t *tw, cm_node_t *node );
 398         void                    TraceThroughAxialBSPTree_r( cm_traceWork_t *tw, cm_node_t *node, float p1f, float p2f, idVec3 &p1, idVec3 &p2);
 399         void                    TraceThroughModel( cm_traceWork_t *tw );
 400         void                    RecurseProcBSP_r( trace_t *results, int parentNodeNum, int nodeNum, float p1f, float p2f, const idVec3 &p1, const idVec3 &p2 );
 401
 402 private:                        // CollisionMap_load.cpp
 403         void                    Clear( void );
 404         void                    FreeTrmModelStructure( void );
 405                                         // model deallocation
 406         void                    RemovePolygonReferences_r( cm_node_t *node, cm_polygon_t *p );
 407         void                    RemoveBrushReferences_r( cm_node_t *node, cm_brush_t *b );
 408         void                    FreeNode( cm_node_t *node );
 409         void                    FreePolygonReference( cm_polygonRef_t *pref );
 410         void                    FreeBrushReference( cm_brushRef_t *bref );
 411         void                    FreePolygon( cm_model_t *model, cm_polygon_t *poly );
 412         void                    FreeBrush( cm_model_t *model, cm_brush_t *brush );
 413         void                    FreeTree_r( cm_model_t *model, cm_node_t *headNode, cm_node_t *node );
 414         void                    FreeModel( cm_model_t *model );
 415                                         // merging polygons
 416         void                    ReplacePolygons( cm_model_t *model, cm_node_t *node, cm_polygon_t *p1, cm_polygon_t *p2, cm_polygon_t *newp );
 417         cm_polygon_t *  TryMergePolygons( cm_model_t *model, cm_polygon_t *p1, cm_polygon_t *p2 );
 418         bool                    MergePolygonWithTreePolygons( cm_model_t *model, cm_node_t *node, cm_polygon_t *polygon );
 419         void                    MergeTreePolygons( cm_model_t *model, cm_node_t *node );
 420                                         // finding internal edges
 421         bool                    PointInsidePolygon( cm_model_t *model, cm_polygon_t *p, idVec3 &v );
 422         void                    FindInternalEdgesOnPolygon( cm_model_t *model, cm_polygon_t *p1, cm_polygon_t *p2 );
 423         void                    FindInternalPolygonEdges( cm_model_t *model, cm_node_t *node, cm_polygon_t *polygon );
 424         void                    FindInternalEdges( cm_model_t *model, cm_node_t *node );
 425         void                    FindContainedEdges( cm_model_t *model, cm_polygon_t *p );
 426                                         // loading of proc BSP tree
 427         void                    ParseProcNodes( idLexer *src );
 428         void                    LoadProcBSP( const char *name );
 429                                         // removal of contained polygons
 430         int                             R_ChoppedAwayByProcBSP( int nodeNum, idFixedWinding *w, const idVec3 &normal, const idVec3 &origin, const float radius );
 431         int                             ChoppedAwayByProcBSP( const idFixedWinding &w, const idPlane &plane, int contents );
 432         void                    ChopWindingListWithBrush( cm_windingList_t *list, cm_brush_t *b );
 433         void                    R_ChopWindingListWithTreeBrushes( cm_windingList_t *list, cm_node_t *node );
 434         idFixedWinding *WindingOutsideBrushes( idFixedWinding *w, const idPlane &plane, int contents, int patch, cm_node_t *headNode );
 435                                         // creation of axial BSP tree
 436         cm_model_t *    AllocModel( void );
 437         cm_node_t *             AllocNode( cm_model_t *model, int blockSize );
 438         cm_polygonRef_t*AllocPolygonReference( cm_model_t *model, int blockSize );
 439         cm_brushRef_t * AllocBrushReference( cm_model_t *model, int blockSize );
 440         cm_polygon_t *  AllocPolygon( cm_model_t *model, int numEdges );
 441         cm_brush_t *    AllocBrush( cm_model_t *model, int numPlanes );
 442         void                    AddPolygonToNode( cm_model_t *model, cm_node_t *node, cm_polygon_t *p );
 443         void                    AddBrushToNode( cm_model_t *model, cm_node_t *node, cm_brush_t *b );
 444         void                    SetupTrmModelStructure( void );
 445         void                    R_FilterPolygonIntoTree( cm_model_t *model, cm_node_t *node, cm_polygonRef_t *pref, cm_polygon_t *p );
 446         void                    R_FilterBrushIntoTree( cm_model_t *model, cm_node_t *node, cm_brushRef_t *pref, cm_brush_t *b );
 447         cm_node_t *             R_CreateAxialBSPTree( cm_model_t *model, cm_node_t *node, const idBounds &bounds );
 448         cm_node_t *             CreateAxialBSPTree( cm_model_t *model, cm_node_t *node );
 449                                         // creation of raw polygons
 450         void                    SetupHash(void);
 451         void                    ShutdownHash(void);
 452         void                    ClearHash( idBounds &bounds );
 453         int                             HashVec(const idVec3 &vec);
 454         int                             GetVertex( cm_model_t *model, const idVec3 &v, int *vertexNum );
 455         int                             GetEdge( cm_model_t *model, const idVec3 &v1, const idVec3 &v2, int *edgeNum, int v1num );
 456         void                    CreatePolygon( cm_model_t *model, idFixedWinding *w, const idPlane &plane, const idMaterial *material, int primitiveNum );
 457         void                    PolygonFromWinding( cm_model_t *model, idFixedWinding *w, const idPlane &plane, const idMaterial *material, int primitiveNum );
 458         void                    CalculateEdgeNormals( cm_model_t *model, cm_node_t *node );
 459         void                    CreatePatchPolygons( cm_model_t *model, idSurface_Patch &mesh, const idMaterial *material, int primitiveNum );
 460         void                    ConvertPatch( cm_model_t *model, const idMapPatch *patch, int primitiveNum );
 461         void                    ConvertBrushSides( cm_model_t *model, const idMapBrush *mapBrush, int primitiveNum );
 462         void                    ConvertBrush( cm_model_t *model, const idMapBrush *mapBrush, int primitiveNum );
 463         void                    PrintModelInfo( const cm_model_t *model );
 464         void                    AccumulateModelInfo( cm_model_t *model );
 465         void                    RemapEdges( cm_node_t *node, int *edgeRemap );
 466         void                    OptimizeArrays( cm_model_t *model );
 467         void                    FinishModel( cm_model_t *model );
 468         void                    BuildModels( const idMapFile *mapFile );
 469         cmHandle_t              FindModel( const char *name );
 470         cm_model_t *    CollisionModelForMapEntity( const idMapEntity *mapEnt );        // brush/patch model from .map
 471         cm_model_t *    LoadRenderModel( const char *fileName );                                        // ASE/LWO models
 472         bool                    TrmFromModel_r( idTraceModel &trm, cm_node_t *node );
 473         bool                    TrmFromModel( const cm_model_t *model, idTraceModel &trm );
 474
 475 private:                        // CollisionMap_files.cpp
 476                                         // writing
 477         void                    WriteNodes( idFile *fp, cm_node_t *node );
 478         int                             CountPolygonMemory( cm_node_t *node ) const;
 479         void                    WritePolygons( idFile *fp, cm_node_t *node );
 480         int                             CountBrushMemory( cm_node_t *node ) const;
 481         void                    WriteBrushes( idFile *fp, cm_node_t *node );
 482         void                    WriteCollisionModel( idFile *fp, cm_model_t *model );
 483         void                    WriteCollisionModelsToFile( const char *filename, int firstModel, int lastModel, unsigned int mapFileCRC );
 484                                         // loading
 485         cm_node_t *             ParseNodes( idLexer *src, cm_model_t *model, cm_node_t *parent );
 486         void                    ParseVertices( idLexer *src, cm_model_t *model );
 487         void                    ParseEdges( idLexer *src, cm_model_t *model );
 488         void                    ParsePolygons( idLexer *src, cm_model_t *model );
 489         void                    ParseBrushes( idLexer *src, cm_model_t *model );
 490         bool                    ParseCollisionModel( idLexer *src );
 491         bool                    LoadCollisionModelFile( const char *name, unsigned int mapFileCRC );
 492
 493 private:                        // CollisionMap_debug
 494         int                             ContentsFromString( const char *string ) const;
 495         const char *    StringFromContents( const int contents ) const;
 496         void                    DrawEdge( cm_model_t *model, int edgeNum, const idVec3 &origin, const idMat3 &axis );
 497         void                    DrawPolygon( cm_model_t *model, cm_polygon_t *p, const idVec3 &origin, const idMat3 &axis,
 498                                                                 const idVec3 &viewOrigin );
 499         void                    DrawNodePolygons( cm_model_t *model, cm_node_t *node, const idVec3 &origin, const idMat3 &axis,
 500                                                                 const idVec3 &viewOrigin, const float radius );
 501
 502 private:                        // collision map data
 503         idStr                   mapName;
 504         ID_TIME_T                       mapFileTime;
 505         int                             loaded;
 506                                         // for multi-check avoidance
 507         int                             checkCount;
 508                                         // models
 509         int                             maxModels;
 510         int                             numModels;
 511         cm_model_t **   models;
 512                                         // polygons and brush for trm model
 513         cm_polygonRef_t*trmPolygons[MAX_TRACEMODEL_POLYS];
 514         cm_brushRef_t * trmBrushes[1];
 515         const idMaterial *trmMaterial;
 516                                         // for data pruning
 517         int                             numProcNodes;
 518         cm_procNode_t * procNodes;
 519                                         // for retrieving contact points
 520         bool                    getContacts;
 521         contactInfo_t * contacts;
 522         int                             maxContacts;
 523         int                             numContacts;
 524 };
 525
 526 // for debugging
 527 extern idCVar cm_debugCollision;