audit all uses of ClipWindingEpsilon and choose the strict variant or not, and explai...
[xonotic/netradiant.git] / tools / quake3 / q3map2 / brush.c
1 /* -------------------------------------------------------------------------------
2
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6 This file is part of GtkRadiant.
7
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21
22 ----------------------------------------------------------------------------------
23
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26
27 ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define BRUSH_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 /* -------------------------------------------------------------------------------
42
43 functions
44
45 ------------------------------------------------------------------------------- */
46
47 /*
48 AllocSideRef() - ydnar
49 allocates and assigns a brush side reference
50 */
51
52 sideRef_t *AllocSideRef( side_t *side, sideRef_t *next )
53 {
54         sideRef_t *sideRef;
55         
56         
57         /* dummy check */
58         if( side == NULL )
59                 return next;
60         
61         /* allocate and return */
62         sideRef = safe_malloc( sizeof( *sideRef ) );
63         sideRef->side = side;
64         sideRef->next = next;
65         return sideRef;
66 }
67
68
69
70 /*
71 CountBrushList()
72 counts the number of brushes in a brush linked list
73 */
74
75 int     CountBrushList( brush_t *brushes )
76 {
77         int     c = 0;
78         
79         
80         /* count brushes */
81         for( ; brushes != NULL; brushes = brushes->next )
82                 c++;
83         return c;
84 }
85
86
87
88 /*
89 AllocBrush()
90 allocates a new brush
91 */
92
93 brush_t *AllocBrush( int numSides )
94 {
95         brush_t         *bb;
96         size_t          c;
97         
98         
99         /* allocate and clear */
100         if( numSides <= 0 )
101                 Error( "AllocBrush called with numsides = %d", numSides );
102         c = (size_t)&(((brush_t*) 0)->sides[ numSides ]);
103         bb = safe_malloc( c );
104         memset( bb, 0, c );
105         if( numthreads == 1 )
106                 numActiveBrushes++;
107         
108         /* return it */
109         return bb;
110 }
111
112
113
114 /*
115 FreeBrush()
116 frees a single brush and all sides/windings
117 */
118
119 void FreeBrush( brush_t *b )
120 {
121         int                     i;
122         
123         
124         /* error check */
125         if( *((unsigned int*) b) == 0xFEFEFEFE )
126         {
127                 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
128                 return;
129         }
130         
131         /* free brush sides */
132         for( i = 0; i < b->numsides; i++ )
133                 if( b->sides[i].winding != NULL )
134                         FreeWinding( b->sides[ i ].winding );
135         
136         /* ydnar: overwrite it */
137         memset( b, 0xFE, (size_t)&(((brush_t*) 0)->sides[ b->numsides ]) );
138         *((unsigned int*) b) = 0xFEFEFEFE;
139         
140         /* free it */
141         free( b );
142         if( numthreads == 1 )
143                 numActiveBrushes--;
144 }
145
146
147
148 /*
149 FreeBrushList()
150 frees a linked list of brushes
151 */
152
153 void FreeBrushList( brush_t *brushes )
154 {
155         brush_t         *next;
156         
157         
158         /* walk brush list */
159         for( ; brushes != NULL; brushes = next )
160         {
161                 next = brushes->next;
162                 FreeBrush( brushes );
163         }               
164 }
165
166
167
168 /*
169 CopyBrush()
170 duplicates the brush, sides, and windings
171 */
172
173 brush_t *CopyBrush( brush_t *brush )
174 {
175         brush_t         *newBrush;
176         size_t          size;
177         int                     i;
178         
179         
180         /* copy brush */
181         size = (size_t)&(((brush_t*) 0)->sides[ brush->numsides ]);
182         newBrush = AllocBrush( brush->numsides );
183         memcpy( newBrush, brush, size );
184         
185         /* ydnar: nuke linked list */
186         newBrush->next = NULL;
187         
188         /* copy sides */
189         for( i = 0; i < brush->numsides; i++ )
190         {
191                 if( brush->sides[ i ].winding != NULL )
192                         newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
193         }
194         
195         /* return it */
196         return newBrush;
197 }
198
199
200
201
202 /*
203 BoundBrush()
204 sets the mins/maxs based on the windings
205 returns false if the brush doesn't enclose a valid volume
206 */
207
208 qboolean BoundBrush( brush_t *brush )
209 {
210         int                     i, j;
211         winding_t       *w;
212         
213         
214         ClearBounds( brush->mins, brush->maxs );
215         for( i = 0; i < brush->numsides; i++ )
216         {
217                 w = brush->sides[ i ].winding;
218                 if( w == NULL )
219                         continue;
220                 for( j = 0; j < w->numpoints; j++ )
221                         AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
222         }
223         
224         for( i = 0; i < 3; i++ )
225         {
226                 if( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] )
227                         return qfalse;
228         }
229         
230         return qtrue;
231 }
232
233
234
235
236 /*
237 SnapWeldVector() - ydnar
238 welds two vec3_t's into a third, taking into account nearest-to-integer
239 instead of averaging
240 */
241
242 #define SNAP_EPSILON    0.01
243
244 void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out )
245 {
246         int             i;
247         vec_t   ai, bi, outi;
248         
249         
250         /* dummy check */
251         if( a == NULL || b == NULL || out == NULL )
252                 return;
253         
254         /* do each element */
255         for( i = 0; i < 3; i++ )
256         {
257                 /* round to integer */
258                 ai = Q_rint( a[ i ] );
259                 bi = Q_rint( a[ i ] );
260                 
261                 /* prefer exact integer */
262                 if( ai == a[ i ] )
263                         out[ i ] = a[ i ];
264                 else if( bi == b[ i ] )
265                         out[ i ] = b[ i ];
266
267                 /* use nearest */
268                 else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )
269                         out[ i ] = a[ i ];
270                 else
271                         out[ i ] = b[ i ];
272                 
273                 /* snap */
274                 outi = Q_rint( out[ i ] );
275                 if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )
276                         out[ i ] = outi;
277         }
278 }
279
280 /*
281 ==================
282 SnapWeldVectorAccu
283
284 Welds two vectors into a third, taking into account nearest-to-integer
285 instead of averaging.
286 ==================
287 */
288 void SnapWeldVectorAccu(vec3_accu_t a, vec3_accu_t b, vec3_accu_t out)
289 {
290         // I'm just preserving what I think was the intended logic of the original
291         // SnapWeldVector().  I'm not actually sure where this function should even
292         // be used.  I'd like to know which kinds of problems this function addresses.
293
294         // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
295         // So what is natural about snapping to the nearest integer?  Maybe we should
296         // be snapping to the nearest 1/8 unit instead?
297
298         int             i;
299         vec_accu_t      ai, bi, ad, bd;
300         
301         if (a == NULL || b == NULL || out == NULL)
302                 Error("SnapWeldVectorAccu: NULL argument");
303         
304         for (i = 0; i < 3; i++)
305         {
306                 ai = Q_rintAccu(a[i]);
307                 bi = Q_rintAccu(b[i]);
308                 ad = fabs(ai - a[i]);
309                 bd = fabs(bi - b[i]);
310         
311                 if (ad < bd)
312                 {
313                         if (ad < SNAP_EPSILON)  out[i] = ai;
314                         else                    out[i] = a[i];
315                 }
316                 else
317                 {
318                         if (bd < SNAP_EPSILON)  out[i] = bi;
319                         else                    out[i] = b[i];
320                 }
321         }
322 }
323
324 /*
325 FixWinding() - ydnar
326 removes degenerate edges from a winding
327 returns qtrue if the winding is valid
328 */
329
330 #define DEGENERATE_EPSILON      0.1
331
332 qboolean FixWinding( winding_t *w )
333 {
334         qboolean        valid = qtrue;
335         int                     i, j, k;
336         vec3_t          vec;
337         float           dist;
338         
339         
340         /* dummy check */
341         if( !w )
342                 return qfalse;
343         
344         /* check all verts */
345         for( i = 0; i < w->numpoints; i++ )
346         {
347                 /* don't remove points if winding is a triangle */
348                 if( w->numpoints == 3 )
349                         return valid;
350                 
351                 /* get second point index */
352                 j = (i + 1) % w->numpoints;
353                 
354                 /* degenerate edge? */
355                 VectorSubtract( w->p[ i ], w->p[ j ], vec );
356                 dist = VectorLength( vec );
357                 if( dist < DEGENERATE_EPSILON )
358                 {
359                         valid = qfalse;
360                         //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
361                         
362                         /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
363                         SnapWeldVector( w->p[ i ], w->p[ j ], vec );
364                         VectorCopy( vec, w->p[ i ] );
365                         //VectorAdd( w->p[ i ], w->p[ j ], vec );
366                         //VectorScale( vec, 0.5, w->p[ i ] );
367                         
368                         /* move the remaining verts */
369                         for( k = i + 2; k < w->numpoints; k++ )
370                         {
371                                 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
372                         }
373                         w->numpoints--;
374                 }
375         }
376         
377         /* one last check and return */
378         if( w->numpoints < 3 )
379                 valid = qfalse;
380         return valid;
381 }
382
383 /*
384 ==================
385 FixWindingAccu
386
387 Removes degenerate edges (edges that are too short) from a winding.
388 Returns qtrue if the winding has been altered by this function.
389 Returns qfalse if the winding is untouched by this function.
390
391 It's advised that you check the winding after this function exits to make
392 sure it still has at least 3 points.  If that is not the case, the winding
393 cannot be considered valid.  The winding may degenerate to one or two points
394 if the some of the winding's points are close together.
395 ==================
396 */
397 qboolean FixWindingAccu(winding_accu_t *w)
398 {
399         int             i, j, k;
400         vec3_accu_t     vec;
401         vec_accu_t      dist;
402         qboolean        done, altered;
403
404         if (w == NULL) Error("FixWindingAccu: NULL argument");
405
406         altered = qfalse;
407
408         while (qtrue)
409         {
410                 if (w->numpoints < 2) break; // Don't remove the only remaining point.
411                 done = qtrue;
412                 for (i = 0; i < w->numpoints; i++)
413                 {
414                         j = (((i + 1) == w->numpoints) ? 0 : (i + 1));
415
416                         VectorSubtractAccu(w->p[i], w->p[j], vec);
417                         dist = VectorLengthAccu(vec);
418                         if (dist < DEGENERATE_EPSILON)
419                         {
420                                 // TODO: I think the "snap weld vector" was written before
421                                 // some of the math precision fixes, and its purpose was
422                                 // probably to address math accuracy issues.  We can think
423                                 // about changing the logic here.  Maybe once plane distance
424                                 // gets 64 bits, we can look at it then.
425                                 SnapWeldVectorAccu(w->p[i], w->p[j], vec);
426                                 VectorCopyAccu(vec, w->p[i]);
427                                 for (k = j + 1; k < w->numpoints; k++)
428                                 {
429                                         VectorCopyAccu(w->p[k], w->p[k - 1]);
430                                 }
431                                 w->numpoints--;
432                                 altered = qtrue;
433                                 // The only way to finish off fixing the winding consistently and
434                                 // accurately is by fixing the winding all over again.  For example,
435                                 // the point at index i and the point at index i-1 could now be
436                                 // less than the epsilon distance apart.  There are too many special
437                                 // case problems we'd need to handle if we didn't start from the
438                                 // beginning.
439                                 done = qfalse;
440                                 break; // This will cause us to return to the "while" loop.
441                         }
442                 }
443                 if (done) break;
444         }
445
446         return altered;
447 }
448
449
450 /*
451 CreateBrushWindings()
452 makes basewindigs for sides and mins/maxs for the brush
453 returns false if the brush doesn't enclose a valid volume
454 */
455
456 qboolean CreateBrushWindings( brush_t *brush )
457 {
458         int                     i, j;
459 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
460         winding_accu_t  *w;
461 #else
462         winding_t       *w;
463 #endif
464         side_t          *side;
465         plane_t         *plane;
466         
467         
468         /* walk the list of brush sides */
469         for( i = 0; i < brush->numsides; i++ )
470         {
471                 /* get side and plane */
472                 side = &brush->sides[ i ];
473                 plane = &mapplanes[ side->planenum ];
474                 
475                 /* make huge winding */
476 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
477                 w = BaseWindingForPlaneAccu(plane->normal, plane->dist);
478 #else
479                 w = BaseWindingForPlane( plane->normal, plane->dist );
480 #endif
481                 
482                 /* walk the list of brush sides */
483                 for( j = 0; j < brush->numsides && w != NULL; j++ )
484                 {
485                         if( i == j )
486                                 continue;
487                         if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
488                                 continue;               /* back side clipaway */
489                         if( brush->sides[ j ].bevel )
490                                 continue;
491                         plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
492 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
493                         ChopWindingInPlaceAccu(&w, plane->normal, plane->dist, 0);
494 #else
495                         ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
496 #endif
497                         
498                         /* ydnar: fix broken windings that would generate trifans */
499 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
500                         // I think it's better to FixWindingAccu() once after we chop with all planes
501                         // so that error isn't multiplied.  There is nothing natural about welding
502                         // the points unless they are the final endpoints.  ChopWindingInPlaceAccu()
503                         // is able to handle all kinds of degenerate windings.
504 #else
505                         FixWinding( w );
506 #endif
507                 }
508                 
509                 /* set side winding */
510 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
511                 if (w != NULL)
512                 {
513                         FixWindingAccu(w);
514                         if (w->numpoints < 3)
515                         {
516                                 FreeWindingAccu(w);
517                                 w = NULL;
518                         }
519                 }
520                 side->winding = (w ? CopyWindingAccuToRegular(w) : NULL);
521                 if (w) FreeWindingAccu(w);
522 #else
523                 side->winding = w;
524 #endif
525         }
526         
527         /* find brush bounds */
528         return BoundBrush( brush );
529 }
530
531
532
533
534 /*
535 ==================
536 BrushFromBounds
537
538 Creates a new axial brush
539 ==================
540 */
541 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
542 {
543         brush_t         *b;
544         int                     i;
545         vec3_t          normal;
546         vec_t           dist;
547
548         b = AllocBrush (6);
549         b->numsides = 6;
550         for (i=0 ; i<3 ; i++)
551         {
552                 VectorClear (normal);
553                 normal[i] = 1;
554                 dist = maxs[i];
555                 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
556
557                 normal[i] = -1;
558                 dist = -mins[i];
559                 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
560         }
561
562         CreateBrushWindings (b);
563
564         return b;
565 }
566
567 /*
568 ==================
569 BrushVolume
570
571 ==================
572 */
573 vec_t BrushVolume (brush_t *brush)
574 {
575         int                     i;
576         winding_t       *w;
577         vec3_t          corner;
578         vec_t           d, area, volume;
579         plane_t         *plane;
580
581         if (!brush)
582                 return 0;
583
584         // grab the first valid point as the corner
585
586         w = NULL;
587         for (i=0 ; i<brush->numsides ; i++)
588         {
589                 w = brush->sides[i].winding;
590                 if (w)
591                         break;
592         }
593         if (!w)
594                 return 0;
595         VectorCopy (w->p[0], corner);
596
597         // make tetrahedrons to all other faces
598
599         volume = 0;
600         for ( ; i<brush->numsides ; i++)
601         {
602                 w = brush->sides[i].winding;
603                 if (!w)
604                         continue;
605                 plane = &mapplanes[brush->sides[i].planenum];
606                 d = -(DotProduct (corner, plane->normal) - plane->dist);
607                 area = WindingArea (w);
608                 volume += d*area;
609         }
610
611         volume /= 3;
612         return volume;
613 }
614
615
616
617 /*
618 WriteBSPBrushMap()
619 writes a map with the split bsp brushes
620 */
621
622 void WriteBSPBrushMap( char *name, brush_t *list )
623 {
624         FILE            *f;
625         side_t          *s;
626         int                     i;
627         winding_t       *w;
628         
629         
630         /* note it */
631         Sys_Printf( "Writing %s\n", name );
632         
633         /* open the map file */
634         f = fopen( name, "wb" );
635         if( f == NULL )
636                 Error( "Can't write %s\b", name );
637
638         fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
639
640         for ( ; list ; list=list->next )
641         {
642                 fprintf (f, "{\n");
643                 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
644                 {
645                         // TODO: See if we can use a smaller winding to prevent resolution loss.
646                         // Is WriteBSPBrushMap() used only to decompile maps?
647                         w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
648
649                         fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
650                         fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
651                         fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
652
653                         fprintf (f, "notexture 0 0 0 1 1\n" );
654                         FreeWinding (w);
655                 }
656                 fprintf (f, "}\n");
657         }
658         fprintf (f, "}\n");
659
660         fclose (f);
661
662 }
663
664
665
666 /*
667 FilterBrushIntoTree_r()
668 adds brush reference to any intersecting bsp leafnode
669 */
670
671 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
672 {
673         brush_t         *front, *back;
674         int                     c;
675         
676         
677         /* dummy check */
678         if( b == NULL )
679                 return 0;
680         
681         /* add it to the leaf list */
682         if( node->planenum == PLANENUM_LEAF )
683         {
684                 /* something somewhere is hammering brushlist */
685                 b->next = node->brushlist;
686                 node->brushlist = b;
687                 
688                 /* classify the leaf by the structural brush */
689                 if( !b->detail )
690                 {
691                         if( b->opaque )
692                         {
693                                 node->opaque = qtrue;
694                                 node->areaportal = qfalse;
695                         }
696                         else if( b->compileFlags & C_AREAPORTAL )
697                         {
698                                 if( !node->opaque )
699                                         node->areaportal = qtrue;
700                         }
701                 }
702                 
703                 return 1;
704         }
705         
706         /* split it by the node plane */
707         c = b->numsides;
708         SplitBrush( b, node->planenum, &front, &back );
709         FreeBrush( b );
710         
711         c = 0;
712         c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
713         c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
714         
715         return c;
716 }
717
718
719
720 /*
721 FilterDetailBrushesIntoTree
722 fragment all the detail brushes into the structural leafs
723 */
724
725 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
726 {
727         brush_t                         *b, *newb;
728         int                                     r;
729         int                                     c_unique, c_clusters;
730         int                                     i;
731         
732         
733         /* note it */
734         Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
735         
736         /* walk the list of brushes */
737         c_unique = 0;
738         c_clusters = 0;
739         for( b = e->brushes; b; b = b->next )
740         {
741                 if( !b->detail )
742                         continue;
743                 c_unique++;
744                 newb = CopyBrush( b );
745                 r = FilterBrushIntoTree_r( newb, tree->headnode );
746                 c_clusters += r;
747                 
748                 /* mark all sides as visible so drawsurfs are created */
749                 if( r )
750                 {
751                         for( i = 0; i < b->numsides; i++ )
752                         {
753                                 if( b->sides[ i ].winding )
754                                         b->sides[ i ].visible = qtrue;
755                         }
756                 }
757         }
758         
759         /* emit some statistics */
760         Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
761         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
762 }
763
764 /*
765 =====================
766 FilterStructuralBrushesIntoTree
767
768 Mark the leafs as opaque and areaportals
769 =====================
770 */
771 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
772         brush_t                 *b, *newb;
773         int                                     r;
774         int                                     c_unique, c_clusters;
775         int                                     i;
776
777         Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
778
779         c_unique = 0;
780         c_clusters = 0;
781         for ( b = e->brushes ; b ; b = b->next ) {
782                 if ( b->detail ) {
783                         continue;
784                 }
785                 c_unique++;
786                 newb = CopyBrush( b );
787                 r = FilterBrushIntoTree_r( newb, tree->headnode );
788                 c_clusters += r;
789
790                 // mark all sides as visible so drawsurfs are created
791                 if ( r ) {
792                         for ( i = 0 ; i < b->numsides ; i++ ) {
793                                 if ( b->sides[i].winding ) {
794                                         b->sides[i].visible = qtrue;
795                                 }
796                         }
797                 }
798         }
799         
800         /* emit some statistics */
801         Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
802         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
803 }
804
805
806
807 /*
808 ================
809 AllocTree
810 ================
811 */
812 tree_t *AllocTree (void)
813 {
814         tree_t  *tree;
815
816         tree = safe_malloc(sizeof(*tree));
817         memset (tree, 0, sizeof(*tree));
818         ClearBounds (tree->mins, tree->maxs);
819
820         return tree;
821 }
822
823 /*
824 ================
825 AllocNode
826 ================
827 */
828 node_t *AllocNode (void)
829 {
830         node_t  *node;
831
832         node = safe_malloc(sizeof(*node));
833         memset (node, 0, sizeof(*node));
834
835         return node;
836 }
837
838
839 /*
840 ================
841 WindingIsTiny
842
843 Returns true if the winding would be crunched out of
844 existance by the vertex snapping.
845 ================
846 */
847 #define EDGE_LENGTH     0.2
848 qboolean WindingIsTiny (winding_t *w)
849 {
850 /*
851         if (WindingArea (w) < 1)
852                 return qtrue;
853         return qfalse;
854 */
855         int             i, j;
856         vec_t   len;
857         vec3_t  delta;
858         int             edges;
859
860         edges = 0;
861         for (i=0 ; i<w->numpoints ; i++)
862         {
863                 j = i == w->numpoints - 1 ? 0 : i+1;
864                 VectorSubtract (w->p[j], w->p[i], delta);
865                 len = VectorLength (delta);
866                 if (len > EDGE_LENGTH)
867                 {
868                         if (++edges == 3)
869                                 return qfalse;
870                 }
871         }
872         return qtrue;
873 }
874
875 /*
876 ================
877 WindingIsHuge
878
879 Returns true if the winding still has one of the points
880 from basewinding for plane
881 ================
882 */
883 qboolean WindingIsHuge (winding_t *w)
884 {
885         int             i, j;
886
887         for (i=0 ; i<w->numpoints ; i++)
888         {
889                 for (j=0 ; j<3 ; j++)
890                         if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
891                                 return qtrue;
892         }
893         return qfalse;
894 }
895
896 //============================================================
897
898 /*
899 ==================
900 BrushMostlyOnSide
901
902 ==================
903 */
904 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
905 {
906         int                     i, j;
907         winding_t       *w;
908         vec_t           d, max;
909         int                     side;
910
911         max = 0;
912         side = PSIDE_FRONT;
913         for (i=0 ; i<brush->numsides ; i++)
914         {
915                 w = brush->sides[i].winding;
916                 if (!w)
917                         continue;
918                 for (j=0 ; j<w->numpoints ; j++)
919                 {
920                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
921                         if (d > max)
922                         {
923                                 max = d;
924                                 side = PSIDE_FRONT;
925                         }
926                         if (-d > max)
927                         {
928                                 max = -d;
929                                 side = PSIDE_BACK;
930                         }
931                 }
932         }
933         return side;
934 }
935
936
937
938 /*
939 SplitBrush()
940 generates two new brushes, leaving the original unchanged
941 */
942
943 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
944 {
945         brush_t         *b[2];
946         int                     i, j;
947         winding_t       *w, *cw[2], *midwinding;
948         plane_t         *plane, *plane2;
949         side_t          *s, *cs;
950         float           d, d_front, d_back;
951         
952         
953         *front = NULL;
954         *back = NULL;
955         plane = &mapplanes[planenum];
956         
957         // check all points
958         d_front = d_back = 0;
959         for (i=0 ; i<brush->numsides ; i++)
960         {
961                 w = brush->sides[i].winding;
962                 if (!w)
963                         continue;
964                 for (j=0 ; j<w->numpoints ; j++)
965                 {
966                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
967                         if (d > 0 && d > d_front)
968                                 d_front = d;
969                         if (d < 0 && d < d_back)
970                                 d_back = d;
971                 }
972         }
973         
974         if (d_front < 0.1) // PLANESIDE_EPSILON)
975         {       // only on back
976                 *back = CopyBrush( brush );
977                 return;
978         }
979         
980         if (d_back > -0.1) // PLANESIDE_EPSILON)
981         {       // only on front
982                 *front = CopyBrush( brush );
983                 return;
984         }
985         
986         // create a new winding from the split plane
987         w = BaseWindingForPlane (plane->normal, plane->dist);
988         for (i=0 ; i<brush->numsides && w ; i++)
989         {
990                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
991                 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
992         }
993
994         if (!w || WindingIsTiny (w) )
995         {       // the brush isn't really split
996                 int             side;
997
998                 side = BrushMostlyOnSide (brush, plane);
999                 if (side == PSIDE_FRONT)
1000                         *front = CopyBrush (brush);
1001                 if (side == PSIDE_BACK)
1002                         *back = CopyBrush (brush);
1003                 return;
1004         }
1005         
1006         if( WindingIsHuge( w ) )
1007                 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1008
1009         midwinding = w;
1010
1011         // split it for real
1012
1013         for (i=0 ; i<2 ; i++)
1014         {
1015                 b[i] = AllocBrush (brush->numsides+1);
1016                 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1017                 b[i]->numsides = 0;
1018                 b[i]->next = NULL;
1019                 b[i]->original = brush->original;
1020         }
1021
1022         // split all the current windings
1023
1024         for (i=0 ; i<brush->numsides ; i++)
1025         {
1026                 s = &brush->sides[i];
1027                 w = s->winding;
1028                 if (!w)
1029                         continue;
1030                 ClipWindingEpsilonStrict (w, plane->normal, plane->dist,
1031                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]); /* strict, in parallel case we get the face back because it also is the midwinding */
1032                 for (j=0 ; j<2 ; j++)
1033                 {
1034                         if (!cw[j])
1035                                 continue;
1036                         cs = &b[j]->sides[b[j]->numsides];
1037                         b[j]->numsides++;
1038                         *cs = *s;
1039                         cs->winding = cw[j];
1040                 }
1041         }
1042
1043
1044         // see if we have valid polygons on both sides
1045         for (i=0 ; i<2 ; i++)
1046         {
1047                 if (b[i]->numsides < 3 || !BoundBrush (b[i]))
1048                 {
1049                         if (b[i]->numsides >= 3)
1050                                 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
1051                         FreeBrush (b[i]);
1052                         b[i] = NULL;
1053                 }
1054         }
1055         
1056         if ( !(b[0] && b[1]) )
1057         {
1058                 if (!b[0] && !b[1])
1059                         Sys_FPrintf (SYS_VRB,"split removed brush\n");
1060                 else
1061                         Sys_FPrintf (SYS_VRB,"split not on both sides\n");
1062                 if (b[0])
1063                 {
1064                         FreeBrush (b[0]);
1065                         *front = CopyBrush (brush);
1066                 }
1067                 if (b[1])
1068                 {
1069                         FreeBrush (b[1]);
1070                         *back = CopyBrush (brush);
1071                 }
1072                 return;
1073         }
1074         
1075         // add the midwinding to both sides
1076         for (i=0 ; i<2 ; i++)
1077         {
1078                 cs = &b[i]->sides[b[i]->numsides];
1079                 b[i]->numsides++;
1080
1081                 cs->planenum = planenum^i^1;
1082                 cs->shaderInfo = NULL;
1083                 if (i==0)
1084                         cs->winding = CopyWinding (midwinding);
1085                 else
1086                         cs->winding = midwinding;
1087         }
1088         
1089         {
1090                 vec_t   v1;
1091                 int             i;
1092                 
1093                 
1094                 for (i=0 ; i<2 ; i++)
1095                 {
1096                         v1 = BrushVolume (b[i]);
1097                         if (v1 < 1.0)
1098                         {
1099                                 FreeBrush (b[i]);
1100                                 b[i] = NULL;
1101         //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
1102                         }
1103                 }
1104         }
1105         
1106         *front = b[0];
1107         *back = b[1];
1108 }