neo/idlib/geometry/Winding.h

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 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 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 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 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 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 __WINDING_H__
  30 #define __WINDING_H__
  31
  32 /*
  33 ===============================================================================
  34
  35         A winding is an arbitrary convex polygon defined by an array of points.
  36
  37 ===============================================================================
  38 */
  39
  40 class idWinding {
  41
  42 public:
  43                                         idWinding( void );
  44                                         explicit idWinding( const int n );                                                              // allocate for n points
  45                                         explicit idWinding( const idVec3 *verts, const int n );                 // winding from points
  46                                         explicit idWinding( const idVec3 &normal, const float dist );   // base winding for plane
  47                                         explicit idWinding( const idPlane &plane );                                             // base winding for plane
  48                                         explicit idWinding( const idWinding &winding );
  49         virtual                 ~idWinding( void );
  50
  51         idWinding &             operator=( const idWinding &winding );
  52         const idVec5 &  operator[]( const int index ) const;
  53         idVec5 &                operator[]( const int index );
  54
  55                                         // add a point to the end of the winding point array
  56         idWinding &             operator+=( const idVec3 &v );
  57         idWinding &             operator+=( const idVec5 &v );
  58         void                    AddPoint( const idVec3 &v );
  59         void                    AddPoint( const idVec5 &v );
  60
  61                                         // number of points on winding
  62         int                             GetNumPoints( void ) const;
  63         void                    SetNumPoints( int n );
  64         virtual void    Clear( void );
  65
  66                                         // huge winding for plane, the points go counter clockwise when facing the front of the plane
  67         void                    BaseForPlane( const idVec3 &normal, const float dist );
  68         void                    BaseForPlane( const idPlane &plane );
  69
  70                                         // splits the winding into a front and back winding, the winding itself stays unchanged
  71                                         // returns a SIDE_?
  72         int                             Split( const idPlane &plane, const float epsilon, idWinding **front, idWinding **back ) const;
  73                                         // returns the winding fragment at the front of the clipping plane,
  74                                         // if there is nothing at the front the winding itself is destroyed and NULL is returned
  75         idWinding *             Clip( const idPlane &plane, const float epsilon = ON_EPSILON, const bool keepOn = false );
  76                                         // cuts off the part at the back side of the plane, returns true if some part was at the front
  77                                         // if there is nothing at the front the number of points is set to zero
  78         bool                    ClipInPlace( const idPlane &plane, const float epsilon = ON_EPSILON, const bool keepOn = false );
  79
  80                                         // returns a copy of the winding
  81         idWinding *             Copy( void ) const;
  82         idWinding *             Reverse( void ) const;
  83         void                    ReverseSelf( void );
  84         void                    RemoveEqualPoints( const float epsilon = ON_EPSILON );
  85         void                    RemoveColinearPoints( const idVec3 &normal, const float epsilon = ON_EPSILON );
  86         void                    RemovePoint( int point );
  87         void                    InsertPoint( const idVec3 &point, int spot );
  88         bool                    InsertPointIfOnEdge( const idVec3 &point, const idPlane &plane, const float epsilon = ON_EPSILON );
  89                                         // add a winding to the convex hull
  90         void                    AddToConvexHull( const idWinding *winding, const idVec3 &normal, const float epsilon = ON_EPSILON );
  91                                         // add a point to the convex hull
  92         void                    AddToConvexHull( const idVec3 &point, const idVec3 &normal, const float epsilon = ON_EPSILON );
  93                                         // tries to merge 'this' with the given winding, returns NULL if merge fails, both 'this' and 'w' stay intact
  94                                         // 'keep' tells if the contacting points should stay even if they create colinear edges
  95         idWinding *             TryMerge( const idWinding &w, const idVec3 &normal, int keep = false ) const;
  96                                         // check whether the winding is valid or not
  97         bool                    Check( bool print = true ) const;
  98
  99         float                   GetArea( void ) const;
 100         idVec3                  GetCenter( void ) const;
 101         float                   GetRadius( const idVec3 &center ) const;
 102         void                    GetPlane( idVec3 &normal, float &dist ) const;
 103         void                    GetPlane( idPlane &plane ) const;
 104         void                    GetBounds( idBounds &bounds ) const;
 105
 106         bool                    IsTiny( void ) const;
 107         bool                    IsHuge( void ) const;   // base winding for a plane is typically huge
 108         void                    Print( void ) const;
 109
 110         float                   PlaneDistance( const idPlane &plane ) const;
 111         int                             PlaneSide( const idPlane &plane, const float epsilon = ON_EPSILON ) const;
 112
 113         bool                    PlanesConcave( const idWinding &w2, const idVec3 &normal1, const idVec3 &normal2, float dist1, float dist2 ) const;
 114
 115         bool                    PointInside( const idVec3 &normal, const idVec3 &point, const float epsilon ) const;
 116                                         // returns true if the line or ray intersects the winding
 117         bool                    LineIntersection( const idPlane &windingPlane, const idVec3 &start, const idVec3 &end, bool backFaceCull = false ) const;
 118                                         // intersection point is start + dir * scale
 119         bool                    RayIntersection( const idPlane &windingPlane, const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull = false ) const;
 120
 121         static float    TriangleArea( const idVec3 &a, const idVec3 &b, const idVec3 &c );
 122
 123 protected:
 124         int                             numPoints;                              // number of points
 125         idVec5 *                p;                                              // pointer to point data
 126         int                             allocedSize;
 127
 128         bool                    EnsureAlloced( int n, bool keep = false );
 129         virtual bool    ReAllocate( int n, bool keep = false );
 130 };
 131
 132 ID_INLINE idWinding::idWinding( void ) {
 133         numPoints = allocedSize = 0;
 134         p = NULL;
 135 }
 136
 137 ID_INLINE idWinding::idWinding( int n ) {
 138         numPoints = allocedSize = 0;
 139         p = NULL;
 140         EnsureAlloced( n );
 141 }
 142
 143 ID_INLINE idWinding::idWinding( const idVec3 *verts, const int n ) {
 144         int i;
 145
 146         numPoints = allocedSize = 0;
 147         p = NULL;
 148         if ( !EnsureAlloced( n ) ) {
 149                 numPoints = 0;
 150                 return;
 151         }
 152         for ( i = 0; i < n; i++ ) {
 153                 p[i].ToVec3() = verts[i];
 154                 p[i].s = p[i].t = 0.0f;
 155         }
 156         numPoints = n;
 157 }
 158
 159 ID_INLINE idWinding::idWinding( const idVec3 &normal, const float dist ) {
 160         numPoints = allocedSize = 0;
 161         p = NULL;
 162         BaseForPlane( normal, dist );
 163 }
 164
 165 ID_INLINE idWinding::idWinding( const idPlane &plane ) {
 166         numPoints = allocedSize = 0;
 167         p = NULL;
 168         BaseForPlane( plane );
 169 }
 170
 171 ID_INLINE idWinding::idWinding( const idWinding &winding ) {
 172         int i;
 173         if ( !EnsureAlloced( winding.GetNumPoints() ) ) {
 174                 numPoints = 0;
 175                 return;
 176         }
 177         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
 178                 p[i] = winding[i];
 179         }
 180         numPoints = winding.GetNumPoints();
 181 }
 182
 183 ID_INLINE idWinding::~idWinding( void ) {
 184         delete[] p;
 185         p = NULL;
 186 }
 187
 188 ID_INLINE idWinding &idWinding::operator=( const idWinding &winding ) {
 189         int i;
 190
 191         if ( !EnsureAlloced( winding.numPoints ) ) {
 192                 numPoints = 0;
 193                 return *this;
 194         }
 195         for ( i = 0; i < winding.numPoints; i++ ) {
 196                 p[i] = winding.p[i];
 197         }
 198         numPoints = winding.numPoints;
 199         return *this;
 200 }
 201
 202 ID_INLINE const idVec5 &idWinding::operator[]( const int index ) const {
 203         //assert( index >= 0 && index < numPoints );
 204         return p[ index ];
 205 }
 206
 207 ID_INLINE idVec5 &idWinding::operator[]( const int index ) {
 208         //assert( index >= 0 && index < numPoints );
 209         return p[ index ];
 210 }
 211
 212 ID_INLINE idWinding &idWinding::operator+=( const idVec3 &v ) {
 213         AddPoint( v );
 214         return *this;
 215 }
 216
 217 ID_INLINE idWinding &idWinding::operator+=( const idVec5 &v ) {
 218         AddPoint( v );
 219         return *this;
 220 }
 221
 222 ID_INLINE void idWinding::AddPoint( const idVec3 &v ) {
 223         if ( !EnsureAlloced(numPoints+1, true) ) {
 224                 return;
 225         }
 226         p[numPoints] = v;
 227         numPoints++;
 228 }
 229
 230 ID_INLINE void idWinding::AddPoint( const idVec5 &v ) {
 231         if ( !EnsureAlloced(numPoints+1, true) ) {
 232                 return;
 233         }
 234         p[numPoints] = v;
 235         numPoints++;
 236 }
 237
 238 ID_INLINE int idWinding::GetNumPoints( void ) const {
 239         return numPoints;
 240 }
 241
 242 ID_INLINE void idWinding::SetNumPoints( int n ) {
 243         if ( !EnsureAlloced( n, true ) ) {
 244                 return;
 245         }
 246         numPoints = n;
 247 }
 248
 249 ID_INLINE void idWinding::Clear( void ) {
 250         numPoints = 0;
 251         delete[] p;
 252         p = NULL;
 253 }
 254
 255 ID_INLINE void idWinding::BaseForPlane( const idPlane &plane ) {
 256         BaseForPlane( plane.Normal(), plane.Dist() );
 257 }
 258
 259 ID_INLINE bool idWinding::EnsureAlloced( int n, bool keep ) {
 260         if ( n > allocedSize ) {
 261                 return ReAllocate( n, keep );
 262         }
 263         return true;
 264 }
 265
 266
 267 /*
 268 ===============================================================================
 269
 270         idFixedWinding is a fixed buffer size winding not using
 271         memory allocations.
 272
 273         When an operation would overflow the fixed buffer a warning
 274         is printed and the operation is safely cancelled.
 275
 276 ===============================================================================
 277 */
 278
 279 #define MAX_POINTS_ON_WINDING   64
 280
 281 class idFixedWinding : public idWinding {
 282
 283 public:
 284                                         idFixedWinding( void );
 285                                         explicit idFixedWinding( const int n );
 286                                         explicit idFixedWinding( const idVec3 *verts, const int n );
 287                                         explicit idFixedWinding( const idVec3 &normal, const float dist );
 288                                         explicit idFixedWinding( const idPlane &plane );
 289                                         explicit idFixedWinding( const idWinding &winding );
 290                                         explicit idFixedWinding( const idFixedWinding &winding );
 291         virtual                 ~idFixedWinding( void );
 292
 293         idFixedWinding &operator=( const idWinding &winding );
 294
 295         virtual void    Clear( void );
 296
 297                                         // splits the winding in a back and front part, 'this' becomes the front part
 298                                         // returns a SIDE_?
 299         int                             Split( idFixedWinding *back, const idPlane &plane, const float epsilon = ON_EPSILON );
 300
 301 protected:
 302         idVec5                  data[MAX_POINTS_ON_WINDING];    // point data
 303
 304         virtual bool    ReAllocate( int n, bool keep = false );
 305 };
 306
 307 ID_INLINE idFixedWinding::idFixedWinding( void ) {
 308         numPoints = 0;
 309         p = data;
 310         allocedSize = MAX_POINTS_ON_WINDING;
 311 }
 312
 313 ID_INLINE idFixedWinding::idFixedWinding( int n ) {
 314         numPoints = 0;
 315         p = data;
 316         allocedSize = MAX_POINTS_ON_WINDING;
 317 }
 318
 319 ID_INLINE idFixedWinding::idFixedWinding( const idVec3 *verts, const int n ) {
 320         int i;
 321
 322         numPoints = 0;
 323         p = data;
 324         allocedSize = MAX_POINTS_ON_WINDING;
 325         if ( !EnsureAlloced( n ) ) {
 326                 numPoints = 0;
 327                 return;
 328         }
 329         for ( i = 0; i < n; i++ ) {
 330                 p[i].ToVec3() = verts[i];
 331                 p[i].s = p[i].t = 0;
 332         }
 333         numPoints = n;
 334 }
 335
 336 ID_INLINE idFixedWinding::idFixedWinding( const idVec3 &normal, const float dist ) {
 337         numPoints = 0;
 338         p = data;
 339         allocedSize = MAX_POINTS_ON_WINDING;
 340         BaseForPlane( normal, dist );
 341 }
 342
 343 ID_INLINE idFixedWinding::idFixedWinding( const idPlane &plane ) {
 344         numPoints = 0;
 345         p = data;
 346         allocedSize = MAX_POINTS_ON_WINDING;
 347         BaseForPlane( plane );
 348 }
 349
 350 ID_INLINE idFixedWinding::idFixedWinding( const idWinding &winding ) {
 351         int i;
 352
 353         p = data;
 354         allocedSize = MAX_POINTS_ON_WINDING;
 355         if ( !EnsureAlloced( winding.GetNumPoints() ) ) {
 356                 numPoints = 0;
 357                 return;
 358         }
 359         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
 360                 p[i] = winding[i];
 361         }
 362         numPoints = winding.GetNumPoints();
 363 }
 364
 365 ID_INLINE idFixedWinding::idFixedWinding( const idFixedWinding &winding ) {
 366         int i;
 367
 368         p = data;
 369         allocedSize = MAX_POINTS_ON_WINDING;
 370         if ( !EnsureAlloced( winding.GetNumPoints() ) ) {
 371                 numPoints = 0;
 372                 return;
 373         }
 374         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
 375                 p[i] = winding[i];
 376         }
 377         numPoints = winding.GetNumPoints();
 378 }
 379
 380 ID_INLINE idFixedWinding::~idFixedWinding( void ) {
 381         p = NULL;       // otherwise it tries to free the fixed buffer
 382 }
 383
 384 ID_INLINE idFixedWinding &idFixedWinding::operator=( const idWinding &winding ) {
 385         int i;
 386
 387         if ( !EnsureAlloced( winding.GetNumPoints() ) ) {
 388                 numPoints = 0;
 389                 return *this;
 390         }
 391         for ( i = 0; i < winding.GetNumPoints(); i++ ) {
 392                 p[i] = winding[i];
 393         }
 394         numPoints = winding.GetNumPoints();
 395         return *this;
 396 }
 397
 398 ID_INLINE void idFixedWinding::Clear( void ) {
 399         numPoints = 0;
 400 }
 401 #endif  /* !__WINDING_H__ */