← Back to branch summary

~ubuntu-branches/ubuntu/natty/alien-arena/natty

« back to all changes in this revision

Viewing changes to source/utils3/common/polylib.c

  • Committer: Bazaar Package Importer
  • Author(s): Andres Mejia, Barry deFreese, Ansgar Burchardt, Gonéri Le Bouder, Andres Mejia
  • Date: 2008-04-18 17:43:24 UTC
  • mfrom: (1.1.2 upstream) (3.1.1 hardy)
  • Revision ID: james.westby@ubuntu.com-20080418174324-si1umi8dngglaha4
Tags: 7.0-1
http://bugs.debian.org/453555
http://bugs.debian.org/457700
[ Barry deFreese ]
* Escape - in alien-arena-server.6.
* Add myself to uploaders.

[ Ansgar Burchardt ]
* Remove deprecated Encoding key from .desktop file.

[ Gonéri Le Bouder ]
* Remove Homepage from package description.

[ Andres Mejia ]
* New upstream release.
* Removing XS- part for Vcs-* lines.
* Removing +ssh part of Vcs-Svn line.
* Bumped to Standards-Version 3.7.3.
* Test for existence of *-stamp stamps before removing them.
* Removed Encoding field in desktop file.
* Modify patch for upstream Makefile to make Makefile more useful in building
  Debian packages.
  + Also fixes problem not detecting the existence of libcurl.
* Remove debug packages for release. Will support nostrip option instead.
* Add description for fix-CVE-2007-4754-CVE-2007-4755.dpatch, silences
  lintian warning.
* Add new link for watchfile.
  + Closes: #453555
* Moved debian/scripts/alien-arena-tarball.sh to
  debian/alien-arena-get-orig-source.
* Modified alien-arena-data-get-orig-source to make it easier to maintain.
* Switched from dpatch to quilt.
* Cut down package description.
* Closing bug about mouse constantly looking up. The submitter could not
  reproduce the bug after deleting the ~/.alien-arena directory.
  + Closes: #457700
* Updated copyright file for new release.
* Updated README.Debian files.
* Adding new images for icons. Need build dependency on sharutils.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/utils3/common/polylib.c
 
1
#ifdef _DEBUG
 
2
#define _CRTDBG_MAP_ALLOC
 
3
#undef THIS_FILE
 
4
static char THIS_FILE[] = __FILE__;
 
5
#endif
 
6
 
 
7
#include "cmdlib.h"
 
8
#include "mathlib.h"
 
9
#include "polylib.h"
 
10
 
 
11
 
 
12
extern int numthreads;
 
13
 
 
14
// counters are only bumped when running single threaded,
 
15
// because they are an awefull coherence problem
 
16
int     c_active_windings;
 
17
int     c_peak_windings;
 
18
int     c_winding_allocs;
 
19
int     c_winding_points;
 
20
 
 
21
#define BOGUS_RANGE     8192
 
22
 
 
23
void pw(winding_t *w)
 
24
{
 
25
        int             i;
 
26
        for (i=0 ; i<w->numpoints ; i++)
 
27
                printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
 
28
}
 
29
 
 
30
 
 
31
/*
 
32
=============
 
33
AllocWinding
 
34
=============
 
35
*/
 
36
winding_t       *AllocWinding (int points)
 
37
{
 
38
        winding_t       *w;
 
39
        int                     s;
 
40
 
 
41
        if (numthreads == 1)
 
42
        {
 
43
                c_winding_allocs++;
 
44
                c_winding_points += points;
 
45
                c_active_windings++;
 
46
                if (c_active_windings > c_peak_windings)
 
47
                        c_peak_windings = c_active_windings;
 
48
        }
 
49
 
 
50
        s = sizeof(vec_t)*3*points + sizeof(int);
 
51
 
 
52
        w = malloc (s);
 
53
 
 
54
        memset (w, 0, s); 
 
55
 
 
56
        return w;
 
57
}
 
58
 
 
59
void FreeWinding (winding_t *w)
 
