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