5 // this code came from qbsp source
7 #define MAX_POINTS_ON_WINDING 64
9 winding_t *Winding_New(int points)
14 if (points > MAX_POINTS_ON_WINDING)
15 Sys_Error("Winding_New: too many points\n");
17 size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
18 w = Mem_Alloc(loadmodel->mempool, size);
25 void Winding_Free(winding_t *w)
30 winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist)
33 double max, v, org[3], vright[3], vup[3], normal[3];
40 VectorVectorsDouble(normal, vright, vup);
42 // find the major axis
44 max = fabs(normal[0]);
70 v = DotProduct(vup, normal);
71 VectorMA(vup, -v, normal, vup);
75 VectorScale(normal, dist, org);
77 CrossProduct(vup, normal, vright);
79 VectorScale(vup, 1024.0*1024.0*1024.0, vup);
80 VectorScale(vright, 1024.0*1024.0*1024.0, vright);
82 // project a really big axis aligned box onto the plane
85 VectorSubtract(org, vright, w->points[0]);
86 VectorAdd(w->points[0], vup, w->points[0]);
88 VectorAdd(org, vright, w->points[1]);
89 VectorAdd(w->points[1], vup, w->points[1]);
91 VectorAdd(org, vright, w->points[2]);
92 VectorSubtract(w->points[2], vup, w->points[2]);
94 VectorSubtract(org, vright, w->points[3]);
95 VectorSubtract(w->points[3], vup, w->points[3]);
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)
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];
112 splitnormal[0] = splitnormalx;
113 splitnormal[1] = splitnormaly;
114 splitnormal[2] = splitnormalz;
115 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
117 // determine sides for each point
118 for (i = 0;i < in->numpoints;i++)
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;
132 if (keepon && !counts[0] && !counts[1])
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");
147 neww = Winding_New(maxpts);
149 for (i = 0;i < in->numpoints;i++)
151 if (neww->numpoints >= maxpts)
152 Sys_Error("Winding_Clip: points exceeded estimate");
156 if (sides[i] == SIDE_ON)
158 VectorCopy(p1, neww->points[neww->numpoints]);
163 if (sides[i] == SIDE_FRONT)
165 VectorCopy(p1, neww->points[neww->numpoints]);
169 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
172 // generate a split point
173 p2 = in->points[(i+1)%in->numpoints];
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)
180 else if (splitnormal[j] == -1)
183 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
186 VectorCopy(mid, neww->points[neww->numpoints]);
190 // free the original winding
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)
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];
207 splitnormal[0] = splitnormalx;
208 splitnormal[1] = splitnormaly;
209 splitnormal[2] = splitnormalz;
211 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
213 // determine sides for each point
214 for (i = 0;i < in->numpoints;i++)
216 dot = DotProduct(in->points[i], splitnormal);
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;
227 *front = *back = NULL;
240 maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors
242 if (maxpts > MAX_POINTS_ON_WINDING)
243 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
245 *front = f = Winding_New(maxpts);
246 *back = b = Winding_New(maxpts);
248 for (i = 0;i < in->numpoints;i++)
250 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
251 Sys_Error("Winding_Divide: points exceeded estimate");
255 if (sides[i] == SIDE_ON)
257 VectorCopy(p1, f->points[f->numpoints]);
259 VectorCopy(p1, b->points[b->numpoints]);
264 if (sides[i] == SIDE_FRONT)
266 VectorCopy(p1, f->points[f->numpoints]);
269 else if (sides[i] == SIDE_BACK)
271 VectorCopy(p1, b->points[b->numpoints]);
275 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
278 // generate a split point
279 p2 = in->points[(i+1)%in->numpoints];
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)
286 else if (splitnormal[j] == -1)
289 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
292 VectorCopy(mid, f->points[f->numpoints]);
294 VectorCopy(mid, b->points[b->numpoints]);