home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / qbsp / tjunc.c < prev    next >
C/C++ Source or Header  |  1996-09-12  |  9KB  |  507 lines
  1. // tjunc.c
  2.  
  3. #include "bsp5.h"
  4.  
  5.  
  6. typedef struct wvert_s
  7. {
  8.     vec_t    t;
  9.     struct wvert_s *prev, *next;
  10. } wvert_t;
  11.  
  12. typedef struct wedge_s
  13. {
  14.     struct wedge_s *next;
  15.     vec3_t    dir;
  16.     vec3_t    origin;
  17.     wvert_t    head;
  18. } wedge_t;
  19.  
  20. int        numwedges, numwverts;
  21. int        tjuncs;
  22. int        tjuncfaces;
  23.  
  24. #define    MAXWVERTS    0x20000
  25. #define    MAXWEDGES    0x10000
  26.  
  27.  
  28. wvert_t    wverts[MAXWVERTS];
  29. wedge_t    wedges[MAXWEDGES];
  30.  
  31.  
  32. void PrintFace (face_t *f)
  33. {
  34.     int        i;
  35.     
  36.     for (i=0 ; i<f->numpoints ; i++)
  37.         printf ("(%5.2f, %5.2f, %5.2f)\n", f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  38. }
  39.  
  40. //============================================================================
  41.  
  42. #define    NUM_HASH    1024
  43.  
  44. wedge_t    *wedge_hash[NUM_HASH];
  45.  
  46. static    vec3_t    hash_min, hash_scale;
  47.  
  48. static    void InitHash (vec3_t mins, vec3_t maxs)
  49. {
  50.     vec3_t    size;
  51.     vec_t    volume;
  52.     vec_t    scale;
  53.     int        newsize[2];
  54.     
  55.     VectorCopy (mins, hash_min);
  56.     VectorSubtract (maxs, mins, size);
  57.     memset (wedge_hash, 0, sizeof(wedge_hash));
  58.     
  59.     volume = size[0]*size[1];
  60.     
  61.     scale = sqrt(volume / NUM_HASH);
  62.  
  63.     newsize[0] = size[0] / scale;
  64.     newsize[1] = size[1] / scale;
  65.  
  66.     hash_scale[0] = newsize[0] / size[0];
  67.     hash_scale[1] = newsize[1] / size[1];
  68.     hash_scale[2] = newsize[1];
  69. }
  70.  
  71. static    unsigned HashVec (vec3_t vec)
  72. {
  73.     unsigned    h;
  74.  
  75.     h =    hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2]
  76.         + hash_scale[1] * (vec[1] - hash_min[1]);
  77.     if ( h >= NUM_HASH)
  78.         return NUM_HASH - 1;
  79.     return h;
  80. }
  81.  
  82. //============================================================================
  83.  
  84. void CanonicalVector (vec3_t vec)
  85. {
  86.     VectorNormalize (vec);
  87.     if (vec[0] > EQUAL_EPSILON)
  88.         return;
  89.     else if (vec[0] < -EQUAL_EPSILON)
  90.     {
  91.         VectorSubtract (vec3_origin, vec, vec);
  92.         return;
  93.     }
  94.     else
  95.         vec[0] = 0;
  96.  
  97.     if (vec[1] > EQUAL_EPSILON)
  98.         return;
  99.     else if (vec[1] < -EQUAL_EPSILON)
  100.     {
  101.         VectorSubtract (vec3_origin, vec, vec);
  102.         return;
  103.     }
  104.     else
  105.         vec[1] = 0;
  106.         
  107.     if (vec[2] > EQUAL_EPSILON)
  108.         return;
  109.     else if (vec[2] < -EQUAL_EPSILON)
  110.     {
  111.         VectorSubtract (vec3_origin, vec, vec);
  112.         return;
  113.     }
  114.     else
  115.         vec[2] = 0;
  116.     Error ("CanonicalVector: degenerate");
  117. }
  118.  
  119. wedge_t    *FindEdge (vec3_t p1, vec3_t p2, vec_t *t1, vec_t *t2)
  120. {
  121.     vec3_t    origin;
  122.     vec3_t    dir;
  123.     wedge_t    *w;
  124.     vec_t    temp;
  125.     int        h;
  126.     
  127.     VectorSubtract (p2, p1, dir);
  128.     CanonicalVector (dir);
  129.  
  130.     *t1 = DotProduct (p1, dir);
  131.     *t2 = DotProduct (p2, dir);
  132.  
  133.     VectorMA (p1, -*t1, dir, origin);
  134.  
  135.     if (*t1 > *t2)
  136.     {
  137.         temp = *t1;
  138.         *t1 = *t2;
  139.         *t2 = temp;
  140.     }
  141.     
  142.     h = HashVec (origin);
  143.  
  144.     for (w = wedge_hash[h] ; w ; w=w->next)
  145.     {
  146.         temp = w->origin[0] - origin[0];
  147.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  148.             continue;
  149.         temp = w->origin[1] - origin[1];
  150.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  151.             continue;
  152.         temp = w->origin[2] - origin[2];
  153.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  154.             continue;
  155.         
  156.         temp = w->dir[0] - dir[0];
  157.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  158.             continue;
  159.         temp = w->dir[1] - dir[1];
  160.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  161.             continue;
  162.         temp = w->dir[2] - dir[2];
  163.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  164.             continue;
  165.  
  166.         return w;
  167.     }
  168.     
  169.     if (numwedges == MAXWEDGES)
  170.         Error ("FindEdge: numwedges == MAXWEDGES");
  171.     w = &wedges[numwedges];
  172.     numwedges++;
  173.     
  174.     w->next = wedge_hash[h];
  175.     wedge_hash[h] = w;
  176.     
  177.     VectorCopy (origin, w->origin);
  178.     VectorCopy (dir, w->dir);
  179.     w->head.next = w->head.prev = &w->head;
  180.     w->head.t = 99999;
  181.     return w;
  182. }
  183.  
  184.  
  185. /*
  186. ===============
  187. AddVert
  188.  
  189. ===============
  190. */
  191. #define    T_EPSILON    0.01
  192.  
  193. void AddVert (wedge_t *w, vec_t t)
  194. {
  195.     wvert_t    *v, *newv;
  196.     
  197.     v = w->head.next;
  198.     do
  199.     {
  200.         if (fabs(v->t - t) < T_EPSILON)
  201.             return;
  202.         if (v->t > t)
  203.             break;
  204.         v = v->next;
  205.     } while (1);
  206.         
  207. // insert a new wvert before v
  208.     if (numwverts == MAXWVERTS)
  209.         Error ("AddVert: numwverts == MAXWVERTS");
  210.  
  211.     newv = &wverts[numwverts];
  212.     numwverts++;
  213.     
  214.     newv->t = t;
  215.     newv->next = v;
  216.     newv->prev = v->prev;
  217.     v->prev->next = newv;
  218.     v->prev = newv;
  219. }
  220.  
  221.  
  222. /*
  223. ===============
  224. AddEdge
  225.  
  226. ===============
  227. */
  228. void AddEdge (vec3_t p1, vec3_t p2)
  229. {
  230.     wedge_t    *w;
  231.     vec_t    t1, t2;
  232.     
  233.     w = FindEdge(p1, p2, &t1, &t2);
  234.     AddVert (w, t1);
  235.     AddVert (w, t2);
  236. }
  237.  
  238. /*
  239. ===============
  240. AddFaceEdges
  241.  
  242. ===============
  243. */
  244. void AddFaceEdges (face_t *f)
  245. {
  246.     int        i, j;
  247.     
  248.     for (i=0 ; i < f->numpoints ; i++)
  249.     {
  250.          j = (i+1)%f->numpoints;
  251.          AddEdge (f->pts[i], f->pts[j]);
  252.     }
  253. }
  254.  
  255.  
  256. //============================================================================
  257.  
  258. // a specially allocated face that can hold hundreds of edges if needed
  259. byte    superfacebuf[8192];
  260. face_t    *superface = (face_t *)superfacebuf;
  261.  
  262. void FixFaceEdges (face_t *f);
  263.  
  264. face_t    *newlist;
  265.  
  266. void SplitFaceForTjunc (face_t *f, face_t *original)
  267. {
  268.     int            i;
  269.     face_t        *new, *chain;
  270.     vec3_t        dir, test;
  271.     vec_t        v;
  272.     int            firstcorner, lastcorner;
  273.     
  274.     chain = NULL;
  275.     do
  276.     {
  277.         if (f->numpoints <= MAXPOINTS)
  278.         {    // the face is now small enough without more cutting
  279.             // so copy it back to the original
  280.             *original = *f;
  281.             original->original = chain;
  282.             original->next = newlist;
  283.             newlist = original;
  284.             return;
  285.         }
  286.         
  287.         tjuncfaces++;
  288.         
  289. restart:    
  290.     // find the last corner    
  291.         VectorSubtract (f->pts[f->numpoints-1], f->pts[0], dir);
  292.         VectorNormalize (dir);        
  293.         for (lastcorner=f->numpoints-1 ; lastcorner > 0 ; lastcorner--)
  294.         {
  295.             VectorSubtract (f->pts[lastcorner-1], f->pts[lastcorner], test);
  296.             VectorNormalize (test);
  297.             v = DotProduct (test, dir);
  298.             if (v < 0.9999 || v > 1.00001)
  299.             {
  300.                 break;
  301.             }
  302.         }
  303.     
  304.     // find the first corner    
  305.         VectorSubtract (f->pts[1], f->pts[0], dir);
  306.         VectorNormalize (dir);        
  307.         for (firstcorner=1 ; firstcorner < f->numpoints-1 ; firstcorner++)
  308.         {
  309.             VectorSubtract (f->pts[firstcorner+1], f->pts[firstcorner], test);
  310.             VectorNormalize (test);
  311.             v = DotProduct (test, dir);
  312.             if (v < 0.9999 || v > 1.00001)
  313.             {
  314.                 break;
  315.             }
  316.         }
  317.     
  318.         if (firstcorner+2 >= MAXPOINTS)
  319.         {
  320.         // rotate the point winding
  321.             VectorCopy (f->pts[0], test);
  322.             for (i=1 ; i<f->numpoints ; i++)
  323.             {
  324.                 VectorCopy (f->pts[i], f->pts[i-1]);
  325.             }
  326.             VectorCopy (test, f->pts[f->numpoints-1]);
  327.             goto restart;
  328.         }
  329.         
  330.         
  331.     // cut off as big a piece as possible, less than MAXPOINTS, and not
  332.     // past lastcorner
  333.             
  334.         new = NewFaceFromFace (f);
  335.         if (f->original)
  336.             Error ("SplitFaceForTjunc: f->original");
  337.             
  338.         new->original = chain;
  339.         chain = new;
  340.         new->next = newlist;
  341.         newlist = new;
  342.         if (f->numpoints - firstcorner <= MAXPOINTS)
  343.             new->numpoints = firstcorner+2;
  344.         else if (lastcorner+2 < MAXPOINTS &&
  345.         f->numpoints - lastcorner <= MAXPOINTS)
  346.             new->numpoints = lastcorner+2;
  347.         else
  348.             new->numpoints = MAXPOINTS;
  349.  
  350.         for (i=0 ; i<new->numpoints ; i++)
  351.         {
  352.             VectorCopy (f->pts[i], new->pts[i]);
  353.         }
  354.         
  355.         
  356.         for (i=new->numpoints-1 ; i<f->numpoints ; i++)
  357.         {
  358.             VectorCopy (f->pts[i], f->pts[i-(new->numpoints-2)]);
  359.         }
  360.         f->numpoints -= (new->numpoints-2);
  361.     } while (1);
  362.  
  363. }
  364.  
  365.  
  366. /*
  367. ===============
  368. FixFaceEdges
  369.  
  370. ===============
  371. */
  372. void FixFaceEdges (face_t *f)
  373. {
  374.     int        i, j, k;
  375.     wedge_t    *w;
  376.     wvert_t    *v;
  377.     vec_t    t1, t2;
  378.  
  379.     *superface = *f;
  380.     
  381. restart:
  382.     for (i=0 ; i < superface->numpoints ; i++)
  383.     {
  384.          j = (i+1)%superface->numpoints;
  385.  
  386.         w = FindEdge (superface->pts[i], superface->pts[j], &t1, &t2);
  387.         
  388.         for (v=w->head.next ; v->t < t1 + T_EPSILON ; v = v->next)
  389.         {
  390.         }
  391.         
  392.         if (v->t < t2-T_EPSILON)
  393.         {
  394.             tjuncs++;
  395.         // insert a new vertex here
  396.             for (k = superface->numpoints ; k> j ; k--)
  397.             {
  398.                 VectorCopy (superface->pts[k-1], superface->pts[k]);
  399.             }
  400.             VectorMA (w->origin, v->t, w->dir, superface->pts[j]);
  401.             superface->numpoints++;
  402.             goto restart;    
  403.         }
  404.     }
  405.  
  406.  
  407.     if (superface->numpoints <= MAXPOINTS)
  408.     {
  409.         *f = *superface;
  410.         f->next = newlist;
  411.         newlist = f;
  412.         return;
  413.     } 
  414.  
  415. // the face needs to be split into multiple faces because of too many edges
  416.  
  417.     SplitFaceForTjunc (superface, f);
  418.  
  419. }
  420.  
  421.  
  422. //============================================================================
  423.  
  424. void tjunc_find_r (node_t *node)
  425. {
  426.     face_t    *f;
  427.  
  428.     if (node->planenum == PLANENUM_LEAF)
  429.         return;
  430.         
  431.     for (f=node->faces ; f ; f=f->next)
  432.         AddFaceEdges (f);
  433.         
  434.     tjunc_find_r (node->children[0]);
  435.     tjunc_find_r (node->children[1]);
  436. }
  437.  
  438. void tjunc_fix_r (node_t *node)
  439. {
  440.     face_t    *f, *next;
  441.  
  442.     if (node->planenum == PLANENUM_LEAF)
  443.         return;
  444.         
  445.     newlist = NULL;
  446.     
  447.     for (f=node->faces ; f ; f=next)
  448.     {
  449.         next = f->next;
  450.         FixFaceEdges (f);
  451.     }
  452.  
  453.     node->faces = newlist;
  454.  
  455.     tjunc_fix_r (node->children[0]);
  456.     tjunc_fix_r (node->children[1]);
  457. }
  458.  
  459. /*
  460. ===========
  461. tjunc
  462.  
  463. ===========
  464. */
  465. void tjunc (node_t *headnode)
  466. {
  467.     vec3_t    maxs, mins;
  468.     int        i;
  469.     
  470.     qprintf ("---- tjunc ----\n");
  471.     
  472.     if (notjunc)
  473.         return;
  474.  
  475. //
  476. // identify all points on common edges
  477. //
  478.  
  479. // origin points won't allways be inside the map, so extend the hash area 
  480.     for (i=0 ; i<3 ; i++)
  481.     {
  482.         if ( fabs(brushset->maxs[i]) > fabs(brushset->mins[i]) )
  483.             maxs[i] = fabs(brushset->maxs[i]);
  484.         else
  485.             maxs[i] = fabs(brushset->mins[i]);
  486.     }
  487.     VectorSubtract (vec3_origin, maxs, mins);
  488.     
  489.     InitHash (mins, maxs);
  490.     
  491.     numwedges = numwverts = 0;
  492.  
  493.     tjunc_find_r (headnode);
  494.         
  495.     qprintf ("%i world edges  %i edge points\n", numwedges, numwverts);
  496.  
  497. //
  498. // add extra vertexes on edges where needed
  499. //
  500.     tjuncs = tjuncfaces = 0;
  501.  
  502.     tjunc_fix_r (headnode);
  503.  
  504.     qprintf ("%i edges added by tjunctions\n", tjuncs);
  505.     qprintf ("%i faces added by tjunctions\n", tjuncfaces);
  506. }
  507.