60
{
 
61
        if (*(unsigned *)w == 0xdeaddead)
 
62
                Error ("FreeWinding: freed a freed winding");
 
63
        *(unsigned *)w = 0xdeaddead;
 
64
 
 
65
        if (numthreads == 1)
 
66
                c_active_windings--;
 
67
 
 
68
        free (w);
 
69
}
 
70
 
 
71
/*
 
72
============
 
73
RemoveColinearPoints
 
74
============
 
75
*/
 
76
int     c_removed;
 
77
 
 
78
void    RemoveColinearPoints (winding_t *w)
 
79
{
 
80
        int             i, j, k;
 
81
        vec3_t  v1, v2;
 
82
        int             nump;
 
83
        vec3_t  p[MAX_POINTS_ON_WINDING];
 
84
 
 
85
        nump = 0;
 
86
        for (i=0 ; i<w->numpoints ; i++)
 
87
        {
 
88
                j = (i+1)%w->numpoints;
 
89
                k = (i+w->numpoints-1)%w->numpoints;
 
90
                VectorSubtract (w->p[j], w->p[i], v1);
 
91
                VectorSubtract (w->p[i], w->p[k], v2);
 
92
                VectorNormalize(v1,v1);
 
93
                VectorNormalize(v2,v2);
 
94
                if (DotProduct(v1, v2) < 0.999)
 
95
                {
 
96
                        VectorCopy (w->p[i], p[nump]);
 
97
                        nump++;
 
98
                }
 
99
        }
 
100
 
 
101
        if (nump == w->numpoints)
 
102
                return;
 
103
 
 
104
        if (numthreads == 1)
 
105
                c_removed += w->numpoints - nump;
 
106
        w->numpoints = nump;
 
107
        memcpy (w->p, p, nump*sizeof(p[0]));
 
108
}
 
109
 
 
110
/*
 
111
============
 
112
WindingPlane
 
113
============
 
114
*/
 
115
void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
 
116
{
 
117
        vec3_t  v1, v2;
 
118
 
 
119
        VectorSubtract (w->p[1], w->p[0], v1);
 
120
        VectorSubtract (w->p[2], w->p[0], v2);
 
121
        CrossProduct (v2, v1, normal);
 
122
        VectorNormalize (normal, normal);
 
123
        *dist = DotProduct (w->p[0], normal);
 
124
 
 
125
}
 
126
 
 
127
/*
 
128
=============
 
129
WindingArea
 
130
=============
 
131
*/
 
132
vec_t   WindingArea (winding_t *w)
 
133
{
 
134
        int             i;
 
135
        vec3_t  d1, d2, cross;
 
136
        vec_t   total;
 
137
 
 
138
        total = 0;
 
139
        for (i=2 ; i<w->numpoints ; i++)
 
140
        {
 
141
                VectorSubtract (w->p[i-1], w->p[0], d1);
 
142
                VectorSubtract (w->p[i], w->p[0], d2);
 
143
                CrossProduct (d1, d2, cross);
 
144
                total += 0.5 * VectorLength ( cross );
 
145
        }
 
146
        return total;
 
147
}
 
148
 
 
149
void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
 
150
{
 
151
        vec_t   v;
 
152
        int             i,j;
 
153
 
 
154
        mins[0] = mins[1] = mins[2] = 99999;
 
155
        maxs[0] = maxs[1] = maxs[2] = -99999;
 
156
 
 
157
        for (i=0 ; i<w->numpoints ; i++)
 
158
        {
 
159
                for (j=0 ; j<3 ; j++)
 
160
                {
 
161
                        v = w->p[i][j];
 
162
                        if (v < mins[j])
 
163
                                mins[j] = v;
 
164
                        if (v > maxs[j])
 
165
                                maxs[j] = v;
 
166
                }
 
167
        }
 
168
}
 
169
 
 
170
/*
 
171
=============
 
172
WindingCenter
 
173
=============
 
174
*/
 
175
void    WindingCenter (winding_t *w, vec3_t center)
 
