Winding2D.h (5847B)
1 /* 2 =========================================================================== 3 4 Doom 3 BFG Edition GPL Source Code 5 Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 6 7 This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code"). 8 9 Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>. 21 22 In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code. If not, please request a copy in writing from id Software at the address below. 23 24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA. 25 26 =========================================================================== 27 */ 28 29 #ifndef __WINDING2D_H__ 30 #define __WINDING2D_H__ 31 32 /* 33 =============================================================================== 34 35 A 2D winding is an arbitrary convex 2D polygon defined by an array of points. 36 37 =============================================================================== 38 */ 39 40 #define MAX_POINTS_ON_WINDING_2D 16 41 42 43 class idWinding2D { 44 public: 45 idWinding2D(); 46 47 idWinding2D & operator=( const idWinding2D &winding ); 48 const idVec2 & operator[]( const int index ) const; 49 idVec2 & operator[]( const int index ); 50 51 void Clear(); 52 void AddPoint( const idVec2 &point ); 53 int GetNumPoints() const; 54 55 void Expand( const float d ); 56 void ExpandForAxialBox( const idVec2 bounds[2] ); 57 58 // splits the winding into a front and back winding, the winding itself stays unchanged 59 // returns a SIDE_? 60 int Split( const idVec3 &plane, const float epsilon, idWinding2D **front, idWinding2D **back ) const; 61 // cuts off the part at the back side of the plane, returns true if some part was at the front 62 // if there is nothing at the front the number of points is set to zero 63 bool ClipInPlace( const idVec3 &plane, const float epsilon = ON_EPSILON, const bool keepOn = false ); 64 65 idWinding2D * Copy() const; 66 idWinding2D * Reverse() const; 67 68 float GetArea() const; 69 idVec2 GetCenter() const; 70 float GetRadius( const idVec2 ¢er ) const; 71 void GetBounds( idVec2 bounds[2] ) const; 72 73 bool IsTiny() const; 74 bool IsHuge() const; // base winding for a plane is typically huge 75 void Print() const; 76 77 float PlaneDistance( const idVec3 &plane ) const; 78 int PlaneSide( const idVec3 &plane, const float epsilon = ON_EPSILON ) const; 79 80 bool PointInside( const idVec2 &point, const float epsilon ) const; 81 bool LineIntersection( const idVec2 &start, const idVec2 &end ) const; 82 bool RayIntersection( const idVec2 &start, const idVec2 &dir, float &scale1, float &scale2, int *edgeNums = NULL ) const; 83 84 static idVec3 Plane2DFromPoints( const idVec2 &start, const idVec2 &end, const bool normalize = false ); 85 static idVec3 Plane2DFromVecs( const idVec2 &start, const idVec2 &dir, const bool normalize = false ); 86 static bool Plane2DIntersection( const idVec3 &plane1, const idVec3 &plane2, idVec2 &point ); 87 88 private: 89 int numPoints; 90 idVec2 p[MAX_POINTS_ON_WINDING_2D]; 91 }; 92 93 ID_INLINE idWinding2D::idWinding2D() { 94 numPoints = 0; 95 } 96 97 ID_INLINE idWinding2D &idWinding2D::operator=( const idWinding2D &winding ) { 98 int i; 99 100 for ( i = 0; i < winding.numPoints; i++ ) { 101 p[i] = winding.p[i]; 102 } 103 numPoints = winding.numPoints; 104 return *this; 105 } 106 107 ID_INLINE const idVec2 &idWinding2D::operator[]( const int index ) const { 108 return p[ index ]; 109 } 110 111 ID_INLINE idVec2 &idWinding2D::operator[]( const int index ) { 112 return p[ index ]; 113 } 114 115 ID_INLINE void idWinding2D::Clear() { 116 numPoints = 0; 117 } 118 119 ID_INLINE void idWinding2D::AddPoint( const idVec2 &point ) { 120 p[numPoints++] = point; 121 } 122 123 ID_INLINE int idWinding2D::GetNumPoints() const { 124 return numPoints; 125 } 126 127 ID_INLINE idVec3 idWinding2D::Plane2DFromPoints( const idVec2 &start, const idVec2 &end, const bool normalize ) { 128 idVec3 plane; 129 plane.x = start.y - end.y; 130 plane.y = end.x - start.x; 131 if ( normalize ) { 132 plane.ToVec2().Normalize(); 133 } 134 plane.z = - ( start.x * plane.x + start.y * plane.y ); 135 return plane; 136 } 137 138 ID_INLINE idVec3 idWinding2D::Plane2DFromVecs( const idVec2 &start, const idVec2 &dir, const bool normalize ) { 139 idVec3 plane; 140 plane.x = -dir.y; 141 plane.y = dir.x; 142 if ( normalize ) { 143 plane.ToVec2().Normalize(); 144 } 145 plane.z = - ( start.x * plane.x + start.y * plane.y ); 146 return plane; 147 } 148 149 ID_INLINE bool idWinding2D::Plane2DIntersection( const idVec3 &plane1, const idVec3 &plane2, idVec2 &point ) { 150 float n00, n01, n11, det, invDet, f0, f1; 151 152 n00 = plane1.x * plane1.x + plane1.y * plane1.y; 153 n01 = plane1.x * plane2.x + plane1.y * plane2.y; 154 n11 = plane2.x * plane2.x + plane2.y * plane2.y; 155 det = n00 * n11 - n01 * n01; 156 157 if ( idMath::Fabs(det) < 1e-6f ) { 158 return false; 159 } 160 161 invDet = 1.0f / det; 162 f0 = ( n01 * plane2.z - n11 * plane1.z ) * invDet; 163 f1 = ( n01 * plane1.z - n00 * plane2.z ) * invDet; 164 point.x = f0 * plane1.x + f1 * plane2.x; 165 point.y = f0 * plane1.y + f1 * plane2.y; 166 return true; 167 } 168 169 #endif /* !__WINDING2D_H__ */