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