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
29 extern int numthreads;
31 // counters are only bumped when running single threaded,
32 // because they are an awefull coherence problem
33 int c_active_windings;
38 #define BOGUS_RANGE 8192
40 void pw( winding_t *w ){
42 for ( i = 0 ; i < w->numpoints ; i++ )
43 printf( "(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2] );
52 winding_t *AllocWinding( int points ){
56 if ( numthreads == 1 ) {
58 c_winding_points += points;
60 if ( c_active_windings > c_peak_windings ) {
61 c_peak_windings = c_active_windings;
64 s = sizeof( vec_t ) * 3 * points + sizeof( int );
67 Error( "AllocWinding MALLOC failed! Could not allocate %s bytes.", s );
73 void FreeWinding( winding_t *w ){
74 if ( *(unsigned *)w == 0xdeaddead ) {
75 Error( "FreeWinding: freed a freed winding" );
77 *(unsigned *)w = 0xdeaddead;
79 if ( numthreads == 1 ) {
92 void RemoveColinearPoints( winding_t *w ){
96 vec3_t p[MAX_POINTS_ON_WINDING];
99 for ( i = 0 ; i < w->numpoints ; i++ )
101 j = ( i + 1 ) % w->numpoints;
102 k = ( i + w->numpoints - 1 ) % w->numpoints;
103 VectorSubtract( w->p[j], w->p[i], v1 );
104 VectorSubtract( w->p[i], w->p[k], v2 );
105 VectorNormalize( v1,v1 );
106 VectorNormalize( v2,v2 );
107 if ( DotProduct( v1, v2 ) < 0.999 ) {
108 VectorCopy( w->p[i], p[nump] );
113 if ( nump == w->numpoints ) {
117 if ( numthreads == 1 ) {
118 c_removed += w->numpoints - nump;
121 memcpy( w->p, p, nump * sizeof( p[0] ) );
129 void WindingPlane( winding_t *w, vec3_t normal, vec_t *dist ){
132 VectorSubtract( w->p[1], w->p[0], v1 );
133 VectorSubtract( w->p[2], w->p[0], v2 );
134 CrossProduct( v2, v1, normal );
135 VectorNormalize( normal, normal );
136 *dist = DotProduct( w->p[0], normal );
145 vec_t WindingArea( winding_t *w ){
147 vec3_t d1, d2, cross;
151 for ( i = 2 ; i < w->numpoints ; i++ )
153 VectorSubtract( w->p[i - 1], w->p[0], d1 );
154 VectorSubtract( w->p[i], w->p[0], d2 );
155 CrossProduct( d1, d2, cross );
156 total += 0.5 * VectorLength( cross );
161 void WindingBounds( winding_t *w, vec3_t mins, vec3_t maxs ){
165 mins[0] = mins[1] = mins[2] = 99999;
166 maxs[0] = maxs[1] = maxs[2] = -99999;
168 for ( i = 0 ; i < w->numpoints ; i++ )
170 for ( j = 0 ; j < 3 ; j++ )
188 void WindingCenter( winding_t *w, vec3_t center ){
192 VectorCopy( vec3_origin, center );
193 for ( i = 0 ; i < w->numpoints ; i++ )
194 VectorAdd( w->p[i], center, center );
196 scale = 1.0 / w->numpoints;
197 VectorScale( center, scale, center );
205 winding_t *BaseWindingForPlane( vec3_t normal, vec_t dist ){
208 vec3_t org, vright, vup;
211 // find the major axis
215 for ( i = 0 ; i < 3; i++ )
217 v = fabs( normal[i] );
224 Error( "BaseWindingForPlane: no axis found" );
227 VectorCopy( vec3_origin, vup );
239 v = DotProduct( vup, normal );
240 VectorMA( vup, -v, normal, vup );
241 VectorNormalize( vup, vup );
243 VectorScale( normal, dist, org );
245 CrossProduct( vup, normal, vright );
247 VectorScale( vup, 8192, vup );
248 VectorScale( vright, 8192, vright );
250 // project a really big axis aligned box onto the plane
251 w = AllocWinding( 4 );
253 VectorSubtract( org, vright, w->p[0] );
254 VectorAdd( w->p[0], vup, w->p[0] );
256 VectorAdd( org, vright, w->p[1] );
257 VectorAdd( w->p[1], vup, w->p[1] );
259 VectorAdd( org, vright, w->p[2] );
260 VectorSubtract( w->p[2], vup, w->p[2] );
262 VectorSubtract( org, vright, w->p[3] );
263 VectorSubtract( w->p[3], vup, w->p[3] );
275 winding_t *CopyWinding( winding_t *w ){
279 c = AllocWinding( w->numpoints );
280 size = (int)( (winding_t *)0 )->p[w->numpoints];
281 memcpy( c, w, size );
290 winding_t *ReverseWinding( winding_t *w ){
294 c = AllocWinding( w->numpoints );
295 for ( i = 0 ; i < w->numpoints ; i++ )
297 VectorCopy( w->p[w->numpoints - 1 - i], c->p[i] );
299 c->numpoints = w->numpoints;
309 void ClipWindingEpsilon( winding_t *in, vec3_t normal, vec_t dist,
310 vec_t epsilon, winding_t **front, winding_t **back ){
311 vec_t dists[MAX_POINTS_ON_WINDING + 4];
312 int sides[MAX_POINTS_ON_WINDING + 4];
314 vec_t dot; // VC 4.2 optimizer bug if not static
321 if ( in->numpoints >= MAX_POINTS_ON_WINDING - 4 ) {
322 Error( "ClipWinding: MAX_POINTS_ON_WINDING" );
325 counts[0] = counts[1] = counts[2] = 0;
327 // determine sides for each point
328 for ( i = 0 ; i < in->numpoints ; i++ )
330 dot = DotProduct( in->p[i], normal );
333 if ( dot > epsilon ) {
334 sides[i] = SIDE_FRONT;
336 else if ( dot < -epsilon ) {
337 sides[i] = SIDE_BACK;
348 *front = *back = NULL;
351 *back = CopyWinding( in );
355 *front = CopyWinding( in );
359 maxpts = in->numpoints + 4; // cant use counts[0]+2 because
360 // of fp grouping errors
362 *front = f = AllocWinding( maxpts );
363 *back = b = AllocWinding( maxpts );
365 for ( i = 0 ; i < in->numpoints ; i++ )
369 if ( sides[i] == SIDE_ON ) {
370 VectorCopy( p1, f->p[f->numpoints] );
372 VectorCopy( p1, b->p[b->numpoints] );
377 if ( sides[i] == SIDE_FRONT ) {
378 VectorCopy( p1, f->p[f->numpoints] );
381 if ( sides[i] == SIDE_BACK ) {
382 VectorCopy( p1, b->p[b->numpoints] );
386 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
390 // generate a split point
391 p2 = in->p[( i + 1 ) % in->numpoints];
393 dot = dists[i] / ( dists[i] - dists[i + 1] );
394 for ( j = 0 ; j < 3 ; j++ )
395 { // avoid round off error when possible
396 if ( normal[j] == 1 ) {
399 else if ( normal[j] == -1 ) {
403 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
407 VectorCopy( mid, f->p[f->numpoints] );
409 VectorCopy( mid, b->p[b->numpoints] );
413 if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
414 Error( "ClipWinding: points exceeded estimate" );
416 if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
417 Error( "ClipWinding: MAX_POINTS_ON_WINDING" );
427 void ChopWindingInPlace( winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon ){
429 vec_t dists[MAX_POINTS_ON_WINDING + 4];
430 int sides[MAX_POINTS_ON_WINDING + 4];
432 vec_t dot; // VC 4.2 optimizer bug if not static
440 counts[0] = counts[1] = counts[2] = 0;
443 printf( "Warning: NULL passed to ChopWindingInPlace\n" );
446 if ( in->numpoints >= MAX_POINTS_ON_WINDING - 4 ) {
447 Error( "ChopWinding: MAX_POINTS_ON_WINDING" );
450 // determine sides for each point
451 for ( i = 0 ; i < in->numpoints ; i++ )
453 dot = DotProduct( in->p[i], normal );
456 if ( dot > epsilon ) {
457 sides[i] = SIDE_FRONT;
459 else if ( dot < -epsilon ) {
460 sides[i] = SIDE_BACK;
477 return; // inout stays the same
480 maxpts = in->numpoints + 4; // cant use counts[0]+2 because
481 // of fp grouping errors
483 f = AllocWinding( maxpts );
485 for ( i = 0 ; i < in->numpoints ; i++ )
489 if ( sides[i] == SIDE_ON ) {
490 VectorCopy( p1, f->p[f->numpoints] );
495 if ( sides[i] == SIDE_FRONT ) {
496 VectorCopy( p1, f->p[f->numpoints] );
500 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
504 // generate a split point
505 p2 = in->p[( i + 1 ) % in->numpoints];
507 dot = dists[i] / ( dists[i] - dists[i + 1] );
508 for ( j = 0 ; j < 3 ; j++ )
509 { // avoid round off error when possible
510 if ( normal[j] == 1 ) {
513 else if ( normal[j] == -1 ) {
517 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
521 VectorCopy( mid, f->p[f->numpoints] );
525 if ( f->numpoints > maxpts ) {
526 Error( "ClipWinding: points exceeded estimate" );
528 if ( f->numpoints > MAX_POINTS_ON_WINDING ) {
529 Error( "ClipWinding: MAX_POINTS_ON_WINDING" );
541 Returns the fragment of in that is on the front side
542 of the cliping plane. The original is freed.
545 winding_t *ChopWinding( winding_t *in, vec3_t normal, vec_t dist ){
548 ClipWindingEpsilon( in, normal, dist, ON_EPSILON, &f, &b );
563 void CheckWinding( winding_t *w ){
567 vec3_t dir, edgenormal, facenormal;
571 if ( w->numpoints < 3 ) {
572 Error( "CheckWinding: %i points",w->numpoints );
575 area = WindingArea( w );
577 Error( "CheckWinding: %f area", area );
580 WindingPlane( w, facenormal, &facedist );
582 for ( i = 0 ; i < w->numpoints ; i++ )
586 for ( j = 0 ; j < 3 ; j++ )
587 if ( p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE ) {
588 Error( "CheckFace: BUGUS_RANGE: %f",p1[j] );
591 j = i + 1 == w->numpoints ? 0 : i + 1;
593 // check the point is on the face plane
594 d = DotProduct( p1, facenormal ) - facedist;
595 if ( d < -ON_EPSILON || d > ON_EPSILON ) {
596 Error( "CheckWinding: point off plane" );
599 // check the edge isnt degenerate
601 VectorSubtract( p2, p1, dir );
603 if ( VectorLength( dir ) < ON_EPSILON ) {
604 Error( "CheckWinding: degenerate edge" );
607 CrossProduct( facenormal, dir, edgenormal );
608 VectorNormalize( edgenormal, edgenormal );
609 edgedist = DotProduct( p1, edgenormal );
610 edgedist += ON_EPSILON;
612 // all other points must be on front side
613 for ( j = 0 ; j < w->numpoints ; j++ )
618 d = DotProduct( w->p[j], edgenormal );
619 if ( d > edgedist ) {
620 Error( "CheckWinding: non-convex" );
632 int WindingOnPlaneSide( winding_t *w, vec3_t normal, vec_t dist ){
633 qboolean front, back;
639 for ( i = 0 ; i < w->numpoints ; i++ )
641 d = DotProduct( w->p[i], normal ) - dist;
642 if ( d < -ON_EPSILON ) {
649 if ( d > ON_EPSILON ) {