← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openarena/hardy-backports

« back to all changes in this revision

Viewing changes to code/qcommon/cm_test.c

  • Committer: Bazaar Package Importer
  • Author(s): Bruno "Fuddl" Kleinert
  • Date: 2007-01-20 12:28:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070120122809-2yza5ojt7nqiyiam
Tags: upstream-0.6.0
Import upstream version 0.6.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
code/qcommon/cm_test.c
 
1
/*
 
2
===========================================================================
 
3
Copyright (C) 1999-2005 Id Software, Inc.
 
4
 
 
5
This file is part of Quake III Arena source code.
 
6
 
 
7
Quake III Arena source code is free software; you can redistribute it
 
8
and/or modify it under the terms of the GNU General Public License as
 
9
published by the Free Software Foundation; either version 2 of the License,
 
10
or (at your option) any later version.
 
11
 
 
12
Quake III Arena source code is distributed in the hope that it will be
 
13
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
GNU General Public License for more details.
 
16
 
 
17
You should have received a copy of the GNU General Public License
 
18
along with Quake III Arena source code; if not, write to the Free Software
 
19
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
20
===========================================================================
 
21
*/
 
22
#include "cm_local.h"
 
23
 
 
24
 
 
25
/*
 
26
==================
 
27
CM_PointLeafnum_r
 
28
 
 
29
==================
 
30
*/
 
31
int CM_PointLeafnum_r( const vec3_t p, int num ) {
 
32
        float           d;
 
33
        cNode_t         *node;
 
34
        cplane_t        *plane;
 
35
 
 
36
        while (num >= 0)
 
37
        {
 
38
                node = cm.nodes + num;
 
39
                plane = node->plane;
 
40
                
 
41
                if (plane->type < 3)
 
42
                        d = p[plane->type] - plane->dist;
 
43
                else
 
44
                        d = DotProduct (plane->normal, p) - plane->dist;
 
45
                if (d < 0)
 
46
                        num = node->children[1];
 
47
                else
 
48
                        num = node->children[0];
 
49
        }
 
50
 
 
51
        c_pointcontents++;              // optimize counter
 
52
 
 
53
        return -1 - num;
 
54
}
 
55
 
 
56
int CM_PointLeafnum( const vec3_t p ) {
 
57
        if ( !cm.numNodes ) {   // map not loaded
 
58
                return 0;
 
59
        }
 
60
        return CM_PointLeafnum_r (p, 0);
 
61
}
 
62
 
 
63
 
 
64
/*
 
65
======================================================================
 
66
 
 
67
LEAF LISTING
 
68
 
 
69
======================================================================
 
70
*/
 
71
 
 
72
 
 
73
void CM_StoreLeafs( leafList_t *ll, int nodenum ) {
 
74
        int             leafNum;
 
75
 
 
76
        leafNum = -1 - nodenum;
 
77
 
 
78
        // store the lastLeaf even if the list is overflowed
 
79
        if ( cm.leafs[ leafNum ].cluster != -1 ) {
 
80
                ll->lastLeaf = leafNum;
 
81
        }
 
82
 
 
83
        if ( ll->count >= ll->maxcount) {
 
84
                ll->overflowed = qtrue;
 
85
                return;
 
86
        }
 
87
        ll->list[ ll->count++ ] = leafNum;
 
88
}
 
89
 
 
90
void CM_StoreBrushes( leafList_t *ll, int nodenum ) {
 
91
        int                     i, k;
 
92
        int                     leafnum;
 
93
        int                     brushnum;
 
94
        cLeaf_t         *leaf;
 
95
        cbrush_t        *b;
 
96
 
 
97
        leafnum = -1 - nodenum;
 
98
 
 
99
        leaf = &cm.leafs[leafnum];
 
100
 
 
101
        for ( k = 0 ; k < leaf->numLeafBrushes ; k++ ) {
 
102
                brushnum = cm.leafbrushes[leaf->firstLeafBrush+k];
 
103
                b = &cm.brushes[brushnum];
 
104
                if ( b->checkcount == cm.checkcount ) {
 
105
                        continue;       // already checked this brush in another leaf
 
106
                }
 
107
                b->checkcount = cm.checkcount;
 
108
                for ( i = 0 ; i < 3 ; i++ ) {
 
109
                        if ( b->bounds[0][i] >= ll->bounds[1][i] || b->bounds[1][i] <= ll->bounds[0][i] ) {
 
110
                                break;
 
111
                        }
 
112
                }
 
113
                if ( i != 3 ) {
 
114
                        continue;
 
115
                }
 
116
                if ( ll->count >= ll->maxcount) {
 
117
                        ll->overflowed = qtrue;
 
118
                        return;
 
119
                }
 
120
                ((cbrush_t **)ll->list)[ ll->count++ ] = b;
 
121
        }
 
122
#if 0
 
123
        // store patches?
 
124
        for ( k = 0 ; k < leaf->numLeafSurfaces ; k++ ) {
 
125
                patch = cm.surfaces[ cm.leafsurfaces[ leaf->firstleafsurface + k ] ];
 
126
                if ( !patch ) {
 
127
                        continue;
 
128
                }
 
129
        }
 
130
#endif
 
131
}
 
