home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / qbsp / surfaces.c < prev    next >
C/C++ Source or Header  |  1996-09-12  |  9KB  |  513 lines
  1. // divide.h
  2.  
  3. #include "bsp5.h"
  4.  
  5.  
  6. surface_t    newcopy_t;
  7.  
  8. /*
  9. a surface has all of the faces that could be drawn on a given plane
  10.  
  11. the outside filling stage can remove some of them so a better bsp can be generated
  12.  
  13. */
  14.  
  15. int    subdivides;
  16.  
  17.  
  18. /*
  19. ===============
  20. SubdivideFace
  21.  
  22. If the face is >256 in either texture direction, carve a valid sized
  23. piece off and insert the remainder in the next link
  24. ===============
  25. */
  26. void SubdivideFace (face_t *f, face_t **prevptr)
  27. {
  28.     float        mins, maxs;
  29.     vec_t        v;
  30.     int            axis, i;
  31.     plane_t        plane;
  32.     face_t        *front, *back, *next;
  33.     texinfo_t    *tex;
  34.  
  35. // special (non-surface cached) faces don't need subdivision
  36.     tex = &texinfo[f->texturenum];
  37.  
  38.     if ( tex->flags & TEX_SPECIAL)
  39.         return;
  40.  
  41.  
  42.     for (axis = 0 ; axis < 2 ; axis++)
  43.     {
  44.         while (1)
  45.         {
  46.             mins = 9999;
  47.             maxs = -9999;
  48.             
  49.             for (i=0 ; i<f->numpoints ; i++)
  50.             {
  51.                 v = DotProduct (f->pts[i], tex->vecs[axis]);
  52.                 if (v < mins)
  53.                     mins = v;
  54.                 if (v > maxs)
  55.                     maxs = v;
  56.             }
  57.         
  58.             if (maxs - mins <= subdivide_size)
  59.                 break;
  60.             
  61.         // split it
  62.             subdivides++;
  63.             
  64.             VectorCopy (tex->vecs[axis], plane.normal);
  65.             v = VectorLength (plane.normal);
  66.             VectorNormalize (plane.normal);            
  67.             plane.dist = (mins + subdivide_size - 16)/v;
  68.             next = f->next;
  69.             SplitFace (f, &plane, &front, &back);
  70.             if (!front || !back)
  71.                 Error ("SubdivideFace: didn't split the polygon");
  72.             *prevptr = back;
  73.             back->next = front;
  74.             front->next = next;
  75.             f = back;
  76.         }
  77.     }
  78. }
  79.  
  80.  
  81. /*
  82. ================
  83. SubdivideFaces
  84. ================
  85. */
  86. void SubdivideFaces (surface_t *surfhead)
  87. {
  88.     surface_t       *surf;
  89.     face_t          *f , **prevptr;
  90.  
  91.     qprintf ("--- SubdivideFaces ---\n");
  92.  
  93.     subdivides = 0;
  94.  
  95.     for (surf = surfhead ; surf ; surf=surf->next)
  96.     {
  97.         prevptr = &surf->faces;
  98.         while (1)
  99.         {
  100.             f = *prevptr;
  101.             if (!f)
  102.                 break;
  103.             SubdivideFace (f, prevptr);
  104.             f = *prevptr;
  105.             prevptr = &f->next;
  106.         }
  107.     }
  108.  
  109.     qprintf ("%i faces added by subdivision\n", subdivides);
  110.     
  111. }
  112.  
  113.  
  114. /*
  115. =============================================================================
  116.  
  117. GatherNodeFaces
  118.  
  119. Frees the current node tree and returns a new chain of the surfaces that
  120. have inside faces.
  121. =============================================================================
  122. */
  123.  
  124. void GatherNodeFaces_r (node_t *node)
  125. {
  126.     face_t    *f, *next;
  127.     
  128.     if (node->planenum != PLANENUM_LEAF)
  129.     {
  130. //
  131. // decision node
  132. //
  133.         for (f=node->faces ; f ; f=next)
  134.         {
  135.             next = f->next;
  136.             if (!f->numpoints)
  137.             {    // face was removed outside
  138.                 FreeFace (f);
  139.             }
  140.             else
  141.             {
  142.                 f->next = validfaces[f->planenum];
  143.                 validfaces[f->planenum] = f;
  144.             }
  145.         }
  146.         
  147.         GatherNodeFaces_r (node->children[0]);
  148.         GatherNodeFaces_r (node->children[1]);
  149.         
  150.         free (node);
  151.     }
  152.     else
  153.     {
  154. //
  155. // leaf node
  156. //
  157.         free (node);
  158.     }
  159. }
  160.  
  161. /*
  162. ================
  163. GatherNodeFaces
  164.  
  165. ================
  166. */
  167. surface_t *GatherNodeFaces (node_t *headnode)
  168. {
  169.     memset (validfaces, 0, sizeof(validfaces));
  170.     GatherNodeFaces_r (headnode);
  171.     return BuildSurfaces ();    
  172. }
  173.  
  174. //===========================================================================
  175.  
  176. typedef struct hashvert_s
  177. {
  178.     struct hashvert_s    *next;
  179.     vec3_t    point;
  180.     int        num;
  181.     int        numplanes;        // for corner determination
  182.     int        planenums[2];
  183.     int        numedges;
  184. } hashvert_t;
  185.  
  186. #define    POINT_EPSILON    0.01
  187.  
  188. int        c_cornerverts;
  189.  
  190. hashvert_t    hvertex[MAX_MAP_VERTS];
  191. hashvert_t    *hvert_p;
  192.  
  193. face_t        *edgefaces[MAX_MAP_EDGES][2];
  194. int        firstmodeledge = 1;
  195. int        firstmodelface;
  196.  
  197. //============================================================================
  198.  
  199. #define    NUM_HASH    4096
  200.  
  201. hashvert_t    *hashverts[NUM_HASH];
  202.  
  203. static    vec3_t    hash_min, hash_scale;
  204.  
  205. static    void InitHash (void)
  206. {
  207.     vec3_t    size;
  208.     vec_t    volume;
  209.     vec_t    scale;
  210.     int        newsize[2];
  211.     int        i;
  212.     
  213.     memset (hashverts, 0, sizeof(hashverts));
  214.  
  215.     for (i=0 ; i<3 ; i++)
  216.     {
  217.         hash_min[i] = -8000;
  218.         size[i] = 16000;
  219.     }
  220.  
  221.     volume = size[0]*size[1];
  222.     
  223.     scale = sqrt(volume / NUM_HASH);
  224.  
  225.     newsize[0] = size[0] / scale;
  226.     newsize[1] = size[1] / scale;
  227.  
  228.     hash_scale[0] = newsize[0] / size[0];
  229.     hash_scale[1] = newsize[1] / size[1];
  230.     hash_scale[2] = newsize[1];
  231.     
  232.     hvert_p = hvertex;
  233. }
  234.  
  235. static    unsigned HashVec (vec3_t vec)
  236. {
  237.     unsigned    h;
  238.     
  239.     h =    hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2]
  240.         + hash_scale[1] * (vec[1] - hash_min[1]);
  241.     if ( h >= NUM_HASH)
  242.         return NUM_HASH - 1;
  243.     return h;
  244. }
  245.  
  246.  
  247. /*
  248. =============
  249. GetVertex
  250. =============
  251. */
  252. int    GetVertex (vec3_t in, int planenum)
  253. {
  254.     int            h;
  255.     int            i;
  256.     hashvert_t    *hv;
  257.     vec3_t        vert;
  258.     
  259.     for (i=0 ; i<3 ; i++)
  260.     {
  261.         if ( fabs(in[i] - Q_rint(in[i])) < 0.001)
  262.             vert[i] = Q_rint(in[i]);
  263.         else
  264.             vert[i] = in[i];
  265.     }
  266.     
  267.     h = HashVec (vert);
  268.     
  269.     for (hv=hashverts[h] ; hv ; hv=hv->next)
  270.     {
  271.         if ( fabs(hv->point[0]-vert[0])<POINT_EPSILON
  272.         && fabs(hv->point[1]-vert[1])<POINT_EPSILON
  273.         && fabs(hv->point[2]-vert[2])<POINT_EPSILON )
  274.         {
  275.             hv->numedges++;
  276.             if (hv->numplanes == 3)
  277.                 return hv->num;        // allready known to be a corner
  278.             for (i=0 ; i<hv->numplanes ; i++)
  279.                 if (hv->planenums[i] == planenum)
  280.                     return hv->num;        // allready know this plane
  281.             if (hv->numplanes == 2)
  282.                 c_cornerverts++;
  283.             else
  284.                 hv->planenums[hv->numplanes] = planenum;
  285.             hv->numplanes++;
  286.             return hv->num;
  287.         }
  288.     }
  289.     
  290.     hv = hvert_p;
  291.     hv->numedges = 1;
  292.     hv->numplanes = 1;
  293.     hv->planenums[0] = planenum;
  294.     hv->next = hashverts[h];
  295.     hashverts[h] = hv;
  296.     VectorCopy (vert, hv->point);
  297.     hv->num = numvertexes;
  298.     if (hv->num==MAX_MAP_VERTS)
  299.         Error ("GetVertex: MAX_MAP_VERTS");
  300.     hvert_p++;
  301.         
  302. // emit a vertex
  303.     if (numvertexes == MAX_MAP_VERTS)
  304.         Error ("numvertexes == MAX_MAP_VERTS");
  305.  
  306.     dvertexes[numvertexes].point[0] = vert[0];
  307.     dvertexes[numvertexes].point[1] = vert[1];
  308.     dvertexes[numvertexes].point[2] = vert[2];
  309.     numvertexes++;
  310.  
  311.     return hv->num;
  312. }
  313.  
  314. //===========================================================================
  315.  
  316.  
  317. /*
  318. ==================
  319. GetEdge
  320.  
  321. Don't allow four way edges
  322. ==================
  323. */
  324. int    c_tryedges;
  325.  
  326. int GetEdge (vec3_t p1, vec3_t p2, face_t *f)
  327. {
  328.     int        v1, v2;
  329.     dedge_t    *edge;
  330.     int        i;
  331.  
  332.     if (!f->contents[0])
  333.         Error ("GetEdge: 0 contents");
  334.  
  335.     c_tryedges++;        
  336.     v1 = GetVertex (p1, f->planenum);
  337.     v2 = GetVertex (p2, f->planenum);
  338.     for (i=firstmodeledge ; i < numedges ; i++)
  339.     {
  340.         edge = &dedges[i];
  341.         if (v1 == edge->v[1] && v2 == edge->v[0]
  342.         && !edgefaces[i][1]
  343.         && edgefaces[i][0]->contents[0] == f->contents[0])
  344.         {
  345.             edgefaces[i][1] = f;
  346.             return -i;
  347.         }
  348.     }
  349.     
  350. // emit an edge
  351.     if (numedges == MAX_MAP_EDGES)
  352.         Error ("numedges == MAX_MAP_EDGES");
  353.     edge = &dedges[numedges];
  354.     numedges++;
  355.     edge->v[0] = v1;
  356.     edge->v[1] = v2;
  357.     edgefaces[i][0] = f;
  358.     
  359.     return i;
  360. }
  361.  
  362.  
  363. /*
  364. ==================
  365. FindFaceEdges
  366. ==================
  367. */
  368. void FindFaceEdges (face_t *face)
  369. {
  370.     int        i;
  371.  
  372.     face->outputnumber = -1;    
  373.     if (face->numpoints > MAXEDGES)
  374.         Error ("WriteFace: %i points", face->numpoints);
  375.  
  376.     for (i=0; i<face->numpoints ; i++)
  377.         face->edges[i] =  GetEdge
  378.         (face->pts[i], face->pts[(i+1)%face->numpoints], face);    
  379. }
  380.  
  381. /*
  382. =============
  383. CheckVertexes
  384. // debugging
  385. =============
  386. */
  387. void CheckVertexes (void)
  388. {
  389.     int        cb, c0, c1, c2, c3;    
  390.     hashvert_t    *hv;
  391.     
  392.     cb = c0 = c1 = c2 = c3 = 0;
  393.     for (hv=hvertex ; hv!=hvert_p ; hv++)
  394.     {
  395.         if (hv->numedges < 0 || hv->numedges & 1)
  396.             cb++;
  397.         else if (!hv->numedges)
  398.             c0++;
  399.         else if (hv->numedges == 2)
  400.             c1++;
  401.         else if (hv->numedges == 4)
  402.             c2++;
  403.         else
  404.             c3++;
  405.     }
  406.     
  407.     qprintf ("%5i bad edge points\n", cb);
  408.     qprintf ("%5i 0 edge points\n", c0);
  409.     qprintf ("%5i 2 edge points\n", c1);
  410.     qprintf ("%5i 4 edge points\n", c2);
  411.     qprintf ("%5i 6+ edge points\n", c3);
  412. }
  413.  
  414. /*
  415. =============
  416. CheckEdges
  417. // debugging
  418. =============
  419. */
  420. void CheckEdges (void)
  421. {
  422.     dedge_t    *edge;
  423.     int        i;
  424.     dvertex_t    *d1, *d2;
  425.     face_t        *f1, *f2;
  426.     int        c_nonconvex;
  427.     int        c_multitexture;
  428.     
  429.     c_nonconvex = c_multitexture = 0;
  430.     
  431. //    CheckVertexes ();
  432.     
  433.     for (i=1 ; i < numedges ; i++)
  434.     {
  435.         edge = &dedges[i];
  436.         if (!edgefaces[i][1])
  437.         {
  438.             d1 = &dvertexes[edge->v[0]];
  439.             d2 = &dvertexes[edge->v[1]];
  440.             qprintf ("unshared edge at: (%8.2f, %8.2f, %8.2f) (%8.2f, %8.2f, %8.2f)\n",d1->point[0], d1->point[1], d1->point[2], d2->point[0], d2->point[1], d2->point[2]); 
  441.         }
  442.         else
  443.         {
  444.             f1 = edgefaces[i][0];
  445.             f2 = edgefaces[i][1];
  446.             if (f1->planeside != f2->planeside)
  447.                 continue;
  448.             if (f1->planenum != f2->planenum)
  449.                 continue;
  450.                 
  451.             // on the same plane, might be discardable
  452.             if (f1->texturenum == f2->texturenum)
  453.             {
  454.                 hvertex[edge->v[0]].numedges-=2;
  455.                 hvertex[edge->v[1]].numedges-=2;
  456.                 c_nonconvex++;
  457.             }
  458.             else
  459.                 c_multitexture++;
  460.         }
  461.     }
  462.  
  463. //    qprintf ("%5i edges\n", i);
  464. //    qprintf ("%5i c_nonconvex\n", c_nonconvex);
  465. //    qprintf ("%5i c_multitexture\n", c_multitexture);
  466.  
  467. //    CheckVertexes ();
  468. }
  469.  
  470.  
  471. /*
  472. ================
  473. MakeFaceEdges_r
  474. ================
  475. */
  476. void MakeFaceEdges_r (node_t *node)
  477. {
  478.     face_t    *f;
  479.     
  480.     if (node->planenum == PLANENUM_LEAF)
  481.         return;
  482.         
  483.     for (f=node->faces ; f ; f=f->next)
  484.         FindFaceEdges (f);
  485.         
  486.     MakeFaceEdges_r (node->children[0]);
  487.     MakeFaceEdges_r (node->children[1]);
  488. }
  489.  
  490. /*
  491. ================
  492. MakeFaceEdges
  493. ================
  494. */
  495. void MakeFaceEdges (node_t *headnode)
  496. {
  497.     qprintf ("----- MakeFaceEdges -----\n");
  498.     
  499.     InitHash ();
  500.     c_tryedges = 0;
  501.     c_cornerverts = 0;
  502.     
  503.     MakeFaceEdges_r (headnode);
  504.  
  505. //    CheckEdges ();
  506.  
  507.     GrowNodeRegions (headnode);
  508.  
  509.     firstmodeledge = numedges;
  510.     firstmodelface = numfaces;
  511. }
  512.  
  513.