Bug Summary

File:tools/ufo2map/csg.cpp
Location:line 458, column 5
Description:Value stored to 'tail' is never read

Annotated Source Code

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/*
29Copyright (C) 1997-2001 Id Software, Inc.
30
31This program is free software; you can redistribute it and/or
32modify it under the terms of the GNU General Public License
33as published by the Free Software Foundation; either version 2
34of the License, or (at your option) any later version.
35
36This program is distributed in the hope that it will be useful,
37but WITHOUT ANY WARRANTY; without even the implied warranty of
38MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
39
40See the GNU General Public License for more details.
41
42You should have received a copy of the GNU General Public License
43along with this program; if not, write to the Free Software
44Foundation, 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 */
55static 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 */
87static 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
107static uint16_t minplanenums[2];
108static 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 */
114static 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 */
160static 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
201static 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 */
222static 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 */
244static 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 */
268int 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
301bspbrush_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 */
389bspbrush_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
403newlist:
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);
Value stored to 'tail' is never read
459 head = CullList(b1, b1);
460 goto newlist;
461 } else {
462 if (sub)
463 FreeBrushList(sub);
464 tail = AddBrushListToTail(sub2, tail);
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}