132
 
 
133
/*
 
134
=============
 
135
CM_BoxLeafnums
 
136
 
 
137
Fills in a list of all the leafs touched
 
138
=============
 
139
*/
 
140
void CM_BoxLeafnums_r( leafList_t *ll, int nodenum ) {
 
141
        cplane_t        *plane;
 
142
        cNode_t         *node;
 
143
        int                     s;
 
144
 
 
145
        while (1) {
 
146
                if (nodenum < 0) {
 
147
                        ll->storeLeafs( ll, nodenum );
 
148
                        return;
 
149
                }
 
150
        
 
151
                node = &cm.nodes[nodenum];
 
152
                plane = node->plane;
 
153
                s = BoxOnPlaneSide( ll->bounds[0], ll->bounds[1], plane );
 
154
                if (s == 1) {
 
155
                        nodenum = node->children[0];
 
156
                } else if (s == 2) {
 
157
                        nodenum = node->children[1];
 
158
                } else {
 
159
                        // go down both
 
160
                        CM_BoxLeafnums_r( ll, node->children[0] );
 
161
                        nodenum = node->children[1];
 
162
                }
 
163
 
 
164
        }
 
165
}
 
166
 
 
167
/*
 
168
==================
 
169
CM_BoxLeafnums
 
170
==================
 
171
*/
 
172
int     CM_BoxLeafnums( const vec3_t mins, const vec3_t maxs, int *list, int listsize, int *lastLeaf) {
 
173
        leafList_t      ll;
 
174
 
 
175
        cm.checkcount++;
 
176
 
 
177
        VectorCopy( mins, ll.bounds[0] );
 
178
        VectorCopy( maxs, ll.bounds[1] );
 
179
        ll.count = 0;
 
180
        ll.maxcount = listsize;
 
181
        ll.list = list;
 
182
        ll.storeLeafs = CM_StoreLeafs;
 
183
        ll.lastLeaf = 0;
 
184
        ll.overflowed = qfalse;
 
185
 
 
186
        CM_BoxLeafnums_r( &ll, 0 );
 
187
 
 
188
        *lastLeaf = ll.lastLeaf;
 
189
        return ll.count;
 
190
}
 
191
 
 
192
/*
 
193
==================
 
194
CM_BoxBrushes
 
195
==================
 
196
*/
 
197
int CM_BoxBrushes( const vec3_t mins, const vec3_t maxs, cbrush_t **list, int listsize ) {
 
198
        leafList_t      ll;
 
199
 
 
200
        cm.checkcount++;
 
201
 
 
202
        VectorCopy( mins, ll.bounds[0] );
 
203
        VectorCopy( maxs, ll.bounds[1] );
 
204
        ll.count = 0;
 
205
        ll.maxcount = listsize;
 
206
        ll.list = (void *)list;
 
207
        ll.storeLeafs = CM_StoreBrushes;
 
208
        ll.lastLeaf = 0;
 
209
        ll.overflowed = qfalse;
 
210
        
 
211
        CM_BoxLeafnums_r( &ll, 0 );
 
212
 
 
213
        return ll.count;
 
214
}
 
215
 
 
216
 
 
217
//====================================================================
 
218
 
 
219
 
 
220
/*
 
221
==================
 
222
CM_PointContents
 
223
 
 
224
==================
 
225
*/
 