176
{
 
177
        int             i;
 
178
        float   scale;
 
179
 
 
180
        VectorCopy (vec3_origin, center);
 
181
        for (i=0 ; i<w->numpoints ; i++)
 
182
                VectorAdd (w->p[i], center, center);
 
183
 
 
184
        scale = 1.0/w->numpoints;
 
185
        VectorScale (center, scale, center);
 
186
}
 
187
 
 
188
/*
 
189
=================
 
190
BaseWindingForPlane
 
191
=================
 
192
*/
 
193
winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
 
194
{
 
195
        int             i, x;
 
196
        vec_t   max, v;
 
197
        vec3_t  org, vright, vup;
 
198
        winding_t       *w;
 
199
        
 
200
// find the major axis
 
201
 
 
202
        max = -BOGUS_RANGE;
 
203
        x = -1;
 
204
        for (i=0 ; i<3; i++)
 
205
        {
 
206
                v = fabs(normal[i]);
 
207
                if (v > max)
 
208
                {
 
209
                        x = i;
 
210
                        max = v;
 
211
                }
 
212
        }
 
213
        if (x==-1)
 
214
                Error ("BaseWindingForPlane: no axis found");
 
215
                
 
216
        VectorCopy (vec3_origin, vup);  
 
217
        switch (x)
 
218
        {
 
219
        case 0:
 
220
        case 1:
 
221
                vup[2] = 1;
 
222
                break;          
 
223
        case 2:
 
224
                vup[0] = 1;
 
225
                break;          
 
226
        }
 
227
 
 
228
        v = DotProduct (vup, normal);
 
229
        VectorMA (vup, -v, normal, vup);
 
230
        VectorNormalize (vup, vup);
 
231
                
 
232
        VectorScale (normal, dist, org);
 
233
        
 
234
        CrossProduct (vup, normal, vright);
 
235
        
 
236
        VectorScale (vup, 8192, vup);
 
237
        VectorScale (vright, 8192, vright);
 
238
 
 
239
// project a really big axis aligned box onto the plane
 
240
        w = AllocWinding (4);
 
241
        
 
242
        VectorSubtract (org, vright, w->p[0]);
 
243
        VectorAdd (w->p[0], vup, w->p[0]);
 
244
        
 
245
        VectorAdd (org, vright, w->p[1]);
 
246
        VectorAdd (w->p[1], vup, w->p[1]);
 
247
        
 
248
        VectorAdd (org, vright, w->p[2]);
 
249
        VectorSubtract (w->p[2], vup, w->p[2]);
 
250
        
 
251
        VectorSubtract (org, vright, w->p[3]);
 
252
        VectorSubtract (w->p[3], vup, w->p[3]);
 
253
        
 
254
        w->numpoints = 4;
 
255
        
 
256
        return w;       
 
257
}
 
258
 
 
259
/*
 
260
==================
 
261
CopyWinding
 
262
==================
 
263
*/
 
264
winding_t       *CopyWinding (winding_t *w)
 
265
{
 
266
        int                     size;
 
267
        winding_t       *c;
 
268
 
 
269
        c = AllocWinding (w->numpoints);
 
270
        size = (int)((winding_t *)0)->p[w->numpoints];
 
271
        memcpy (c, w, size);
 
272
 
 
273
        return c;
 
274
}
 
275
 
 
276
/*
 
277
==================
 
278
ReverseWinding
 
279
==================
 
280
*/
 
281
winding_t       *ReverseWinding (winding_t *w)
 
282
{
 
283
        int                     i;
 
284
        winding_t       *c;
 
285
 
 
286
        c = AllocWinding (w->numpoints);
 
287
        for (i=0 ; i<w->numpoints ; i++)
 
288
        {
 
289
                VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
 
290
        }
 
291
 
 
292
        c->numpoints = w->numpoints;
 
293
        
 
294
        return c;
 
295
}
 
296
 
 
297
 
 
298
/*
 
299
=============
 
300
ClipWindingEpsilon
 
301
=============
 
302
*/
 
303
void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 
 
