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