2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
28 #define BOGUS_RANGE (g_MaxWorldCoord+1)
35 #define NORMAL_EPSILON 0.0001
36 #define DIST_EPSILON 0.02
38 int Plane_Equal(plane_t *a, plane_t *b, int flip)
44 normal[0] = - b->normal[0];
45 normal[1] = - b->normal[1];
46 normal[2] = - b->normal[2];
50 normal[0] = b->normal[0];
51 normal[1] = b->normal[1];
52 normal[2] = b->normal[2];
56 fabs(a->normal[0] - normal[0]) < NORMAL_EPSILON
57 && fabs(a->normal[1] - normal[1]) < NORMAL_EPSILON
58 && fabs(a->normal[2] - normal[2]) < NORMAL_EPSILON
59 && fabs(a->dist - dist) < DIST_EPSILON )
69 int Plane_FromPoints(vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane)
73 VectorSubtract(p2, p1, v1);
74 VectorSubtract(p3, p1, v2);
75 //CrossProduct(v2, v1, plane->normal);
76 CrossProduct(v1, v2, plane->normal);
77 if (VectorNormalize(plane->normal, plane->normal) < 0.1) return false;
78 plane->dist = DotProduct(p1, plane->normal);
87 int Point_Equal(vec3_t p1, vec3_t p2, float epsilon)
91 for (i = 0; i < 3; i++)
93 if (fabs(p1[i] - p2[i]) > epsilon) return false;
105 winding_t *Winding_BaseForPlane (plane_t *p)
109 vec3_t org, vright, vup;
112 // find the major axis
114 Sys_Printf("Winding_BaseForPlane %p\n",p);
121 v = fabs(p->normal[i]);
129 Error ("Winding_BaseForPlane: no axis found");
131 VectorCopy (vec3_origin, vup);
144 v = DotProduct (vup, p->normal);
145 VectorMA (vup, -v, p->normal, vup);
146 VectorNormalize (vup, vup);
148 VectorScale (p->normal, p->dist, org);
150 CrossProduct (vup, p->normal, vright);
152 VectorScale (vup, BOGUS_RANGE, vup);
153 VectorScale (vright, BOGUS_RANGE, vright);
155 // project a really big axis aligned box onto the plane
156 w = Winding_Alloc (4);
158 VectorSubtract (org, vright, w->points[0]);
159 VectorAdd (w->points[0], vup, w->points[0]);
161 VectorAdd (org, vright, w->points[1]);
162 VectorAdd (w->points[1], vup, w->points[1]);
164 VectorAdd (org, vright, w->points[2]);
165 VectorSubtract (w->points[2], vup, w->points[2]);
167 VectorSubtract (org, vright, w->points[3]);
168 VectorSubtract (w->points[3], vup, w->points[3]);
175 // macro to compute winding size
176 #define WINDING_SIZE(pt) (sizeof(int)*2+sizeof(float)*5*(pt))
183 winding_t *Winding_Alloc (int points)
188 if (points > MAX_POINTS_ON_WINDING)
189 Error ("Winding_Alloc: %i points", points);
191 // size = (int)((winding_t *)0)->points[points];
192 size = WINDING_SIZE(points);
193 w = (winding_t*) malloc (size);
195 w->maxpoints = points;
200 void Winding_Free (winding_t *w)
210 winding_t *Winding_Clone(winding_t *w)
215 // size = (int)((winding_t *)0)->points[w->numpoints];
216 size = WINDING_SIZE(w->numpoints);
217 c = (winding_t*)qmalloc (size);
227 winding_t *Winding_Reverse(winding_t *w)
232 c = Winding_Alloc(w->numpoints);
233 for (i = 0; i < w->numpoints; i++)
235 VectorCopy (w->points[w->numpoints-1-i], c->points[i]);
237 c->numpoints = w->numpoints;
246 void Winding_RemovePoint(winding_t *w, int point)
248 if (point < 0 || point >= w->numpoints)
249 Error("Winding_RemovePoint: point out of range");
251 if (point < w->numpoints-1)
253 memmove(&w->points[point], &w->points[point+1], (int)((winding_t *)0)->points[w->numpoints - point - 1]);
263 winding_t *Winding_InsertPoint(winding_t *w, vec3_t point, int spot)
268 if (spot > w->numpoints)
270 Error("Winding_InsertPoint: spot > w->numpoints");
274 Error("Winding_InsertPoint: spot < 0");
276 neww = Winding_Alloc(w->numpoints + 1);
277 neww->numpoints = w->numpoints + 1;
278 for (i = 0, j = 0; i < neww->numpoints; i++)
282 VectorCopy(point, neww->points[i]);
286 VectorCopy(w->points[j], neww->points[i]);
298 #define EDGE_LENGTH 0.2
300 int Winding_IsTiny (winding_t *w)
308 for (i=0 ; i<w->numpoints ; i++)
310 j = i == w->numpoints - 1 ? 0 : i+1;
311 VectorSubtract (w->points[j], w->points[i], delta);
312 len = VectorLength (delta);
313 if (len > EDGE_LENGTH)
327 int Winding_IsHuge(winding_t *w)
331 for (i=0 ; i<w->numpoints ; i++)
333 for (j=0 ; j<3 ; j++)
334 if (w->points[i][j] < -BOGUS_RANGE+1 || w->points[i][j] > BOGUS_RANGE-1)
342 Winding_PlanesConcave
345 #define WCONVEX_EPSILON 0.2
347 int Winding_PlanesConcave(winding_t *w1, winding_t *w2,
348 vec3_t normal1, vec3_t normal2,
349 float dist1, float dist2)
353 if (!w1 || !w2) return false;
355 // check if one of the points of winding 1 is at the back of the plane of winding 2
356 for (i = 0; i < w1->numpoints; i++)
358 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return true;
360 // check if one of the points of winding 2 is at the back of the plane of winding 1
361 for (i = 0; i < w2->numpoints; i++)
363 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return true;
373 Clips the winding to the plane, returning the new winding on the positive side
374 Frees the input winding.
375 If keepon is true, an exactly on-plane winding will be saved, otherwise
376 it will be clipped away.
379 winding_t *Winding_Clip (winding_t *in, plane_t *split, qboolean keepon)
381 vec_t dists[MAX_POINTS_ON_WINDING];
382 int sides[MAX_POINTS_ON_WINDING];
391 counts[0] = counts[1] = counts[2] = 0;
393 // determine sides for each point
394 for (i=0 ; i<in->numpoints ; i++)
396 dot = DotProduct (in->points[i], split->normal);
399 if (dot > ON_EPSILON)
400 sides[i] = SIDE_FRONT;
401 else if (dot < -ON_EPSILON)
402 sides[i] = SIDE_BACK;
412 if (keepon && !counts[0] && !counts[1])
423 maxpts = in->numpoints+4; // can't use counts[0]+2 because
424 // of fp grouping errors
425 neww = Winding_Alloc (maxpts);
427 for (i=0 ; i<in->numpoints ; i++)
431 if (sides[i] == SIDE_ON)
433 VectorCopy (p1, neww->points[neww->numpoints]);
438 if (sides[i] == SIDE_FRONT)
440 VectorCopy (p1, neww->points[neww->numpoints]);
444 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
447 // generate a split point
448 p2 = in->points[(i+1)%in->numpoints];
450 dot = dists[i] / (dists[i]-dists[i+1]);
451 for (j=0 ; j<3 ; j++)
452 { // avoid round off error when possible
453 if (split->normal[j] == 1)
454 mid[j] = split->dist;
455 else if (split->normal[j] == -1)
456 mid[j] = -split->dist;
458 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
461 VectorCopy (mid, neww->points[neww->numpoints]);
465 if (neww->numpoints > maxpts)
466 Error ("Winding_Clip: points exceeded estimate");
468 // free the original winding
478 split the input winding with the plane
479 the input winding stays untouched
482 void Winding_SplitEpsilon (winding_t *in, vec3_t normal, double dist,
483 vec_t epsilon, winding_t **front, winding_t **back)
485 vec_t dists[MAX_POINTS_ON_WINDING+4];
486 int sides[MAX_POINTS_ON_WINDING+4];
495 counts[0] = counts[1] = counts[2] = 0;
497 // determine sides for each point
498 for (i = 0; i < in->numpoints; i++)
500 dot = DotProduct (in->points[i], normal);
504 sides[i] = SIDE_FRONT;
505 else if (dot < -epsilon)
506 sides[i] = SIDE_BACK;
516 *front = *back = NULL;
520 *back = Winding_Clone(in);
525 *front = Winding_Clone(in);
529 maxpts = in->numpoints+4; // cant use counts[0]+2 because
530 // of fp grouping errors
532 *front = f = Winding_Alloc (maxpts);
533 *back = b = Winding_Alloc (maxpts);
535 for (i = 0; i < in->numpoints; i++)
539 if (sides[i] == SIDE_ON)
541 VectorCopy (p1, f->points[f->numpoints]);
543 VectorCopy (p1, b->points[b->numpoints]);
548 if (sides[i] == SIDE_FRONT)
550 VectorCopy (p1, f->points[f->numpoints]);
553 if (sides[i] == SIDE_BACK)
555 VectorCopy (p1, b->points[b->numpoints]);
559 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
562 // generate a split point
563 p2 = in->points[(i+1)%in->numpoints];
565 dot = dists[i] / (dists[i]-dists[i+1]);
566 for (j = 0; j < 3; j++)
568 // avoid round off error when possible
571 else if (normal[j] == -1)
574 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
577 VectorCopy (mid, f->points[f->numpoints]);
579 VectorCopy (mid, b->points[b->numpoints]);
583 if (f->numpoints > maxpts || b->numpoints > maxpts)
584 Error ("Winding_Clip: points exceeded estimate");
585 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
586 Error ("Winding_Clip: MAX_POINTS_ON_WINDING");
593 If two windings share a common edge and the edges that meet at the
594 common points are both inside the other polygons, merge them
596 Returns NULL if the windings couldn't be merged, or the new winding.
597 The originals will NOT be freed.
599 if keep is true no points are ever removed
602 #define CONTINUOUS_EPSILON 0.005
604 winding_t *Winding_TryMerge(winding_t *f1, winding_t *f2, vec3_t planenormal, int keep)
606 vec_t *p1, *p2, *p3, *p4, *back;
609 vec3_t normal, delta;
611 qboolean keep1, keep2;
615 // find a common edge
617 p1 = p2 = NULL; // stop compiler warning
620 for (i = 0; i < f1->numpoints; i++)
623 p2 = f1->points[(i+1) % f1->numpoints];
624 for (j = 0; j < f2->numpoints; j++)
627 p4 = f2->points[(j+1) % f2->numpoints];
628 for (k = 0; k < 3; k++)
630 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
632 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
638 if (j < f2->numpoints)
642 if (i == f1->numpoints)
643 return NULL; // no matching edges
646 // check slope of connected lines
647 // if the slopes are colinear, the point can be removed
649 back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
650 VectorSubtract (p1, back, delta);
651 CrossProduct (planenormal, delta, normal);
652 VectorNormalize (normal, normal);
654 back = f2->points[(j+2)%f2->numpoints];
655 VectorSubtract (back, p1, delta);
656 dot = DotProduct (delta, normal);
657 if (dot > CONTINUOUS_EPSILON)
658 return NULL; // not a convex polygon
659 keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
661 back = f1->points[(i+2)%f1->numpoints];
662 VectorSubtract (back, p2, delta);
663 CrossProduct (planenormal, delta, normal);
664 VectorNormalize (normal, normal);
666 back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
667 VectorSubtract (back, p2, delta);
668 dot = DotProduct (delta, normal);
669 if (dot > CONTINUOUS_EPSILON)
670 return NULL; // not a convex polygon
671 keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
674 // build the new polygon
676 newf = Winding_Alloc (f1->numpoints + f2->numpoints);
678 // copy first polygon
679 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
681 if (!keep && k==(i+1)%f1->numpoints && !keep2)
684 VectorCopy (f1->points[k], newf->points[newf->numpoints]);
688 // copy second polygon
689 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
691 if (!keep && l==(j+1)%f2->numpoints && !keep1)
693 VectorCopy (f2->points[l], newf->points[newf->numpoints]);
705 void Winding_Plane (winding_t *w, vec3_t normal, double *dist)
710 //find two vectors each longer than 0.5 units
711 for (i = 0; i < w->numpoints; i++)
713 VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], v1);
714 VectorSubtract(w->points[(i+2) % w->numpoints], w->points[i], v2);
715 if (VectorLength(v1) > 0.5 && VectorLength(v2) > 0.5) break;
717 CrossProduct(v2, v1, normal);
718 VectorNormalize(normal, normal);
719 *dist = DotProduct(w->points[0], normal);
727 float Winding_Area (winding_t *w)
730 vec3_t d1, d2, cross;
734 for (i=2 ; i<w->numpoints ; i++)
736 VectorSubtract (w->points[i-1], w->points[0], d1);
737 VectorSubtract (w->points[i], w->points[0], d2);
738 CrossProduct (d1, d2, cross);
739 total += 0.5 * VectorLength ( cross );
749 void Winding_Bounds (winding_t *w, vec3_t mins, vec3_t maxs)
754 mins[0] = mins[1] = mins[2] = 99999;
755 maxs[0] = maxs[1] = maxs[2] = -99999;
757 for (i=0 ; i<w->numpoints ; i++)
759 for (j=0 ; j<3 ; j++)
776 int Winding_PointInside(winding_t *w, plane_t *plane, vec3_t point, float epsilon)
779 vec3_t dir, normal, pointvec;
781 for (i = 0; i < w->numpoints; i++)
783 VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], dir);
784 VectorSubtract(point, w->points[i], pointvec);
786 CrossProduct(dir, plane->normal, normal);
788 if (DotProduct(pointvec, normal) < -epsilon) return false;
795 Winding_VectorIntersect
798 int Winding_VectorIntersect(winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon)
800 float front, back, frac;
803 front = DotProduct(p1, plane->normal) - plane->dist;
804 back = DotProduct(p2, plane->normal) - plane->dist;
805 //if both points at the same side of the plane
806 if (front < -epsilon && back < -epsilon) return false;
807 if (front > epsilon && back > epsilon) return false;
808 //get point of intersection with winding plane
809 if (fabs(front-back) < 0.001)
815 frac = front/(front-back);
816 mid[0] = p1[0] + (p2[0] - p1[0]) * frac;
817 mid[1] = p1[1] + (p2[1] - p1[1]) * frac;
818 mid[2] = p1[2] + (p2[2] - p1[2]) * frac;
820 return Winding_PointInside(w, plane, mid, epsilon);