304
                                vec_t epsilon, winding_t **front, winding_t **back)
 
305
{
 
306
        vec_t   dists[MAX_POINTS_ON_WINDING+4];
 
307
        int             sides[MAX_POINTS_ON_WINDING+4];
 
308
        int             counts[3];
 
309
        static  vec_t   dot;            // VC 4.2 optimizer bug if not static
 
310
        int             i, j;
 
311
        vec_t   *p1, *p2;
 
312
        vec3_t  mid;
 
313
        winding_t       *f, *b;
 
314
        int             maxpts;
 
315
        
 
316
        counts[0] = counts[1] = counts[2] = 0;
 
317
 
 
318
// determine sides for each point
 
319
        for (i=0 ; i<in->numpoints ; i++)
 
320
        {
 
321
                dot = DotProduct (in->p[i], normal);
 
322
                dot -= dist;
 
323
                dists[i] = dot;
 
324
                if (dot > epsilon)
 
325
                        sides[i] = SIDE_FRONT;
 
326
                else if (dot < -epsilon)
 
327
                        sides[i] = SIDE_BACK;
 
328
                else
 
329
                {
 
330
                        sides[i] = SIDE_ON;
 
331
                }
 
332
                counts[sides[i]]++;
 
333
        }
 
334
        sides[i] = sides[0];
 
335
        dists[i] = dists[0];
 
336
        
 
337
        *front = *back = NULL;
 
338
 
 
339
        if (!counts[0])
 
340
        {
 
341
                *back = CopyWinding (in);
 
342
                return;
 
343
        }
 
344
        if (!counts[1])
 
345
        {
 
346
                *front = CopyWinding (in);
 
347
                return;
 
348
        }
 
349
 
 
350
        maxpts = in->numpoints+4;       // cant use counts[0]+2 because
 
351
                                                                // of fp grouping errors
 
352
 
 
353
        *front = f = AllocWinding (maxpts);
 
354
        *back = b = AllocWinding (maxpts);
 
355
                
 
356
        for (i=0 ; i<in->numpoints ; i++)
 
357
        {
 
358
                p1 = in->p[i];
 
359
                
 
360
                if (sides[i] == SIDE_ON)
 
361
                {
 
362
                        VectorCopy (p1, f->p[f->numpoints]);
 
363
                        f->numpoints++;
 
364
                        VectorCopy (p1, b->p[b->numpoints]);
 
365
                        b->numpoints++;
 
366
                        continue;
 
367
                }
 
368
        
 
369
                if (sides[i] == SIDE_FRONT)
 
370
                {
 
371
                        VectorCopy (p1, f->p[f->numpoints]);
 
372
                        f->numpoints++;
 
373
                }
 
374
                if (sides[i] == SIDE_BACK)
 
375
                {
 
376
                        VectorCopy (p1, b->p[b->numpoints]);
 
377
                        b->numpoints++;
 
378
                }
 
379
 
 
380
                if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 
381
                        continue;
 
382
                        
 
383
        // generate a split point
 
384
                p2 = in->p[(i+1)%in->numpoints];
 
385
                
 
386
                dot = dists[i] / (dists[i]-dists[i+1]);
 
387
                for (j=0 ; j<3 ; j++)
 
388
                {       // avoid round off error when possible
 
389
                        if (normal[j] == 1)
 
390
                                mid[j] = dist;
 
391
                        else if (normal[j] == -1)
 
392
                                mid[j] = -dist;
 
393
                        else
 
394
                                mid[j] = p1[j] + dot*(p2[j]-p1[j]);
 
395
                }
 
396
                        
 
397
                VectorCopy (mid, f->p[f->numpoints]);
 
398
                f->numpoints++;
 
399
                VectorCopy (mid, b->p[b->numpoints]);
 
400
                b->numpoints++;
 
401
        }
 
402
        
 
403
        if (f->numpoints > maxpts || b->numpoints > maxpts)
 
404
                Error ("ClipWinding: points exceeded estimate");
 
405
        if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
 
406
                Error ("ClipWinding: MAX_POINTS_ON_WINDING");
 
407
}
 