226
int CM_PointContents( const vec3_t p, clipHandle_t model ) {
 
227
        int                     leafnum;
 
228
        int                     i, k;
 
229
        int                     brushnum;
 
230
        cLeaf_t         *leaf;
 
231
        cbrush_t        *b;
 
232
        int                     contents;
 
233
        float           d;
 
234
        cmodel_t        *clipm;
 
235
 
 
236
        if (!cm.numNodes) {     // map not loaded
 
237
                return 0;
 
238
        }
 
239
 
 
240
        if ( model ) {
 
241
                clipm = CM_ClipHandleToModel( model );
 
242
                leaf = &clipm->leaf;
 
243
        } else {
 
244
                leafnum = CM_PointLeafnum_r (p, 0);
 
245
                leaf = &cm.leafs[leafnum];
 
246
        }
 
247
 
 
248
        contents = 0;
 
249
        for (k=0 ; k<leaf->numLeafBrushes ; k++) {
 
250
                brushnum = cm.leafbrushes[leaf->firstLeafBrush+k];
 
251
                b = &cm.brushes[brushnum];
 
252
 
 
253
                // see if the point is in the brush
 
254
                for ( i = 0 ; i < b->numsides ; i++ ) {
 
255
                        d = DotProduct( p, b->sides[i].plane->normal );
 
256
// FIXME test for Cash
 
257
//                      if ( d >= b->sides[i].plane->dist ) {
 
258
                        if ( d > b->sides[i].plane->dist ) {
 
259
                                break;
 
260
                        }
 
261
                }
 
262
 
 
263
                if ( i == b->numsides ) {
 
264
                        contents |= b->contents;
 
265
                }
 
266
        }
 
267
 
 
268
        return contents;
 
269
}
 
270
 
 
271
/*
 
272
==================
 
273
CM_TransformedPointContents
 
274
 
 
275
Handles offseting and rotation of the end points for moving and
 
276
rotating entities
 
277
==================
 
278
*/
 
279
int     CM_TransformedPointContents( const vec3_t p, clipHandle_t model, const vec3_t origin, const vec3_t angles) {
 
280
        vec3_t          p_l;
 
281
        vec3_t          temp;
 
282
        vec3_t          forward, right, up;
 
283
 
 
284
        // subtract origin offset
 
285
        VectorSubtract (p, origin, p_l);
 
286
 
 
287
        // rotate start and end into the models frame of reference
 
288
        if ( model != BOX_MODEL_HANDLE && 
 
289
        (angles[0] || angles[1] || angles[2]) )
 
290
        {
 
291
                AngleVectors (angles, forward, right, up);
 
292
 
 
293
                VectorCopy (p_l, temp);
 
294
                p_l[0] = DotProduct (temp, forward);
 
295
                p_l[1] = -DotProduct (temp, right);
 
296
                p_l[2] = DotProduct (temp, up);
 
297
        }
 
298
 
 
299
        return CM_PointContents( p_l, model );
 
300
}
 
301
 
 
302
 
 
303
 
 
304
/*
 
305
===============================================================================
 
306
 
 
307
PVS
 
308
 
 
309
===============================================================================
 
310
*/
 
311
 
 
312
byte    *CM_ClusterPVS (int cluster) {
 
313
        if (cluster < 0 || cluster >= cm.numClusters || !cm.vised ) {
 
314
                return cm.visibility;
 
315
        }
 
316
 
 
317
        return cm.visibility + cluster * cm.clusterBytes;
 
318
}
 
319
 
 
320
 
 
321
 
 
322
/*
 
323
===============================================================================
 
324
 
 
325
AREAPORTALS
 
326
 
 
327
===============================================================================
 
328
*/
 
329
 
 
330
void CM_FloodArea_r( int areaNum, int floodnum) {
 
331
        int             i;
 
332
        cArea_t *area;
 
333
        int             *con;
 
334
 
 
335
        area = &cm.areas[ areaNum ];
 
336
 
 
337
        if ( area->floodvalid == cm.floodvalid ) {
 
338
                if (area->floodnum == floodnum)
 
339
                        return;
 
340
                Com_Error (ERR_DROP, "FloodArea_r: reflooded");
 
341
        }
 
342
 
 
343
        area->floodnum = floodnum;
 
344
        area->floodvalid = cm.floodvalid;
 
345
        con = cm.areaPortals + areaNum * cm.numAreas;
 
346
        for ( i=0 ; i < cm.numAreas  ; i++ ) {
 
347
                if ( con[i] > 0 ) {
 
348
                        CM_FloodArea_r( i, floodnum );
 
349
                }
 
350
        }
 
351
}
 
352
 
 
353
/*
 
354
====================
 
355
CM_FloodAreaConnections
 
356
 
 
357
====================
 
358
*/
 
