File: | tools/ufo2map/csg.cpp |
Location: | line 464, column 5 |
Description: | Value stored to 'tail' is never read |
1 | /** |
2 | * @file |
3 | * @brief Constructive Solids Geometry |
4 | * @note tag all brushes with original contents |
5 | * brushes may contain multiple contents |
6 | * there will be no brush overlap after csg phase |
7 | * |
8 | * each side has a count of the other sides it splits |
9 | * |
10 | * the best split will be the one that minimizes the total split counts |
11 | * of all remaining sides |
12 | * |
13 | * precalc side on plane table |
14 | * |
15 | * evaluate split side |
16 | * @code |
17 | * { |
18 | * cost = 0 |
19 | * for all sides |
20 | * for all sides |
21 | * get |
22 | * if side splits side and splitside is on same child |
23 | * cost++; |
24 | * } |
25 | * @endcode |
26 | */ |
27 | |
28 | /* |
29 | Copyright (C) 1997-2001 Id Software, Inc. |
30 | |
31 | This program is free software; you can redistribute it and/or |
32 | modify it under the terms of the GNU General Public License |
33 | as published by the Free Software Foundation; either version 2 |
34 | of the License, or (at your option) any later version. |
35 | |
36 | This program is distributed in the hope that it will be useful, |
37 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
38 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
39 | |
40 | See the GNU General Public License for more details. |
41 | |
42 | You should have received a copy of the GNU General Public License |
43 | along with this program; if not, write to the Free Software |
44 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
45 | |
46 | */ |
47 | |
48 | #include "bsp.h" |
49 | |
50 | /** |
51 | * @return a list of brushes that remain after B is subtracted from A. |
52 | * @note Return may by empty if A is contained inside B. |
53 | * @note The originals are undisturbed. |
54 | */ |
55 | static bspbrush_t *SubtractBrush (bspbrush_t *a, const bspbrush_t *b) |
56 | { |
57 | /* a - b = out (list) */ |
58 | int i; |
59 | bspbrush_t *front, *back, *out; |
60 | bspbrush_t *in; |
61 | |
62 | in = a; |
63 | out = NULL__null; |
64 | for (i = 0; i < b->numsides && in; i++) { |
65 | SplitBrush(in, b->sides[i].planenum, &front, &back); |
66 | if (in != a) |
67 | FreeBrush(in); |
68 | if (front) { /* add to list */ |
69 | front->next = out; |
70 | out = front; |
71 | } |
72 | in = back; |
73 | } |
74 | if (in) |
75 | FreeBrush(in); |
76 | else { /* didn't really intersect */ |
77 | FreeBrushList(out); |
78 | return a; |
79 | } |
80 | return out; |
81 | } |
82 | |
83 | /** |
84 | * @return true if the two brushes definately do not intersect. |
85 | * @note There will be false negatives for some non-axial combinations. |
86 | */ |
87 | static bool BrushesDisjoint (bspbrush_t *a, bspbrush_t *b) |
88 | { |
89 | int i, j; |
90 | |
91 | /* check bounding boxes */ |
92 | for (i = 0; i < 3; i++) |
93 | if (a->mins[i] >= b->maxs[i] || a->maxs[i] <= b->mins[i]) |
94 | return true; /* bounding boxes don't overlap */ |
95 | |
96 | /* check for opposing planes */ |
97 | for (i = 0; i < a->numsides; i++) { |
98 | for (j = 0; j < b->numsides; j++) { |
99 | if (a->sides[i].planenum == (b->sides[j].planenum ^ 1)) |
100 | return true; /* opposite planes, so not touching */ |
101 | } |
102 | } |
103 | |
104 | return false; /* might intersect */ |
105 | } |
106 | |
107 | static uint16_t minplanenums[2]; |
108 | static uint16_t maxplanenums[2]; |
109 | |
110 | /** |
111 | * @brief Any planes shared with the box edge will be set to no texinfo |
112 | * @note not thread safe |
113 | */ |
114 | static bspbrush_t *ClipBrushToBox (bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs) |
115 | { |
116 | int i, j; |
117 | bspbrush_t *front, *back; |
118 | |
119 | for (j = 0; j < 2; j++) { |
120 | if (brush->maxs[j] > clipmaxs[j]) { |
121 | SplitBrush(brush, maxplanenums[j], &front, &back); |
122 | FreeBrush(brush); |
123 | if (front) |
124 | FreeBrush(front); |
125 | brush = back; |
126 | if (!brush) |
127 | return NULL__null; |
128 | } |
129 | if (brush->mins[j] < clipmins[j]) { |
130 | SplitBrush(brush, minplanenums[j], &front, &back); |
131 | FreeBrush(brush); |
132 | if (back) |
133 | FreeBrush(back); |
134 | brush = front; |
135 | if (!brush) |
136 | return NULL__null; |
137 | } |
138 | } |
139 | |
140 | /* remove any colinear faces */ |
141 | for (i = 0; i < brush->numsides; i++) { |
142 | side_t *side = &brush->sides[i]; |
143 | const int p = side->planenum & ~1; |
144 | if (p == maxplanenums[0] || p == maxplanenums[1] |
145 | || p == minplanenums[0] || p == minplanenums[1]) { |
146 | side->texinfo = TEXINFO_NODE-1; |
147 | side->visible = false; |
148 | } |
149 | } |
150 | return brush; |
151 | } |
152 | |
153 | /** |
154 | * @brief checks if the level# matches the contentsmask. |
155 | * The level# is mapped to the appropriate levelflags. |
156 | * @param[in] contents The contentsmask (of the brush, surface, etc.) to check |
157 | * @param[in] level -1 for skipping the levelflag check |
158 | * @return boolean value |
159 | */ |
160 | static bool IsInLevel (const int contents, const int level) |
161 | { |
162 | /* special levels */ |
163 | switch (level) { |
164 | case LEVEL_LIGHTCLIP256: |
165 | if (contents & CONTENTS_LIGHTCLIP0x00080000) |
166 | return true; |
167 | else |
168 | return false; |
169 | case LEVEL_WEAPONCLIP257: |
170 | if (contents & CONTENTS_WEAPONCLIP0x02000000) |
171 | return true; |
172 | else |
173 | return false; |
174 | case LEVEL_ACTORCLIP258: |
175 | if (contents & CONTENTS_ACTORCLIP0x00010000) |
176 | return true; |
177 | else |
178 | return false; |
179 | } |
180 | |
181 | /* If the brush is any kind of clip, we are not looking for it after here. */ |
182 | if (contents & MASK_CLIP(0x00010000 | 0x02000000 | 0x00080000)) |
183 | return false; |
184 | |
185 | /* standard levels */ |
186 | if (level == -1) |
187 | return true; |
188 | else if (level) { |
189 | if (((contents >> 8) & 0xFF) == level) |
190 | return true; |
191 | else |
192 | return false; |
193 | } else { |
194 | if (contents & 0xFF00) |
195 | return false; |
196 | else |
197 | return true; |
198 | } |
199 | } |
200 | |
201 | static bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail) |
202 | { |
203 | bspbrush_t *walk, *next; |
204 | |
205 | /* add to end of list */ |
206 | for (walk = list; walk; walk = next) { |
207 | next = walk->next; |
208 | walk->next = NULL__null; |
209 | tail->next = walk; |
210 | tail = walk; |
211 | } |
212 | |
213 | return tail; |
214 | } |
215 | |
216 | /** |
217 | * @brief Builds a new list that doesn't hold the given brush |
218 | * @param[in] list The brush list to copy |
219 | * @param[in] skip The brush to skip |
220 | * @return a @c bspbrush_t that is the old list without the skip entry |
221 | */ |
222 | static bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip) |
223 | { |
224 | bspbrush_t *newlist; |
225 | bspbrush_t *next; |
226 | |
227 | newlist = NULL__null; |
228 | |
229 | for (; list; list = next) { |
230 | next = list->next; |
231 | if (list == skip) { |
232 | FreeBrush(list); |
233 | continue; |
234 | } |
235 | list->next = newlist; |
236 | newlist = list; |
237 | } |
238 | return newlist; |
239 | } |
240 | |
241 | /** |
242 | * @brief Returns true if b1 is allowed to bite b2 |
243 | */ |
244 | static inline bool BrushGE (bspbrush_t *b1, bspbrush_t *b2) |
245 | { |
246 | /* detail brushes never bite structural brushes */ |
247 | if ((b1->original->contentFlags & CONTENTS_DETAIL0x08000000) |
248 | && !(b2->original->contentFlags & CONTENTS_DETAIL0x08000000)) |
249 | return false; |
250 | if (b1->original->contentFlags & CONTENTS_SOLID0x0001) |
251 | return true; |
252 | return false; |
253 | } |
254 | |
255 | /** |
256 | * @brief sets mins and maxs to the smallest sizes that can contain all brushes from startbrush |
257 | * to endbrush that are in a given level. |
258 | * @param[in] startbrush the index of the first brush to check. |
259 | * @param[in] endbrush the index after the last brush to check. |
260 | * @param[in] level the level that we are searching for brushes in. -1 for skipping the levelflag check. |
261 | * @param[in] clipmins the absolute lowest boundary to allow for brushes. |
262 | * @param[in] clipmaxs the absolute highest boundary to allow for brushes. |
263 | * @param[out] mins the lowest boundary for all accepted brushes within the clipped bounds. |
264 | * @param[out] maxs the highest boundary for all accepted brushes within the clipped bounds. |
265 | * @sa ProcessSubModel |
266 | * @sa IsInLevel |
267 | */ |
268 | int MapBrushesBounds (const int startbrush, const int endbrush, const int level, const vec3_t clipmins, const vec3_t clipmaxs, vec3_t mins, vec3_t maxs) |
269 | { |
270 | int i, j, num; |
271 | |
272 | ClearBounds(mins, maxs); |
273 | num = 0; |
274 | |
275 | for (i = startbrush; i < endbrush; i++) { |
276 | const mapbrush_t *b = &mapbrushes[i]; |
277 | |
278 | /* don't use finished brushes again */ |
279 | if (b->finished) |
280 | continue; |
281 | |
282 | if (!IsInLevel(b->contentFlags, level)) |
283 | continue; |
284 | |
285 | /* check the bounds */ |
286 | for (j = 0; j < 3; j++) |
287 | if (b->mins[j] < clipmins[j] |
288 | || b->maxs[j] > clipmaxs[j]) |
289 | break; |
290 | if (j != 3) |
291 | continue; |
292 | |
293 | num++; |
294 | AddPointToBounds(b->mins, mins, maxs); |
295 | AddPointToBounds(b->maxs, mins, maxs); |
296 | } |
297 | |
298 | return num; |
299 | } |
300 | |
301 | bspbrush_t *MakeBspBrushList (int startbrush, int endbrush, int level, vec3_t clipmins, vec3_t clipmaxs) |
302 | { |
303 | bspbrush_t *brushlist, *newbrush; |
304 | int i, j, vis; |
305 | int numsides; |
306 | |
307 | Verb_Printf(VERB_DUMP, "MakeBspBrushList: bounds (%f %f %f) (%f %f %f)\n", |
308 | clipmins[0], clipmins[1], clipmins[2], clipmaxs[0], clipmaxs[1], clipmaxs[2]); |
309 | |
310 | for (i = 0; i < 2; i++) { |
311 | float dist; |
312 | vec3_t normal = {0, 0, 0}; |
313 | normal[i] = 1; |
314 | dist = clipmaxs[i]; |
315 | maxplanenums[i] = FindOrCreateFloatPlane(normal, dist); |
316 | dist = clipmins[i]; |
317 | minplanenums[i] = FindOrCreateFloatPlane(normal, dist); |
318 | } |
319 | |
320 | brushlist = NULL__null; |
321 | |
322 | for (i = startbrush; i < endbrush; i++) { |
323 | mapbrush_t *mb = &mapbrushes[i]; |
324 | |
325 | if (!IsInLevel(mb->contentFlags, level)){ |
326 | Verb_Printf(VERB_DUMP, "Rejected brush %i: wrong level.\n", i); |
327 | continue; |
328 | } |
329 | |
330 | if (mb->finished){ |
331 | Verb_Printf(VERB_DUMP, "Rejected brush %i: already finished.\n", i); |
332 | continue; |
333 | } |
334 | |
335 | numsides = mb->numsides; |
336 | if (!numsides) { |
337 | Verb_Printf(VERB_DUMP, "Rejected brush %i: no sides.\n", i); |
338 | continue; |
339 | } |
340 | |
341 | /* make sure the brush has at least one face showing */ |
342 | vis = 0; |
343 | for (j = 0; j < numsides; j++) |
344 | if (mb->original_sides[j].visible && mb->original_sides[j].winding) |
345 | vis++; |
346 | |
347 | /* if the brush is outside the clip area, skip it */ |
348 | for (j = 0; j < 3; j++) |
349 | if (mb->mins[j] < clipmins[j] || mb->maxs[j] > clipmaxs[j]) |
350 | break; |
351 | if (j != 3) |
352 | continue; |
353 | |
354 | mb->finished = true; |
355 | |
356 | /* make a copy of the brush */ |
357 | newbrush = AllocBrush(mb->numsides); |
358 | newbrush->original = mb; |
359 | newbrush->numsides = mb->numsides; |
360 | memcpy(newbrush->sides, mb->original_sides, numsides * sizeof(side_t)); |
361 | for (j = 0; j < numsides; j++) { |
362 | side_t *side = &newbrush->sides[j]; |
363 | if (side->winding) |
364 | side->winding = CopyWinding(side->winding); |
365 | if (side->surfaceFlags & SURF_HINT0x00000100) |
366 | side->visible = true; /* hints are always visible */ |
367 | } |
368 | VectorCopy(mb->mins, newbrush->mins)((newbrush->mins)[0]=(mb->mins)[0],(newbrush->mins)[ 1]=(mb->mins)[1],(newbrush->mins)[2]=(mb->mins)[2]); |
369 | VectorCopy(mb->maxs, newbrush->maxs)((newbrush->maxs)[0]=(mb->maxs)[0],(newbrush->maxs)[ 1]=(mb->maxs)[1],(newbrush->maxs)[2]=(mb->maxs)[2]); |
370 | |
371 | /* carve off anything outside the clip box */ |
372 | newbrush = ClipBrushToBox(newbrush, clipmins, clipmaxs); |
373 | if (!newbrush) { |
374 | Verb_Printf(VERB_DUMP, "Rejected brush %i: cannot clip to box.\n", i); |
375 | continue; |
376 | } |
377 | |
378 | newbrush->next = brushlist; |
379 | brushlist = newbrush; |
380 | Verb_Printf(VERB_DUMP, "Added brush %i.\n", i); |
381 | } |
382 | |
383 | return brushlist; |
384 | } |
385 | |
386 | /** |
387 | * @brief Carves any intersecting solid brushes into the minimum number of non-intersecting brushes. |
388 | */ |
389 | bspbrush_t *ChopBrushes (bspbrush_t *head) |
390 | { |
391 | bspbrush_t *b1, *b2, *next; |
392 | bspbrush_t *tail; |
393 | bspbrush_t *keep; |
394 | bspbrush_t *sub, *sub2; |
395 | int c1, c2; |
396 | const int originalBrushes = CountBrushList(head); |
397 | int keepBrushes; |
398 | |
399 | Verb_Printf(VERB_EXTRA, "---- ChopBrushes ----\n"); |
400 | |
401 | keep = NULL__null; |
402 | |
403 | newlist: |
404 | /* find tail */ |
405 | if (!head) |
406 | return NULL__null; |
407 | |
408 | for (tail = head; tail->next; tail = tail->next); |
409 | |
410 | for (b1 = head; b1; b1 = next) { |
411 | next = b1->next; |
412 | for (b2 = b1->next; b2; b2 = b2->next) { |
413 | if (BrushesDisjoint(b1, b2)) |
414 | continue; |
415 | |
416 | sub = sub2 = NULL__null; |
417 | c1 = c2 = 999999; |
418 | |
419 | if (BrushGE(b2, b1)) { |
420 | sub = SubtractBrush(b1, b2); |
421 | if (sub == b1) |
422 | continue; /* didn't really intersect */ |
423 | if (!sub) { /* b1 is swallowed by b2 */ |
424 | head = CullList(b1, b1); |
425 | goto newlist; |
426 | } |
427 | c1 = CountBrushList(sub); |
428 | } |
429 | |
430 | if (BrushGE(b1, b2)) { |
431 | sub2 = SubtractBrush(b2, b1); |
432 | if (sub2 == b2) |
433 | continue; /* didn't really intersect */ |
434 | if (!sub2) { /* b2 is swallowed by b1 */ |
435 | FreeBrushList(sub); |
436 | head = CullList(b1, b2); |
437 | goto newlist; |
438 | } |
439 | c2 = CountBrushList(sub2); |
440 | } |
441 | |
442 | if (!sub && !sub2) |
443 | continue; /* neither one can bite */ |
444 | |
445 | /* only accept if it didn't fragment */ |
446 | /* (commenting this out allows full fragmentation) */ |
447 | if (c1 > 1 && c2 > 1) { |
448 | if (sub2) |
449 | FreeBrushList(sub2); |
450 | if (sub) |
451 | FreeBrushList(sub); |
452 | continue; |
453 | } |
454 | |
455 | if (c1 < c2) { |
456 | if (sub2) |
457 | FreeBrushList(sub2); |
458 | tail = AddBrushListToTail(sub, tail); |
459 | head = CullList(b1, b1); |
460 | goto newlist; |
461 | } else { |
462 | if (sub) |
463 | FreeBrushList(sub); |
464 | tail = AddBrushListToTail(sub2, tail); |
Value stored to 'tail' is never read | |
465 | head = CullList(b1, b2); |
466 | goto newlist; |
467 | } |
468 | } |
469 | |
470 | /* b1 is no longer intersecting anything, so keep it */ |
471 | if (!b2) { |
472 | b1->next = keep; |
473 | keep = b1; |
474 | } |
475 | } |
476 | |
477 | keepBrushes = CountBrushList(keep); |
478 | if (keepBrushes != originalBrushes) { |
479 | Verb_Printf(VERB_EXTRA, "original brushes: %i\n", originalBrushes); |
480 | Verb_Printf(VERB_EXTRA, "output brushes: %i\n", keepBrushes); |
481 | } |
482 | return keep; |
483 | } |