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 //////////////////////////////////////////////////////////////////////
47 //////////////////////////////////////////////////////////////////////
49 //////////////////////////////////////////////////////////////////////
51 #define BOGUS_RANGE 4096
53 void DWinding::AllocWinding(int points)
58 p = new vec3_t[points];
61 vec_t DWinding::WindingArea()
67 for (int i = 2; i < numpoints ; i++)
69 VectorSubtract (p[i-1], p[0], d1);
70 VectorSubtract (p[i], p[0], d2);
72 CrossProduct (d1, d2, cross);
74 total += 0.5f * VectorLength ( cross );
80 void DWinding::RemoveColinearPoints()
82 vec3_t p2[MAX_POINTS_ON_WINDING];
85 for (int i = 0; i < numpoints; i++)
87 int j = (i+1)%numpoints;
88 int k = (i+numpoints-1)%numpoints;
91 VectorSubtract (p[j], p[i], v1);
92 VectorSubtract (p[i], p[k], v2);
93 VectorNormalize(v1, v1);
94 VectorNormalize(v2, v2);
96 if (DotProduct(v1, v2) < 0.999)
98 VectorCopy (p[i], p2[nump]);
103 if (nump == numpoints)
107 memcpy (p, p2, nump*sizeof(vec3_t));
110 DPlane* DWinding::WindingPlane()
112 DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);
116 void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)
121 VectorCopy(mins, p[0]);
122 VectorCopy(maxs, p[0]);
124 for (int i = 1; i < numpoints ;i++)
126 for (int j = 0; j < 3; j++)
137 void DWinding::WindingCentre(vec3_t centre)
139 VectorCopy (vec3_origin, centre);
140 for (int i = 0; i < numpoints; i++)
141 VectorAdd (p[i], centre, centre);
143 float scale = 1.0f/numpoints;
144 VectorScale (centre, scale, centre);
148 DWinding* DWinding::CopyWinding()
150 DWinding* c = new DWinding;
151 c->AllocWinding(numpoints);
152 memcpy (c->p, p, numpoints*sizeof(vec3_t));
157 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
162 for (int i = 0; i < numpoints; i++)
164 vec_t d = DotProduct (p[i], normal) - dist;
188 void DWinding::CheckWinding()
192 vec3_t dir, edgenormal;
195 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
197 vec_t area = WindingArea();
199 globalOutputStream() << "CheckWinding: " << area << " area\n";
201 DPlane* wPlane = WindingPlane ();
203 for (i = 0; i < numpoints; i++)
208 for (j = 0; j < 3; j++)
209 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
210 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
212 j = i + 1 == numpoints ? 0 : i + 1;
214 // check the point is on the face plane
215 vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;
216 if (d < -ON_EPSILON || d > ON_EPSILON)
217 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";
226 CrossProduct (wPlane->normal, dir, edgenormal);
227 VectorNormalize (edgenormal, edgenormal);
228 edgedist = DotProduct (p1, edgenormal);
230 // all other points must be on front side
231 for (j = 0 ; j < numpoints ; j++)
236 d = DotProduct (p[j], edgenormal);
237 if (d > (edgedist + ON_EPSILON))
238 globalOutputStream() << "CheckWinding: non-convex\n";
245 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)
258 vec_t dists[MAX_POINTS_ON_WINDING+4];
259 int sides[MAX_POINTS_ON_WINDING+4];
264 counts[0] = counts[1] = counts[2] = 0;
266 // determine sides for each point
268 for (i = 0; i < numpoints; i++)
270 vec_t dot = DotProduct (p[i], chopPlane->normal);
271 dot -= chopPlane->_d;
275 sides[i] = SIDE_FRONT;
276 else if (dot < -epsilon)
277 sides[i] = SIDE_BACK;
295 int maxpts = numpoints+4; // cant use counts[0]+2 because
296 // of fp grouping errors
298 DWinding* f = new DWinding;
299 f->AllocWinding(maxpts);
302 for (i = 0; i < numpoints; i++)
306 if (sides[i] == SIDE_ON)
308 VectorCopy (p1, f->p[f->numpoints]);
313 if (sides[i] == SIDE_FRONT)
315 VectorCopy (p1, f->p[f->numpoints]);
319 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
322 // generate a split point
323 p2 = p[(i+1)%numpoints];
325 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
326 for (int j = 0; j < 3; j++)
328 if (chopPlane->normal[j] == 1)
329 mid[j] = chopPlane->_d;
330 else if (chopPlane->normal[j] == -1)
331 mid[j] = -chopPlane->_d;
333 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
336 VectorCopy (mid, f->p[f->numpoints]);
340 if (f->numpoints > maxpts)
341 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
342 if (f->numpoints > MAX_POINTS_ON_WINDING)
343 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
352 void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
354 vec_t dists[MAX_POINTS_ON_WINDING+4];
355 int sides[MAX_POINTS_ON_WINDING+4];
360 counts[0] = counts[1] = counts[2] = 0;
362 // determine sides for each point
364 for (i = 0; i < numpoints; i++)
366 vec_t dot = -chopPlane->DistanceToPoint(p[i]);
370 sides[i] = SIDE_FRONT;
371 else if (dot < -epsilon)
372 sides[i] = SIDE_BACK;
381 *front = *back = NULL;
385 *back = CopyWinding();
390 *front = CopyWinding();
394 int maxpts = numpoints+4; // cant use counts[0]+2 because
395 // of fp grouping errors
397 DWinding* f = new DWinding;
398 DWinding* b = new DWinding;
400 f->AllocWinding(maxpts);
403 b->AllocWinding(maxpts);
409 for (i = 0; i < numpoints ; i++)
413 if (sides[i] == SIDE_ON)
415 VectorCopy (p1, f->p[f->numpoints]);
417 VectorCopy (p1, b->p[b->numpoints]);
422 if (sides[i] == SIDE_FRONT)
424 VectorCopy (p1, f->p[f->numpoints]);
427 if (sides[i] == SIDE_BACK)
429 VectorCopy (p1, b->p[b->numpoints]);
433 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
436 // generate a split point
437 p2 = p[(i+1)%numpoints];
439 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
440 for (int j = 0; j < 3; j++)
442 if (chopPlane->normal[j] == 1)
443 mid[j] = chopPlane->_d;
444 else if (chopPlane->normal[j] == -1)
445 mid[j] = -chopPlane->_d;
447 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
450 VectorCopy (mid, f->p[f->numpoints]);
452 VectorCopy (mid, b->p[b->numpoints]);
456 if (f->numpoints > maxpts || b->numpoints > maxpts)
457 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
458 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
459 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
462 bool DWinding::ChopWinding(DPlane* chopPlane)
466 ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);
481 numpoints = f->numpoints;