1 /*
2 Copyright (C) 1997-2001 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18
19 */
20 // cmodel.c -- model loading
21
22 #include "qcommon.h"
23
24 #define CM_Malloc( size ) Z_TagMalloc( size, TAG_CMODEL )
25 #define CM_Mallocz( size ) Z_TagMallocz( size, TAG_CMODEL )
26 #define CM_Free( ptr ) Z_Free( ptr )
27
28 static mapsurface_t nullsurface;
29 static cleaf_t nullleaf;
30
31 static int floodvalid;
32 static int checkcount;
33
34 static cvar_t *map_noareas;
35 static cvar_t *map_load_entities;
36
37 void CM_FloodAreaConnections( cm_t *cm );
38
39 /*
40 ===============================================================================
41
42 MAP LOADING
43
44 ===============================================================================
45 */
46
47 static byte *cmod_base;
48 static cmcache_t *cmod;
49
50 /*
51 =================
52 CMod_LoadSubmodels
53 =================
54 */
CMod_LoadSubmodels(lump_t * l)55 static void CMod_LoadSubmodels (lump_t *l)
56 {
57 dmodel_t *in;
58 cmodel_t *out;
59 int i, j, count;
60 uint32 headnode;
61
62 in = (void *)(cmod_base + l->fileofs);
63 if (l->filelen % sizeof(*in))
64 Com_Error (ERR_DROP, "CMod_LoadSubmodels: funny lump size");
65 count = l->filelen / sizeof(*in);
66
67 if (count < 1)
68 Com_Error (ERR_DROP, "Map with no models");
69 if (count > MAX_MAP_MODELS)
70 Com_Error (ERR_DROP, "Map has too many models");
71
72 cmod->cmodels = CM_Malloc( sizeof( *out ) * count );
73 cmod->numcmodels = count;
74
75 out = cmod->cmodels;
76 for ( i=0 ; i<count ; i++, in++, out++)
77 {
78 for (j=0 ; j<3 ; j++)
79 { // spread the mins / maxs by a pixel
80 out->mins[j] = LittleFloat (in->mins[j]) - 1;
81 out->maxs[j] = LittleFloat (in->maxs[j]) + 1;
82 out->origin[j] = LittleFloat (in->origin[j]);
83 }
84 headnode = LittleLong (in->headnode);
85 if( headnode >= cmod->numnodes ) {
86 // FIXME: headnode may be garbage for some models
87 Com_DPrintf( "CMod_LoadSubmodels: bad headnode for model %d\n", i );
88 out->headnode = NULL;
89 } else {
90 out->headnode = cmod->nodes + headnode;
91 }
92 }
93 }
94
95
96 /*
97 =================
98 CMod_LoadSurfaces
99 =================
100 */
CMod_LoadSurfaces(lump_t * l)101 static void CMod_LoadSurfaces (lump_t *l)
102 {
103 texinfo_t *in;
104 mapsurface_t *out;
105 int i, count;
106
107 in = (void *)(cmod_base + l->fileofs);
108 if (l->filelen % sizeof(*in))
109 Com_Error (ERR_DROP, "CMod_LoadSurfaces: funny lump size");
110 count = l->filelen / sizeof(*in);
111 if (count < 1)
112 Com_Error (ERR_DROP, "Map with no surfaces");
113 if (count > MAX_MAP_TEXINFO)
114 Com_Error (ERR_DROP, "Map has too many surfaces");
115
116 cmod->numtexinfo = count;
117 cmod->surfaces = CM_Malloc( sizeof( *out ) * count );
118
119 out = cmod->surfaces;
120 for ( i=0 ; i<count ; i++, in++, out++)
121 {
122 Q_strncpyz (out->c.name, in->texture, sizeof(out->c.name));
123 Q_strncpyz (out->rname, in->texture, sizeof(out->rname));
124 out->c.flags = LittleLong (in->flags);
125 out->c.value = LittleLong (in->value);
126 }
127 }
128
129
130 /*
131 =================
132 CMod_LoadNodes
133
134 =================
135 */
CMod_LoadNodes(lump_t * l)136 static void CMod_LoadNodes (lump_t *l)
137 {
138 dnode_t *in;
139 uint32 child;
140 cnode_t *out;
141 int i, j, count;
142 uint32 planeNum;
143
144 in = (void *)(cmod_base + l->fileofs);
145 if (l->filelen % sizeof(*in))
146 Com_Error (ERR_DROP, "CMod_LoadNodes: funny lump size");
147 count = l->filelen / sizeof(*in);
148
149 if (count < 1)
150 Com_Error (ERR_DROP, "Map has no nodes");
151 if (count > MAX_MAP_NODES)
152 Com_Error (ERR_DROP, "Map has too many nodes");
153
154 cmod->numnodes = count;
155 cmod->nodes = CM_Malloc( sizeof( *out ) * count );
156
157 out = cmod->nodes;
158 for (i=0 ; i<count ; i++, out++, in++)
159 {
160 planeNum = LittleLong(in->planenum);
161 if( planeNum >= cmod->numplanes ) {
162 Com_Error (ERR_DROP, "CMod_LoadNodes: bad planenum");
163 }
164 out->plane = cmod->planes + planeNum;
165
166 for( j = 0; j < 2; j++ ) {
167 child = LittleLong( in->children[j] );
168 if( child & 0x80000000 ) {
169 child = ~child;
170 if( child >= cmod->numleafs ) {
171 Com_Error( ERR_DROP, "CMod_LoadNodes: bad leafnum" );
172 }
173 out->children[j] = ( cnode_t * )( cmod->leafs + child );
174 } else {
175 if( child >= count ) {
176 Com_Error ( ERR_DROP, "CMod_LoadNodes: bad nodenum" );
177 }
178 out->children[j] = cmod->nodes + child;
179 }
180 }
181 }
182
183 }
184
185 /*
186 =================
187 CMod_LoadBrushes
188
189 =================
190 */
CMod_LoadBrushes(lump_t * l)191 static void CMod_LoadBrushes (lump_t *l)
192 {
193 dbrush_t *in;
194 cbrush_t *out;
195 int i, count;
196 uint32 firstSide, numSides;
197
198 in = (void *)(cmod_base + l->fileofs);
199 if (l->filelen % sizeof(*in))
200 Com_Error (ERR_DROP, "CMod_LoadBrushes: funny lump size");
201 count = l->filelen / sizeof(*in);
202
203 if (count > MAX_MAP_BRUSHES)
204 Com_Error (ERR_DROP, "Map has too many brushes");
205
206 cmod->numbrushes = count;
207 cmod->brushes = CM_Malloc( sizeof( *out ) * count );
208
209 out = cmod->brushes;
210 for (i=0 ; i<count ; i++, out++, in++)
211 {
212 firstSide = LittleLong(in->firstside);
213 numSides = LittleLong(in->numsides);
214 if( firstSide + numSides > cmod->numbrushsides ) {
215 Com_Error (ERR_DROP, "CMod_LoadBrushes: bad brushsides");
216 }
217 out->firstbrushside = cmod->brushsides + firstSide;
218 out->numsides = numSides;
219 out->contents = LittleLong(in->contents);
220 out->checkcount = 0;
221 }
222
223 }
224
225 /*
226 =================
227 CMod_LoadLeafs
228 =================
229 */
CMod_LoadLeafs(lump_t * l)230 static void CMod_LoadLeafs (lump_t *l)
231 {
232 int i;
233 cleaf_t *out;
234 dleaf_t *in;
235 int count;
236 uint16 areaNum, firstBrush, numBrushes;
237
238 in = (void *)(cmod_base + l->fileofs);
239 if (l->filelen % sizeof(*in))
240 Com_Error (ERR_DROP, "CMod_LoadLeafs: funny lump size");
241 count = l->filelen / sizeof(*in);
242
243 if (count < 1)
244 Com_Error (ERR_DROP, "Map with no leafs");
245 // need to save space for box planes
246 if (count > MAX_MAP_LEAFS)
247 Com_Error (ERR_DROP, "Map has too many leafs");
248
249 cmod->numleafs = count;
250 cmod->numclusters = 0;
251 cmod->leafs = CM_Malloc( sizeof( *out ) * count );
252
253 out = cmod->leafs;
254 for ( i=0 ; i<count ; i++, in++, out++)
255 {
256 out->plane = NULL;
257 out->contents = LittleLong (in->contents);
258 out->cluster = ( signed short )LittleShort (in->cluster);
259 areaNum = LittleShort (in->area);
260 if( areaNum >= cmod->numareas ) {
261 Com_Error (ERR_DROP, "CMod_LoadLeafs: bad areanum");
262 }
263 out->area = areaNum;
264
265 firstBrush = LittleShort (in->firstleafbrush);
266 numBrushes = LittleShort (in->numleafbrushes);
267 if( firstBrush + numBrushes > cmod->numleafbrushes ) {
268 Com_Error (ERR_DROP, "CMod_LoadLeafs: bad brushnum");
269 }
270
271 out->firstleafbrush = cmod->leafbrushes + firstBrush;
272 out->numleafbrushes = numBrushes;
273
274 if (out->cluster >= cmod->numclusters)
275 cmod->numclusters = out->cluster + 1;
276 }
277
278 if (cmod->leafs[0].contents != CONTENTS_SOLID)
279 Com_Error (ERR_DROP, "Map leaf 0 is not CONTENTS_SOLID");
280 }
281
282 /*
283 =================
284 CMod_LoadPlanes
285 =================
286 */
CMod_LoadPlanes(lump_t * l)287 static void CMod_LoadPlanes (lump_t *l)
288 {
289 int i;
290 cplane_t *out;
291 dplane_t *in;
292 int count;
293
294 in = (void *)(cmod_base + l->fileofs);
295 if (l->filelen % sizeof(*in))
296 Com_Error (ERR_DROP, "CMod_LoadPlanes: funny lump size");
297 count = l->filelen / sizeof(*in);
298
299 if (count < 1)
300 Com_Error (ERR_DROP, "Map with no planes");
301 if (count > MAX_MAP_PLANES)
302 Com_Error (ERR_DROP, "Map has too many planes");
303
304 cmod->numplanes = count;
305 cmod->planes = CM_Malloc( sizeof( *out ) * count );
306
307 out = cmod->planes;
308 for ( i=0 ; i<count ; i++, in++, out++)
309 {
310 out->normal[0] = LittleFloat( in->normal[0] );
311 out->normal[1] = LittleFloat( in->normal[1] );
312 out->normal[2] = LittleFloat( in->normal[2] );
313 out->dist = LittleFloat (in->dist);
314 //out->type = LittleLong (in->type);
315
316 SetPlaneType( out );
317 SetPlaneSignbits( out );
318 }
319 }
320
321 /*
322 =================
323 CMod_LoadLeafBrushes
324 =================
325 */
CMod_LoadLeafBrushes(lump_t * l)326 static void CMod_LoadLeafBrushes (lump_t *l)
327 {
328 int i;
329 cbrush_t **out;
330 uint16 *in;
331 int count;
332 uint16 brushNum;
333
334 in = (void *)(cmod_base + l->fileofs);
335 if (l->filelen % sizeof(*in))
336 Com_Error (ERR_DROP, "CMod_LoadLeafBrushes: funny lump size");
337 count = l->filelen / sizeof(*in);
338
339 if (count < 1)
340 Com_Error (ERR_DROP, "Map with no leafbrushes");
341 if (count > MAX_MAP_LEAFBRUSHES)
342 Com_Error (ERR_DROP, "Map has too many leafbrushes");
343
344 cmod->numleafbrushes = count;
345 cmod->leafbrushes = CM_Malloc( sizeof( *out ) * count );
346
347 out = cmod->leafbrushes;
348 for ( i=0 ; i<count ; i++, in++, out++) {
349 brushNum = LittleShort (*in);
350 if( brushNum >= cmod->numbrushes ) {
351 Com_Error (ERR_DROP, "CMod_LoadLeafBrushes: bad brushnum");
352 }
353 *out = cmod->brushes + brushNum;
354 }
355 }
356
357 /*
358 =================
359 CMod_LoadBrushSides
360 =================
361 */
CMod_LoadBrushSides(lump_t * l)362 static void CMod_LoadBrushSides (lump_t *l)
363 {
364 int i;
365 cbrushside_t *out;
366 dbrushside_t *in;
367 int count;
368 uint32 planeNum;
369 uint16 texinfoNum;
370
371 in = (void *)(cmod_base + l->fileofs);
372 if (l->filelen % sizeof(*in))
373 Com_Error (ERR_DROP, "CMod_LoadBrushSides: funny lump size");
374 count = l->filelen / sizeof(*in);
375
376 if (count > MAX_MAP_BRUSHSIDES)
377 Com_Error (ERR_DROP, "Map has too many brush sides");
378
379 cmod->numbrushsides = count;
380 cmod->brushsides = CM_Malloc( sizeof( *out ) * count );
381
382 out = cmod->brushsides;
383 for ( i=0 ; i<count ; i++, in++, out++)
384 {
385 planeNum = LittleShort (in->planenum);
386 if( planeNum >= cmod->numplanes ) {
387 Com_Error (ERR_DROP, "CMod_LoadBrushSides: bad planenum");
388 }
389 out->plane = cmod->planes + planeNum;
390 texinfoNum = LittleShort (in->texinfo);
391 if( texinfoNum == (uint16)-1 ) {
392 out->surface = &nullsurface;
393 } else {
394 if (texinfoNum >= cmod->numtexinfo)
395 Com_Error (ERR_DROP, "CMod_LoadBrushSides: bad texinfo");
396 out->surface = cmod->surfaces + texinfoNum;
397 }
398 }
399 }
400
401 /*
402 =================
403 CMod_LoadAreas
404 =================
405 */
CMod_LoadAreas(lump_t * l)406 static void CMod_LoadAreas (lump_t *l)
407 {
408 int i;
409 carea_t *out;
410 darea_t *in;
411 int count;
412 uint32 numPortals, firstPortal;
413
414 in = (void *)(cmod_base + l->fileofs);
415 if (l->filelen % sizeof(*in))
416 Com_Error (ERR_DROP, "CMod_LoadAreas: funny lump size");
417 count = l->filelen / sizeof(*in);
418
419 if (count > MAX_MAP_AREAS)
420 Com_Error (ERR_DROP, "Map has too many areas");
421
422 cmod->numareas = count;
423 cmod->areas = CM_Malloc( sizeof( *out ) * count );
424
425 out = cmod->areas;
426 for ( i=0 ; i<count ; i++, in++, out++)
427 {
428 numPortals = LittleLong (in->numareaportals);
429 firstPortal = LittleLong (in->firstareaportal);
430 if( firstPortal + numPortals > cmod->numareaportals ) {
431 Com_Error (ERR_DROP, "CMod_LoadAreas: bad areaportals");
432 }
433 out->numareaportals = numPortals;
434 out->firstareaportal = firstPortal;
435 out->floodvalid = 0;
436 }
437 }
438
439 /*
440 =================
441 CMod_LoadAreaPortals
442 =================
443 */
CMod_LoadAreaPortals(lump_t * l)444 static void CMod_LoadAreaPortals (lump_t *l)
445 {
446 int i;
447 careaportal_t *out;
448 dareaportal_t *in;
449 int count;
450 uint32 portalNum, otherArea;
451
452 in = (void *)(cmod_base + l->fileofs);
453 if (l->filelen % sizeof(*in))
454 Com_Error (ERR_DROP, "CMod_LoadAreaPortals: funny lump size");
455 count = l->filelen / sizeof(*in);
456
457 if (count > MAX_MAP_AREAS)
458 Com_Error (ERR_DROP, "Map has too many areas");
459
460 cmod->numareaportals = count;
461 cmod->areaportals = CM_Malloc( sizeof( *out ) * count );
462
463 out = cmod->areaportals;
464 for ( i=0 ; i<count ; i++, in++, out++)
465 {
466 portalNum = LittleLong (in->portalnum);
467 if( portalNum >= MAX_MAP_AREAPORTALS ) {
468 Com_Error (ERR_DROP, "CMod_LoadAreaPortals: bad portalnum");
469 }
470 out->portalnum = portalNum;
471 otherArea = LittleLong (in->otherarea);
472 if( otherArea >= MAX_MAP_AREAS ) {
473 Com_Error (ERR_DROP, "CMod_LoadAreaPortals: bad otherarea");
474 }
475 out->otherarea = otherArea;
476 }
477 }
478
479 /*
480 =================
481 CMod_LoadVisibility
482 =================
483 */
CMod_LoadVisibility(lump_t * l)484 static void CMod_LoadVisibility( lump_t *l ) {
485 int i;
486 uint32 numClusters;
487
488 if( !l->filelen ) {
489 return;
490 }
491
492 if( l->filelen > MAX_MAP_VISIBILITY )
493 Com_Error (ERR_DROP, "Map has too large visibility lump");
494
495 cmod->numvisibility = l->filelen;
496 cmod->vis = CM_Malloc( l->filelen );
497 memcpy( cmod->vis, cmod_base + l->fileofs, l->filelen );
498
499 numClusters = LittleLong( cmod->vis->numclusters );
500 cmod->vis->numclusters = numClusters;
501 for( i = 0; i < numClusters; i++ ) {
502 cmod->vis->bitofs[i][0] = LittleLong( cmod->vis->bitofs[i][0] );
503 cmod->vis->bitofs[i][1] = LittleLong( cmod->vis->bitofs[i][1] );
504 }
505
506 cmod->visrowsize = ( numClusters + 7 ) >> 3;
507 }
508
509
510 /*
511 =================
512 CMod_LoadEntityString
513 =================
514 */
CMod_LoadEntityString(lump_t * l)515 static void CMod_LoadEntityString( lump_t *l ) {
516 if( l->filelen > MAX_MAP_ENTSTRING ) {
517 Com_Error( ERR_DROP, "Map has too large entity lump" );
518 }
519
520 cmod->numEntityChars = l->filelen;
521 cmod->entitystring = CM_Malloc( l->filelen + 1 );
522 memcpy( cmod->entitystring, cmod_base + l->fileofs, l->filelen );
523 cmod->entitystring[l->filelen] = 0;
524 }
525
526 #if 0
527 /*
528 ==================
529 CM_ConcatToEntityString
530 ==================
531 */
532 static void CM_ConcatToEntityString( const char *text ) {
533 int len;
534
535 len = strlen( text );
536 if( numEntityChars + len > sizeof( cmod->entitystring ) - 1 ) {
537 Com_Error( ERR_DROP, "CM_ConcatToEntityString: oversize entity lump" );
538 }
539
540 strcpy( cmod->entitystring + numEntityChars, text );
541 numEntityChars += len;
542 }
543
544 /*
545 ==================
546 CM_ParseMapFile
547
548 Parses complete *.map file
549 ==================
550 */
551 static qboolean CM_ParseMapFile( const char *data ) {
552 char *token;
553 int numInlineModels;
554 qboolean inlineModel;
555 char buffer[MAX_STRING_CHARS];
556 char key[MAX_TOKEN_CHARS];
557
558 numInlineModels = 0;
559
560 while( 1 ) {
561 token = COM_Parse( ( const char ** )&data );
562 if( !data ) {
563 break;
564 }
565
566 if( *token != '{' ) {
567 Com_WPrintf( "CM_ParseMapFile: expected '{', found '%s'\n", token );
568 return qfalse;
569 }
570
571 CM_ConcatToEntityString( "{ " );
572
573 inlineModel = qfalse;
574
575 // Parse entity
576 while( 1 ) {
577 token = COM_Parse( ( const char ** )&data );
578 if( !data ) {
579 Com_WPrintf( "CM_ParseMapFile: expected key, found EOF\n" );
580 return qfalse;
581 }
582
583 if( *token == '}' ) {
584 // FIXME HACK: restore inline model number
585 // This may not work properly if the entity order is different!!!
586 if( inlineModel && numInlineModels ) {
587 Com_sprintf( buffer, sizeof( buffer ), "\"model\" \"*%i\" } ", numInlineModels );
588 CM_ConcatToEntityString( buffer );
589 } else {
590 CM_ConcatToEntityString( "} " );
591 }
592
593 if( inlineModel ) {
594 numInlineModels++;
595 }
596
597 break;
598 }
599
600 if( *token == '{' ) {
601 inlineModel = qtrue;
602
603 // Parse brush
604 while( 1 ) {
605 token = COM_Parse( ( const char ** )&data );
606 if( !data ) {
607 Com_WPrintf( "CM_ParseMapFile: expected brush data, found EOF\n" );
608 return qfalse;
609 }
610
611 if( *token == '}' ) {
612 break;
613 }
614
615 if( *token == '{' ) {
616 Com_WPrintf( "CM_ParseMapFile: expected brush data, found '{'\n" );
617 return qfalse;
618 }
619
620 }
621
622 continue;
623 }
624
625 Q_strncpyz( key, token, sizeof( key ) );
626
627 token = COM_Parse( ( const char ** )&data );
628 if( !data ) {
629 Com_WPrintf( "CM_ParseMapFile: expected value, found EOF\n" );
630 return qfalse;
631 }
632
633 if( *token == '}' || *token == '{' ) {
634 Com_WPrintf( "CM_ParseMapFile: expected value, found '%s'\n", token );
635 return qfalse;
636 }
637
638 Com_sprintf( buffer, sizeof( buffer ), "\"%s\" \"%s\" ", key, token );
639
640 CM_ConcatToEntityString( buffer );
641
642 }
643 }
644
645 cmod->entitystring[numEntityChars] = 0;
646
647 if( numInlineModels != numcmodels + 1 ) {
648 Com_WPrintf( "CM_ParseMapFile: mismatched number of inline models\n" );
649 return qfalse;
650 }
651
652 return qtrue;
653 }
654 #endif
655
656 #define CM_CACHESIZE 16
657
658 static cmcache_t cm_cache[CM_CACHESIZE];
659
CM_FreeMap(cm_t * cm)660 void CM_FreeMap( cm_t *cm ) {
661 cmcache_t *cache;
662
663 if( cm->floodnums ) {
664 Z_Free( cm->floodnums );
665 }
666
667 cache = cm->cache;
668 if( cache ) {
669 if( cache->refcount <= 0 ) {
670 Com_Error( ERR_FATAL, "CM_FreeMap: negative refcount" );
671 }
672 if( --cache->refcount == 0 ) {
673
674 #define CM_FREE( f ) \
675 do { \
676 if( cache->f ) { \
677 CM_Free( cache->f ); \
678 } \
679 } while( 0 )
680
681 CM_FREE( vis );
682 CM_FREE( surfaces );
683 CM_FREE( planes );
684 CM_FREE( brushsides );
685 CM_FREE( brushes );
686 CM_FREE( leafbrushes );
687 CM_FREE( areaportals );
688 CM_FREE( areas );
689 CM_FREE( leafs );
690 CM_FREE( nodes );
691 CM_FREE( cmodels );
692 CM_FREE( entitystring );
693
694 memset( cache, 0, sizeof( *cache ) );
695 }
696 }
697
698 memset( cm, 0, sizeof( *cm ) );
699 }
700
701
702 /*
703 ==================
704 CM_LoadMap
705
706 Loads in the map and all submodels
707 ==================
708 */
CM_LoadMap(cm_t * cm,const char * name,uint32 flags,uint32 * checksum)709 qboolean CM_LoadMap( cm_t *cm, const char *name, uint32 flags, uint32 *checksum ) {
710 cmcache_t *cache;
711 byte *buf;
712 int i;
713 dheader_t header;
714 int length;
715 // char *entstring;
716 // char buffer[MAX_QPATH];
717
718 if( !name || !name[0] ) {
719 Com_Error( ERR_FATAL, "CM_LoadMap: NULL name" );
720 }
721
722 for( i = 0, cache = cm_cache; i < CM_CACHESIZE; i++, cache++ ) {
723 if( !cache->name[0] ) {
724 continue;
725 }
726 if( strcmp( cache->name, name ) ) {
727 continue;
728 }
729 //if( !( cache->flags & CM_LOAD_VISONLY ) || ( flags & CM_LOAD_VISONLY ) )
730 {
731 cm->cache = cache;
732 if( checksum ) {
733 *checksum = cache->checksum;
734 }
735 cm->cache = cache;
736 if( flags & CM_LOAD_CLIENT ) {
737 cm->floodnums = NULL;
738 cm->portalopen = NULL;
739 } else {
740 cm->floodnums = CM_Mallocz( sizeof( int ) * cache->numareas +
741 sizeof( qboolean ) * cache->numareaportals );
742 cm->portalopen = ( qboolean * )( cm->floodnums + cache->numareas );
743 CM_FloodAreaConnections( cm );
744 }
745 cache->refcount++;
746 return qtrue; // still have the right version
747 }
748 break;
749 }
750
751 // find a free slot
752 for( i = 0, cache = cm_cache; i < CM_CACHESIZE; i++, cache++ ) {
753 if( !cache->name[0] ) {
754 break;
755 }
756 }
757 if( i == CM_CACHESIZE ) {
758 Com_Error( ERR_DROP, "Out of cache slots to load %s", name );
759 }
760
761 //
762 // load the file
763 //
764 length = FS_LoadFileEx( name, (void **)&buf, FS_FLAG_CACHE );
765 if( !buf )
766 Com_Error( ERR_DROP, "Couldn't load %s", name );
767
768 cache->checksum = LittleLong( Com_BlockChecksum( buf, length ) );
769 if( checksum ) {
770 *checksum = cache->checksum;
771 }
772
773 header = *( dheader_t * )buf;
774 for( i = 0; i < sizeof( dheader_t )/4; i++ )
775 (( uint32 * )&header)[i] = LittleLong( (( uint32 * )&header)[i] );
776
777 if( header.version != BSPVERSION ) {
778 Com_Error( ERR_DROP, "CM_LoadMap: %s has wrong version number (%i should be %i)",
779 name, header.version, BSPVERSION );
780 }
781
782 cmod_base = buf;
783 cmod = cache;
784
785 #define CM_LOAD( Func, Lump ) \
786 do { \
787 CMod_Load##Func( &header.lumps[LUMP_##Lump] ); \
788 } while( 0 )
789
790 // load into heap
791 CM_LOAD( Visibility, VISIBILITY );
792 CM_LOAD( Surfaces, TEXINFO );
793 CM_LOAD( Planes, PLANES );
794 CM_LOAD( BrushSides, BRUSHSIDES );
795 CM_LOAD( Brushes, BRUSHES );
796 CM_LOAD( LeafBrushes, LEAFBRUSHES );
797 CM_LOAD( AreaPortals, AREAPORTALS );
798 CM_LOAD( Areas, AREAS );
799 CM_LOAD( Leafs, LEAFS );
800 CM_LOAD( Nodes, NODES );
801 CM_LOAD( Submodels, MODELS );
802
803 #if 0
804 // Load the entity string from file, if specified
805 entstring = NULL;
806 if( cmod->load_entities->integer && !clientload ) {
807 COM_StripExtension( name, buffer, sizeof( buffer ) );
808 Q_strcat( buffer, sizeof( buffer ), ".map" );
809 FS_LoadFile( buffer, ( void ** )&entstring );
810 }
811
812 if( entstring ) {
813 Com_Printf( "Loading %s...\n", buffer );
814 if( !CM_ParseMapFile( entstring ) ) {
815 CMod_LoadEntityString( &header.lumps[LUMP_ENTITIES] );
816 }
817 FS_FreeFile( entstring );
818 } else {
819 CMod_LoadEntityString( &header.lumps[LUMP_ENTITIES] );
820 }
821 #else
822 CMod_LoadEntityString( &header.lumps[LUMP_ENTITIES] );
823 #endif
824
825 FS_FreeFile( buf );
826
827 cache->refcount = 1;
828 cm->cache = cache;
829
830 if( flags & CM_LOAD_CLIENT ) {
831 cm->floodnums = NULL;
832 cm->portalopen = NULL;
833 } else {
834 cm->floodnums = CM_Mallocz( sizeof( int ) * cache->numareas +
835 sizeof( qboolean ) * cache->numareaportals );
836 cm->portalopen = ( qboolean * )( cm->floodnums + cache->numareas );
837 CM_FloodAreaConnections( cm );
838 }
839
840 Q_strncpyz( cache->name, name, sizeof( cache->name ) );
841
842 //map_load_entities->modified = qfalse;
843
844 return qtrue;
845 }
846
847 /*
848 ==================
849 CM_InlineModel
850 ==================
851 */
CM_InlineModel(cm_t * cm,const char * name)852 cmodel_t *CM_InlineModel( cm_t *cm, const char *name ) {
853 int num;
854 cmodel_t *cmodel;
855
856 if( !name || name[0] != '*' ) {
857 Com_Error( ERR_DROP, "CM_InlineModel: bad name" );
858 }
859 if( !cm->cache ) {
860 Com_Error( ERR_DROP, "CM_InlineModel: NULL cache" );
861 }
862 num = atoi( name + 1 );
863 if( num < 1 || num >= cm->cache->numcmodels ) {
864 Com_Error ( ERR_DROP, "CM_InlineModel: bad number" );
865 }
866
867 cmodel = &cmod->cmodels[num];
868
869 return cmodel;
870 }
871
CM_NumClusters(cm_t * cm)872 int CM_NumClusters( cm_t *cm ) {
873 if( !cm->cache ) {
874 return 0;
875 }
876 return cm->cache->numclusters;
877 }
878
CM_NumInlineModels(cm_t * cm)879 int CM_NumInlineModels( cm_t *cm ) {
880 if( !cm->cache ) {
881 return 0;
882 }
883 return cm->cache->numcmodels;
884 }
885
CM_EntityString(cm_t * cm)886 char *CM_EntityString( cm_t *cm ) {
887 if( !cm->cache ) {
888 return "";
889 }
890 if( !cm->cache->entitystring ) {
891 return "";
892 }
893 return cm->cache->entitystring;
894 }
895
CM_NodeNum(cm_t * cm,int number)896 cnode_t *CM_NodeNum( cm_t *cm, int number ) {
897 if( !cm->cache ) {
898 Com_Error( ERR_DROP, "CM_NodeNum: NULL cache" );
899 }
900 if( number < 0 || number >= cm->cache->numnodes ) {
901 Com_Error( ERR_DROP, "CM_NodeNum: bad number" );
902 }
903 return cm->cache->nodes + number;
904 }
905
906 //=======================================================================
907
908 static cplane_t box_planes[12];
909 static cnode_t box_nodes[6];
910 static cnode_t *box_headnode;
911 static cbrush_t box_brush;
912 static cbrush_t *box_leafbrush;
913 static cbrushside_t box_brushsides[6];
914 static cleaf_t box_leaf;
915 static cleaf_t box_emptyleaf;
916
917 /*
918 ===================
919 CM_InitBoxHull
920
921 Set up the planes and nodes so that the six floats of a bounding box
922 can just be stored out and get a proper clipping hull structure.
923 ===================
924 */
CM_InitBoxHull(void)925 static void CM_InitBoxHull( void ) {
926 int i;
927 int side;
928 cnode_t *c;
929 cplane_t *p;
930 cbrushside_t *s;
931
932 box_headnode = &box_nodes[0];
933
934 box_brush.numsides = 6;
935 box_brush.firstbrushside = &box_brushsides[0];
936 box_brush.contents = CONTENTS_MONSTER;
937
938 box_leaf.contents = CONTENTS_MONSTER;
939 box_leaf.firstleafbrush = &box_leafbrush;
940 box_leaf.numleafbrushes = 1;
941
942 box_leafbrush = &box_brush;
943
944 for( i = 0; i < 6; i++ ) {
945 side = i & 1;
946
947 // brush sides
948 s = &box_brushsides[i];
949 s->plane = &box_planes[i*2+side];
950 s->surface = &nullsurface;
951
952 // nodes
953 c = &box_nodes[i];
954 c->plane = &box_planes[i*2];
955 c->children[side] = ( cnode_t * )&box_emptyleaf;
956 if( i != 5 )
957 c->children[side^1] = &box_nodes[i + 1];
958 else
959 c->children[side^1] = ( cnode_t * )&box_leaf;
960
961 // planes
962 p = &box_planes[i*2];
963 p->type = i >> 1;
964 p->signbits = 0;
965 VectorClear( p->normal );
966 p->normal[i>>1] = 1;
967
968 p = &box_planes[i*2+1];
969 p->type = 3 + ( i >> 1 );
970 p->signbits = 0;
971 VectorClear( p->normal );
972 p->normal[i>>1] = -1;
973 }
974 }
975
976
977 /*
978 ===================
979 CM_HeadnodeForBox
980
981 To keep everything totally uniform, bounding boxes are turned into small
982 BSP trees instead of being compared directly.
983 ===================
984 */
CM_HeadnodeForBox(vec3_t mins,vec3_t maxs)985 cnode_t *CM_HeadnodeForBox( vec3_t mins, vec3_t maxs ) {
986 box_planes[0].dist = maxs[0];
987 box_planes[1].dist = -maxs[0];
988 box_planes[2].dist = mins[0];
989 box_planes[3].dist = -mins[0];
990 box_planes[4].dist = maxs[1];
991 box_planes[5].dist = -maxs[1];
992 box_planes[6].dist = mins[1];
993 box_planes[7].dist = -mins[1];
994 box_planes[8].dist = maxs[2];
995 box_planes[9].dist = -maxs[2];
996 box_planes[10].dist = mins[2];
997 box_planes[11].dist = -mins[2];
998
999 return box_headnode;
1000 }
1001
1002
1003 /*
1004 ==================
1005 CM_PointLeaf_r
1006
1007 ==================
1008 */
CM_PointLeaf_r(vec3_t p,cnode_t * node)1009 static cleaf_t *CM_PointLeaf_r( vec3_t p, cnode_t *node ) {
1010 float d;
1011 cplane_t *plane;
1012
1013 while( node->plane ) {
1014 plane = node->plane;
1015 if( plane->type < 3 )
1016 d = p[plane->type] - plane->dist;
1017 else
1018 d = DotProduct( plane->normal, p ) - plane->dist;
1019 if( d < 0 )
1020 node = node->children[1];
1021 else
1022 node = node->children[0];
1023 }
1024
1025 return ( cleaf_t * )node;
1026 }
1027
CM_PointLeaf(cm_t * cm,vec3_t p)1028 cleaf_t *CM_PointLeaf( cm_t *cm, vec3_t p ) {
1029 if( !cm->cache ) {
1030 return &nullleaf; // server may call this without map loaded
1031 }
1032 return CM_PointLeaf_r( p, cm->cache->nodes );
1033 }
1034
1035
1036 /*
1037 =============
1038 CM_BoxLeafnums
1039
1040 Fills in a list of all the leafs touched
1041 =============
1042 */
1043 static int leaf_count, leaf_maxcount;
1044 static cleaf_t **leaf_list;
1045 static float *leaf_mins, *leaf_maxs;
1046 static cnode_t *leaf_topnode;
1047
CM_BoxLeafs_r(cnode_t * node)1048 static void CM_BoxLeafs_r( cnode_t *node ) {
1049 cplane_t *plane;
1050 int s;
1051
1052 while( 1 ) {
1053 plane = node->plane;
1054 if( !plane ) {
1055 if( leaf_count >= leaf_maxcount ) {
1056 return;
1057 }
1058 leaf_list[leaf_count++] = ( cleaf_t * )node;
1059 return;
1060 }
1061
1062 s = BoxOnPlaneSide( leaf_mins, leaf_maxs, plane );
1063 if( s == 1 ) {
1064 node = node->children[0];
1065 } else if( s == 2 ) {
1066 node = node->children[1];
1067 } else {
1068 // go down both
1069 if( !leaf_topnode ) {
1070 leaf_topnode = node;
1071 }
1072 CM_BoxLeafs_r( node->children[0] );
1073 node = node->children[1];
1074 }
1075
1076 }
1077 }
1078
CM_BoxLeafs_headnode(vec3_t mins,vec3_t maxs,cleaf_t ** list,int listsize,cnode_t * headnode,cnode_t ** topnode)1079 static int CM_BoxLeafs_headnode( vec3_t mins, vec3_t maxs, cleaf_t **list, int listsize,
1080 cnode_t *headnode, cnode_t **topnode )
1081 {
1082 leaf_list = list;
1083 leaf_count = 0;
1084 leaf_maxcount = listsize;
1085 leaf_mins = mins;
1086 leaf_maxs = maxs;
1087
1088 leaf_topnode = NULL;
1089
1090 CM_BoxLeafs_r( headnode );
1091
1092 if( topnode )
1093 *topnode = leaf_topnode;
1094
1095 return leaf_count;
1096 }
1097
CM_BoxLeafs(cm_t * cm,vec3_t mins,vec3_t maxs,cleaf_t ** list,int listsize,cnode_t ** topnode)1098 int CM_BoxLeafs( cm_t *cm, vec3_t mins, vec3_t maxs, cleaf_t **list, int listsize, cnode_t **topnode ) {
1099 if( !cm->cache ) // map not loaded
1100 return 0;
1101 return CM_BoxLeafs_headnode( mins, maxs, list,
1102 listsize, cm->cache->nodes, topnode );
1103 }
1104
1105
1106
1107 /*
1108 ==================
1109 CM_PointContents
1110
1111 ==================
1112 */
CM_PointContents(vec3_t p,cnode_t * headnode)1113 int CM_PointContents( vec3_t p, cnode_t *headnode ) {
1114 cleaf_t *leaf;
1115
1116 if( !headnode ) {
1117 return 0;
1118 }
1119
1120 leaf = CM_PointLeaf_r( p, headnode );
1121
1122 return leaf->contents;
1123 }
1124
1125 /*
1126 ==================
1127 CM_TransformedPointContents
1128
1129 Handles offseting and rotation of the end points for moving and
1130 rotating entities
1131 ==================
1132 */
CM_TransformedPointContents(vec3_t p,cnode_t * headnode,vec3_t origin,vec3_t angles)1133 int CM_TransformedPointContents( vec3_t p, cnode_t *headnode, vec3_t origin, vec3_t angles ) {
1134 vec3_t p_l;
1135 vec3_t temp;
1136 vec3_t forward, right, up;
1137 cleaf_t *leaf;
1138
1139 if( !headnode ) {
1140 return 0;
1141 }
1142
1143 // subtract origin offset
1144 VectorSubtract (p, origin, p_l);
1145
1146 // rotate start and end into the models frame of reference
1147 if (headnode != box_headnode &&
1148 (angles[0] || angles[1] || angles[2]) )
1149 {
1150 AngleVectors (angles, forward, right, up);
1151
1152 VectorCopy (p_l, temp);
1153 p_l[0] = DotProduct (temp, forward);
1154 p_l[1] = -DotProduct (temp, right);
1155 p_l[2] = DotProduct (temp, up);
1156 }
1157
1158 leaf = CM_PointLeaf_r( p_l, headnode );
1159
1160 return leaf->contents;
1161 }
1162
1163
1164 /*
1165 ===============================================================================
1166
1167 BOX TRACING
1168
1169 ===============================================================================
1170 */
1171
1172 // 1/32 epsilon to keep floating point happy
1173 #define DIST_EPSILON (0.03125)
1174
1175 static vec3_t trace_start, trace_end;
1176 static vec3_t trace_mins, trace_maxs;
1177 static vec3_t trace_extents;
1178
1179 static trace_t *trace_trace;
1180 static int trace_contents;
1181 static qboolean trace_ispoint; // optimized case
1182
1183 /*
1184 ================
1185 CM_ClipBoxToBrush
1186 ================
1187 */
CM_ClipBoxToBrush(vec3_t mins,vec3_t maxs,vec3_t p1,vec3_t p2,trace_t * trace,cbrush_t * brush)1188 static void CM_ClipBoxToBrush (vec3_t mins, vec3_t maxs, vec3_t p1, vec3_t p2,
1189 trace_t *trace, cbrush_t *brush)
1190 {
1191 int i, j;
1192 cplane_t *plane, *clipplane;
1193 float dist;
1194 float enterfrac, leavefrac;
1195 vec3_t ofs;
1196 float d1, d2;
1197 qboolean getout, startout;
1198 float f;
1199 cbrushside_t *side, *leadside;
1200
1201 enterfrac = -1;
1202 leavefrac = 1;
1203 clipplane = NULL;
1204
1205 if (!brush->numsides)
1206 return;
1207
1208 getout = qfalse;
1209 startout = qfalse;
1210 leadside = NULL;
1211
1212 side = brush->firstbrushside;
1213 for (i=0 ; i<brush->numsides ; i++, side++)
1214 {
1215 plane = side->plane;
1216
1217 // FIXME: special case for axial
1218
1219 if (!trace_ispoint)
1220 { // general box case
1221
1222 // push the plane out apropriately for mins/maxs
1223
1224 // FIXME: use signbits into 8 way lookup for each mins/maxs
1225 for (j=0 ; j<3 ; j++)
1226 {
1227 if (plane->normal[j] < 0)
1228 ofs[j] = maxs[j];
1229 else
1230 ofs[j] = mins[j];
1231 }
1232 dist = DotProduct (ofs, plane->normal);
1233 dist = plane->dist - dist;
1234 }
1235 else
1236 { // special point case
1237 dist = plane->dist;
1238 }
1239
1240 d1 = DotProduct (p1, plane->normal) - dist;
1241 d2 = DotProduct (p2, plane->normal) - dist;
1242
1243 if (d2 > 0)
1244 getout = qtrue; // endpoint is not in solid
1245 if (d1 > 0)
1246 startout = qtrue;
1247
1248 // if completely in front of face, no intersection
1249 if (d1 > 0 && d2 >= d1)
1250 return;
1251
1252 if (d1 <= 0 && d2 <= 0)
1253 continue;
1254
1255 // crosses face
1256 if (d1 > d2)
1257 { // enter
1258 f = (d1-DIST_EPSILON) / (d1-d2);
1259 if (f > enterfrac)
1260 {
1261 enterfrac = f;
1262 clipplane = plane;
1263 leadside = side;
1264 }
1265 }
1266 else
1267 { // leave
1268 f = (d1+DIST_EPSILON) / (d1-d2);
1269 if (f < leavefrac)
1270 leavefrac = f;
1271 }
1272 }
1273
1274 if (!startout)
1275 { // original point was inside brush
1276 trace->startsolid = qtrue;
1277 if (!getout)
1278 trace->allsolid = qtrue;
1279 return;
1280 }
1281 if (enterfrac < leavefrac)
1282 {
1283 if (enterfrac > -1 && enterfrac < trace->fraction)
1284 {
1285 if (enterfrac < 0)
1286 enterfrac = 0;
1287 trace->fraction = enterfrac;
1288 trace->plane = *clipplane;
1289 trace->surface = &(leadside->surface->c);
1290 trace->contents = brush->contents;
1291 }
1292 }
1293 }
1294
1295 /*
1296 ================
1297 CM_TestBoxInBrush
1298 ================
1299 */
CM_TestBoxInBrush(vec3_t mins,vec3_t maxs,vec3_t p1,trace_t * trace,cbrush_t * brush)1300 static void CM_TestBoxInBrush (vec3_t mins, vec3_t maxs, vec3_t p1,
1301 trace_t *trace, cbrush_t *brush)
1302 {
1303 int i, j;
1304 cplane_t *plane;
1305 float dist;
1306 vec3_t ofs;
1307 float d1;
1308 cbrushside_t *side;
1309
1310 if (!brush->numsides)
1311 return;
1312
1313 side = brush->firstbrushside;
1314 for (i=0 ; i<brush->numsides ; i++, side++)
1315 {
1316 plane = side->plane;
1317
1318 // FIXME: special case for axial
1319
1320 // general box case
1321
1322 // push the plane out apropriately for mins/maxs
1323
1324 // FIXME: use signbits into 8 way lookup for each mins/maxs
1325 for (j=0 ; j<3 ; j++)
1326 {
1327 if (plane->normal[j] < 0)
1328 ofs[j] = maxs[j];
1329 else
1330 ofs[j] = mins[j];
1331 }
1332 dist = DotProduct (ofs, plane->normal);
1333 dist = plane->dist - dist;
1334
1335 d1 = DotProduct (p1, plane->normal) - dist;
1336
1337 // if completely in front of face, no intersection
1338 if (d1 > 0)
1339 return;
1340
1341 }
1342
1343 // inside this brush
1344 trace->startsolid = trace->allsolid = qtrue;
1345 trace->fraction = 0;
1346 trace->contents = brush->contents;
1347 }
1348
1349
1350 /*
1351 ================
1352 CM_TraceToLeaf
1353 ================
1354 */
CM_TraceToLeaf(cleaf_t * leaf)1355 static void CM_TraceToLeaf ( cleaf_t *leaf )
1356 {
1357 int k;
1358 cbrush_t *b, **leafbrush;
1359
1360 if( !( leaf->contents & trace_contents ) )
1361 return;
1362 // trace line against all brushes in the leaf
1363 leafbrush = leaf->firstleafbrush;
1364 for (k=0 ; k<leaf->numleafbrushes ; k++, leafbrush++)
1365 {
1366 b = *leafbrush;
1367 if (b->checkcount == checkcount)
1368 continue; // already checked this brush in another leaf
1369 b->checkcount = checkcount;
1370
1371 if ( !(b->contents & trace_contents))
1372 continue;
1373 CM_ClipBoxToBrush (trace_mins, trace_maxs, trace_start, trace_end, trace_trace, b);
1374 if (!trace_trace->fraction)
1375 return;
1376 }
1377
1378 }
1379
1380
1381 /*
1382 ================
1383 CM_TestInLeaf
1384 ================
1385 */
CM_TestInLeaf(cleaf_t * leaf)1386 static void CM_TestInLeaf ( cleaf_t *leaf )
1387 {
1388 int k;
1389 cbrush_t *b, **leafbrush;
1390
1391 if( !( leaf->contents & trace_contents ) )
1392 return;
1393 // trace line against all brushes in the leaf
1394 leafbrush = leaf->firstleafbrush;
1395 for (k=0 ; k<leaf->numleafbrushes ; k++, leafbrush++)
1396 {
1397 b = *leafbrush;
1398 if (b->checkcount == checkcount)
1399 continue; // already checked this brush in another leaf
1400 b->checkcount = checkcount;
1401
1402 if ( !(b->contents & trace_contents))
1403 continue;
1404 CM_TestBoxInBrush (trace_mins, trace_maxs, trace_start, trace_trace, b);
1405 if (!trace_trace->fraction)
1406 return;
1407 }
1408
1409 }
1410
1411
1412 /*
1413 ==================
1414 CM_RecursiveHullCheck
1415
1416 ==================
1417 */
CM_RecursiveHullCheck(cnode_t * node,float p1f,float p2f,vec3_t p1,vec3_t p2)1418 static void CM_RecursiveHullCheck ( cnode_t *node, float p1f, float p2f, vec3_t p1, vec3_t p2)
1419 {
1420 cplane_t *plane;
1421 float t1, t2, offset;
1422 float frac, frac2;
1423 float idist;
1424 int i;
1425 vec3_t mid;
1426 int side;
1427 float midf;
1428
1429 if (trace_trace->fraction <= p1f)
1430 return; // already hit something nearer
1431
1432 // if plane is NULL, we are in a leaf node
1433 plane = node->plane;
1434 if (!plane)
1435 {
1436 CM_TraceToLeaf ( ( cleaf_t * )node );
1437 return;
1438 }
1439
1440 //
1441 // find the point distances to the seperating plane
1442 // and the offset for the size of the box
1443 //
1444 if (plane->type < 3)
1445 {
1446 t1 = p1[plane->type] - plane->dist;
1447 t2 = p2[plane->type] - plane->dist;
1448 offset = trace_extents[plane->type];
1449 }
1450 else
1451 {
1452 t1 = DotProduct (plane->normal, p1) - plane->dist;
1453 t2 = DotProduct (plane->normal, p2) - plane->dist;
1454 if (trace_ispoint)
1455 offset = 0;
1456 else
1457 offset = fabs(trace_extents[0]*plane->normal[0]) +
1458 fabs(trace_extents[1]*plane->normal[1]) +
1459 fabs(trace_extents[2]*plane->normal[2]);
1460 }
1461
1462 // see which sides we need to consider
1463 if (t1 >= offset && t2 >= offset)
1464 {
1465 CM_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
1466 return;
1467 }
1468 if (t1 < -offset && t2 < -offset)
1469 {
1470 CM_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
1471 return;
1472 }
1473
1474 // put the crosspoint DIST_EPSILON pixels on the near side
1475 if (t1 < t2)
1476 {
1477 idist = 1.0/(t1-t2);
1478 side = 1;
1479 frac2 = (t1 + offset + DIST_EPSILON)*idist;
1480 frac = (t1 - offset + DIST_EPSILON)*idist;
1481 }
1482 else if (t1 > t2)
1483 {
1484 idist = 1.0/(t1-t2);
1485 side = 0;
1486 frac2 = (t1 - offset - DIST_EPSILON)*idist;
1487 frac = (t1 + offset + DIST_EPSILON)*idist;
1488 }
1489 else
1490 {
1491 side = 0;
1492 frac = 1;
1493 frac2 = 0;
1494 }
1495
1496 // move up to the node
1497 if (frac < 0)
1498 frac = 0;
1499 if (frac > 1)
1500 frac = 1;
1501
1502 midf = p1f + (p2f - p1f)*frac;
1503 for (i=0 ; i<3 ; i++)
1504 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
1505
1506 CM_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
1507
1508
1509 // go past the node
1510 if (frac2 < 0)
1511 frac2 = 0;
1512 if (frac2 > 1)
1513 frac2 = 1;
1514
1515 midf = p1f + (p2f - p1f)*frac2;
1516 for (i=0 ; i<3 ; i++)
1517 mid[i] = p1[i] + frac2*(p2[i] - p1[i]);
1518
1519 CM_RecursiveHullCheck (node->children[side^1], midf, p2f, mid, p2);
1520 }
1521
1522
1523
1524 //======================================================================
1525
1526 /*
1527 ==================
1528 CM_BoxTrace
1529 ==================
1530 */
CM_BoxTrace(trace_t * trace,vec3_t start,vec3_t end,vec3_t mins,vec3_t maxs,cnode_t * headnode,int brushmask)1531 void CM_BoxTrace( trace_t *trace, vec3_t start, vec3_t end,
1532 vec3_t mins, vec3_t maxs,
1533 cnode_t *headnode, int brushmask )
1534 {
1535 int i;
1536
1537 checkcount++; // for multi-check avoidance
1538
1539 // fill in a default trace
1540 trace_trace = trace;
1541 memset (trace_trace, 0, sizeof( *trace_trace ));
1542 trace_trace->fraction = 1;
1543 trace_trace->surface = &(nullsurface.c);
1544
1545 if( !headnode ) {
1546 return;
1547 }
1548
1549 trace_contents = brushmask;
1550 VectorCopy (start, trace_start);
1551 VectorCopy (end, trace_end);
1552 VectorCopy (mins, trace_mins);
1553 VectorCopy (maxs, trace_maxs);
1554
1555 //
1556 // check for position test special case
1557 //
1558 if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2])
1559 {
1560 cleaf_t *leafs[1024];
1561 int i, numleafs;
1562 vec3_t c1, c2;
1563 cnode_t *topnode;
1564
1565 VectorAdd (start, mins, c1);
1566 VectorAdd (start, maxs, c2);
1567 for (i=0 ; i<3 ; i++)
1568 {
1569 c1[i] -= 1;
1570 c2[i] += 1;
1571 }
1572
1573 numleafs = CM_BoxLeafs_headnode (c1, c2, leafs, 1024, headnode, &topnode);
1574 for (i=0 ; i<numleafs ; i++)
1575 {
1576 CM_TestInLeaf (leafs[i]);
1577 if (trace_trace->allsolid)
1578 break;
1579 }
1580 VectorCopy (start, trace_trace->endpos);
1581 return;
1582 }
1583
1584 //
1585 // check for point special case
1586 //
1587 if (mins[0] == 0 && mins[1] == 0 && mins[2] == 0
1588 && maxs[0] == 0 && maxs[1] == 0 && maxs[2] == 0)
1589 {
1590 trace_ispoint = qtrue;
1591 VectorClear (trace_extents);
1592 }
1593 else
1594 {
1595 trace_ispoint = qfalse;
1596 trace_extents[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
1597 trace_extents[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
1598 trace_extents[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
1599 }
1600
1601 //
1602 // general sweeping through world
1603 //
1604 CM_RecursiveHullCheck (headnode, 0, 1, start, end);
1605
1606 if (trace_trace->fraction == 1)
1607 {
1608 VectorCopy (end, trace_trace->endpos);
1609 }
1610 else
1611 {
1612 for (i=0 ; i<3 ; i++)
1613 trace_trace->endpos[i] = start[i] + trace_trace->fraction * (end[i] - start[i]);
1614 }
1615
1616 }
1617
1618
1619 /*
1620 ==================
1621 CM_TransformedBoxTrace
1622
1623 Handles offseting and rotation of the end points for moving and
1624 rotating entities
1625 ==================
1626 */
CM_TransformedBoxTrace(trace_t * trace,vec3_t start,vec3_t end,vec3_t mins,vec3_t maxs,cnode_t * headnode,int brushmask,vec3_t origin,vec3_t angles)1627 void CM_TransformedBoxTrace ( trace_t *trace, vec3_t start, vec3_t end,
1628 vec3_t mins, vec3_t maxs,
1629 cnode_t *headnode, int brushmask,
1630 vec3_t origin, vec3_t angles)
1631 {
1632 vec3_t start_l, end_l;
1633 vec3_t a;
1634 vec3_t forward, right, up;
1635 vec3_t temp;
1636 qboolean rotated;
1637
1638 // subtract origin offset
1639 VectorSubtract (start, origin, start_l);
1640 VectorSubtract (end, origin, end_l);
1641
1642 // rotate start and end into the models frame of reference
1643 if (headnode != box_headnode &&
1644 (angles[0] || angles[1] || angles[2]) )
1645 rotated = qtrue;
1646 else
1647 rotated = qfalse;
1648
1649 if (rotated)
1650 {
1651 AngleVectors (angles, forward, right, up);
1652
1653 VectorCopy (start_l, temp);
1654 start_l[0] = DotProduct (temp, forward);
1655 start_l[1] = -DotProduct (temp, right);
1656 start_l[2] = DotProduct (temp, up);
1657
1658 VectorCopy (end_l, temp);
1659 end_l[0] = DotProduct (temp, forward);
1660 end_l[1] = -DotProduct (temp, right);
1661 end_l[2] = DotProduct (temp, up);
1662 }
1663
1664 // sweep the box through the model
1665 CM_BoxTrace ( trace, start_l, end_l, mins, maxs, headnode, brushmask);
1666
1667 if (rotated && trace->fraction != 1.0)
1668 {
1669 // FIXME: figure out how to do this with existing angles
1670 VectorNegate (angles, a);
1671 AngleVectors (a, forward, right, up);
1672
1673 VectorCopy (trace->plane.normal, temp);
1674 trace->plane.normal[0] = DotProduct (temp, forward);
1675 trace->plane.normal[1] = -DotProduct (temp, right);
1676 trace->plane.normal[2] = DotProduct (temp, up);
1677 }
1678
1679 trace->endpos[0] = start[0] + trace->fraction * (end[0] - start[0]);
1680 trace->endpos[1] = start[1] + trace->fraction * (end[1] - start[1]);
1681 trace->endpos[2] = start[2] + trace->fraction * (end[2] - start[2]);
1682 }
1683
1684 /*
1685 ===============================================================================
1686
1687 PVS / PHS
1688
1689 ===============================================================================
1690 */
1691
1692 static byte pvsrow[MAX_MAP_LEAFS/8];
1693 static byte phsrow[MAX_MAP_LEAFS/8];
1694
1695 /*
1696 ===================
1697 CM_DecompressVis
1698 ===================
1699 */
CM_DecompressVis(byte * in,byte * out,int rowsize)1700 static void CM_DecompressVis( byte *in, byte *out, int rowsize ) {
1701 int c;
1702 byte *out_p;
1703
1704 out_p = out;
1705 do {
1706 if( *in ) {
1707 *out_p++ = *in++;
1708 continue;
1709 }
1710
1711 c = in[1];
1712 in += 2;
1713 if( ( out_p - out ) + c > rowsize ) {
1714 c = rowsize - ( out_p - out );
1715 Com_WPrintf( "CM_DecompressVis: overrun\n" );
1716 }
1717 while( c ) {
1718 *out_p++ = 0;
1719 c--;
1720 }
1721 } while( out_p - out < rowsize );
1722 }
1723
CM_ClusterPVS(cm_t * cm,int cluster)1724 byte *CM_ClusterPVS( cm_t *cm, int cluster ) {
1725 cmcache_t *cache = cm->cache;
1726
1727 if( !cache || !cache->vis ) {
1728 memset( pvsrow, 0xff, sizeof( pvsrow ) );
1729 } else if( cluster == -1 ) {
1730 memset( pvsrow, 0, cache->visrowsize );
1731 } else {
1732 CM_DecompressVis( ( byte * )cache->vis + cache->vis->bitofs[cluster][DVIS_PVS],
1733 pvsrow, cache->visrowsize );
1734 }
1735 return pvsrow;
1736 }
1737
CM_ClusterPHS(cm_t * cm,int cluster)1738 byte *CM_ClusterPHS( cm_t *cm, int cluster ) {
1739 cmcache_t *cache = cm->cache;
1740
1741 if( !cache || !cache->vis ) {
1742 memset( phsrow, 0xff, sizeof( phsrow ) );
1743 } else if( cluster == -1 ) {
1744 memset( phsrow, 0, cache->visrowsize );
1745 } else {
1746 CM_DecompressVis( ( byte * )cache->vis + cache->vis->bitofs[cluster][DVIS_PHS],
1747 phsrow, cache->visrowsize );
1748 }
1749 return phsrow;
1750 }
1751
1752 /*
1753 ===============================================================================
1754
1755 AREAPORTALS
1756
1757 ===============================================================================
1758 */
1759
FloodArea_r(cm_t * cm,int number,int floodnum)1760 static void FloodArea_r( cm_t *cm, int number, int floodnum ) {
1761 int i;
1762 careaportal_t *p;
1763 carea_t *area;
1764
1765 area = &cmod->areas[number];
1766 if( area->floodvalid == floodvalid ) {
1767 if( cm->floodnums[number] == floodnum )
1768 return;
1769 Com_Error( ERR_DROP, "FloodArea_r: reflooded" );
1770 }
1771
1772 cm->floodnums[number] = floodnum;
1773 area->floodvalid = floodvalid;
1774 p = &cm->cache->areaportals[area->firstareaportal];
1775 for( i = 0; i < area->numareaportals; i++, p++ ) {
1776 if( cm->portalopen[p->portalnum] )
1777 FloodArea_r( cm, p->otherarea, floodnum );
1778 }
1779 }
1780
1781 /*
1782 ====================
1783 CM_FloodAreaConnections
1784 ====================
1785 */
CM_FloodAreaConnections(cm_t * cm)1786 void CM_FloodAreaConnections( cm_t *cm ) {
1787 int i;
1788 carea_t *area;
1789 int floodnum;
1790
1791 // all current floods are now invalid
1792 floodvalid++;
1793 floodnum = 0;
1794
1795 // area 0 is not used
1796 for( i = 1; i < cm->cache->numareas; i++ ) {
1797 area = &cm->cache->areas[i];
1798 if( area->floodvalid == floodvalid )
1799 continue; // already flooded into
1800 floodnum++;
1801 FloodArea_r( cm, i, floodnum );
1802 }
1803
1804 }
1805
CM_SetAreaPortalState(cm_t * cm,int portalnum,qboolean open)1806 void CM_SetAreaPortalState( cm_t *cm, int portalnum, qboolean open ) {
1807 if( portalnum > cm->cache->numareaportals )
1808 Com_Error( ERR_DROP, "CM_SetAreaPortalState: areaportal > numareaportals" );
1809
1810 cm->portalopen[portalnum] = open;
1811 CM_FloodAreaConnections( cm );
1812 }
1813
CM_AreasConnected(cm_t * cm,int area1,int area2)1814 qboolean CM_AreasConnected( cm_t *cm, int area1, int area2 ) {
1815 cmcache_t *cache = cm->cache;
1816
1817 if( map_noareas->integer )
1818 return qtrue;
1819
1820 if( area1 > cache->numareas || area2 > cache->numareas )
1821 Com_Error( ERR_DROP, "CM_AreasConnected: area > numareas" );
1822
1823 if( cm->floodnums[area1] == cm->floodnums[area2] )
1824 return qtrue;
1825
1826 return qfalse;
1827 }
1828
1829
1830 /*
1831 =================
1832 CM_WriteAreaBits
1833
1834 Writes a length byte followed by a bit vector of all the areas
1835 that area in the same flood as the area parameter
1836
1837 This is used by the client refreshes to cull visibility
1838 =================
1839 */
CM_WriteAreaBits(cm_t * cm,byte * buffer,int area)1840 int CM_WriteAreaBits( cm_t *cm, byte *buffer, int area ) {
1841 cmcache_t *cache = cm->cache;
1842 int i;
1843 int floodnum;
1844 int bytes;
1845
1846 bytes = ( cache->numareas + 7 ) >> 3;
1847
1848 if( map_noareas->integer || !area ) {
1849 // for debugging, send everything
1850 memset( buffer, 255, bytes );
1851 } else {
1852 memset( buffer, 0, bytes );
1853
1854 floodnum = cm->floodnums[area];
1855 for ( i = 0; i < cache->numareas; i++) {
1856 if( cm->floodnums[i] == floodnum ) {
1857 Q_SetBit( buffer, i );
1858 }
1859 }
1860 }
1861
1862 return bytes;
1863 }
1864
CM_WritePortalBits(cm_t * cm,byte * buffer)1865 int CM_WritePortalBits( cm_t *cm, byte *buffer ) {
1866 int i, bytes, numportals;
1867
1868 numportals = cm->cache->numareaportals;
1869 if( numportals > MAX_MAP_AREAS ) {
1870 /* HACK: use the same array size as areabytes!
1871 * It is nonsense for a map to have > 256 areaportals anyway. */
1872 Com_WPrintf( "CM_WritePortalBits: too many areaportals\n" );
1873 numportals = MAX_MAP_AREAS;
1874 }
1875
1876 bytes = ( numportals + 7 ) >> 3;
1877 memset( buffer, 0, bytes );
1878 for( i = 0; i < numportals; i++ ) {
1879 if( cm->portalopen[i] ) {
1880 Q_SetBit( buffer, i );
1881 }
1882 }
1883
1884 return bytes;
1885 }
1886
CM_SetPortalStates(cm_t * cm,byte * buffer,int bytes)1887 void CM_SetPortalStates( cm_t *cm, byte *buffer, int bytes ) {
1888 int i, numportals;
1889
1890 if( !bytes ) {
1891 return;
1892 }
1893
1894 numportals = bytes << 3;
1895 if( numportals > cm->cache->numareaportals ) {
1896 numportals = cm->cache->numareaportals;
1897 }
1898
1899 for( i = 0; i < numportals; i++ ) {
1900 cm->portalopen[i] = Q_IsBitSet( buffer, i ) ? qtrue : qfalse;
1901 }
1902
1903 CM_FloodAreaConnections( cm );
1904 }
1905
1906
1907 /*
1908 ===================
1909 CM_WritePortalState
1910
1911 Writes the portal state to a savegame file
1912 ===================
1913 */
CM_WritePortalState(cm_t * cm,fileHandle_t f)1914 void CM_WritePortalState( cm_t *cm, fileHandle_t f ) {
1915 // FIXME: incompatible savegames
1916 FS_Write( cm->portalopen, sizeof( qboolean ) * cm->cache->numareaportals, f );
1917 }
1918
1919 /*
1920 ===================
1921 CM_ReadPortalState
1922
1923 Reads the portal state from a savegame file
1924 and recalculates the area connections
1925 ===================
1926 */
CM_ReadPortalState(cm_t * cm,fileHandle_t f)1927 void CM_ReadPortalState( cm_t *cm, fileHandle_t f ) {
1928 FS_Read( cm->portalopen, sizeof( qboolean ) * cm->cache->numareaportals, f );
1929 CM_FloodAreaConnections( cm );
1930 }
1931
1932 /*
1933 =============
1934 CM_HeadnodeVisible
1935
1936 Returns qtrue if any leaf under headnode has a cluster that
1937 is potentially visible
1938 =============
1939 */
CM_HeadnodeVisible(cnode_t * node,byte * visbits)1940 qboolean CM_HeadnodeVisible( cnode_t *node, byte *visbits ) {
1941 cleaf_t *leaf;
1942 int cluster;
1943
1944 if( !node->plane ) {
1945 leaf = ( cleaf_t * )node;
1946 cluster = leaf->cluster;
1947 if( cluster == -1 )
1948 return qfalse;
1949 if( Q_IsBitSet( visbits, cluster ) )
1950 return qtrue;
1951 return qfalse;
1952 }
1953
1954 if( CM_HeadnodeVisible( node->children[0], visbits ) )
1955 return qtrue;
1956 return CM_HeadnodeVisible( node->children[1], visbits );
1957 }
1958
1959
1960 /*
1961 ============
1962 CM_FatPVS
1963
1964 The client will interpolate the view position,
1965 so we can't use a single PVS point
1966 ===========
1967 */
CM_FatPVS(cm_t * cm,const vec3_t org)1968 byte *CM_FatPVS( cm_t *cm, const vec3_t org ) {
1969 static byte fatpvs[MAX_MAP_LEAFS/8];
1970 cleaf_t *leafs[64];
1971 int clusters[64];
1972 int i, j, count;
1973 int longs;
1974 uint32 *src, *dst;
1975 vec3_t mins, maxs;
1976
1977 if( !cm->cache ) { // map not loaded
1978 memset( fatpvs, 0, sizeof( fatpvs ) );
1979 return fatpvs;
1980 }
1981
1982 for( i = 0; i < 3; i++ ) {
1983 mins[i] = org[i] - 8;
1984 maxs[i] = org[i] + 8;
1985 }
1986
1987 count = CM_BoxLeafs( cm, mins, maxs, leafs, 64, NULL );
1988 if( count < 1 )
1989 Com_Error( ERR_DROP, "CM_FatPVS: leaf count < 1" );
1990 longs = ( cm->cache->numclusters + 31 ) >> 5;
1991
1992 // convert leafs to clusters
1993 for( i = 0 ; i < count; i++ ) {
1994 clusters[i] = leafs[i]->cluster;
1995 }
1996
1997 src = ( uint32 * )CM_ClusterPVS( cm, clusters[0] );
1998 dst = ( uint32 * )fatpvs;
1999 for( j = 0; j < longs; j++ ) {
2000 *dst++ = *src++;
2001 }
2002
2003 // or in all the other leaf bits
2004 for( i = 1; i < count; i++ ) {
2005 for( j = 0; j < i; j++ ) {
2006 if( clusters[i] == clusters[j] ) {
2007 goto nextleaf; // already have the cluster we want
2008 }
2009 }
2010 src = ( uint32 * )CM_ClusterPVS( cm, clusters[i] );
2011 dst = ( uint32 * )fatpvs;
2012 for( j = 0; j < longs; j++ ) {
2013 *dst++ |= *src++;
2014 }
2015
2016 nextleaf:;
2017 }
2018
2019 return fatpvs;
2020 }
2021
2022 /*
2023 =============
2024 CM_Init
2025 =============
2026 */
CM_Init(void)2027 void CM_Init( void ) {
2028 CM_InitBoxHull();
2029
2030 map_noareas = Cvar_Get( "map_noareas", "0", 0 );
2031 map_load_entities = Cvar_Get( "map_load_entities", "0", 0 );
2032 }
2033
2034