1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.
This file is part of Quake III Arena source code.
Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.
Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Quake III Arena source code; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
===========================================================================
*/
#include "q_shared.h"
#include "qcommon.h"
#include "cm_polylib.h"
#define MAX_SUBMODELS 256
#define BOX_MODEL_HANDLE 255
#define CAPSULE_MODEL_HANDLE 254
typedef struct {
cplane_t *plane;
int children[2]; // negative numbers are leafs
} cNode_t;
typedef struct {
int cluster;
int area;
int firstLeafBrush;
int numLeafBrushes;
int firstLeafSurface;
int numLeafSurfaces;
} cLeaf_t;
typedef struct cmodel_s {
vec3_t mins, maxs;
cLeaf_t leaf; // submodels don't reference the main tree
} cmodel_t;
typedef struct {
cplane_t *plane;
int surfaceFlags;
int shaderNum;
} cbrushside_t;
typedef struct {
int shaderNum; // the shader that determined the contents
int contents;
vec3_t bounds[2];
int numsides;
cbrushside_t *sides;
int checkcount; // to avoid repeated testings
} cbrush_t;
typedef struct {
int checkcount; // to avoid repeated testings
int surfaceFlags;
int contents;
struct patchCollide_s *pc;
} cPatch_t;
typedef struct {
int floodnum;
int floodvalid;
} cArea_t;
typedef struct {
char name[MAX_QPATH];
int numShaders;
dshader_t *shaders;
int numBrushSides;
cbrushside_t *brushsides;
int numPlanes;
cplane_t *planes;
int numNodes;
cNode_t *nodes;
int numLeafs;
cLeaf_t *leafs;
int numLeafBrushes;
int *leafbrushes;
int numLeafSurfaces;
int *leafsurfaces;
int numSubModels;
cmodel_t *cmodels;
int numBrushes;
cbrush_t *brushes;
int numClusters;
int clusterBytes;
byte *visibility;
qboolean vised; // if false, visibility is just a single cluster of ffs
int numEntityChars;
char *entityString;
int numAreas;
cArea_t *areas;
int *areaPortals; // [ numAreas*numAreas ] reference counts
int numSurfaces;
cPatch_t **surfaces; // non-patches will be NULL
int floodvalid;
int checkcount; // incremented on each trace
} clipMap_t;
// keep 1/8 unit away to keep the position valid before network snapping
// and to avoid various numeric issues
#define SURFACE_CLIP_EPSILON (0.125)
extern clipMap_t cm;
extern int c_pointcontents;
extern int c_traces, c_brush_traces, c_patch_traces;
extern cvar_t *cm_noAreas;
extern cvar_t *cm_noCurves;
extern cvar_t *cm_playerCurveClip;
// cm_test.c
// Used for oriented capsule collision detection
typedef struct
{
qboolean use;
float radius;
float halfheight;
vec3_t offset;
} sphere_t;
typedef struct {
vec3_t start;
vec3_t end;
vec3_t size[2]; // size of the box being swept through the model
vec3_t offsets[8]; // [signbits][x] = either size[0][x] or size[1][x]
float maxOffset; // longest corner length from origin
vec3_t extents; // greatest of abs(size[0]) and abs(size[1])
vec3_t bounds[2]; // enclosing box of start and end surrounding by size
vec3_t modelOrigin;// origin of the model tracing through
int contents; // ored contents of the model tracing through
qboolean isPoint; // optimized case
trace_t trace; // returned from trace call
sphere_t sphere; // sphere for oriendted capsule collision
} traceWork_t;
typedef struct leafList_s {
int count;
int maxcount;
qboolean overflowed;
int *list;
vec3_t bounds[2];
int lastLeaf; // for overflows where each leaf can't be stored individually
void (*storeLeafs)( struct leafList_s *ll, int nodenum );
} leafList_t;
int CM_BoxBrushes( const vec3_t mins, const vec3_t maxs, cbrush_t **list, int listsize );
void CM_StoreLeafs( leafList_t *ll, int nodenum );
void CM_StoreBrushes( leafList_t *ll, int nodenum );
void CM_BoxLeafnums_r( leafList_t *ll, int nodenum );
cmodel_t *CM_ClipHandleToModel( clipHandle_t handle );
// cm_patch.c
struct patchCollide_s *CM_GeneratePatchCollide( int width, int height, vec3_t *points );
void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
void CM_ClearLevelPatches( void );
|
