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 //////////////////////////////////////////////////////////////////////
45 //////////////////////////////////////////////////////////////////////
47 //////////////////////////////////////////////////////////////////////
49 #define BOGUS_RANGE 4096
51 void DWinding::AllocWinding(int points)
56 p = new vec3_t[points];
59 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()
80 vec3_t p2[MAX_POINTS_ON_WINDING];
83 for (int i = 0; i < numpoints; i++)
85 int j = (i+1)%numpoints;
86 int k = (i+numpoints-1)%numpoints;
89 VectorSubtract (p[j], p[i], v1);
90 VectorSubtract (p[i], p[k], v2);
91 VectorNormalize(v1, v1);
92 VectorNormalize(v2, v2);
94 if (DotProduct(v1, v2) < 0.999)
96 VectorCopy (p[i], p2[nump]);
101 if (nump == numpoints)
105 memcpy (p, p2, nump*sizeof(vec3_t));
108 DPlane* DWinding::WindingPlane()
110 DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);
114 void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)
119 VectorCopy(mins, p[0]);
120 VectorCopy(maxs, p[0]);
122 for (int i = 1; i < numpoints ;i++)
124 for (int j = 0; j < 3; j++)
135 void DWinding::WindingCentre(vec3_t centre)
137 VectorCopy (vec3_origin, centre);
138 for (int i = 0; i < numpoints; i++)
139 VectorAdd (p[i], centre, centre);
141 float scale = 1.0f/numpoints;
142 VectorScale (centre, scale, centre);
146 DWinding* DWinding::CopyWinding()
148 DWinding* c = new DWinding;
149 c->AllocWinding(numpoints);
150 memcpy (c->p, p, numpoints*sizeof(vec3_t));
155 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
160 for (int i = 0; i < numpoints; i++)
162 vec_t d = DotProduct (p[i], normal) - dist;
186 void DWinding::CheckWinding()
190 vec3_t dir, edgenormal;
193 Sys_Printf ("CheckWinding: %i points", numpoints);
195 vec_t area = WindingArea();
197 Sys_Printf ("CheckWinding: %f area", area);
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 Sys_Printf ("CheckFace: BUGUS_RANGE: %f", p1[j]);
210 j = i + 1 == numpoints ? 0 : i + 1;
212 // check the point is on the face plane
213 vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;
214 if (d < -ON_EPSILON || d > ON_EPSILON)
215 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");
224 CrossProduct (wPlane->normal, dir, edgenormal);
225 VectorNormalize (edgenormal, edgenormal);
226 edgedist = DotProduct (p1, edgenormal);
228 // all other points must be on front side
229 for (j = 0 ; j < numpoints ; j++)
234 d = DotProduct (p[j], edgenormal);
235 if (d > (edgedist + ON_EPSILON))
236 Sys_Printf ("CheckWinding: non-convex");
243 DWinding* DWinding::ReverseWinding()
245 DWinding* c = new DWinding;
246 c->AllocWinding(numpoints);
248 for (int i = 0; i < numpoints ; i++)
249 VectorCopy (p[numpoints-1-i], c->p[i]);
254 bool DWinding::ChopWindingInPlace(DPlane* chopPlane, vec_t epsilon)
256 vec_t dists[MAX_POINTS_ON_WINDING+4];
257 int sides[MAX_POINTS_ON_WINDING+4];
262 counts[0] = counts[1] = counts[2] = 0;
264 // determine sides for each point
266 for (i = 0; i < numpoints; i++)
268 vec_t dot = DotProduct (p[i], chopPlane->normal);
269 dot -= chopPlane->_d;
273 sides[i] = SIDE_FRONT;
274 else if (dot < -epsilon)
275 sides[i] = SIDE_BACK;
293 int maxpts = numpoints+4; // cant use counts[0]+2 because
294 // of fp grouping errors
296 DWinding* f = new DWinding;
297 f->AllocWinding(maxpts);
300 for (i = 0; i < numpoints; i++)
304 if (sides[i] == SIDE_ON)
306 VectorCopy (p1, f->p[f->numpoints]);
311 if (sides[i] == SIDE_FRONT)
313 VectorCopy (p1, f->p[f->numpoints]);
317 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
320 // generate a split point
321 p2 = p[(i+1)%numpoints];
323 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
324 for (int j = 0; j < 3; j++)
326 if (chopPlane->normal[j] == 1)
327 mid[j] = chopPlane->_d;
328 else if (chopPlane->normal[j] == -1)
329 mid[j] = -chopPlane->_d;
331 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
334 VectorCopy (mid, f->p[f->numpoints]);
338 if (f->numpoints > maxpts)
339 Sys_Printf ("ClipWinding: points exceeded estimate");
340 if (f->numpoints > MAX_POINTS_ON_WINDING)
341 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");
350 void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
352 vec_t dists[MAX_POINTS_ON_WINDING+4];
353 int sides[MAX_POINTS_ON_WINDING+4];
358 counts[0] = counts[1] = counts[2] = 0;
360 // determine sides for each point
362 for (i = 0; i < numpoints; i++)
364 vec_t dot = -chopPlane->DistanceToPoint(p[i]);
368 sides[i] = SIDE_FRONT;
369 else if (dot < -epsilon)
370 sides[i] = SIDE_BACK;
379 *front = *back = NULL;
383 *back = CopyWinding();
388 *front = CopyWinding();
392 int maxpts = numpoints+4; // cant use counts[0]+2 because
393 // of fp grouping errors
395 DWinding* f = new DWinding;
396 DWinding* b = new DWinding;
398 f->AllocWinding(maxpts);
401 b->AllocWinding(maxpts);
407 for (i = 0; i < numpoints ; i++)
411 if (sides[i] == SIDE_ON)
413 VectorCopy (p1, f->p[f->numpoints]);
415 VectorCopy (p1, b->p[b->numpoints]);
420 if (sides[i] == SIDE_FRONT)
422 VectorCopy (p1, f->p[f->numpoints]);
425 if (sides[i] == SIDE_BACK)
427 VectorCopy (p1, b->p[b->numpoints]);
431 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
434 // generate a split point
435 p2 = p[(i+1)%numpoints];
437 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
438 for (int j = 0; j < 3; j++)
440 if (chopPlane->normal[j] == 1)
441 mid[j] = chopPlane->_d;
442 else if (chopPlane->normal[j] == -1)
443 mid[j] = -chopPlane->_d;
445 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
448 VectorCopy (mid, f->p[f->numpoints]);
450 VectorCopy (mid, b->p[b->numpoints]);
454 if (f->numpoints > maxpts || b->numpoints > maxpts)
455 Sys_Printf ("ClipWinding: points exceeded estimate");
456 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
457 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");
460 bool DWinding::ChopWinding(DPlane* chopPlane)
464 ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);
479 numpoints = f->numpoints;