1 /*
2 BobToolz plugin for GtkRadiant
3 Copyright (C) 2001 Gordon Biggans
4
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.
9
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.
14
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
18 */
19
20 // DWinding.cpp: implementation of the DWinding class.
21 //
22 //////////////////////////////////////////////////////////////////////
23
24 #include "DWinding.h"
25
26 #include <list>
27
28 #include "DPoint.h"
29 #include "DPlane.h"
30
31 //////////////////////////////////////////////////////////////////////
32 // Construction/Destruction
33 //////////////////////////////////////////////////////////////////////
34
DWinding()35 DWinding::DWinding(){
36 numpoints = 0;
37 p = NULL;
38 }
39
~DWinding()40 DWinding::~DWinding(){
41 if ( p ) {
42 delete[] p;
43 }
44 }
45
46 //////////////////////////////////////////////////////////////////////
47 // Implementation
48 //////////////////////////////////////////////////////////////////////
49
50 #define BOGUS_RANGE 4096
51
AllocWinding(int points)52 void DWinding::AllocWinding( int points ){
53 numpoints = points;
54 if ( p ) {
55 delete[] p;
56 }
57 p = new vec3_t[points];
58 }
59
WindingArea()60 vec_t DWinding::WindingArea(){
61 vec3_t d1, d2, cross;
62 vec_t total;
63
64 total = 0;
65 for ( int i = 2; i < numpoints ; i++ )
66 {
67 VectorSubtract( p[i - 1], p[0], d1 );
68 VectorSubtract( p[i], p[0], d2 );
69
70 CrossProduct( d1, d2, cross );
71
72 total += 0.5f * VectorLength( cross );
73 }
74
75 return total;
76 }
77
RemoveColinearPoints()78 void DWinding::RemoveColinearPoints(){
79 vec3_t p2[MAX_POINTS_ON_WINDING];
80
81 int nump = 0;
82 for ( int i = 0; i < numpoints; i++ )
83 {
84 int j = ( i + 1 ) % numpoints;
85 int k = ( i + numpoints - 1 ) % numpoints;
86
87 vec3_t v1, v2;
88 VectorSubtract( p[j], p[i], v1 );
89 VectorSubtract( p[i], p[k], v2 );
90 VectorNormalize( v1, v1 );
91 VectorNormalize( v2, v2 );
92
93 if ( DotProduct( v1, v2 ) < 0.999 ) {
94 VectorCopy( p[i], p2[nump] );
95 nump++;
96 }
97 }
98
99 if ( nump == numpoints ) {
100 return;
101 }
102
103 AllocWinding( nump );
104 memcpy( p, p2, nump * sizeof( vec3_t ) );
105 }
106
WindingPlane()107 DPlane* DWinding::WindingPlane(){
108 DPlane* newPlane = new DPlane( p[0], p[1], p[2], NULL );
109 return newPlane;
110 }
111
WindingBounds(vec3_t mins,vec3_t maxs)112 void DWinding::WindingBounds( vec3_t mins, vec3_t maxs ){
113 if ( numpoints == 0 ) {
114 return;
115 }
116
117 VectorCopy( mins, p[0] );
118 VectorCopy( maxs, p[0] );
119
120 for ( int i = 1; i < numpoints ; i++ )
121 {
122 for ( int j = 0; j < 3; j++ )
123 {
124 vec_t v = p[i][j];
125 if ( v < mins[j] ) {
126 mins[j] = v;
127 }
128 if ( v > maxs[j] ) {
129 maxs[j] = v;
130 }
131 }
132 }
133 }
134
WindingCentre(vec3_t centre)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 );
139
140 float scale = 1.0f / numpoints;
141 VectorScale( centre, scale, centre );
142 }
143
144
CopyWinding()145 DWinding* DWinding::CopyWinding(){
146 DWinding* c = new DWinding;
147 c->AllocWinding( numpoints );
148 memcpy( c->p, p, numpoints * sizeof( vec3_t ) );
149 return c;
150 }
151
152
WindingOnPlaneSide(vec3_t normal,vec_t dist)153 int DWinding::WindingOnPlaneSide( vec3_t normal, vec_t dist ){
154 bool front = false;
155 bool back = false;
156
157 for ( int i = 0; i < numpoints; i++ )
158 {
159 vec_t d = DotProduct( p[i], normal ) - dist;
160 if ( d < -ON_EPSILON ) {
161 if ( front ) {
162 return SIDE_CROSS;
163 }
164 back = true;
165 continue;
166 }
167 if ( d > ON_EPSILON ) {
168 if ( back ) {
169 return SIDE_CROSS;
170 }
171 front = true;
172 continue;
173 }
174 }
175
176 if ( back ) {
177 return SIDE_BACK;
178 }
179 if ( front ) {
180 return SIDE_FRONT;
181 }
182 return SIDE_ON;
183 }
184
CheckWinding()185 void DWinding::CheckWinding(){
186 vec_t *p1, *p2;
187 vec_t edgedist;
188 vec3_t dir, edgenormal;
189
190 if ( numpoints < 3 ) {
191 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
192 }
193
194 vec_t area = WindingArea();
195 if ( area < 1 ) {
196 globalOutputStream() << "CheckWinding: " << area << " area\n";
197 }
198
199 DPlane* wPlane = WindingPlane();
200 int i;
201 for ( i = 0; i < numpoints; i++ )
202 {
203 p1 = p[i];
204
205 int j;
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";
209 }
210
211 j = i + 1 == numpoints ? 0 : i + 1;
212
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";
217 }
218
219 // check the edge isnt degenerate
220 p2 = p[j];
221 VectorSubtract( p2, p1, dir );
222
223 if ( VectorLength( dir ) < ON_EPSILON ) {
224 globalOutputStream() << "CheckWinding: degenerate edge\n";
225 }
226
227 CrossProduct( wPlane->normal, dir, edgenormal );
228 VectorNormalize( edgenormal, edgenormal );
229 edgedist = DotProduct( p1, edgenormal );
230
231 // all other points must be on front side
232 for ( j = 0 ; j < numpoints ; j++ )
233 {
234 if ( j == i ) {
235 continue;
236 }
237
238 d = DotProduct( p[j], edgenormal );
239 if ( d > ( edgedist + ON_EPSILON ) ) {
240 globalOutputStream() << "CheckWinding: non-convex\n";
241 }
242 }
243 }
244
245 delete wPlane;
246 }
247
ReverseWinding()248 DWinding* DWinding::ReverseWinding(){
249 DWinding* c = new DWinding;
250 c->AllocWinding( numpoints );
251
252 for ( int i = 0; i < numpoints ; i++ )
253 VectorCopy( p[numpoints - 1 - i], c->p[i] );
254
255 return c;
256 }
257
ChopWindingInPlace(DPlane * chopPlane,vec_t epsilon)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];
261 int counts[3];
262 vec_t *p1, *p2;
263 vec3_t mid;
264
265 counts[0] = counts[1] = counts[2] = 0;
266
267 // determine sides for each point
268 int i;
269 for ( i = 0; i < numpoints; i++ )
270 {
271 vec_t dot = DotProduct( p[i], chopPlane->normal );
272 dot -= chopPlane->_d;
273 dists[i] = dot;
274
275 if ( dot > epsilon ) {
276 sides[i] = SIDE_FRONT;
277 }
278 else if ( dot < -epsilon ) {
279 sides[i] = SIDE_BACK;
280 }
281 else{
282 sides[i] = SIDE_ON;
283 }
284
285 counts[sides[i]]++;
286 }
287 sides[i] = sides[0];
288 dists[i] = dists[0];
289
290 if ( !counts[0] ) {
291 delete this;
292 return false;
293 }
294
295 if ( !counts[1] ) {
296 return true;
297 }
298
299 int maxpts = numpoints + 4; // cant use counts[0]+2 because
300 // of fp grouping errors
301
302 DWinding* f = new DWinding;
303 f->AllocWinding( maxpts );
304 f->numpoints = 0;
305
306 for ( i = 0; i < numpoints; i++ )
307 {
308 p1 = p[i];
309
310 if ( sides[i] == SIDE_ON ) {
311 VectorCopy( p1, f->p[f->numpoints] );
312 f->numpoints++;
313 continue;
314 }
315
316 if ( sides[i] == SIDE_FRONT ) {
317 VectorCopy( p1, f->p[f->numpoints] );
318 f->numpoints++;
319 }
320
321 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
322 continue;
323 }
324
325 // generate a split point
326 p2 = p[( i + 1 ) % numpoints];
327
328 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
329 for ( int j = 0; j < 3; j++ )
330 {
331 if ( chopPlane->normal[j] == 1 ) {
332 mid[j] = chopPlane->_d;
333 }
334 else if ( chopPlane->normal[j] == -1 ) {
335 mid[j] = -chopPlane->_d;
336 }
337 else{
338 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
339 }
340 }
341
342 VectorCopy( mid, f->p[f->numpoints] );
343 f->numpoints++;
344 }
345
346 if ( f->numpoints > maxpts ) {
347 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
348 }
349 if ( f->numpoints > MAX_POINTS_ON_WINDING ) {
350 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
351 }
352
353 delete[] p;
354 p = f->p;
355 f->p = NULL;
356 delete f;
357 return true;
358 }
359
ClipWindingEpsilon(DPlane * chopPlane,vec_t epsilon,DWinding ** front,DWinding ** back)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];
363 int counts[3];
364 vec_t *p1, *p2;
365 vec3_t mid;
366
367 counts[0] = counts[1] = counts[2] = 0;
368
369 // determine sides for each point
370 int i;
371 for ( i = 0; i < numpoints; i++ )
372 {
373 vec_t dot = -chopPlane->DistanceToPoint( p[i] );
374 dists[i] = dot;
375
376 if ( dot > epsilon ) {
377 sides[i] = SIDE_FRONT;
378 }
379 else if ( dot < -epsilon ) {
380 sides[i] = SIDE_BACK;
381 }
382 else{
383 sides[i] = SIDE_ON;
384 }
385
386 counts[sides[i]]++;
387 }
388 sides[i] = sides[0];
389 dists[i] = dists[0];
390
391 *front = *back = NULL;
392
393 if ( !counts[0] ) {
394 *back = CopyWinding();
395 return;
396 }
397 if ( !counts[1] ) {
398 *front = CopyWinding();
399 return;
400 }
401
402 int maxpts = numpoints + 4; // cant use counts[0]+2 because
403 // of fp grouping errors
404
405 DWinding* f = new DWinding;
406 DWinding* b = new DWinding;
407
408 f->AllocWinding( maxpts );
409 f->numpoints = 0;
410
411 b->AllocWinding( maxpts );
412 b->numpoints = 0;
413
414 *front = f;
415 *back = b;
416
417 for ( i = 0; i < numpoints ; i++ )
418 {
419 p1 = p[i];
420
421 if ( sides[i] == SIDE_ON ) {
422 VectorCopy( p1, f->p[f->numpoints] );
423 f->numpoints++;
424 VectorCopy( p1, b->p[b->numpoints] );
425 b->numpoints++;
426 continue;
427 }
428
429 if ( sides[i] == SIDE_FRONT ) {
430 VectorCopy( p1, f->p[f->numpoints] );
431 f->numpoints++;
432 }
433 if ( sides[i] == SIDE_BACK ) {
434 VectorCopy( p1, b->p[b->numpoints] );
435 b->numpoints++;
436 }
437
438 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
439 continue;
440 }
441
442 // generate a split point
443 p2 = p[( i + 1 ) % numpoints];
444
445 vec_t dot = dists[i] / ( dists[i] - dists[i + 1] );
446 for ( int j = 0; j < 3; j++ )
447 {
448 if ( chopPlane->normal[j] == 1 ) {
449 mid[j] = chopPlane->_d;
450 }
451 else if ( chopPlane->normal[j] == -1 ) {
452 mid[j] = -chopPlane->_d;
453 }
454 else{
455 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
456 }
457 }
458
459 VectorCopy( mid, f->p[f->numpoints] );
460 f->numpoints++;
461 VectorCopy( mid, b->p[b->numpoints] );
462 b->numpoints++;
463 }
464
465 if ( f->numpoints > maxpts || b->numpoints > maxpts ) {
466 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
467 }
468 if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) {
469 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
470 }
471 }
472
ChopWinding(DPlane * chopPlane)473 bool DWinding::ChopWinding( DPlane* chopPlane ){
474 DWinding *f, *b;
475
476 ClipWindingEpsilon( chopPlane, (float)ON_EPSILON, &f, &b );
477
478 if ( b ) {
479 delete ( b );
480 }
481
482
483 if ( !f ) {
484 delete this;
485 return false;
486 }
487
488 delete[] p;
489 p = f->p;
490 f->p = NULL;
491 numpoints = f->numpoints;
492 delete f;
493
494 return true;
495 }
496