DOOM-3-BFG

DOOM 3 BFG Edition
Log | Files | Refs

Winding.h (12339B)

      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 __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();
     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();
     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() const;
     63 	void			SetNumPoints( int n );
     64 	virtual void	Clear();
     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() const;
     82 	idWinding *		Reverse() const;
     83 	void			ReverseSelf();
     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 idVec5 &point, int spot );
     88 	bool			InsertPointIfOnEdge( const idVec5 &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() const;
    100 	idVec3			GetCenter() 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() const;
    107 	bool			IsHuge() const;	// base winding for a plane is typically huge
    108 	void			Print() 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() {
    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() {
    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() 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() {
    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();
    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();
    292 
    293 	idFixedWinding &operator=( const idWinding &winding );
    294 
    295 	virtual void	Clear();
    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() {
    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() {
    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() {
    399 	numPoints = 0;
    400 }
    401 #endif	/* !__WINDING_H__ */