home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Programmation / c / QuakeC / qtools0.2-src.lha / src / libqbuild / winding.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  13.1 KB  |  585 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int c_activewindings, c_peakwindings;
  5.  
  6. /*=========================================================================== */
  7.  
  8. void WindingBounds(register struct winding *w, vec3_t mins, vec3_t maxs)
  9. {
  10.   vec_t v;
  11.   int i, j;
  12.  
  13.   mins[0] = mins[1] = mins[2] = 99999;
  14.   maxs[0] = maxs[1] = maxs[2] = -99999;
  15.  
  16.   for (i = 0; i < w->numpoints; i++) {
  17.     for (j = 0; j < 3; j++) {
  18.       v = w->points[i][j];
  19.       if (v < mins[j])
  20.     mins[j] = v;
  21.       if (v > maxs[j])
  22.     maxs[j] = v;
  23.     }
  24.   }
  25. }
  26. void WindingCenter(register struct winding *w, vec3_t center)
  27. {
  28.   int i;
  29.  
  30.   VectorClear(center);
  31.   for (i = 0; i < w->numpoints; i++)
  32.     VectorAdd(w->points[i], center, center);
  33.  
  34.   VectorScale(center, 1.0 / w->numpoints, center);
  35. }
  36.  
  37. vec_t WindingArea(register struct winding *w)
  38. {
  39.   int i;
  40.   vec3_t d1, d2, cross;
  41.   vec_t total = 0;
  42.  
  43.   for (i = 2; i < w->numpoints; i++) {
  44.     VectorSubtract(w->points[i - 1], w->points[0], d1);
  45.     VectorSubtract(w->points[i], w->points[0], d2);
  46.     CrossProduct(d1, d2, cross);
  47.     total += 0.5 * VectorLength(cross);
  48.   }
  49.   return total;
  50. }
  51.  
  52. /*
  53.  * =================
  54.  * BaseWindingForPlane
  55.  * =================
  56.  */
  57. struct winding *BaseWindingForPlane(register struct plane *p)
  58. {
  59.   int i, x;
  60.   vec_t max, v;
  61.   vec3_t org, vright, vup;
  62.   struct winding *w;
  63.  
  64.   /* find the major axis */
  65.   max = -BOGUS_RANGE;
  66.   x = -1;
  67.   for (i = 0; i < 3; i++) {
  68.     v = fabs(p->normal[i]);
  69.     if (v > max) {
  70.       x = i;
  71.       max = v;
  72.     }
  73.   }
  74.   if (x == -1)
  75.     Error("BaseWindingForPlane: no axis found");
  76.  
  77.   VectorClear(vup);
  78.   switch (x) {
  79.     case 0:
  80.     case 1:
  81.       vup[2] = 1;
  82.       break;
  83.     case 2:
  84.       vup[0] = 1;
  85.       break;
  86.   }
  87.  
  88.   v = DotProduct(vup, p->normal);
  89.   VectorMA(vup, -v, p->normal, vup);
  90.   VectorNormalize(vup);
  91.  
  92.   VectorScale(p->normal, p->dist, org);
  93.  
  94.   CrossProduct(vup, p->normal, vright);
  95.  
  96.   VectorScale(vup, 8192, vup);
  97.   VectorScale(vright, 8192, vright);
  98.  
  99.   /* project a really big axis aligned box onto the plane */
  100.   w = NewWinding(4);
  101.  
  102.   VectorSubtract(org, vright, w->points[0]);
  103.   VectorAdd(w->points[0], vup, w->points[0]);
  104.  
  105.   VectorAdd(org, vright, w->points[1]);
  106.   VectorAdd(w->points[1], vup, w->points[1]);
  107.  
  108.   VectorAdd(org, vright, w->points[2]);
  109.   VectorSubtract(w->points[2], vup, w->points[2]);
  110.  
  111.   VectorSubtract(org, vright, w->points[3]);
  112.   VectorSubtract(w->points[3], vup, w->points[3]);
  113.  
  114.   w->numpoints = 4;
  115.  
  116.   return w;
  117. }
  118.  
  119. /*
  120.  * =============
  121.  * WindingFromFace
  122.  * =============
  123.  */
  124. struct winding *WindingFromFace(__memBase, register struct dface_t *f)
  125. {
  126.   int se;
  127.   struct dvertex_t *dv;
  128.   int v;
  129.   struct winding *w;
  130.   int i, j, k;
  131.   vec3_t v1, v2;
  132.   int nump;
  133.   vec3_t p[MAX_POINTS_ON_WINDING];
  134.  
  135.   w = NewWinding(f->numedges);
  136.   w->numpoints = f->numedges;
  137.  
  138.   for (i = 0; i < f->numedges; i++) {
  139.     se = bspMem->shared.quake1.dsurfedges[f->firstedge + i];
  140.     if (se < 0)
  141.       v = bspMem->shared.quake1.dedges[-se].v[1];
  142.     else
  143.       v = bspMem->shared.quake1.dedges[se].v[0];
  144.  
  145.     dv = &bspMem->shared.quake1.dvertexes[v];
  146.     VectorCopy(dv->point, w->points[i]);
  147.   }
  148.  
  149.   nump = 0;
  150.   for (i = 0; i < w->numpoints; i++) {
  151.     j = (i + 1) % w->numpoints;
  152.     k = (i + w->numpoints - 1) % w->numpoints;
  153.     VectorSubtract(w->points[j], w->points[i], v1);
  154.     VectorSubtract(w->points[i], w->points[k], v2);
  155.     VectorNormalize(v1);
  156.     VectorNormalize(v2);
  157.     if (DotProduct(v1, v2) < 0.999) {
  158.       VectorCopy(w->points[i], p[nump]);
  159.       nump++;
  160.     }
  161.   }
  162.  
  163.   if (nump != w->numpoints) {
  164.     w->numpoints = nump;
  165.     __memcpy(w->points, p, nump * sizeof(vec3_t));
  166.   }
  167.   return w;
  168. }
  169.  
  170. /*
  171.  * ==================
  172.  * CopyWinding
  173.  * ==================
  174.  */
  175. struct winding *CopyWinding(register struct winding *w)
  176. {
  177.   int size;
  178.   struct winding *c;
  179.  
  180.   /*size = (int)((struct winding *)0)->points[w->numpoints];            hell, bloody shit */
  181.   size = (w->numpoints * sizeof(vec3_t)) + sizeof(bool) + sizeof(int);
  182.  
  183.   if (!(c = (struct winding *)tmalloc(size)))
  184.     Error(failed_memoryunsize, "winding");
  185.   __memcpy(c, w, size);
  186.   c->original = FALSE;
  187.   return c;
  188. }
  189.  
  190. /*
  191.  * ==================
  192.  * CheckWinding
  193.  * 
  194.  * Check for possible errors
  195.  * ==================
  196.  */
  197. void CheckWinding(register struct winding *w)
  198. {
  199. }
  200.  
  201. void CheckWindingInNode(register struct winding *w, register struct node *node)
  202. {
  203.   int i, j;
  204.  
  205.   for (i = 0; i < w->numpoints; i++) {
  206.     for (j = 0; j < 3; j++)
  207.       if (w->points[i][j] < node->mins[j] - 1
  208.       || w->points[i][j] > node->maxs[j] + 1) {
  209.     eprintf("CheckWindingInNode: outside\n");
  210.     return;
  211.       }
  212.   }
  213. }
  214.  
  215. void CheckWindingArea(register struct winding *w)
  216. {
  217.   int i;
  218.   float total, add;
  219.   vec3_t v1, v2, cross;
  220.  
  221.   total = 0;
  222.   for (i = 1; i < w->numpoints; i++) {
  223.     VectorSubtract(w->points[i], w->points[0], v1);
  224.     VectorSubtract(w->points[i + 1], w->points[0], v2);
  225.     CrossProduct(v1, v2, cross);
  226.     add = VectorLength(cross);
  227.     total += add * 0.5;
  228.   }
  229.   if (total < 16)
  230.     eprintf("winding area %f\n", total);
  231. }
  232.  
  233. void PlaneFromWinding(register struct winding *w, register struct plane *plane)
  234. {
  235.   vec3_t v1, v2;
  236.  
  237.   /* calc plane */
  238.   VectorSubtract(w->points[2], w->points[1], v1);
  239.   VectorSubtract(w->points[0], w->points[1], v2);
  240.   CrossProduct(v2, v1, plane->normal);
  241.   VectorNormalize(plane->normal);
  242.   plane->dist = DotProduct(w->points[0], plane->normal);
  243. }
  244.  
  245. /*
  246.  * ==================
  247.  * ClipWinding
  248.  * 
  249.  * Clips the winding to the plane, returning the new winding on the positive side
  250.  * Frees the input winding.
  251.  * If keepon is TRUE, an exactly on-plane winding will be saved, otherwise
  252.  * it will be clipped away.
  253.  * ==================
  254.  */
  255. struct winding *ClipWinding(register struct winding *in, register struct plane *split, register bool keepon)
  256. {
  257.   vec_t dists[MAX_POINTS_ON_WINDING];
  258.   int sides[MAX_POINTS_ON_WINDING];
  259.   int counts[3];
  260.   vec_t dot;
  261.   int i, j;
  262.   vec_t *p1, *p2;
  263.   vec3_t mid;
  264.   struct winding *neww;
  265.   int maxpts;
  266.  
  267.   counts[0] = counts[1] = counts[2] = 0;
  268.  
  269.   /* determine sides for each point */
  270.   for (i = 0; i < in->numpoints; i++) {
  271.     dot = DotProduct(in->points[i], split->normal);
  272.     dot -= split->dist;
  273.     dists[i] = dot;
  274.     if (dot > ON_EPSILON)
  275.       sides[i] = SIDE_FRONT;
  276.     else if (dot < -ON_EPSILON)
  277.       sides[i] = SIDE_BACK;
  278.     else {
  279.       sides[i] = SIDE_ON;
  280.     }
  281.     counts[sides[i]]++;
  282.   }
  283.   sides[i] = sides[0];
  284.   dists[i] = dists[0];
  285.  
  286. /*
  287.  * printf("counts[0]: %d\n", counts[0]);
  288.  * printf("counts[1]: %d\n", counts[1]);
  289.  */
  290.  
  291.   if (keepon && !counts[0] && !counts[1])
  292.     return in;
  293.  
  294.   if (!counts[0]) {
  295.     FreeWinding(in);
  296.     return NULL;
  297.   }
  298.   if (!counts[1])
  299.     return in;
  300.  
  301.   maxpts = in->numpoints + 4;                    /* can't use counts[0]+2 because */
  302.   /* of fp grouping errors */
  303.  
  304.   neww = NewWinding(maxpts);
  305.  
  306.   for (i = 0; i < in->numpoints; i++) {
  307.     p1 = in->points[i];
  308.  
  309.     if (sides[i] == SIDE_ON) {
  310.       VectorCopy(p1, neww->points[neww->numpoints]);
  311.       neww->numpoints++;
  312.       continue;
  313.     }
  314.  
  315.     if (sides[i] == SIDE_FRONT) {
  316.       VectorCopy(p1, neww->points[neww->numpoints]);
  317.       neww->numpoints++;
  318.     }
  319.  
  320.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  321.       continue;
  322.  
  323.     /* generate a split point */
  324.     p2 = in->points[(i + 1) % in->numpoints];
  325.  
  326.     dot = dists[i] / (dists[i] - dists[i + 1]);
  327.     for (j = 0; j < 3; j++) {                    /* avoid round off error when possible */
  328.  
  329.       if (split->normal[j] == 1)
  330.     mid[j] = split->dist;
  331.       else if (split->normal[j] == -1)
  332.     mid[j] = -split->dist;
  333.       else
  334.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  335.     }
  336.  
  337.     VectorCopy(mid, neww->points[neww->numpoints]);
  338.     neww->numpoints++;
  339.   }
  340.  
  341.   if (neww->numpoints > maxpts)
  342.     Error("ClipWinding: points exceeded estimate");
  343.  
  344.   /* free the original winding */
  345.   FreeWinding(in);
  346.  
  347.   return neww;
  348. }
  349.  
  350. void ClipWindingEpsilon(struct winding *in, vec3_t normal, vec_t dist,
  351.          vec_t epsilon, struct winding **front, struct winding **back)
  352. {
  353.   vec_t dists[MAX_POINTS_ON_WINDING + 4];
  354.   int sides[MAX_POINTS_ON_WINDING + 4];
  355.   int counts[3];
  356.   vec_t dot;
  357.   int i, j;
  358.   vec_t *p1, *p2;
  359.   vec3_t mid;
  360.   struct winding *f, *b;
  361.   int maxpts;
  362.  
  363.   counts[0] = counts[1] = counts[2] = 0;
  364.  
  365.   /* determine sides for each point */
  366.   for (i = 0; i < in->numpoints; i++) {
  367.     dot = DotProduct(in->points[i], normal);
  368.     dot -= dist;
  369.     dists[i] = dot;
  370.     if (dot > epsilon)
  371.       sides[i] = SIDE_FRONT;
  372.     else if (dot < -epsilon)
  373.       sides[i] = SIDE_BACK;
  374.     else {
  375.       sides[i] = SIDE_ON;
  376.     }
  377.     counts[sides[i]]++;
  378.   }
  379.   sides[i] = sides[0];
  380.   dists[i] = dists[0];
  381.  
  382.   *front = *back = NULL;
  383.  
  384.   if (!counts[0]) {
  385.     *back = CopyWinding(in);
  386.     return;
  387.   }
  388.   if (!counts[1]) {
  389.     *front = CopyWinding(in);
  390.     return;
  391.   }
  392.  
  393.   maxpts = in->numpoints + 4;                    /* cant use counts[0]+2 because */
  394.   /* of fp grouping errors */
  395.  
  396.   *front = f = NewWinding(maxpts);
  397.   *back = b = NewWinding(maxpts);
  398.  
  399.   for (i = 0; i < in->numpoints; i++) {
  400.     p1 = in->points[i];
  401.  
  402.     if (sides[i] == SIDE_ON) {
  403.       VectorCopy(p1, f->points[f->numpoints]);
  404.       f->numpoints++;
  405.       VectorCopy(p1, b->points[b->numpoints]);
  406.       b->numpoints++;
  407.       continue;
  408.     }
  409.  
  410.     if (sides[i] == SIDE_FRONT) {
  411.       VectorCopy(p1, f->points[f->numpoints]);
  412.       f->numpoints++;
  413.     }
  414.     if (sides[i] == SIDE_BACK) {
  415.       VectorCopy(p1, b->points[b->numpoints]);
  416.       b->numpoints++;
  417.     }
  418.  
  419.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  420.       continue;
  421.  
  422.     /* generate a split point */
  423.     p2 = in->points[(i + 1) % in->numpoints];
  424.  
  425.     dot = dists[i] / (dists[i] - dists[i + 1]);
  426.     for (j = 0; j < 3; j++) {                    /* avoid round off error when possible */
  427.  
  428.       if (normal[j] == 1)
  429.     mid[j] = dist;
  430.       else if (normal[j] == -1)
  431.     mid[j] = -dist;
  432.       else
  433.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  434.     }
  435.  
  436.     VectorCopy(mid, f->points[f->numpoints]);
  437.     f->numpoints++;
  438.     VectorCopy(mid, b->points[b->numpoints]);
  439.     b->numpoints++;
  440.   }
  441.  
  442.   if (f->numpoints > maxpts || b->numpoints > maxpts)
  443.     Error("ClipWinding: points exceeded estimate");
  444.   if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  445.     Error("ClipWinding: MAX_POINTS_ON_WINDING");
  446. }
  447. /*
  448.  * ==================
  449.  * DivideWinding
  450.  * 
  451.  * Divides a winding by a plane, producing one or two windings.  The
  452.  * original winding is not damaged or freed.  If only on one side, the
  453.  * returned winding will be the input winding.  If on both sides, two
  454.  * new windings will be created.
  455.  * ==================
  456.  */
  457. void DivideWinding(struct winding *in, struct plane *split, struct winding **front, struct winding **back)
  458. {
  459.   vec_t dists[MAX_POINTS_ON_WINDING];
  460.   int sides[MAX_POINTS_ON_WINDING];
  461.   int counts[3];
  462.   vec_t dot;
  463.   int i, j;
  464.   vec_t *p1, *p2;
  465.   vec3_t mid;
  466.   struct winding *f, *b;
  467.   int maxpts;
  468.  
  469.   counts[0] = counts[1] = counts[2] = 0;
  470.  
  471.   /* determine sides for each point */
  472.   for (i = 0; i < in->numpoints; i++) {
  473.     dot = DotProduct(in->points[i], split->normal);
  474.     dot -= split->dist;
  475.     dists[i] = dot;
  476.     if (dot > ON_EPSILON)
  477.       sides[i] = SIDE_FRONT;
  478.     else if (dot < -ON_EPSILON)
  479.       sides[i] = SIDE_BACK;
  480.     else {
  481.       sides[i] = SIDE_ON;
  482.     }
  483.     counts[sides[i]]++;
  484.   }
  485.   sides[i] = sides[0];
  486.   dists[i] = dists[0];
  487.  
  488.   *front = *back = NULL;
  489.  
  490.   if (!counts[0]) {
  491.     *back = in;
  492.     return;
  493.   }
  494.   if (!counts[1]) {
  495.     *front = in;
  496.     return;
  497.   }
  498.  
  499.   maxpts = in->numpoints + 4;                    /* can't use counts[0]+2 because */
  500.   /* of fp grouping errors */
  501.  
  502.   *front = f = NewWinding(maxpts);
  503.   *back = b = NewWinding(maxpts);
  504.  
  505.   for (i = 0; i < in->numpoints; i++) {
  506.     p1 = in->points[i];
  507.  
  508.     if (sides[i] == SIDE_ON) {
  509.       VectorCopy(p1, f->points[f->numpoints]);
  510.       f->numpoints++;
  511.       VectorCopy(p1, b->points[b->numpoints]);
  512.       b->numpoints++;
  513.       continue;
  514.     }
  515.  
  516.     if (sides[i] == SIDE_FRONT) {
  517.       VectorCopy(p1, f->points[f->numpoints]);
  518.       f->numpoints++;
  519.     }
  520.     if (sides[i] == SIDE_BACK) {
  521.       VectorCopy(p1, b->points[b->numpoints]);
  522.       b->numpoints++;
  523.     }
  524.  
  525.     if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
  526.       continue;
  527.  
  528.     /* generate a split point */
  529.     p2 = in->points[(i + 1) % in->numpoints];
  530.  
  531.     dot = dists[i] / (dists[i] - dists[i + 1]);
  532.     for (j = 0; j < 3; j++) {                    /* avoid round off error when possible */
  533.  
  534.       if (split->normal[j] == 1)
  535.     mid[j] = split->dist;
  536.       else if (split->normal[j] == -1)
  537.     mid[j] = -split->dist;
  538.       else
  539.     mid[j] = p1[j] + dot * (p2[j] - p1[j]);
  540.     }
  541.  
  542.     VectorCopy(mid, f->points[f->numpoints]);
  543.     f->numpoints++;
  544.     VectorCopy(mid, b->points[b->numpoints]);
  545.     b->numpoints++;
  546.   }
  547.  
  548.   if (f->numpoints > maxpts || b->numpoints > maxpts)
  549.     Error("ClipWinding: points exceeded estimate");
  550. }
  551.  
  552. /*
  553.  * ==================
  554.  * NewWinding
  555.  * ==================
  556.  */
  557. struct winding *NewWinding(register int points)
  558. {
  559.   struct winding *w;
  560.   int size;
  561.  
  562.   if (points > MAX_POINTS_ON_WINDING)
  563.     Error("NewWinding: %i points", points);
  564.  
  565.   c_activewindings++;
  566.   if (c_activewindings > c_peakwindings)
  567.     c_peakwindings = c_activewindings;
  568.  
  569.   /*size = (int)((struct winding *)0)->points[points];          hell, bloody shit! */
  570.   size = (points * sizeof(vec3_t)) + sizeof(bool) + sizeof(int);
  571.  
  572.   if (!(w = (struct winding *)tmalloc(size)))
  573.     Error(failed_memoryunsize, "winding");
  574.   bzero(w, size);
  575.  
  576.   return w;
  577. }
  578.  
  579. void FreeWinding(register struct winding *w)
  580. {
  581.   c_activewindings--;
  582.   if (!w->original)
  583.     tfree(w);
  584. }
  585.