2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
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.
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.
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/>.
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.
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.
26 ===========================================================================
30 ===============================================================================
32 Trace model vs. polygonal model collision detection.
34 ===============================================================================
37 #include "../idlib/precompiled.h"
40 #include "CollisionModel_local.h"
42 #define CM_FILE_EXT "cm"
43 #define CM_FILEID "CM"
44 #define CM_FILEVERSION "1.00"
48 ===============================================================================
50 Writing of collision model file
52 ===============================================================================
55 void CM_GetNodeBounds( idBounds *bounds, cm_node_t *node );
56 int CM_GetNodeContents( cm_node_t *node );
61 idCollisionModelManagerLocal::WriteNodes
64 void idCollisionModelManagerLocal::WriteNodes( idFile *fp, cm_node_t *node ) {
65 fp->WriteFloatString( "\t( %d %f )\n", node->planeType, node->planeDist );
66 if ( node->planeType != -1 ) {
67 WriteNodes( fp, node->children[0] );
68 WriteNodes( fp, node->children[1] );
74 idCollisionModelManagerLocal::CountPolygonMemory
77 int idCollisionModelManagerLocal::CountPolygonMemory( cm_node_t *node ) const {
78 cm_polygonRef_t *pref;
83 for ( pref = node->polygons; pref; pref = pref->next ) {
85 if ( p->checkcount == checkCount ) {
88 p->checkcount = checkCount;
90 memory += sizeof( cm_polygon_t ) + ( p->numEdges - 1 ) * sizeof( p->edges[0] );
92 if ( node->planeType != -1 ) {
93 memory += CountPolygonMemory( node->children[0] );
94 memory += CountPolygonMemory( node->children[1] );
101 idCollisionModelManagerLocal::WritePolygons
104 void idCollisionModelManagerLocal::WritePolygons( idFile *fp, cm_node_t *node ) {
105 cm_polygonRef_t *pref;
109 for ( pref = node->polygons; pref; pref = pref->next ) {
111 if ( p->checkcount == checkCount ) {
114 p->checkcount = checkCount;
115 fp->WriteFloatString( "\t%d (", p->numEdges );
116 for ( i = 0; i < p->numEdges; i++ ) {
117 fp->WriteFloatString( " %d", p->edges[i] );
119 fp->WriteFloatString( " ) ( %f %f %f ) %f", p->plane.Normal()[0], p->plane.Normal()[1], p->plane.Normal()[2], p->plane.Dist() );
120 fp->WriteFloatString( " ( %f %f %f )", p->bounds[0][0], p->bounds[0][1], p->bounds[0][2] );
121 fp->WriteFloatString( " ( %f %f %f )", p->bounds[1][0], p->bounds[1][1], p->bounds[1][2] );
122 fp->WriteFloatString( " \"%s\"\n", p->material->GetName() );
124 if ( node->planeType != -1 ) {
125 WritePolygons( fp, node->children[0] );
126 WritePolygons( fp, node->children[1] );
132 idCollisionModelManagerLocal::CountBrushMemory
135 int idCollisionModelManagerLocal::CountBrushMemory( cm_node_t *node ) const {
141 for ( bref = node->brushes; bref; bref = bref->next ) {
143 if ( b->checkcount == checkCount ) {
146 b->checkcount = checkCount;
148 memory += sizeof( cm_brush_t ) + ( b->numPlanes - 1 ) * sizeof( b->planes[0] );
150 if ( node->planeType != -1 ) {
151 memory += CountBrushMemory( node->children[0] );
152 memory += CountBrushMemory( node->children[1] );
159 idCollisionModelManagerLocal::WriteBrushes
162 void idCollisionModelManagerLocal::WriteBrushes( idFile *fp, cm_node_t *node ) {
167 for ( bref = node->brushes; bref; bref = bref->next ) {
169 if ( b->checkcount == checkCount ) {
172 b->checkcount = checkCount;
173 fp->WriteFloatString( "\t%d {\n", b->numPlanes );
174 for ( i = 0; i < b->numPlanes; i++ ) {
175 fp->WriteFloatString( "\t\t( %f %f %f ) %f\n", b->planes[i].Normal()[0], b->planes[i].Normal()[1], b->planes[i].Normal()[2], b->planes[i].Dist() );
177 fp->WriteFloatString( "\t} ( %f %f %f )", b->bounds[0][0], b->bounds[0][1], b->bounds[0][2] );
178 fp->WriteFloatString( " ( %f %f %f ) \"%s\"\n", b->bounds[1][0], b->bounds[1][1], b->bounds[1][2], StringFromContents( b->contents ) );
180 if ( node->planeType != -1 ) {
181 WriteBrushes( fp, node->children[0] );
182 WriteBrushes( fp, node->children[1] );
188 idCollisionModelManagerLocal::WriteCollisionModel
191 void idCollisionModelManagerLocal::WriteCollisionModel( idFile *fp, cm_model_t *model ) {
192 int i, polygonMemory, brushMemory;
194 fp->WriteFloatString( "collisionModel \"%s\" {\n", model->name.c_str() );
196 fp->WriteFloatString( "\tvertices { /* numVertices = */ %d\n", model->numVertices );
197 for ( i = 0; i < model->numVertices; i++ ) {
198 fp->WriteFloatString( "\t/* %d */ ( %f %f %f )\n", i, model->vertices[i].p[0], model->vertices[i].p[1], model->vertices[i].p[2] );
200 fp->WriteFloatString( "\t}\n" );
202 fp->WriteFloatString( "\tedges { /* numEdges = */ %d\n", model->numEdges );
203 for ( i = 0; i < model->numEdges; i++ ) {
204 fp->WriteFloatString( "\t/* %d */ ( %d %d ) %d %d\n", i, model->edges[i].vertexNum[0], model->edges[i].vertexNum[1], model->edges[i].internal, model->edges[i].numUsers );
206 fp->WriteFloatString( "\t}\n" );
208 fp->WriteFloatString( "\tnodes {\n" );
209 WriteNodes( fp, model->node );
210 fp->WriteFloatString( "\t}\n" );
213 polygonMemory = CountPolygonMemory( model->node );
214 fp->WriteFloatString( "\tpolygons /* polygonMemory = */ %d {\n", polygonMemory );
216 WritePolygons( fp, model->node );
217 fp->WriteFloatString( "\t}\n" );
220 brushMemory = CountBrushMemory( model->node );
221 fp->WriteFloatString( "\tbrushes /* brushMemory = */ %d {\n", brushMemory );
223 WriteBrushes( fp, model->node );
224 fp->WriteFloatString( "\t}\n" );
226 fp->WriteFloatString( "}\n" );
231 idCollisionModelManagerLocal::WriteCollisionModelsToFile
234 void idCollisionModelManagerLocal::WriteCollisionModelsToFile( const char *filename, int firstModel, int lastModel, unsigned int mapFileCRC ) {
240 name.SetFileExtension( CM_FILE_EXT );
242 common->Printf( "writing %s\n", name.c_str() );
243 // _D3XP was saving to fs_cdpath
244 fp = fileSystem->OpenFileWrite( name, "fs_devpath" );
246 common->Warning( "idCollisionModelManagerLocal::WriteCollisionModelsToFile: Error opening file %s\n", name.c_str() );
250 // write file id and version
251 fp->WriteFloatString( "%s \"%s\"\n\n", CM_FILEID, CM_FILEVERSION );
252 // write the map file crc
253 fp->WriteFloatString( "%u\n\n", mapFileCRC );
255 // write the collision models
256 for ( i = firstModel; i < lastModel; i++ ) {
257 WriteCollisionModel( fp, models[ i ] );
260 fileSystem->CloseFile( fp );
265 idCollisionModelManagerLocal::WriteCollisionModelForMapEntity
268 bool idCollisionModelManagerLocal::WriteCollisionModelForMapEntity( const idMapEntity *mapEnt, const char *filename, const bool testTraceModel ) {
274 model = CollisionModelForMapEntity( mapEnt );
275 model->name = filename;
278 name.SetFileExtension( CM_FILE_EXT );
280 common->Printf( "writing %s\n", name.c_str() );
281 fp = fileSystem->OpenFileWrite( name, "fs_devpath" );
283 common->Printf( "idCollisionModelManagerLocal::WriteCollisionModelForMapEntity: Error opening file %s\n", name.c_str() );
288 // write file id and version
289 fp->WriteFloatString( "%s \"%s\"\n\n", CM_FILEID, CM_FILEVERSION );
290 // write the map file crc
291 fp->WriteFloatString( "%u\n\n", 0 );
293 // write the collision model
294 WriteCollisionModel( fp, model );
296 fileSystem->CloseFile( fp );
298 if ( testTraceModel ) {
300 TrmFromModel( model, trm );
310 ===============================================================================
312 Loading of collision model file
314 ===============================================================================
319 idCollisionModelManagerLocal::ParseVertices
322 void idCollisionModelManagerLocal::ParseVertices( idLexer *src, cm_model_t *model ) {
325 src->ExpectTokenString( "{" );
326 model->numVertices = src->ParseInt();
327 model->maxVertices = model->numVertices;
328 model->vertices = (cm_vertex_t *) Mem_Alloc( model->maxVertices * sizeof( cm_vertex_t ) );
329 for ( i = 0; i < model->numVertices; i++ ) {
330 src->Parse1DMatrix( 3, model->vertices[i].p.ToFloatPtr() );
331 model->vertices[i].side = 0;
332 model->vertices[i].sideSet = 0;
333 model->vertices[i].checkcount = 0;
335 src->ExpectTokenString( "}" );
340 idCollisionModelManagerLocal::ParseEdges
343 void idCollisionModelManagerLocal::ParseEdges( idLexer *src, cm_model_t *model ) {
346 src->ExpectTokenString( "{" );
347 model->numEdges = src->ParseInt();
348 model->maxEdges = model->numEdges;
349 model->edges = (cm_edge_t *) Mem_Alloc( model->maxEdges * sizeof( cm_edge_t ) );
350 for ( i = 0; i < model->numEdges; i++ ) {
351 src->ExpectTokenString( "(" );
352 model->edges[i].vertexNum[0] = src->ParseInt();
353 model->edges[i].vertexNum[1] = src->ParseInt();
354 src->ExpectTokenString( ")" );
355 model->edges[i].side = 0;
356 model->edges[i].sideSet = 0;
357 model->edges[i].internal = src->ParseInt();
358 model->edges[i].numUsers = src->ParseInt();
359 model->edges[i].normal = vec3_origin;
360 model->edges[i].checkcount = 0;
361 model->numInternalEdges += model->edges[i].internal;
363 src->ExpectTokenString( "}" );
368 idCollisionModelManagerLocal::ParseNodes
371 cm_node_t *idCollisionModelManagerLocal::ParseNodes( idLexer *src, cm_model_t *model, cm_node_t *parent ) {
375 node = AllocNode( model, model->numNodes < NODE_BLOCK_SIZE_SMALL ? NODE_BLOCK_SIZE_SMALL : NODE_BLOCK_SIZE_LARGE );
376 node->brushes = NULL;
377 node->polygons = NULL;
378 node->parent = parent;
379 src->ExpectTokenString( "(" );
380 node->planeType = src->ParseInt();
381 node->planeDist = src->ParseFloat();
382 src->ExpectTokenString( ")" );
383 if ( node->planeType != -1 ) {
384 node->children[0] = ParseNodes( src, model, node );
385 node->children[1] = ParseNodes( src, model, node );
392 idCollisionModelManagerLocal::ParsePolygons
395 void idCollisionModelManagerLocal::ParsePolygons( idLexer *src, cm_model_t *model ) {
401 if ( src->CheckTokenType( TT_NUMBER, 0, &token ) ) {
402 model->polygonBlock = (cm_polygonBlock_t *) Mem_Alloc( sizeof( cm_polygonBlock_t ) + token.GetIntValue() );
403 model->polygonBlock->bytesRemaining = token.GetIntValue();
404 model->polygonBlock->next = ( (byte *) model->polygonBlock ) + sizeof( cm_polygonBlock_t );
407 src->ExpectTokenString( "{" );
408 while ( !src->CheckTokenString( "}" ) ) {
410 numEdges = src->ParseInt();
411 p = AllocPolygon( model, numEdges );
412 p->numEdges = numEdges;
413 src->ExpectTokenString( "(" );
414 for ( i = 0; i < p->numEdges; i++ ) {
415 p->edges[i] = src->ParseInt();
417 src->ExpectTokenString( ")" );
418 src->Parse1DMatrix( 3, normal.ToFloatPtr() );
419 p->plane.SetNormal( normal );
420 p->plane.SetDist( src->ParseFloat() );
421 src->Parse1DMatrix( 3, p->bounds[0].ToFloatPtr() );
422 src->Parse1DMatrix( 3, p->bounds[1].ToFloatPtr() );
423 src->ExpectTokenType( TT_STRING, 0, &token );
425 p->material = declManager->FindMaterial( token );
426 p->contents = p->material->GetContentFlags();
428 // filter polygon into tree
429 R_FilterPolygonIntoTree( model, model->node, NULL, p );
435 idCollisionModelManagerLocal::ParseBrushes
438 void idCollisionModelManagerLocal::ParseBrushes( idLexer *src, cm_model_t *model ) {
444 if ( src->CheckTokenType( TT_NUMBER, 0, &token ) ) {
445 model->brushBlock = (cm_brushBlock_t *) Mem_Alloc( sizeof( cm_brushBlock_t ) + token.GetIntValue() );
446 model->brushBlock->bytesRemaining = token.GetIntValue();
447 model->brushBlock->next = ( (byte *) model->brushBlock ) + sizeof( cm_brushBlock_t );
450 src->ExpectTokenString( "{" );
451 while ( !src->CheckTokenString( "}" ) ) {
453 numPlanes = src->ParseInt();
454 b = AllocBrush( model, numPlanes );
455 b->numPlanes = numPlanes;
456 src->ExpectTokenString( "{" );
457 for ( i = 0; i < b->numPlanes; i++ ) {
458 src->Parse1DMatrix( 3, normal.ToFloatPtr() );
459 b->planes[i].SetNormal( normal );
460 b->planes[i].SetDist( src->ParseFloat() );
462 src->ExpectTokenString( "}" );
463 src->Parse1DMatrix( 3, b->bounds[0].ToFloatPtr() );
464 src->Parse1DMatrix( 3, b->bounds[1].ToFloatPtr() );
465 src->ReadToken( &token );
466 if ( token.type == TT_NUMBER ) {
467 b->contents = token.GetIntValue(); // old .cm files use a single integer
469 b->contents = ContentsFromString( token );
473 // filter brush into tree
474 R_FilterBrushIntoTree( model, model->node, NULL, b );
480 idCollisionModelManagerLocal::ParseCollisionModel
483 bool idCollisionModelManagerLocal::ParseCollisionModel( idLexer *src ) {
487 if ( numModels >= MAX_SUBMODELS ) {
488 common->Error( "LoadModel: no free slots" );
491 model = AllocModel();
492 models[numModels ] = model;
495 src->ExpectTokenType( TT_STRING, 0, &token );
497 src->ExpectTokenString( "{" );
498 while ( !src->CheckTokenString( "}" ) ) {
500 src->ReadToken( &token );
502 if ( token == "vertices" ) {
503 ParseVertices( src, model );
507 if ( token == "edges" ) {
508 ParseEdges( src, model );
512 if ( token == "nodes" ) {
513 src->ExpectTokenString( "{" );
514 model->node = ParseNodes( src, model, NULL );
515 src->ExpectTokenString( "}" );
519 if ( token == "polygons" ) {
520 ParsePolygons( src, model );
524 if ( token == "brushes" ) {
525 ParseBrushes( src, model );
529 src->Error( "ParseCollisionModel: bad token \"%s\"", token.c_str() );
531 // calculate edge normals
533 CalculateEdgeNormals( model, model->node );
534 // get model bounds from brush and polygon bounds
535 CM_GetNodeBounds( &model->bounds, model->node );
536 // get model contents
537 model->contents = CM_GetNodeContents( model->node );
538 // total memory used by this model
539 model->usedMemory = model->numVertices * sizeof(cm_vertex_t) +
540 model->numEdges * sizeof(cm_edge_t) +
541 model->polygonMemory +
543 model->numNodes * sizeof(cm_node_t) +
544 model->numPolygonRefs * sizeof(cm_polygonRef_t) +
545 model->numBrushRefs * sizeof(cm_brushRef_t);
552 idCollisionModelManagerLocal::LoadCollisionModelFile
555 bool idCollisionModelManagerLocal::LoadCollisionModelFile( const char *name, unsigned int mapFileCRC ) {
563 fileName.SetFileExtension( CM_FILE_EXT );
564 src = new idLexer( fileName );
565 src->SetFlags( LEXFL_NOSTRINGCONCAT | LEXFL_NODOLLARPRECOMPILE );
566 if ( !src->IsLoaded() ) {
571 if ( !src->ExpectTokenString( CM_FILEID ) ) {
572 common->Warning( "%s is not an CM file.", fileName.c_str() );
577 if ( !src->ReadToken( &token ) || token != CM_FILEVERSION ) {
578 common->Warning( "%s has version %s instead of %s", fileName.c_str(), token.c_str(), CM_FILEVERSION );
583 if ( !src->ExpectTokenType( TT_NUMBER, TT_INTEGER, &token ) ) {
584 common->Warning( "%s has no map file CRC", fileName.c_str() );
589 crc = token.GetUnsignedLongValue();
590 if ( mapFileCRC && crc != mapFileCRC ) {
591 common->Printf( "%s is out of date\n", fileName.c_str() );
598 if ( !src->ReadToken( &token ) ) {
602 if ( token == "collisionModel" ) {
603 if ( !ParseCollisionModel( src ) ) {
610 src->Error( "idCollisionModelManagerLocal::LoadCollisionModelFile: bad token \"%s\"", token.c_str() );