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