b62d12ff34f762071ec6d5d17241546a54c034a3
[divverent/netradiant.git] / tools / quake3 / common / polylib.c
1 /*
2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 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 GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22
23 #include "cmdlib.h"
24 #include "mathlib.h"
25 #include "inout.h"
26 #include "polylib.h"
27 #include "qfiles.h"
28
29
30 extern int numthreads;
31
32 // counters are only bumped when running single threaded,
33 // because they are an awefull coherence problem
34 int     c_active_windings;
35 int     c_peak_windings;
36 int     c_winding_allocs;
37 int     c_winding_points;
38
39 #define BOGUS_RANGE     WORLD_SIZE
40
41 void pw(winding_t *w)
42 {
43         int             i;
44         for (i=0 ; i<w->numpoints ; i++)
45                 Sys_Printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
46 }
47
48
49 /*
50 =============
51 AllocWinding
52 =============
53 */
54 winding_t       *AllocWinding (int points)
55 {
56         winding_t       *w;
57         int                     s;
58
59   if (points >= MAX_POINTS_ON_WINDING)
60     Error ("AllocWinding failed: MAX_POINTS_ON_WINDING exceeded");
61
62         if (numthreads == 1)
63         {
64                 c_winding_allocs++;
65                 c_winding_points += points;
66                 c_active_windings++;
67                 if (c_active_windings > c_peak_windings)
68                         c_peak_windings = c_active_windings;
69         }
70         s = sizeof(vec_t)*3*points + sizeof(int);
71         w = safe_malloc (s);
72         memset (w, 0, s); 
73         return w;
74 }
75
76 void FreeWinding (winding_t *w)
77 {
78         if (*(unsigned *)w == 0xdeaddead)
79                 Error ("FreeWinding: freed a freed winding");
80         *(unsigned *)w = 0xdeaddead;
81
82         if (numthreads == 1)
83                 c_active_windings--;
84         free (w);
85 }
86
87 /*
88 ============
89 RemoveColinearPoints
90 ============
91 */
92 int     c_removed;
93
94 void    RemoveColinearPoints (winding_t *w)
95 {
96         int             i, j, k;
97         vec3_t  v1, v2;
98         int             nump;
99         vec3_t  p[MAX_POINTS_ON_WINDING];
100
101         nump = 0;
102         for (i=0 ; i<w->numpoints ; i++)
103         {
104                 j = (i+1)%w->numpoints;
105                 k = (i+w->numpoints-1)%w->numpoints;
106                 VectorSubtract (w->p[j], w->p[i], v1);
107                 VectorSubtract (w->p[i], w->p[k], v2);
108                 VectorNormalize(v1,v1);
109                 VectorNormalize(v2,v2);
110                 if (DotProduct(v1, v2) < 0.999)
111                 {
112                         VectorCopy (w->p[i], p[nump]);
113                         nump++;
114                 }
115         }
116
117         if (nump == w->numpoints)
118                 return;
119
120         if (numthreads == 1)
121                 c_removed += w->numpoints - nump;
122         w->numpoints = nump;
123         memcpy (w->p, p, nump*sizeof(p[0]));
124 }
125
126 /*
127 ============
128 WindingPlane
129 ============
130 */
131 void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
132 {
133         vec3_t  v1, v2;
134
135         VectorSubtract (w->p[1], w->p[0], v1);
136         VectorSubtract (w->p[2], w->p[0], v2);
137         CrossProduct (v2, v1, normal);
138         VectorNormalize (normal, normal);
139         *dist = DotProduct (w->p[0], normal);
140
141 }
142
143 /*
144 =============
145 WindingArea
146 =============
147 */
148 vec_t   WindingArea (winding_t *w)
149 {
150         int             i;
151         vec3_t  d1, d2, cross;
152         vec_t   total;
153
154         total = 0;
155         for (i=2 ; i<w->numpoints ; i++)
156         {
157                 VectorSubtract (w->p[i-1], w->p[0], d1);
158                 VectorSubtract (w->p[i], w->p[0], d2);
159                 CrossProduct (d1, d2, cross);
160                 total += 0.5 * VectorLength ( cross );
161         }
162         return total;
163 }
164
165 void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
166 {
167         vec_t   v;
168         int             i,j;
169
170         mins[0] = mins[1] = mins[2] = 99999;
171         maxs[0] = maxs[1] = maxs[2] = -99999;
172
173         for (i=0 ; i<w->numpoints ; i++)
174         {
175                 for (j=0 ; j<3 ; j++)
176                 {
177                         v = w->p[i][j];
178                         if (v < mins[j])
179                                 mins[j] = v;
180                         if (v > maxs[j])
181                                 maxs[j] = v;
182                 }
183         }
184 }
185
186 /*
187 =============
188 WindingCenter
189 =============
190 */
191 void    WindingCenter (winding_t *w, vec3_t center)
192 {
193         int             i;
194         float   scale;
195
196         VectorCopy (vec3_origin, center);
197         for (i=0 ; i<w->numpoints ; i++)
198                 VectorAdd (w->p[i], center, center);
199
200         scale = 1.0/w->numpoints;
201         VectorScale (center, scale, center);
202 }
203
204 /*
205 =================
206 BaseWindingForPlane
207 =================
208 */
209 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
210 {
211         // The goal in this function is to replicate the exact behavior that was in the original
212         // BaseWindingForPlane() function (see below).  The only thing we're going to change is the
213         // accuracy of the operation.  The original code gave a preference for the vup vector to start
214         // out as (0, 0, 1), unless the normal had a dominant Z value, in which case vup started out
215         // as (1, 0, 0).  After that, vup was "bent" [along the plane defined by normal and vup] to
216         // become perpendicular to normal.  After that the vright vector was computed as the cross
217         // product of vup and normal.
218
219         // Once these vectors are calculated, I'm constructing the winding points in exactly the same
220         // way as was done in the original function.  Orientation is the same.
221
222         // Note that the 4 points in the returned winding_t may actually not be necessary (3 might
223         // be enough).  However, I want to minimize the chance of ANY bugs popping up due to any
224         // change in behavior of this function.  Therefore, behavior stays exactly the same, except
225         // for precision of math.  Performance might be better in the new function as well.
226
227         int             x, i;
228         vec_t           max, v;
229         vec3_t          vright, vup, org;
230         winding_t       *w;
231
232         max = -BOGUS_RANGE;
233         x = -1;
234         for (i = 0; i < 3; i++) {
235                 v = fabs(normal[i]);
236                 if (v > max) {
237                         x = i;
238                         max = v;
239                 }
240         }
241         if (x == -1) Error("BaseWindingForPlane: no axis found");
242
243         switch (x) {
244                 case 0: // Fall through to next case.
245                 case 1:
246                         vright[0] = -normal[1];
247                         vright[1] = normal[0];
248                         vright[2] = 0;
249                         break;
250                 case 2:
251                         vright[0] = 0;
252                         vright[1] = -normal[2];
253                         vright[2] = normal[1];
254                         break;
255         }
256         CrossProduct(normal, vright, vup);
257
258         // IMPORTANT NOTE: vright and vup are NOT unit vectors at this point.
259         // However, normal, vup, and vright are pairwise perpendicular.
260
261         VectorSetLength(vup, MAX_WORLD_COORD * 2, vup);
262         VectorSetLength(vright, MAX_WORLD_COORD * 2, vright);
263         VectorScale(normal, dist, org);
264
265         w = AllocWinding(4);
266
267         VectorSubtract(org, vright, w->p[0]);
268         VectorAdd(w->p[0], vup, w->p[0]);
269
270         VectorAdd(org, vright, w->p[1]);
271         VectorAdd(w->p[1], vup, w->p[1]);
272
273         VectorAdd(org, vright, w->p[2]);
274         VectorSubtract(w->p[2], vup, w->p[2]);
275
276         VectorSubtract(org, vright, w->p[3]);
277         VectorSubtract(w->p[3], vup, w->p[3]);
278
279         w->numpoints = 4;
280
281         return w;
282 }
283
284 // Old function, not used but here for reference.  Please do not modify it.
285 // (You may remove it at some point.)
286 winding_t *_BaseWindingForPlane_orig_(vec3_t normal, vec_t dist)
287 {
288         int             i, x;
289         vec_t   max, v;
290         vec3_t  org, vright, vup;
291         winding_t       *w;
292         
293 // find the major axis
294
295         max = -BOGUS_RANGE;
296         x = -1;
297         for (i=0 ; i<3; i++)
298         {
299                 v = fabs(normal[i]);
300                 if (v > max)
301                 {
302                         x = i;
303                         max = v;
304                 }
305         }
306         if (x==-1)
307                 Error ("BaseWindingForPlane: no axis found");
308                 
309         VectorCopy (vec3_origin, vup);  
310         switch (x)
311         {
312         case 0:
313         case 1:
314                 vup[2] = 1;
315                 break;          
316         case 2:
317                 vup[0] = 1;
318                 break;          
319         }
320
321         v = DotProduct (vup, normal);
322         VectorMA (vup, -v, normal, vup);
323         VectorNormalize (vup, vup);
324                 
325         VectorScale (normal, dist, org);
326         
327         CrossProduct (vup, normal, vright);
328         
329         // LordHavoc: this has to use *2 because otherwise some created points may
330         // be inside the world (think of a diagonal case), and any brush with such
331         // points should be removed, failure to detect such cases is disasterous
332         VectorScale (vup, MAX_WORLD_COORD*2, vup);
333         VectorScale (vright, MAX_WORLD_COORD*2, vright);
334
335   // project a really big       axis aligned box onto the plane
336         w = AllocWinding (4);
337         
338         VectorSubtract (org, vright, w->p[0]);
339         VectorAdd (w->p[0], vup, w->p[0]);
340         
341         VectorAdd (org, vright, w->p[1]);
342         VectorAdd (w->p[1], vup, w->p[1]);
343         
344         VectorAdd (org, vright, w->p[2]);
345         VectorSubtract (w->p[2], vup, w->p[2]);
346         
347         VectorSubtract (org, vright, w->p[3]);
348         VectorSubtract (w->p[3], vup, w->p[3]);
349         
350         w->numpoints = 4;
351         
352         return w;       
353 }
354
355 /*
356 ==================
357 CopyWinding
358 ==================
359 */
360 winding_t       *CopyWinding (winding_t *w)
361 {
362         size_t                  size;
363         winding_t       *c;
364
365         c = AllocWinding (w->numpoints);
366         size = (size_t)((winding_t *)NULL)->p[w->numpoints];
367         memcpy (c, w, size);
368         return c;
369 }
370
371 /*
372 ==================
373 ReverseWinding
374 ==================
375 */
376 winding_t       *ReverseWinding (winding_t *w)
377 {
378         int                     i;
379         winding_t       *c;
380
381         c = AllocWinding (w->numpoints);
382         for (i=0 ; i<w->numpoints ; i++)
383         {
384                 VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
385         }
386         c->numpoints = w->numpoints;
387         return c;
388 }
389
390
391 /*
392 =============
393 ClipWindingEpsilon
394 =============
395 */
396 void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 
397                                 vec_t epsilon, winding_t **front, winding_t **back)
398 {
399         vec_t   dists[MAX_POINTS_ON_WINDING+4];
400         int             sides[MAX_POINTS_ON_WINDING+4];
401         int             counts[3];
402         static  vec_t   dot;            // VC 4.2 optimizer bug if not static
403         int             i, j;
404         vec_t   *p1, *p2;
405         vec3_t  mid;
406         winding_t       *f, *b;
407         int             maxpts;
408         
409         counts[0] = counts[1] = counts[2] = 0;
410
411 // determine sides for each point
412         for (i=0 ; i<in->numpoints ; i++)
413   {
414
415                 dot = DotProduct (in->p[i], normal);
416                 dot -= dist;
417                 dists[i] = dot;
418                 if (dot > epsilon)
419                         sides[i] = SIDE_FRONT;
420                 else if (dot < -epsilon)
421                         sides[i] = SIDE_BACK;
422                 else
423                 {
424                         sides[i] = SIDE_ON;
425                 }
426                 counts[sides[i]]++;
427         }
428         sides[i] = sides[0];
429         dists[i] = dists[0];
430         
431         *front = *back = NULL;
432
433         if (!counts[0])
434         {
435                 *back = CopyWinding (in);
436                 return;
437         }
438         if (!counts[1])
439         {
440                 *front = CopyWinding (in);
441                 return;
442         }
443
444         maxpts = in->numpoints+4;       // cant use counts[0]+2 because
445                                                                 // of fp grouping errors
446
447         *front = f = AllocWinding (maxpts);
448         *back = b = AllocWinding (maxpts);
449                 
450         for (i=0 ; i<in->numpoints ; i++)
451         {
452                 p1 = in->p[i];
453                 
454                 if (sides[i] == SIDE_ON)
455                 {
456                         VectorCopy (p1, f->p[f->numpoints]);
457                         f->numpoints++;
458                         VectorCopy (p1, b->p[b->numpoints]);
459                         b->numpoints++;
460                         continue;
461                 }
462         
463                 if (sides[i] == SIDE_FRONT)
464                 {
465                         VectorCopy (p1, f->p[f->numpoints]);
466                         f->numpoints++;
467                 }
468                 if (sides[i] == SIDE_BACK)
469                 {
470                         VectorCopy (p1, b->p[b->numpoints]);
471                         b->numpoints++;
472                 }
473
474                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
475                         continue;
476                         
477         // generate a split point
478                 p2 = in->p[(i+1)%in->numpoints];
479                 
480                 dot = dists[i] / (dists[i]-dists[i+1]);
481                 for (j=0 ; j<3 ; j++)
482                 {       // avoid round off error when possible
483                         if (normal[j] == 1)
484                                 mid[j] = dist;
485                         else if (normal[j] == -1)
486                                 mid[j] = -dist;
487                         else
488                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
489                 }
490                         
491                 VectorCopy (mid, f->p[f->numpoints]);
492                 f->numpoints++;
493                 VectorCopy (mid, b->p[b->numpoints]);
494                 b->numpoints++;
495         }
496         
497         if (f->numpoints > maxpts || b->numpoints > maxpts)
498                 Error ("ClipWinding: points exceeded estimate");
499         if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
500                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
501 }
502
503
504 /*
505 =============
506 ChopWindingInPlace
507 =============
508 */
509 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
510 {
511         winding_t       *in;
512         vec_t   dists[MAX_POINTS_ON_WINDING+4];
513         int             sides[MAX_POINTS_ON_WINDING+4];
514         int             counts[3];
515         static  vec_t   dot;            // VC 4.2 optimizer bug if not static
516         int             i, j;
517         vec_t   *p1, *p2;
518         vec3_t  mid;
519         winding_t       *f;
520         int             maxpts;
521
522         in = *inout;
523         counts[0] = counts[1] = counts[2] = 0;
524
525 // determine sides for each point
526         for (i=0 ; i<in->numpoints ; i++)
527         {
528                 dot = DotProduct (in->p[i], normal);
529                 dot -= dist;
530                 dists[i] = dot;
531                 if (dot > epsilon)
532                         sides[i] = SIDE_FRONT;
533                 else if (dot < -epsilon)
534                         sides[i] = SIDE_BACK;
535                 else
536                 {
537                         sides[i] = SIDE_ON;
538                 }
539                 counts[sides[i]]++;
540         }
541         sides[i] = sides[0];
542         dists[i] = dists[0];
543         
544         if (!counts[0])
545         {
546                 FreeWinding (in);
547                 *inout = NULL;
548                 return;
549         }
550         if (!counts[1])
551                 return;         // inout stays the same
552
553         maxpts = in->numpoints+4;       // cant use counts[0]+2 because
554                                                                 // of fp grouping errors
555
556         f = AllocWinding (maxpts);
557                 
558         for (i=0 ; i<in->numpoints ; i++)
559         {
560                 p1 = in->p[i];
561                 
562                 if (sides[i] == SIDE_ON)
563                 {
564                         VectorCopy (p1, f->p[f->numpoints]);
565                         f->numpoints++;
566                         continue;
567                 }
568         
569                 if (sides[i] == SIDE_FRONT)
570                 {
571                         VectorCopy (p1, f->p[f->numpoints]);
572                         f->numpoints++;
573                 }
574
575                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
576                         continue;
577                         
578         // generate a split point
579                 p2 = in->p[(i+1)%in->numpoints];
580                 
581                 dot = dists[i] / (dists[i]-dists[i+1]);
582                 for (j=0 ; j<3 ; j++)
583                 {       // avoid round off error when possible
584                         if (normal[j] == 1)
585                                 mid[j] = dist;
586                         else if (normal[j] == -1)
587                                 mid[j] = -dist;
588                         else
589                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
590                 }
591                         
592                 VectorCopy (mid, f->p[f->numpoints]);
593                 f->numpoints++;
594         }
595         
596         if (f->numpoints > maxpts)
597                 Error ("ClipWinding: points exceeded estimate");
598         if (f->numpoints > MAX_POINTS_ON_WINDING)
599                 Error ("ClipWinding: MAX_POINTS_ON_WINDING");
600
601         FreeWinding (in);
602         *inout = f;
603 }
604
605
606 /*
607 =================
608 ChopWinding
609
610 Returns the fragment of in that is on the front side
611 of the cliping plane.  The original is freed.
612 =================
613 */
614 winding_t       *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
615 {
616         winding_t       *f, *b;
617
618         ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
619         FreeWinding (in);
620         if (b)
621                 FreeWinding (b);
622         return f;
623 }
624
625
626 /*
627 =================
628 CheckWinding
629
630 =================
631 */
632 void CheckWinding (winding_t *w)
633 {
634         int             i, j;
635         vec_t   *p1, *p2;
636         vec_t   d, edgedist;
637         vec3_t  dir, edgenormal, facenormal;
638         vec_t   area;
639         vec_t   facedist;
640
641         if (w->numpoints < 3)
642                 Error ("CheckWinding: %i points",w->numpoints);
643         
644         area = WindingArea(w);
645         if (area < 1)
646                 Error ("CheckWinding: %f area", area);
647
648         WindingPlane (w, facenormal, &facedist);
649         
650         for (i=0 ; i<w->numpoints ; i++)
651         {
652                 p1 = w->p[i];
653
654                 for (j=0 ; j<3 ; j++)
655                         if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD)
656                                 Error ("CheckFace: MAX_WORLD_COORD exceeded: %f",p1[j]);
657
658                 j = i+1 == w->numpoints ? 0 : i+1;
659                 
660         // check the point is on the face plane
661                 d = DotProduct (p1, facenormal) - facedist;
662                 if (d < -ON_EPSILON || d > ON_EPSILON)
663                         Error ("CheckWinding: point off plane");
664         
665         // check the edge isnt degenerate
666                 p2 = w->p[j];
667                 VectorSubtract (p2, p1, dir);
668                 
669                 if (VectorLength (dir) < ON_EPSILON)
670                         Error ("CheckWinding: degenerate edge");
671                         
672                 CrossProduct (facenormal, dir, edgenormal);
673                 VectorNormalize (edgenormal, edgenormal);
674                 edgedist = DotProduct (p1, edgenormal);
675                 edgedist += ON_EPSILON;
676                 
677         // all other points must be on front side
678                 for (j=0 ; j<w->numpoints ; j++)
679                 {
680                         if (j == i)
681                                 continue;
682                         d = DotProduct (w->p[j], edgenormal);
683                         if (d > edgedist)
684                                 Error ("CheckWinding: non-convex");
685                 }
686         }
687 }
688
689
690 /*
691 ============
692 WindingOnPlaneSide
693 ============
694 */
695 int             WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
696 {
697         qboolean        front, back;
698         int                     i;
699         vec_t           d;
700
701         front = qfalse;
702         back = qfalse;
703         for (i=0 ; i<w->numpoints ; i++)
704         {
705                 d = DotProduct (w->p[i], normal) - dist;
706                 if (d < -ON_EPSILON)
707                 {
708                         if (front)
709                                 return SIDE_CROSS;
710                         back = qtrue;
711                         continue;
712                 }
713                 if (d > ON_EPSILON)
714                 {
715                         if (back)
716                                 return SIDE_CROSS;
717                         front = qtrue;
718                         continue;
719                 }
720         }
721
722         if (back)
723                 return SIDE_BACK;
724         if (front)
725                 return SIDE_FRONT;
726         return SIDE_ON;
727 }
728
729
730 /*
731 =================
732 AddWindingToConvexHull
733
734 Both w and *hull are on the same plane
735 =================
736 */
737 #define MAX_HULL_POINTS         128
738 void    AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) {
739         int                     i, j, k;
740         float           *p, *copy;
741         vec3_t          dir;
742         float           d;
743         int                     numHullPoints, numNew;
744         vec3_t          hullPoints[MAX_HULL_POINTS];
745         vec3_t          newHullPoints[MAX_HULL_POINTS];
746         vec3_t          hullDirs[MAX_HULL_POINTS];
747         qboolean        hullSide[MAX_HULL_POINTS];
748         qboolean        outside;
749
750         if ( !*hull ) {
751                 *hull = CopyWinding( w );
752                 return;
753         }
754
755         numHullPoints = (*hull)->numpoints;
756         memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
757
758         for ( i = 0 ; i < w->numpoints ; i++ ) {
759                 p = w->p[i];
760
761                 // calculate hull side vectors
762                 for ( j = 0 ; j < numHullPoints ; j++ ) {
763                         k = ( j + 1 ) % numHullPoints;
764
765                         VectorSubtract( hullPoints[k], hullPoints[j], dir );
766                         VectorNormalize( dir, dir );
767                         CrossProduct( normal, dir, hullDirs[j] );
768                 }
769
770                 outside = qfalse;
771                 for ( j = 0 ; j < numHullPoints ; j++ ) {
772                         VectorSubtract( p, hullPoints[j], dir );
773                         d = DotProduct( dir, hullDirs[j] );
774                         if ( d >= ON_EPSILON ) {
775                                 outside = qtrue;
776                         }
777                         if ( d >= -ON_EPSILON ) {
778                                 hullSide[j] = qtrue;
779                         } else {
780                                 hullSide[j] = qfalse;
781                         }
782                 }
783
784                 // if the point is effectively inside, do nothing
785                 if ( !outside ) {
786                         continue;
787                 }
788
789                 // find the back side to front side transition
790                 for ( j = 0 ; j < numHullPoints ; j++ ) {
791                         if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
792                                 break;
793                         }
794                 }
795                 if ( j == numHullPoints ) {
796                         continue;
797                 }
798
799                 // insert the point here
800                 VectorCopy( p, newHullPoints[0] );
801                 numNew = 1;
802
803                 // copy over all points that aren't double fronts
804                 j = (j+1)%numHullPoints;
805                 for ( k = 0 ; k < numHullPoints ; k++ ) {
806                         if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
807                                 continue;
808                         }
809                         copy = hullPoints[ (j+k+1) % numHullPoints ];
810                         VectorCopy( copy, newHullPoints[numNew] );
811                         numNew++;
812                 }
813
814                 numHullPoints = numNew;
815                 memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
816         }
817
818         FreeWinding( *hull );
819         w = AllocWinding( numHullPoints );
820         w->numpoints = numHullPoints;
821         *hull = w;
822         memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
823 }
824
825