File: | tools/ufo2map/common/polylib.cpp |
Location: | line 242, column 2 |
Description: | Assigned value is garbage or undefined |
1 | /** | ||
2 | * @file | ||
3 | * @brief | ||
4 | * @note Winding = Polyon representation of brushes | ||
5 | */ | ||
6 | |||
7 | /* | ||
8 | Copyright (C) 1997-2001 Id Software, Inc. | ||
9 | |||
10 | This program is free software; you can redistribute it and/or | ||
11 | modify it under the terms of the GNU General Public License | ||
12 | as published by the Free Software Foundation; either version 2 | ||
13 | of the License, or (at your option) any later version. | ||
14 | |||
15 | This program is distributed in the hope that it will be useful, | ||
16 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
17 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | ||
18 | |||
19 | See the GNU General Public License for more details. | ||
20 | |||
21 | You should have received a copy of the GNU General Public License | ||
22 | along with this program; if not, write to the Free Software | ||
23 | Foundation, 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 | */ | ||
38 | winding_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 | */ | ||
46 | void 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 | |||
55 | void 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 | |||
81 | vec_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 | |||
97 | void 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 | |||
115 | void 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 | |||
128 | winding_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 | */ | ||
198 | winding_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 | |||
206 | winding_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 | |||
218 | void 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 | |||
314 | void 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++) { | ||
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]; | ||
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 | */ | ||
409 | winding_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 | */ | ||
425 | bool 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 | */ | ||
448 | bool 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 | */ | ||
466 | static 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 | */ | ||
504 | bool 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 | } |