home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / common / polylib.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-12  |  7.2 KB  |  401 lines
  1.  
  2. #include "cmdlib.h"
  3. #include "mathlib.h"
  4. #include "polylib.h"
  5.  
  6. #define    BOGUS_RANGE    8192
  7.  
  8. /*
  9. =============
  10. AllocWinding
  11. =============
  12. */
  13. winding_t    *AllocWinding (int points)
  14. {
  15.     winding_t    *w;
  16.     int            s;
  17.  
  18.     s = sizeof(vec_t)*3*points + sizeof(int);
  19.     w = malloc (s);
  20.     memset (w, 0, s); 
  21.     return w;
  22. }
  23.  
  24. /*
  25. ============
  26. RemoveColinearPoints
  27. ============
  28. */
  29. int    c_removed;
  30.  
  31. void    RemoveColinearPoints (winding_t *w)
  32. {
  33.     int        i, j, k;
  34.     vec3_t    v1, v2;
  35.     int        nump;
  36.     vec3_t    p[MAX_POINTS_ON_WINDING];
  37.  
  38.     nump = 0;
  39.     for (i=0 ; i<w->numpoints ; i++)
  40.     {
  41.         j = (i+1)%w->numpoints;
  42.         k = (i+w->numpoints-1)%w->numpoints;
  43.         VectorSubtract (w->p[j], w->p[i], v1);
  44.         VectorSubtract (w->p[i], w->p[k], v2);
  45.         VectorNormalize(v1);
  46.         VectorNormalize(v2);
  47.         if (DotProduct(v1, v2) < 0.999)
  48.         {
  49.             VectorCopy (w->p[i], p[nump]);
  50.             nump++;
  51.         }
  52.     }
  53.  
  54.     if (nump == w->numpoints)
  55.         return;
  56.  
  57.     c_removed += w->numpoints - nump;
  58.     w->numpoints = nump;
  59.     memcpy (w->p, p, nump*sizeof(p[0]));
  60. }
  61.  
  62. /*
  63. ============
  64. WindingPlane
  65. ============
  66. */
  67. void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
  68. {
  69.     vec3_t    v1, v2;
  70.  
  71.     VectorSubtract (w->p[1], w->p[0], v1);
  72.     VectorSubtract (w->p[2], w->p[0], v2);
  73.     CrossProduct (v1, v2, normal);
  74.     VectorNormalize (normal);
  75.     *dist = DotProduct (w->p[0], normal);
  76.  
  77. }
  78.  
  79. /*
  80. =============
  81. WindingArea
  82. =============
  83. */
  84. vec_t    WindingArea (winding_t *w)
  85. {
  86.     int        i;
  87.     vec3_t    d1, d2, cross;
  88.     vec_t    total;
  89.  
  90.     total = 0;
  91.     for (i=2 ; i<w->numpoints ; i++)
  92.     {
  93.         VectorSubtract (w->p[i-1], w->p[0], d1);
  94.         VectorSubtract (w->p[i], w->p[0], d2);
  95.         CrossProduct (d1, d2, cross);
  96.         total += 0.5 * VectorLength ( cross );
  97.     }
  98.     return total;
  99. }
  100.  
  101. /*
  102. =============
  103. WindingCenter
  104. =============
  105. */
  106. void    WindingCenter (winding_t *w, vec3_t center)
  107. {
  108.     int        i;
  109.     vec3_t    d1, d2, cross;
  110.     float    scale;
  111.  
  112.     VectorCopy (vec3_origin, center);
  113.     for (i=0 ; i<w->numpoints ; i++)
  114.         VectorAdd (w->p[i], center, center);
  115.  
  116.     scale = 1.0/w->numpoints;
  117.     VectorScale (center, scale, center);
  118. }
  119.  
  120. /*
  121. =================
  122. BaseWindingForPlane
  123. =================
  124. */
  125. winding_t *BaseWindingForPlane (vec3_t normal, float dist)
  126. {
  127.     int        i, x;
  128.     vec_t    max, v;
  129.     vec3_t    org, vright, vup;
  130.     winding_t    *w;
  131.     
  132. // find the major axis
  133.  
  134.     max = -BOGUS_RANGE;
  135.     x = -1;
  136.     for (i=0 ; i<3; i++)
  137.     {
  138.         v = fabs(normal[i]);
  139.         if (v > max)
  140.         {
  141.             x = i;
  142.             max = v;
  143.         }
  144.     }
  145.     if (x==-1)
  146.         Error ("BaseWindingForPlane: no axis found");
  147.         
  148.     VectorCopy (vec3_origin, vup);    
  149.     switch (x)
  150.     {
  151.     case 0:
  152.     case 1:
  153.         vup[2] = 1;
  154.         break;        
  155.     case 2:
  156.         vup[0] = 1;
  157.         break;        
  158.     }
  159.  
  160.     v = DotProduct (vup, normal);
  161.     VectorMA (vup, -v, normal, vup);
  162.     VectorNormalize (vup);
  163.         
  164.     VectorScale (normal, dist, org);
  165.     
  166.     CrossProduct (vup, normal, vright);
  167.     
  168.     VectorScale (vup, 8192, vup);
  169.     VectorScale (vright, 8192, vright);
  170.  
  171. // project a really big    axis aligned box onto the plane
  172.     w = AllocWinding (4);
  173.     
  174.     VectorSubtract (org, vright, w->p[0]);
  175.     VectorAdd (w->p[0], vup, w->p[0]);
  176.     
  177.     VectorAdd (org, vright, w->p[1]);
  178.     VectorAdd (w->p[1], vup, w->p[1]);
  179.     
  180.     VectorAdd (org, vright, w->p[2]);
  181.     VectorSubtract (w->p[2], vup, w->p[2]);
  182.     
  183.     VectorSubtract (org, vright, w->p[3]);
  184.     VectorSubtract (w->p[3], vup, w->p[3]);
  185.     
  186.     w->numpoints = 4;
  187.     
  188.     return w;    
  189. }
  190.  
  191. /*
  192. ==================
  193. CopyWinding
  194. ==================
  195. */
  196. winding_t    *CopyWinding (winding_t *w)
  197. {
  198.     int            size;
  199.     winding_t    *c;
  200.     
  201.     size = (int)((winding_t *)0)->p[w->numpoints];
  202.     c = malloc (size);
  203.     memcpy (c, w, size);
  204.     return c;
  205. }
  206.  
  207.  
  208. /*
  209. =============
  210. ClipWinding
  211. =============
  212. */
  213. void    ClipWinding (winding_t *in, vec3_t normal, vec_t dist,
  214.                      winding_t **front, winding_t **back)
  215. {
  216.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  217.     int        sides[MAX_POINTS_ON_WINDING+4];
  218.     int        counts[3];
  219.     vec_t    dot;
  220.     int        i, j;
  221.     vec_t    *p1, *p2;
  222.     vec3_t    mid;
  223.     winding_t    *f, *b;
  224.     int        maxpts;
  225.     
  226.     counts[0] = counts[1] = counts[2] = 0;
  227.  
  228. // determine sides for each point
  229.     for (i=0 ; i<in->numpoints ; i++)
  230.     {
  231.         dot = DotProduct (in->p[i], normal);
  232.         dot -= dist;
  233.         dists[i] = dot;
  234.         if (dot > ON_EPSILON)
  235.             sides[i] = SIDE_FRONT;
  236.         else if (dot < -ON_EPSILON)
  237.             sides[i] = SIDE_BACK;
  238.         else
  239.         {
  240.             sides[i] = SIDE_ON;
  241.         }
  242.         counts[sides[i]]++;
  243.     }
  244.     sides[i] = sides[0];
  245.     dists[i] = dists[0];
  246.     
  247.     *front = *back = NULL;
  248.  
  249.     if (!counts[0])
  250.     {
  251.         *back = CopyWinding (in);
  252.         return;
  253.     }
  254.     if (!counts[1])
  255.     {
  256.         *front = CopyWinding (in);
  257.         return;
  258.     }
  259.  
  260.     maxpts = in->numpoints+4;    // can't use counts[0]+2 because
  261.                                 // of fp grouping errors
  262.  
  263.     *front = f = AllocWinding (maxpts);
  264.     *back = b = AllocWinding (maxpts);
  265.         
  266.     for (i=0 ; i<in->numpoints ; i++)
  267.     {
  268.         p1 = in->p[i];
  269.         
  270.         if (sides[i] == SIDE_ON)
  271.         {
  272.             VectorCopy (p1, f->p[f->numpoints]);
  273.             f->numpoints++;
  274.             VectorCopy (p1, b->p[b->numpoints]);
  275.             b->numpoints++;
  276.             continue;
  277.         }
  278.     
  279.         if (sides[i] == SIDE_FRONT)
  280.         {
  281.             VectorCopy (p1, f->p[f->numpoints]);
  282.             f->numpoints++;
  283.         }
  284.         if (sides[i] == SIDE_BACK)
  285.         {
  286.             VectorCopy (p1, b->p[b->numpoints]);
  287.             b->numpoints++;
  288.         }
  289.  
  290.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  291.             continue;
  292.             
  293.     // generate a split point
  294.         p2 = in->p[(i+1)%in->numpoints];
  295.         
  296.         dot = dists[i] / (dists[i]-dists[i+1]);
  297.         for (j=0 ; j<3 ; j++)
  298.         {    // avoid round off error when possible
  299.             if (normal[j] == 1)
  300.                 mid[j] = dist;
  301.             else if (normal[j] == -1)
  302.                 mid[j] = -dist;
  303.             else
  304.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  305.         }
  306.             
  307.         VectorCopy (mid, f->p[f->numpoints]);
  308.         f->numpoints++;
  309.         VectorCopy (mid, b->p[b->numpoints]);
  310.         b->numpoints++;
  311.     }
  312.     
  313.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  314.         Error ("ClipWinding: points exceeded estimate");
  315.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  316.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  317. }
  318.  
  319. /*
  320. =================
  321. ChopWinding
  322.  
  323. Returns the fragment of in that is on the front side
  324. of the cliping plane.  The original is freed.
  325. =================
  326. */
  327. winding_t    *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
  328. {
  329.     winding_t    *f, *b;
  330.  
  331.     ClipWinding (in, normal, dist, &f, &b);
  332.     free (in);
  333.     if (b)
  334.         free (b);
  335.     return f;
  336. }
  337.  
  338. /*
  339. =================
  340. CheckWinding
  341.  
  342. =================
  343. */
  344. void CheckWinding (winding_t *w)
  345. {
  346.     int        i, j;
  347.     vec_t    *p1, *p2;
  348.     vec_t    d, edgedist;
  349.     vec3_t    dir, edgenormal, facenormal;
  350.     vec_t    area;
  351.     vec_t    facedist;
  352.  
  353.     if (w->numpoints < 3)
  354.         Error ("CheckFace: %i points",w->numpoints);
  355.     
  356.     area = WindingArea(w);
  357.     if (area < 1)
  358.         Error ("CheckFace: %f area", area);
  359.  
  360.     WindingPlane (w, facenormal, &facedist);
  361.     
  362.     for (i=0 ; i<w->numpoints ; i++)
  363.     {
  364.         p1 = w->p[i];
  365.  
  366.         for (j=0 ; j<3 ; j++)
  367.             if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
  368.                 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
  369.  
  370.         j = i+1 == w->numpoints ? 0 : i+1;
  371.         
  372.     // check the point is on the face plane
  373.         d = DotProduct (p1, facenormal) - facedist;
  374.         if (d < -ON_EPSILON || d > ON_EPSILON)
  375.             Error ("CheckFace: point off plane");
  376.     
  377.     // check the edge isn't degenerate
  378.         p2 = w->p[j];
  379.         VectorSubtract (p2, p1, dir);
  380.         
  381.         if (VectorLength (dir) < ON_EPSILON)
  382.             Error ("CheckFace: degenerate edge");
  383.             
  384.         CrossProduct (facenormal, dir, edgenormal);
  385.         VectorNormalize (edgenormal);
  386.         edgedist = DotProduct (p1, edgenormal);
  387.         edgedist += ON_EPSILON;
  388.         
  389.     // all other points must be on front side
  390.         for (j=0 ; j<w->numpoints ; j++)
  391.         {
  392.             if (j == i)
  393.                 continue;
  394.             d = DotProduct (w->p[j], edgenormal);
  395.             if (d > edgedist)
  396.                 Error ("CheckFace: non-convex");
  397.         }
  398.     }
  399. }
  400.  
  401.