polygon.c

   1
   2 /*
   3 Polygon clipping routines written by Forest Hale and placed into public domain.
   4 */
   5
   6 #include "quakedef.h"
   7
   8 #include <math.h>
   9 #include "polygon.h"
  10
  11 void PolygonF_QuadForPlane(float *outpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float quadsize)
  12 {
  13         float d, quadright[3], quadup[3];
  14         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
  15         {
  16                 quadup[0] = 1;
  17                 quadup[1] = 0;
  18                 quadup[2] = 0;
  19         }
  20         else
  21         {
  22                 quadup[0] = 0;
  23                 quadup[1] = 0;
  24                 quadup[2] = 1;
  25         }
  26         // d = -DotProduct(quadup, planenormal);
  27         d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
  28         // VectorMA(quadup, d, planenormal, quadup);
  29         quadup[0] += d * planenormalx;
  30         quadup[1] += d * planenormaly;
  31         quadup[2] += d * planenormalz;
  32         // VectorNormalize(quadup);
  33         d = (float)(1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]));
  34         quadup[0] *= d;
  35         quadup[1] *= d;
  36         quadup[2] *= d;
  37         // CrossProduct(quadup,planenormal,quadright);
  38         quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
  39         quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
  40         quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
  41         // make the points
  42         outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
  43         outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
  44         outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
  45         outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
  46         outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
  47         outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
  48         outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
  49         outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
  50         outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
  51         outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
  52         outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
  53         outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
  54 }
  55
  56 void PolygonD_QuadForPlane(double *outpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double quadsize)
  57 {
  58         double d, quadright[3], quadup[3];
  59         if (fabs(planenormalz) > fabs(planenormalx) && fabs(planenormalz) > fabs(planenormaly))
  60         {
  61                 quadup[0] = 1;
  62                 quadup[1] = 0;
  63                 quadup[2] = 0;
  64         }
  65         else
  66         {
  67                 quadup[0] = 0;
  68                 quadup[1] = 0;
  69                 quadup[2] = 1;
  70         }
  71         // d = -DotProduct(quadup, planenormal);
  72         d = -(quadup[0] * planenormalx + quadup[1] * planenormaly + quadup[2] * planenormalz);
  73         // VectorMA(quadup, d, planenormal, quadup);
  74         quadup[0] += d * planenormalx;
  75         quadup[1] += d * planenormaly;
  76         quadup[2] += d * planenormalz;
  77         // VectorNormalize(quadup);
  78         d = 1.0 / sqrt(quadup[0] * quadup[0] + quadup[1] * quadup[1] + quadup[2] * quadup[2]);
  79         quadup[0] *= d;
  80         quadup[1] *= d;
  81         quadup[2] *= d;
  82         // CrossProduct(quadup,planenormal,quadright);
  83         quadright[0] = quadup[1] * planenormalz - quadup[2] * planenormaly;
  84         quadright[1] = quadup[2] * planenormalx - quadup[0] * planenormalz;
  85         quadright[2] = quadup[0] * planenormaly - quadup[1] * planenormalx;
  86         // make the points
  87         outpoints[0] = planedist * planenormalx - quadsize * quadright[0] + quadsize * quadup[0];
  88         outpoints[1] = planedist * planenormaly - quadsize * quadright[1] + quadsize * quadup[1];
  89         outpoints[2] = planedist * planenormalz - quadsize * quadright[2] + quadsize * quadup[2];
  90         outpoints[3] = planedist * planenormalx + quadsize * quadright[0] + quadsize * quadup[0];
  91         outpoints[4] = planedist * planenormaly + quadsize * quadright[1] + quadsize * quadup[1];
  92         outpoints[5] = planedist * planenormalz + quadsize * quadright[2] + quadsize * quadup[2];
  93         outpoints[6] = planedist * planenormalx + quadsize * quadright[0] - quadsize * quadup[0];
  94         outpoints[7] = planedist * planenormaly + quadsize * quadright[1] - quadsize * quadup[1];
  95         outpoints[8] = planedist * planenormalz + quadsize * quadright[2] - quadsize * quadup[2];
  96         outpoints[9] = planedist * planenormalx - quadsize * quadright[0] - quadsize * quadup[0];
  97         outpoints[10] = planedist * planenormaly - quadsize * quadright[1] - quadsize * quadup[1];
  98         outpoints[11] = planedist * planenormalz - quadsize * quadright[2] - quadsize * quadup[2];
  99 }
 100
 101 void PolygonF_Divide(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, float *outbackpoints, int *neededbackpoints, int *oncountpointer)
 102 {
 103         int i, frontcount = 0, backcount = 0, oncount = 0;
 104         const float *n, *p;
 105         double frac, pdist, ndist;
 106         for (i = 0;i < innumpoints;i++)
 107         {
 108                 p = inpoints + i * 3;
 109                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 110                 pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist;
 111                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 112                 if (pdist >= -epsilon)
 113                 {
 114                         if (pdist <= epsilon)
 115                                 oncount++;
 116                         if (frontcount < outfrontmaxpoints)
 117                         {
 118                                 *outfrontpoints++ = p[0];
 119                                 *outfrontpoints++ = p[1];
 120                                 *outfrontpoints++ = p[2];
 121                         }
 122                         frontcount++;
 123                 }
 124                 if (pdist <= epsilon)
 125                 {
 126                         if (backcount < outbackmaxpoints)
 127                         {
 128                                 *outbackpoints++ = p[0];
 129                                 *outbackpoints++ = p[1];
 130                                 *outbackpoints++ = p[2];
 131                         }
 132                         backcount++;
 133                 }
 134                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 135                 {
 136                         oncount++;
 137                         frac = pdist / (pdist - ndist);
 138                         if (frontcount < outfrontmaxpoints)
 139                         {
 140                                 *outfrontpoints++ = (float)(p[0] + frac * (n[0] - p[0]));
 141                                 *outfrontpoints++ = (float)(p[1] + frac * (n[1] - p[1]));
 142                                 *outfrontpoints++ = (float)(p[2] + frac * (n[2] - p[2]));
 143                         }
 144                         frontcount++;
 145                         if (backcount < outbackmaxpoints)
 146                         {
 147                                 *outbackpoints++ = (float)(p[0] + frac * (n[0] - p[0]));
 148                                 *outbackpoints++ = (float)(p[1] + frac * (n[1] - p[1]));
 149                                 *outbackpoints++ = (float)(p[2] + frac * (n[2] - p[2]));
 150                         }
 151                         backcount++;
 152                 }
 153         }
 154         if (neededfrontpoints)
 155                 *neededfrontpoints = frontcount;
 156         if (neededbackpoints)
 157                 *neededbackpoints = backcount;
 158         if (oncountpointer)
 159                 *oncountpointer = oncount;
 160 }
 161
 162 void PolygonD_Divide(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, double *outbackpoints, int *neededbackpoints, int *oncountpointer)
 163 {
 164         int i, frontcount = 0, backcount = 0, oncount = 0;
 165         const double *n, *p;
 166         double frac, pdist, ndist;
 167         for (i = 0;i < innumpoints;i++)
 168         {
 169                 p = inpoints + i * 3;
 170                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 171                 pdist = p[0] * planenormalx + p[1] * planenormaly + p[2] * planenormalz - planedist;
 172                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 173                 if (pdist >= -epsilon)
 174                 {
 175                         if (pdist <= epsilon)
 176                                 oncount++;
 177                         if (frontcount < outfrontmaxpoints)
 178                         {
 179                                 *outfrontpoints++ = p[0];
 180                                 *outfrontpoints++ = p[1];
 181                                 *outfrontpoints++ = p[2];
 182                         }
 183                         frontcount++;
 184                 }
 185                 if (pdist <= epsilon)
 186                 {
 187                         if (backcount < outbackmaxpoints)
 188                         {
 189                                 *outbackpoints++ = p[0];
 190                                 *outbackpoints++ = p[1];
 191                                 *outbackpoints++ = p[2];
 192                         }
 193                         backcount++;
 194                 }
 195                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 196                 {
 197                         oncount++;
 198                         frac = pdist / (pdist - ndist);
 199                         if (frontcount < outfrontmaxpoints)
 200                         {
 201                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
 202                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
 203                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
 204                         }
 205                         frontcount++;
 206                         if (backcount < outbackmaxpoints)
 207                         {
 208                                 *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
 209                                 *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
 210                                 *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
 211                         }
 212                         backcount++;
 213                 }
 214         }
 215         if (neededfrontpoints)
 216                 *neededfrontpoints = frontcount;
 217         if (neededbackpoints)
 218                 *neededbackpoints = backcount;
 219         if (oncountpointer)
 220                 *oncountpointer = oncount;
 221 }
 222