359
void    CM_FloodAreaConnections( void ) {
 
360
        int             i;
 
361
        cArea_t *area;
 
362
        int             floodnum;
 
363
 
 
364
        // all current floods are now invalid
 
365
        cm.floodvalid++;
 
366
        floodnum = 0;
 
367
 
 
368
        for (i = 0 ; i < cm.numAreas ; i++) {
 
369
                area = &cm.areas[i];
 
370
                if (area->floodvalid == cm.floodvalid) {
 
371
                        continue;               // already flooded into
 
372
                }
 
373
                floodnum++;
 
374
                CM_FloodArea_r (i, floodnum);
 
375
        }
 
376
 
 
377
}
 
378
 
 
379
/*
 
380
====================
 
381
CM_AdjustAreaPortalState
 
382
 
 
383
====================
 
384
*/
 
385
void    CM_AdjustAreaPortalState( int area1, int area2, qboolean open ) {
 
386
        if ( area1 < 0 || area2 < 0 ) {
 
387
                return;
 
388
        }
 
389
 
 
390
        if ( area1 >= cm.numAreas || area2 >= cm.numAreas ) {
 
391
                Com_Error (ERR_DROP, "CM_ChangeAreaPortalState: bad area number");
 
392
        }
 
393
 
 
394
        if ( open ) {
 
395
                cm.areaPortals[ area1 * cm.numAreas + area2 ]++;
 
396
                cm.areaPortals[ area2 * cm.numAreas + area1 ]++;
 
397
        } else {
 
398
                cm.areaPortals[ area1 * cm.numAreas + area2 ]--;
 
399
                cm.areaPortals[ area2 * cm.numAreas + area1 ]--;
 
400
                if ( cm.areaPortals[ area2 * cm.numAreas + area1 ] < 0 ) {
 
401
                        Com_Error (ERR_DROP, "CM_AdjustAreaPortalState: negative reference count");
 
402
                }
 
403
        }
 
404
 
 
405
        CM_FloodAreaConnections ();
 
406
}
 
407
 
 
408
/*
 
409
====================
 
410
CM_AreasConnected
 
411
 
 
412
====================
 
413
*/
 
414
qboolean        CM_AreasConnected( int area1, int area2 ) {
 
415
#ifndef BSPC
 
416
        if ( cm_noAreas->integer ) {
 
417
                return qtrue;
 
418
        }
 
419
#endif
 
420
 
 
421
        if ( area1 < 0 || area2 < 0 ) {
 
422
                return qfalse;
 
423
        }
 
424
 
 
425
        if (area1 >= cm.numAreas || area2 >= cm.numAreas) {
 
426
                Com_Error (ERR_DROP, "area >= cm.numAreas");
 
427
        }
 
428
 
 
429
        if (cm.areas[area1].floodnum == cm.areas[area2].floodnum) {
 
430
                return qtrue;
 
431
        }
 
432
        return qfalse;
 
433
}
 
434
 
 
435
 
 
436
/*
 
437
=================
 
438
CM_WriteAreaBits
 
439
 
 
440
Writes a bit vector of all the areas
 
441
that are in the same flood as the area parameter
 
442
Returns the number of bytes needed to hold all the bits.
 
443
 
 
444
The bits are OR'd in, so you can CM_WriteAreaBits from multiple
 
445
viewpoints and get the union of all visible areas.
 
446
 
 
447
This is used to cull non-visible entities from snapshots
 
448
=================
 
449
*/
 
450
int CM_WriteAreaBits (byte *buffer, int area)
 
451
{
 
452
        int             i;
 
453
        int             floodnum;
 
454
        int             bytes;
 
455
 
 
456
        bytes = (cm.numAreas+7)>>3;
 
457
 
 
458
#ifndef BSPC
 
459
        if (cm_noAreas->integer || area == -1)
 
460
#else
 
461
        if ( area == -1)
 
462
#endif
 
463
        {       // for debugging, send everything
 
464
                Com_Memset (buffer, 255, bytes);
 
465
        }
 
466
        else
 
467
        {
 
468
                floodnum = cm.areas[area].floodnum;
 
469
                for (i=0 ; i<cm.numAreas ; i++)
 
470
                {
 
471
                        if (cm.areas[i].floodnum == floodnum || area == -1)
 
472
                                buffer[i>>3] |= 1<<(i&7);
 
473
                }
 
474
        }
 
475
 
 
476
        return bytes;
 
477
}
 
478