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