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