winding.c

   1
   2 #include "quakedef.h"
   3 #include "winding.h"
   4
   5 // this code came from qbsp source
   6
   7 #define MAX_POINTS_ON_WINDING 64
   8
   9 winding_t *Winding_New(int points)
  10 {
  11         winding_t *w;
  12         w = Mem_Alloc(loadmodel->mempool, sizeof(winding_t) + sizeof(double[3]) * (points - 8));
  13         w->maxpoints = points;
  14         return w;
  15 }
  16
  17 void Winding_Free(winding_t *w)
  18 {
  19         Mem_Free(w);
  20 }
  21
  22 winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist)
  23 {
  24         winding_t *w;
  25         w = Winding_New(4);
  26         BufWinding_NewFromPlane(w, normalx, normaly, normalz, dist);
  27         return w;
  28 }
  29
  30 //Clips the winding to the plane, returning the new winding on the positive side
  31 //Frees the input winding.
  32 //If keepon is true, an exactly on-plane winding will be saved, otherwise
  33 //it will be clipped away.
  34 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
  35 {
  36         winding_t *neww;
  37         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
  38         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
  39
  40         splitnormal[0] = splitnormalx;
  41         splitnormal[1] = splitnormaly;
  42         splitnormal[2] = splitnormalz;
  43         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
  44
  45         // determine sides for each point
  46         for (i = 0;i < in->numpoints;i++)
  47         {
  48                 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
  49                 if (dot > ON_EPSILON)
  50                         sides[i] = SIDE_FRONT;
  51                 else if (dot < -ON_EPSILON)
  52                         sides[i] = SIDE_BACK;
  53                 else
  54                         sides[i] = SIDE_ON;
  55                 counts[sides[i]]++;
  56         }
  57         sides[i] = sides[0];
  58         dists[i] = dists[0];
  59
  60         if (keepon && !counts[0] && !counts[1])
  61                 return in;
  62
  63         if (!counts[0])
  64         {
  65                 Winding_Free(in);
  66                 return NULL;
  67         }
  68         if (!counts[1])
  69                 return in;
  70
  71         maxpts = 0;
  72         for (i = 0;i < in->numpoints;i++)
  73         {
  74                 if (sides[i] == SIDE_ON)
  75                 {
  76                         maxpts++;
  77                         continue;
  78                 }
  79                 if (sides[i] == SIDE_FRONT)
  80                         maxpts++;
  81                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  82                         continue;
  83                 maxpts++;
  84         }
  85
  86         if (maxpts > MAX_POINTS_ON_WINDING)
  87                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
  88
  89         neww = Winding_New(maxpts);
  90
  91         for (i = 0;i < in->numpoints;i++)
  92         {
  93                 p1 = in->points[i];
  94
  95                 if (sides[i] == SIDE_ON)
  96                 {
  97                         VectorCopy(p1, neww->points[neww->numpoints]);
  98                         neww->numpoints++;
  99                         continue;
 100                 }
 101
 102                 if (sides[i] == SIDE_FRONT)
 103                 {
 104                         VectorCopy(p1, neww->points[neww->numpoints]);
 105                         neww->numpoints++;
 106                 }
 107
 108                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 109                         continue;
 110
 111                 // generate a split point
 112                 p2 = in->points[(i+1)%in->numpoints];
 113
 114                 dot = dists[i] / (dists[i]-dists[i+1]);
 115                 for (j = 0;j < 3;j++)
 116                 {       // avoid round off error when possible
 117                         if (splitnormal[j] == 1)
 118                                 mid[j] = splitdist;
 119                         else if (splitnormal[j] == -1)
 120                                 mid[j] = -splitdist;
 121                         else
 122                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 123                 }
 124
 125                 VectorCopy(mid, neww->points[neww->numpoints]);
 126                 neww->numpoints++;
 127         }
 128
 129         // free the original winding
 130         Winding_Free(in);
 131
 132         return neww;
 133 }
 134
 135
 136 //Divides a winding by a plane, producing one or two windings.  The
 137 //original winding is not damaged or freed.  If only on one side, the
 138 //returned winding will be the input winding.  If on both sides, two
 139 //new windings will be created.
 140 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
 141 {
 142         winding_t *f, *b;
 143         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 144         int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 145
 146         splitnormal[0] = splitnormalx;
 147         splitnormal[1] = splitnormaly;
 148         splitnormal[2] = splitnormalz;
 149
 150         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 151
 152         // determine sides for each point
 153         for (i = 0;i < in->numpoints;i++)
 154         {
 155                 dot = DotProduct(in->points[i], splitnormal);
 156                 dot -= splitdist;
 157                 dists[i] = dot;
 158                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 159                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 160                 else sides[i] = SIDE_ON;
 161                 counts[sides[i]]++;
 162         }
 163         sides[i] = sides[0];
 164         dists[i] = dists[0];
 165
 166         *front = *back = NULL;
 167
 168         if (!counts[0])
 169         {
 170                 *back = in;
 171                 return;
 172         }
 173         if (!counts[1])
 174         {
 175                 *front = in;
 176                 return;
 177         }
 178
 179         frontpts = 0;
 180         backpts = 0;
 181
 182         for (i = 0;i < in->numpoints;i++)
 183         {
 184                 if (sides[i] == SIDE_ON)
 185                 {
 186                         frontpts++;
 187                         backpts++;
 188                         continue;
 189                 }
 190                 if (sides[i] == SIDE_FRONT)
 191                         frontpts++;
 192                 else if (sides[i] == SIDE_BACK)
 193                         backpts++;
 194                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 195                         continue;
 196                 frontpts++;
 197                 backpts++;
 198         }
 199
 200         if (frontpts > MAX_POINTS_ON_WINDING)
 201                 Sys_Error("Winding_Clip: frontpts > MAX_POINTS_ON_WINDING");
 202         if (backpts > MAX_POINTS_ON_WINDING)
 203                 Sys_Error("Winding_Clip: backpts > MAX_POINTS_ON_WINDING");
 204
 205         *front = f = Winding_New(frontpts);
 206         *back = b = Winding_New(backpts);
 207
 208         for (i = 0;i < in->numpoints;i++)
 209         {
 210                 p1 = in->points[i];
 211
 212                 if (sides[i] == SIDE_ON)
 213                 {
 214                         VectorCopy(p1, f->points[f->numpoints]);
 215                         f->numpoints++;
 216                         VectorCopy(p1, b->points[b->numpoints]);
 217                         b->numpoints++;
 218                         continue;
 219                 }
 220
 221                 if (sides[i] == SIDE_FRONT)
 222                 {
 223                         VectorCopy(p1, f->points[f->numpoints]);
 224                         f->numpoints++;
 225                 }
 226                 else if (sides[i] == SIDE_BACK)
 227                 {
 228                         VectorCopy(p1, b->points[b->numpoints]);
 229                         b->numpoints++;
 230                 }
 231
 232                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 233                         continue;
 234
 235                 // generate a split point
 236                 p2 = in->points[(i+1)%in->numpoints];
 237
 238                 dot = dists[i] / (dists[i]-dists[i+1]);
 239                 for (j = 0;j < 3;j++)
 240                 {       // avoid round off error when possible
 241                         if (splitnormal[j] == 1)
 242                                 mid[j] = splitdist;
 243                         else if (splitnormal[j] == -1)
 244                                 mid[j] = -splitdist;
 245                         else
 246                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 247                 }
 248
 249                 VectorCopy(mid, f->points[f->numpoints]);
 250                 f->numpoints++;
 251                 VectorCopy(mid, b->points[b->numpoints]);
 252                 b->numpoints++;
 253         }
 254 }
 255
 256 // LordHavoc: these functions are more efficient by not allocating/freeing memory all the time
 257
 258 void BufWinding_NewFromPlane(winding_t *w, double normalx, double normaly, double normalz, double dist)
 259 {
 260         int x;
 261         double max, v, org[3], vright[3], vup[3], normal[3];
 262
 263         w->numpoints = 0;
 264         if (w->maxpoints < 4)
 265                 return;
 266
 267         w->numpoints = 4;
 268
 269         normal[0] = normalx;
 270         normal[1] = normaly;
 271         normal[2] = normalz;
 272 #if 0
 273         VectorVectorsDouble(normal, vright, vup);
 274 #else
 275         // find the major axis
 276         x = 0;
 277         max = fabs(normal[0]);
 278         v = fabs(normal[1]);
 279         if(v > max)
 280         {
 281                 x = 1;
 282                 max = v;
 283         }
 284         v = fabs(normal[2]);
 285         if(v > max)
 286         {
 287                 x = 2;
 288                 max = v;
 289         }
 290
 291         VectorClear(vup);
 292         switch(x)
 293         {
 294         case 0:
 295         case 1:
 296                 vup[2] = 1;
 297                 break;
 298         case 2:
 299                 vup[0] = 1;
 300                 break;
 301         }
 302
 303         v = DotProduct(vup, normal);
 304         VectorMA(vup, -v, normal, vup);
 305         VectorNormalize(vup);
 306 #endif
 307
 308         VectorScale(normal, dist, org);
 309
 310         CrossProduct(vup, normal, vright);
 311
 312         VectorScale(vup, 1024.0*1024.0*1024.0, vup);
 313         VectorScale(vright, 1024.0*1024.0*1024.0, vright);
 314
 315         // project a really big axis aligned box onto the plane
 316         VectorSubtract(org, vright, w->points[0]);
 317         VectorAdd(w->points[0], vup, w->points[0]);
 318
 319         VectorAdd(org, vright, w->points[1]);
 320         VectorAdd(w->points[1], vup, w->points[1]);
 321
 322         VectorAdd(org, vright, w->points[2]);
 323         VectorSubtract(w->points[2], vup, w->points[2]);
 324
 325         VectorSubtract(org, vright, w->points[3]);
 326         VectorSubtract(w->points[3], vup, w->points[3]);
 327
 328 #if 0
 329         {
 330                 double n[3];
 331                 TriangleNormal(w->points[0], w->points[1], w->points[2], n);
 332                 VectorNormalize(n);
 333                 if (fabs(DotProduct(n, normal) - 1) > 0.01f)
 334                         Con_Printf("%.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f) != %.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f)\n", normal[0], normal[1], normal[2], vright[0], vright[1], vright[2], vup[0], vup[1], vup[2], n[0], n[1], n[2], w->points[0][0], w->points[0][1], w->points[0][2], w->points[1][0], w->points[1][1], w->points[1][2], w->points[2][0], w->points[2][1], w->points[2][2], w->points[3][0], w->points[3][1], w->points[3][2]);
 335         }
 336 #endif
 337 }
 338
 339 void BufWinding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t *outfront, int *neededfrontpoints, winding_t *outback, int *neededbackpoints)
 340 {
 341         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 342         int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 343
 344         if (outfront)
 345                 outfront->numpoints = 0;
 346         if (outback)
 347                 outback->numpoints = 0;
 348
 349         if (in->numpoints > MAX_POINTS_ON_WINDING || (!outfront && !outback))
 350         {
 351                 if (neededfrontpoints)
 352                         *neededfrontpoints = 0;
 353                 if (neededbackpoints)
 354                         *neededbackpoints = 0;
 355                 return;
 356         }
 357
 358         splitnormal[0] = splitnormalx;
 359         splitnormal[1] = splitnormaly;
 360         splitnormal[2] = splitnormalz;
 361
 362         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 363
 364         // determine sides for each point
 365         for (i = 0;i < in->numpoints;i++)
 366         {
 367                 dot = DotProduct(in->points[i], splitnormal);
 368                 dot -= splitdist;
 369                 dists[i] = dot;
 370                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 371                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 372                 else sides[i] = SIDE_ON;
 373                 counts[sides[i]]++;
 374         }
 375         sides[i] = sides[0];
 376         dists[i] = dists[0];
 377
 378         frontpts = 0;
 379         backpts = 0;
 380         for (i = 0;i < in->numpoints;i++)
 381         {
 382                 if (sides[i] != SIDE_ON)
 383                 {
 384                         if (sides[i] == SIDE_FRONT)
 385                                 frontpts++;
 386                         else if (sides[i] == SIDE_BACK)
 387                                 backpts++;
 388                         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 389                                 continue;
 390                 }
 391                 frontpts++;
 392                 backpts++;
 393         }
 394
 395         if (neededfrontpoints)
 396                 *neededfrontpoints = frontpts;
 397         if (neededbackpoints)
 398                 *neededbackpoints = backpts;
 399         if ((outfront && outfront->maxpoints < frontpts) || (outback && outback->maxpoints < backpts))
 400                 return;
 401
 402         for (i = 0;i < in->numpoints;i++)
 403         {
 404                 p1 = in->points[i];
 405
 406                 if (sides[i] == SIDE_ON)
 407                 {
 408                         if (outfront)
 409                         {
 410                                 VectorCopy(p1, outfront->points[outfront->numpoints]);
 411                                 outfront->numpoints++;
 412                         }
 413                         if (outback)
 414                         {
 415                                 VectorCopy(p1, outback->points[outback->numpoints]);
 416                                 outback->numpoints++;
 417                         }
 418                         continue;
 419                 }
 420
 421                 if (sides[i] == SIDE_FRONT)
 422                 {
 423                         if (outfront)
 424                         {
 425                                 VectorCopy(p1, outfront->points[outfront->numpoints]);
 426                                 outfront->numpoints++;
 427                         }
 428                 }
 429                 else if (sides[i] == SIDE_BACK)
 430                 {
 431                         if (outback)
 432                         {
 433                                 VectorCopy(p1, outback->points[outback->numpoints]);
 434                                 outback->numpoints++;
 435                         }
 436                 }
 437
 438                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 439                         continue;
 440
 441                 // generate a split point
 442                 p2 = in->points[(i+1)%in->numpoints];
 443
 444                 dot = dists[i] / (dists[i]-dists[i+1]);
 445                 for (j = 0;j < 3;j++)
 446                 {       // avoid round off error when possible
 447                         if (splitnormal[j] == 1)
 448                                 mid[j] = splitdist;
 449                         else if (splitnormal[j] == -1)
 450                                 mid[j] = -splitdist;
 451                         else
 452                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 453                 }
 454
 455                 if (outfront)
 456                 {
 457                         VectorCopy(mid, outfront->points[outfront->numpoints]);
 458                         outfront->numpoints++;
 459                 }
 460                 if (outback)
 461                 {
 462                         VectorCopy(mid, outback->points[outback->numpoints]);
 463                         outback->numpoints++;
 464                 }
 465         }
 466 }
 467
 468 void Polygon_Divide_Double(int innumpoints, const double *inpoints, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int outfrontmaxpoints, double *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, double *outbackpoints, int *neededbackpoints)
 469 {
 470         double dot, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 471         const double *p1, *p2;
 472         int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 473
 474         if (neededfrontpoints)
 475                 *neededfrontpoints = 0;
 476         if (neededbackpoints)
 477                 *neededbackpoints = 0;
 478
 479         if (innumpoints > MAX_POINTS_ON_WINDING || (!outfrontmaxpoints && !outbackmaxpoints))
 480                 return;
 481
 482         splitnormal[0] = splitnormalx;
 483         splitnormal[1] = splitnormaly;
 484         splitnormal[2] = splitnormalz;
 485
 486         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 487
 488         // determine sides for each point
 489         for (i = 0;i < innumpoints;i++)
 490         {
 491                 dot = DotProduct(inpoints + i * 3, splitnormal);
 492                 dot -= splitdist;
 493                 dists[i] = dot;
 494                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 495                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 496                 else sides[i] = SIDE_ON;
 497                 counts[sides[i]]++;
 498         }
 499         sides[i] = sides[0];
 500         dists[i] = dists[0];
 501
 502         frontpts = 0;
 503         backpts = 0;
 504         for (i = 0;i < innumpoints;i++)
 505         {
 506                 if (sides[i] != SIDE_ON)
 507                 {
 508                         if (sides[i] == SIDE_FRONT)
 509                                 frontpts++;
 510                         else if (sides[i] == SIDE_BACK)
 511                                 backpts++;
 512                         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 513                                 continue;
 514                 }
 515                 frontpts++;
 516                 backpts++;
 517         }
 518
 519         if (neededfrontpoints)
 520                 *neededfrontpoints = frontpts;
 521         if (neededbackpoints)
 522                 *neededbackpoints = backpts;
 523         if ((outfrontmaxpoints && outfrontmaxpoints < frontpts) || (outbackmaxpoints && outbackmaxpoints < backpts))
 524                 return;
 525
 526         for (i = 0;i < innumpoints;i++)
 527         {
 528                 p1 = inpoints + i * 3;
 529
 530                 if (sides[i] == SIDE_ON)
 531                 {
 532                         if (outfrontmaxpoints)
 533                         {
 534                                 VectorCopy(p1, outfrontpoints);
 535                                 outfrontpoints += 3;
 536                         }
 537                         if (outbackmaxpoints)
 538                         {
 539                                 VectorCopy(p1, outbackpoints);
 540                                 outbackpoints += 3;
 541                         }
 542                         continue;
 543                 }
 544
 545                 if (sides[i] == SIDE_FRONT)
 546                 {
 547                         if (outfrontmaxpoints)
 548                         {
 549                                 VectorCopy(p1, outfrontpoints);
 550                                 outfrontpoints += 3;
 551                         }
 552                 }
 553                 else if (sides[i] == SIDE_BACK)
 554                 {
 555                         if (outbackmaxpoints)
 556                         {
 557                                 VectorCopy(p1, outbackpoints);
 558                                 outbackpoints += 3;
 559                         }
 560                 }
 561
 562                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 563                         continue;
 564
 565                 // generate a split point
 566                 p2 = inpoints + ((i+1)%innumpoints) * 3;
 567
 568                 dot = dists[i] / (dists[i]-dists[i+1]);
 569                 for (j = 0;j < 3;j++)
 570                 {       // avoid round off error when possible
 571                         if (splitnormal[j] == 1)
 572                                 mid[j] = splitdist;
 573                         else if (splitnormal[j] == -1)
 574                                 mid[j] = -splitdist;
 575                         else
 576                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 577                 }
 578
 579                 if (outfrontmaxpoints)
 580                 {
 581                         VectorCopy(mid, outfrontpoints);
 582                         outfrontpoints += 3;
 583                 }
 584                 if (outbackmaxpoints)
 585                 {
 586                         VectorCopy(mid, outbackpoints);
 587                         outbackpoints += 3;
 588                 }
 589         }
 590 }
 591
 592 void Polygon_Divide_Float(int innumpoints, const float *inpoints, float splitnormalx, float splitnormaly, float splitnormalz, float splitdist, int outfrontmaxpoints, float *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, float *outbackpoints, int *neededbackpoints)
 593 {
 594         float dot, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 595         const float *p1, *p2;
 596         int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 597
 598         if (neededfrontpoints)
 599                 *neededfrontpoints = 0;
 600         if (neededbackpoints)
 601                 *neededbackpoints = 0;
 602
 603         if (innumpoints > MAX_POINTS_ON_WINDING || (!outfrontmaxpoints && !outbackmaxpoints))
 604                 return;
 605
 606         splitnormal[0] = splitnormalx;
 607         splitnormal[1] = splitnormaly;
 608         splitnormal[2] = splitnormalz;
 609
 610         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 611
 612         // determine sides for each point
 613         for (i = 0;i < innumpoints;i++)
 614         {
 615                 dot = DotProduct(inpoints + i * 3, splitnormal);
 616                 dot -= splitdist;
 617                 dists[i] = dot;
 618                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 619                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 620                 else sides[i] = SIDE_ON;
 621                 counts[sides[i]]++;
 622         }
 623         sides[i] = sides[0];
 624         dists[i] = dists[0];
 625
 626         frontpts = 0;
 627         backpts = 0;
 628         for (i = 0;i < innumpoints;i++)
 629         {
 630                 if (sides[i] != SIDE_ON)
 631                 {
 632                         if (sides[i] == SIDE_FRONT)
 633                                 frontpts++;
 634                         else if (sides[i] == SIDE_BACK)
 635                                 backpts++;
 636                         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 637                                 continue;
 638                 }
 639                 frontpts++;
 640                 backpts++;
 641         }
 642
 643         if (neededfrontpoints)
 644                 *neededfrontpoints = frontpts;
 645         if (neededbackpoints)
 646                 *neededbackpoints = backpts;
 647         if ((outfrontmaxpoints && outfrontmaxpoints < frontpts) || (outbackmaxpoints && outbackmaxpoints < backpts))
 648                 return;
 649
 650         for (i = 0;i < innumpoints;i++)
 651         {
 652                 p1 = inpoints + i * 3;
 653
 654                 if (sides[i] == SIDE_ON)
 655                 {
 656                         if (outfrontmaxpoints)
 657                         {
 658                                 VectorCopy(p1, outfrontpoints);
 659                                 outfrontpoints += 3;
 660                         }
 661                         if (outbackmaxpoints)
 662                         {
 663                                 VectorCopy(p1, outbackpoints);
 664                                 outbackpoints += 3;
 665                         }
 666                         continue;
 667                 }
 668
 669                 if (sides[i] == SIDE_FRONT)
 670                 {
 671                         if (outfrontmaxpoints)
 672                         {
 673                                 VectorCopy(p1, outfrontpoints);
 674                                 outfrontpoints += 3;
 675                         }
 676                 }
 677                 else if (sides[i] == SIDE_BACK)
 678                 {
 679                         if (outbackmaxpoints)
 680                         {
 681                                 VectorCopy(p1, outbackpoints);
 682                                 outbackpoints += 3;
 683                         }
 684                 }
 685
 686                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 687                         continue;
 688
 689                 // generate a split point
 690                 p2 = inpoints + ((i+1)%innumpoints) * 3;
 691
 692                 dot = dists[i] / (dists[i]-dists[i+1]);
 693                 for (j = 0;j < 3;j++)
 694                 {       // avoid round off error when possible
 695                         if (splitnormal[j] == 1)
 696                                 mid[j] = splitdist;
 697                         else if (splitnormal[j] == -1)
 698                                 mid[j] = -splitdist;
 699                         else
 700                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 701                 }
 702
 703                 if (outfrontmaxpoints)
 704                 {
 705                         VectorCopy(mid, outfrontpoints);
 706                         outfrontpoints += 3;
 707                 }
 708                 if (outbackmaxpoints)
 709                 {
 710                         VectorCopy(mid, outbackpoints);
 711                         outbackpoints += 3;
 712                 }
 713         }
 714 }
 715