1 /*
2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21 // faces.c
22
23 #include "qbsp.h"
24
25 /*
26
27 some faces will be removed before saving, but still form nodes:
28
29 the insides of sky volumes
30 meeting planes of different water current volumes
31
32 */
33
34 // undefine for dumb linear searches
35 #define USE_HASHING
36
37 #define INTEGRAL_EPSILON 0.01
38 #define POINT_EPSILON 0.5
39 #define OFF_EPSILON 0.5
40
41 int c_merge;
42 int c_subdivide;
43
44 int c_totalverts;
45 int c_uniqueverts;
46 int c_degenerate;
47 int c_tjunctions;
48 int c_faceoverflows;
49 int c_facecollapse;
50 int c_badstartverts;
51
52 #define MAX_SUPERVERTS 512
53 int superverts[MAX_SUPERVERTS];
54 int numsuperverts;
55
56 face_t *edgefaces[MAX_MAP_EDGES][2];
57 int firstmodeledge = 1;
58 int firstmodelface;
59
60 int c_tryedges;
61
62 vec3_t edge_dir;
63 vec3_t edge_start;
64 vec_t edge_len;
65
66 int num_edge_verts;
67 int edge_verts[MAX_MAP_VERTS];
68
69
70 float subdivide_size = 240;
71
72
73 face_t *NewFaceFromFace (face_t *f);
74
75 //===========================================================================
76
77 typedef struct hashvert_s
78 {
79 struct hashvert_s *next;
80 int num;
81 } hashvert_t;
82
83
84 #define HASH_SIZE 64
85
86
87 int vertexchain[MAX_MAP_VERTS]; // the next vertex in a hash chain
88 int hashverts[HASH_SIZE*HASH_SIZE]; // a vertex number, or 0 for no verts
89
90 face_t *edgefaces[MAX_MAP_EDGES][2];
91
92 //============================================================================
93
94
HashVec(vec3_t vec)95 unsigned HashVec (vec3_t vec)
96 {
97 int x, y;
98
99 x = (4096 + (int)(vec[0]+0.5)) >> 7;
100 y = (4096 + (int)(vec[1]+0.5)) >> 7;
101
102 if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )
103 Error ("HashVec: point outside valid range");
104
105 return y*HASH_SIZE + x;
106 }
107
108 #ifdef USE_HASHING
109 /*
110 =============
111 GetVertex
112
113 Uses hashing
114 =============
115 */
GetVertexnum(vec3_t in)116 int GetVertexnum (vec3_t in)
117 {
118 int h;
119 int i;
120 float *p;
121 vec3_t vert;
122 int vnum;
123
124 c_totalverts++;
125
126 for (i=0 ; i<3 ; i++)
127 {
128 if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)
129 vert[i] = Q_rint(in[i]);
130 else
131 vert[i] = in[i];
132 }
133
134 h = HashVec (vert);
135
136 for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])
137 {
138 p = dvertexes[vnum].point;
139 if ( fabs(p[0]-vert[0])<POINT_EPSILON
140 && fabs(p[1]-vert[1])<POINT_EPSILON
141 && fabs(p[2]-vert[2])<POINT_EPSILON )
142 return vnum;
143 }
144
145 // emit a vertex
146 if (numvertexes == MAX_MAP_VERTS)
147 Error ("numvertexes == MAX_MAP_VERTS");
148
149 dvertexes[numvertexes].point[0] = vert[0];
150 dvertexes[numvertexes].point[1] = vert[1];
151 dvertexes[numvertexes].point[2] = vert[2];
152
153 vertexchain[numvertexes] = hashverts[h];
154 hashverts[h] = numvertexes;
155
156 c_uniqueverts++;
157
158 numvertexes++;
159
160 return numvertexes-1;
161 }
162 #else
163 /*
164 ==================
165 GetVertexnum
166
167 Dumb linear search
168 ==================
169 */
GetVertexnum(vec3_t v)170 int GetVertexnum (vec3_t v)
171 {
172 int i, j;
173 dvertex_t *dv;
174 vec_t d;
175
176 c_totalverts++;
177
178 // make really close values exactly integral
179 for (i=0 ; i<3 ; i++)
180 {
181 if ( fabs(v[i] - (int)(v[i]+0.5)) < INTEGRAL_EPSILON )
182 v[i] = (int)(v[i]+0.5);
183 if (v[i] < -4096 || v[i] > 4096)
184 Error ("GetVertexnum: outside +/- 4096");
185 }
186
187 // search for an existing vertex match
188 for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)
189 {
190 for (j=0 ; j<3 ; j++)
191 {
192 d = v[j] - dv->point[j];
193 if ( d > POINT_EPSILON || d < -POINT_EPSILON)
194 break;
195 }
196 if (j == 3)
197 return i; // a match
198 }
199
200 // new point
201 if (numvertexes == MAX_MAP_VERTS)
202 Error ("MAX_MAP_VERTS");
203 VectorCopy (v, dv->point);
204 numvertexes++;
205 c_uniqueverts++;
206
207 return numvertexes-1;
208 }
209 #endif
210
211
212 /*
213 ==================
214 FaceFromSuperverts
215
216 The faces vertexes have beeb added to the superverts[] array,
217 and there may be more there than can be held in a face (MAXEDGES).
218
219 If less, the faces vertexnums[] will be filled in, otherwise
220 face will reference a tree of split[] faces until all of the
221 vertexnums can be added.
222
223 superverts[base] will become face->vertexnums[0], and the others
224 will be circularly filled in.
225 ==================
226 */
FaceFromSuperverts(node_t * node,face_t * f,int base)227 void FaceFromSuperverts (node_t *node, face_t *f, int base)
228 {
229 face_t *newf;
230 int remaining;
231 int i;
232
233 remaining = numsuperverts;
234 while (remaining > MAXEDGES)
235 { // must split into two faces, because of vertex overload
236 c_faceoverflows++;
237
238 newf = f->split[0] = NewFaceFromFace (f);
239 newf = f->split[0];
240 newf->next = node->faces;
241 node->faces = newf;
242
243 newf->numpoints = MAXEDGES;
244 for (i=0 ; i<MAXEDGES ; i++)
245 newf->vertexnums[i] = superverts[(i+base)%numsuperverts];
246
247 f->split[1] = NewFaceFromFace (f);
248 f = f->split[1];
249 f->next = node->faces;
250 node->faces = f;
251
252 remaining -= (MAXEDGES-2);
253 base = (base+MAXEDGES-1)%numsuperverts;
254 }
255
256 // copy the vertexes back to the face
257 f->numpoints = remaining;
258 for (i=0 ; i<remaining ; i++)
259 f->vertexnums[i] = superverts[(i+base)%numsuperverts];
260 }
261
262
263 /*
264 ==================
265 EmitFaceVertexes
266 ==================
267 */
EmitFaceVertexes(node_t * node,face_t * f)268 void EmitFaceVertexes (node_t *node, face_t *f)
269 {
270 winding_t *w;
271 int i;
272
273 if (f->merged || f->split[0] || f->split[1])
274 return;
275
276 w = f->w;
277 for (i=0 ; i<w->numpoints ; i++)
278 {
279 if (noweld)
280 { // make every point unique
281 if (numvertexes == MAX_MAP_VERTS)
282 Error ("MAX_MAP_VERTS");
283 superverts[i] = numvertexes;
284 VectorCopy (w->p[i], dvertexes[numvertexes].point);
285 numvertexes++;
286 c_uniqueverts++;
287 c_totalverts++;
288 }
289 else
290 superverts[i] = GetVertexnum (w->p[i]);
291 }
292 numsuperverts = w->numpoints;
293
294 // this may fragment the face if > MAXEDGES
295 FaceFromSuperverts (node, f, 0);
296 }
297
298 /*
299 ==================
300 EmitVertexes_r
301 ==================
302 */
EmitVertexes_r(node_t * node)303 void EmitVertexes_r (node_t *node)
304 {
305 int i;
306 face_t *f;
307
308 if (node->planenum == PLANENUM_LEAF)
309 return;
310
311 for (f=node->faces ; f ; f=f->next)
312 {
313 EmitFaceVertexes (node, f);
314 }
315
316 for (i=0 ; i<2 ; i++)
317 EmitVertexes_r (node->children[i]);
318 }
319
320
321 #ifdef USE_HASHING
322 /*
323 ==========
324 FindEdgeVerts
325
326 Uses the hash tables to cut down to a small number
327 ==========
328 */
FindEdgeVerts(vec3_t v1,vec3_t v2)329 void FindEdgeVerts (vec3_t v1, vec3_t v2)
330 {
331 int x1, x2, y1, y2, t;
332 int x, y;
333 int vnum;
334
335 #if 0
336 {
337 int i;
338 num_edge_verts = numvertexes-1;
339 for (i=0 ; i<numvertexes-1 ; i++)
340 edge_verts[i] = i+1;
341 }
342 #endif
343
344 x1 = (4096 + (int)(v1[0]+0.5)) >> 7;
345 y1 = (4096 + (int)(v1[1]+0.5)) >> 7;
346 x2 = (4096 + (int)(v2[0]+0.5)) >> 7;
347 y2 = (4096 + (int)(v2[1]+0.5)) >> 7;
348
349 if (x1 > x2)
350 {
351 t = x1;
352 x1 = x2;
353 x2 = t;
354 }
355 if (y1 > y2)
356 {
357 t = y1;
358 y1 = y2;
359 y2 = t;
360 }
361 #if 0
362 x1--;
363 x2++;
364 y1--;
365 y2++;
366 if (x1 < 0)
367 x1 = 0;
368 if (x2 >= HASH_SIZE)
369 x2 = HASH_SIZE;
370 if (y1 < 0)
371 y1 = 0;
372 if (y2 >= HASH_SIZE)
373 y2 = HASH_SIZE;
374 #endif
375 num_edge_verts = 0;
376 for (x=x1 ; x <= x2 ; x++)
377 {
378 for (y=y1 ; y <= y2 ; y++)
379 {
380 for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])
381 {
382 edge_verts[num_edge_verts++] = vnum;
383 }
384 }
385 }
386 }
387
388 #else
389 /*
390 ==========
391 FindEdgeVerts
392
393 Forced a dumb check of everything
394 ==========
395 */
FindEdgeVerts(vec3_t v1,vec3_t v2)396 void FindEdgeVerts (vec3_t v1, vec3_t v2)
397 {
398 int i;
399
400 num_edge_verts = numvertexes-1;
401 for (i=0 ; i<num_edge_verts ; i++)
402 edge_verts[i] = i+1;
403 }
404 #endif
405
406 /*
407 ==========
408 TestEdge
409
410 Can be recursively reentered
411 ==========
412 */
TestEdge(vec_t start,vec_t end,int p1,int p2,int startvert)413 void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)
414 {
415 int j, k;
416 vec_t dist;
417 vec3_t delta;
418 vec3_t exact;
419 vec3_t off;
420 vec_t error;
421 vec3_t p;
422
423 if (p1 == p2)
424 {
425 c_degenerate++;
426 return; // degenerate edge
427 }
428
429 for (k=startvert ; k<num_edge_verts ; k++)
430 {
431 j = edge_verts[k];
432 if (j==p1 || j == p2)
433 continue;
434
435 VectorCopy (dvertexes[j].point, p);
436
437 VectorSubtract (p, edge_start, delta);
438 dist = DotProduct (delta, edge_dir);
439 if (dist <=start || dist >= end)
440 continue; // off an end
441 VectorMA (edge_start, dist, edge_dir, exact);
442 VectorSubtract (p, exact, off);
443 error = VectorLength (off);
444
445 if (fabs(error) > OFF_EPSILON)
446 continue; // not on the edge
447
448 // break the edge
449 c_tjunctions++;
450 TestEdge (start, dist, p1, j, k+1);
451 TestEdge (dist, end, j, p2, k+1);
452 return;
453 }
454
455 // the edge p1 to p2 is now free of tjunctions
456 if (numsuperverts >= MAX_SUPERVERTS)
457 Error ("MAX_SUPERVERTS");
458 superverts[numsuperverts] = p1;
459 numsuperverts++;
460 }
461
462 /*
463 ==================
464 FixFaceEdges
465
466 ==================
467 */
FixFaceEdges(node_t * node,face_t * f)468 void FixFaceEdges (node_t *node, face_t *f)
469 {
470 int p1, p2;
471 int i;
472 vec3_t e2;
473 vec_t len;
474 int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
475 int base;
476
477 if (f->merged || f->split[0] || f->split[1])
478 return;
479
480 numsuperverts = 0;
481
482 for (i=0 ; i<f->numpoints ; i++)
483 {
484 p1 = f->vertexnums[i];
485 p2 = f->vertexnums[(i+1)%f->numpoints];
486
487 VectorCopy (dvertexes[p1].point, edge_start);
488 VectorCopy (dvertexes[p2].point, e2);
489
490 FindEdgeVerts (edge_start, e2);
491
492 VectorSubtract (e2, edge_start, edge_dir);
493 len = VectorNormalize (edge_dir, edge_dir);
494
495 start[i] = numsuperverts;
496 TestEdge (0, len, p1, p2, 0);
497
498 count[i] = numsuperverts - start[i];
499 }
500
501 if (numsuperverts < 3)
502 { // entire face collapsed
503 f->numpoints = 0;
504 c_facecollapse++;
505 return;
506 }
507
508 // we want to pick a vertex that doesn't have tjunctions
509 // on either side, which can cause artifacts on trifans,
510 // especially underwater
511 for (i=0 ; i<f->numpoints ; i++)
512 {
513 if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)
514 break;
515 }
516 if (i == f->numpoints)
517 {
518 f->badstartvert = true;
519 c_badstartverts++;
520 base = 0;
521 }
522 else
523 { // rotate the vertex order
524 base = start[i];
525 }
526
527 // this may fragment the face if > MAXEDGES
528 FaceFromSuperverts (node, f, base);
529 }
530
531 /*
532 ==================
533 FixEdges_r
534 ==================
535 */
FixEdges_r(node_t * node)536 void FixEdges_r (node_t *node)
537 {
538 int i;
539 face_t *f;
540
541 if (node->planenum == PLANENUM_LEAF)
542 return;
543
544 for (f=node->faces ; f ; f=f->next)
545 FixFaceEdges (node, f);
546
547 for (i=0 ; i<2 ; i++)
548 FixEdges_r (node->children[i]);
549 }
550
551 /*
552 ===========
553 FixTjuncs
554
555 ===========
556 */
FixTjuncs(node_t * headnode)557 void FixTjuncs (node_t *headnode)
558 {
559 // snap and merge all vertexes
560 Sys_FPrintf( SYS_VRB, "---- snap verts ----\n");
561 memset (hashverts, 0, sizeof(hashverts));
562 c_totalverts = 0;
563 c_uniqueverts = 0;
564 c_faceoverflows = 0;
565 EmitVertexes_r (headnode);
566 Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts);
567
568 // break edges on tjunctions
569 Sys_FPrintf( SYS_VRB, "---- tjunc ----\n");
570 c_tryedges = 0;
571 c_degenerate = 0;
572 c_facecollapse = 0;
573 c_tjunctions = 0;
574 if (!notjunc)
575 FixEdges_r (headnode);
576 Sys_FPrintf( SYS_VRB, "%5i edges degenerated\n", c_degenerate);
577 Sys_FPrintf( SYS_VRB, "%5i faces degenerated\n", c_facecollapse);
578 Sys_FPrintf( SYS_VRB, "%5i edges added by tjunctions\n", c_tjunctions);
579 Sys_FPrintf( SYS_VRB, "%5i faces added by tjunctions\n", c_faceoverflows);
580 Sys_FPrintf( SYS_VRB, "%5i bad start verts\n", c_badstartverts);
581 }
582
583
584 //========================================================
585
586 int c_faces;
587
AllocFace(void)588 face_t *AllocFace (void)
589 {
590 face_t *f;
591
592 f = malloc(sizeof(*f));
593 memset (f, 0, sizeof(*f));
594 c_faces++;
595
596 return f;
597 }
598
NewFaceFromFace(face_t * f)599 face_t *NewFaceFromFace (face_t *f)
600 {
601 face_t *newf;
602
603 newf = AllocFace ();
604 *newf = *f;
605 newf->merged = NULL;
606 newf->split[0] = newf->split[1] = NULL;
607 newf->w = NULL;
608 return newf;
609 }
610
FreeFace(face_t * f)611 void FreeFace (face_t *f)
612 {
613 if (f->w)
614 FreeWinding (f->w);
615 free (f);
616 c_faces--;
617 }
618
619 //========================================================
620
621 /*
622 ==================
623 GetEdge
624
625 Called by writebsp.
626 Don't allow four way edges
627 ==================
628 */
GetEdge2(int v1,int v2,face_t * f)629 int GetEdge2 (int v1, int v2, face_t *f)
630 {
631 dedge_t *edge;
632 int i;
633
634 c_tryedges++;
635
636 if (!noshare)
637 {
638 for (i=firstmodeledge ; i < numedges ; i++)
639 {
640 edge = &dedges[i];
641 if (v1 == edge->v[1] && v2 == edge->v[0]
642 && edgefaces[i][0]->contents == f->contents)
643 {
644 if (edgefaces[i][1])
645 // Sys_Printf ("WARNING: multiple backward edge\n");
646 continue;
647 edgefaces[i][1] = f;
648 return -i;
649 }
650 #if 0
651 if (v1 == edge->v[0] && v2 == edge->v[1])
652 {
653 Sys_Printf ("WARNING: multiple forward edge\n");
654 return i;
655 }
656 #endif
657 }
658 }
659
660 // emit an edge
661 if (numedges >= MAX_MAP_EDGES)
662 Error ("numedges == MAX_MAP_EDGES");
663 edge = &dedges[numedges];
664 numedges++;
665 edge->v[0] = v1;
666 edge->v[1] = v2;
667 edgefaces[numedges-1][0] = f;
668
669 return numedges-1;
670 }
671
672 /*
673 ===========================================================================
674
675 FACE MERGING
676
677 ===========================================================================
678 */
679
680 #define CONTINUOUS_EPSILON 0.001
681
682 /*
683 =============
684 TryMergeWinding
685
686 If two polygons share a common edge and the edges that meet at the
687 common points are both inside the other polygons, merge them
688
689 Returns NULL if the faces couldn't be merged, or the new face.
690 The originals will NOT be freed.
691 =============
692 */
TryMergeWinding(winding_t * f1,winding_t * f2,vec3_t planenormal)693 winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal)
694 {
695 vec_t *p1, *p2, *p3, *p4, *back;
696 winding_t *newf;
697 int i, j, k, l;
698 vec3_t normal, delta;
699 vec_t dot;
700 qboolean keep1, keep2;
701
702
703 //
704 // find a common edge
705 //
706 p1 = p2 = NULL; // stop compiler warning
707 j = 0; //
708
709 for (i=0 ; i<f1->numpoints ; i++)
710 {
711 p1 = f1->p[i];
712 p2 = f1->p[(i+1)%f1->numpoints];
713 for (j=0 ; j<f2->numpoints ; j++)
714 {
715 p3 = f2->p[j];
716 p4 = f2->p[(j+1)%f2->numpoints];
717 for (k=0 ; k<3 ; k++)
718 {
719 if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
720 break;
721 if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
722 break;
723 }
724 if (k==3)
725 break;
726 }
727 if (j < f2->numpoints)
728 break;
729 }
730
731 if (i == f1->numpoints)
732 return NULL; // no matching edges
733
734 //
735 // check slope of connected lines
736 // if the slopes are colinear, the point can be removed
737 //
738 back = f1->p[(i+f1->numpoints-1)%f1->numpoints];
739 VectorSubtract (p1, back, delta);
740 CrossProduct (planenormal, delta, normal);
741 VectorNormalize (normal, normal);
742
743 back = f2->p[(j+2)%f2->numpoints];
744 VectorSubtract (back, p1, delta);
745 dot = DotProduct (delta, normal);
746 if (dot > CONTINUOUS_EPSILON)
747 return NULL; // not a convex polygon
748 keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
749
750 back = f1->p[(i+2)%f1->numpoints];
751 VectorSubtract (back, p2, delta);
752 CrossProduct (planenormal, delta, normal);
753 VectorNormalize (normal, normal);
754
755 back = f2->p[(j+f2->numpoints-1)%f2->numpoints];
756 VectorSubtract (back, p2, delta);
757 dot = DotProduct (delta, normal);
758 if (dot > CONTINUOUS_EPSILON)
759 return NULL; // not a convex polygon
760 keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
761
762 //
763 // build the new polygon
764 //
765 newf = AllocWinding (f1->numpoints + f2->numpoints);
766
767 // copy first polygon
768 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
769 {
770 if (k==(i+1)%f1->numpoints && !keep2)
771 continue;
772
773 VectorCopy (f1->p[k], newf->p[newf->numpoints]);
774 newf->numpoints++;
775 }
776
777 // copy second polygon
778 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
779 {
780 if (l==(j+1)%f2->numpoints && !keep1)
781 continue;
782 VectorCopy (f2->p[l], newf->p[newf->numpoints]);
783 newf->numpoints++;
784 }
785
786 return newf;
787 }
788
789 /*
790 =============
791 TryMerge
792
793 If two polygons share a common edge and the edges that meet at the
794 common points are both inside the other polygons, merge them
795
796 Returns NULL if the faces couldn't be merged, or the new face.
797 The originals will NOT be freed.
798 =============
799 */
TryMerge(face_t * f1,face_t * f2,vec3_t planenormal)800 face_t *TryMerge (face_t *f1, face_t *f2, vec3_t planenormal)
801 {
802 face_t *newf;
803 winding_t *nw;
804
805 if (!f1->w || !f2->w)
806 return NULL;
807 if (f1->texinfo != f2->texinfo)
808 return NULL;
809 if (f1->planenum != f2->planenum) // on front and back sides
810 return NULL;
811 if (f1->contents != f2->contents)
812 return NULL;
813
814
815 nw = TryMergeWinding (f1->w, f2->w, planenormal);
816 if (!nw)
817 return NULL;
818
819 c_merge++;
820 newf = NewFaceFromFace (f1);
821 newf->w = nw;
822
823 f1->merged = newf;
824 f2->merged = newf;
825
826 return newf;
827 }
828
829 /*
830 ===============
831 MergeNodeFaces
832 ===============
833 */
MergeNodeFaces(node_t * node)834 void MergeNodeFaces (node_t *node)
835 {
836 face_t *f1, *f2, *end;
837 face_t *merged;
838 plane_t *plane;
839
840 plane = &mapplanes[node->planenum];
841 merged = NULL;
842
843 for (f1 = node->faces ; f1 ; f1 = f1->next)
844 {
845 if (f1->merged || f1->split[0] || f1->split[1])
846 continue;
847 for (f2 = node->faces ; f2 != f1 ; f2=f2->next)
848 {
849 if (f2->merged || f2->split[0] || f2->split[1])
850 continue;
851 merged = TryMerge (f1, f2, plane->normal);
852 if (!merged)
853 continue;
854
855 // add merged to the end of the node face list
856 // so it will be checked against all the faces again
857 for (end = node->faces ; end->next ; end = end->next)
858 ;
859 merged->next = NULL;
860 end->next = merged;
861 break;
862 }
863 }
864 }
865
866 //=====================================================================
867
868 /*
869 ===============
870 SubdivideFace
871
872 Chop up faces that are larger than we want in the surface cache
873 ===============
874 */
SubdivideFace(node_t * node,face_t * f)875 void SubdivideFace (node_t *node, face_t *f)
876 {
877 float mins, maxs;
878 vec_t v;
879 int axis, i;
880 texinfo_t *tex;
881 vec3_t temp;
882 vec_t dist;
883 winding_t *w, *frontw, *backw;
884
885 if (f->merged)
886 return;
887
888 // special (non-surface cached) faces don't need subdivision
889 tex = &texinfo[f->texinfo];
890
891 if ( tex->flags & (SURF_WARP|SURF_SKY) )
892 {
893 return;
894 }
895
896 for (axis = 0 ; axis < 2 ; axis++)
897 {
898 while (1)
899 {
900 mins = 999999;
901 maxs = -999999;
902
903 VectorCopy (tex->vecs[axis], temp);
904 w = f->w;
905 for (i=0 ; i<w->numpoints ; i++)
906 {
907 v = DotProduct (w->p[i], temp);
908 if (v < mins)
909 mins = v;
910 if (v > maxs)
911 maxs = v;
912 }
913 #if 0
914 if (maxs - mins <= 0)
915 Error ("zero extents");
916 #endif
917 if (axis == 2)
918 { // allow double high walls
919 if (maxs - mins <= subdivide_size/* *2 */)
920 break;
921 }
922 else if (maxs - mins <= subdivide_size)
923 break;
924
925 // split it
926 c_subdivide++;
927
928 v = VectorNormalize (temp, temp);
929
930 dist = (mins + subdivide_size - 16)/v;
931
932 ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
933 if (!frontw || !backw)
934 Error ("SubdivideFace: didn't split the polygon");
935
936 f->split[0] = NewFaceFromFace (f);
937 f->split[0]->w = frontw;
938 f->split[0]->next = node->faces;
939 node->faces = f->split[0];
940
941 f->split[1] = NewFaceFromFace (f);
942 f->split[1]->w = backw;
943 f->split[1]->next = node->faces;
944 node->faces = f->split[1];
945
946 SubdivideFace (node, f->split[0]);
947 SubdivideFace (node, f->split[1]);
948 return;
949 }
950 }
951 }
952
SubdivideNodeFaces(node_t * node)953 void SubdivideNodeFaces (node_t *node)
954 {
955 face_t *f;
956
957 for (f = node->faces ; f ; f=f->next)
958 {
959 SubdivideFace (node, f);
960 }
961 }
962
963 //===========================================================================
964
965 int c_nodefaces;
966
967
968 /*
969 ============
970 FaceFromPortal
971
972 ============
973 */
FaceFromPortal(portal_t * p,int pside)974 face_t *FaceFromPortal (portal_t *p, int pside)
975 {
976 face_t *f;
977 side_t *side;
978
979 side = p->side;
980 if (!side)
981 return NULL; // portal does not bridge different visible contents
982
983 f = AllocFace ();
984
985 f->texinfo = side->texinfo;
986 f->planenum = (side->planenum & ~1) | pside;
987 f->portal = p;
988
989 if ( (p->nodes[pside]->contents & CONTENTS_WINDOW)
990 && VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents) == CONTENTS_WINDOW )
991 return NULL; // don't show insides of windows
992
993 if (pside)
994 {
995 f->w = ReverseWinding(p->winding);
996 f->contents = p->nodes[1]->contents;
997 }
998 else
999 {
1000 f->w = CopyWinding(p->winding);
1001 f->contents = p->nodes[0]->contents;
1002 }
1003 return f;
1004 }
1005
1006
1007 /*
1008 ===============
1009 MakeFaces_r
1010
1011 If a portal will make a visible face,
1012 mark the side that originally created it
1013
1014 solid / empty : solid
1015 solid / water : solid
1016 water / empty : water
1017 water / water : none
1018 ===============
1019 */
MakeFaces_r(node_t * node)1020 void MakeFaces_r (node_t *node)
1021 {
1022 portal_t *p;
1023 int s;
1024
1025 // recurse down to leafs
1026 if (node->planenum != PLANENUM_LEAF)
1027 {
1028 MakeFaces_r (node->children[0]);
1029 MakeFaces_r (node->children[1]);
1030
1031 // merge together all visible faces on the node
1032 if (!nomerge)
1033 MergeNodeFaces (node);
1034 if (!nosubdiv)
1035 SubdivideNodeFaces (node);
1036
1037 return;
1038 }
1039
1040 // solid leafs never have visible faces
1041 if (node->contents & CONTENTS_SOLID)
1042 return;
1043
1044 // see which portals are valid
1045 for (p=node->portals ; p ; p = p->next[s])
1046 {
1047 s = (p->nodes[1] == node);
1048
1049 p->face[s] = FaceFromPortal (p, s);
1050 if (p->face[s])
1051 {
1052 c_nodefaces++;
1053 p->face[s]->next = p->onnode->faces;
1054 p->onnode->faces = p->face[s];
1055 }
1056 }
1057 }
1058
1059 /*
1060 ============
1061 MakeFaces
1062 ============
1063 */
MakeFaces(node_t * node)1064 void MakeFaces (node_t *node)
1065 {
1066 Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n");
1067 c_merge = 0;
1068 c_subdivide = 0;
1069 c_nodefaces = 0;
1070
1071 MakeFaces_r (node);
1072
1073 Sys_FPrintf( SYS_VRB, "%5i makefaces\n", c_nodefaces);
1074 Sys_FPrintf( SYS_VRB, "%5i merged\n", c_merge);
1075 Sys_FPrintf( SYS_VRB, "%5i subdivided\n", c_subdivide);
1076 }
1077