5 // this code came from qbsp source
7 #define MAX_POINTS_ON_WINDING 64
9 winding_t *Winding_New(int points)
12 w = Mem_Alloc(loadmodel->mempool, sizeof(winding_t) + sizeof(double[3]) * (points - 8));
13 w->maxpoints = points;
17 void Winding_Free(winding_t *w)
22 winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist)
26 BufWinding_NewFromPlane(w, normalx, normaly, normalz, dist);
30 //Clips the winding to the plane, returning the new winding on the positive side
31 //Frees the input winding.
32 //If keepon is true, an exactly on-plane winding will be saved, otherwise
33 //it will be clipped away.
34 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
37 double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
38 int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
40 splitnormal[0] = splitnormalx;
41 splitnormal[1] = splitnormaly;
42 splitnormal[2] = splitnormalz;
43 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
45 // determine sides for each point
46 for (i = 0;i < in->numpoints;i++)
48 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
50 sides[i] = SIDE_FRONT;
51 else if (dot < -ON_EPSILON)
60 if (keepon && !counts[0] && !counts[1])
72 for (i = 0;i < in->numpoints;i++)
74 if (sides[i] == SIDE_ON)
79 if (sides[i] == SIDE_FRONT)
81 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
86 if (maxpts > MAX_POINTS_ON_WINDING)
87 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
89 neww = Winding_New(maxpts);
91 for (i = 0;i < in->numpoints;i++)
95 if (sides[i] == SIDE_ON)
97 VectorCopy(p1, neww->points[neww->numpoints]);
102 if (sides[i] == SIDE_FRONT)
104 VectorCopy(p1, neww->points[neww->numpoints]);
108 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
111 // generate a split point
112 p2 = in->points[(i+1)%in->numpoints];
114 dot = dists[i] / (dists[i]-dists[i+1]);
115 for (j = 0;j < 3;j++)
116 { // avoid round off error when possible
117 if (splitnormal[j] == 1)
119 else if (splitnormal[j] == -1)
122 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
125 VectorCopy(mid, neww->points[neww->numpoints]);
129 // free the original winding
136 //Divides a winding by a plane, producing one or two windings. The
137 //original winding is not damaged or freed. If only on one side, the
138 //returned winding will be the input winding. If on both sides, two
139 //new windings will be created.
140 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
143 double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
144 int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
146 splitnormal[0] = splitnormalx;
147 splitnormal[1] = splitnormaly;
148 splitnormal[2] = splitnormalz;
150 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
152 // determine sides for each point
153 for (i = 0;i < in->numpoints;i++)
155 dot = DotProduct(in->points[i], splitnormal);
158 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
159 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
160 else sides[i] = SIDE_ON;
166 *front = *back = NULL;
182 for (i = 0;i < in->numpoints;i++)
184 if (sides[i] == SIDE_ON)
190 if (sides[i] == SIDE_FRONT)
192 else if (sides[i] == SIDE_BACK)
194 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
200 if (frontpts > MAX_POINTS_ON_WINDING)
201 Sys_Error("Winding_Clip: frontpts > MAX_POINTS_ON_WINDING");
202 if (backpts > MAX_POINTS_ON_WINDING)
203 Sys_Error("Winding_Clip: backpts > MAX_POINTS_ON_WINDING");
205 *front = f = Winding_New(frontpts);
206 *back = b = Winding_New(backpts);
208 for (i = 0;i < in->numpoints;i++)
212 if (sides[i] == SIDE_ON)
214 VectorCopy(p1, f->points[f->numpoints]);
216 VectorCopy(p1, b->points[b->numpoints]);
221 if (sides[i] == SIDE_FRONT)
223 VectorCopy(p1, f->points[f->numpoints]);
226 else if (sides[i] == SIDE_BACK)
228 VectorCopy(p1, b->points[b->numpoints]);
232 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
235 // generate a split point
236 p2 = in->points[(i+1)%in->numpoints];
238 dot = dists[i] / (dists[i]-dists[i+1]);
239 for (j = 0;j < 3;j++)
240 { // avoid round off error when possible
241 if (splitnormal[j] == 1)
243 else if (splitnormal[j] == -1)
246 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
249 VectorCopy(mid, f->points[f->numpoints]);
251 VectorCopy(mid, b->points[b->numpoints]);
256 // LordHavoc: these functions are more efficient by not allocating/freeing memory all the time
258 void BufWinding_NewFromPlane(winding_t *w, double normalx, double normaly, double normalz, double dist)
261 double max, v, org[3], vright[3], vup[3], normal[3];
264 if (w->maxpoints < 4)
273 VectorVectorsDouble(normal, vright, vup);
275 // find the major axis
277 max = fabs(normal[0]);
303 v = DotProduct(vup, normal);
304 VectorMA(vup, -v, normal, vup);
305 VectorNormalize(vup);
308 VectorScale(normal, dist, org);
310 CrossProduct(vup, normal, vright);
312 VectorScale(vup, 1024.0*1024.0*1024.0, vup);
313 VectorScale(vright, 1024.0*1024.0*1024.0, vright);
315 // project a really big axis aligned box onto the plane
316 VectorSubtract(org, vright, w->points[0]);
317 VectorAdd(w->points[0], vup, w->points[0]);
319 VectorAdd(org, vright, w->points[1]);
320 VectorAdd(w->points[1], vup, w->points[1]);
322 VectorAdd(org, vright, w->points[2]);
323 VectorSubtract(w->points[2], vup, w->points[2]);
325 VectorSubtract(org, vright, w->points[3]);
326 VectorSubtract(w->points[3], vup, w->points[3]);
331 TriangleNormal(w->points[0], w->points[1], w->points[2], n);
333 if (fabs(DotProduct(n, normal) - 1) > 0.01f)
334 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]);
339 void BufWinding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t *outfront, int *neededfrontpoints, winding_t *outback, int *neededbackpoints)
341 double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
342 int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
345 outfront->numpoints = 0;
347 outback->numpoints = 0;
349 if (in->numpoints > MAX_POINTS_ON_WINDING || (!outfront && !outback))
351 if (neededfrontpoints)
352 *neededfrontpoints = 0;
353 if (neededbackpoints)
354 *neededbackpoints = 0;
358 splitnormal[0] = splitnormalx;
359 splitnormal[1] = splitnormaly;
360 splitnormal[2] = splitnormalz;
362 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
364 // determine sides for each point
365 for (i = 0;i < in->numpoints;i++)
367 dot = DotProduct(in->points[i], splitnormal);
370 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
371 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
372 else sides[i] = SIDE_ON;
380 for (i = 0;i < in->numpoints;i++)
382 if (sides[i] != SIDE_ON)
384 if (sides[i] == SIDE_FRONT)
386 else if (sides[i] == SIDE_BACK)
388 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
395 if (neededfrontpoints)
396 *neededfrontpoints = frontpts;
397 if (neededbackpoints)
398 *neededbackpoints = backpts;
399 if ((outfront && outfront->maxpoints < frontpts) || (outback && outback->maxpoints < backpts))
402 for (i = 0;i < in->numpoints;i++)
406 if (sides[i] == SIDE_ON)
410 VectorCopy(p1, outfront->points[outfront->numpoints]);
411 outfront->numpoints++;
415 VectorCopy(p1, outback->points[outback->numpoints]);
416 outback->numpoints++;
421 if (sides[i] == SIDE_FRONT)
425 VectorCopy(p1, outfront->points[outfront->numpoints]);
426 outfront->numpoints++;
429 else if (sides[i] == SIDE_BACK)
433 VectorCopy(p1, outback->points[outback->numpoints]);
434 outback->numpoints++;
438 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
441 // generate a split point
442 p2 = in->points[(i+1)%in->numpoints];
444 dot = dists[i] / (dists[i]-dists[i+1]);
445 for (j = 0;j < 3;j++)
446 { // avoid round off error when possible
447 if (splitnormal[j] == 1)
449 else if (splitnormal[j] == -1)
452 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
457 VectorCopy(mid, outfront->points[outfront->numpoints]);
458 outfront->numpoints++;
462 VectorCopy(mid, outback->points[outback->numpoints]);
463 outback->numpoints++;
468 void Polygon_Divide_Double(int innumpoints, const double *inpoints, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int outfrontmaxpoints, double *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, double *outbackpoints, int *neededbackpoints)
470 double dot, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
471 const double *p1, *p2;
472 int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
474 if (neededfrontpoints)
475 *neededfrontpoints = 0;
476 if (neededbackpoints)
477 *neededbackpoints = 0;
479 if (innumpoints > MAX_POINTS_ON_WINDING || (!outfrontmaxpoints && !outbackmaxpoints))
482 splitnormal[0] = splitnormalx;
483 splitnormal[1] = splitnormaly;
484 splitnormal[2] = splitnormalz;
486 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
488 // determine sides for each point
489 for (i = 0;i < innumpoints;i++)
491 dot = DotProduct(inpoints + i * 3, splitnormal);
494 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
495 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
496 else sides[i] = SIDE_ON;
504 for (i = 0;i < innumpoints;i++)
506 if (sides[i] != SIDE_ON)
508 if (sides[i] == SIDE_FRONT)
510 else if (sides[i] == SIDE_BACK)
512 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
519 if (neededfrontpoints)
520 *neededfrontpoints = frontpts;
521 if (neededbackpoints)
522 *neededbackpoints = backpts;
523 if ((outfrontmaxpoints && outfrontmaxpoints < frontpts) || (outbackmaxpoints && outbackmaxpoints < backpts))
526 for (i = 0;i < innumpoints;i++)
528 p1 = inpoints + i * 3;
530 if (sides[i] == SIDE_ON)
532 if (outfrontmaxpoints)
534 VectorCopy(p1, outfrontpoints);
537 if (outbackmaxpoints)
539 VectorCopy(p1, outbackpoints);
545 if (sides[i] == SIDE_FRONT)
547 if (outfrontmaxpoints)
549 VectorCopy(p1, outfrontpoints);
553 else if (sides[i] == SIDE_BACK)
555 if (outbackmaxpoints)
557 VectorCopy(p1, outbackpoints);
562 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
565 // generate a split point
566 p2 = inpoints + ((i+1)%innumpoints) * 3;
568 dot = dists[i] / (dists[i]-dists[i+1]);
569 for (j = 0;j < 3;j++)
570 { // avoid round off error when possible
571 if (splitnormal[j] == 1)
573 else if (splitnormal[j] == -1)
576 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
579 if (outfrontmaxpoints)
581 VectorCopy(mid, outfrontpoints);
584 if (outbackmaxpoints)
586 VectorCopy(mid, outbackpoints);
592 void Polygon_Divide_Float(int innumpoints, const float *inpoints, float splitnormalx, float splitnormaly, float splitnormalz, float splitdist, int outfrontmaxpoints, float *outfrontpoints, int *neededfrontpoints, int outbackmaxpoints, float *outbackpoints, int *neededbackpoints)
594 float dot, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
595 const float *p1, *p2;
596 int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
598 if (neededfrontpoints)
599 *neededfrontpoints = 0;
600 if (neededbackpoints)
601 *neededbackpoints = 0;
603 if (innumpoints > MAX_POINTS_ON_WINDING || (!outfrontmaxpoints && !outbackmaxpoints))
606 splitnormal[0] = splitnormalx;
607 splitnormal[1] = splitnormaly;
608 splitnormal[2] = splitnormalz;
610 counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
612 // determine sides for each point
613 for (i = 0;i < innumpoints;i++)
615 dot = DotProduct(inpoints + i * 3, splitnormal);
618 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
619 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
620 else sides[i] = SIDE_ON;
628 for (i = 0;i < innumpoints;i++)
630 if (sides[i] != SIDE_ON)
632 if (sides[i] == SIDE_FRONT)
634 else if (sides[i] == SIDE_BACK)
636 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
643 if (neededfrontpoints)
644 *neededfrontpoints = frontpts;
645 if (neededbackpoints)
646 *neededbackpoints = backpts;
647 if ((outfrontmaxpoints && outfrontmaxpoints < frontpts) || (outbackmaxpoints && outbackmaxpoints < backpts))
650 for (i = 0;i < innumpoints;i++)
652 p1 = inpoints + i * 3;
654 if (sides[i] == SIDE_ON)
656 if (outfrontmaxpoints)
658 VectorCopy(p1, outfrontpoints);
661 if (outbackmaxpoints)
663 VectorCopy(p1, outbackpoints);
669 if (sides[i] == SIDE_FRONT)
671 if (outfrontmaxpoints)
673 VectorCopy(p1, outfrontpoints);
677 else if (sides[i] == SIDE_BACK)
679 if (outbackmaxpoints)
681 VectorCopy(p1, outbackpoints);
686 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
689 // generate a split point
690 p2 = inpoints + ((i+1)%innumpoints) * 3;
692 dot = dists[i] / (dists[i]-dists[i+1]);
693 for (j = 0;j < 3;j++)
694 { // avoid round off error when possible
695 if (splitnormal[j] == 1)
697 else if (splitnormal[j] == -1)
700 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
703 if (outfrontmaxpoints)
705 VectorCopy(mid, outfrontpoints);
708 if (outbackmaxpoints)
710 VectorCopy(mid, outbackpoints);