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