2 BobToolz plugin for GtkRadiant
\r
3 Copyright (C) 2001 Gordon Biggans
\r
5 This library is free software; you can redistribute it and/or
\r
6 modify it under the terms of the GNU Lesser General Public
\r
7 License as published by the Free Software Foundation; either
\r
8 version 2.1 of the License, or (at your option) any later version.
\r
10 This library is distributed in the hope that it will be useful,
\r
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
\r
13 Lesser General Public License for more details.
\r
15 You should have received a copy of the GNU Lesser General Public
\r
16 License along with this library; if not, write to the Free Software
\r
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
\r
20 // DWinding.cpp: implementation of the DWinding class.
\r
22 //////////////////////////////////////////////////////////////////////
\r
25 #include "DWinding.h"
\r
29 //////////////////////////////////////////////////////////////////////
\r
30 // Construction/Destruction
\r
31 //////////////////////////////////////////////////////////////////////
\r
33 DWinding::DWinding()
\r
39 DWinding::~DWinding()
\r
45 //////////////////////////////////////////////////////////////////////
\r
47 //////////////////////////////////////////////////////////////////////
\r
49 #define BOGUS_RANGE 4096
\r
51 void DWinding::AllocWinding(int points)
\r
56 p = new vec3_t[points];
\r
59 vec_t DWinding::WindingArea()
\r
61 vec3_t d1, d2, cross;
\r
65 for (int i = 2; i < numpoints ; i++)
\r
67 VectorSubtract (p[i-1], p[0], d1);
\r
68 VectorSubtract (p[i], p[0], d2);
\r
70 CrossProduct (d1, d2, cross);
\r
72 total += 0.5f * VectorLength ( cross );
\r
78 void DWinding::RemoveColinearPoints()
\r
80 vec3_t p2[MAX_POINTS_ON_WINDING];
\r
83 for (int i = 0; i < numpoints; i++)
\r
85 int j = (i+1)%numpoints;
\r
86 int k = (i+numpoints-1)%numpoints;
\r
89 VectorSubtract (p[j], p[i], v1);
\r
90 VectorSubtract (p[i], p[k], v2);
\r
91 VectorNormalize(v1, v1);
\r
92 VectorNormalize(v2, v2);
\r
94 if (DotProduct(v1, v2) < 0.999)
\r
96 VectorCopy (p[i], p2[nump]);
\r
101 if (nump == numpoints)
\r
104 AllocWinding(nump);
\r
105 memcpy (p, p2, nump*sizeof(vec3_t));
\r
108 DPlane* DWinding::WindingPlane()
\r
110 DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);
\r
114 void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)
\r
119 VectorCopy(mins, p[0]);
\r
120 VectorCopy(maxs, p[0]);
\r
122 for (int i = 1; i < numpoints ;i++)
\r
124 for (int j = 0; j < 3; j++)
\r
135 void DWinding::WindingCentre(vec3_t centre)
\r
137 VectorCopy (vec3_origin, centre);
\r
138 for (int i = 0; i < numpoints; i++)
\r
139 VectorAdd (p[i], centre, centre);
\r
141 float scale = 1.0f/numpoints;
\r
142 VectorScale (centre, scale, centre);
\r
146 DWinding* DWinding::CopyWinding()
\r
148 DWinding* c = new DWinding;
\r
149 c->AllocWinding(numpoints);
\r
150 memcpy (c->p, p, numpoints*sizeof(vec3_t));
\r
155 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
\r
157 bool front = FALSE;
\r
160 for (int i = 0; i < numpoints; i++)
\r
162 vec_t d = DotProduct (p[i], normal) - dist;
\r
163 if (d < -ON_EPSILON)
\r
170 if (d > ON_EPSILON)
\r
186 void DWinding::CheckWinding()
\r
190 vec3_t dir, edgenormal;
\r
193 Sys_Printf ("CheckWinding: %i points", numpoints);
\r
195 vec_t area = WindingArea();
\r
197 Sys_Printf ("CheckWinding: %f area", area);
\r
199 DPlane* wPlane = WindingPlane ();
\r
201 for (i = 0; i < numpoints; i++)
\r
206 for (j = 0; j < 3; j++)
\r
207 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
\r
208 Sys_Printf ("CheckFace: BUGUS_RANGE: %f", p1[j]);
\r
210 j = i + 1 == numpoints ? 0 : i + 1;
\r
212 // check the point is on the face plane
\r
213 vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;
\r
214 if (d < -ON_EPSILON || d > ON_EPSILON)
\r
215 Sys_Printf ("CheckWinding: point off plane");
\r
217 // check the edge isnt degenerate
\r
219 VectorSubtract (p2, p1, dir);
\r
221 if (VectorLength (dir) < ON_EPSILON)
\r
222 Sys_Printf ("CheckWinding: degenerate edge");
\r
224 CrossProduct (wPlane->normal, dir, edgenormal);
\r
225 VectorNormalize (edgenormal, edgenormal);
\r
226 edgedist = DotProduct (p1, edgenormal);
\r
228 // all other points must be on front side
\r
229 for (j = 0 ; j < numpoints ; j++)
\r
234 d = DotProduct (p[j], edgenormal);
\r
235 if (d > (edgedist + ON_EPSILON))
\r
236 Sys_Printf ("CheckWinding: non-convex");
\r
243 DWinding* DWinding::ReverseWinding()
\r
245 DWinding* c = new DWinding;
\r
246 c->AllocWinding(numpoints);
\r
248 for (int i = 0; i < numpoints ; i++)
\r
249 VectorCopy (p[numpoints-1-i], c->p[i]);
\r
254 bool DWinding::ChopWindingInPlace(DPlane* chopPlane, vec_t epsilon)
\r
256 vec_t dists[MAX_POINTS_ON_WINDING+4];
\r
257 int sides[MAX_POINTS_ON_WINDING+4];
\r
262 counts[0] = counts[1] = counts[2] = 0;
\r
264 // determine sides for each point
\r
266 for (i = 0; i < numpoints; i++)
\r
268 vec_t dot = DotProduct (p[i], chopPlane->normal);
\r
269 dot -= chopPlane->_d;
\r
273 sides[i] = SIDE_FRONT;
\r
274 else if (dot < -epsilon)
\r
275 sides[i] = SIDE_BACK;
\r
277 sides[i] = SIDE_ON;
\r
279 counts[sides[i]]++;
\r
281 sides[i] = sides[0];
\r
282 dists[i] = dists[0];
\r
293 int maxpts = numpoints+4; // cant use counts[0]+2 because
\r
294 // of fp grouping errors
\r
296 DWinding* f = new DWinding;
\r
297 f->AllocWinding(maxpts);
\r
300 for (i = 0; i < numpoints; i++)
\r
304 if (sides[i] == SIDE_ON)
\r
306 VectorCopy (p1, f->p[f->numpoints]);
\r
311 if (sides[i] == SIDE_FRONT)
\r
313 VectorCopy (p1, f->p[f->numpoints]);
\r
317 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
\r
320 // generate a split point
\r
321 p2 = p[(i+1)%numpoints];
\r
323 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
\r
324 for (int j = 0; j < 3; j++)
\r
326 if (chopPlane->normal[j] == 1)
\r
327 mid[j] = chopPlane->_d;
\r
328 else if (chopPlane->normal[j] == -1)
\r
329 mid[j] = -chopPlane->_d;
\r
331 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
\r
334 VectorCopy (mid, f->p[f->numpoints]);
\r
338 if (f->numpoints > maxpts)
\r
339 Sys_Printf ("ClipWinding: points exceeded estimate");
\r
340 if (f->numpoints > MAX_POINTS_ON_WINDING)
\r
341 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");
\r
350 void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
\r
352 vec_t dists[MAX_POINTS_ON_WINDING+4];
\r
353 int sides[MAX_POINTS_ON_WINDING+4];
\r
358 counts[0] = counts[1] = counts[2] = 0;
\r
360 // determine sides for each point
\r
362 for (i = 0; i < numpoints; i++)
\r
364 vec_t dot = -chopPlane->DistanceToPoint(p[i]);
\r
368 sides[i] = SIDE_FRONT;
\r
369 else if (dot < -epsilon)
\r
370 sides[i] = SIDE_BACK;
\r
372 sides[i] = SIDE_ON;
\r
374 counts[sides[i]]++;
\r
376 sides[i] = sides[0];
\r
377 dists[i] = dists[0];
\r
379 *front = *back = NULL;
\r
383 *back = CopyWinding();
\r
388 *front = CopyWinding();
\r
392 int maxpts = numpoints+4; // cant use counts[0]+2 because
\r
393 // of fp grouping errors
\r
395 DWinding* f = new DWinding;
\r
396 DWinding* b = new DWinding;
\r
398 f->AllocWinding(maxpts);
\r
401 b->AllocWinding(maxpts);
\r
407 for (i = 0; i < numpoints ; i++)
\r
411 if (sides[i] == SIDE_ON)
\r
413 VectorCopy (p1, f->p[f->numpoints]);
\r
415 VectorCopy (p1, b->p[b->numpoints]);
\r
420 if (sides[i] == SIDE_FRONT)
\r
422 VectorCopy (p1, f->p[f->numpoints]);
\r
425 if (sides[i] == SIDE_BACK)
\r
427 VectorCopy (p1, b->p[b->numpoints]);
\r
431 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
\r
434 // generate a split point
\r
435 p2 = p[(i+1)%numpoints];
\r
437 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
\r
438 for (int j = 0; j < 3; j++)
\r
440 if (chopPlane->normal[j] == 1)
\r
441 mid[j] = chopPlane->_d;
\r
442 else if (chopPlane->normal[j] == -1)
\r
443 mid[j] = -chopPlane->_d;
\r
445 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
\r
448 VectorCopy (mid, f->p[f->numpoints]);
\r
450 VectorCopy (mid, b->p[b->numpoints]);
\r
454 if (f->numpoints > maxpts || b->numpoints > maxpts)
\r
455 Sys_Printf ("ClipWinding: points exceeded estimate");
\r
456 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
\r
457 Sys_Printf ("ClipWinding: MAX_POINTS_ON_WINDING");
\r
460 bool DWinding::ChopWinding(DPlane* chopPlane)
\r
464 ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);
\r
479 numpoints = f->numpoints;
\r