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