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