home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / qbsp / region.c < prev    next >
C/C++ Source or Header  |  1996-09-12  |  9KB  |  512 lines
  1. // region.h
  2.  
  3. #include "bsp5.h"
  4.  
  5. /*
  6.  
  7. input
  8. -----
  9. vertexes
  10. edges
  11. faces
  12.  
  13. output
  14. ------
  15. smaller set of vertexes
  16. smaller set of edges
  17. regions
  18. ? triangulated regions
  19. face to region mapping numbers
  20.  
  21. */
  22.  
  23. #define    MAX_EDGES_IN_REGION    32
  24.  
  25. int        firstedge;
  26.  
  27. vec3_t    region_mins, region_maxs;
  28.  
  29. void AddPointToRegion (vec3_t p)
  30. {
  31.     int        i;
  32.     
  33.     for (i=0 ; i<3 ; i++)
  34.     {
  35.         if (p[i] < region_mins[i])
  36.             region_mins[i] = p[i];
  37.         if (p[i] > region_maxs[i])
  38.             region_maxs[i] = p[i];
  39.     }    
  40. }
  41.  
  42. void ClearRegionSize (void)
  43. {
  44.     region_mins[0] = region_mins[1] = region_mins[2] = 9999;
  45.     region_maxs[0] = region_maxs[1] = region_maxs[2] = -9999;
  46. }
  47.  
  48. void AddFaceToRegionSize (face_t *f)
  49. {
  50.     int        i;
  51.  
  52.     for (i=0 ; i<f->numpoints ; i++)
  53.         AddPointToRegion (f->pts[i]);
  54. }
  55.  
  56. /*
  57. ==============
  58. CanJoinFaces
  59. ==============
  60. */
  61. qboolean CanJoinFaces (face_t *f, face_t *f2)
  62. {
  63.     vec3_t        oldmins, oldmaxs;
  64.     int            i;
  65.  
  66.     if (f2->planenum != f->planenum
  67.     || f2->planeside != f->planeside
  68.     || f2->texturenum != f->texturenum)
  69.         return false;
  70.     if (f2->outputnumber != -1)
  71.         return false;
  72.     if (f2->contents[0] != f->contents[0])
  73.     {    // does this ever happen? theyy shouldn't share.
  74.         printf ("CanJoinFaces: edge with different contents");
  75.         return false;
  76.     }
  77.     
  78. // check size constraints
  79.     if ( ! (texinfo[f->texturenum].flags & TEX_SPECIAL) )
  80.     {    
  81.         VectorCopy (region_mins, oldmins);
  82.         VectorCopy (region_maxs, oldmaxs);
  83.         AddFaceToRegionSize (f2);
  84.         for (i=0 ; i<3 ; i++)
  85.         {
  86.             if (region_maxs[i] - region_mins[i] > 240)
  87.             {
  88.                 VectorCopy (oldmins, region_mins);
  89.                 VectorCopy (oldmaxs, region_maxs);
  90.                 return false;
  91.             }
  92.         }
  93.     }
  94.     else
  95.     {
  96.         if (numsurfedges - firstedge + f2->numpoints > MAX_EDGES_IN_REGION)
  97.             return false;        // a huge water or sky polygon
  98.     }
  99.     
  100. // check edge count constraints
  101.     return true;
  102. }
  103.  
  104.  
  105. /*
  106. ==============
  107. RecursiveGrowRegion
  108. ==============
  109. */
  110. void RecursiveGrowRegion (dface_t *r, face_t *f)
  111. {
  112.     int        e;
  113.     face_t    *f2;
  114.     int        i;
  115.     
  116.     if (f->outputnumber == numfaces)
  117.         return;
  118.  
  119.     if (f->outputnumber != -1)
  120.         Error ("RecursiveGrowRegion: region collision");
  121.     f->outputnumber = numfaces;
  122.     
  123. // add edges    
  124.     for (i=0 ; i<f->numpoints ; i++)
  125.     {
  126.         e = f->edges[i];
  127.         if (!edgefaces[abs(e)][0])
  128.             continue;    // edge has allready been removed
  129.         if (e > 0)
  130.             f2 = edgefaces[e][1];
  131.         else
  132.             f2 = edgefaces[-e][0];
  133.         if (f2 && f2->outputnumber == numfaces)
  134.         {
  135.             edgefaces[abs(e)][0] = NULL;
  136.             edgefaces[abs(e)][1] = NULL;
  137.             continue;    // allready merged
  138.         }
  139.         if (f2 && CanJoinFaces (f, f2))
  140.         {    // remove the edge and merge the faces
  141.             edgefaces[abs(e)][0] = NULL;
  142.             edgefaces[abs(e)][1] = NULL;
  143.             RecursiveGrowRegion (r, f2);
  144.         }
  145.         else
  146.         {
  147.         // emit a surfedge
  148.             if (numsurfedges == MAX_MAP_SURFEDGES)
  149.                 Error ("numsurfedges == MAX_MAP_SURFEDGES");
  150.             dsurfedges[numsurfedges] = e;
  151.             numsurfedges++;
  152.         }
  153.     }
  154.  
  155. }
  156.  
  157. void PrintDface (int f)
  158. {    // for debugging
  159.     dface_t    *df;
  160.     dedge_t    *e;
  161.     int        i, n;
  162.     
  163.     df = &dfaces[f];
  164.     for (i=0 ; i<df->numedges ; i++)
  165.     {
  166.         n = dsurfedges[df->firstedge+i];
  167.         e = &dedges[abs(n)];
  168.         if (n < 0)
  169.             printf ("%5i  =  %5i : %5i\n", n, e->v[1], e->v[0]);
  170.         else
  171.             printf ("%5i  =  %5i : %5i\n", n, e->v[0], e->v[1]);
  172.     }
  173. }
  174.  
  175. void FindVertexUse (int v)
  176. {    // for debugging
  177.     int        i, j, n;
  178.     dface_t    *df;
  179.     dedge_t    *e;
  180.     
  181.     for (i=firstmodelface ; i<numfaces ; i++)
  182.     {
  183.         df = &dfaces[i];
  184.         for (j=0 ; j<df->numedges ; j++)
  185.         {
  186.             n = dsurfedges[df->firstedge+j];
  187.             e = &dedges[abs(n)];
  188.             if (e->v[0] == v || e->v[1] == v)
  189.             {
  190.                 printf ("on face %i\n", i);
  191.                 break;
  192.             }
  193.         }
  194.     }
  195. }
  196.  
  197. void FindEdgeUse (int v)
  198. {    // for debugging
  199.     int        i, j, n;
  200.     dface_t    *df;
  201.     
  202.     for (i=firstmodelface ; i<numfaces ; i++)
  203.     {
  204.         df = &dfaces[i];
  205.         for (j=0 ; j<df->numedges ; j++)
  206.         {
  207.             n = dsurfedges[df->firstedge+j];
  208.             if (n == v || -n == v)
  209.             {
  210.                 printf ("on face %i\n", i);
  211.                 break;
  212.             }
  213.         }
  214.     }
  215. }
  216.  
  217. /*
  218. ================
  219. HealEdges
  220.  
  221. Extends e1 so that it goes all the way to e2, and removes all references
  222. to e2
  223. ================
  224. */
  225. int        edgemapping[MAX_MAP_EDGES];
  226. void HealEdges (int e1, int e2)
  227. {
  228.     int        i, j, n, saved;
  229.     dface_t    *df;
  230.     dedge_t    *ed, *ed2;
  231.     vec3_t    v1, v2;
  232.     dface_t    *found[2];
  233.     int        foundj[2];
  234.  
  235. return;    
  236.     e1 = edgemapping[e1];
  237.     e2 = edgemapping[e2];
  238.  
  239. // extend e1 to e2
  240.     ed = &dedges[e1];
  241.     ed2 = &dedges[e2];
  242.     VectorSubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v1);
  243.     VectorNormalize (v1);
  244.     
  245.     if (ed->v[0] == ed2->v[0])
  246.         ed->v[0] = ed2->v[1];
  247.     else if (ed->v[0] == ed2->v[1])
  248.         ed->v[0] = ed2->v[0];
  249.     else if (ed->v[1] == ed2->v[0])
  250.         ed->v[1] = ed2->v[1];
  251.     else if (ed->v[1] == ed2->v[1])
  252.         ed->v[1] = ed2->v[0];
  253.     else
  254.         Error ("HealEdges: edges don't meet");
  255.  
  256.     VectorSubtract (dvertexes[ed->v[1]].point, dvertexes[ed->v[0]].point, v2);
  257.     VectorNormalize (v2);
  258.     
  259.     if (!VectorCompare (v1, v2))
  260.         Error ("HealEdges: edges not colinear");
  261.  
  262.     edgemapping[e2] = e1;
  263.     saved = 0;
  264.     
  265. // remove all uses of e2
  266.     for (i=firstmodelface ; i<numfaces ; i++)
  267.     {
  268.         df = &dfaces[i];
  269.         for (j=0 ; j<df->numedges ; j++)
  270.         {
  271.             n = dsurfedges[df->firstedge+j];
  272.             if (n == e2 || n == -e2)
  273.             {
  274.                 found[saved] = df;
  275.                 foundj[saved] = j;
  276.                 saved++;
  277.                 break;
  278.             }
  279.         }
  280.     }
  281.     
  282.     if (saved != 2)
  283.         printf ("WARNING: didn't find both faces for a saved edge\n");
  284.     else
  285.     {
  286.         for (i=0 ; i<2 ; i++)
  287.         {    // remove this edge
  288.             df = found[i];
  289.             j = foundj[i];
  290.             for (j++ ; j<df->numedges ; j++)
  291.                 dsurfedges[df->firstedge+j-1] =
  292.                 dsurfedges[df->firstedge+j];
  293.             dsurfedges[df->firstedge+j-1] = 0;
  294.             df->numedges--;
  295.         }
  296.  
  297.  
  298.         edgefaces[e2][0] = edgefaces[e2][1] = NULL;
  299.     }
  300. }
  301.  
  302. typedef struct
  303. {
  304.     int        numedges;
  305.     int        edges[2];
  306. } checkpoint_t;
  307.  
  308. checkpoint_t    checkpoints[MAX_MAP_VERTS];
  309.  
  310. /*
  311. ==============
  312. RemoveColinearEdges
  313. ==============
  314. */
  315. void RemoveColinearEdges (void)
  316. {
  317.     int        i,j, v;
  318.     int        c0, c1, c2, c3;
  319.     checkpoint_t    *cp;
  320.     
  321. // no edges remapped yet
  322.     for (i=0 ; i<numedges ; i++)
  323.         edgemapping[i] = i;
  324.         
  325. // find vertexes that only have two edges
  326.     memset (checkpoints, 0, sizeof(checkpoints));
  327.     
  328.     for (i=firstmodeledge ; i<numedges ; i++)
  329.     {
  330.         if (!edgefaces[i][0])
  331.             continue;        // removed
  332.         for (j=0 ; j<2 ; j++)
  333.         {
  334.             v = dedges[i].v[j];
  335.             cp = &checkpoints[v];
  336.             if (cp->numedges<2)
  337.                 cp->edges[cp->numedges] = i;
  338.             cp->numedges++;
  339.         }
  340.     }
  341.     
  342. // if a vertex only has two edges and they are colinear, it can be removed
  343.     c0 = c1 = c2 = c3 = 0;
  344.     
  345.     for (i=0 ; i<numvertexes ; i++)
  346.     {
  347.         cp = &checkpoints[i];
  348.         switch (cp->numedges)
  349.         {
  350.         case 0:
  351.             c0++;
  352.             break;
  353.         case 1:
  354.             c1++;
  355.             break;
  356.         case 2:
  357.             c2++;
  358.             HealEdges (cp->edges[0], cp->edges[1]);
  359.             break;
  360.         default:
  361.             c3++;
  362.             break;
  363.         }
  364.     }
  365.     
  366. //    qprintf ("%5i c0\n", c0);
  367. //    qprintf ("%5i c1\n", c1);
  368. //    qprintf ("%5i c2\n", c2);
  369. //    qprintf ("%5i c3+\n", c3);
  370.     qprintf ("%5i deges removed by tjunction healing\n", c2);
  371. }
  372.  
  373. /*
  374. ==============
  375. CountRealNumbers
  376. ==============
  377. */
  378. void CountRealNumbers (void)
  379. {
  380.     int        i;
  381.     int        c;
  382.     
  383.     qprintf ("%5i regions\n", numfaces-firstmodelface);
  384.  
  385.     c = 0;
  386.     for (i=firstmodelface ; i<numfaces ; i++)
  387.         c += dfaces[i].numedges;
  388.     qprintf ("%5i real marksurfaces\n", c);
  389.     
  390.     c = 0;
  391.     for (i=firstmodeledge ; i<numedges ; i++)
  392.         if (edgefaces[i][0])
  393.             c++;        // not removed
  394.  
  395.     qprintf ("%5i real edges\n", c);
  396. }
  397.  
  398. //=============================================================================
  399.  
  400. /*
  401. ==============
  402. GrowNodeRegion_r
  403. ==============
  404. */
  405. void GrowNodeRegion_r (node_t *node)
  406. {
  407.     dface_t        *r;
  408.     face_t        *f;
  409.     int            i;
  410.  
  411.     if (node->planenum == PLANENUM_LEAF)
  412.         return;
  413.  
  414.     node->firstface = numfaces;
  415.  
  416.     for (f=node->faces ; f ; f=f->next)
  417.     {
  418. //        if (f->outputnumber != -1)
  419. //            continue;    // allready grown into an earlier region
  420.             
  421.     // emit a region
  422.  
  423.         if (numfaces == MAX_MAP_FACES)
  424.             Error ("MAX_MAP_FACES");
  425.         f->outputnumber = numfaces;
  426.         r = &dfaces[numfaces];
  427.  
  428.         r->planenum = node->outputplanenum;
  429.         r->side = f->planeside;
  430.         r->texinfo = f->texturenum;
  431.         for (i=0 ; i<MAXLIGHTMAPS ; i++)
  432.             r->styles[i] = 255;
  433.         r->lightofs = -1;
  434.  
  435.     // add the face and mergable neighbors to it
  436.     
  437. #if 0
  438.         ClearRegionSize ();
  439.         AddFaceToRegionSize (f);
  440.         RecursiveGrowRegion (r, f);
  441. #endif
  442.         r->firstedge = firstedge = numsurfedges;
  443.         for (i=0 ; i<f->numpoints ; i++)
  444.         {
  445.             if (numsurfedges == MAX_MAP_SURFEDGES)
  446.                 Error ("numsurfedges == MAX_MAP_SURFEDGES");
  447.             dsurfedges[numsurfedges] = f->edges[i];
  448.             numsurfedges++;
  449.         }
  450.         
  451.         r->numedges = numsurfedges - r->firstedge;
  452.  
  453.         numfaces++;
  454.     }
  455.  
  456.     node->numfaces = numfaces - node->firstface;
  457.  
  458.     GrowNodeRegion_r (node->children[0]);
  459.     GrowNodeRegion_r (node->children[1]);
  460. }
  461.  
  462.  
  463. /*
  464. ==============
  465. GrowNodeRegions
  466. ==============
  467. */
  468. void GrowNodeRegions (node_t *headnode)
  469. {
  470.     qprintf ("---- GrowRegions ----\n");
  471.         
  472.     GrowNodeRegion_r (headnode);
  473.         
  474. //RemoveColinearEdges ();
  475.     CountRealNumbers ();
  476. }
  477.  
  478. /*
  479. ===============================================================================
  480.  
  481. Turn the faces on a plane into optimal non-convex regions
  482. The edges may still be split later as a result of tjunctions
  483.  
  484. typedef struct
  485. {
  486.     vec3_t    dir;
  487.     vec3_t    origin;
  488.     vec3_t    p[2];
  489. } 
  490. for all faces
  491.     for all edges
  492.         for all edges so far
  493.             if overlap
  494.                 split
  495.                 
  496.  
  497. ===============================================================================
  498. */
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512.