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 int PolygonF_Clip(int innumpoints, const float *inpoints, float planenormalx, float planenormaly, float planenormalz, float planedist, float epsilon, int outfrontmaxpoints, float *outfrontpoints)
 102 {
 103         int i, frontcount = 0;
 104         const float *n, *p;
 105         float frac, pdist, ndist;
 106         if (innumpoints < 1)
 107                 return 0;
 108         n = inpoints;
 109         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 110         for(i = 0;i < innumpoints;i++)
 111         {
 112                 p = n;
 113                 pdist = ndist;
 114                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 115                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 116                 if (pdist >= -epsilon)
 117                 {
 118                         if (frontcount < outfrontmaxpoints)
 119                         {
 120                                 *outfrontpoints++ = p[0];
 121                                 *outfrontpoints++ = p[1];
 122                                 *outfrontpoints++ = p[2];
 123                         }
 124                         frontcount++;
 125                 }
 126                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 127                 {
 128                         frac = pdist / (pdist - ndist);
 129                         if (frontcount < outfrontmaxpoints)
 130                         {
 131                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
 132                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
 133                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
 134                         }
 135                         frontcount++;
 136                 }
 137         }
 138         return frontcount;
 139 }
 140
 141 int PolygonD_Clip(int innumpoints, const double *inpoints, double planenormalx, double planenormaly, double planenormalz, double planedist, double epsilon, int outfrontmaxpoints, double *outfrontpoints)
 142 {
 143         int i, frontcount = 0;
 144         const double *n, *p;
 145         double frac, pdist, ndist;
 146         if (innumpoints < 1)
 147                 return 0;
 148         n = inpoints;
 149         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 150         for(i = 0;i < innumpoints;i++)
 151         {
 152                 p = n;
 153                 pdist = ndist;
 154                 n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 155                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 156                 if (pdist >= -epsilon)
 157                 {
 158                         if (frontcount < outfrontmaxpoints)
 159                         {
 160                                 *outfrontpoints++ = p[0];
 161                                 *outfrontpoints++ = p[1];
 162                                 *outfrontpoints++ = p[2];
 163                         }
 164                         frontcount++;
 165                 }
 166                 if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 167                 {
 168                         frac = pdist / (pdist - ndist);
 169                         if (frontcount < outfrontmaxpoints)
 170                         {
 171                                 *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
 172                                 *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
 173                                 *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
 174                         }
 175                         frontcount++;
 176                 }
 177         }
 178         return frontcount;
 179 }
 180
 181 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)
 182 {
 183         int i, frontcount = 0, backcount = 0, oncount = 0;
 184         const float *n, *p;
 185         float frac, pdist, ndist;
 186         if (innumpoints)
 187         {
 188                 n = inpoints;
 189                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 190                 for(i = 0;i < innumpoints;i++)
 191                 {
 192                         p = n;
 193                         pdist = ndist;
 194                         n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 195                         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 196                         if (pdist >= -epsilon)
 197                         {
 198                                 if (pdist <= epsilon)
 199                                         oncount++;
 200                                 if (frontcount < outfrontmaxpoints)
 201                                 {
 202                                         *outfrontpoints++ = p[0];
 203                                         *outfrontpoints++ = p[1];
 204                                         *outfrontpoints++ = p[2];
 205                                 }
 206                                 frontcount++;
 207                         }
 208                         if (pdist <= epsilon)
 209                         {
 210                                 if (backcount < outbackmaxpoints)
 211                                 {
 212                                         *outbackpoints++ = p[0];
 213                                         *outbackpoints++ = p[1];
 214                                         *outbackpoints++ = p[2];
 215                                 }
 216                                 backcount++;
 217                         }
 218                         if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 219                         {
 220                                 oncount++;
 221                                 frac = pdist / (pdist - ndist);
 222                                 if (frontcount < outfrontmaxpoints)
 223                                 {
 224                                         *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
 225                                         *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
 226                                         *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
 227                                 }
 228                                 frontcount++;
 229                                 if (backcount < outbackmaxpoints)
 230                                 {
 231                                         *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
 232                                         *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
 233                                         *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
 234                                 }
 235                                 backcount++;
 236                         }
 237                 }
 238         }
 239         if (neededfrontpoints)
 240                 *neededfrontpoints = frontcount;
 241         if (neededbackpoints)
 242                 *neededbackpoints = backcount;
 243         if (oncountpointer)
 244                 *oncountpointer = oncount;
 245 }
 246
 247 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)
 248 {
 249         int i = 0, frontcount = 0, backcount = 0, oncount = 0;
 250         const double *n, *p;
 251         double frac, pdist, ndist;
 252         if (innumpoints)
 253         {
 254                 n = inpoints;
 255                 ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 256                 for(i = 0;i < innumpoints;i++)
 257                 {
 258                         p = n;
 259                         pdist = ndist;
 260                         n = inpoints + ((i + 1) < innumpoints ? (i + 1) : 0) * 3;
 261                         ndist = n[0] * planenormalx + n[1] * planenormaly + n[2] * planenormalz - planedist;
 262                         if (pdist >= -epsilon)
 263                         {
 264                                 if (pdist <= epsilon)
 265                                         oncount++;
 266                                 if (frontcount < outfrontmaxpoints)
 267                                 {
 268                                         *outfrontpoints++ = p[0];
 269                                         *outfrontpoints++ = p[1];
 270                                         *outfrontpoints++ = p[2];
 271                                 }
 272                                 frontcount++;
 273                         }
 274                         if (pdist <= epsilon)
 275                         {
 276                                 if (backcount < outbackmaxpoints)
 277                                 {
 278                                         *outbackpoints++ = p[0];
 279                                         *outbackpoints++ = p[1];
 280                                         *outbackpoints++ = p[2];
 281                                 }
 282                                 backcount++;
 283                         }
 284                         if ((pdist > epsilon && ndist < -epsilon) || (pdist < -epsilon && ndist > epsilon))
 285                         {
 286                                 oncount++;
 287                                 frac = pdist / (pdist - ndist);
 288                                 if (frontcount < outfrontmaxpoints)
 289                                 {
 290                                         *outfrontpoints++ = p[0] + frac * (n[0] - p[0]);
 291                                         *outfrontpoints++ = p[1] + frac * (n[1] - p[1]);
 292                                         *outfrontpoints++ = p[2] + frac * (n[2] - p[2]);
 293                                 }
 294                                 frontcount++;
 295                                 if (backcount < outbackmaxpoints)
 296                                 {
 297                                         *outbackpoints++ = p[0] + frac * (n[0] - p[0]);
 298                                         *outbackpoints++ = p[1] + frac * (n[1] - p[1]);
 299                                         *outbackpoints++ = p[2] + frac * (n[2] - p[2]);
 300                                 }
 301                                 backcount++;
 302                         }
 303                 }
 304         }
 305         if (neededfrontpoints)
 306                 *neededfrontpoints = frontcount;
 307         if (neededbackpoints)
 308                 *neededbackpoints = backcount;
 309         if (oncountpointer)
 310                 *oncountpointer = oncount;
 311 }
 312