Merge commit '515673c08f8718a237e90c2130a1f5294f966d6a'
[xonotic/netradiant.git] / tools / quake3 / q3map2 / facebsp.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 FACEBSP_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 int                     c_faceLeafs;
42
43
44 /*
45 ================
46 AllocBspFace
47 ================
48 */
49 face_t  *AllocBspFace( void ) {
50         face_t  *f;
51
52         f = safe_malloc(sizeof(*f));
53         memset( f, 0, sizeof(*f) );
54
55         return f;
56 }
57
58
59
60 /*
61 ================
62 FreeBspFace
63 ================
64 */
65 void    FreeBspFace( face_t *f ) {
66         if ( f->w ) {
67                 FreeWinding( f->w );
68         }
69         free( f );
70 }
71
72
73
74 /*
75 SelectSplitPlaneNum()
76 finds the best split plane for this node
77 */
78
79 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )
80 {
81         face_t          *split;
82         face_t          *check;
83         face_t          *bestSplit;
84         int                     splits, facing, front, back;
85         int                     side;
86         plane_t         *plane;
87         int                     value, bestValue;
88         int                     i;
89         vec3_t          normal;
90         float           dist;
91         int                     planenum;
92         float       sizeBias;
93
94         //int frontC,backC,splitsC,facingC;
95
96         
97         /* ydnar: set some defaults */
98         *splitPlaneNum = -1; /* leaf */
99         *compileFlags = 0;
100         
101         /* ydnar 2002-06-24: changed this to split on z-axis as well */
102         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
103         
104         /* if it is crossing a block boundary, force a split */
105         for( i = 0; i < 3; i++ )
106         {
107                 if( blockSize[ i ] <= 0 )
108                         continue;
109                 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
110                 if( node->maxs[ i ] > dist )
111                 {
112                         VectorClear( normal );
113                         normal[ i ] = 1;
114                         planenum = FindFloatPlane( normal, dist, 0, NULL );
115                         *splitPlaneNum = planenum;
116                         return;
117                 }
118         }
119         
120         /* pick one of the face planes */
121         bestValue = -99999;
122         bestSplit = list;
123         
124
125         // div0: this check causes detail/structural mixes
126         //for( split = list; split; split = split->next )
127         //      split->checked = qfalse;
128         
129         for( split = list; split; split = split->next )
130         {
131                 //if ( split->checked )
132                 //      continue;
133
134                 plane = &mapplanes[ split->planenum ];
135                 splits = 0;
136                 facing = 0;
137                 front = 0;
138                 back = 0;
139                 for ( check = list ; check ; check = check->next ) {
140                         if ( check->planenum == split->planenum ) {
141                                 facing++;
142                                 //check->checked = qtrue;       // won't need to test this plane again
143                                 continue;
144                         }
145                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
146                         if ( side == SIDE_CROSS ) {
147                                 splits++;
148                         } else if ( side == SIDE_FRONT ) {
149                                 front++;
150                         } else if ( side == SIDE_BACK ) {
151                                 back++;
152                         }
153                 }
154
155                 if(bspAlternateSplitWeights)
156                 {
157                         // from 27
158
159                         //Bigger is better
160                         sizeBias=WindingArea(split->w);
161
162                         //Base score = 20000 perfectly balanced 
163                         value = 20000-(abs(front-back));
164                         value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again 
165                         value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
166                         value -= splits*5;        //more splits = bad
167                         value +=  sizeBias*10; //We want a huge score bias based on plane size
168                 }
169                 else
170                 {
171                         value =  5*facing - 5*splits; // - abs(front-back);
172                         if ( plane->type < 3 ) {
173                                 value+=5;               // axial is better
174                         }
175                 }
176
177                 value += split->priority;               // prioritize hints higher
178
179                 if ( value > bestValue ) {
180                         bestValue = value;
181                         bestSplit = split;
182                         //frontC=front;
183                         //backC=back;
184                         //splitsC=splits;
185                         //facingC=facing;
186                 }
187         }
188         
189         /* nothing, we have a leaf */
190         if( bestValue == -99999 )
191                 return;
192         
193         //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
194
195         /* set best split data */
196         *splitPlaneNum = bestSplit->planenum;
197         *compileFlags = bestSplit->compileFlags;
198
199 #if 0
200         if(bestSplit->compileFlags & C_DETAIL)
201                 for( split = list; split; split = split->next )
202                         if(!(split->compileFlags & C_DETAIL))
203                                 Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (1)\n");
204         if((node->compileFlags & C_DETAIL) && !(bestSplit->compileFlags & C_DETAIL))
205                 Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (2)\n");
206 #endif
207
208    if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;
209 }
210
211
212
213 /*
214 CountFaceList()
215 counts bsp faces in the linked list
216 */
217
218 int     CountFaceList( face_t *list )
219 {
220         int             c;
221         
222
223         c = 0;
224         for( ; list != NULL; list = list->next )
225                 c++;
226         return c;
227 }
228
229
230
231 /*
232 BuildFaceTree_r()
233 recursively builds the bsp, splitting on face planes
234 */
235
236 void BuildFaceTree_r( node_t *node, face_t *list )
237 {
238         face_t          *split;
239         face_t          *next;
240         int                     side;
241         plane_t         *plane;
242         face_t          *newFace;
243         face_t          *childLists[2];
244         winding_t       *frontWinding, *backWinding;
245         int                     i;
246         int                     splitPlaneNum, compileFlags;
247 #if 0
248         qboolean isstruct = qfalse;
249 #endif
250         
251         
252         /* count faces left */
253         i = CountFaceList( list );
254         
255         /* select the best split plane */
256         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
257         
258         /* if we don't have any more faces, this is a node */
259         if ( splitPlaneNum == -1 )
260         {
261                 node->planenum = PLANENUM_LEAF;
262                 node->has_structural_children = qfalse;
263                 c_faceLeafs++;
264                 return;
265         }
266         
267         /* partition the list */
268         node->planenum = splitPlaneNum;
269         node->compileFlags = compileFlags;
270         node->has_structural_children = !(compileFlags & C_DETAIL) && !node->opaque;
271         plane = &mapplanes[ splitPlaneNum ];
272         childLists[0] = NULL;
273         childLists[1] = NULL;
274
275         for( split = list; split; split = next )
276         {
277                 /* set next */
278                 next = split->next;
279                 
280                 /* don't split by identical plane */
281                 if( split->planenum == node->planenum )
282                 {
283                         FreeBspFace( split );
284                         continue;
285                 }
286
287 #if 0
288                 if(!(split->compileFlags & C_DETAIL))
289                         isstruct = 1;
290 #endif
291                 
292                 /* determine which side the face falls on */
293                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
294                 
295                 /* switch on side */
296                 if( side == SIDE_CROSS )
297                 {
298                         ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
299                                 &frontWinding, &backWinding ); /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
300                         if( frontWinding ) {
301                                 newFace = AllocBspFace();
302                                 newFace->w = frontWinding;
303                                 newFace->next = childLists[0];
304                                 newFace->planenum = split->planenum;
305                                 newFace->priority = split->priority;
306                                 newFace->compileFlags = split->compileFlags;
307                                 childLists[0] = newFace;
308                         }
309                         if( backWinding ) {
310                                 newFace = AllocBspFace();
311                                 newFace->w = backWinding;
312                                 newFace->next = childLists[1];
313                                 newFace->planenum = split->planenum;
314                                 newFace->priority = split->priority;
315                                 newFace->compileFlags = split->compileFlags;
316                                 childLists[1] = newFace;
317                         }
318                         FreeBspFace( split );
319                 } else if ( side == SIDE_FRONT ) {
320                         split->next = childLists[0];
321                         childLists[0] = split;
322                 } else if ( side == SIDE_BACK ) {
323                         split->next = childLists[1];
324                         childLists[1] = split;
325                 }
326         }
327
328
329         // recursively process children
330         for ( i = 0 ; i < 2 ; i++ ) {
331                 node->children[i] = AllocNode();
332                 node->children[i]->parent = node;
333                 VectorCopy( node->mins, node->children[i]->mins );
334                 VectorCopy( node->maxs, node->children[i]->maxs );
335         }
336
337         for ( i = 0 ; i < 3 ; i++ ) {
338                 if ( plane->normal[i] == 1 ) {
339                         node->children[0]->mins[i] = plane->dist;
340                         node->children[1]->maxs[i] = plane->dist;
341                         break;
342                 }
343                 if ( plane->normal[i] == -1 ) {
344                         node->children[0]->maxs[i] = -plane->dist;
345                         node->children[1]->mins[i] = -plane->dist;
346                         break;
347                 }
348         }
349
350 #if 0
351         if((node->compileFlags & C_DETAIL) && isstruct)
352                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children);
353 #endif
354
355         for ( i = 0 ; i < 2 ; i++ ) {
356                 BuildFaceTree_r ( node->children[i], childLists[i]);
357                 node->has_structural_children |= node->children[i]->has_structural_children;
358         }
359
360 #if 0
361         if((node->compileFlags & C_DETAIL) && !(node->children[0]->compileFlags & C_DETAIL) && node->children[0]->planenum != PLANENUM_LEAF)
362                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children);
363         if((node->compileFlags & C_DETAIL) && isstruct)
364                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children);
365 #endif
366 }
367
368
369 /*
370 ================
371 FaceBSP
372
373 List will be freed before returning
374 ================
375 */
376 tree_t *FaceBSP( face_t *list ) {
377         tree_t          *tree;
378         face_t  *face;
379         int                     i;
380         int                     count;
381
382         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
383
384         tree = AllocTree ();
385
386         count = 0;
387         for( face = list; face != NULL; face = face->next )
388         {
389                 count++;
390                 for( i = 0; i < face->w->numpoints; i++ )
391                 {
392                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
393                 }
394         }
395         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
396
397    for( i = 0; i < nummapplanes; i++)
398    {
399       mapplanes[ i ].counter=0;
400    }
401
402         tree->headnode = AllocNode();
403         VectorCopy( tree->mins, tree->headnode->mins );
404         VectorCopy( tree->maxs, tree->headnode->maxs );
405         c_faceLeafs = 0;
406
407         BuildFaceTree_r ( tree->headnode, list );
408
409         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
410
411         return tree;
412 }
413
414
415
416 /*
417 MakeStructuralBSPFaceList()
418 get structural brush faces
419 */
420
421 face_t *MakeStructuralBSPFaceList( brush_t *list )
422 {
423         brush_t         *b;
424         int                     i;
425         side_t          *s;
426         winding_t       *w;
427         face_t          *f, *flist;
428         
429         
430         flist = NULL;
431         for( b = list; b != NULL; b = b->next )
432         {
433                 if( !deepBSP && b->detail )
434                         continue;
435                 
436                 for( i = 0; i < b->numsides; i++ )
437                 {
438                         /* get side and winding */
439                         s = &b->sides[ i ];
440                         w = s->winding;
441                         if( w == NULL )
442                                 continue;
443                         
444                         /* ydnar: skip certain faces */
445                         if( s->compileFlags & C_SKIP )
446                                 continue;
447                         
448                         /* allocate a face */
449                         f = AllocBspFace();
450                         f->w = CopyWinding( w );
451                         f->planenum = s->planenum & ~1;
452                         f->compileFlags = s->compileFlags;      /* ydnar */
453                         if(b->detail)
454                                 f->compileFlags |= C_DETAIL;
455                         
456                         /* ydnar: set priority */
457                         f->priority = 0;
458                         if( f->compileFlags & C_HINT )
459                                 f->priority += HINT_PRIORITY;
460                         if( f->compileFlags & C_ANTIPORTAL )
461                                 f->priority += ANTIPORTAL_PRIORITY;
462                         if( f->compileFlags & C_AREAPORTAL )
463                                 f->priority += AREAPORTAL_PRIORITY;
464                         if( f->compileFlags & C_DETAIL )
465                                 f->priority += DETAIL_PRIORITY;
466                         
467                         /* get next face */
468                         f->next = flist;
469                         flist = f;
470                 }
471         }
472         
473         return flist;
474 }
475
476
477
478 /*
479 MakeVisibleBSPFaceList()
480 get visible brush faces
481 */
482
483 face_t *MakeVisibleBSPFaceList( brush_t *list )
484 {
485         brush_t         *b;
486         int                     i;
487         side_t          *s;
488         winding_t       *w;
489         face_t          *f, *flist;
490         
491         
492         flist = NULL;
493         for( b = list; b != NULL; b = b->next )
494         {
495                 if( !deepBSP && b->detail )
496                         continue;
497                 
498                 for( i = 0; i < b->numsides; i++ )
499                 {
500                         /* get side and winding */
501                         s = &b->sides[ i ];
502                         w = s->visibleHull;
503                         if( w == NULL )
504                                 continue;
505                         
506                         /* ydnar: skip certain faces */
507                         if( s->compileFlags & C_SKIP )
508                                 continue;
509                         
510                         /* allocate a face */
511                         f = AllocBspFace();
512                         f->w = CopyWinding( w );
513                         f->planenum = s->planenum & ~1;
514                         f->compileFlags = s->compileFlags;      /* ydnar */
515                         if(b->detail)
516                                 f->compileFlags |= C_DETAIL;
517                         
518                         /* ydnar: set priority */
519                         f->priority = 0;
520                         if( f->compileFlags & C_HINT )
521                                 f->priority += HINT_PRIORITY;
522                         if( f->compileFlags & C_ANTIPORTAL )
523                                 f->priority += ANTIPORTAL_PRIORITY;
524                         if( f->compileFlags & C_AREAPORTAL )
525                                 f->priority += AREAPORTAL_PRIORITY;
526                         if( f->compileFlags & C_DETAIL )
527                                 f->priority += DETAIL_PRIORITY;
528                         
529                         /* get next face */
530                         f->next = flist;
531                         flist = f;
532                 }
533         }
534         
535         return flist;
536 }
537