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 #if 0
  98         {
  99                 double n[3];
 100                 TriangleNormal(w->points[0], w->points[1], w->points[2], n);
 101                 VectorNormalize(n);
 102                 if (fabs(DotProduct(n, normal) - 1) > 0.01f)
 103                         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]);
 104         }
 105 #endif
 106
 107         w->numpoints = 4;
 108
 109         return w;
 110 }
 111
 112 //Clips the winding to the plane, returning the new winding on the positive side
 113 //Frees the input winding.
 114 //If keepon is true, an exactly on-plane winding will be saved, otherwise
 115 //it will be clipped away.
 116 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
 117 {
 118         winding_t *neww;
 119         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 120         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 121
 122         splitnormal[0] = splitnormalx;
 123         splitnormal[1] = splitnormaly;
 124         splitnormal[2] = splitnormalz;
 125         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 126
 127         // determine sides for each point
 128         for (i = 0;i < in->numpoints;i++)
 129         {
 130                 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
 131                 if (dot > ON_EPSILON)
 132                         sides[i] = SIDE_FRONT;
 133                 else if (dot < -ON_EPSILON)
 134                         sides[i] = SIDE_BACK;
 135                 else
 136                         sides[i] = SIDE_ON;
 137                 counts[sides[i]]++;
 138         }
 139         sides[i] = sides[0];
 140         dists[i] = dists[0];
 141
 142         if (keepon && !counts[0] && !counts[1])
 143                 return in;
 144
 145         if (!counts[0])
 146         {
 147                 Winding_Free(in);
 148                 return NULL;
 149         }
 150         if (!counts[1])
 151                 return in;
 152
 153         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
 154         if (maxpts > MAX_POINTS_ON_WINDING)
 155                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
 156
 157         neww = Winding_New(maxpts);
 158
 159         for (i = 0;i < in->numpoints;i++)
 160         {
 161                 if (neww->numpoints >= maxpts)
 162                         Sys_Error("Winding_Clip: points exceeded estimate");
 163
 164                 p1 = in->points[i];
 165
 166                 if (sides[i] == SIDE_ON)
 167                 {
 168                         VectorCopy(p1, neww->points[neww->numpoints]);
 169                         neww->numpoints++;
 170                         continue;
 171                 }
 172
 173                 if (sides[i] == SIDE_FRONT)
 174                 {
 175                         VectorCopy(p1, neww->points[neww->numpoints]);
 176                         neww->numpoints++;
 177                 }
 178
 179                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 180                         continue;
 181
 182                 // generate a split point
 183                 p2 = in->points[(i+1)%in->numpoints];
 184
 185                 dot = dists[i] / (dists[i]-dists[i+1]);
 186                 for (j = 0;j < 3;j++)
 187                 {       // avoid round off error when possible
 188                         if (splitnormal[j] == 1)
 189                                 mid[j] = splitdist;
 190                         else if (splitnormal[j] == -1)
 191                                 mid[j] = -splitdist;
 192                         else
 193                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 194                 }
 195
 196                 VectorCopy(mid, neww->points[neww->numpoints]);
 197                 neww->numpoints++;
 198         }
 199
 200         // free the original winding
 201         Winding_Free(in);
 202
 203         return neww;
 204 }
 205
 206
 207 //Divides a winding by a plane, producing one or two windings.  The
 208 //original winding is not damaged or freed.  If only on one side, the
 209 //returned winding will be the input winding.  If on both sides, two
 210 //new windings will be created.
 211 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
 212 {
 213         winding_t *f, *b;
 214         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
 215         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
 216
 217         splitnormal[0] = splitnormalx;
 218         splitnormal[1] = splitnormaly;
 219         splitnormal[2] = splitnormalz;
 220
 221         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
 222
 223         // determine sides for each point
 224         for (i = 0;i < in->numpoints;i++)
 225         {
 226                 dot = DotProduct(in->points[i], splitnormal);
 227                 dot -= splitdist;
 228                 dists[i] = dot;
 229                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
 230                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
 231                 else sides[i] = SIDE_ON;
 232                 counts[sides[i]]++;
 233         }
 234         sides[i] = sides[0];
 235         dists[i] = dists[0];
 236
 237         *front = *back = NULL;
 238
 239         if (!counts[0])
 240         {
 241                 *back = in;
 242                 return;
 243         }
 244         if (!counts[1])
 245         {
 246                 *front = in;
 247                 return;
 248         }
 249
 250         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
 251
 252         if (maxpts > MAX_POINTS_ON_WINDING)
 253                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
 254
 255         *front = f = Winding_New(maxpts);
 256         *back = b = Winding_New(maxpts);
 257
 258         for (i = 0;i < in->numpoints;i++)
 259         {
 260                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
 261                         Sys_Error("Winding_Divide: points exceeded estimate");
 262
 263                 p1 = in->points[i];
 264
 265                 if (sides[i] == SIDE_ON)
 266                 {
 267                         VectorCopy(p1, f->points[f->numpoints]);
 268                         f->numpoints++;
 269                         VectorCopy(p1, b->points[b->numpoints]);
 270                         b->numpoints++;
 271                         continue;
 272                 }
 273
 274                 if (sides[i] == SIDE_FRONT)
 275                 {
 276                         VectorCopy(p1, f->points[f->numpoints]);
 277                         f->numpoints++;
 278                 }
 279                 else if (sides[i] == SIDE_BACK)
 280                 {
 281                         VectorCopy(p1, b->points[b->numpoints]);
 282                         b->numpoints++;
 283                 }
 284
 285                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 286                         continue;
 287
 288                 // generate a split point
 289                 p2 = in->points[(i+1)%in->numpoints];
 290
 291                 dot = dists[i] / (dists[i]-dists[i+1]);
 292                 for (j = 0;j < 3;j++)
 293                 {       // avoid round off error when possible
 294                         if (splitnormal[j] == 1)
 295                                 mid[j] = splitdist;
 296                         else if (splitnormal[j] == -1)
 297                                 mid[j] = -splitdist;
 298                         else
 299                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
 300                 }
 301
 302                 VectorCopy(mid, f->points[f->numpoints]);
 303                 f->numpoints++;
 304                 VectorCopy(mid, b->points[b->numpoints]);
 305                 b->numpoints++;
 306         }
 307 }
 308
 309