408
 
 
409
 
 
410
/*
 
411
=============
 
412
ChopWindingInPlace
 
413
=============
 
414
*/
 
415
extern int cur_root;
 
416
void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
 
417
{
 
418
        winding_t       *in;
 
419
        vec_t   dists[MAX_POINTS_ON_WINDING+4];
 
420
        int             sides[MAX_POINTS_ON_WINDING+4];
 
421
        int             counts[3];
 
422
        static  vec_t   dot;            // VC 4.2 optimizer bug if not static
 
423
        int             i, j;
 
424
        vec_t   *p1, *p2;
 
425
        vec3_t  mid;
 
426
        winding_t       *f;
 
427
        int             maxpts;
 
428
 
 
429
        in = *inout;
 
430
        counts[0] = counts[1] = counts[2] = 0;
 
431
 
 
432
// determine sides for each point
 
433
        for (i=0 ; i<in->numpoints ; i++)
 
434
        {
 
435
                dot = DotProduct (in->p[i], normal);
 
436
                dot -= dist;
 
437
                dists[i] = dot;
 
438
                if (dot > epsilon)
 
439
                {
 
440
                        sides[i] = SIDE_FRONT;
 
441
                }
 
442
                else if (dot < -epsilon)
 
443
                {
 
444
                        sides[i] = SIDE_BACK;
 
445
                }
 
446
                else
 
447
                {
 
448
                        sides[i] = SIDE_ON;
 
449
                }
 
450
                counts[sides[i]]++;
 
451
        }
 
452
        sides[i] = sides[0];
 
453
        dists[i] = dists[0];
 
454
        
 
455
        if (!counts[0])
 
456
        {
 
457
                FreeWinding (in);
 
458
                *inout = NULL;
 
459
                return;
 
460
        }
 
461
        if (!counts[1])
 
462
        {
 
463
                return;         // inout stays the same
 
464
        }
 
465
 
 
466
        maxpts = in->numpoints+4;       // cant use counts[0]+2 because
 
467
 
 
468
 
 
469
        f = AllocWinding (maxpts);
 
470
                
 
471
        for (i=0 ; i<in->numpoints ; i++)
 
472
        {
 
473
                p1 = in->p[i];
 
474
                
 
475
                if (sides[i] == SIDE_ON)
 
476
                {
 
477
                        VectorCopy (p1, f->p[f->numpoints]);
 
478
                        f->numpoints++;
 
479
                        continue;
 
480
                }
 
481
        
 
482
                if (sides[i] == SIDE_FRONT)
 
483
                {
 
484
                        VectorCopy (p1, f->p[f->numpoints]);
 
485
                        f->numpoints++;
 
486
                }
 
487
 
 
488
                if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 
489
                {
 
490
 
 
491
                        continue;
 
492
                }
 
493
                        
 
494
        // generate a split point
 
495
                p2 = in->p[(i+1)%in->numpoints];
 
496
                
 
497
                dot = dists[i] / (dists[i]-dists[i+1]);
 
498
                for (j=0 ; j<3 ; j++)
 
499
                {       // avoid round off error when possible
 
500
                        if (normal[j] >= 1)
 
501
                                mid[j] = dist;
 
502
                        else if (normal[j] <= -1)
 
503
                                mid[j] = -dist;
 
504
                        else
 
505
                                mid[j] = p1[j] + dot*(p2[j]-p1[j]);
 
506
                }
 
507
                        
 
508
                VectorCopy (mid, f->p[f->numpoints]);
 
509
                f->numpoints++;
 
510
        }
 
511
        
 
512
        if (f->numpoints > maxpts)
 
513
                Error ("ClipWinding: points exceeded estimate");
 
514
        if (f->numpoints > MAX_POINTS_ON_WINDING)
 
515
                Error ("ClipWinding: MAX_POINTS_ON_WINDING");
 
516
 
 
517
        FreeWinding (in);
 
518
        *inout = f;
 
519
}
 
