uncrustify! now the code is only ugly on the *inside*
[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
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         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
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                         }
144                         else if ( side == SIDE_FRONT ) {
145                                 front++;
146                         }
147                         else if ( side == SIDE_BACK ) {
148                                 back++;
149                         }
150                 }
151                 value =  5 * facing - 5 * splits; // - abs(front-back);
152                 if ( plane->type < 3 ) {
153                         value += 5;       // axial is better
154                 }
155                 value += split->priority;       // prioritize hints higher
156
157                 if ( value > bestValue ) {
158                         bestValue = value;
159                         bestSplit = split;
160                 }
161         }
162
163         /* nothing, we have a leaf */
164         if ( bestValue == -99999 ) {
165                 return;
166         }
167
168         /* set best split data */
169         *splitPlaneNum = bestSplit->planenum;
170         *compileFlags = bestSplit->compileFlags;
171 }
172
173
174
175 /*
176    CountFaceList()
177    counts bsp faces in the linked list
178  */
179
180 int CountFaceList( face_t *list ){
181         int c;
182
183
184         c = 0;
185         for ( ; list != NULL; list = list->next )
186                 c++;
187         return c;
188 }
189
190
191
192 /*
193    BuildFaceTree_r()
194    recursively builds the bsp, splitting on face planes
195  */
196
197 void BuildFaceTree_r( node_t *node, face_t *list ){
198         face_t      *split;
199         face_t      *next;
200         int side;
201         plane_t     *plane;
202         face_t      *newFace;
203         face_t      *childLists[2];
204         winding_t   *frontWinding, *backWinding;
205         int i;
206         int splitPlaneNum, compileFlags;
207
208
209         /* count faces left */
210         i = CountFaceList( list );
211
212         /* select the best split plane */
213         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
214
215         /* if we don't have any more faces, this is a node */
216         if ( splitPlaneNum == -1 ) {
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                         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                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
245                                                                 &frontWinding, &backWinding );
246                         if ( frontWinding ) {
247                                 newFace = AllocBspFace();
248                                 newFace->w = frontWinding;
249                                 newFace->next = childLists[0];
250                                 newFace->planenum = split->planenum;
251                                 newFace->priority = split->priority;
252                                 newFace->compileFlags = split->compileFlags;
253                                 childLists[0] = newFace;
254                         }
255                         if ( backWinding ) {
256                                 newFace = AllocBspFace();
257                                 newFace->w = backWinding;
258                                 newFace->next = childLists[1];
259                                 newFace->planenum = split->planenum;
260                                 newFace->priority = split->priority;
261                                 newFace->compileFlags = split->compileFlags;
262                                 childLists[1] = newFace;
263                         }
264                         FreeBspFace( split );
265                 }
266                 else if ( side == SIDE_FRONT ) {
267                         split->next = childLists[0];
268                         childLists[0] = split;
269                 }
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         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
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
370                         /* ydnar: skip certain faces */
371                         if ( s->compileFlags & C_SKIP ) {
372                                 continue;
373                         }
374
375                         /* allocate a face */
376                         f = AllocBspFace();
377                         f->w = CopyWinding( w );
378                         f->planenum = s->planenum & ~1;
379                         f->compileFlags = s->compileFlags;  /* ydnar */
380
381                         /* ydnar: set priority */
382                         f->priority = 0;
383                         if ( f->compileFlags & C_HINT ) {
384                                 f->priority += HINT_PRIORITY;
385                         }
386                         if ( f->compileFlags & C_ANTIPORTAL ) {
387                                 f->priority += ANTIPORTAL_PRIORITY;
388                         }
389                         if ( f->compileFlags & C_AREAPORTAL ) {
390                                 f->priority += AREAPORTAL_PRIORITY;
391                         }
392
393                         /* get next face */
394                         f->next = flist;
395                         flist = f;
396                 }
397         }
398
399         return flist;
400 }
401
402
403
404 /*
405    MakeVisibleBSPFaceList()
406    get visible brush faces
407  */
408
409 face_t *MakeVisibleBSPFaceList( brush_t *list ){
410         brush_t     *b;
411         int i;
412         side_t      *s;
413         winding_t   *w;
414         face_t      *f, *flist;
415
416
417         flist = NULL;
418         for ( b = list; b != NULL; b = b->next )
419         {
420                 if ( b->detail ) {
421                         continue;
422                 }
423
424                 for ( i = 0; i < b->numsides; i++ )
425                 {
426                         /* get side and winding */
427                         s = &b->sides[ i ];
428                         w = s->visibleHull;
429                         if ( w == NULL ) {
430                                 continue;
431                         }
432
433                         /* ydnar: skip certain faces */
434                         if ( s->compileFlags & C_SKIP ) {
435                                 continue;
436                         }
437
438                         /* allocate a face */
439                         f = AllocBspFace();
440                         f->w = CopyWinding( w );
441                         f->planenum = s->planenum & ~1;
442                         f->compileFlags = s->compileFlags;  /* ydnar */
443
444                         /* ydnar: set priority */
445                         f->priority = 0;
446                         if ( f->compileFlags & C_HINT ) {
447                                 f->priority += HINT_PRIORITY;
448                         }
449                         if ( f->compileFlags & C_ANTIPORTAL ) {
450                                 f->priority += ANTIPORTAL_PRIORITY;
451                         }
452                         if ( f->compileFlags & C_AREAPORTAL ) {
453                                 f->priority += AREAPORTAL_PRIORITY;
454                         }
455
456                         /* get next face */
457                         f->next = flist;
458                         flist = f;
459                 }
460         }
461
462         return flist;
463 }