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