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 //////////////////////////////////////////////////////////////////////
31 //////////////////////////////////////////////////////////////////////
32 // Construction/Destruction
33 //////////////////////////////////////////////////////////////////////
40 DWinding::~DWinding(){
46 //////////////////////////////////////////////////////////////////////
48 //////////////////////////////////////////////////////////////////////
50 #define BOGUS_RANGE 4096
52 void DWinding::AllocWinding( int points ){
57 p = new vec3_t[points];
60 vec_t DWinding::WindingArea(){
65 for ( int i = 2; i < numpoints ; i++ )
67 VectorSubtract( p[i - 1], p[0], d1 );
68 VectorSubtract( p[i], p[0], d2 );
70 CrossProduct( d1, d2, cross );
72 total += 0.5f * VectorLength( cross );
78 void DWinding::RemoveColinearPoints(){
79 vec3_t p2[MAX_POINTS_ON_WINDING];
82 for ( int i = 0; i < numpoints; i++ )
84 int j = ( i + 1 ) % numpoints;
85 int k = ( i + numpoints - 1 ) % numpoints;
88 VectorSubtract( p[j], p[i], v1 );
89 VectorSubtract( p[i], p[k], v2 );
90 VectorNormalize( v1, v1 );
91 VectorNormalize( v2, v2 );
93 if ( DotProduct( v1, v2 ) < 0.999 ) {
94 VectorCopy( p[i], p2[nump] );
99 if ( nump == numpoints ) {
103 AllocWinding( nump );
104 memcpy( p, p2, nump * sizeof( vec3_t ) );
107 DPlane* DWinding::WindingPlane(){
108 DPlane* newPlane = new DPlane( p[0], p[1], p[2], NULL );
112 void DWinding::WindingBounds( vec3_t mins, vec3_t maxs ){
113 if ( numpoints == 0 ) {
117 VectorCopy( mins, p[0] );
118 VectorCopy( maxs, p[0] );
120 for ( int i = 1; i < numpoints ; i++ )
122 for ( int j = 0; j < 3; j++ )
135 void DWinding::WindingCentre( vec3_t centre ){
136 VectorCopy( vec3_origin, centre );
137 for ( int i = 0; i < numpoints; i++ )
138 VectorAdd( p[i], centre, centre );
140 float scale = 1.0f / numpoints;
141 VectorScale( centre, scale, centre );
145 DWinding* DWinding::CopyWinding(){
146 DWinding* c = new DWinding;
147 c->AllocWinding( numpoints );
148 memcpy( c->p, p, numpoints * sizeof( vec3_t ) );
153 int DWinding::WindingOnPlaneSide( vec3_t normal, vec_t dist ){
157 for ( int i = 0; i < numpoints; i++ )
159 vec_t d = DotProduct( p[i], normal ) - dist;
160 if ( d < -ON_EPSILON ) {
167 if ( d > ON_EPSILON ) {
185 void DWinding::CheckWinding(){
188 vec3_t dir, edgenormal;
190 if ( numpoints < 3 ) {
191 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
194 vec_t area = WindingArea();
196 globalOutputStream() << "CheckWinding: " << area << " area\n";
199 DPlane* wPlane = WindingPlane();
201 for ( i = 0; i < numpoints; i++ )
206 for ( j = 0; j < 3; j++ )
207 if ( p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE ) {
208 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
211 j = i + 1 == numpoints ? 0 : i + 1;
213 // check the point is on the face plane
214 vec_t d = DotProduct( p1, wPlane->normal ) - wPlane->_d;
215 if ( d < -ON_EPSILON || d > ON_EPSILON ) {
216 globalOutputStream() << "CheckWinding: point off plane\n";
219 // check the edge isnt degenerate
221 VectorSubtract( p2, p1, dir );
223 if ( VectorLength( dir ) < ON_EPSILON ) {
224 globalOutputStream() << "CheckWinding: degenerate edge\n";
227 CrossProduct( wPlane->normal, dir, edgenormal );
228 VectorNormalize( edgenormal, edgenormal );
229 edgedist = DotProduct( p1, edgenormal );
231 // all other points must be on front side
232 for ( j = 0 ; j < numpoints ; j++ )
238 d = DotProduct( p[j], edgenormal );
239 if ( d > ( edgedist + ON_EPSILON ) ) {
240 globalOutputStream() << "CheckWinding: non-convex\n";
248 DWinding* DWinding::ReverseWinding(){
249 DWinding* c = new DWinding;
250 c->AllocWinding( numpoints );
252 for ( int i = 0; i < numpoints ; i++ )
253 VectorCopy( p[numpoints - 1 - i], c->p[i] );
258 bool DWinding::ChopWindingInPlace( DPlane* chopPlane, vec_t epsilon ){
259 vec_t dists[MAX_POINTS_ON_WINDING + 4];
260 int sides[MAX_POINTS_ON_WINDING + 4];
265 counts[0] = counts[1] = counts[2] = 0;
267 // determine sides for each point
269 for ( i = 0; i < numpoints; i++ )
271 vec_t dot = DotProduct( p[i], chopPlane->normal );
272 dot -= chopPlane->_d;
275 if ( dot > epsilon ) {
276 sides[i] = SIDE_FRONT;
278 else if ( dot < -epsilon ) {
279 sides[i] = SIDE_BACK;
299 int maxpts = numpoints + 4; // cant use counts[0]+2 because
300 // of fp grouping errors
302 DWinding* f = new DWinding;
303 f->AllocWinding( maxpts );
306 for ( i = 0; i < numpoints; i++ )
310 if ( sides[i] == SIDE_ON ) {
311 VectorCopy( p1, f->p[f->numpoints] );
316 if ( sides[i] == SIDE_FRONT ) {
317 VectorCopy( p1, f->p[f->numpoints] );
321 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
325 // generate a split point
326 p2 = p[( i + 1 ) % numpoints];
328 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
329 for ( int j = 0; j < 3; j++ )
331 if ( chopPlane->normal[j] == 1 ) {
332 mid[j] = chopPlane->_d;
334 else if ( chopPlane->normal[j] == -1 ) {
335 mid[j] = -chopPlane->_d;
338 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
342 VectorCopy( mid, f->p[f->numpoints] );
346 if ( f->numpoints > maxpts ) {
347 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
349 if ( f->numpoints > MAX_POINTS_ON_WINDING ) {
350 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
360 void DWinding::ClipWindingEpsilon( DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back ){
361 vec_t dists[MAX_POINTS_ON_WINDING + 4];
362 int sides[MAX_POINTS_ON_WINDING + 4];
367 counts[0] = counts[1] = counts[2] = 0;
369 // determine sides for each point
371 for ( i = 0; i < numpoints; i++ )
373 vec_t dot = -chopPlane->DistanceToPoint( p[i] );
376 if ( dot > epsilon ) {
377 sides[i] = SIDE_FRONT;
379 else if ( dot < -epsilon ) {
380 sides[i] = SIDE_BACK;
391 *front = *back = NULL;
394 *back = CopyWinding();
398 *front = CopyWinding();
402 int maxpts = numpoints + 4; // cant use counts[0]+2 because
403 // of fp grouping errors
405 DWinding* f = new DWinding;
406 DWinding* b = new DWinding;
408 f->AllocWinding( maxpts );
411 b->AllocWinding( maxpts );
417 for ( i = 0; i < numpoints ; i++ )
421 if ( sides[i] == SIDE_ON ) {
422 VectorCopy( p1, f->p[f->numpoints] );
424 VectorCopy( p1, b->p[b->numpoints] );
429 if ( sides[i] == SIDE_FRONT ) {
430 VectorCopy( p1, f->p[f->numpoints] );
433 if ( sides[i] == SIDE_BACK ) {
434 VectorCopy( p1, b->p[b->numpoints] );
438 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
442 // generate a split point
443 p2 = p[( i + 1 ) % numpoints];
445 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
446 for ( int j = 0; j < 3; j++ )
448 if ( chopPlane->normal[j] == 1 ) {
449 mid[j] = chopPlane->_d;
451 else if ( chopPlane->normal[j] == -1 ) {
452 mid[j] = -chopPlane->_d;
455 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
459 VectorCopy( mid, f->p[f->numpoints] );
461 VectorCopy( mid, b->p[b->numpoints] );
465 if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
466 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
468 if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
469 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
473 bool DWinding::ChopWinding( DPlane* chopPlane ){
476 ClipWindingEpsilon( chopPlane, (float)ON_EPSILON, &f, &b );
491 numpoints = f->numpoints;