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 //////////////////////////////////////////////////////////////////////
48 //////////////////////////////////////////////////////////////////////
50 //////////////////////////////////////////////////////////////////////
52 const int BOGUS_RANGE = 4096;
54 void DWinding::AllocWinding(int points)
60 p = new vec3_t[points];
63 vec_t DWinding::WindingArea()
69 for (int i = 2; i < numpoints; i++) {
70 VectorSubtract(p[i - 1], p[0], d1);
71 VectorSubtract(p[i], p[0], d2);
73 CrossProduct(d1, d2, cross);
75 total += 0.5f * VectorLength(cross);
81 void DWinding::RemoveColinearPoints()
83 vec3_t p2[MAX_POINTS_ON_WINDING];
86 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) {
97 VectorCopy(p[i], p2[nump]);
102 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)
118 if (numpoints == 0) {
122 VectorCopy(mins, p[0]);
123 VectorCopy(maxs, p[0]);
125 for (int i = 1; i < numpoints; i++) {
126 for (int j = 0; j < 3; j++) {
138 void DWinding::WindingCentre(vec3_t centre)
140 VectorCopy(vec3_origin, centre);
141 for (int i = 0; i < numpoints; i++)
142 VectorAdd(p[i], centre, centre);
144 float scale = 1.0f / numpoints;
145 VectorScale(centre, scale, centre);
149 DWinding *DWinding::CopyWinding()
151 DWinding *c = new DWinding;
152 c->AllocWinding(numpoints);
153 memcpy(c->p, p, numpoints * sizeof(vec3_t));
158 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
163 for (int i = 0; i < numpoints; i++) {
164 vec_t d = DotProduct(p[i], normal) - dist;
165 if (d < -ON_EPSILON) {
172 if (d > ON_EPSILON) {
190 void DWinding::CheckWinding()
194 vec3_t dir, edgenormal;
197 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
200 vec_t area = WindingArea();
202 globalOutputStream() << "CheckWinding: " << area << " area\n";
205 DPlane *wPlane = WindingPlane();
207 for (i = 0; i < numpoints; i++) {
211 for (j = 0; j < 3; j++) {
212 if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE) {
213 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
217 j = i + 1 == numpoints ? 0 : i + 1;
219 // check the point is on the face plane
220 vec_t d = DotProduct(p1, wPlane->normal) - wPlane->_d;
221 if (d < -ON_EPSILON || d > ON_EPSILON) {
222 globalOutputStream() << "CheckWinding: point off plane\n";
225 // check the edge isnt degenerate
227 VectorSubtract(p2, p1, dir);
229 if (VectorLength(dir) < ON_EPSILON) {
230 globalOutputStream() << "CheckWinding: degenerate edge\n";
233 CrossProduct(wPlane->normal, dir, edgenormal);
234 VectorNormalize(edgenormal, edgenormal);
235 edgedist = DotProduct(p1, edgenormal);
237 // all other points must be on front side
238 for (j = 0; j < numpoints; j++) {
243 d = DotProduct(p[j], edgenormal);
244 if (d > (edgedist + ON_EPSILON)) {
245 globalOutputStream() << "CheckWinding: non-convex\n";
253 DWinding *DWinding::ReverseWinding()
255 DWinding *c = new DWinding;
256 c->AllocWinding(numpoints);
258 for (int i = 0; i < numpoints; i++)
259 VectorCopy(p[numpoints - 1 - i], c->p[i]);
264 bool DWinding::ChopWindingInPlace(DPlane *chopPlane, vec_t epsilon)
266 vec_t dists[MAX_POINTS_ON_WINDING + 4];
267 int sides[MAX_POINTS_ON_WINDING + 4];
272 counts[0] = counts[1] = counts[2] = 0;
274 // determine sides for each point
276 for (i = 0; i < numpoints; i++) {
277 vec_t dot = DotProduct(p[i], chopPlane->normal);
278 dot -= chopPlane->_d;
282 sides[i] = SIDE_FRONT;
283 } else if (dot < -epsilon) {
284 sides[i] = SIDE_BACK;
303 int maxpts = numpoints + 4; // cant use counts[0]+2 because
304 // of fp grouping errors
306 DWinding *f = new DWinding;
307 f->AllocWinding(maxpts);
310 for (i = 0; i < numpoints; i++) {
313 if (sides[i] == SIDE_ON) {
314 VectorCopy(p1, f->p[f->numpoints]);
319 if (sides[i] == SIDE_FRONT) {
320 VectorCopy(p1, f->p[f->numpoints]);
324 if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i]) {
328 // generate a split point
329 p2 = p[(i + 1) % numpoints];
331 vec_t dot = dists[i] / (dists[i] - dists[i + 1]);
332 for (int j = 0; j < 3; j++) {
333 if (chopPlane->normal[j] == 1) {
334 mid[j] = chopPlane->_d;
335 } else if (chopPlane->normal[j] == -1) {
336 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)
362 vec_t dists[MAX_POINTS_ON_WINDING + 4];
363 int sides[MAX_POINTS_ON_WINDING + 4];
368 counts[0] = counts[1] = counts[2] = 0;
370 // determine sides for each point
372 for (i = 0; i < numpoints; i++) {
373 vec_t dot = -chopPlane->DistanceToPoint(p[i]);
377 sides[i] = SIDE_FRONT;
378 } else if (dot < -epsilon) {
379 sides[i] = SIDE_BACK;
389 *front = *back = NULL;
392 *back = CopyWinding();
396 *front = CopyWinding();
400 int maxpts = numpoints + 4; // cant use counts[0]+2 because
401 // of fp grouping errors
403 DWinding *f = new DWinding;
404 DWinding *b = new DWinding;
406 f->AllocWinding(maxpts);
409 b->AllocWinding(maxpts);
415 for (i = 0; i < numpoints; i++) {
418 if (sides[i] == SIDE_ON) {
419 VectorCopy(p1, f->p[f->numpoints]);
421 VectorCopy(p1, b->p[b->numpoints]);
426 if (sides[i] == SIDE_FRONT) {
427 VectorCopy(p1, f->p[f->numpoints]);
430 if (sides[i] == SIDE_BACK) {
431 VectorCopy(p1, b->p[b->numpoints]);
435 if (sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i]) {
439 // generate a split point
440 p2 = p[(i + 1) % numpoints];
442 vec_t dot = dists[i] / (dists[i] - dists[i + 1]);
443 for (int j = 0; j < 3; j++) {
444 if (chopPlane->normal[j] == 1) {
445 mid[j] = chopPlane->_d;
446 } else if (chopPlane->normal[j] == -1) {
447 mid[j] = -chopPlane->_d;
449 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
453 VectorCopy(mid, f->p[f->numpoints]);
455 VectorCopy(mid, b->p[b->numpoints]);
459 if (f->numpoints > maxpts || b->numpoints > maxpts) {
460 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
462 if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING) {
463 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
467 bool DWinding::ChopWinding(DPlane *chopPlane)
471 ClipWindingEpsilon(chopPlane, (float) ON_EPSILON, &f, &b);
486 numpoints = f->numpoints;