Bug Summary

File:tools/ufo2map/common/polylib.cpp
Location:line 342, column 2
Description:Assigned value is garbage or undefined

Annotated Source Code

1/**
2 * @file
3 * @brief
4 * @note Winding = Polyon representation of brushes
5 */
6
7/*
8Copyright (C) 1997-2001 Id Software, Inc.
9
10This program is free software; you can redistribute it and/or
11modify it under the terms of the GNU General Public License
12as published by the Free Software Foundation; either version 2
13of the License, or (at your option) any later version.
14
15This program is distributed in the hope that it will be useful,
16but WITHOUT ANY WARRANTY; without even the implied warranty of
17MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18
19See the GNU General Public License for more details.
20
21You should have received a copy of the GNU General Public License
22along with this program; if not, write to the Free Software
23Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24
25*/
26
27#include "polylib.h"
28#include "shared.h"
29
30
31#define BOGUS_RANGE8192 8192
32
33/**
34 * @brief Allocate a new winding (polygon)
35 * @param[in] points Amount of points for this winding
36 * @sa FreeWinding
37 */
38winding_t *AllocWinding (int points)
39{
40 return (winding_t *)Mem_Alloc(sizeof(vec3_t) * points + sizeof(int))_Mem_Alloc(((sizeof(vec3_t) * points + sizeof(int))),true,(com_genericPool
),(0),"src/tools/ufo2map/common/polylib.cpp",40)
;
41}
42
43/**
44 * @sa AllocWinding
45 */
46void FreeWinding (winding_t *w)
47{
48 if (*(unsigned *)w == 0xdeaddead)
49 Sys_Error("FreeWinding: freed a freed winding");
50 *(unsigned *)w = 0xdeaddead;
51
52 Mem_Free(w)_Mem_Free((w),"src/tools/ufo2map/common/polylib.cpp",52);
53}
54
55void RemoveColinearPoints (winding_t *w)
56{
57 int i, nump = 0;
58 vec3_t v1, v2;
59 vec3_t p[MAX_POINTS_ON_WINDING64];
60
61 for (i = 0; i < w->numpoints; i++) {
62 const int j = (i + 1) % w->numpoints;
63 const int k = (i + w->numpoints - 1) % w->numpoints;
64 VectorSubtract(w->p[j], w->p[i], v1)((v1)[0]=(w->p[j])[0]-(w->p[i])[0],(v1)[1]=(w->p[j])
[1]-(w->p[i])[1],(v1)[2]=(w->p[j])[2]-(w->p[i])[2])
;
65 VectorSubtract(w->p[i], w->p[k], v2)((v2)[0]=(w->p[i])[0]-(w->p[k])[0],(v2)[1]=(w->p[i])
[1]-(w->p[k])[1],(v2)[2]=(w->p[i])[2]-(w->p[k])[2])
;
66 VectorNormalize(v1);
67 VectorNormalize(v2);
68 if (DotProduct(v1, v2)((v1)[0]*(v2)[0]+(v1)[1]*(v2)[1]+(v1)[2]*(v2)[2]) < 0.999) {
69 VectorCopy(w->p[i], p[nump])((p[nump])[0]=(w->p[i])[0],(p[nump])[1]=(w->p[i])[1],(p
[nump])[2]=(w->p[i])[2])
;
70 nump++;
71 }
72 }
73
74 if (nump == w->numpoints)
75 return;
76
77 w->numpoints = nump;
78 memcpy(w->p, p, nump * sizeof(p[0]));
79}
80
81vec_t WindingArea (const winding_t *w)
82{
83 int i;
84 vec3_t d1, d2, cross;
85 vec_t total;
86
87 total = 0;
88 for (i = 2; i < w->numpoints; i++) {
89 VectorSubtract(w->p[i - 1], w->p[0], d1)((d1)[0]=(w->p[i - 1])[0]-(w->p[0])[0],(d1)[1]=(w->p
[i - 1])[1]-(w->p[0])[1],(d1)[2]=(w->p[i - 1])[2]-(w->
p[0])[2])
;
90 VectorSubtract(w->p[i], w->p[0], d2)((d2)[0]=(w->p[i])[0]-(w->p[0])[0],(d2)[1]=(w->p[i])
[1]-(w->p[0])[1],(d2)[2]=(w->p[i])[2]-(w->p[0])[2])
;
91 CrossProduct(d1, d2, cross);
92 total += VectorLength(cross);
93 }
94 return total * 0.5f;
95}
96
97void WindingBounds (const winding_t *w, vec3_t mins, vec3_t maxs)
98{
99 int i, j;
100
101 mins[0] = mins[1] = mins[2] = 99999;
102 maxs[0] = maxs[1] = maxs[2] = -99999;
103
104 for (i = 0; i < w->numpoints; i++) {
105 for (j = 0; j < 3; j++) {
106 const vec_t v = w->p[i][j];
107 if (v < mins[j])
108 mins[j] = v;
109 if (v > maxs[j])
110 maxs[j] = v;
111 }
112 }
113}
114
115void WindingCenter (const winding_t *w, vec3_t center)
116{
117 int i;
118 vec_t scale;
119
120 VectorCopy(vec3_origin, center)((center)[0]=(vec3_origin)[0],(center)[1]=(vec3_origin)[1],(center
)[2]=(vec3_origin)[2])
;
121 for (i = 0; i < w->numpoints; i++)
122 VectorAdd(w->p[i], center, center)((center)[0]=(w->p[i])[0]+(center)[0],(center)[1]=(w->p
[i])[1]+(center)[1],(center)[2]=(w->p[i])[2]+(center)[2])
;
123
124 scale = 1.0 / w->numpoints;
125 VectorScale(center, scale, center)((center)[0] = (center)[0] * (scale),(center)[1] = (center)[1
] * (scale),(center)[2] = (center)[2] * (scale))
;
126}
127
128winding_t *BaseWindingForPlane (const vec3_t normal, const vec_t dist)
129{
130 int i, x;
131 vec_t max, v;
132 vec3_t org, vright, vup;
133 winding_t *w;
134
135 /* find the major axis */
136 max = -BOGUS_RANGE8192;
137 x = -1;
138 for (i = 0; i < 3; i++) {
139 v = fabs(normal[i]);
140 if (v > max) {
141 x = i;
142 max = v;
143 }
144 }
145 if (x == -1)
146 Sys_Error("BaseWindingForPlane: no axis found");
147
148 VectorCopy(vec3_origin, vup)((vup)[0]=(vec3_origin)[0],(vup)[1]=(vec3_origin)[1],(vup)[2]
=(vec3_origin)[2])
;
149 /* axis */
150 switch (x) {
151 case 0:
152 case 1:
153 vup[2] = 1;
154 break;
155 case 2:
156 vup[0] = 1;
157 break;
158 }
159
160 v = DotProduct(vup, normal)((vup)[0]*(normal)[0]+(vup)[1]*(normal)[1]+(vup)[2]*(normal)[
2])
;
161 VectorMA(vup, -v, normal, vup);
162 VectorNormalize(vup);
163
164 VectorScale(normal, dist, org)((org)[0] = (normal)[0] * (dist),(org)[1] = (normal)[1] * (dist
),(org)[2] = (normal)[2] * (dist))
;
165
166 CrossProduct(vup, normal, vright);
167
168 VectorScale(vup, 8192, vup)((vup)[0] = (vup)[0] * (8192),(vup)[1] = (vup)[1] * (8192),(vup
)[2] = (vup)[2] * (8192))
;
169 VectorScale(vright, 8192, vright)((vright)[0] = (vright)[0] * (8192),(vright)[1] = (vright)[1]
* (8192),(vright)[2] = (vright)[2] * (8192))
;
170
171 /* project a really big axis aligned box onto the plane */
172 w = AllocWinding(4);
173 if (!w)
174 return NULL__null;
175
176 VectorSubtract(org, vright, w->p[0])((w->p[0])[0]=(org)[0]-(vright)[0],(w->p[0])[1]=(org)[1
]-(vright)[1],(w->p[0])[2]=(org)[2]-(vright)[2])
;
177 VectorAdd(w->p[0], vup, w->p[0])((w->p[0])[0]=(w->p[0])[0]+(vup)[0],(w->p[0])[1]=(w->
p[0])[1]+(vup)[1],(w->p[0])[2]=(w->p[0])[2]+(vup)[2])
;
178
179 VectorAdd(org, vright, w->p[1])((w->p[1])[0]=(org)[0]+(vright)[0],(w->p[1])[1]=(org)[1
]+(vright)[1],(w->p[1])[2]=(org)[2]+(vright)[2])
;
180 VectorAdd(w->p[1], vup, w->p[1])((w->p[1])[0]=(w->p[1])[0]+(vup)[0],(w->p[1])[1]=(w->
p[1])[1]+(vup)[1],(w->p[1])[2]=(w->p[1])[2]+(vup)[2])
;
181
182 VectorAdd(org, vright, w->p[2])((w->p[2])[0]=(org)[0]+(vright)[0],(w->p[2])[1]=(org)[1
]+(vright)[1],(w->p[2])[2]=(org)[2]+(vright)[2])
;
183 VectorSubtract(w->p[2], vup, w->p[2])((w->p[2])[0]=(w->p[2])[0]-(vup)[0],(w->p[2])[1]=(w->
p[2])[1]-(vup)[1],(w->p[2])[2]=(w->p[2])[2]-(vup)[2])
;
184
185 VectorSubtract(org, vright, w->p[3])((w->p[3])[0]=(org)[0]-(vright)[0],(w->p[3])[1]=(org)[1
]-(vright)[1],(w->p[3])[2]=(org)[2]-(vright)[2])
;
186 VectorSubtract(w->p[3], vup, w->p[3])((w->p[3])[0]=(w->p[3])[0]-(vup)[0],(w->p[3])[1]=(w->
p[3])[1]-(vup)[1],(w->p[3])[2]=(w->p[3])[2]-(vup)[2])
;
187
188 w->numpoints = 4;
189
190 return w;
191}
192
193/**
194 * @brief Copy a winding with all its points allocated
195 * @param[in] w The winding to copy
196 * @returns the new winding
197 */
198winding_t *CopyWinding (const winding_t *w)
199{
200 winding_t *c = AllocWinding(w->numpoints);
201 const ptrdiff_t size = (ptrdiff_t)((winding_t *)0)->p[w->numpoints];
202 memcpy(c, w, size);
203 return c;
204}
205
206winding_t *ReverseWinding (const winding_t *w)
207{
208 int i;
209 winding_t *c = AllocWinding(w->numpoints);
210
211 for (i = 0; i < w->numpoints; i++) {
212 VectorCopy(w->p[w->numpoints - 1 - i], c->p[i])((c->p[i])[0]=(w->p[w->numpoints - 1 - i])[0],(c->
p[i])[1]=(w->p[w->numpoints - 1 - i])[1],(c->p[i])[2
]=(w->p[w->numpoints - 1 - i])[2])
;
213 }
214 c->numpoints = w->numpoints;
215 return c;
216}
217
218void ClipWindingEpsilon (const winding_t *in, const vec3_t normal, const vec_t dist,
219 const vec_t epsilon, winding_t **front, winding_t **back)
220{
221 vec_t dists[MAX_POINTS_ON_WINDING64 + 4];
222 int sides[MAX_POINTS_ON_WINDING64 + 4];
223 int counts[3];
224 int i, j;
225 winding_t *f, *b;
226 int maxpts;
227
228 VectorClear(counts)((counts)[0]=(counts)[1]=(counts)[2]=0);
229
230 /* determine sides for each point */
231 for (i = 0; i < in->numpoints; i++) {
232 const vec_t dot = DotProduct(in->p[i], normal)((in->p[i])[0]*(normal)[0]+(in->p[i])[1]*(normal)[1]+(in
->p[i])[2]*(normal)[2])
- dist;
233 dists[i] = dot;
234 if (dot > epsilon)
235 sides[i] = SIDE_FRONT0;
236 else if (dot < -epsilon)
237 sides[i] = SIDE_BACK1;
238 else
239 sides[i] = SIDE_ON2;
240 counts[sides[i]]++;
241 }
242 sides[i] = sides[0];
243 dists[i] = dists[0];
244
245 if (!counts[0]) {
246 *back = CopyWinding(in);
247 *front = NULL__null;
248 return;
249 }
250 if (!counts[1]) {
251 *front = CopyWinding(in);
252 *back = NULL__null;
253 return;
254 }
255
256 /* can't use counts[0] + 2 because of floating point grouping errors */
257 maxpts = in->numpoints + 4;
258
259 *front = f = AllocWinding(maxpts);
260 *back = b = AllocWinding(maxpts);
261
262 for (i = 0; i < in->numpoints; i++) {
263 const vec_t *p1 = in->p[i];
264 const vec_t *p2;
265 vec_t dot;
266 vec3_t mid;
267
268 if (sides[i] == SIDE_ON2) {
269 VectorCopy(p1, f->p[f->numpoints])((f->p[f->numpoints])[0]=(p1)[0],(f->p[f->numpoints
])[1]=(p1)[1],(f->p[f->numpoints])[2]=(p1)[2])
;
270 f->numpoints++;
271 VectorCopy(p1, b->p[b->numpoints])((b->p[b->numpoints])[0]=(p1)[0],(b->p[b->numpoints
])[1]=(p1)[1],(b->p[b->numpoints])[2]=(p1)[2])
;
272 b->numpoints++;
273 continue;
274 }
275
276 if (sides[i] == SIDE_FRONT0) {
277 VectorCopy(p1, f->p[f->numpoints])((f->p[f->numpoints])[0]=(p1)[0],(f->p[f->numpoints
])[1]=(p1)[1],(f->p[f->numpoints])[2]=(p1)[2])
;
278 f->numpoints++;
279 }
280 if (sides[i] == SIDE_BACK1) {
281 VectorCopy(p1, b->p[b->numpoints])((b->p[b->numpoints])[0]=(p1)[0],(b->p[b->numpoints
])[1]=(p1)[1],(b->p[b->numpoints])[2]=(p1)[2])
;
282 b->numpoints++;
283 }
284
285 if (sides[i + 1] == SIDE_ON2 || sides[i + 1] == sides[i])
286 continue;
287
288 /* generate a split point */
289 p2 = in->p[(i + 1) % in->numpoints];
290
291 dot = dists[i] / (dists[i] - dists[i + 1]);
292 /* avoid round off error when possible */
293 for (j = 0; j < 3; j++) {
294 if (normal[j] == 1)
295 mid[j] = dist;
296 else if (normal[j] == -1)
297 mid[j] = -dist;
298 else
299 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
300 }
301
302 VectorCopy(mid, f->p[f->numpoints])((f->p[f->numpoints])[0]=(mid)[0],(f->p[f->numpoints
])[1]=(mid)[1],(f->p[f->numpoints])[2]=(mid)[2])
;
303 f->numpoints++;
304 VectorCopy(mid, b->p[b->numpoints])((b->p[b->numpoints])[0]=(mid)[0],(b->p[b->numpoints
])[1]=(mid)[1],(b->p[b->numpoints])[2]=(mid)[2])
;
305 b->numpoints++;
306 }
307
308 if (f->numpoints > maxpts || b->numpoints > maxpts)
309 Sys_Error("ClipWinding: points exceeded estimate");
310 if (f->numpoints > MAX_POINTS_ON_WINDING64 || b->numpoints > MAX_POINTS_ON_WINDING64)
311 Sys_Error("ClipWinding: MAX_POINTS_ON_WINDING");
312}
313
314void ChopWindingInPlace (winding_t **inout, const vec3_t normal, const vec_t dist, const vec_t epsilon)
315{
316 winding_t *in;
317 /** @todo Why + 4? */
318 vec_t dists[MAX_POINTS_ON_WINDING64 + 4];
319 int sides[MAX_POINTS_ON_WINDING64 + 4];
320 int counts[3];
321 int i, j;
322 vec3_t mid;
323 winding_t *f;
324 int maxpts;
325
326 in = *inout;
327 VectorClear(counts)((counts)[0]=(counts)[1]=(counts)[2]=0);
328
329 /* determine sides for each point */
330 for (i = 0; i < in->numpoints; i++) {
1
Loop condition is false. Execution continues on line 342
331 const vec_t dot = DotProduct(in->p[i], normal)((in->p[i])[0]*(normal)[0]+(in->p[i])[1]*(normal)[1]+(in
->p[i])[2]*(normal)[2])
- dist;
332 dists[i] = dot;
333 if (dot > epsilon)
334 sides[i] = SIDE_FRONT0;
335 else if (dot < -epsilon)
336 sides[i] = SIDE_BACK1;
337 else {
338 sides[i] = SIDE_ON2;
339 }
340 counts[sides[i]]++;
341 }
342 sides[i] = sides[0];
2
Assigned value is garbage or undefined
343 dists[i] = dists[0];
344
345 if (!counts[0]) {
346 FreeWinding(in);
347 *inout = NULL__null;
348 return;
349 }
350 if (!counts[1])
351 return; /* inout stays the same */
352
353 /* cant use counts[0] + 2 because of fp grouping errors */
354 maxpts = in->numpoints + 4;
355
356 f = AllocWinding(maxpts);
357
358 for (i = 0; i < in->numpoints; i++) {
359 const vec_t *p1 = in->p[i];
360 const vec_t *p2;
361 vec_t dot;
362
363 if (sides[i] == SIDE_ON2) {
364 VectorCopy(p1, f->p[f->numpoints])((f->p[f->numpoints])[0]=(p1)[0],(f->p[f->numpoints
])[1]=(p1)[1],(f->p[f->numpoints])[2]=(p1)[2])
;
365 f->numpoints++;
366 continue;
367 }
368
369 if (sides[i] == SIDE_FRONT0) {
370 VectorCopy(p1, f->p[f->numpoints])((f->p[f->numpoints])[0]=(p1)[0],(f->p[f->numpoints
])[1]=(p1)[1],(f->p[f->numpoints])[2]=(p1)[2])
;
371 f->numpoints++;
372 }
373
374 if (sides[i + 1] == SIDE_ON2 || sides[i + 1] == sides[i])
375 continue;
376
377 /* generate a split point */
378 p2 = in->p[(i + 1) % in->numpoints];
379
380 dot = dists[i] / (dists[i] - dists[i + 1]);
381 /* avoid round off error when possible */
382 for (j = 0; j < 3; j++) {
383 if (normal[j] == 1)
384 mid[j] = dist;
385 else if (normal[j] == -1)
386 mid[j] = -dist;
387 else
388 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
389 }
390
391 VectorCopy(mid, f->p[f->numpoints])((f->p[f->numpoints])[0]=(mid)[0],(f->p[f->numpoints
])[1]=(mid)[1],(f->p[f->numpoints])[2]=(mid)[2])
;
392 f->numpoints++;
393 }
394
395 if (f->numpoints > maxpts)
396 Sys_Error("ClipWinding: points exceeded estimate");
397 if (f->numpoints > MAX_POINTS_ON_WINDING64)
398 Sys_Error("ClipWinding: MAX_POINTS_ON_WINDING");
399
400 FreeWinding(in);
401 *inout = f;
402}
403
404
405/**
406 * @return the fragment of in that is on the front side of the cliping plane.
407 * @note The original is freed.
408 */
409winding_t *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
410{
411 winding_t *f, *b;
412
413 ClipWindingEpsilon(in, normal, dist, ON_EPSILON0.1, &f, &b);
414 FreeWinding(in);
415 if (b)
416 FreeWinding(b);
417 return f;
418}
419
420#define EDGE_LENGTH0.2 0.2
421/**
422 * @brief Returns true if the winding would be crunched out of existance by the
423 * vertex snapping.
424 */
425bool WindingIsTiny (winding_t *w)
426{
427 int i, edges;
428 vec_t len;
429 vec3_t delta;
430
431 edges = 0;
432 for (i = 0; i < w->numpoints; i++) {
433 const int j = ((i == w->numpoints - 1) ? 0 : i) + 1;
434 VectorSubtract(w->p[j], w->p[i], delta)((delta)[0]=(w->p[j])[0]-(w->p[i])[0],(delta)[1]=(w->
p[j])[1]-(w->p[i])[1],(delta)[2]=(w->p[j])[2]-(w->p[
i])[2])
;
435 len = VectorLength(delta);
436 if (len > EDGE_LENGTH0.2) {
437 if (++edges == 3)
438 return false;
439 }
440 }
441 return true;
442}
443
444/**
445 * @brief Returns true if the winding still has one of the points from
446 * basewinding for plane
447 */
448bool WindingIsHuge (const winding_t *w)
449{
450 int i, j;
451
452 for (i = 0; i < w->numpoints; i++) {
453 for (j = 0; j < 3; j++)
454 if (w->p[i][j] < -MAX_WORLD_WIDTH4096 || w->p[i][j] > MAX_WORLD_WIDTH4096)
455 return true;
456 }
457 return false;
458}
459
460#define SNAP_EPSILON0.01 0.01
461
462/**
463 * @brief welds two vec3_t's into a third, taking into account nearest-to-integer
464 * instead of averaging
465 */
466static void SnapWeldVector (const vec3_t a, const vec3_t b, vec3_t out)
467{
468 int i;
469 vec_t outi;
470
471 /* dummy check */
472 if (a == NULL__null || b == NULL__null || out == NULL__null)
473 return;
474
475 /* do each element */
476 for (i = 0; i < 3; i++) {
477 /* round to integer */
478 const double ai = rint(a[i]);
479 const double bi = rint(a[i]);
480
481 /* prefer exact integer */
482 if (ai == a[i])
483 out[i] = a[i];
484 else if (bi == b[i])
485 out[i] = b[i];
486
487 /* use nearest */
488 else if (fabs(ai - a[i]) < fabs(bi < b[i]))
489 out[i] = a[i];
490 else
491 out[i] = b[i];
492
493 /* snap */
494 outi = rint(out[i]);
495 if (fabs(outi - out[i]) <= SNAP_EPSILON0.01)
496 out[i] = outi;
497 }
498}
499
500/**
501 * @brief removes degenerate edges from a winding
502 * @returns true if the winding is valid
503 */
504bool FixWinding (winding_t *w)
505{
506 bool valid;
507 int i, k;
508
509 /* dummy check */
510 if (!w)
511 return false;
512
513 valid = true;
514
515 /* check all verts */
516 for (i = 0; i < w->numpoints; i++) {
517 /* get second point index */
518 const int j = (i + 1) % w->numpoints;
519 vec3_t vec;
520 float dist;
521
522 /* don't remove points if winding is a triangle */
523 if (w->numpoints == 3)
524 return valid;
525
526 /* degenerate edge? */
527 VectorSubtract(w->p[i], w->p[j], vec)((vec)[0]=(w->p[i])[0]-(w->p[j])[0],(vec)[1]=(w->p[i
])[1]-(w->p[j])[1],(vec)[2]=(w->p[i])[2]-(w->p[j])[2
])
;
528 dist = VectorLength(vec);
529 if (dist < ON_EPSILON0.1) {
530 valid = false;
531
532 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
533 SnapWeldVector(w->p[i], w->p[j], vec);
534 VectorCopy(vec, w->p[i])((w->p[i])[0]=(vec)[0],(w->p[i])[1]=(vec)[1],(w->p[i
])[2]=(vec)[2])
;
535
536 /* move the remaining verts */
537 for (k = i + 2; k < w->numpoints; k++)
538 VectorCopy(w->p[k], w->p[k - 1])((w->p[k - 1])[0]=(w->p[k])[0],(w->p[k - 1])[1]=(w->
p[k])[1],(w->p[k - 1])[2]=(w->p[k])[2])
;
539
540 w->numpoints--;
541 }
542 }
543
544 /* one last check and return */
545 if (w->numpoints < 3)
546 valid = false;
547 return valid;
548}