--- /dev/null
+/*
+BobToolz plugin for GtkRadiant
+Copyright (C) 2001 Gordon Biggans
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+// DWinding.cpp: implementation of the DWinding class.
+//
+//////////////////////////////////////////////////////////////////////
+
+#include "DWinding.h"
+
+#include <list>
+
+#include "DPoint.h"
+#include "DPlane.h"
+
+//////////////////////////////////////////////////////////////////////
+// Construction/Destruction
+//////////////////////////////////////////////////////////////////////
+
+DWinding::DWinding()
+{
+ numpoints = 0;
+ p = NULL;
+}
+
+DWinding::~DWinding()
+{
+ if(p)
+ delete[] p;
+}
+
+//////////////////////////////////////////////////////////////////////
+// Implementation
+//////////////////////////////////////////////////////////////////////
+
+#define BOGUS_RANGE 4096
+
+void DWinding::AllocWinding(int points)
+{
+ numpoints = points;
+ if(p)
+ delete[] p;
+ p = new vec3_t[points];
+}
+
+vec_t DWinding::WindingArea()
+{
+ vec3_t d1, d2, cross;
+ vec_t total;
+
+ total = 0;
+ for (int i = 2; i < numpoints ; i++)
+ {
+ VectorSubtract (p[i-1], p[0], d1);
+ VectorSubtract (p[i], p[0], d2);
+
+ CrossProduct (d1, d2, cross);
+
+ total += 0.5f * VectorLength ( cross );
+ }
+
+ return total;
+}
+
+void DWinding::RemoveColinearPoints()
+{
+ vec3_t p2[MAX_POINTS_ON_WINDING];
+
+ int nump = 0;
+ for (int i = 0; i < numpoints; i++)
+ {
+ int j = (i+1)%numpoints;
+ int k = (i+numpoints-1)%numpoints;
+
+ vec3_t v1, v2;
+ VectorSubtract (p[j], p[i], v1);
+ VectorSubtract (p[i], p[k], v2);
+ VectorNormalize(v1, v1);
+ VectorNormalize(v2, v2);
+
+ if (DotProduct(v1, v2) < 0.999)
+ {
+ VectorCopy (p[i], p2[nump]);
+ nump++;
+ }
+ }
+
+ if (nump == numpoints)
+ return;
+
+ AllocWinding(nump);
+ memcpy (p, p2, nump*sizeof(vec3_t));
+}
+
+DPlane* DWinding::WindingPlane()
+{
+ DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);
+ return newPlane;
+}
+
+void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)
+{
+ if(numpoints == 0)
+ return;
+
+ VectorCopy(mins, p[0]);
+ VectorCopy(maxs, p[0]);
+
+ for (int i = 1; i < numpoints ;i++)
+ {
+ for (int j = 0; j < 3; j++)
+ {
+ vec_t v = p[i][j];
+ if (v < mins[j])
+ mins[j] = v;
+ if (v > maxs[j])
+ maxs[j] = v;
+ }
+ }
+}
+
+void DWinding::WindingCentre(vec3_t centre)
+{
+ VectorCopy (vec3_origin, centre);
+ for (int i = 0; i < numpoints; i++)
+ VectorAdd (p[i], centre, centre);
+
+ float scale = 1.0f/numpoints;
+ VectorScale (centre, scale, centre);
+}
+
+
+DWinding* DWinding::CopyWinding()
+{
+ DWinding* c = new DWinding;
+ c->AllocWinding(numpoints);
+ memcpy (c->p, p, numpoints*sizeof(vec3_t));
+ return c;
+}
+
+
+int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
+{
+ bool front = false;
+ bool back = false;
+
+ for (int i = 0; i < numpoints; i++)
+ {
+ vec_t d = DotProduct (p[i], normal) - dist;
+ if (d < -ON_EPSILON)
+ {
+ if (front)
+ return SIDE_CROSS;
+ back = true;
+ continue;
+ }
+ if (d > ON_EPSILON)
+ {
+ if (back)
+ return SIDE_CROSS;
+ front = true;
+ continue;
+ }
+ }
+
+ if (back)
+ return SIDE_BACK;
+ if (front)
+ return SIDE_FRONT;
+ return SIDE_ON;
+}
+
+void DWinding::CheckWinding()
+{
+ vec_t *p1, *p2;
+ vec_t edgedist;
+ vec3_t dir, edgenormal;
+
+ if (numpoints < 3)
+ globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
+
+ vec_t area = WindingArea();
+ if (area < 1)
+ globalOutputStream() << "CheckWinding: " << area << " area\n";
+
+ DPlane* wPlane = WindingPlane ();
+ int i;
+ for (i = 0; i < numpoints; i++)
+ {
+ p1 = p[i];
+
+ int j;
+ for (j = 0; j < 3; j++)
+ if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
+ globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
+
+ j = i + 1 == numpoints ? 0 : i + 1;
+
+ // check the point is on the face plane
+ vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;
+ if (d < -ON_EPSILON || d > ON_EPSILON)
+ globalOutputStream() << "CheckWinding: point off plane\n";
+
+ // check the edge isnt degenerate
+ p2 = p[j];
+ VectorSubtract (p2, p1, dir);
+
+ if (VectorLength (dir) < ON_EPSILON)
+ globalOutputStream() << "CheckWinding: degenerate edge\n";
+
+ CrossProduct (wPlane->normal, dir, edgenormal);
+ VectorNormalize (edgenormal, edgenormal);
+ edgedist = DotProduct (p1, edgenormal);
+
+ // all other points must be on front side
+ for (j = 0 ; j < numpoints ; j++)
+ {
+ if (j == i)
+ continue;
+
+ d = DotProduct (p[j], edgenormal);
+ if (d > (edgedist + ON_EPSILON))
+ globalOutputStream() << "CheckWinding: non-convex\n";
+ }
+ }
+
+ delete wPlane;
+}
+
+DWinding* DWinding::ReverseWinding()
+{
+ DWinding* c = new DWinding;
+ c->AllocWinding(numpoints);
+
+ for (int i = 0; i < numpoints ; i++)
+ VectorCopy (p[numpoints-1-i], c->p[i]);
+
+ return c;
+}
+
+bool DWinding::ChopWindingInPlace(DPlane* chopPlane, vec_t epsilon)
+{
+ vec_t dists[MAX_POINTS_ON_WINDING+4];
+ int sides[MAX_POINTS_ON_WINDING+4];
+ int counts[3];
+ vec_t *p1, *p2;
+ vec3_t mid;
+
+ counts[0] = counts[1] = counts[2] = 0;
+
+// determine sides for each point
+ int i;
+ for (i = 0; i < numpoints; i++)
+ {
+ vec_t dot = DotProduct (p[i], chopPlane->normal);
+ dot -= chopPlane->_d;
+ dists[i] = dot;
+
+ if (dot > epsilon)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -epsilon)
+ sides[i] = SIDE_BACK;
+ else
+ sides[i] = SIDE_ON;
+
+ counts[sides[i]]++;
+ }
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ if (!counts[0])
+ {
+ delete this;
+ return false;
+ }
+
+ if (!counts[1])
+ return true;
+
+ int maxpts = numpoints+4; // cant use counts[0]+2 because
+ // of fp grouping errors
+
+ DWinding* f = new DWinding;
+ f->AllocWinding(maxpts);
+ f->numpoints = 0;
+
+ for (i = 0; i < numpoints; i++)
+ {
+ p1 = p[i];
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ // generate a split point
+ p2 = p[(i+1)%numpoints];
+
+ vec_t dot = dists[i] / (dists[i]-dists[i+1]);
+ for (int j = 0; j < 3; j++)
+ {
+ if (chopPlane->normal[j] == 1)
+ mid[j] = chopPlane->_d;
+ else if (chopPlane->normal[j] == -1)
+ mid[j] = -chopPlane->_d;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+
+ if (f->numpoints > maxpts)
+ globalOutputStream() << "ClipWinding: points exceeded estimate\n";
+ if (f->numpoints > MAX_POINTS_ON_WINDING)
+ globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
+
+ delete[] p;
+ p = f->p;
+ f->p = NULL;
+ delete f;
+ return true;
+}
+
+void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
+{
+ vec_t dists[MAX_POINTS_ON_WINDING+4];
+ int sides[MAX_POINTS_ON_WINDING+4];
+ int counts[3];
+ vec_t *p1, *p2;
+ vec3_t mid;
+
+ counts[0] = counts[1] = counts[2] = 0;
+
+// determine sides for each point
+ int i;
+ for (i = 0; i < numpoints; i++)
+ {
+ vec_t dot = -chopPlane->DistanceToPoint(p[i]);
+ dists[i] = dot;
+
+ if (dot > epsilon)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -epsilon)
+ sides[i] = SIDE_BACK;
+ else
+ sides[i] = SIDE_ON;
+
+ counts[sides[i]]++;
+ }
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ *front = *back = NULL;
+
+ if (!counts[0])
+ {
+ *back = CopyWinding();
+ return;
+ }
+ if (!counts[1])
+ {
+ *front = CopyWinding();
+ return;
+ }
+
+ int maxpts = numpoints+4; // cant use counts[0]+2 because
+ // of fp grouping errors
+
+ DWinding* f = new DWinding;
+ DWinding* b = new DWinding;
+
+ f->AllocWinding(maxpts);
+ f->numpoints = 0;
+
+ b->AllocWinding(maxpts);
+ b->numpoints = 0;
+
+ *front = f;
+ *back = b;
+
+ for (i = 0; i < numpoints ; i++)
+ {
+ p1 = p[i];
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ VectorCopy (p1, b->p[b->numpoints]);
+ b->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, f->p[f->numpoints]);
+ f->numpoints++;
+ }
+ if (sides[i] == SIDE_BACK)
+ {
+ VectorCopy (p1, b->p[b->numpoints]);
+ b->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ // generate a split point
+ p2 = p[(i+1)%numpoints];
+
+ vec_t dot = dists[i] / (dists[i]-dists[i+1]);
+ for (int j = 0; j < 3; j++)
+ {
+ if (chopPlane->normal[j] == 1)
+ mid[j] = chopPlane->_d;
+ else if (chopPlane->normal[j] == -1)
+ mid[j] = -chopPlane->_d;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, f->p[f->numpoints]);
+ f->numpoints++;
+ VectorCopy (mid, b->p[b->numpoints]);
+ b->numpoints++;
+ }
+
+ if (f->numpoints > maxpts || b->numpoints > maxpts)
+ globalOutputStream() << "ClipWinding: points exceeded estimate\n";
+ if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
+ globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
+}
+
+bool DWinding::ChopWinding(DPlane* chopPlane)
+{
+ DWinding *f, *b;
+
+ ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);
+
+ if (b)
+ delete (b);
+
+
+ if(!f)
+ {
+ delete this;
+ return false;
+ }
+
+ delete[] p;
+ p = f->p;
+ f->p = NULL;
+ numpoints = f->numpoints;
+ delete f;
+
+ return true;
+}
projects / voretournament / voretournament.git / blobdiff