mPlaneSet.h

Public Typedefs

PlaneSet< PlaneD >

PlaneSetD 

PlaneSet< PlaneF >

PlaneSetF 

Public Typedefs

typedef PlaneSet< PlaneD > PlaneSetD 

typedef PlaneSet< PlaneF > PlaneSetF 

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _MPLANESET_H_
 25#define _MPLANESET_H_
 26
 27#ifndef _MPLANE_H_
 28#include "math/mPlane.h"
 29#endif
 30
 31#ifndef _MBOX_H_
 32#include "math/mBox.h"
 33#endif
 34
 35#ifndef _MSPHERE_H_
 36#include "math/mSphere.h"
 37#endif
 38
 39#ifndef _MORIENTEDBOX_H_
 40#include "math/mOrientedBox.h"
 41#endif
 42
 43#ifndef _TEMPALLOC_H_
 44#include "util/tempAlloc.h"
 45#endif
 46
 47#ifndef _TALGORITHM_H_
 48#include "core/tAlgorithm.h"
 49#endif
 50
 51
 52/// Set of planes which can be tested against bounding volumes.
 53///
 54/// This class is meant as a helper to collect functionality for working with sets
 55/// of planes.  As a helper, it does not define means to manage the data it uses.
 56///
 57/// @warn This class does not manage the memory needed for the set.
 58template< typename T >
 59class PlaneSet
 60{
 61   protected:
 62
 63      /// Number of planes in #mPlanes.
 64      U32 mNumPlanes;
 65
 66      /// Set of planes.  The memory for this array is managed outside
 67      /// this class.
 68      const T* mPlanes;
 69
 70      template< typename P > OverlapTestResult _testOverlap( const P& bounds ) const;
 71      template< typename P > bool _isContained( const P& bounds ) const;
 72
 73   public:
 74
 75      /// @name Constructors
 76      /// @{
 77
 78      /// Create an uninitialized set.
 79      /// @warn None of the members will be initialized.
 80      PlaneSet() :mNumPlanes(0), mPlanes(NULL) {}
 81      
 82      /// Use the given set of planes to initialize the set.
 83      ///
 84      /// @param planes The planes.  Memory must be valid for the entire
 85      ///   lifetime of the plane set.
 86      /// @param numPlanes Number of planes.
 87      PlaneSet( const T* planes, U32 numPlanes )
 88         : mNumPlanes( numPlanes ), mPlanes( planes ) {}
 89
 90      /// @}
 91
 92      /// @name Accessors
 93      /// @{
 94
 95      /// Return the number of planes that this set consists of.
 96      U32 getNumPlanes() const { return mNumPlanes; }
 97
 98      /// Return the array of planes for this set.
 99      const T* getPlanes() const { return mPlanes; }
100
101      /// @}
102
103      /// @name Intersection
104      /// All of these intersection methods are approximate in that they can produce
105      /// false positives on GeometryIntersecting.  For precise results, use Intersector.
106      /// @{
107
108      /// Test intersection of the given AABB with the volume defined by the plane set.
109      ///
110      /// @param aabb Axis-aligned bounding box.
111      /// @return The type of overlap that the given AABB has with the plane set.
112      ///
113      /// @note The method will not test for those edge cases where none of the planes
114      ///      rejects the given AABB yet the AABB is actually outside the volume defined by the planes.
115      ///      This speeds up the test at the cost of losing precision which is acceptable for
116      ///      cases where doing the additional tests for all intersecting objects will generally
117      ///      waste more time than accepting a few additional non-intersecting objects as
118      ///      intersecting.
119      OverlapTestResult testPotentialIntersection( const Box3F& aabb ) const
120      {
121         return _testOverlap( aabb );
122      }
123
124      /// Test intersection of the given sphere with the volume defined by the plane set.
125      ///
126      /// @param sphere Sphere.
127      /// @return The type of overlap that the given sphere has with the plane set.
128      ///
129      /// @note The method will not test for those edge cases where none of the planes
130      ///      rejects the given sphere yet the sphere is actually outside the volume defined by the planes.
131      ///      This speeds up the test at the cost of losing precision which is acceptable for
132      ///      cases where doing the additional tests for all intersecting objects will generally
133      ///      waste more time than accepting a few additional non-intersecting objects as
134      ///      intersecting.
135      OverlapTestResult testPotentialIntersection( const SphereF& sphere ) const
136      {
137         return _testOverlap( sphere );
138      }
139
140      /// Test intersection of the given OBB with the volume defined by the plane set.
141      ///
142      /// @param obb Oriented bounding box.
143      /// @return The type of overlap that the given OBB has with the plane set.
144      ///
145      /// @note The method will not test for those edge cases where none of the planes
146      ///      rejects the given OBB yet the OBB is actually outside the volume defined by the planes.
147      ///      This speeds up the test at the cost of losing precision which is acceptable for
148      ///      cases where doing the additional tests for all intersecting objects will generally
149      ///      waste more time than accepting a few additional non-intersecting objects as
150      ///      intersecting.
151      OverlapTestResult testPotentialIntersection( const OrientedBox3F& obb ) const
152      {
153         return _testOverlap( obb );
154      }
155
156      /// Returns a bitmask of which planes are hit by the given box.
157      U32 testPlanes( const Box3F& bounds, U32 planeMask = 0xFFFFFFFF, F32 expand = 0.0f ) const;
158
159      /// @}
160
161      /// @name Containment
162      /// Testing for containment of geometric shapes within the volume enclosed by the planes.
163      /// @{
164
165      /// Return true if the given point lies on the positive side of all the planes
166      /// in the set.
167      bool isContained( const Point3F& point, F32 epsilon = __EQUAL_CONST_F ) const;
168
169      /// Return true if all of the given points lie on the positive side of all the planes
170      /// in the set.
171      bool isContained( const Point3F* points, U32 numPoints ) const;
172
173      /// Return true if the given AABB lies on the positive side of all the planes
174      /// in the set.
175      bool isContained( const Box3F& aabb ) const { return _isContained( aabb ); }
176
177      /// Return true if the given sphere lies on the positive side of all the planes
178      /// in the set.
179      bool isContained( const SphereF& sphere ) const { return _isContained( sphere ); }
180
181      /// Return true if the given OBB lies on the positive side of all the planes
182      /// in the set.
183      bool isContained( const OrientedBox3F& obb ) const { return _isContained( obb ); }
184
185      /// @}
186
187      /// @name Clipping
188      /// @{
189
190      /// Clip the given line segment against the plane set.  If the segment
191      /// intersects with any of the planes, the points will be clipped at the
192      /// intersection.
193      ///
194      /// @return True if any part of the segment is inside the volume defined by the plane set.
195      bool clipSegment( Point3F& pnt0, Point3F& pnt1 ) const;
196
197      /// Clip a convex polygon by all planes in the set.
198      ///
199      /// @param inVertices Array holding the vertices of the input polygon.
200      /// @param inNumVertices Number of vertices in @a inVertices.
201      /// @param outVertices Array to hold the vertices of the clipped polygon.  Must have spaces for
202      ///   @a inNumVertices + numberOfPlanesInSet.  Must not be the same as @a inVertices.
203      /// @param maxOutVertices Maximum number of vertices that can be stored in @a outVertices.  If insufficient to
204      ///   store the clipped polygon, the return value will be 0.
205      ///
206      /// @return Number of vertices in the clipped polygon, i.e. number of vertices stored in @a outVertices.
207      ///
208      /// @note Be aware that if the polygon fully lies on the negative side of all planes,
209      ///   the resulting @a outNumVertices will be zero, i.e. no polygon will result from the clip.
210      U32 clipPolygon( const Point3F* inVertices, U32 inNumVertices, Point3F* outVertices, U32 maxOutVertices ) const;
211
212      /// @}
213};
214
215typedef PlaneSet< PlaneF> PlaneSetF;
216typedef PlaneSet< PlaneD> PlaneSetD;
217
218
219//-----------------------------------------------------------------------------
220
221template< typename T >
222template< typename P >
223inline OverlapTestResult PlaneSet< T >::_testOverlap( const P& bounds ) const
224{
225   bool allInside = true;
226
227   // First, find out whether there is any plane for which the bounds completely
228   // lie on the negative side.  If so, the bounds are clearly outside of the volume.
229   
230   const U32 numPlanes = getNumPlanes();
231   for( U32 nplane = 0; nplane < numPlanes; ++ nplane )
232   {
233      const PlaneF& plane = getPlanes()[ nplane ];
234
235      const PlaneF::Side side = plane.whichSide( bounds );
236      if( side == PlaneF::Back )
237         return GeometryOutside;
238
239      if( side != PlaneF::Front )
240         allInside = false;
241   }
242
243   // Test for containment.
244
245   if( allInside )
246      return GeometryInside;
247
248   // Otherwise classify as intersecting.
249
250   return GeometryIntersecting;
251}
252
253//-----------------------------------------------------------------------------
254
255template< typename T >
256inline bool PlaneSet< T >::isContained( const Point3F& point, F32 epsilon ) const
257{
258   epsilon = - epsilon;
259
260   for( U32 i = 0; i < mNumPlanes; ++ i )
261   {
262      const F32 dist = mPlanes[ i ].distToPlane( point );
263      if( dist < epsilon )
264         return false;
265   }
266
267   return true;
268}
269
270//-----------------------------------------------------------------------------
271
272template< typename T >
273inline bool PlaneSet< T >::isContained( const Point3F* points, U32 numPoints ) const
274{
275   for( U32 i = 0; i < numPoints; ++ i )
276      if( !isContained( points[ i ] ) )
277         return false;
278
279   return true;
280}
281
282//-----------------------------------------------------------------------------
283
284template< typename T >
285template< typename P >
286inline bool PlaneSet< T >::_isContained( const P& bounds ) const
287{
288   for( U32 i = 0; i < mNumPlanes; ++ i )
289      if( mPlanes[ i ].whichSide( bounds ) != PlaneF::Front )
290         return false;
291
292   return true;
293}
294
295//-----------------------------------------------------------------------------
296
297template< typename T >
298U32 PlaneSet< T >::testPlanes( const Box3F& bounds, U32 planeMask, F32 expand ) const
299{
300   AssertFatal( mNumPlanes <= 32, "PlaneSet::testPlanes - Too many planes in set!" );
301
302   // This is based on the paper "A Faster Overlap Test for a Plane and a Bounding Box" 
303   // by Kenny Hoff.  See http://www.cs.unc.edu/~hoff/research/vfculler/boxplane.html
304
305   U32 retMask = 0;
306
307   const U32 numPlanes = getMin( mNumPlanes, U32( 32 ) );
308   for ( S32 i = 0; i < numPlanes; i++ )
309   {
310      U32 mask = ( 1 << i );
311
312      if ( !( planeMask & mask ) )
313         continue;
314
315      const PlaneF& plane = mPlanes[ i ];
316
317      Point3F minPoint, maxPoint;
318
319      if( plane.x > 0 )
320      {
321         maxPoint.x = bounds.maxExtents.x;
322         minPoint.x = bounds.minExtents.x;
323      }
324      else
325      {
326         maxPoint.x = bounds.minExtents.x;
327         minPoint.x = bounds.maxExtents.x;
328      }
329
330      if( plane.y > 0 )
331      {
332         maxPoint.y = bounds.maxExtents.y;
333         minPoint.y = bounds.minExtents.y;
334      }
335      else
336      {
337         maxPoint.y = bounds.minExtents.y;
338         minPoint.y = bounds.maxExtents.y;
339      }
340
341      if( plane.z > 0 )
342      {
343         maxPoint.z = bounds.maxExtents.z;
344         minPoint.z = bounds.minExtents.z;
345      }
346      else
347      {
348         maxPoint.z = bounds.minExtents.z;
349         minPoint.z = bounds.maxExtents.z;
350      }
351
352      F32 maxDot = mDot( maxPoint, plane );
353
354      if( maxDot <= - ( plane.d + expand ) )
355         return -1;
356
357      F32 minDot = mDot( minPoint, plane );
358
359      if( ( minDot + plane.d ) < 0.0f )
360         retMask |= mask;
361   }
362
363   return retMask;
364}
365
366//-----------------------------------------------------------------------------
367
368template< typename T >
369bool PlaneSet< T >::clipSegment( Point3F &pnt0, Point3F &pnt1 ) const
370{  
371   F32 tmin = F32_MAX;
372   F32 tmax = -F32_MAX;
373   U32 hitCount = 0;
374   Point3F tpnt;
375
376   const U32 numPlanes = mNumPlanes;
377   for( U32 i = 0; i < numPlanes; ++ i )
378   {
379      const PlaneF &plane = mPlanes[ i ];
380
381      F32 t = plane.intersect( pnt0, pnt1 );
382
383      if( t >= 0.0f && t <= 1.0f )
384      {
385         tpnt.interpolate( pnt0, pnt1, t );
386
387         if ( isContained( tpnt, 1.0e-004f ) )
388         {
389            tmin = getMin( tmin, t );
390            tmax = getMax( tmax, t );
391            hitCount ++;
392         }
393      }
394   }
395
396   // If we had no intersections then either both points are inside or both are outside.
397
398   if( hitCount == 0 )  
399      return isContained( pnt0 );
400
401   // If we had one intersection then we have one point inside.
402   // tmin and tmax are the same here.
403   if( hitCount == 1 )
404   {
405      if( isContained( pnt0 ) )
406         pnt1.interpolate( pnt0, pnt1, tmax );
407      else
408         pnt0.interpolate( pnt0, pnt1, tmin );
409   }
410   else
411   {
412      Point3F prevPnt0( pnt0 );
413      Point3F prevPnt1( pnt1 );
414
415      if( tmin < F32_MAX )
416         pnt0.interpolate( prevPnt0, prevPnt1, tmin );
417      if( tmax > -F32_MAX )
418         pnt1.interpolate( prevPnt0, prevPnt1, tmax );
419   }
420
421   return true;   
422}
423
424//-----------------------------------------------------------------------------
425
426template< typename T >
427U32 PlaneSet< T >::clipPolygon( const Point3F* inVertices, U32 inNumVertices, Point3F* outVertices, U32 maxOutVertices ) const
428{
429   TempAlloc< Point3F> tempBuffer( inNumVertices + mNumPlanes );
430
431   // We use two buffers as interchanging roles as source and target.
432   // For the first iteration, inVertices is the source.
433
434   Point3F* tempPolygon = tempBuffer;
435   Point3F* clippedPolygon = const_cast< Point3F* >( inVertices );
436
437   U32 numClippedPolygonVertices = inNumVertices;
438   U32 numTempPolygonVertices = 0;
439
440   for( U32 nplane = 0; nplane < mNumPlanes; ++ nplane )
441   {
442      // Make the output of the last iteration the
443      // input of this iteration.
444
445     T3D::swap( tempPolygon, clippedPolygon );
446      numTempPolygonVertices = numClippedPolygonVertices;
447
448      if( maxOutVertices < numTempPolygonVertices + 1 )
449         return 0;
450
451      // Clip our current remainder of the original polygon
452      // against the current plane.
453
454      const PlaneF& plane = mPlanes[ nplane ];
455      numClippedPolygonVertices = plane.clipPolygon( tempPolygon, numTempPolygonVertices, clippedPolygon );
456
457      // If the polygon was completely on the backside of the plane,
458      // then polygon is outside the frustum.  In this case, return false
459      // to indicate we haven't clipped anything.
460
461      if( !numClippedPolygonVertices )
462         return 0;
463
464      // On first iteration, replace the inVertices with the
465      // outVertices buffer.
466
467      if( tempPolygon == inVertices )
468         tempPolygon = outVertices;
469   }
470
471   // If outVertices isn't the target buffer of the last
472   // iteration, copy the vertices over from the temporary
473   // buffer.
474
475   if( clippedPolygon != outVertices )
476      dMemcpy( outVertices, clippedPolygon, numClippedPolygonVertices * sizeof( Point3F ) );
477
478   return numClippedPolygonVertices;
479}
480
481#endif // !_MPLANESET_H_
482