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