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