fix two msvc compile errors
[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         qboolean isstruct = qfalse;
248         
249         
250         /* count faces left */
251         i = CountFaceList( list );
252         
253         /* select the best split plane */
254         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
255         
256         /* if we don't have any more faces, this is a node */
257         if ( splitPlaneNum == -1 )
258         {
259                 node->planenum = PLANENUM_LEAF;
260                 node->has_structural_children = qfalse;
261                 c_faceLeafs++;
262                 return;
263         }
264         
265         /* partition the list */
266         node->planenum = splitPlaneNum;
267         node->compileFlags = compileFlags;
268         node->has_structural_children = !(compileFlags & C_DETAIL) && !node->opaque;
269         plane = &mapplanes[ splitPlaneNum ];
270         childLists[0] = NULL;
271         childLists[1] = NULL;
272
273         for( split = list; split; split = next )
274         {
275                 /* set next */
276                 next = split->next;
277                 
278                 /* don't split by identical plane */
279                 if( split->planenum == node->planenum )
280                 {
281                         FreeBspFace( split );
282                         continue;
283                 }
284
285                 if(!(split->compileFlags & C_DETAIL))
286                         isstruct = 1;
287                 
288                 /* determine which side the face falls on */
289                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
290                 
291                 /* switch on side */
292                 if( side == SIDE_CROSS )
293                 {
294                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
295                                 &frontWinding, &backWinding );
296                         if( frontWinding ) {
297                                 newFace = AllocBspFace();
298                                 newFace->w = frontWinding;
299                                 newFace->next = childLists[0];
300                                 newFace->planenum = split->planenum;
301                                 newFace->priority = split->priority;
302                                 newFace->compileFlags = split->compileFlags;
303                                 childLists[0] = newFace;
304                         }
305                         if( backWinding ) {
306                                 newFace = AllocBspFace();
307                                 newFace->w = backWinding;
308                                 newFace->next = childLists[1];
309                                 newFace->planenum = split->planenum;
310                                 newFace->priority = split->priority;
311                                 newFace->compileFlags = split->compileFlags;
312                                 childLists[1] = newFace;
313                         }
314                         FreeBspFace( split );
315                 } else if ( side == SIDE_FRONT ) {
316                         split->next = childLists[0];
317                         childLists[0] = split;
318                 } else if ( side == SIDE_BACK ) {
319                         split->next = childLists[1];
320                         childLists[1] = split;
321                 }
322         }
323
324
325         // recursively process children
326         for ( i = 0 ; i < 2 ; i++ ) {
327                 node->children[i] = AllocNode();
328                 node->children[i]->parent = node;
329                 VectorCopy( node->mins, node->children[i]->mins );
330                 VectorCopy( node->maxs, node->children[i]->maxs );
331         }
332
333         for ( i = 0 ; i < 3 ; i++ ) {
334                 if ( plane->normal[i] == 1 ) {
335                         node->children[0]->mins[i] = plane->dist;
336                         node->children[1]->maxs[i] = plane->dist;
337                         break;
338                 }
339         }
340
341 #if 0
342         if((node->compileFlags & C_DETAIL) && isstruct)
343                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children);
344 #endif
345
346         for ( i = 0 ; i < 2 ; i++ ) {
347                 BuildFaceTree_r ( node->children[i], childLists[i]);
348                 node->has_structural_children |= node->children[i]->has_structural_children;
349         }
350
351 #if 0
352         if((node->compileFlags & C_DETAIL) && !(node->children[0]->compileFlags & C_DETAIL) && node->children[0]->planenum != PLANENUM_LEAF)
353                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children);
354         if((node->compileFlags & C_DETAIL) && isstruct)
355                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children);
356 #endif
357 }
358
359
360 /*
361 ================
362 FaceBSP
363
364 List will be freed before returning
365 ================
366 */
367 tree_t *FaceBSP( face_t *list ) {
368         tree_t          *tree;
369         face_t  *face;
370         int                     i;
371         int                     count;
372
373         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
374
375         tree = AllocTree ();
376
377         count = 0;
378         for( face = list; face != NULL; face = face->next )
379         {
380                 count++;
381                 for( i = 0; i < face->w->numpoints; i++ )
382                 {
383                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
384                 }
385         }
386         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
387
388    for( i = 0; i < nummapplanes; i++)
389    {
390       mapplanes[ i ].counter=0;
391    }
392
393         tree->headnode = AllocNode();
394         VectorCopy( tree->mins, tree->headnode->mins );
395         VectorCopy( tree->maxs, tree->headnode->maxs );
396         c_faceLeafs = 0;
397
398         BuildFaceTree_r ( tree->headnode, list );
399
400         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
401
402         return tree;
403 }
404
405
406
407 /*
408 MakeStructuralBSPFaceList()
409 get structural brush faces
410 */
411
412 face_t *MakeStructuralBSPFaceList( brush_t *list )
413 {
414         brush_t         *b;
415         int                     i;
416         side_t          *s;
417         winding_t       *w;
418         face_t          *f, *flist;
419         
420         
421         flist = NULL;
422         for( b = list; b != NULL; b = b->next )
423         {
424                 if( !deepBSP && b->detail )
425                         continue;
426                 
427                 for( i = 0; i < b->numsides; i++ )
428                 {
429                         /* get side and winding */
430                         s = &b->sides[ i ];
431                         w = s->winding;
432                         if( w == NULL )
433                                 continue;
434                         
435                         /* ydnar: skip certain faces */
436                         if( s->compileFlags & C_SKIP )
437                                 continue;
438                         
439                         /* allocate a face */
440                         f = AllocBspFace();
441                         f->w = CopyWinding( w );
442                         f->planenum = s->planenum & ~1;
443                         f->compileFlags = s->compileFlags;      /* ydnar */
444                         if(b->detail)
445                                 f->compileFlags |= C_DETAIL;
446                         
447                         /* ydnar: set priority */
448                         f->priority = 0;
449                         if( f->compileFlags & C_HINT )
450                                 f->priority += HINT_PRIORITY;
451                         if( f->compileFlags & C_ANTIPORTAL )
452                                 f->priority += ANTIPORTAL_PRIORITY;
453                         if( f->compileFlags & C_AREAPORTAL )
454                                 f->priority += AREAPORTAL_PRIORITY;
455                         if( f->compileFlags & C_DETAIL )
456                                 f->priority += DETAIL_PRIORITY;
457                         
458                         /* get next face */
459                         f->next = flist;
460                         flist = f;
461                 }
462         }
463         
464         return flist;
465 }
466
467
468
469 /*
470 MakeVisibleBSPFaceList()
471 get visible brush faces
472 */
473
474 face_t *MakeVisibleBSPFaceList( brush_t *list )
475 {
476         brush_t         *b;
477         int                     i;
478         side_t          *s;
479         winding_t       *w;
480         face_t          *f, *flist;
481         
482         
483         flist = NULL;
484         for( b = list; b != NULL; b = b->next )
485         {
486                 if( !deepBSP && b->detail )
487                         continue;
488                 
489                 for( i = 0; i < b->numsides; i++ )
490                 {
491                         /* get side and winding */
492                         s = &b->sides[ i ];
493                         w = s->visibleHull;
494                         if( w == NULL )
495                                 continue;
496                         
497                         /* ydnar: skip certain faces */
498                         if( s->compileFlags & C_SKIP )
499                                 continue;
500                         
501                         /* allocate a face */
502                         f = AllocBspFace();
503                         f->w = CopyWinding( w );
504                         f->planenum = s->planenum & ~1;
505                         f->compileFlags = s->compileFlags;      /* ydnar */
506                         if(b->detail)
507                                 f->compileFlags |= C_DETAIL;
508                         
509                         /* ydnar: set priority */
510                         f->priority = 0;
511                         if( f->compileFlags & C_HINT )
512                                 f->priority += HINT_PRIORITY;
513                         if( f->compileFlags & C_ANTIPORTAL )
514                                 f->priority += ANTIPORTAL_PRIORITY;
515                         if( f->compileFlags & C_AREAPORTAL )
516                                 f->priority += AREAPORTAL_PRIORITY;
517                         if( f->compileFlags & C_DETAIL )
518                                 f->priority += DETAIL_PRIORITY;
519                         
520                         /* get next face */
521                         f->next = flist;
522                         flist = f;
523                 }
524         }
525         
526         return flist;
527 }
528