File: | tools/ufo2map/faces.cpp |
Location: | line 163, column 3 |
Description: | Value stored to 'newf' is never read |
1 | /** |
2 | * @file |
3 | * @note some faces will be removed before saving, but still form nodes: |
4 | * meeting planes of different water current volumes |
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 | |
28 | #include "bsp.h" |
29 | |
30 | #define INTEGRAL_EPSILON0.01 0.01 |
31 | #define POINT_EPSILON0.5 0.5 |
32 | #define OFF_EPSILON0.5 0.5 |
33 | |
34 | static int c_merge, c_subdivide, c_totalverts, c_uniqueverts, c_degenerate, c_tjunctions, c_faceoverflows, c_facecollapse, c_badstartverts, c_faces; |
35 | |
36 | #define MAX_SUPERVERTS512 512 |
37 | static int superverts[MAX_SUPERVERTS512]; |
38 | static int numsuperverts; |
39 | |
40 | static const face_t *edgefaces[MAX_MAP_EDGES128000][2]; |
41 | int firstmodeledge = 1; |
42 | |
43 | static vec3_t edge_dir; |
44 | static vec3_t edge_start; |
45 | |
46 | static int num_edge_verts; |
47 | static int edge_verts[MAX_MAP_VERTS65536]; |
48 | |
49 | #define HASH_SIZE64 64 |
50 | |
51 | static int vertexchain[MAX_MAP_VERTS65536]; /* the next vertex in a hash chain */ |
52 | static int hashverts[HASH_SIZE64 * HASH_SIZE64]; /* a vertex number, or 0 for no verts */ |
53 | |
54 | /** |
55 | * @todo Fix this to support the full bsp level bounds |
56 | */ |
57 | static unsigned HashVec (const vec3_t vec) |
58 | { |
59 | const int x = (4096 + (int)(vec[0] + 0.5)) >> 7; |
60 | const int y = (4096 + (int)(vec[1] + 0.5)) >> 7; |
61 | |
62 | if (x < 0 || x >= HASH_SIZE64 || y < 0 || y >= HASH_SIZE64) |
63 | Sys_Error("HashVec: point outside valid range"); |
64 | |
65 | return y * HASH_SIZE64 + x; |
66 | } |
67 | |
68 | /** |
69 | * @brief Returns the number of an existing vertex or allocates a new one |
70 | * @note Uses hashing |
71 | */ |
72 | static int GetVertexnum (const vec3_t in) |
73 | { |
74 | int h, i, vnum; |
75 | vec3_t vert; |
76 | |
77 | c_totalverts++; |
78 | |
79 | for (i = 0; i < 3; i++) { |
80 | if (fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON0.01) |
81 | vert[i] = Q_rint(in[i]); |
82 | else |
83 | vert[i] = in[i]; |
84 | } |
85 | |
86 | h = HashVec(vert); |
87 | |
88 | for (vnum = hashverts[h]; vnum; vnum = vertexchain[vnum]) { |
89 | const float *p = curTile->vertexes[vnum].point; |
90 | if (fabs(p[0] - vert[0]) < POINT_EPSILON0.5 |
91 | && fabs(p[1] - vert[1]) < POINT_EPSILON0.5 |
92 | && fabs(p[2] - vert[2]) < POINT_EPSILON0.5) |
93 | return vnum; |
94 | } |
95 | |
96 | /* emit a vertex */ |
97 | if (curTile->numvertexes == MAX_MAP_VERTS65536) |
98 | Sys_Error("numvertexes == MAX_MAP_VERTS"); |
99 | |
100 | curTile->vertexes[curTile->numvertexes].point[0] = vert[0]; |
101 | curTile->vertexes[curTile->numvertexes].point[1] = vert[1]; |
102 | curTile->vertexes[curTile->numvertexes].point[2] = vert[2]; |
103 | |
104 | vertexchain[curTile->numvertexes] = hashverts[h]; |
105 | hashverts[h] = curTile->numvertexes; |
106 | |
107 | c_uniqueverts++; |
108 | |
109 | curTile->numvertexes++; |
110 | curTile->numnormals++; |
111 | |
112 | return curTile->numvertexes - 1; |
113 | } |
114 | |
115 | static face_t *AllocFace (void) |
116 | { |
117 | c_faces++; |
118 | |
119 | return Mem_AllocType(face_t)((face_t*)_Mem_Alloc(((sizeof(face_t))),true,(com_genericPool ),(0),"src/tools/ufo2map/faces.cpp",119)); |
120 | } |
121 | |
122 | static face_t *NewFaceFromFace (const face_t *f) |
123 | { |
124 | face_t *newf; |
125 | |
126 | newf = AllocFace(); |
127 | *newf = *f; |
128 | newf->merged = NULL__null; |
129 | newf->split[0] = newf->split[1] = NULL__null; |
130 | newf->w = NULL__null; |
131 | return newf; |
132 | } |
133 | |
134 | void FreeFace (face_t *f) |
135 | { |
136 | if (f->w) |
137 | FreeWinding(f->w); |
138 | Mem_Free(f)_Mem_Free((f),"src/tools/ufo2map/faces.cpp",138); |
139 | c_faces--; |
140 | } |
141 | |
142 | /** |
143 | * @brief The faces vertexes have been added to the superverts[] array, |
144 | * and there may be more there than can be held in a face (MAXEDGES). |
145 | * |
146 | * If less, the faces vertexnums[] will be filled in, otherwise |
147 | * face will reference a tree of split[] faces until all of the |
148 | * vertexnums can be added. |
149 | * |
150 | * @note superverts[base] will become face->vertexnums[0], and the others |
151 | * will be circularly filled in. |
152 | */ |
153 | static void FaceFromSuperverts (node_t *node, face_t *f, int base) |
154 | { |
155 | face_t *newf; |
156 | int i, remaining; |
157 | |
158 | remaining = numsuperverts; |
159 | /* must split into two faces, because of vertex overload */ |
160 | while (remaining > MAXEDGES20) { |
161 | c_faceoverflows++; |
162 | |
163 | newf = f->split[0] = NewFaceFromFace(f); |
Value stored to 'newf' is never read | |
164 | newf = f->split[0]; |
165 | newf->next = node->faces; |
166 | node->faces = newf; |
167 | |
168 | newf->numpoints = MAXEDGES20; |
169 | for (i = 0; i < MAXEDGES20; i++) |
170 | newf->vertexnums[i] = superverts[(i + base) % numsuperverts]; |
171 | |
172 | f->split[1] = NewFaceFromFace(f); |
173 | f = f->split[1]; |
174 | f->next = node->faces; |
175 | node->faces = f; |
176 | |
177 | remaining -= (MAXEDGES20 - 2); |
178 | base = (base + MAXEDGES20 - 1) % numsuperverts; |
179 | } |
180 | |
181 | /* copy the vertexes back to the face */ |
182 | f->numpoints = remaining; |
183 | for (i = 0; i < remaining; i++) |
184 | f->vertexnums[i] = superverts[(i + base) % numsuperverts]; |
185 | } |
186 | |
187 | static void EmitFaceVertexes (node_t *node, face_t *f) |
188 | { |
189 | winding_t *w; |
190 | int i; |
191 | |
192 | if (f->merged || f->split[0] || f->split[1]) |
193 | return; |
194 | |
195 | w = f->w; |
196 | for (i = 0; i < w->numpoints; i++) { |
197 | /* make every point unique */ |
198 | if (config.noweld) { |
199 | if (curTile->numvertexes == MAX_MAP_VERTS65536) |
200 | Sys_Error("MAX_MAP_VERTS (%i)", curTile->numvertexes); |
201 | superverts[i] = curTile->numvertexes; |
202 | VectorCopy(w->p[i], curTile->vertexes[curTile->numvertexes].point)((curTile->vertexes[curTile->numvertexes].point)[0]=(w-> p[i])[0],(curTile->vertexes[curTile->numvertexes].point )[1]=(w->p[i])[1],(curTile->vertexes[curTile->numvertexes ].point)[2]=(w->p[i])[2]); |
203 | curTile->numvertexes++; |
204 | curTile->numnormals++; |
205 | c_uniqueverts++; |
206 | c_totalverts++; |
207 | } else |
208 | superverts[i] = GetVertexnum(w->p[i]); |
209 | } |
210 | numsuperverts = w->numpoints; |
211 | |
212 | /* this may fragment the face if > MAXEDGES */ |
213 | FaceFromSuperverts(node, f, 0); |
214 | } |
215 | |
216 | static void EmitVertexes_r (node_t *node) |
217 | { |
218 | int i; |
219 | face_t *f; |
220 | |
221 | if (node->planenum == PLANENUM_LEAF-1) |
222 | return; |
223 | |
224 | for (f = node->faces; f; f = f->next) |
225 | EmitFaceVertexes(node, f); |
226 | |
227 | for (i = 0; i < 2; i++) |
228 | EmitVertexes_r(node->children[i]); |
229 | } |
230 | |
231 | |
232 | /** |
233 | * @brief Uses the hash tables to cut down to a small number |
234 | */ |
235 | static void FindEdgeVerts (const vec3_t v1, const vec3_t v2) |
236 | { |
237 | int x1, x2, y1, y2, t; |
238 | int x, y, vnum; |
239 | |
240 | x1 = (MAX_WORLD_WIDTH4096 + (int)(v1[0] + 0.5)) >> 7; |
241 | y1 = (MAX_WORLD_WIDTH4096 + (int)(v1[1] + 0.5)) >> 7; |
242 | x2 = (MAX_WORLD_WIDTH4096 + (int)(v2[0] + 0.5)) >> 7; |
243 | y2 = (MAX_WORLD_WIDTH4096 + (int)(v2[1] + 0.5)) >> 7; |
244 | |
245 | if (x1 > x2) { |
246 | t = x1; |
247 | x1 = x2; |
248 | x2 = t; |
249 | } |
250 | if (y1 > y2) { |
251 | t = y1; |
252 | y1 = y2; |
253 | y2 = t; |
254 | } |
255 | num_edge_verts = 0; |
256 | for (x = x1; x <= x2; x++) |
257 | for (y = y1; y <= y2; y++) |
258 | for (vnum = hashverts[y * HASH_SIZE64 + x]; vnum; vnum = vertexchain[vnum]) |
259 | edge_verts[num_edge_verts++] = vnum; |
260 | } |
261 | |
262 | /** |
263 | * @note Can be recursively reentered |
264 | */ |
265 | static void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert) |
266 | { |
267 | int k; |
268 | vec_t dist, error; |
269 | vec3_t delta, exact, off, p; |
270 | |
271 | if (p1 == p2) { |
272 | c_degenerate++; |
273 | return; /* degenerate edge */ |
274 | } |
275 | |
276 | for (k = startvert; k < num_edge_verts; k++) { |
277 | const int j = edge_verts[k]; |
278 | if (j == p1 || j == p2) |
279 | continue; |
280 | |
281 | VectorCopy(curTile->vertexes[j].point, p)((p)[0]=(curTile->vertexes[j].point)[0],(p)[1]=(curTile-> vertexes[j].point)[1],(p)[2]=(curTile->vertexes[j].point)[ 2]); |
282 | |
283 | VectorSubtract(p, edge_start, delta)((delta)[0]=(p)[0]-(edge_start)[0],(delta)[1]=(p)[1]-(edge_start )[1],(delta)[2]=(p)[2]-(edge_start)[2]); |
284 | dist = DotProduct(delta, edge_dir)((delta)[0]*(edge_dir)[0]+(delta)[1]*(edge_dir)[1]+(delta)[2] *(edge_dir)[2]); |
285 | if (dist <= start || dist >= end) |
286 | continue; /* off an end */ |
287 | VectorMA(edge_start, dist, edge_dir, exact); |
288 | VectorSubtract(p, exact, off)((off)[0]=(p)[0]-(exact)[0],(off)[1]=(p)[1]-(exact)[1],(off)[ 2]=(p)[2]-(exact)[2]); |
289 | error = VectorLength(off); |
290 | |
291 | if (fabs(error) > OFF_EPSILON0.5) |
292 | continue; /* not on the edge */ |
293 | |
294 | /* break the edge */ |
295 | c_tjunctions++; |
296 | TestEdge(start, dist, p1, j, k + 1); |
297 | TestEdge(dist, end, j, p2, k + 1); |
298 | return; |
299 | } |
300 | |
301 | /* the edge p1 to p2 is now free of tjunctions */ |
302 | if (numsuperverts >= MAX_SUPERVERTS512) |
303 | Sys_Error("MAX_SUPERVERTS (%i)", numsuperverts); |
304 | superverts[numsuperverts] = p1; |
305 | numsuperverts++; |
306 | } |
307 | |
308 | static void FixFaceEdges (node_t *node, face_t *f) |
309 | { |
310 | int i, base; |
311 | vec3_t e2; |
312 | vec_t len; |
313 | int count[MAX_SUPERVERTS512], start[MAX_SUPERVERTS512]; |
314 | |
315 | if (f->merged || f->split[0] || f->split[1]) |
316 | return; |
317 | |
318 | numsuperverts = 0; |
319 | |
320 | for (i = 0; i < f->numpoints; i++) { |
321 | const int p1 = f->vertexnums[i]; |
322 | const int p2 = f->vertexnums[(i + 1) % f->numpoints]; |
323 | |
324 | VectorCopy(curTile->vertexes[p1].point, edge_start)((edge_start)[0]=(curTile->vertexes[p1].point)[0],(edge_start )[1]=(curTile->vertexes[p1].point)[1],(edge_start)[2]=(curTile ->vertexes[p1].point)[2]); |
325 | VectorCopy(curTile->vertexes[p2].point, e2)((e2)[0]=(curTile->vertexes[p2].point)[0],(e2)[1]=(curTile ->vertexes[p2].point)[1],(e2)[2]=(curTile->vertexes[p2] .point)[2]); |
326 | |
327 | FindEdgeVerts(edge_start, e2); |
328 | |
329 | VectorSubtract(e2, edge_start, edge_dir)((edge_dir)[0]=(e2)[0]-(edge_start)[0],(edge_dir)[1]=(e2)[1]- (edge_start)[1],(edge_dir)[2]=(e2)[2]-(edge_start)[2]); |
330 | len = VectorNormalize(edge_dir); |
331 | |
332 | start[i] = numsuperverts; |
333 | TestEdge(0, len, p1, p2, 0); |
334 | |
335 | count[i] = numsuperverts - start[i]; |
336 | } |
337 | |
338 | /* entire face collapsed */ |
339 | if (numsuperverts < 3) { |
340 | f->numpoints = 0; |
341 | c_facecollapse++; |
342 | return; |
343 | } |
344 | |
345 | /* we want to pick a vertex that doesn't have tjunctions |
346 | * on either side, which can cause artifacts on trifans, |
347 | * especially underwater */ |
348 | for (i = 0; i < f->numpoints; i++) { |
349 | if (count[i] == 1 && count[(i + f->numpoints - 1) % f->numpoints] == 1) |
350 | break; |
351 | } |
352 | if (i == f->numpoints) { |
353 | c_badstartverts++; |
354 | base = 0; |
355 | } else { |
356 | /* rotate the vertex order */ |
357 | base = start[i]; |
358 | } |
359 | |
360 | /* this may fragment the face if > MAXEDGES */ |
361 | FaceFromSuperverts(node, f, base); |
362 | } |
363 | |
364 | static void FixEdges_r (node_t *node) |
365 | { |
366 | int i; |
367 | face_t *f; |
368 | |
369 | if (node->planenum == PLANENUM_LEAF-1) |
370 | return; |
371 | |
372 | for (f = node->faces; f; f = f->next) |
373 | FixFaceEdges(node, f); |
374 | |
375 | for (i = 0; i < 2; i++) |
376 | FixEdges_r(node->children[i]); |
377 | } |
378 | |
379 | /** |
380 | * @sa ProcessSubModel |
381 | * @sa ConstructLevelNodes_r |
382 | */ |
383 | void FixTjuncs (node_t *headnode) |
384 | { |
385 | /* snap and merge all vertexes */ |
386 | Verb_Printf(VERB_EXTRA, "---- snap verts ----\n"); |
387 | OBJZERO(hashverts)(memset(&((hashverts)), (0), sizeof((hashverts)))); |
388 | c_totalverts = 0; |
389 | c_uniqueverts = 0; |
390 | c_faceoverflows = 0; |
391 | EmitVertexes_r(headnode); |
392 | Verb_Printf(VERB_EXTRA, "%i unique from %i\n", c_uniqueverts, c_totalverts); |
393 | |
394 | /* break edges on tjunctions */ |
395 | Verb_Printf(VERB_EXTRA, "---- tjunc ----\n"); |
396 | c_degenerate = 0; |
397 | c_facecollapse = 0; |
398 | c_tjunctions = 0; |
399 | if (!config.notjunc) |
400 | FixEdges_r(headnode); |
401 | Verb_Printf(VERB_EXTRA, "%5i edges degenerated\n", c_degenerate); |
402 | Verb_Printf(VERB_EXTRA, "%5i faces degenerated\n", c_facecollapse); |
403 | Verb_Printf(VERB_EXTRA, "%5i edges added by tjunctions\n", c_tjunctions); |
404 | Verb_Printf(VERB_EXTRA, "%5i faces added by tjunctions\n", c_faceoverflows); |
405 | Verb_Printf(VERB_EXTRA, "%5i bad start verts\n", c_badstartverts); |
406 | } |
407 | |
408 | /** |
409 | * @sa EmitFace. |
410 | * @note Don't allow four way edges |
411 | */ |
412 | int GetEdge (int v1, int v2, const face_t *f) |
413 | { |
414 | dBspEdge_t *edge; |
415 | |
416 | if (!config.noshare) { |
417 | int i; |
418 | for (i = firstmodeledge; i < curTile->numedges; i++) { |
419 | edge = &curTile->edges[i]; |
420 | if (v1 == edge->v[1] && v2 == edge->v[0] |
421 | && edgefaces[i][0]->contentFlags == f->contentFlags) { |
422 | if (edgefaces[i][1]) |
423 | continue; |
424 | edgefaces[i][1] = f; |
425 | return -i; |
426 | } |
427 | } |
428 | } |
429 | |
430 | /* emit an edge */ |
431 | if (curTile->numedges >= MAX_MAP_EDGES128000) |
432 | Sys_Error("numedges >= MAX_MAP_EDGES (%i)", curTile->numedges); |
433 | edge = &curTile->edges[curTile->numedges]; |
434 | edge->v[0] = v1; |
435 | edge->v[1] = v2; |
436 | edgefaces[curTile->numedges][0] = f; |
437 | curTile->numedges++; |
438 | |
439 | return curTile->numedges - 1; |
440 | } |
441 | |
442 | /* |
443 | =========================================================================== |
444 | FACE MERGING |
445 | =========================================================================== |
446 | */ |
447 | |
448 | #define CONTINUOUS_EPSILON0.001 0.001 |
449 | |
450 | /** |
451 | * @brief If two polygons share a common edge and the edges that meet at the |
452 | * common points are both inside the other polygons, merge them |
453 | * @return NULL if the faces couldn't be merged, or the new winding. |
454 | * @note The originals will NOT be freed. |
455 | */ |
456 | static winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, const vec3_t planenormal) |
457 | { |
458 | vec_t *p1, *p2, *back; |
459 | winding_t *newf; |
460 | int i, j, k, l; |
461 | vec3_t normal, delta; |
462 | vec_t dot; |
463 | bool keep1, keep2; |
464 | |
465 | p1 = p2 = NULL__null; |
466 | j = 0; |
467 | |
468 | /* find a common edge */ |
469 | for (i = 0; i < f1->numpoints; i++) { |
470 | p1 = f1->p[i]; |
471 | p2 = f1->p[(i + 1) % f1->numpoints]; |
472 | for (j = 0; j < f2->numpoints; j++) { |
473 | const vec_t *p3 = f2->p[j]; |
474 | const vec_t *p4 = f2->p[(j + 1) % f2->numpoints]; |
475 | for (k = 0; k < 3; k++) { |
476 | if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON0.001) |
477 | break; |
478 | if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON0.001) |
479 | break; |
480 | } |
481 | if (k == 3) |
482 | break; |
483 | } |
484 | if (j < f2->numpoints) |
485 | break; |
486 | } |
487 | |
488 | /* no matching edges */ |
489 | if (i == f1->numpoints) |
490 | return NULL__null; |
491 | |
492 | /* check slope of connected lines */ |
493 | /* if the slopes are colinear, the point can be removed */ |
494 | back = f1->p[(i + f1->numpoints - 1) % f1->numpoints]; |
495 | VectorSubtract(p1, back, delta)((delta)[0]=(p1)[0]-(back)[0],(delta)[1]=(p1)[1]-(back)[1],(delta )[2]=(p1)[2]-(back)[2]); |
496 | CrossProduct(planenormal, delta, normal); |
497 | VectorNormalize(normal); |
498 | |
499 | back = f2->p[(j + 2) % f2->numpoints]; |
500 | VectorSubtract(back, p1, delta)((delta)[0]=(back)[0]-(p1)[0],(delta)[1]=(back)[1]-(p1)[1],(delta )[2]=(back)[2]-(p1)[2]); |
501 | dot = DotProduct(delta, normal)((delta)[0]*(normal)[0]+(delta)[1]*(normal)[1]+(delta)[2]*(normal )[2]); |
502 | /* not a convex polygon */ |
503 | if (dot > CONTINUOUS_EPSILON0.001) |
504 | return NULL__null; |
505 | keep1 = (bool)(dot < -CONTINUOUS_EPSILON0.001); |
506 | |
507 | back = f1->p[(i + 2) % f1->numpoints]; |
508 | VectorSubtract(back, p2, delta)((delta)[0]=(back)[0]-(p2)[0],(delta)[1]=(back)[1]-(p2)[1],(delta )[2]=(back)[2]-(p2)[2]); |
509 | CrossProduct(planenormal, delta, normal); |
510 | VectorNormalize(normal); |
511 | |
512 | back = f2->p[(j + f2->numpoints - 1) % f2->numpoints]; |
513 | VectorSubtract(back, p2, delta)((delta)[0]=(back)[0]-(p2)[0],(delta)[1]=(back)[1]-(p2)[1],(delta )[2]=(back)[2]-(p2)[2]); |
514 | dot = DotProduct(delta, normal)((delta)[0]*(normal)[0]+(delta)[1]*(normal)[1]+(delta)[2]*(normal )[2]); |
515 | /* not a convex polygon */ |
516 | if (dot > CONTINUOUS_EPSILON0.001) |
517 | return NULL__null; |
518 | keep2 = (bool)(dot < -CONTINUOUS_EPSILON0.001); |
519 | |
520 | /* build the new polygon */ |
521 | newf = AllocWinding(f1->numpoints + f2->numpoints); |
522 | |
523 | /* copy first polygon */ |
524 | for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints) { |
525 | if (k == (i + 1) % f1->numpoints && !keep2) |
526 | continue; |
527 | |
528 | VectorCopy(f1->p[k], newf->p[newf->numpoints])((newf->p[newf->numpoints])[0]=(f1->p[k])[0],(newf-> p[newf->numpoints])[1]=(f1->p[k])[1],(newf->p[newf-> numpoints])[2]=(f1->p[k])[2]); |
529 | newf->numpoints++; |
530 | } |
531 | |
532 | /* copy second polygon */ |
533 | for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints) { |
534 | if (l == (j + 1) % f2->numpoints && !keep1) |
535 | continue; |
536 | VectorCopy(f2->p[l], newf->p[newf->numpoints])((newf->p[newf->numpoints])[0]=(f2->p[l])[0],(newf-> p[newf->numpoints])[1]=(f2->p[l])[1],(newf->p[newf-> numpoints])[2]=(f2->p[l])[2]); |
537 | newf->numpoints++; |
538 | } |
539 | |
540 | return newf; |
541 | } |
542 | |
543 | /** |
544 | * @brief If two polygons share a common edge and the edges that meet at the |
545 | * common points are both inside the other polygons, merge them |
546 | * |
547 | * @return NULL if the faces couldn't be merged, or the new face. |
548 | * @note The originals will NOT be freed. |
549 | */ |
550 | static face_t *TryMerge (face_t *f1, face_t *f2, const vec3_t planenormal) |
551 | { |
552 | face_t *newf; |
553 | winding_t *nw; |
554 | |
555 | if (!f1->w || !f2->w) |
556 | return NULL__null; |
557 | if (f1->texinfo != f2->texinfo) |
558 | return NULL__null; |
559 | if (f1->planenum != f2->planenum) /* on front and back sides */ |
560 | return NULL__null; |
561 | if (f1->contentFlags != f2->contentFlags) |
562 | return NULL__null; |
563 | |
564 | nw = TryMergeWinding(f1->w, f2->w, planenormal); |
565 | if (!nw) |
566 | return NULL__null; |
567 | |
568 | c_merge++; |
569 | newf = NewFaceFromFace(f1); |
570 | newf->w = nw; |
571 | |
572 | f1->merged = newf; |
573 | f2->merged = newf; |
574 | |
575 | return newf; |
576 | } |
577 | |
578 | static void MergeNodeFaces (node_t *node) |
579 | { |
580 | face_t *f1; |
581 | |
582 | for (f1 = node->faces; f1; f1 = f1->next) { |
583 | face_t *f2; |
584 | if (f1->merged || f1->split[0] || f1->split[1]) |
585 | continue; |
586 | for (f2 = node->faces; f2 != f1; f2 = f2->next) { |
587 | const plane_t *plane = &mapplanes[node->planenum]; |
588 | face_t *merged; |
589 | face_t *end; |
590 | |
591 | if (f2->merged || f2->split[0] || f2->split[1]) |
592 | continue; |
593 | |
594 | merged = TryMerge(f1, f2, plane->normal); |
595 | if (!merged) |
596 | continue; |
597 | |
598 | /* add merged to the end of the node face list |
599 | * so it will be checked against all the faces again */ |
600 | for (end = node->faces; end->next; end = end->next); |
601 | |
602 | merged->next = NULL__null; |
603 | end->next = merged; |
604 | break; |
605 | } |
606 | } |
607 | } |
608 | |
609 | /*===================================================================== */ |
610 | |
611 | /** |
612 | * @brief Chop up faces that are larger than we want in the surface cache |
613 | */ |
614 | static void SubdivideFace (node_t *node, face_t *f) |
615 | { |
616 | int axis, i; |
617 | const dBspTexinfo_t *tex; |
618 | vec3_t temp; |
619 | vec_t dist; |
620 | |
621 | if (f->merged) |
622 | return; |
623 | |
624 | /* special (non-surface cached) faces don't need subdivision */ |
625 | tex = &curTile->texinfo[f->texinfo]; |
626 | if (tex->surfaceFlags & SURF_WARP0x00000008) |
627 | return; |
628 | |
629 | for (axis = 0; axis < 2; axis++) { |
630 | while (1) { |
631 | const winding_t *w = f->w; |
632 | winding_t *frontw, *backw; |
633 | float mins = 999999; |
634 | float maxs = -999999; |
635 | vec_t v; |
636 | |
637 | VectorCopy(tex->vecs[axis], temp)((temp)[0]=(tex->vecs[axis])[0],(temp)[1]=(tex->vecs[axis ])[1],(temp)[2]=(tex->vecs[axis])[2]); |
638 | for (i = 0; i < w->numpoints; i++) { |
639 | v = DotProduct(w->p[i], temp)((w->p[i])[0]*(temp)[0]+(w->p[i])[1]*(temp)[1]+(w->p [i])[2]*(temp)[2]); |
640 | if (v < mins) |
641 | mins = v; |
642 | if (v > maxs) |
643 | maxs = v; |
644 | } |
645 | |
646 | /* no bsp subdivide for this winding? */ |
647 | if (maxs - mins <= config.subdivideSize) |
648 | break; |
649 | |
650 | /* split it */ |
651 | c_subdivide++; |
652 | |
653 | v = VectorNormalize(temp); |
654 | |
655 | dist = (mins + config.subdivideSize - 16) / v; |
656 | |
657 | ClipWindingEpsilon(w, temp, dist, ON_EPSILON0.1, &frontw, &backw); |
658 | if (!frontw || !backw) |
659 | Sys_Error("SubdivideFace: didn't split the polygon (texture: '%s')", |
660 | tex->texture); |
661 | |
662 | f->split[0] = NewFaceFromFace(f); |
663 | f->split[0]->w = frontw; |
664 | f->split[0]->next = node->faces; |
665 | node->faces = f->split[0]; |
666 | |
667 | f->split[1] = NewFaceFromFace(f); |
668 | f->split[1]->w = backw; |
669 | f->split[1]->next = node->faces; |
670 | node->faces = f->split[1]; |
671 | |
672 | SubdivideFace(node, f->split[0]); |
673 | SubdivideFace(node, f->split[1]); |
674 | return; |
675 | } |
676 | } |
677 | } |
678 | |
679 | static void SubdivideNodeFaces (node_t *node) |
680 | { |
681 | face_t *f; |
682 | |
683 | for (f = node->faces; f; f = f->next) |
684 | SubdivideFace(node, f); |
685 | } |
686 | |
687 | static int c_nodefaces; |
688 | |
689 | static face_t *FaceFromPortal (portal_t *p, bool pside) |
690 | { |
691 | face_t *f; |
692 | side_t *side = p->side; |
693 | |
694 | /* portal does not bridge different visible contents */ |
695 | if (!side) |
696 | return NULL__null; |
697 | |
698 | /* nodraw/caulk faces */ |
699 | if (side->surfaceFlags & SURF_NODRAW0x00000080) |
700 | return NULL__null; |
701 | |
702 | f = AllocFace(); |
703 | |
704 | f->texinfo = side->texinfo; |
705 | f->planenum = (side->planenum & ~1) | pside; |
706 | f->portal = p; |
707 | |
708 | if ((p->nodes[pside]->contentFlags & CONTENTS_WINDOW0x0002) |
709 | && VisibleContents(p->nodes[!pside]->contentFlags ^ p->nodes[pside]->contentFlags) == CONTENTS_WINDOW0x0002) |
710 | return NULL__null; /* don't show insides of windows */ |
711 | |
712 | /* do back-clipping */ |
713 | if (!config.nobackclip && mapplanes[f->planenum].normal[2] < -0.9) { |
714 | /* this face is not visible from birds view - optimize away |
715 | * but only if it's not light emitting surface */ |
716 | const entity_t *e = &entities[side->brush->entitynum]; |
717 | if (!Q_streq(ValueForKey(e, "classname"), "func_rotating")(strcmp(ValueForKey(e, "classname"), "func_rotating") == 0)) { |
718 | if (!(curTile->texinfo[f->texinfo].surfaceFlags & SURF_LIGHT0x00000001)) { |
719 | /* e.g. water surfaces are removed if we set the surfaceFlags |
720 | * to SURF_NODRAW for this side */ |
721 | /*side->surfaceFlags |= SURF_NODRAW;*/ |
722 | return NULL__null; |
723 | } |
724 | } |
725 | } |
726 | |
727 | if (pside) { |
728 | f->w = ReverseWinding(p->winding); |
729 | f->contentFlags = p->nodes[1]->contentFlags; |
730 | } else { |
731 | f->w = CopyWinding(p->winding); |
732 | f->contentFlags = p->nodes[0]->contentFlags; |
733 | } |
734 | return f; |
735 | } |
736 | |
737 | |
738 | /** |
739 | * @brief If a portal will make a visible face, mark the side that originally created it |
740 | * - solid / empty : solid |
741 | * - solid / water : solid |
742 | * - water / empty : water |
743 | * - water / water : none |
744 | */ |
745 | static void MakeFaces_r (node_t *node) |
746 | { |
747 | portal_t *p; |
748 | |
749 | /* recurse down to leafs */ |
750 | if (node->planenum != PLANENUM_LEAF-1) { |
751 | MakeFaces_r(node->children[0]); |
752 | MakeFaces_r(node->children[1]); |
753 | |
754 | /* merge together all visible faces on the node */ |
755 | if (!config.nomerge) |
756 | MergeNodeFaces(node); |
757 | if (!config.nosubdiv) |
758 | SubdivideNodeFaces(node); |
759 | |
760 | return; |
761 | } |
762 | |
763 | /* solid leafs never have visible faces */ |
764 | if (node->contentFlags & CONTENTS_SOLID0x0001) |
765 | return; |
766 | |
767 | /* see which portals are valid */ |
768 | for (p = node->portals; p;) { |
769 | const int pside = (p->nodes[1] == node); |
770 | |
771 | p->face[pside] = FaceFromPortal(p, pside); |
772 | if (p->face[pside]) { |
773 | c_nodefaces++; |
774 | p->face[pside]->next = p->onnode->faces; |
775 | p->onnode->faces = p->face[pside]; |
776 | } |
777 | p = p->next[pside]; |
778 | } |
779 | } |
780 | |
781 | void MakeFaces (node_t *node) |
782 | { |
783 | Verb_Printf(VERB_EXTRA, "--- MakeFaces ---\n"); |
784 | c_merge = 0; |
785 | c_subdivide = 0; |
786 | c_nodefaces = 0; |
787 | |
788 | MakeFaces_r(node); |
789 | |
790 | Verb_Printf(VERB_EXTRA, "%5i makefaces\n", c_nodefaces); |
791 | Verb_Printf(VERB_EXTRA, "%5i merged\n", c_merge); |
792 | Verb_Printf(VERB_EXTRA, "%5i subdivided\n", c_subdivide); |
793 | } |