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