set eol-style
[xonotic/netradiant.git] / tools / quake3 / q3map2 / facebsp.c
1 /*
2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20
21 ----------------------------------------------------------------------------------
22
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
25
26 ------------------------------------------------------------------------------- */
27
28
29
30 /* marker */
31 #define FACEBSP_C
32
33
34
35 /* dependencies */
36 #include "q3map2.h"
37
38
39
40 int                     c_faceLeafs;
41
42
43 /*
44 ================
45 AllocBspFace
46 ================
47 */
48 face_t  *AllocBspFace( void ) {
49         face_t  *f;
50
51         f = safe_malloc(sizeof(*f));
52         memset( f, 0, sizeof(*f) );
53
54         return f;
55 }
56
57
58
59 /*
60 ================
61 FreeBspFace
62 ================
63 */
64 void    FreeBspFace( face_t *f ) {
65         if ( f->w ) {
66                 FreeWinding( f->w );
67         }
68         free( f );
69 }
70
71
72
73 /*
74 SelectSplitPlaneNum()
75 finds the best split plane for this node
76 */
77
78 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )
79 {
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         
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                 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
106                 if( node->maxs[ i ] > dist )
107                 {
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         for( split = list; split; split = split->next )
121                 split->checked = qfalse;
122         
123         for( split = list; split; split = split->next )
124         {
125                 if ( split->checked )
126                         continue;
127                 
128                 plane = &mapplanes[ split->planenum ];
129                 splits = 0;
130                 facing = 0;
131                 front = 0;
132                 back = 0;
133                 for ( check = list ; check ; check = check->next ) {
134                         if ( check->planenum == split->planenum ) {
135                                 facing++;
136                                 check->checked = qtrue; // won't need to test this plane again
137                                 continue;
138                         }
139                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
140                         if ( side == SIDE_CROSS ) {
141                                 splits++;
142                         } else if ( side == SIDE_FRONT ) {
143                                 front++;
144                         } else if ( side == SIDE_BACK ) {
145                                 back++;
146                         }
147                 }
148                 value =  5*facing - 5*splits; // - abs(front-back);
149                 if ( plane->type < 3 ) {
150                         value+=5;               // axial is better
151                 }
152                 value += split->priority;               // prioritize hints higher
153
154                 if ( value > bestValue ) {
155                         bestValue = value;
156                         bestSplit = split;
157                 }
158         }
159         
160         /* nothing, we have a leaf */
161         if( bestValue == -99999 )
162                 return;
163         
164         /* set best split data */
165         *splitPlaneNum = bestSplit->planenum;
166         *compileFlags = bestSplit->compileFlags;
167 }
168
169
170
171 /*
172 CountFaceList()
173 counts bsp faces in the linked list
174 */
175
176 int     CountFaceList( face_t *list )
177 {
178         int             c;
179         
180
181         c = 0;
182         for( list; list != NULL; list = list->next )
183                 c++;
184         return c;
185 }
186
187
188
189 /*
190 BuildFaceTree_r()
191 recursively builds the bsp, splitting on face planes
192 */
193
194 void BuildFaceTree_r( node_t *node, face_t *list )
195 {
196         face_t          *split;
197         face_t          *next;
198         int                     side;
199         plane_t         *plane;
200         face_t          *newFace;
201         face_t          *childLists[2];
202         winding_t       *frontWinding, *backWinding;
203         int                     i;
204         int                     splitPlaneNum, compileFlags;
205         
206         
207         /* count faces left */
208         i = CountFaceList( list );
209         
210         /* select the best split plane */
211         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
212         
213         /* if we don't have any more faces, this is a node */
214         if ( splitPlaneNum == -1 )
215         {
216                 node->planenum = PLANENUM_LEAF;
217                 c_faceLeafs++;
218                 return;
219         }
220         
221         /* partition the list */
222         node->planenum = splitPlaneNum;
223         node->compileFlags = compileFlags;
224         plane = &mapplanes[ splitPlaneNum ];
225         childLists[0] = NULL;
226         childLists[1] = NULL;
227         for( split = list; split; split = next )
228         {
229                 /* set next */
230                 next = split->next;
231                 
232                 /* don't split by identical plane */
233                 if( split->planenum == node->planenum )
234                 {
235                         FreeBspFace( split );
236                         continue;
237                 }
238                 
239                 /* determine which side the face falls on */
240                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
241                 
242                 /* switch on side */
243                 if( side == SIDE_CROSS )
244                 {
245                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
246                                 &frontWinding, &backWinding );
247                         if( frontWinding ) {
248                                 newFace = AllocBspFace();
249                                 newFace->w = frontWinding;
250                                 newFace->next = childLists[0];
251                                 newFace->planenum = split->planenum;
252                                 newFace->priority = split->priority;
253                                 newFace->compileFlags = split->compileFlags;
254                                 childLists[0] = newFace;
255                         }
256                         if( backWinding ) {
257                                 newFace = AllocBspFace();
258                                 newFace->w = backWinding;
259                                 newFace->next = childLists[1];
260                                 newFace->planenum = split->planenum;
261                                 newFace->priority = split->priority;
262                                 newFace->compileFlags = split->compileFlags;
263                                 childLists[1] = newFace;
264                         }
265                         FreeBspFace( split );
266                 } else if ( side == SIDE_FRONT ) {
267                         split->next = childLists[0];
268                         childLists[0] = split;
269                 } else if ( side == SIDE_BACK ) {
270                         split->next = childLists[1];
271                         childLists[1] = split;
272                 }
273         }
274
275
276         // recursively process children
277         for ( i = 0 ; i < 2 ; i++ ) {
278                 node->children[i] = AllocNode();
279                 node->children[i]->parent = node;
280                 VectorCopy( node->mins, node->children[i]->mins );
281                 VectorCopy( node->maxs, node->children[i]->maxs );
282         }
283
284         for ( i = 0 ; i < 3 ; i++ ) {
285                 if ( plane->normal[i] == 1 ) {
286                         node->children[0]->mins[i] = plane->dist;
287                         node->children[1]->maxs[i] = plane->dist;
288                         break;
289                 }
290         }
291
292         for ( i = 0 ; i < 2 ; i++ ) {
293                 BuildFaceTree_r ( node->children[i], childLists[i]);
294         }
295 }
296
297
298 /*
299 ================
300 FaceBSP
301
302 List will be freed before returning
303 ================
304 */
305 tree_t *FaceBSP( face_t *list ) {
306         tree_t          *tree;
307         face_t  *face;
308         int                     i;
309         int                     count;
310
311         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
312
313         tree = AllocTree ();
314
315         count = 0;
316         for( face = list; face != NULL; face = face->next )
317         {
318                 count++;
319                 for( i = 0; i < face->w->numpoints; i++ )
320                 {
321                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
322                 }
323         }
324         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
325
326         tree->headnode = AllocNode();
327         VectorCopy( tree->mins, tree->headnode->mins );
328         VectorCopy( tree->maxs, tree->headnode->maxs );
329         c_faceLeafs = 0;
330
331         BuildFaceTree_r ( tree->headnode, list );
332
333         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
334
335         return tree;
336 }
337
338
339
340 /*
341 MakeStructuralBSPFaceList()
342 get structural brush faces
343 */
344
345 face_t *MakeStructuralBSPFaceList( brush_t *list )
346 {
347         brush_t         *b;
348         int                     i;
349         side_t          *s;
350         winding_t       *w;
351         face_t          *f, *flist;
352         
353         
354         flist = NULL;
355         for( b = list; b != NULL; b = b->next )
356         {
357                 if( b->detail )
358                         continue;
359                 
360                 for( i = 0; i < b->numsides; i++ )
361                 {
362                         /* get side and winding */
363                         s = &b->sides[ i ];
364                         w = s->winding;
365                         if( w == NULL )
366                                 continue;
367                         
368                         /* ydnar: skip certain faces */
369                         if( s->compileFlags & C_SKIP )
370                                 continue;
371                         
372                         /* allocate a face */
373                         f = AllocBspFace();
374                         f->w = CopyWinding( w );
375                         f->planenum = s->planenum & ~1;
376                         f->compileFlags = s->compileFlags;      /* ydnar */
377                         
378                         /* ydnar: set priority */
379                         f->priority = 0;
380                         if( f->compileFlags & C_HINT )
381                                 f->priority += HINT_PRIORITY;
382                         if( f->compileFlags & C_ANTIPORTAL )
383                                 f->priority += ANTIPORTAL_PRIORITY;
384                         if( f->compileFlags & C_AREAPORTAL )
385                                 f->priority += AREAPORTAL_PRIORITY;
386                         
387                         /* get next face */
388                         f->next = flist;
389                         flist = f;
390                 }
391         }
392         
393         return flist;
394 }
395
396
397
398 /*
399 MakeVisibleBSPFaceList()
400 get visible brush faces
401 */
402
403 face_t *MakeVisibleBSPFaceList( brush_t *list )
404 {
405         brush_t         *b;
406         int                     i;
407         side_t          *s;
408         winding_t       *w;
409         face_t          *f, *flist;
410         
411         
412         flist = NULL;
413         for( b = list; b != NULL; b = b->next )
414         {
415                 if( b->detail )
416                         continue;
417                 
418                 for( i = 0; i < b->numsides; i++ )
419                 {
420                         /* get side and winding */
421                         s = &b->sides[ i ];
422                         w = s->visibleHull;
423                         if( w == NULL )
424                                 continue;
425                         
426                         /* ydnar: skip certain faces */
427                         if( s->compileFlags & C_SKIP )
428                                 continue;
429                         
430                         /* allocate a face */
431                         f = AllocBspFace();
432                         f->w = CopyWinding( w );
433                         f->planenum = s->planenum & ~1;
434                         f->compileFlags = s->compileFlags;      /* ydnar */
435                         
436                         /* ydnar: set priority */
437                         f->priority = 0;
438                         if( f->compileFlags & C_HINT )
439                                 f->priority += HINT_PRIORITY;
440                         if( f->compileFlags & C_ANTIPORTAL )
441                                 f->priority += ANTIPORTAL_PRIORITY;
442                         if( f->compileFlags & C_AREAPORTAL )
443                                 f->priority += AREAPORTAL_PRIORITY;
444                         
445                         /* get next face */
446                         f->next = flist;
447                         flist = f;
448                 }
449         }
450         
451         return flist;
452 }
453