2 BobToolz plugin for GtkRadiant
3 Copyright (C) 2001 Gordon Biggans
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // DWinding.cpp: implementation of the DWinding class.
22 //////////////////////////////////////////////////////////////////////
29 //////////////////////////////////////////////////////////////////////
30 // Construction/Destruction
31 //////////////////////////////////////////////////////////////////////
38 DWinding::~DWinding(){
44 //////////////////////////////////////////////////////////////////////
46 //////////////////////////////////////////////////////////////////////
48 #define BOGUS_RANGE 4096
50 void DWinding::AllocWinding( int points ){
55 p = new vec3_t[points];
58 vec_t DWinding::WindingArea(){
63 for ( int i = 2; i < numpoints ; i++ )
65 VectorSubtract( p[i - 1], p[0], d1 );
66 VectorSubtract( p[i], p[0], d2 );
68 CrossProduct( d1, d2, cross );
70 total += 0.5f * VectorLength( cross );
76 void DWinding::RemoveColinearPoints(){
77 vec3_t p2[MAX_POINTS_ON_WINDING];
80 for ( int i = 0; i < numpoints; i++ )
82 int j = ( i + 1 ) % numpoints;
83 int k = ( i + numpoints - 1 ) % numpoints;
86 VectorSubtract( p[j], p[i], v1 );
87 VectorSubtract( p[i], p[k], v2 );
88 VectorNormalize( v1, v1 );
89 VectorNormalize( v2, v2 );
91 if ( DotProduct( v1, v2 ) < 0.999 ) {
92 VectorCopy( p[i], p2[nump] );
97 if ( nump == numpoints ) {
101 AllocWinding( nump );
102 memcpy( p, p2, nump * sizeof( vec3_t ) );
105 DPlane* DWinding::WindingPlane(){
106 DPlane* newPlane = new DPlane( p[0], p[1], p[2], NULL );
110 void DWinding::WindingBounds( vec3_t mins, vec3_t maxs ){
111 if ( numpoints == 0 ) {
115 VectorCopy( mins, p[0] );
116 VectorCopy( maxs, p[0] );
118 for ( int i = 1; i < numpoints ; i++ )
120 for ( int j = 0; j < 3; j++ )
133 void DWinding::WindingCentre( vec3_t centre ){
134 VectorCopy( vec3_origin, centre );
135 for ( int i = 0; i < numpoints; i++ )
136 VectorAdd( p[i], centre, centre );
138 float scale = 1.0f / numpoints;
139 VectorScale( centre, scale, centre );
143 DWinding* DWinding::CopyWinding(){
144 DWinding* c = new DWinding;
145 c->AllocWinding( numpoints );
146 memcpy( c->p, p, numpoints * sizeof( vec3_t ) );
151 int DWinding::WindingOnPlaneSide( vec3_t normal, vec_t dist ){
155 for ( int i = 0; i < numpoints; i++ )
157 vec_t d = DotProduct( p[i], normal ) - dist;
158 if ( d < -ON_EPSILON ) {
165 if ( d > ON_EPSILON ) {
183 void DWinding::CheckWinding(){
186 vec3_t dir, edgenormal;
188 if ( numpoints < 3 ) {
189 Sys_Printf( "CheckWinding: %i points", numpoints );
192 vec_t area = WindingArea();
194 Sys_Printf( "CheckWinding: %f area", area );
197 DPlane* wPlane = WindingPlane();
199 for ( i = 0; i < numpoints; i++ )
204 for ( j = 0; j < 3; j++ )
205 if ( p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE ) {
206 Sys_Printf( "CheckFace: BUGUS_RANGE: %f", p1[j] );
209 j = i + 1 == numpoints ? 0 : i + 1;
211 // check the point is on the face plane
212 vec_t d = DotProduct( p1, wPlane->normal ) - wPlane->_d;
213 if ( d < -ON_EPSILON || d > ON_EPSILON ) {
214 Sys_Printf( "CheckWinding: point off plane" );
217 // check the edge isnt degenerate
219 VectorSubtract( p2, p1, dir );
221 if ( VectorLength( dir ) < ON_EPSILON ) {
222 Sys_Printf( "CheckWinding: degenerate edge" );
225 CrossProduct( wPlane->normal, dir, edgenormal );
226 VectorNormalize( edgenormal, edgenormal );
227 edgedist = DotProduct( p1, edgenormal );
229 // all other points must be on front side
230 for ( j = 0 ; j < numpoints ; j++ )
236 d = DotProduct( p[j], edgenormal );
237 if ( d > ( edgedist + ON_EPSILON ) ) {
238 Sys_Printf( "CheckWinding: non-convex" );
246 DWinding* DWinding::ReverseWinding(){
247 DWinding* c = new DWinding;
248 c->AllocWinding( numpoints );
250 for ( int i = 0; i < numpoints ; i++ )
251 VectorCopy( p[numpoints - 1 - i], c->p[i] );
256 bool DWinding::ChopWindingInPlace( DPlane* chopPlane, vec_t epsilon ){
257 vec_t dists[MAX_POINTS_ON_WINDING + 4];
258 int sides[MAX_POINTS_ON_WINDING + 4];
263 counts[0] = counts[1] = counts[2] = 0;
265 // determine sides for each point
267 for ( i = 0; i < numpoints; i++ )
269 vec_t dot = DotProduct( p[i], chopPlane->normal );
270 dot -= chopPlane->_d;
273 if ( dot > epsilon ) {
274 sides[i] = SIDE_FRONT;
276 else if ( dot < -epsilon ) {
277 sides[i] = SIDE_BACK;
297 int maxpts = numpoints + 4; // cant use counts[0]+2 because
298 // of fp grouping errors
300 DWinding* f = new DWinding;
301 f->AllocWinding( maxpts );
304 for ( i = 0; i < numpoints; i++ )
308 if ( sides[i] == SIDE_ON ) {
309 VectorCopy( p1, f->p[f->numpoints] );
314 if ( sides[i] == SIDE_FRONT ) {
315 VectorCopy( p1, f->p[f->numpoints] );
319 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
323 // generate a split point
324 p2 = p[( i + 1 ) % numpoints];
326 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
327 for ( int j = 0; j < 3; j++ )
329 if ( chopPlane->normal[j] == 1 ) {
330 mid[j] = chopPlane->_d;
332 else if ( chopPlane->normal[j] == -1 ) {
333 mid[j] = -chopPlane->_d;
336 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
340 VectorCopy( mid, f->p[f->numpoints] );
344 if ( f->numpoints > maxpts ) {
345 Sys_Printf( "ClipWinding: points exceeded estimate" );
347 if ( f->numpoints > MAX_POINTS_ON_WINDING ) {
348 Sys_Printf( "ClipWinding: MAX_POINTS_ON_WINDING" );
358 void DWinding::ClipWindingEpsilon( DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back ){
359 vec_t dists[MAX_POINTS_ON_WINDING + 4];
360 int sides[MAX_POINTS_ON_WINDING + 4];
365 counts[0] = counts[1] = counts[2] = 0;
367 // determine sides for each point
369 for ( i = 0; i < numpoints; i++ )
371 vec_t dot = -chopPlane->DistanceToPoint( p[i] );
374 if ( dot > epsilon ) {
375 sides[i] = SIDE_FRONT;
377 else if ( dot < -epsilon ) {
378 sides[i] = SIDE_BACK;
389 *front = *back = NULL;
392 *back = CopyWinding();
396 *front = CopyWinding();
400 int maxpts = numpoints + 4; // cant use counts[0]+2 because
401 // of fp grouping errors
403 DWinding* f = new DWinding;
404 DWinding* b = new DWinding;
406 f->AllocWinding( maxpts );
409 b->AllocWinding( maxpts );
415 for ( i = 0; i < numpoints ; i++ )
419 if ( sides[i] == SIDE_ON ) {
420 VectorCopy( p1, f->p[f->numpoints] );
422 VectorCopy( p1, b->p[b->numpoints] );
427 if ( sides[i] == SIDE_FRONT ) {
428 VectorCopy( p1, f->p[f->numpoints] );
431 if ( sides[i] == SIDE_BACK ) {
432 VectorCopy( p1, b->p[b->numpoints] );
436 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
440 // generate a split point
441 p2 = p[( i + 1 ) % numpoints];
443 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
444 for ( int j = 0; j < 3; j++ )
446 if ( chopPlane->normal[j] == 1 ) {
447 mid[j] = chopPlane->_d;
449 else if ( chopPlane->normal[j] == -1 ) {
450 mid[j] = -chopPlane->_d;
453 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
457 VectorCopy( mid, f->p[f->numpoints] );
459 VectorCopy( mid, b->p[b->numpoints] );
463 if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
464 Sys_Printf( "ClipWinding: points exceeded estimate" );
466 if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
467 Sys_Printf( "ClipWinding: MAX_POINTS_ON_WINDING" );
471 bool DWinding::ChopWinding( DPlane* chopPlane ){
474 ClipWindingEpsilon( chopPlane, (float)ON_EPSILON, &f, &b );
489 numpoints = f->numpoints;