270eefe280014c415b15031a73ed1b331834a0f9
[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         
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                 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
107                 if( node->maxs[ i ] > dist )
108                 {
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         for( split = list; split; split = split->next )
122                 split->checked = qfalse;
123         
124         for( split = list; split; split = split->next )
125         {
126                 if ( split->checked )
127                         continue;
128                 
129                 plane = &mapplanes[ split->planenum ];
130                 splits = 0;
131                 facing = 0;
132                 front = 0;
133                 back = 0;
134                 for ( check = list ; check ; check = check->next ) {
135                         if ( check->planenum == split->planenum ) {
136                                 facing++;
137                                 check->checked = qtrue; // won't need to test this plane again
138                                 continue;
139                         }
140                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
141                         if ( side == SIDE_CROSS ) {
142                                 splits++;
143                         } else if ( side == SIDE_FRONT ) {
144                                 front++;
145                         } else if ( side == SIDE_BACK ) {
146                                 back++;
147                         }
148                 }
149                 value =  5*facing - 5*splits; // - abs(front-back);
150                 if ( plane->type < 3 ) {
151                         value+=5;               // axial is better
152                 }
153                 value += split->priority;               // prioritize hints higher
154
155                 if ( value > bestValue ) {
156                         bestValue = value;
157                         bestSplit = split;
158                 }
159         }
160         
161         /* nothing, we have a leaf */
162         if( bestValue == -99999 )
163                 return;
164         
165         /* set best split data */
166         *splitPlaneNum = bestSplit->planenum;
167         *compileFlags = bestSplit->compileFlags;
168 }
169
170
171
172 /*
173 CountFaceList()
174 counts bsp faces in the linked list
175 */
176
177 int     CountFaceList( face_t *list )
178 {
179         int             c;
180         
181
182         c = 0;
183         for( ; list != NULL; list = list->next )
184                 c++;
185         return c;
186 }
187
188
189
190 /*
191 BuildFaceTree_r()
192 recursively builds the bsp, splitting on face planes
193 */
194
195 void BuildFaceTree_r( node_t *node, face_t *list )
196 {
197         face_t          *split;
198         face_t          *next;
199         int                     side;
200         plane_t         *plane;
201         face_t          *newFace;
202         face_t          *childLists[2];
203         winding_t       *frontWinding, *backWinding;
204         int                     i;
205         int                     splitPlaneNum, compileFlags;
206         
207         
208         /* count faces left */
209         i = CountFaceList( list );
210         
211         /* select the best split plane */
212         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
213         
214         /* if we don't have any more faces, this is a node */
215         if ( splitPlaneNum == -1 )
216         {
217                 node->planenum = PLANENUM_LEAF;
218                 c_faceLeafs++;
219                 return;
220         }
221         
222         /* partition the list */
223         node->planenum = splitPlaneNum;
224         node->compileFlags = compileFlags;
225         plane = &mapplanes[ splitPlaneNum ];
226         childLists[0] = NULL;
227         childLists[1] = NULL;
228         for( split = list; split; split = next )
229         {
230                 /* set next */
231                 next = split->next;
232                 
233                 /* don't split by identical plane */
234                 if( split->planenum == node->planenum )
235                 {
236                         FreeBspFace( split );
237                         continue;
238                 }
239                 
240                 /* determine which side the face falls on */
241                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
242                 
243                 /* switch on side */
244                 if( side == SIDE_CROSS )
245                 {
246                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
247                                 &frontWinding, &backWinding );
248                         if( frontWinding ) {
249                                 newFace = AllocBspFace();
250                                 newFace->w = frontWinding;
251                                 newFace->next = childLists[0];
252                                 newFace->planenum = split->planenum;
253                                 newFace->priority = split->priority;
254                                 newFace->compileFlags = split->compileFlags;
255                                 childLists[0] = newFace;
256                         }
257                         if( backWinding ) {
258                                 newFace = AllocBspFace();
259                                 newFace->w = backWinding;
260                                 newFace->next = childLists[1];
261                                 newFace->planenum = split->planenum;
262                                 newFace->priority = split->priority;
263                                 newFace->compileFlags = split->compileFlags;
264                                 childLists[1] = newFace;
265                         }
266                         FreeBspFace( split );
267                 } else if ( side == SIDE_FRONT ) {
268                         split->next = childLists[0];
269                         childLists[0] = split;
270                 } else if ( side == SIDE_BACK ) {
271                         split->next = childLists[1];
272                         childLists[1] = split;
273                 }
274         }
275
276
277         // recursively process children
278         for ( i = 0 ; i < 2 ; i++ ) {
279                 node->children[i] = AllocNode();
280                 node->children[i]->parent = node;
281                 VectorCopy( node->mins, node->children[i]->mins );
282                 VectorCopy( node->maxs, node->children[i]->maxs );
283         }
284
285         for ( i = 0 ; i < 3 ; i++ ) {
286                 if ( plane->normal[i] == 1 ) {
287                         node->children[0]->mins[i] = plane->dist;
288                         node->children[1]->maxs[i] = plane->dist;
289                         break;
290                 }
291         }
292
293         for ( i = 0 ; i < 2 ; i++ ) {
294                 BuildFaceTree_r ( node->children[i], childLists[i]);
295         }
296 }
297
298
299 /*
300 ================
301 FaceBSP
302
303 List will be freed before returning
304 ================
305 */
306 tree_t *FaceBSP( face_t *list ) {
307         tree_t          *tree;
308         face_t  *face;
309         int                     i;
310         int                     count;
311
312         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
313
314         tree = AllocTree ();
315
316         count = 0;
317         for( face = list; face != NULL; face = face->next )
318         {
319                 count++;
320                 for( i = 0; i < face->w->numpoints; i++ )
321                 {
322                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
323                 }
324         }
325         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
326
327         tree->headnode = AllocNode();
328         VectorCopy( tree->mins, tree->headnode->mins );
329         VectorCopy( tree->maxs, tree->headnode->maxs );
330         c_faceLeafs = 0;
331
332         BuildFaceTree_r ( tree->headnode, list );
333
334         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
335
336         return tree;
337 }
338
339
340
341 /*
342 MakeStructuralBSPFaceList()
343 get structural brush faces
344 */
345
346 face_t *MakeStructuralBSPFaceList( brush_t *list )
347 {
348         brush_t         *b;
349         int                     i;
350         side_t          *s;
351         winding_t       *w;
352         face_t          *f, *flist;
353         
354         
355         flist = NULL;
356         for( b = list; b != NULL; b = b->next )
357         {
358                 if( b->detail )
359                         continue;
360                 
361                 for( i = 0; i < b->numsides; i++ )
362                 {
363                         /* get side and winding */
364                         s = &b->sides[ i ];
365                         w = s->winding;
366                         if( w == NULL )
367                                 continue;
368                         
369                         /* ydnar: skip certain faces */
370                         if( s->compileFlags & C_SKIP )
371                                 continue;
372                         
373                         /* allocate a face */
374                         f = AllocBspFace();
375                         f->w = CopyWinding( w );
376                         f->planenum = s->planenum & ~1;
377                         f->compileFlags = s->compileFlags;      /* ydnar */
378                         
379                         /* ydnar: set priority */
380                         f->priority = 0;
381                         if( f->compileFlags & C_HINT )
382                                 f->priority += HINT_PRIORITY;
383                         if( f->compileFlags & C_ANTIPORTAL )
384                                 f->priority += ANTIPORTAL_PRIORITY;
385                         if( f->compileFlags & C_AREAPORTAL )
386                                 f->priority += AREAPORTAL_PRIORITY;
387                         
388                         /* get next face */
389                         f->next = flist;
390                         flist = f;
391                 }
392         }
393         
394         return flist;
395 }
396
397
398
399 /*
400 MakeVisibleBSPFaceList()
401 get visible brush faces
402 */
403
404 face_t *MakeVisibleBSPFaceList( brush_t *list )
405 {
406         brush_t         *b;
407         int                     i;
408         side_t          *s;
409         winding_t       *w;
410         face_t          *f, *flist;
411         
412         
413         flist = NULL;
414         for( b = list; b != NULL; b = b->next )
415         {
416                 if( b->detail )
417                         continue;
418                 
419                 for( i = 0; i < b->numsides; i++ )
420                 {
421                         /* get side and winding */
422                         s = &b->sides[ i ];
423                         w = s->visibleHull;
424                         if( w == NULL )
425                                 continue;
426                         
427                         /* ydnar: skip certain faces */
428                         if( s->compileFlags & C_SKIP )
429                                 continue;
430                         
431                         /* allocate a face */
432                         f = AllocBspFace();
433                         f->w = CopyWinding( w );
434                         f->planenum = s->planenum & ~1;
435                         f->compileFlags = s->compileFlags;      /* ydnar */
436                         
437                         /* ydnar: set priority */
438                         f->priority = 0;
439                         if( f->compileFlags & C_HINT )
440                                 f->priority += HINT_PRIORITY;
441                         if( f->compileFlags & C_ANTIPORTAL )
442                                 f->priority += ANTIPORTAL_PRIORITY;
443                         if( f->compileFlags & C_AREAPORTAL )
444                                 f->priority += AREAPORTAL_PRIORITY;
445                         
446                         /* get next face */
447                         f->next = flist;
448                         flist = f;
449                 }
450         }
451         
452         return flist;
453 }
454