home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / common / polylib.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-18  |  11.5 KB  |  622 lines
  1.  
  2. #include "cmdlib.h"
  3. #include "mathlib.h"
  4. #include "polylib.h"
  5.  
  6.  
  7. extern int numthreads;
  8.  
  9. // counters are only bumped when running single threaded,
  10. // because they are an awefull coherence problem
  11. int    c_active_windings;
  12. int    c_peak_windings;
  13. int    c_winding_allocs;
  14. int    c_winding_points;
  15.  
  16. #define    BOGUS_RANGE    8192
  17.  
  18. void pw(winding_t *w)
  19. {
  20.     int        i;
  21.     for (i=0 ; i<w->numpoints ; i++)
  22.         printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
  23. }
  24.  
  25.  
  26. /*
  27. =============
  28. AllocWinding
  29. =============
  30. */
  31. winding_t    *AllocWinding (int points)
  32. {
  33.     winding_t    *w;
  34.     int            s;
  35.  
  36.     if (numthreads == 1)
  37.     {
  38.         c_winding_allocs++;
  39.         c_winding_points += points;
  40.         c_active_windings++;
  41.         if (c_active_windings > c_peak_windings)
  42.             c_peak_windings = c_active_windings;
  43.     }
  44.     s = sizeof(vec_t)*3*points + sizeof(int);
  45.     w = malloc (s);
  46.     memset (w, 0, s); 
  47.     return w;
  48. }
  49.  
  50. void FreeWinding (winding_t *w)
  51. {
  52.     if (*(unsigned *)w == 0xdeaddead)
  53.         Error ("FreeWinding: freed a freed winding");
  54.     *(unsigned *)w = 0xdeaddead;
  55.  
  56.     if (numthreads == 1)
  57.         c_active_windings--;
  58.     free (w);
  59. }
  60.  
  61. /*
  62. ============
  63. RemoveColinearPoints
  64. ============
  65. */
  66. int    c_removed;
  67.  
  68. void    RemoveColinearPoints (winding_t *w)
  69. {
  70.     int        i, j, k;
  71.     vec3_t    v1, v2;
  72.     int        nump;
  73.     vec3_t    p[MAX_POINTS_ON_WINDING];
  74.  
  75.     nump = 0;
  76.     for (i=0 ; i<w->numpoints ; i++)
  77.     {
  78.         j = (i+1)%w->numpoints;
  79.         k = (i+w->numpoints-1)%w->numpoints;
  80.         VectorSubtract (w->p[j], w->p[i], v1);
  81.         VectorSubtract (w->p[i], w->p[k], v2);
  82.         VectorNormalize(v1,v1);
  83.         VectorNormalize(v2,v2);
  84.         if (DotProduct(v1, v2) < 0.999)
  85.         {
  86.             VectorCopy (w->p[i], p[nump]);
  87.             nump++;
  88.         }
  89.     }
  90.  
  91.     if (nump == w->numpoints)
  92.         return;
  93.  
  94.     if (numthreads == 1)
  95.         c_removed += w->numpoints - nump;
  96.     w->numpoints = nump;
  97.     memcpy (w->p, p, nump*sizeof(p[0]));
  98. }
  99.  
  100. /*
  101. ============
  102. WindingPlane
  103. ============
  104. */
  105. void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
  106. {
  107.     vec3_t    v1, v2;
  108.  
  109.     VectorSubtract (w->p[1], w->p[0], v1);
  110.     VectorSubtract (w->p[2], w->p[0], v2);
  111.     CrossProduct (v2, v1, normal);
  112.     VectorNormalize (normal, normal);
  113.     *dist = DotProduct (w->p[0], normal);
  114.  
  115. }
  116.  
  117. /*
  118. =============
  119. WindingArea
  120. =============
  121. */
  122. vec_t    WindingArea (winding_t *w)
  123. {
  124.     int        i;
  125.     vec3_t    d1, d2, cross;
  126.     vec_t    total;
  127.  
  128.     total = 0;
  129.     for (i=2 ; i<w->numpoints ; i++)
  130.     {
  131.         VectorSubtract (w->p[i-1], w->p[0], d1);
  132.         VectorSubtract (w->p[i], w->p[0], d2);
  133.         CrossProduct (d1, d2, cross);
  134.         total += 0.5 * VectorLength ( cross );
  135.     }
  136.     return total;
  137. }
  138.  
  139. void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
  140. {
  141.     vec_t    v;
  142.     int        i,j;
  143.  
  144.     mins[0] = mins[1] = mins[2] = 99999;
  145.     maxs[0] = maxs[1] = maxs[2] = -99999;
  146.  
  147.     for (i=0 ; i<w->numpoints ; i++)
  148.     {
  149.         for (j=0 ; j<3 ; j++)
  150.         {
  151.             v = w->p[i][j];
  152.             if (v < mins[j])
  153.                 mins[j] = v;
  154.             if (v > maxs[j])
  155.                 maxs[j] = v;
  156.         }
  157.     }
  158. }
  159.  
  160. /*
  161. =============
  162. WindingCenter
  163. =============
  164. */
  165. void    WindingCenter (winding_t *w, vec3_t center)
  166. {
  167.     int        i;
  168.     float    scale;
  169.  
  170.     VectorCopy (vec3_origin, center);
  171.     for (i=0 ; i<w->numpoints ; i++)
  172.         VectorAdd (w->p[i], center, center);
  173.  
  174.     scale = 1.0/w->numpoints;
  175.     VectorScale (center, scale, center);
  176. }
  177.  
  178. /*
  179. =================
  180. BaseWindingForPlane
  181. =================
  182. */
  183. winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
  184. {
  185.     int        i, x;
  186.     vec_t    max, v;
  187.     vec3_t    org, vright, vup;
  188.     winding_t    *w;
  189.     
  190. // find the major axis
  191.  
  192.     max = -BOGUS_RANGE;
  193.     x = -1;
  194.     for (i=0 ; i<3; i++)
  195.     {
  196.         v = fabs(normal[i]);
  197.         if (v > max)
  198.         {
  199.             x = i;
  200.             max = v;
  201.         }
  202.     }
  203.     if (x==-1)
  204.         Error ("BaseWindingForPlane: no axis found");
  205.         
  206.     VectorCopy (vec3_origin, vup);    
  207.     switch (x)
  208.     {
  209.     case 0:
  210.     case 1:
  211.         vup[2] = 1;
  212.         break;        
  213.     case 2:
  214.         vup[0] = 1;
  215.         break;        
  216.     }
  217.  
  218.     v = DotProduct (vup, normal);
  219.     VectorMA (vup, -v, normal, vup);
  220.     VectorNormalize (vup, vup);
  221.         
  222.     VectorScale (normal, dist, org);
  223.     
  224.     CrossProduct (vup, normal, vright);
  225.     
  226.     VectorScale (vup, 8192, vup);
  227.     VectorScale (vright, 8192, vright);
  228.  
  229. // project a really big    axis aligned box onto the plane
  230.     w = AllocWinding (4);
  231.     
  232.     VectorSubtract (org, vright, w->p[0]);
  233.     VectorAdd (w->p[0], vup, w->p[0]);
  234.     
  235.     VectorAdd (org, vright, w->p[1]);
  236.     VectorAdd (w->p[1], vup, w->p[1]);
  237.     
  238.     VectorAdd (org, vright, w->p[2]);
  239.     VectorSubtract (w->p[2], vup, w->p[2]);
  240.     
  241.     VectorSubtract (org, vright, w->p[3]);
  242.     VectorSubtract (w->p[3], vup, w->p[3]);
  243.     
  244.     w->numpoints = 4;
  245.     
  246.     return w;    
  247. }
  248.  
  249. /*
  250. ==================
  251. CopyWinding
  252. ==================
  253. */
  254. winding_t    *CopyWinding (winding_t *w)
  255. {
  256.     int            size;
  257.     winding_t    *c;
  258.  
  259.     c = AllocWinding (w->numpoints);
  260.     size = (int)((winding_t *)0)->p[w->numpoints];
  261.     memcpy (c, w, size);
  262.     return c;
  263. }
  264.  
  265. /*
  266. ==================
  267. ReverseWinding
  268. ==================
  269. */
  270. winding_t    *ReverseWinding (winding_t *w)
  271. {
  272.     int            i;
  273.     winding_t    *c;
  274.  
  275.     c = AllocWinding (w->numpoints);
  276.     for (i=0 ; i<w->numpoints ; i++)
  277.     {
  278.         VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
  279.     }
  280.     c->numpoints = w->numpoints;
  281.     return c;
  282. }
  283.  
  284.  
  285. /*
  286. =============
  287. ClipWindingEpsilon
  288. =============
  289. */
  290. void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 
  291.                 vec_t epsilon, winding_t **front, winding_t **back)
  292. {
  293.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  294.     int        sides[MAX_POINTS_ON_WINDING+4];
  295.     int        counts[3];
  296.     static    vec_t    dot;        // VC 4.2 optimizer bug if not static
  297.     int        i, j;
  298.     vec_t    *p1, *p2;
  299.     vec3_t    mid;
  300.     winding_t    *f, *b;
  301.     int        maxpts;
  302.     
  303.     counts[0] = counts[1] = counts[2] = 0;
  304.  
  305. // determine sides for each point
  306.     for (i=0 ; i<in->numpoints ; i++)
  307.     {
  308.         dot = DotProduct (in->p[i], normal);
  309.         dot -= dist;
  310.         dists[i] = dot;
  311.         if (dot > epsilon)
  312.             sides[i] = SIDE_FRONT;
  313.         else if (dot < -epsilon)
  314.             sides[i] = SIDE_BACK;
  315.         else
  316.         {
  317.             sides[i] = SIDE_ON;
  318.         }
  319.         counts[sides[i]]++;
  320.     }
  321.     sides[i] = sides[0];
  322.     dists[i] = dists[0];
  323.     
  324.     *front = *back = NULL;
  325.  
  326.     if (!counts[0])
  327.     {
  328.         *back = CopyWinding (in);
  329.         return;
  330.     }
  331.     if (!counts[1])
  332.     {
  333.         *front = CopyWinding (in);
  334.         return;
  335.     }
  336.  
  337.     maxpts = in->numpoints+4;    // cant use counts[0]+2 because
  338.                                 // of fp grouping errors
  339.  
  340.     *front = f = AllocWinding (maxpts);
  341.     *back = b = AllocWinding (maxpts);
  342.         
  343.     for (i=0 ; i<in->numpoints ; i++)
  344.     {
  345.         p1 = in->p[i];
  346.         
  347.         if (sides[i] == SIDE_ON)
  348.         {
  349.             VectorCopy (p1, f->p[f->numpoints]);
  350.             f->numpoints++;
  351.             VectorCopy (p1, b->p[b->numpoints]);
  352.             b->numpoints++;
  353.             continue;
  354.         }
  355.     
  356.         if (sides[i] == SIDE_FRONT)
  357.         {
  358.             VectorCopy (p1, f->p[f->numpoints]);
  359.             f->numpoints++;
  360.         }
  361.         if (sides[i] == SIDE_BACK)
  362.         {
  363.             VectorCopy (p1, b->p[b->numpoints]);
  364.             b->numpoints++;
  365.         }
  366.  
  367.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  368.             continue;
  369.             
  370.     // generate a split point
  371.         p2 = in->p[(i+1)%in->numpoints];
  372.         
  373.         dot = dists[i] / (dists[i]-dists[i+1]);
  374.         for (j=0 ; j<3 ; j++)
  375.         {    // avoid round off error when possible
  376.             if (normal[j] == 1)
  377.                 mid[j] = dist;
  378.             else if (normal[j] == -1)
  379.                 mid[j] = -dist;
  380.             else
  381.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  382.         }
  383.             
  384.         VectorCopy (mid, f->p[f->numpoints]);
  385.         f->numpoints++;
  386.         VectorCopy (mid, b->p[b->numpoints]);
  387.         b->numpoints++;
  388.     }
  389.     
  390.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  391.         Error ("ClipWinding: points exceeded estimate");
  392.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  393.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  394. }
  395.  
  396.  
  397. /*
  398. =============
  399. ChopWindingInPlace
  400. =============
  401. */
  402. void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
  403. {
  404.     winding_t    *in;
  405.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  406.     int        sides[MAX_POINTS_ON_WINDING+4];
  407.     int        counts[3];
  408.     static    vec_t    dot;        // VC 4.2 optimizer bug if not static
  409.     int        i, j;
  410.     vec_t    *p1, *p2;
  411.     vec3_t    mid;
  412.     winding_t    *f;
  413.     int        maxpts;
  414.  
  415.     in = *inout;
  416.     counts[0] = counts[1] = counts[2] = 0;
  417.  
  418. // determine sides for each point
  419.     for (i=0 ; i<in->numpoints ; i++)
  420.     {
  421.         dot = DotProduct (in->p[i], normal);
  422.         dot -= dist;
  423.         dists[i] = dot;
  424.         if (dot > epsilon)
  425.             sides[i] = SIDE_FRONT;
  426.         else if (dot < -epsilon)
  427.             sides[i] = SIDE_BACK;
  428.         else
  429.         {
  430.             sides[i] = SIDE_ON;
  431.         }
  432.         counts[sides[i]]++;
  433.     }
  434.     sides[i] = sides[0];
  435.     dists[i] = dists[0];
  436.     
  437.     if (!counts[0])
  438.     {
  439.         FreeWinding (in);
  440.         *inout = NULL;
  441.         return;
  442.     }
  443.     if (!counts[1])
  444.         return;        // inout stays the same
  445.  
  446.     maxpts = in->numpoints+4;    // cant use counts[0]+2 because
  447.                                 // of fp grouping errors
  448.  
  449.     f = AllocWinding (maxpts);
  450.         
  451.     for (i=0 ; i<in->numpoints ; i++)
  452.     {
  453.         p1 = in->p[i];
  454.         
  455.         if (sides[i] == SIDE_ON)
  456.         {
  457.             VectorCopy (p1, f->p[f->numpoints]);
  458.             f->numpoints++;
  459.             continue;
  460.         }
  461.     
  462.         if (sides[i] == SIDE_FRONT)
  463.         {
  464.             VectorCopy (p1, f->p[f->numpoints]);
  465.             f->numpoints++;
  466.         }
  467.  
  468.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  469.             continue;
  470.             
  471.     // generate a split point
  472.         p2 = in->p[(i+1)%in->numpoints];
  473.         
  474.         dot = dists[i] / (dists[i]-dists[i+1]);
  475.         for (j=0 ; j<3 ; j++)
  476.         {    // avoid round off error when possible
  477.             if (normal[j] == 1)
  478.                 mid[j] = dist;
  479.             else if (normal[j] == -1)
  480.                 mid[j] = -dist;
  481.             else
  482.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  483.         }
  484.             
  485.         VectorCopy (mid, f->p[f->numpoints]);
  486.         f->numpoints++;
  487.     }
  488.     
  489.     if (f->numpoints > maxpts)
  490.         Error ("ClipWinding: points exceeded estimate");
  491.     if (f->numpoints > MAX_POINTS_ON_WINDING)
  492.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  493.  
  494.     FreeWinding (in);
  495.     *inout = f;
  496. }
  497.  
  498.  
  499. /*
  500. =================
  501. ChopWinding
  502.  
  503. Returns the fragment of in that is on the front side
  504. of the cliping plane.  The original is freed.
  505. =================
  506. */
  507. winding_t    *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
  508. {
  509.     winding_t    *f, *b;
  510.  
  511.     ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
  512.     FreeWinding (in);
  513.     if (b)
  514.         FreeWinding (b);
  515.     return f;
  516. }
  517.  
  518.  
  519. /*
  520. =================
  521. CheckWinding
  522.  
  523. =================
  524. */
  525. void CheckWinding (winding_t *w)
  526. {
  527.     int        i, j;
  528.     vec_t    *p1, *p2;
  529.     vec_t    d, edgedist;
  530.     vec3_t    dir, edgenormal, facenormal;
  531.     vec_t    area;
  532.     vec_t    facedist;
  533.  
  534.     if (w->numpoints < 3)
  535.         Error ("CheckWinding: %i points",w->numpoints);
  536.     
  537.     area = WindingArea(w);
  538.     if (area < 1)
  539.         Error ("CheckWinding: %f area", area);
  540.  
  541.     WindingPlane (w, facenormal, &facedist);
  542.     
  543.     for (i=0 ; i<w->numpoints ; i++)
  544.     {
  545.         p1 = w->p[i];
  546.  
  547.         for (j=0 ; j<3 ; j++)
  548.             if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
  549.                 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
  550.  
  551.         j = i+1 == w->numpoints ? 0 : i+1;
  552.         
  553.     // check the point is on the face plane
  554.         d = DotProduct (p1, facenormal) - facedist;
  555.         if (d < -ON_EPSILON || d > ON_EPSILON)
  556.             Error ("CheckWinding: point off plane");
  557.     
  558.     // check the edge isnt degenerate
  559.         p2 = w->p[j];
  560.         VectorSubtract (p2, p1, dir);
  561.         
  562.         if (VectorLength (dir) < ON_EPSILON)
  563.             Error ("CheckWinding: degenerate edge");
  564.             
  565.         CrossProduct (facenormal, dir, edgenormal);
  566.         VectorNormalize (edgenormal, edgenormal);
  567.         edgedist = DotProduct (p1, edgenormal);
  568.         edgedist += ON_EPSILON;
  569.         
  570.     // all other points must be on front side
  571.         for (j=0 ; j<w->numpoints ; j++)
  572.         {
  573.             if (j == i)
  574.                 continue;
  575.             d = DotProduct (w->p[j], edgenormal);
  576.             if (d > edgedist)
  577.                 Error ("CheckWinding: non-convex");
  578.         }
  579.     }
  580. }
  581.  
  582.  
  583. /*
  584. ============
  585. WindingOnPlaneSide
  586. ============
  587. */
  588. int        WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
  589. {
  590.     qboolean    front, back;
  591.     int            i;
  592.     vec_t        d;
  593.  
  594.     front = false;
  595.     back = false;
  596.     for (i=0 ; i<w->numpoints ; i++)
  597.     {
  598.         d = DotProduct (w->p[i], normal) - dist;
  599.         if (d < -ON_EPSILON)
  600.         {
  601.             if (front)
  602.                 return SIDE_CROSS;
  603.             back = true;
  604.             continue;
  605.         }
  606.         if (d > ON_EPSILON)
  607.         {
  608.             if (back)
  609.                 return SIDE_CROSS;
  610.             front = true;
  611.             continue;
  612.         }
  613.     }
  614.  
  615.     if (back)
  616.         return SIDE_BACK;
  617.     if (front)
  618.         return SIDE_FRONT;
  619.     return SIDE_ON;
  620. }
  621.  
  622.