-#define MAX_POINTS_ON_WINDING 64
-
-typedef struct
-{
- int numpoints;
- int padding;
- double points[8][3]; // variable sized
-}
-winding_t;
-
-/*
-==================
-NewWinding
-==================
-*/
-static winding_t *NewWinding(int points)
-{
- winding_t *w;
- int size;
-
- if (points > MAX_POINTS_ON_WINDING)
- Sys_Error("NewWinding: too many points\n");
-
- size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
- w = Mem_Alloc(loadmodel->mempool, size);
- memset(w, 0, size);
-
- return w;
-}
-
-static void FreeWinding(winding_t *w)
-{
- Mem_Free(w);
-}
-
-/*
-=================
-BaseWindingForPlane
-=================
-*/
-static winding_t *BaseWindingForPlane(mplane_t *p)
-{
- double org[3], vright[3], vup[3], normal[3];
- winding_t *w;
-
- VectorCopy(p->normal, normal);
- VectorVectorsDouble(normal, vright, vup);
-
- VectorScale(vup, 1024.0*1024.0*1024.0, vup);
- VectorScale(vright, 1024.0*1024.0*1024.0, vright);
-
- // project a really big axis aligned box onto the plane
- w = NewWinding(4);
-
- VectorScale(p->normal, p->dist, org);
-
- VectorSubtract(org, vright, w->points[0]);
- VectorAdd(w->points[0], vup, w->points[0]);
-
- VectorAdd(org, vright, w->points[1]);
- VectorAdd(w->points[1], vup, w->points[1]);
-
- VectorAdd(org, vright, w->points[2]);
- VectorSubtract(w->points[2], vup, w->points[2]);
-
- VectorSubtract(org, vright, w->points[3]);
- VectorSubtract(w->points[3], vup, w->points[3]);
-
- w->numpoints = 4;
-
- return w;
-}
-
-/*
-==================
-ClipWinding
-
-Clips the winding to the plane, returning the new winding on the positive side
-Frees the input winding.
-If keepon is true, an exactly on-plane winding will be saved, otherwise
-it will be clipped away.
-==================
-*/
-static winding_t *ClipWinding(winding_t *in, mplane_t *split, int keepon)
-{
- double dists[MAX_POINTS_ON_WINDING + 1];
- int sides[MAX_POINTS_ON_WINDING + 1];
- int counts[3];
- double dot;
- int i, j;
- double *p1, *p2;
- double mid[3];
- winding_t *neww;
- int maxpts;
-
- counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
-
- // determine sides for each point
- for (i = 0;i < in->numpoints;i++)
- {
- dists[i] = dot = DotProduct(in->points[i], split->normal) - split->dist;
- if (dot > ON_EPSILON)
- sides[i] = SIDE_FRONT;
- else if (dot < -ON_EPSILON)
- sides[i] = SIDE_BACK;
- else
- sides[i] = SIDE_ON;
- counts[sides[i]]++;
- }
- sides[i] = sides[0];
- dists[i] = dists[0];
-
- if (keepon && !counts[0] && !counts[1])
- return in;
-
- if (!counts[0])
- {
- FreeWinding(in);
- return NULL;
- }
- if (!counts[1])
- return in;
-
- maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors
- if (maxpts > MAX_POINTS_ON_WINDING)
- Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
-
- neww = NewWinding(maxpts);
-
- for (i = 0;i < in->numpoints;i++)
- {
- if (neww->numpoints >= maxpts)
- Sys_Error("ClipWinding: points exceeded estimate");
-
- p1 = in->points[i];
-
- if (sides[i] == SIDE_ON)
- {
- VectorCopy(p1, neww->points[neww->numpoints]);
- neww->numpoints++;
- continue;
- }
-
- if (sides[i] == SIDE_FRONT)
- {
- VectorCopy(p1, neww->points[neww->numpoints]);
- neww->numpoints++;
- }
-
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
- continue;
-
- // generate a split point
- p2 = in->points[(i+1)%in->numpoints];
-
- dot = dists[i] / (dists[i]-dists[i+1]);
- for (j = 0;j < 3;j++)
- { // avoid round off error when possible
- if (split->normal[j] == 1)
- mid[j] = split->dist;
- else if (split->normal[j] == -1)
- mid[j] = -split->dist;
- else
- mid[j] = p1[j] + dot* (p2[j]-p1[j]);
- }
-
- VectorCopy(mid, neww->points[neww->numpoints]);
- neww->numpoints++;
- }
-
- // free the original winding
- FreeWinding(in);
-
- return neww;
-}
-
-
-/*
-==================
-DivideWinding
-
-Divides a winding by a plane, producing one or two windings. The
-original winding is not damaged or freed. If only on one side, the
-returned winding will be the input winding. If on both sides, two
-new windings will be created.
-==================
-*/
-static void DivideWinding(winding_t *in, mplane_t *split, winding_t **front, winding_t **back)
-{
- double dists[MAX_POINTS_ON_WINDING + 1];
- int sides[MAX_POINTS_ON_WINDING + 1];
- int counts[3];
- double dot;
- int i, j;
- double *p1, *p2;
- double mid[3];
- winding_t *f, *b;
- int maxpts;
-
- counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
-
- // determine sides for each point
- for (i = 0;i < in->numpoints;i++)
- {
- dot = DotProduct(in->points[i], split->normal);
- dot -= split->dist;
- dists[i] = dot;
- if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
- else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
- else sides[i] = SIDE_ON;
- counts[sides[i]]++;
- }
- sides[i] = sides[0];
- dists[i] = dists[0];
-
- *front = *back = NULL;
-
- if (!counts[0])
- {
- *back = in;
- return;
- }
- if (!counts[1])
- {
- *front = in;
- return;
- }
-
- maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors
-
- if (maxpts > MAX_POINTS_ON_WINDING)
- Sys_Error("ClipWinding: maxpts > MAX_POINTS_ON_WINDING");
-
- *front = f = NewWinding(maxpts);
- *back = b = NewWinding(maxpts);
-
- for (i = 0;i < in->numpoints;i++)
- {
- if (f->numpoints >= maxpts || b->numpoints >= maxpts)
- Sys_Error("DivideWinding: points exceeded estimate");
-
- p1 = in->points[i];
-
- if (sides[i] == SIDE_ON)
- {
- VectorCopy(p1, f->points[f->numpoints]);
- f->numpoints++;
- VectorCopy(p1, b->points[b->numpoints]);
- b->numpoints++;
- continue;
- }
-
- if (sides[i] == SIDE_FRONT)
- {
- VectorCopy(p1, f->points[f->numpoints]);
- f->numpoints++;
- }
- else if (sides[i] == SIDE_BACK)
- {
- VectorCopy(p1, b->points[b->numpoints]);
- b->numpoints++;
- }
-
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
- continue;
-
- // generate a split point
- p2 = in->points[(i+1)%in->numpoints];
-
- dot = dists[i] / (dists[i]-dists[i+1]);
- for (j = 0;j < 3;j++)
- { // avoid round off error when possible
- if (split->normal[j] == 1)
- mid[j] = split->dist;
- else if (split->normal[j] == -1)
- mid[j] = -split->dist;
- else
- mid[j] = p1[j] + dot* (p2[j]-p1[j]);
- }
-
- VectorCopy(mid, f->points[f->numpoints]);
- f->numpoints++;
- VectorCopy(mid, b->points[b->numpoints]);
- b->numpoints++;
- }
-}
-