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