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]);
100 TriangleNormal(w->points[0], w->points[1], w->points[2], 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]);
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)
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];
122 splitnormal[0] = splitnormalx;
123 splitnormal[1] = splitnormaly;
124 splitnormal[2] = splitnormalz;
125 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
127 // determine sides for each point
128 for (i = 0;i < in->numpoints;i++)
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;
142 if (keepon && !counts[0] && !counts[1])
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");
157 neww = Winding_New(maxpts);
159 for (i = 0;i < in->numpoints;i++)
161 if (neww->numpoints >= maxpts)
162 Sys_Error("Winding_Clip: points exceeded estimate");
166 if (sides[i] == SIDE_ON)
168 VectorCopy(p1, neww->points[neww->numpoints]);
173 if (sides[i] == SIDE_FRONT)
175 VectorCopy(p1, neww->points[neww->numpoints]);
179 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
182 // generate a split point
183 p2 = in->points[(i+1)%in->numpoints];
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)
190 else if (splitnormal[j] == -1)
193 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
196 VectorCopy(mid, neww->points[neww->numpoints]);
200 // free the original winding
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)
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];
217 splitnormal[0] = splitnormalx;
218 splitnormal[1] = splitnormaly;
219 splitnormal[2] = splitnormalz;
221 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
223 // determine sides for each point
224 for (i = 0;i < in->numpoints;i++)
226 dot = DotProduct(in->points[i], splitnormal);
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;
237 *front = *back = NULL;
250 maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors
252 if (maxpts > MAX_POINTS_ON_WINDING)
253 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
255 *front = f = Winding_New(maxpts);
256 *back = b = Winding_New(maxpts);
258 for (i = 0;i < in->numpoints;i++)
260 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
261 Sys_Error("Winding_Divide: points exceeded estimate");
265 if (sides[i] == SIDE_ON)
267 VectorCopy(p1, f->points[f->numpoints]);
269 VectorCopy(p1, b->points[b->numpoints]);
274 if (sides[i] == SIDE_FRONT)
276 VectorCopy(p1, f->points[f->numpoints]);
279 else if (sides[i] == SIDE_BACK)
281 VectorCopy(p1, b->points[b->numpoints]);
285 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
288 // generate a split point
289 p2 = in->points[(i+1)%in->numpoints];
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)
296 else if (splitnormal[j] == -1)
299 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
302 VectorCopy(mid, f->points[f->numpoints]);
304 VectorCopy(mid, b->points[b->numpoints]);