2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
27 some faces will be removed before saving, but still form nodes:
29 the insides of sky volumes
30 meeting planes of different water current volumes
34 // undefine for dumb linear searches
37 #define INTEGRAL_EPSILON 0.01
38 #define POINT_EPSILON 0.5
39 #define OFF_EPSILON 0.5
52 #define MAX_SUPERVERTS 512
53 int superverts[MAX_SUPERVERTS];
56 face_t *edgefaces[MAX_MAP_EDGES][2];
57 int firstmodeledge = 1;
67 int edge_verts[MAX_MAP_VERTS];
70 float subdivide_size = 240;
73 face_t *NewFaceFromFace (face_t *f);
75 //===========================================================================
77 typedef struct hashvert_s
79 struct hashvert_s *next;
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
90 face_t *edgefaces[MAX_MAP_EDGES][2];
92 //============================================================================
95 unsigned HashVec (vec3_t vec)
99 x = (4096 + (int)(vec[0]+0.5)) >> 7;
100 y = (4096 + (int)(vec[1]+0.5)) >> 7;
102 if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )
103 Error ("HashVec: point outside valid range");
105 return y*HASH_SIZE + x;
116 int GetVertexnum (vec3_t in)
126 for (i=0 ; i<3 ; i++)
128 if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)
129 vert[i] = Q_rint(in[i]);
136 for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])
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 )
146 if (numvertexes == MAX_MAP_VERTS)
147 Error ("numvertexes == MAX_MAP_VERTS");
149 dvertexes[numvertexes].point[0] = vert[0];
150 dvertexes[numvertexes].point[1] = vert[1];
151 dvertexes[numvertexes].point[2] = vert[2];
153 vertexchain[numvertexes] = hashverts[h];
154 hashverts[h] = numvertexes;
160 return numvertexes-1;
170 int GetVertexnum (vec3_t v)
178 // make really close values exactly integral
179 for (i=0 ; i<3 ; i++)
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");
187 // search for an existing vertex match
188 for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)
190 for (j=0 ; j<3 ; j++)
192 d = v[j] - dv->point[j];
193 if ( d > POINT_EPSILON || d < -POINT_EPSILON)
201 if (numvertexes == MAX_MAP_VERTS)
202 Error ("MAX_MAP_VERTS");
203 VectorCopy (v, dv->point);
207 return numvertexes-1;
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).
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.
223 superverts[base] will become face->vertexnums[0], and the others
224 will be circularly filled in.
227 void FaceFromSuperverts (node_t *node, face_t *f, int base)
233 remaining = numsuperverts;
234 while (remaining > MAXEDGES)
235 { // must split into two faces, because of vertex overload
238 newf = f->split[0] = NewFaceFromFace (f);
240 newf->next = node->faces;
243 newf->numpoints = MAXEDGES;
244 for (i=0 ; i<MAXEDGES ; i++)
245 newf->vertexnums[i] = superverts[(i+base)%numsuperverts];
247 f->split[1] = NewFaceFromFace (f);
249 f->next = node->faces;
252 remaining -= (MAXEDGES-2);
253 base = (base+MAXEDGES-1)%numsuperverts;
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];
268 void EmitFaceVertexes (node_t *node, face_t *f)
273 if (f->merged || f->split[0] || f->split[1])
277 for (i=0 ; i<w->numpoints ; i++)
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);
290 superverts[i] = GetVertexnum (w->p[i]);
292 numsuperverts = w->numpoints;
294 // this may fragment the face if > MAXEDGES
295 FaceFromSuperverts (node, f, 0);
303 void EmitVertexes_r (node_t *node)
308 if (node->planenum == PLANENUM_LEAF)
311 for (f=node->faces ; f ; f=f->next)
313 EmitFaceVertexes (node, f);
316 for (i=0 ; i<2 ; i++)
317 EmitVertexes_r (node->children[i]);
326 Uses the hash tables to cut down to a small number
329 void FindEdgeVerts (vec3_t v1, vec3_t v2)
331 int x1, x2, y1, y2, t;
338 num_edge_verts = numvertexes-1;
339 for (i=0 ; i<numvertexes-1 ; i++)
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;
376 for (x=x1 ; x <= x2 ; x++)
378 for (y=y1 ; y <= y2 ; y++)
380 for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])
382 edge_verts[num_edge_verts++] = vnum;
393 Forced a dumb check of everything
396 void FindEdgeVerts (vec3_t v1, vec3_t v2)
400 num_edge_verts = numvertexes-1;
401 for (i=0 ; i<num_edge_verts ; i++)
410 Can be recursively reentered
413 void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)
426 return; // degenerate edge
429 for (k=startvert ; k<num_edge_verts ; k++)
432 if (j==p1 || j == p2)
435 VectorCopy (dvertexes[j].point, p);
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);
445 if (fabs(error) > OFF_EPSILON)
446 continue; // not on the edge
450 TestEdge (start, dist, p1, j, k+1);
451 TestEdge (dist, end, j, p2, k+1);
455 // the edge p1 to p2 is now free of tjunctions
456 if (numsuperverts >= MAX_SUPERVERTS)
457 Error ("MAX_SUPERVERTS");
458 superverts[numsuperverts] = p1;
468 void FixFaceEdges (node_t *node, face_t *f)
474 int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
477 if (f->merged || f->split[0] || f->split[1])
482 for (i=0 ; i<f->numpoints ; i++)
484 p1 = f->vertexnums[i];
485 p2 = f->vertexnums[(i+1)%f->numpoints];
487 VectorCopy (dvertexes[p1].point, edge_start);
488 VectorCopy (dvertexes[p2].point, e2);
490 FindEdgeVerts (edge_start, e2);
492 VectorSubtract (e2, edge_start, edge_dir);
493 len = VectorNormalize (edge_dir, edge_dir);
495 start[i] = numsuperverts;
496 TestEdge (0, len, p1, p2, 0);
498 count[i] = numsuperverts - start[i];
501 if (numsuperverts < 3)
502 { // entire face collapsed
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++)
513 if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)
516 if (i == f->numpoints)
518 f->badstartvert = true;
523 { // rotate the vertex order
527 // this may fragment the face if > MAXEDGES
528 FaceFromSuperverts (node, f, base);
536 void FixEdges_r (node_t *node)
541 if (node->planenum == PLANENUM_LEAF)
544 for (f=node->faces ; f ; f=f->next)
545 FixFaceEdges (node, f);
547 for (i=0 ; i<2 ; i++)
548 FixEdges_r (node->children[i]);
557 void FixTjuncs (node_t *headnode)
559 // snap and merge all vertexes
560 Sys_FPrintf( SYS_VRB, "---- snap verts ----\n");
561 memset (hashverts, 0, sizeof(hashverts));
565 EmitVertexes_r (headnode);
566 Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts);
568 // break edges on tjunctions
569 Sys_FPrintf( SYS_VRB, "---- tjunc ----\n");
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);
584 //========================================================
588 face_t *AllocFace (void)
592 f = malloc(sizeof(*f));
593 memset (f, 0, sizeof(*f));
599 face_t *NewFaceFromFace (face_t *f)
606 newf->split[0] = newf->split[1] = NULL;
611 void FreeFace (face_t *f)
619 //========================================================
626 Don't allow four way edges
629 int GetEdge2 (int v1, int v2, face_t *f)
638 for (i=firstmodeledge ; i < numedges ; i++)
641 if (v1 == edge->v[1] && v2 == edge->v[0]
642 && edgefaces[i][0]->contents == f->contents)
645 // Sys_Printf ("WARNING: multiple backward edge\n");
651 if (v1 == edge->v[0] && v2 == edge->v[1])
653 Sys_Printf ("WARNING: multiple forward edge\n");
661 if (numedges >= MAX_MAP_EDGES)
662 Error ("numedges == MAX_MAP_EDGES");
663 edge = &dedges[numedges];
667 edgefaces[numedges-1][0] = f;
673 ===========================================================================
677 ===========================================================================
680 #define CONTINUOUS_EPSILON 0.001
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
689 Returns NULL if the faces couldn't be merged, or the new face.
690 The originals will NOT be freed.
693 winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal)
695 vec_t *p1, *p2, *p3, *p4, *back;
698 vec3_t normal, delta;
700 qboolean keep1, keep2;
704 // find a common edge
706 p1 = p2 = NULL; // stop compiler warning
709 for (i=0 ; i<f1->numpoints ; i++)
712 p2 = f1->p[(i+1)%f1->numpoints];
713 for (j=0 ; j<f2->numpoints ; j++)
716 p4 = f2->p[(j+1)%f2->numpoints];
717 for (k=0 ; k<3 ; k++)
719 if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
721 if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
727 if (j < f2->numpoints)
731 if (i == f1->numpoints)
732 return NULL; // no matching edges
735 // check slope of connected lines
736 // if the slopes are colinear, the point can be removed
738 back = f1->p[(i+f1->numpoints-1)%f1->numpoints];
739 VectorSubtract (p1, back, delta);
740 CrossProduct (planenormal, delta, normal);
741 VectorNormalize (normal, normal);
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);
750 back = f1->p[(i+2)%f1->numpoints];
751 VectorSubtract (back, p2, delta);
752 CrossProduct (planenormal, delta, normal);
753 VectorNormalize (normal, normal);
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);
763 // build the new polygon
765 newf = AllocWinding (f1->numpoints + f2->numpoints);
767 // copy first polygon
768 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
770 if (k==(i+1)%f1->numpoints && !keep2)
773 VectorCopy (f1->p[k], newf->p[newf->numpoints]);
777 // copy second polygon
778 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
780 if (l==(j+1)%f2->numpoints && !keep1)
782 VectorCopy (f2->p[l], newf->p[newf->numpoints]);
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
796 Returns NULL if the faces couldn't be merged, or the new face.
797 The originals will NOT be freed.
800 face_t *TryMerge (face_t *f1, face_t *f2, vec3_t planenormal)
805 if (!f1->w || !f2->w)
807 if (f1->texinfo != f2->texinfo)
809 if (f1->planenum != f2->planenum) // on front and back sides
811 if (f1->contents != f2->contents)
815 nw = TryMergeWinding (f1->w, f2->w, planenormal);
820 newf = NewFaceFromFace (f1);
834 void MergeNodeFaces (node_t *node)
836 face_t *f1, *f2, *end;
840 plane = &mapplanes[node->planenum];
843 for (f1 = node->faces ; f1 ; f1 = f1->next)
845 if (f1->merged || f1->split[0] || f1->split[1])
847 for (f2 = node->faces ; f2 != f1 ; f2=f2->next)
849 if (f2->merged || f2->split[0] || f2->split[1])
851 merged = TryMerge (f1, f2, plane->normal);
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)
866 //=====================================================================
872 Chop up faces that are larger than we want in the surface cache
875 void SubdivideFace (node_t *node, face_t *f)
883 winding_t *w, *frontw, *backw;
888 // special (non-surface cached) faces don't need subdivision
889 tex = &texinfo[f->texinfo];
891 if ( tex->flags & (SURF_WARP|SURF_SKY) )
896 for (axis = 0 ; axis < 2 ; axis++)
903 VectorCopy (tex->vecs[axis], temp);
905 for (i=0 ; i<w->numpoints ; i++)
907 v = DotProduct (w->p[i], temp);
914 if (maxs - mins <= 0)
915 Error ("zero extents");
918 { // allow double high walls
919 if (maxs - mins <= subdivide_size/* *2 */)
922 else if (maxs - mins <= subdivide_size)
928 v = VectorNormalize (temp, temp);
930 dist = (mins + subdivide_size - 16)/v;
932 ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
933 if (!frontw || !backw)
934 Error ("SubdivideFace: didn't split the polygon");
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];
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];
946 SubdivideFace (node, f->split[0]);
947 SubdivideFace (node, f->split[1]);
953 void SubdivideNodeFaces (node_t *node)
957 for (f = node->faces ; f ; f=f->next)
959 SubdivideFace (node, f);
963 //===========================================================================
974 face_t *FaceFromPortal (portal_t *p, int pside)
981 return NULL; // portal does not bridge different visible contents
985 f->texinfo = side->texinfo;
986 f->planenum = (side->planenum & ~1) | pside;
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
995 f->w = ReverseWinding(p->winding);
996 f->contents = p->nodes[1]->contents;
1000 f->w = CopyWinding(p->winding);
1001 f->contents = p->nodes[0]->contents;
1011 If a portal will make a visible face,
1012 mark the side that originally created it
1014 solid / empty : solid
1015 solid / water : solid
1016 water / empty : water
1017 water / water : none
1020 void MakeFaces_r (node_t *node)
1025 // recurse down to leafs
1026 if (node->planenum != PLANENUM_LEAF)
1028 MakeFaces_r (node->children[0]);
1029 MakeFaces_r (node->children[1]);
1031 // merge together all visible faces on the node
1033 MergeNodeFaces (node);
1035 SubdivideNodeFaces (node);
1040 // solid leafs never have visible faces
1041 if (node->contents & CONTENTS_SOLID)
1044 // see which portals are valid
1045 for (p=node->portals ; p ; p = p->next[s])
1047 s = (p->nodes[1] == node);
1049 p->face[s] = FaceFromPortal (p, s);
1053 p->face[s]->next = p->onnode->faces;
1054 p->onnode->faces = p->face[s];
1064 void MakeFaces (node_t *node)
1066 Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n");
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);