520
 
 
521
 
 
522
/*
 
523
=================
 
524
ChopWinding
 
525
 
 
526
Returns the fragment of in that is on the front side
 
527
of the cliping plane.  The original is freed.
 
528
=================
 
529
*/
 
530
winding_t       *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
 
531
{
 
532
        winding_t       *f, *b;
 
533
 
 
534
        ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
 
535
        FreeWinding (in);
 
536
        if (b)
 
537
                FreeWinding (b);
 
538
        return f;
 
539
}
 
540
 
 
541
 
 
542
/*
 
543
=================
 
544
CheckWinding
 
545
 
 
546
=================
 
547
*/
 
548
void CheckWinding (winding_t *w)
 
549
{
 
550
        int             i, j;
 
551
        vec_t   *p1, *p2;
 
552
        vec_t   d, edgedist;
 
553
        vec3_t  dir, edgenormal, facenormal;
 
554
        vec_t   area;
 
555
        vec_t   facedist;
 
556
 
 
557
        if (w->numpoints < 3)
 
558
                Error ("CheckWinding: %i points",w->numpoints);
 
559
        
 
560
        area = WindingArea(w);
 
561
        if (area < 1)
 
562
                Error ("CheckWinding: %f area", area);
 
563
 
 
564
        WindingPlane (w, facenormal, &facedist);
 
565
        
 
566
        for (i=0 ; i<w->numpoints ; i++)
 
567
        {
 
568
                p1 = w->p[i];
 
569
 
 
570
                for (j=0 ; j<3 ; j++)
 
571
                        if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
 
572
                                Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
 
573
 
 
574
                j = i+1 == w->numpoints ? 0 : i+1;
 
575
                
 
576
        // check the point is on the face plane
 
577
                d = DotProduct (p1, facenormal) - facedist;
 
578
                if (d < -ON_EPSILON || d > ON_EPSILON)
 
579
                        Error ("CheckWinding: point off plane");
 
580
        
 
581
        // check the edge isnt degenerate
 
582
                p2 = w->p[j];
 
583
                VectorSubtract (p2, p1, dir);
 
584
                
 
585
                if (VectorLength (dir) < ON_EPSILON)
 
586
                        Error ("CheckWinding: degenerate edge");
 
587
                        
 
588
                CrossProduct (facenormal, dir, edgenormal);
 
589
                VectorNormalize (edgenormal, edgenormal);
 
590
                edgedist = DotProduct (p1, edgenormal);
 
591
                edgedist += ON_EPSILON;
 
592
                
 
593
        // all other points must be on front side
 
594
                for (j=0 ; j<w->numpoints ; j++)
 
595
                {
 
596
                        if (j == i)
 
597
                                continue;
 
598
                        d = DotProduct (w->p[j], edgenormal);
 
599
                        if (d > edgedist)
 
600
                                Error ("CheckWinding: non-convex");
 
601
                }
 
602
        }
 
603
}
 
604
 
 
605
 
 
606
/*
 
607
============
 
608
WindingOnPlaneSide
 
609
============
 
610
*/
 
611
int             WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
 
612
{
 
613
        qboolean        front, back;
 
614
        int                     i;
 
615
        vec_t           d;
 
616
 
 
617
        front = false;
 
618
        back = false;
 
619
        for (i=0 ; i<w->numpoints ; i++)
 
620
        {
 
621
                d = DotProduct (w->p[i], normal) - dist;
 
622
                if (d < -ON_EPSILON)
 
623
                {
 
624
                        if (front)
 
625
                                return SIDE_CROSS;
 
626
                        back = true;
 
627
                        continue;
 
628
                }
 
629
                if (d > ON_EPSILON)
 
630
                {
 
631
                        if (back)
 
632
                                return SIDE_CROSS;
 
633
                        front = true;
 
634
                        continue;
 
635
                }
 
636
        }
 
637
 
 
638
        if (back)
 
639
                return SIDE_BACK;
 
640
        if (front)
 
641
                return SIDE_FRONT;
 
642
        return SIDE_ON;
 
643
}
 
644