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         int size;
  13
  14         if (points > MAX_POINTS_ON_WINDING)
  15                 Sys_Error("Winding_New: too many points\n");
  16
  17         size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
  18         w = Mem_Alloc(loadmodel->mempool, size);
  19         //Mem_Alloc clears
  20         //memset(w, 0, size);
  21
  22         return w;
  23 }
  24
  25 void Winding_Free(winding_t *w)
  26 {
  27         Mem_Free(w);
  28 }
  29
  30 winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist)
  31 {
  32         int x;
  33         double max, v, org[3], vright[3], vup[3], normal[3];
  34         winding_t *w;
  35
  36         normal[0] = normalx;
  37         normal[1] = normaly;
  38         normal[2] = normalz;
  39 #if 0
  40         VectorVectorsDouble(normal, vright, vup);
  41 #else
  42         // find the major axis
  43         x = 0;
  44         max = fabs(normal[0]);
  45         v = fabs(normal[1]);
  46         if(v > max)
  47         {
  48                 x = 1;
  49                 max = v;
  50         }
  51         v = fabs(normal[2]);
  52         if(v > max)
  53         {
  54                 x = 2;
  55                 max = v;
  56         }
  57
  58         VectorClear(vup);
  59         switch(x)
  60         {
  61         case 0:
  62         case 1:
  63                 vup[2] = 1;
  64                 break;
  65         case 2:
  66                 vup[0] = 1;
  67                 break;
  68         }
  69
  70         v = DotProduct(vup, normal);
  71         VectorMA(vup, -v, normal, vup);
  72         VectorNormalize(vup);
  73 #endif
  74
  75         VectorScale(normal, dist, org);
  76
  77         CrossProduct(vup, normal, vright);
  78
  79         VectorScale(vup, 1024.0*1024.0*1024.0, vup);
  80         VectorScale(vright, 1024.0*1024.0*1024.0, vright);
  81
  82         // project a really big axis aligned box onto the plane
  83         w = Winding_New(4);
  84
  85         VectorSubtract(org, vright, w->points[0]);
  86         VectorAdd(w->points[0], vup, w->points[0]);
  87
  88         VectorAdd(org, vright, w->points[1]);
  89         VectorAdd(w->points[1], vup, w->points[1]);
  90
  91         VectorAdd(org, vright, w->points[2]);
  92         VectorSubtract(w->points[2], vup, w->points[2]);
  93
  94         VectorSubtract(org, vright, w->points[3]);
  95         VectorSubtract(w->points[3], vup, w->points[3]);
  96
  97         w->numpoints = 4;
  98
  99         return w;
 100 }
 101
 102 //Clips the winding to the plane, returning the new winding on the positive side
 103 //Frees the input winding.
 104 //If keepon is true, an exactly on-plane winding will be saved, otherwise
 105 //it will be clipped away.
 106 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
 107 {
 108         winding_t *neww;
 109         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 110         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 111
 112         splitnormal[0] = splitnormalx;
 113         splitnormal[1] = splitnormaly;
 114         splitnormal[2] = splitnormalz;
 115         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 116
 117         // determine sides for each point
 118         for (i = 0;i < in->numpoints;i++)
 119         {
 120                 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
 121                 if (dot > ON_EPSILON)
 122                         sides[i] = SIDE_FRONT;
 123                 else if (dot < -ON_EPSILON)
 124                         sides[i] = SIDE_BACK;
 125                 else
 126                         sides[i] = SIDE_ON;
 127                 counts[sides[i]]++;
 128         }
 129         sides[i] = sides[0];
 130         dists[i] = dists[0];
 131
 132         if (keepon && !counts[0] && !counts[1])
 133                 return in;
 134
 135         if (!counts[0])
 136         {
 137                 Winding_Free(in);
 138                 return NULL;
 139         }
 140         if (!counts[1])
 141                 return in;
 142
 143         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
 144         if (maxpts > MAX_POINTS_ON_WINDING)
 145                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
 146
 147         neww = Winding_New(maxpts);
 148
 149         for (i = 0;i < in->numpoints;i++)
 150         {
 151                 if (neww->numpoints >= maxpts)
 152                         Sys_Error("Winding_Clip: points exceeded estimate");
 153
 154                 p1 = in->points[i];
 155
 156                 if (sides[i] == SIDE_ON)
 157                 {
 158                         VectorCopy(p1, neww->points[neww->numpoints]);
 159                         neww->numpoints++;
 160                         continue;
 161                 }
 162
 163                 if (sides[i] == SIDE_FRONT)
 164                 {
 165                         VectorCopy(p1, neww->points[neww->numpoints]);
 166                         neww->numpoints++;
 167                 }
 168
 169                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 170                         continue;
 171
 172                 // generate a split point
 173                 p2 = in->points[(i+1)%in->numpoints];
 174
 175                 dot = dists[i] / (dists[i]-dists[i+1]);
 176                 for (j = 0;j < 3;j++)
 177                 {       // avoid round off error when possible
 178                         if (splitnormal[j] == 1)
 179                                 mid[j] = splitdist;
 180                         else if (splitnormal[j] == -1)
 181                                 mid[j] = -splitdist;
 182                         else
 183                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 184                 }
 185
 186                 VectorCopy(mid, neww->points[neww->numpoints]);
 187                 neww->numpoints++;
 188         }
 189
 190         // free the original winding
 191         Winding_Free(in);
 192
 193         return neww;
 194 }
 195
 196
 197 //Divides a winding by a plane, producing one or two windings.  The
 198 //original winding is not damaged or freed.  If only on one side, the
 199 //returned winding will be the input winding.  If on both sides, two
 200 //new windings will be created.
 201 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
 202 {
 203         winding_t *f, *b;
 204         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 205         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 206
 207         splitnormal[0] = splitnormalx;
 208         splitnormal[1] = splitnormaly;
 209         splitnormal[2] = splitnormalz;
 210
 211         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 212
 213         // determine sides for each point
 214         for (i = 0;i < in->numpoints;i++)
 215         {
 216                 dot = DotProduct(in->points[i], splitnormal);
 217                 dot -= splitdist;
 218                 dists[i] = dot;
 219                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 220                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 221                 else sides[i] = SIDE_ON;
 222                 counts[sides[i]]++;
 223         }
 224         sides[i] = sides[0];
 225         dists[i] = dists[0];
 226
 227         *front = *back = NULL;
 228
 229         if (!counts[0])
 230         {
 231                 *back = in;
 232                 return;
 233         }
 234         if (!counts[1])
 235         {
 236                 *front = in;
 237                 return;
 238         }
 239
 240         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
 241
 242         if (maxpts > MAX_POINTS_ON_WINDING)
 243                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
 244
 245         *front = f = Winding_New(maxpts);
 246         *back = b = Winding_New(maxpts);
 247
 248         for (i = 0;i < in->numpoints;i++)
 249         {
 250                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
 251                         Sys_Error("Winding_Divide: points exceeded estimate");
 252
 253                 p1 = in->points[i];
 254
 255                 if (sides[i] == SIDE_ON)
 256                 {
 257                         VectorCopy(p1, f->points[f->numpoints]);
 258                         f->numpoints++;
 259                         VectorCopy(p1, b->points[b->numpoints]);
 260                         b->numpoints++;
 261                         continue;
 262                 }
 263
 264                 if (sides[i] == SIDE_FRONT)
 265                 {
 266                         VectorCopy(p1, f->points[f->numpoints]);
 267                         f->numpoints++;
 268                 }
 269                 else if (sides[i] == SIDE_BACK)
 270                 {
 271                         VectorCopy(p1, b->points[b->numpoints]);
 272                         b->numpoints++;
 273                 }
 274
 275                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 276                         continue;
 277
 278                 // generate a split point
 279                 p2 = in->points[(i+1)%in->numpoints];
 280
 281                 dot = dists[i] / (dists[i]-dists[i+1]);
 282                 for (j = 0;j < 3;j++)
 283                 {       // avoid round off error when possible
 284                         if (splitnormal[j] == 1)
 285                                 mid[j] = splitdist;
 286                         else if (splitnormal[j] == -1)
 287                                 mid[j] = -splitdist;
 288                         else
 289                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 290                 }
 291
 292                 VectorCopy(mid, f->points[f->numpoints]);
 293                 f->numpoints++;
 294                 VectorCopy(mid, b->points[b->numpoints]);
 295                 b->numpoints++;
 296         }
 297 }
 298
 299