X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=radiant%2Fwinding.cpp;h=608451102c1eab8827889f7f3ff2395ffe764fab;hb=ef66faa7fed7cac452d5fb49a3a69b741816f80f;hp=bba895013c7da78c00069c69a7c9a29d4a77f305;hpb=12b372f89ce109a4db9d510884fbe7d05af79870;p=xonotic%2Fnetradiant.git diff --git a/radiant/winding.cpp b/radiant/winding.cpp index bba89501..60845110 100644 --- a/radiant/winding.cpp +++ b/radiant/winding.cpp @@ -1,346 +1,837 @@ /* -Copyright (C) 1999-2006 Id Software, Inc. and contributors. -For a list of contributors, see the accompanying CONTRIBUTORS file. + Copyright (C) 1999-2007 id Software, Inc. and contributors. + For a list of contributors, see the accompanying CONTRIBUTORS file. -This file is part of GtkRadiant. + This file is part of GtkRadiant. -GtkRadiant is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + GtkRadiant is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -GtkRadiant 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 General Public License for more details. + GtkRadiant 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 General Public License for more details. -You should have received a copy of the GNU General Public License -along with GtkRadiant; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -*/ + You should have received a copy of the GNU General Public License + along with GtkRadiant; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ -#include "winding.h" -#include -#include "math/line.h" +#include "stdafx.h" +#include +#include "winding.h" +#define BOGUS_RANGE ( g_MaxWorldCoord + 1 ) -inline double plane3_distance_to_point(const Plane3& plane, const DoubleVector3& point) -{ - return vector3_dot(point, plane.normal()) - plane.dist(); -} - -inline double plane3_distance_to_point(const Plane3& plane, const Vector3& point) -{ - return vector3_dot(point, plane.normal()) - plane.dist(); +/* + ============= + Plane_Equal + ============= + */ +#define NORMAL_EPSILON 0.0001 +#define DIST_EPSILON 0.02 + +int Plane_Equal( plane_t *a, plane_t *b, int flip ){ + vec3_t normal; + float dist; + + if ( flip ) { + normal[0] = -b->normal[0]; + normal[1] = -b->normal[1]; + normal[2] = -b->normal[2]; + dist = -b->dist; + } + else { + normal[0] = b->normal[0]; + normal[1] = b->normal[1]; + normal[2] = b->normal[2]; + dist = b->dist; + } + if ( + fabs( a->normal[0] - normal[0] ) < NORMAL_EPSILON + && fabs( a->normal[1] - normal[1] ) < NORMAL_EPSILON + && fabs( a->normal[2] - normal[2] ) < NORMAL_EPSILON + && fabs( a->dist - dist ) < DIST_EPSILON ) { + return true; + } + return false; } -/// \brief Returns the point at which \p line intersects \p plane, or an undefined value if there is no intersection. -inline DoubleVector3 line_intersect_plane(const DoubleLine& line, const Plane3& plane) -{ - return line.origin + vector3_scaled( - line.direction, - -plane3_distance_to_point(plane, line.origin) - / vector3_dot(line.direction, plane.normal()) - ); +/* + ============ + Plane_FromPoints + ============ + */ +int Plane_FromPoints( vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane ){ + vec3_t v1, v2; + + VectorSubtract( p2, p1, v1 ); + VectorSubtract( p3, p1, v2 ); + //CrossProduct(v2, v1, plane->normal); + CrossProduct( v1, v2, plane->normal ); + if ( VectorNormalize( plane->normal, plane->normal ) < 0.1 ) { + return false; + } + plane->dist = DotProduct( p1, plane->normal ); + return true; } -inline bool float_is_largest_absolute(double axis, double other) -{ - return fabs(axis) > fabs(other); +/* + ================= + Point_Equal + ================= + */ +int Point_Equal( vec3_t p1, vec3_t p2, float epsilon ){ + int i; + + for ( i = 0; i < 3; i++ ) + { + if ( fabs( p1[i] - p2[i] ) > epsilon ) { + return false; + } + } + return true; } -/// \brief Returns the index of the component of \p v that has the largest absolute value. -inline int vector3_largest_absolute_component_index(const DoubleVector3& v) -{ - return (float_is_largest_absolute(v[1], v[0])) - ? (float_is_largest_absolute(v[1], v[2])) - ? 1 - : 2 - : (float_is_largest_absolute(v[0], v[2])) - ? 0 - : 2; -} -/// \brief Returns the infinite line that is the intersection of \p plane and \p other. -inline DoubleLine plane3_intersect_plane3(const Plane3& plane, const Plane3& other) -{ - DoubleLine line; - line.direction = vector3_cross(plane.normal(), other.normal()); - switch(vector3_largest_absolute_component_index(line.direction)) - { - case 0: - line.origin.x() = 0; - line.origin.y() = (-other.dist() * plane.normal().z() - -plane.dist() * other.normal().z()) / line.direction.x(); - line.origin.z() = (-plane.dist() * other.normal().y() - -other.dist() * plane.normal().y()) / line.direction.x(); - break; - case 1: - line.origin.x() = (-plane.dist() * other.normal().z() - -other.dist() * plane.normal().z()) / line.direction.y(); - line.origin.y() = 0; - line.origin.z() = (-other.dist() * plane.normal().x() - -plane.dist() * other.normal().x()) / line.direction.y(); - break; - case 2: - line.origin.x() = (-other.dist() * plane.normal().y() - -plane.dist() * other.normal().y()) / line.direction.z(); - line.origin.y() = (-plane.dist() * other.normal().x() - -other.dist() * plane.normal().x()) / line.direction.z(); - line.origin.z() = 0; - break; - default: - break; - } - - return line; +/* + ================= + Winding_BaseForPlane + ================= + */ +//#define DBG_WNDG +winding_t *Winding_BaseForPlane( plane_t *p ){ + int i, x; + vec_t max, v; + vec3_t org, vright, vup; + winding_t *w; + + // find the major axis +#ifdef DBG_WNDG + Sys_Printf( "Winding_BaseForPlane %p\n",p ); +#endif + + max = -BOGUS_RANGE; + x = -1; + for ( i = 0 ; i < 3; i++ ) + { + v = fabs( p->normal[i] ); + if ( v > max ) { + x = i; + max = v; + } + } + if ( x == -1 ) { + Error( "Winding_BaseForPlane: no axis found" ); + } + + VectorCopy( vec3_origin, vup ); + switch ( x ) + { + case 0: + case 1: + vup[2] = 1; + break; + case 2: + vup[0] = 1; + break; + } + + + v = DotProduct( vup, p->normal ); + VectorMA( vup, -v, p->normal, vup ); + VectorNormalize( vup, vup ); + + VectorScale( p->normal, p->dist, org ); + + CrossProduct( vup, p->normal, vright ); + + VectorScale( vup, BOGUS_RANGE, vup ); + VectorScale( vright, BOGUS_RANGE, vright ); + + // project a really big axis aligned box onto the plane + w = Winding_Alloc( 4 ); + + VectorSubtract( org, vright, w->points[0] ); + VectorAdd( w->points[0], vup, w->points[0] ); + + VectorAdd( org, vright, w->points[1] ); + VectorAdd( w->points[1], vup, w->points[1] ); + + VectorAdd( org, vright, w->points[2] ); + VectorSubtract( w->points[2], vup, w->points[2] ); + + VectorSubtract( org, vright, w->points[3] ); + VectorSubtract( w->points[3], vup, w->points[3] ); + + w->numpoints = 4; + + return w; } +// macro to compute winding size +#define WINDING_SIZE( pt ) ( sizeof( int )*2 + sizeof( float )*5*( pt ) ) -/// \brief Keep the value of \p infinity as small as possible to improve precision in Winding_Clip. -void Winding_createInfinite(FixedWinding& winding, const Plane3& plane, double infinity) -{ - double max = -infinity; - int x = -1; - for (int i=0 ; i<3; i++) - { - double d = fabs(plane.normal()[i]); - if (d > max) - { - x = i; - max = d; - } - } - if(x == -1) - { - globalErrorStream() << "invalid plane\n"; - return; - } - - DoubleVector3 vup = g_vector3_identity; - switch (x) - { - case 0: - case 1: - vup[2] = 1; - break; - case 2: - vup[0] = 1; - break; - } - - - vector3_add(vup, vector3_scaled(plane.normal(), -vector3_dot(vup, plane.normal()))); - vector3_normalise(vup); - - DoubleVector3 org = vector3_scaled(plane.normal(), plane.dist()); - - DoubleVector3 vright = vector3_cross(vup, plane.normal()); - - vector3_scale(vup, infinity); - vector3_scale(vright, infinity); - - // project a really big axis aligned box onto the plane - - DoubleLine r1, r2, r3, r4; - r1.origin = vector3_added(vector3_subtracted(org, vright), vup); - r1.direction = vector3_normalised(vright); - winding.push_back(FixedWindingVertex(r1.origin, r1, c_brush_maxFaces)); - r2.origin = vector3_added(vector3_added(org, vright), vup); - r2.direction = vector3_normalised(vector3_negated(vup)); - winding.push_back(FixedWindingVertex(r2.origin, r2, c_brush_maxFaces)); - r3.origin = vector3_subtracted(vector3_added(org, vright), vup); - r3.direction = vector3_normalised(vector3_negated(vright)); - winding.push_back(FixedWindingVertex(r3.origin, r3, c_brush_maxFaces)); - r4.origin = vector3_subtracted(vector3_subtracted(org, vright), vup); - r4.direction = vector3_normalised(vup); - winding.push_back(FixedWindingVertex(r4.origin, r4, c_brush_maxFaces)); +/* + ================== + Winding_Alloc + ================== + */ +winding_t *Winding_Alloc( int points ){ + winding_t *w; + int size; + + if ( points > MAX_POINTS_ON_WINDING ) { + Error( "Winding_Alloc: %i points", points ); + } + +// size = (int)((winding_t *)0)->points[points]; + size = WINDING_SIZE( points ); + w = (winding_t*) malloc( size ); + memset( w, 0, size ); + w->maxpoints = points; + + return w; } +void Winding_Free( winding_t *w ){ + free( w ); +} -inline PlaneClassification Winding_ClassifyDistance(const double distance, const double epsilon) -{ - if(distance > epsilon) - { - return ePlaneFront; - } - if(distance < -epsilon) - { - return ePlaneBack; - } - return ePlaneOn; +/* + ================== + Winding_Clone + ================== + */ +winding_t *Winding_Clone( winding_t *w ){ + int size; + winding_t *c; + +// size = (int)((winding_t *)0)->points[w->numpoints]; + size = WINDING_SIZE( w->numpoints ); + c = (winding_t*)qmalloc( size ); + memcpy( c, w, size ); + return c; } -/// \brief Returns true if -/// !flipped && winding is completely BACK or ON -/// or flipped && winding is completely FRONT or ON -bool Winding_TestPlane(const Winding& winding, const Plane3& plane, bool flipped) -{ - const int test = (flipped) ? ePlaneBack : ePlaneFront; - for(Winding::const_iterator i = winding.begin(); i != winding.end(); ++i) - { - if(test == Winding_ClassifyDistance(plane3_distance_to_point(plane, (*i).vertex), ON_EPSILON)) - { - return false; - } - } - return true; +/* + ================== + ReverseWinding + ================== + */ +winding_t *Winding_Reverse( winding_t *w ){ + int i; + winding_t *c; + + c = Winding_Alloc( w->numpoints ); + for ( i = 0; i < w->numpoints; i++ ) + { + VectorCopy( w->points[w->numpoints - 1 - i], c->points[i] ); + } + c->numpoints = w->numpoints; + return c; } -/// \brief Returns true if any point in \p w1 is in front of plane2, or any point in \p w2 is in front of plane1 -bool Winding_PlanesConcave(const Winding& w1, const Winding& w2, const Plane3& plane1, const Plane3& plane2) -{ - return !Winding_TestPlane(w1, plane2, false) || !Winding_TestPlane(w2, plane1, false); +/* + ============== + Winding_RemovePoint + ============== + */ +void Winding_RemovePoint( winding_t *w, int point ){ + if ( point < 0 || point >= w->numpoints ) { + Error( "Winding_RemovePoint: point out of range" ); + } + + if ( point < w->numpoints - 1 ) { + memmove( &w->points[point], &w->points[point + 1], (size_t)( (winding_t *)0 )->points[w->numpoints - point - 1] ); + } + w->numpoints--; } -brushsplit_t Winding_ClassifyPlane(const Winding& winding, const Plane3& plane) -{ - brushsplit_t split; - for(Winding::const_iterator i = winding.begin(); i != winding.end(); ++i) - { - ++split.counts[Winding_ClassifyDistance(plane3_distance_to_point(plane, (*i).vertex), ON_EPSILON)]; - } - return split; +/* + ============= + Winding_InsertPoint + ============= + */ +winding_t *Winding_InsertPoint( winding_t *w, vec3_t point, int spot ){ + int i, j; + winding_t *neww; + + if ( spot > w->numpoints ) { + Error( "Winding_InsertPoint: spot > w->numpoints" ); + } //end if + if ( spot < 0 ) { + Error( "Winding_InsertPoint: spot < 0" ); + } //end if + neww = Winding_Alloc( w->numpoints + 1 ); + neww->numpoints = w->numpoints + 1; + for ( i = 0, j = 0; i < neww->numpoints; i++ ) + { + if ( i == spot ) { + VectorCopy( point, neww->points[i] ); + } + else + { + VectorCopy( w->points[j], neww->points[i] ); + j++; + } + } + return neww; } +/* + ============== + Winding_IsTiny + ============== + */ +#define EDGE_LENGTH 0.2 + +int Winding_IsTiny( winding_t *w ){ + int i, j; + vec_t len; + vec3_t delta; + int edges; + + edges = 0; + for ( i = 0 ; i < w->numpoints ; i++ ) + { + j = i == w->numpoints - 1 ? 0 : i + 1; + VectorSubtract( w->points[j], w->points[i], delta ); + len = VectorLength( delta ); + if ( len > EDGE_LENGTH ) { + if ( ++edges == 3 ) { + return false; + } + } + } + return true; +} -#define DEBUG_EPSILON ON_EPSILON -const double DEBUG_EPSILON_SQUARED = DEBUG_EPSILON * DEBUG_EPSILON; - -#define WINDING_DEBUG 0 - -/// \brief Clip \p winding which lies on \p plane by \p clipPlane, resulting in \p clipped. -/// If \p winding is completely in front of the plane, \p clipped will be identical to \p winding. -/// If \p winding is completely in back of the plane, \p clipped will be empty. -/// If \p winding intersects the plane, the edge of \p clipped which lies on \p clipPlane will store the value of \p adjacent. -void Winding_Clip(const FixedWinding& winding, const Plane3& plane, const Plane3& clipPlane, std::size_t adjacent, FixedWinding& clipped) -{ - PlaneClassification classification = Winding_ClassifyDistance(plane3_distance_to_point(clipPlane, winding.back().vertex), ON_EPSILON); - PlaneClassification nextClassification; - // for each edge - for(std::size_t next = 0, i = winding.size()-1; next != winding.size(); i = next, ++next, classification = nextClassification) - { - nextClassification = Winding_ClassifyDistance(plane3_distance_to_point(clipPlane, winding[next].vertex), ON_EPSILON); - const FixedWindingVertex& vertex = winding[i]; - - // if first vertex of edge is ON - if(classification == ePlaneOn) - { - // append first vertex to output winding - if(nextClassification == ePlaneBack) - { - // this edge lies on the clip plane - clipped.push_back(FixedWindingVertex(vertex.vertex, plane3_intersect_plane3(plane, clipPlane), adjacent)); - } - else - { - clipped.push_back(vertex); - } - continue; - } - - // if first vertex of edge is FRONT - if(classification == ePlaneFront) - { - // add first vertex to output winding - clipped.push_back(vertex); - } - // if second vertex of edge is ON - if(nextClassification == ePlaneOn) - { - continue; - } - // else if second vertex of edge is same as first - else if(nextClassification == classification) - { - continue; - } - // else if first vertex of edge is FRONT and there are only two edges - else if(classification == ePlaneFront && winding.size() == 2) - { - continue; - } - // else first vertex is FRONT and second is BACK or vice versa - else - { - // append intersection point of line and plane to output winding - DoubleVector3 mid(line_intersect_plane(vertex.edge, clipPlane)); - - if(classification == ePlaneFront) - { - // this edge lies on the clip plane - clipped.push_back(FixedWindingVertex(mid, plane3_intersect_plane3(plane, clipPlane), adjacent)); - } - else - { - clipped.push_back(FixedWindingVertex(mid, vertex.edge, vertex.adjacent)); - } - } - } +/* + ============== + Winding_IsHuge + ============== + */ +int Winding_IsHuge( winding_t *w ){ + int i, j; + + for ( i = 0 ; i < w->numpoints ; i++ ) + { + for ( j = 0 ; j < 3 ; j++ ) + if ( w->points[i][j] < -BOGUS_RANGE + 1 || w->points[i][j] > BOGUS_RANGE - 1 ) { + return true; + } + } + return false; } -std::size_t Winding_FindAdjacent(const Winding& winding, std::size_t face) -{ - for(std::size_t i=0; inumpoints; i++ ) + { + if ( DotProduct( normal2, w1->points[i] ) - dist2 > WCONVEX_EPSILON ) { + return true; + } + } + // check if one of the points of winding 2 is at the back of the plane of winding 1 + for ( i = 0; i < w2->numpoints; i++ ) + { + if ( DotProduct( normal1, w2->points[i] ) - dist1 > WCONVEX_EPSILON ) { + return true; + } + } + + return false; } -std::size_t Winding_Opposite(const Winding& winding, const std::size_t index, const std::size_t other) -{ - ASSERT_MESSAGE(index < winding.numpoints && other < winding.numpoints, "Winding_Opposite: index out of range"); +/* + ================== + Winding_Clip + + Clips the winding to the plane, returning the new winding on the positive side + Frees the input winding. + If keepon is true, an exactly on-plane winding will be saved, otherwise + it will be clipped away. + ================== + */ +winding_t *Winding_Clip( winding_t *in, plane_t *split, qboolean keepon ){ + vec_t dists[MAX_POINTS_ON_WINDING]; + int sides[MAX_POINTS_ON_WINDING]; + int counts[3]; + vec_t dot; + int i, j; + vec_t *p1, *p2; + vec3_t mid; + winding_t *neww; + int maxpts; + + counts[0] = counts[1] = counts[2] = 0; + + // determine sides for each point + for ( i = 0 ; i < in->numpoints ; i++ ) + { + dot = DotProduct( in->points[i], split->normal ); + dot -= split->dist; + dists[i] = dot; + if ( dot > ON_EPSILON ) { + sides[i] = SIDE_FRONT; + } + else if ( dot < -ON_EPSILON ) { + sides[i] = SIDE_BACK; + } + else + { + sides[i] = SIDE_ON; + } + counts[sides[i]]++; + } + sides[i] = sides[0]; + dists[i] = dists[0]; + + if ( keepon && !counts[0] && !counts[1] ) { + return in; + } + + if ( !counts[0] ) { + Winding_Free( in ); + return NULL; + } + if ( !counts[1] ) { + return in; + } + + maxpts = in->numpoints + 4; // can't use counts[0]+2 because + // of fp grouping errors + neww = Winding_Alloc( maxpts ); + + for ( i = 0 ; i < in->numpoints ; i++ ) + { + p1 = in->points[i]; + + if ( sides[i] == SIDE_ON ) { + VectorCopy( p1, neww->points[neww->numpoints] ); + neww->numpoints++; + continue; + } + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, neww->points[neww->numpoints] ); + neww->numpoints++; + } + + if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) { + continue; + } + + // generate a split point + p2 = in->points[( i + 1 ) % in->numpoints]; + + dot = dists[i] / ( dists[i] - dists[i + 1] ); + for ( j = 0 ; j < 3 ; j++ ) + { // avoid round off error when possible + if ( split->normal[j] == 1 ) { + mid[j] = split->dist; + } + else if ( split->normal[j] == -1 ) { + mid[j] = -split->dist; + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } + } + + VectorCopy( mid, neww->points[neww->numpoints] ); + neww->numpoints++; + } + + if ( neww->numpoints > maxpts ) { + Error( "Winding_Clip: points exceeded estimate" ); + } + + // free the original winding + Winding_Free( in ); + + return neww; +} - double dist_best = 0; - std::size_t index_best = c_brush_maxFaces; +/* + ============= + Winding_SplitEpsilon + + split the input winding with the plane + the input winding stays untouched + ============= + */ +void Winding_SplitEpsilon( winding_t *in, vec3_t normal, double dist, + vec_t epsilon, winding_t **front, winding_t **back ){ + vec_t dists[MAX_POINTS_ON_WINDING + 4]; + int sides[MAX_POINTS_ON_WINDING + 4]; + int counts[3]; + vec_t dot; + int i, j; + vec_t *p1, *p2; + vec3_t mid; + winding_t *f, *b; + int maxpts; + + counts[0] = counts[1] = counts[2] = 0; + + // determine sides for each point + for ( i = 0; i < in->numpoints; i++ ) + { + dot = DotProduct( in->points[i], normal ); + dot -= dist; + 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 = Winding_Clone( in ); + return; + } + if ( !counts[1] ) { + *front = Winding_Clone( in ); + return; + } + + maxpts = in->numpoints + 4; // cant use counts[0]+2 because + // of fp grouping errors + + *front = f = Winding_Alloc( maxpts ); + *back = b = Winding_Alloc( maxpts ); + + for ( i = 0; i < in->numpoints; i++ ) + { + p1 = in->points[i]; + + if ( sides[i] == SIDE_ON ) { + VectorCopy( p1, f->points[f->numpoints] ); + f->numpoints++; + VectorCopy( p1, b->points[b->numpoints] ); + b->numpoints++; + continue; + } + + if ( sides[i] == SIDE_FRONT ) { + VectorCopy( p1, f->points[f->numpoints] ); + f->numpoints++; + } + if ( sides[i] == SIDE_BACK ) { + VectorCopy( p1, b->points[b->numpoints] ); + b->numpoints++; + } + + if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) { + continue; + } + + // generate a split point + p2 = in->points[( i + 1 ) % in->numpoints]; + + dot = dists[i] / ( dists[i] - dists[i + 1] ); + for ( j = 0; j < 3; j++ ) + { + // avoid round off error when possible + if ( normal[j] == 1 ) { + mid[j] = dist; + } + else if ( normal[j] == -1 ) { + mid[j] = -dist; + } + else{ + mid[j] = p1[j] + dot * ( p2[j] - p1[j] ); + } + } + + VectorCopy( mid, f->points[f->numpoints] ); + f->numpoints++; + VectorCopy( mid, b->points[b->numpoints] ); + b->numpoints++; + } + + if ( f->numpoints > maxpts || b->numpoints > maxpts ) { + Error( "Winding_Clip: points exceeded estimate" ); + } + if ( f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING ) { + Error( "Winding_Clip: MAX_POINTS_ON_WINDING" ); + } +} - Ray edge(ray_for_points(winding[index].vertex, winding[other].vertex)); +/* + ============= + Winding_TryMerge + + If two windings share a common edge and the edges that meet at the + common points are both inside the other polygons, merge them + + Returns NULL if the windings couldn't be merged, or the new winding. + The originals will NOT be freed. + + if keep is true no points are ever removed + ============= + */ +#define CONTINUOUS_EPSILON 0.005 + +winding_t *Winding_TryMerge( winding_t *f1, winding_t *f2, vec3_t planenormal, int keep ){ + vec_t *p1, *p2, *p3, *p4, *back; + winding_t *newf; + int i, j, k, l; + vec3_t normal, delta; + vec_t dot; + qboolean keep1, keep2; + + + // + // find a common edge + // + p1 = p2 = NULL; // stop compiler warning + j = 0; // + + for ( i = 0; i < f1->numpoints; i++ ) + { + p1 = f1->points[i]; + p2 = f1->points[( i + 1 ) % f1->numpoints]; + for ( j = 0; j < f2->numpoints; j++ ) + { + p3 = f2->points[j]; + p4 = f2->points[( j + 1 ) % f2->numpoints]; + for ( k = 0; k < 3; k++ ) + { + if ( fabs( p1[k] - p4[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME + break; + } + if ( fabs( p2[k] - p3[k] ) > 0.1 ) { //EQUAL_EPSILON) //ME + break; + } + } //end for + if ( k == 3 ) { + break; + } + } //end for + if ( j < f2->numpoints ) { + break; + } + } //end for + + if ( i == f1->numpoints ) { + return NULL; // no matching edges + + } + // + // check slope of connected lines + // if the slopes are colinear, the point can be removed + // + back = f1->points[( i + f1->numpoints - 1 ) % f1->numpoints]; + VectorSubtract( p1, back, delta ); + CrossProduct( planenormal, delta, normal ); + VectorNormalize( normal, normal ); + + back = f2->points[( j + 2 ) % f2->numpoints]; + VectorSubtract( back, p1, delta ); + dot = DotProduct( delta, normal ); + if ( dot > CONTINUOUS_EPSILON ) { + return NULL; // not a convex polygon + } + keep1 = (qboolean)( dot < -CONTINUOUS_EPSILON ); + + back = f1->points[( i + 2 ) % f1->numpoints]; + VectorSubtract( back, p2, delta ); + CrossProduct( planenormal, delta, normal ); + VectorNormalize( normal, normal ); + + back = f2->points[( j + f2->numpoints - 1 ) % f2->numpoints]; + VectorSubtract( back, p2, delta ); + dot = DotProduct( delta, normal ); + if ( dot > CONTINUOUS_EPSILON ) { + return NULL; // not a convex polygon + } + keep2 = (qboolean)( dot < -CONTINUOUS_EPSILON ); + + // + // build the new polygon + // + newf = Winding_Alloc( f1->numpoints + f2->numpoints ); + + // copy first polygon + for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints ) + { + if ( !keep && k == ( i + 1 ) % f1->numpoints && !keep2 ) { + continue; + } + + VectorCopy( f1->points[k], newf->points[newf->numpoints] ); + newf->numpoints++; + } + + // copy second polygon + for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints ) + { + if ( !keep && l == ( j + 1 ) % f2->numpoints && !keep1 ) { + continue; + } + VectorCopy( f2->points[l], newf->points[newf->numpoints] ); + newf->numpoints++; + } + + return newf; +} - for(std::size_t i=0; inumpoints; i++ ) + { + VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], v1 ); + VectorSubtract( w->points[( i + 2 ) % w->numpoints], w->points[i], v2 ); + if ( VectorLength( v1 ) > 0.5 && VectorLength( v2 ) > 0.5 ) { + break; + } + } + CrossProduct( v2, v1, normal ); + VectorNormalize( normal, normal ); + *dist = DotProduct( w->points[0], normal ); +} - double dist_squared = ray_squared_distance_to_point(edge, winding[i].vertex); +/* + ============= + Winding_Area + ============= + */ +float Winding_Area( winding_t *w ){ + int i; + vec3_t d1, d2, cross; + float total; + + total = 0; + for ( i = 2 ; i < w->numpoints ; i++ ) + { + VectorSubtract( w->points[i - 1], w->points[0], d1 ); + VectorSubtract( w->points[i], w->points[0], d2 ); + CrossProduct( d1, d2, cross ); + total += 0.5 * VectorLength( cross ); + } + return total; +} - if(dist_squared > dist_best) - { - dist_best = dist_squared; - index_best = i; - } - } - return index_best; +/* + ============= + Winding_Bounds + ============= + */ +void Winding_Bounds( winding_t *w, vec3_t mins, vec3_t maxs ){ + vec_t v; + int i,j; + + mins[0] = mins[1] = mins[2] = 99999; + maxs[0] = maxs[1] = maxs[2] = -99999; + + for ( i = 0 ; i < w->numpoints ; i++ ) + { + for ( j = 0 ; j < 3 ; j++ ) + { + v = w->points[i][j]; + if ( v < mins[j] ) { + mins[j] = v; + } + if ( v > maxs[j] ) { + maxs[j] = v; + } + } + } } -std::size_t Winding_Opposite(const Winding& winding, const std::size_t index) -{ - return Winding_Opposite(winding, index, Winding_next(winding, index)); + +/* + ================= + Winding_PointInside + ================= + */ +int Winding_PointInside( winding_t *w, plane_t *plane, vec3_t point, float epsilon ){ + int i; + vec3_t dir, normal, pointvec; + + for ( i = 0; i < w->numpoints; i++ ) + { + VectorSubtract( w->points[( i + 1 ) % w->numpoints], w->points[i], dir ); + VectorSubtract( point, w->points[i], pointvec ); + // + CrossProduct( dir, plane->normal, normal ); + // + if ( DotProduct( pointvec, normal ) < -epsilon ) { + return false; + } + } + return true; } -/// \brief Calculate the \p centroid of the polygon defined by \p winding which lies on plane \p plane. -void Winding_Centroid(const Winding& winding, const Plane3& plane, Vector3& centroid) -{ - double area2 = 0, x_sum = 0, y_sum = 0; - const ProjectionAxis axis = projectionaxis_for_normal(plane.normal()); - const indexremap_t remap = indexremap_for_projectionaxis(axis); - for(std::size_t i = winding.numpoints-1, j = 0; j < winding.numpoints; i = j, ++j) - { - const double ai = winding[i].vertex[remap.x] * winding[j].vertex[remap.y] - winding[j].vertex[remap.x] * winding[i].vertex[remap.y]; - area2 += ai; - x_sum += (winding[j].vertex[remap.x] + winding[i].vertex[remap.x]) * ai; - y_sum += (winding[j].vertex[remap.y] + winding[i].vertex[remap.y]) * ai; - } - - centroid[remap.x] = static_cast(x_sum / (3 * area2)); - centroid[remap.y] = static_cast(y_sum / (3 * area2)); - { - Ray ray(Vector3(0, 0, 0), Vector3(0, 0, 0)); - ray.origin[remap.x] = centroid[remap.x]; - ray.origin[remap.y] = centroid[remap.y]; - ray.direction[remap.z] = 1; - centroid[remap.z] = static_cast(ray_distance_to_plane(ray, plane)); - } +/* + ================= + Winding_VectorIntersect + ================= + */ +int Winding_VectorIntersect( winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon ){ + float front, back, frac; + vec3_t mid; + + front = DotProduct( p1, plane->normal ) - plane->dist; + back = DotProduct( p2, plane->normal ) - plane->dist; + //if both points at the same side of the plane + if ( front < -epsilon && back < -epsilon ) { + return false; + } + if ( front > epsilon && back > epsilon ) { + return false; + } + //get point of intersection with winding plane + if ( fabs( front - back ) < 0.001 ) { + VectorCopy( p2, mid ); + } + else + { + frac = front / ( front - back ); + mid[0] = p1[0] + ( p2[0] - p1[0] ) * frac; + mid[1] = p1[1] + ( p2[1] - p1[1] ) * frac; + mid[2] = p1[2] + ( p2[2] - p1[2] ) * frac; + } + return Winding_PointInside( w, plane, mid, epsilon ); }