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