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