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 ){
43 normal[0] = -b->normal[0];
44 normal[1] = -b->normal[1];
45 normal[2] = -b->normal[2];
49 normal[0] = b->normal[0];
50 normal[1] = b->normal[1];
51 normal[2] = b->normal[2];
55 fabs( a->normal[0] - normal[0] ) < NORMAL_EPSILON
56 && fabs( a->normal[1] - normal[1] ) < NORMAL_EPSILON
57 && fabs( a->normal[2] - normal[2] ) < NORMAL_EPSILON
58 && fabs( a->dist - dist ) < DIST_EPSILON ) {
69 int Plane_FromPoints( vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane ){
72 VectorSubtract( p2, p1, v1 );
73 VectorSubtract( p3, p1, v2 );
74 //CrossProduct(v2, v1, plane->normal);
75 CrossProduct( v1, v2, plane->normal );
76 if ( VectorNormalize( plane->normal, plane->normal ) < 0.1 ) {
79 plane->dist = DotProduct( p1, plane->normal );
88 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 ) {
107 winding_t *Winding_BaseForPlane( plane_t *p ){
110 vec3_t org, vright, vup;
113 // find the major axis
115 Sys_Printf( "Winding_BaseForPlane %p\n",p );
120 for ( i = 0 ; i < 3; i++ )
122 v = fabs( p->normal[i] );
129 Error( "Winding_BaseForPlane: no axis found" );
132 VectorCopy( vec3_origin, vup );
145 v = DotProduct( vup, p->normal );
146 VectorMA( vup, -v, p->normal, vup );
147 VectorNormalize( vup, vup );
149 VectorScale( p->normal, p->dist, org );
151 CrossProduct( vup, p->normal, vright );
153 VectorScale( vup, BOGUS_RANGE, vup );
154 VectorScale( vright, BOGUS_RANGE, vright );
156 // project a really big axis aligned box onto the plane
157 w = Winding_Alloc( 4 );
159 VectorSubtract( org, vright, w->points[0] );
160 VectorAdd( w->points[0], vup, w->points[0] );
162 VectorAdd( org, vright, w->points[1] );
163 VectorAdd( w->points[1], vup, w->points[1] );
165 VectorAdd( org, vright, w->points[2] );
166 VectorSubtract( w->points[2], vup, w->points[2] );
168 VectorSubtract( org, vright, w->points[3] );
169 VectorSubtract( w->points[3], vup, w->points[3] );
176 // macro to compute winding size
177 #define WINDING_SIZE( pt ) ( sizeof( int )*2 + sizeof( float )*5*( pt ) )
184 winding_t *Winding_Alloc( int points ){
188 if ( points > MAX_POINTS_ON_WINDING ) {
189 Error( "Winding_Alloc: %i points", points );
192 // size = (int)((winding_t *)0)->points[points];
193 size = WINDING_SIZE( points );
194 w = (winding_t*) malloc( size );
195 memset( w, 0, size );
196 w->maxpoints = points;
201 void Winding_Free( winding_t *w ){
210 winding_t *Winding_Clone( winding_t *w ){
214 // size = (int)((winding_t *)0)->points[w->numpoints];
215 size = WINDING_SIZE( w->numpoints );
216 c = (winding_t*)qmalloc( size );
217 memcpy( c, w, size );
226 winding_t *Winding_Reverse( winding_t *w ){
230 c = Winding_Alloc( w->numpoints );
231 for ( i = 0; i < w->numpoints; i++ )
233 VectorCopy( w->points[w->numpoints - 1 - i], c->points[i] );
235 c->numpoints = w->numpoints;
244 void Winding_RemovePoint( winding_t *w, int point ){
245 if ( point < 0 || point >= w->numpoints ) {
246 Error( "Winding_RemovePoint: point out of range" );
249 if ( point < w->numpoints - 1 ) {
250 memmove( &w->points[point], &w->points[point + 1], (size_t)( (winding_t *)0 )->points[w->numpoints - point - 1] );
260 winding_t *Winding_InsertPoint( winding_t *w, vec3_t point, int spot ){
264 if ( spot > w->numpoints ) {
265 Error( "Winding_InsertPoint: spot > w->numpoints" );
268 Error( "Winding_InsertPoint: spot < 0" );
270 neww = Winding_Alloc( w->numpoints + 1 );
271 neww->numpoints = w->numpoints + 1;
272 for ( i = 0, j = 0; i < neww->numpoints; i++ )
275 VectorCopy( point, neww->points[i] );
279 VectorCopy( w->points[j], neww->points[i] );
291 #define EDGE_LENGTH 0.2
293 int Winding_IsTiny( winding_t *w ){
300 for ( i = 0 ; i < w->numpoints ; i++ )
302 j = i == w->numpoints - 1 ? 0 : i + 1;
303 VectorSubtract( w->points[j], w->points[i], delta );
304 len = VectorLength( delta );
305 if ( len > EDGE_LENGTH ) {
306 if ( ++edges == 3 ) {
319 int Winding_IsHuge( winding_t *w ){
322 for ( i = 0 ; i < w->numpoints ; i++ )
324 for ( j = 0 ; j < 3 ; j++ )
325 if ( w->points[i][j] < -BOGUS_RANGE + 1 || w->points[i][j] > BOGUS_RANGE - 1 ) {
334 Winding_PlanesConcave
337 #define WCONVEX_EPSILON 0.2
339 int Winding_PlanesConcave( winding_t *w1, winding_t *w2,
340 vec3_t normal1, vec3_t normal2,
341 float dist1, float dist2 ){
348 // check if one of the points of winding 1 is at the back of the plane of winding 2
349 for ( i = 0; i < w1->numpoints; i++ )
351 if ( DotProduct( normal2, w1->points[i] ) - dist2 > WCONVEX_EPSILON ) {
355 // check if one of the points of winding 2 is at the back of the plane of winding 1
356 for ( i = 0; i < w2->numpoints; i++ )
358 if ( DotProduct( normal1, w2->points[i] ) - dist1 > WCONVEX_EPSILON ) {
370 Clips the winding to the plane, returning the new winding on the positive side
371 Frees the input winding.
372 If keepon is true, an exactly on-plane winding will be saved, otherwise
373 it will be clipped away.
376 winding_t *Winding_Clip( winding_t *in, plane_t *split, qboolean keepon ){
377 vec_t dists[MAX_POINTS_ON_WINDING];
378 int sides[MAX_POINTS_ON_WINDING];
387 counts[0] = counts[1] = counts[2] = 0;
389 // determine sides for each point
390 for ( i = 0 ; i < in->numpoints ; i++ )
392 dot = DotProduct( in->points[i], split->normal );
395 if ( dot > ON_EPSILON ) {
396 sides[i] = SIDE_FRONT;
398 else if ( dot < -ON_EPSILON ) {
399 sides[i] = SIDE_BACK;
410 if ( keepon && !counts[0] && !counts[1] ) {
422 maxpts = in->numpoints + 4; // can't use counts[0]+2 because
423 // of fp grouping errors
424 neww = Winding_Alloc( maxpts );
426 for ( i = 0 ; i < in->numpoints ; i++ )
430 if ( sides[i] == SIDE_ON ) {
431 VectorCopy( p1, neww->points[neww->numpoints] );
436 if ( sides[i] == SIDE_FRONT ) {
437 VectorCopy( p1, neww->points[neww->numpoints] );
441 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
445 // generate a split point
446 p2 = in->points[( i + 1 ) % in->numpoints];
448 dot = dists[i] / ( dists[i] - dists[i + 1] );
449 for ( j = 0 ; j < 3 ; j++ )
450 { // avoid round off error when possible
451 if ( split->normal[j] == 1 ) {
452 mid[j] = split->dist;
454 else if ( split->normal[j] == -1 ) {
455 mid[j] = -split->dist;
458 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
462 VectorCopy( mid, neww->points[neww->numpoints] );
466 if ( neww->numpoints > maxpts ) {
467 Error( "Winding_Clip: points exceeded estimate" );
470 // free the original winding
480 split the input winding with the plane
481 the input winding stays untouched
484 void Winding_SplitEpsilon( winding_t *in, vec3_t normal, double dist,
485 vec_t epsilon, winding_t **front, winding_t **back ){
486 vec_t dists[MAX_POINTS_ON_WINDING + 4];
487 int sides[MAX_POINTS_ON_WINDING + 4];
496 counts[0] = counts[1] = counts[2] = 0;
498 // determine sides for each point
499 for ( i = 0; i < in->numpoints; i++ )
501 dot = DotProduct( in->points[i], normal );
504 if ( dot > epsilon ) {
505 sides[i] = SIDE_FRONT;
507 else if ( dot < -epsilon ) {
508 sides[i] = SIDE_BACK;
519 *front = *back = NULL;
522 *back = Winding_Clone( in );
526 *front = Winding_Clone( in );
530 maxpts = in->numpoints + 4; // cant use counts[0]+2 because
531 // of fp grouping errors
533 *front = f = Winding_Alloc( maxpts );
534 *back = b = Winding_Alloc( maxpts );
536 for ( i = 0; i < in->numpoints; i++ )
540 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 ) {
549 VectorCopy( p1, f->points[f->numpoints] );
552 if ( sides[i] == SIDE_BACK ) {
553 VectorCopy( p1, b->points[b->numpoints] );
557 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
561 // generate a split point
562 p2 = in->points[( i + 1 ) % in->numpoints];
564 dot = dists[i] / ( dists[i] - dists[i + 1] );
565 for ( j = 0; j < 3; j++ )
567 // avoid round off error when possible
568 if ( normal[j] == 1 ) {
571 else if ( normal[j] == -1 ) {
575 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
579 VectorCopy( mid, f->points[f->numpoints] );
581 VectorCopy( mid, b->points[b->numpoints] );
585 if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
586 Error( "Winding_Clip: points exceeded estimate" );
588 if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
589 Error( "Winding_Clip: MAX_POINTS_ON_WINDING" );
597 If two windings share a common edge and the edges that meet at the
598 common points are both inside the other polygons, merge them
600 Returns NULL if the windings couldn't be merged, or the new winding.
601 The originals will NOT be freed.
603 if keep is true no points are ever removed
606 #define CONTINUOUS_EPSILON 0.005
608 winding_t *Winding_TryMerge( winding_t *f1, winding_t *f2, vec3_t planenormal, int keep ){
609 vec_t *p1, *p2, *p3, *p4, *back;
612 vec3_t normal, delta;
614 qboolean keep1, keep2;
618 // find a common edge
620 p1 = p2 = NULL; // stop compiler warning
623 for ( i = 0; i < f1->numpoints; i++ )
626 p2 = f1->points[( i + 1 ) % f1->numpoints];
627 for ( j = 0; j < f2->numpoints; j++ )
630 p4 = f2->points[( j + 1 ) % f2->numpoints];
631 for ( k = 0; k < 3; k++ )
633 if ( fabs( p1[k] - p4[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME
636 if ( fabs( p2[k] - p3[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME
644 if ( j < f2->numpoints ) {
649 if ( i == f1->numpoints ) {
650 return NULL; // no matching edges
654 // check slope of connected lines
655 // if the slopes are colinear, the point can be removed
657 back = f1->points[( i + f1->numpoints - 1 ) % f1->numpoints];
658 VectorSubtract( p1, back, delta );
659 CrossProduct( planenormal, delta, normal );
660 VectorNormalize( normal, normal );
662 back = f2->points[( j + 2 ) % f2->numpoints];
663 VectorSubtract( back, p1, delta );
664 dot = DotProduct( delta, normal );
665 if ( dot > CONTINUOUS_EPSILON ) {
666 return NULL; // not a convex polygon
668 keep1 = (qboolean)( dot < -CONTINUOUS_EPSILON );
670 back = f1->points[( i + 2 ) % f1->numpoints];
671 VectorSubtract( back, p2, delta );
672 CrossProduct( planenormal, delta, normal );
673 VectorNormalize( normal, normal );
675 back = f2->points[( j + f2->numpoints - 1 ) % f2->numpoints];
676 VectorSubtract( back, p2, delta );
677 dot = DotProduct( delta, normal );
678 if ( dot > CONTINUOUS_EPSILON ) {
679 return NULL; // not a convex polygon
681 keep2 = (qboolean)( dot < -CONTINUOUS_EPSILON );
684 // build the new polygon
686 newf = Winding_Alloc( f1->numpoints + f2->numpoints );
688 // copy first polygon
689 for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints )
691 if ( !keep && k == ( i + 1 ) % f1->numpoints && !keep2 ) {
695 VectorCopy( f1->points[k], newf->points[newf->numpoints] );
699 // copy second polygon
700 for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints )
702 if ( !keep && l == ( j + 1 ) % f2->numpoints && !keep1 ) {
705 VectorCopy( f2->points[l], newf->points[newf->numpoints] );
717 void Winding_Plane( winding_t *w, vec3_t normal, double *dist ){
721 //find two vectors each longer than 0.5 units
722 for ( i = 0; i < w->numpoints; i++ )
724 VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], v1 );
725 VectorSubtract( w->points[( i + 2 ) % w->numpoints], w->points[i], v2 );
726 if ( VectorLength( v1 ) > 0.5 && VectorLength( v2 ) > 0.5 ) {
730 CrossProduct( v2, v1, normal );
731 VectorNormalize( normal, normal );
732 *dist = DotProduct( w->points[0], normal );
740 float Winding_Area( winding_t *w ){
742 vec3_t d1, d2, cross;
746 for ( i = 2 ; i < w->numpoints ; i++ )
748 VectorSubtract( w->points[i - 1], w->points[0], d1 );
749 VectorSubtract( w->points[i], w->points[0], d2 );
750 CrossProduct( d1, d2, cross );
751 total += 0.5 * VectorLength( cross );
761 void Winding_Bounds( winding_t *w, vec3_t mins, vec3_t maxs ){
765 mins[0] = mins[1] = mins[2] = 99999;
766 maxs[0] = maxs[1] = maxs[2] = -99999;
768 for ( i = 0 ; i < w->numpoints ; i++ )
770 for ( j = 0 ; j < 3 ; j++ )
789 int Winding_PointInside( winding_t *w, plane_t *plane, vec3_t point, float epsilon ){
791 vec3_t dir, normal, pointvec;
793 for ( i = 0; i < w->numpoints; i++ )
795 VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], dir );
796 VectorSubtract( point, w->points[i], pointvec );
798 CrossProduct( dir, plane->normal, normal );
800 if ( DotProduct( pointvec, normal ) < -epsilon ) {
809 Winding_VectorIntersect
812 int Winding_VectorIntersect( winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon ){
813 float front, back, frac;
816 front = DotProduct( p1, plane->normal ) - plane->dist;
817 back = DotProduct( p2, plane->normal ) - plane->dist;
818 //if both points at the same side of the plane
819 if ( front < -epsilon && back < -epsilon ) {
822 if ( front > epsilon && back > epsilon ) {
825 //get point of intersection with winding plane
826 if ( fabs( front - back ) < 0.001 ) {
827 VectorCopy( p2, mid );
831 frac = front / ( front - back );
832 mid[0] = p1[0] + ( p2[0] - p1[0] ) * frac;
833 mid[1] = p1[1] + ( p2[1] - p1[1] ) * frac;
834 mid[2] = p1[2] + ( p2[2] - p1[2] ) * frac;
836 return Winding_PointInside( w, plane, mid, epsilon );