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