Bug Summary

File:tools/ufo2map/faces.cpp
Location:line 163, column 3
Description:Value stored to 'newf' is never read

Annotated Source Code

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/*
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
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
34static 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
37static int superverts[MAX_SUPERVERTS512];
38static int numsuperverts;
39
40static const face_t *edgefaces[MAX_MAP_EDGES128000][2];
41int firstmodeledge = 1;
42
43static vec3_t edge_dir;
44static vec3_t edge_start;
45
46static int num_edge_verts;
47static int edge_verts[MAX_MAP_VERTS65536];
48
49#define HASH_SIZE64 64
50
51static int vertexchain[MAX_MAP_VERTS65536]; /* the next vertex in a hash chain */
52static 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 */
57static 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 */
72static 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
115static 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
122static 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
134void 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 */
153static 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
187static 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
216static 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 */
235static 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 */
265static 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
308static 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
364static 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 */
383void 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 */
412int 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===========================================================================
444FACE 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 */
456static 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 */
550static 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
578static 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 */
614static 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
679static 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
687static int c_nodefaces;
688
689static 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 */
745static 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
781void 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}