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