mIntersector.h

Engine/source/math/mIntersector.h

Precise and fast geometric intersection testing.

More...

Classes:

Detailed Description

Precise and fast geometric intersection testing.

  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 _MINTERSECTOR_H_
 25#define _MINTERSECTOR_H_
 26
 27#ifndef _MCONSTANTS_H_
 28#include "math/mConstants.h"
 29#endif
 30
 31#ifndef _MBOX_H_
 32#include "math/mBox.h"
 33#endif
 34
 35#ifndef _MORIENTEDBOX_H_
 36#include "math/mOrientedBox.h"
 37#endif
 38
 39#ifndef _MSPHERE_H_
 40#include "math/mSphere.h"
 41#endif
 42
 43#ifndef _MPLANE_H_
 44#include "math/mPlane.h"
 45#endif
 46
 47#ifndef _MPOLYHEDRON_H_
 48#include "math/mPolyhedron.h"
 49#endif
 50
 51#ifndef _MPLANETRANSFORMER_H_
 52#include "math/mPlaneTransformer.h"
 53#endif
 54
 55#ifndef _PROFILER_H_
 56#include "platform/profiler.h"
 57#endif
 58
 59
 60/// @file
 61/// Precise and fast geometric intersection testing.
 62
 63
 64/// Base class for intersector implementations.
 65template< typename Tester, typename Testee >
 66struct IntersectorBase
 67{
 68      typedef Tester TesterType;
 69      typedef Testee TesteeType;
 70
 71   protected:
 72
 73      TesterType mTester;
 74
 75   public:
 76
 77      IntersectorBase() {}
 78      IntersectorBase( const TesterType& tester )
 79         : mTester( tester ) {}
 80};
 81
 82
 83/// Convex polyhedron / AABB intersection.
 84///
 85/// This class implements the algorithm described in "Detecting Intersection of a Rectangular
 86/// Solid and a Convex Polyhedron", Graphics Gems IV, Chapter 1.7, by Ned Greene.
 87///
 88/// The polyhedron is preprocessed when an object of this class is constructed.
 89///
 90/// This class also assumes that the polyhedron is represented in object space and thus also
 91/// stores local copies of the polyhedron's planes transformed into world space.
 92///
 93/// The approach of the algorithm is simple.  It uses a maximum of three successive stages
 94/// to determine intersection.  Each stage can early out if it can draw a conclusive result
 95/// already.
 96///
 97/// 1. Simple tests of the polyhedron's bounding box against the input box.
 98/// 2. Standard test on plane set.
 99/// 3. Plane tests reduced to 2D and done for each of the orthographic side projections.
100///
101/// @note The intersector depends on planes facing inwards.
102template< typename Polyhedron >
103struct PolyhedronBoxIntersector : public IntersectorBase< Polyhedron, Box3F >
104{
105      typedef IntersectorBase< Polyhedron, Box3F> Parent;
106      typedef Polyhedron PolyhedronType;
107
108   protected:
109
110      /// Bounds of the polyhedron.
111      Box3F mBounds;
112
113      /// World-space planes.
114      Vector< PlaneF> mPlanes;
115
116      /// Number of silhouette edges for each of the orthographic projections.
117      Point3I mNumEdgeLines;
118
119      /// Edge line equations.  X projection first, then Y, then Z.
120      /// X of each equation is mapped to a, Y to b, and Z to c of the standard
121      /// implicit form of line equations.
122      Vector< Point3F> mEdgeLines;
123
124      /// Run the preprocessing step on the current polyhedron.
125      void _preprocess( const MatrixF& objToWorld, const Point3F& scale );
126
127      /// Project the point orthogonally down the given axis such that
128      /// the orientation of the resulting coordinate system remains
129      /// right-handed.
130      Point2F _project( U32 axis, const Point3F& p )
131      {
132         switch( axis )
133         {
134            case 0:  return Point2F( - p.y, p.z );
135            case 1:  return Point2F( p.x, p.z );
136            default: // silence compiler
137            case 2:  return Point2F( p.x, - p.y );
138         }
139      }
140
141   public:
142
143      PolyhedronBoxIntersector() {}
144      PolyhedronBoxIntersector( const PolyhedronType& polyhedron,
145                                const MatrixF& objToWorld,
146                                const Point3F& scale,
147                                const Box3F& wsBounds )
148         : Parent( polyhedron ), mBounds( wsBounds )
149      {
150         _preprocess( objToWorld, scale );
151      }
152
153      OverlapTestResult test( const Box3F& box ) const;
154};
155
156//-----------------------------------------------------------------------------
157
158template< typename Polyhedron >
159void PolyhedronBoxIntersector< Polyhedron >::_preprocess( const MatrixF& objToWorld, const Point3F& scale )
160{
161   PROFILE_SCOPE( PolyhedronBoxIntersector_preprocess );
162
163   // Transform the planes.
164
165   const U32 numPlanes = this->mTester.getNumPlanes();
166   const typename Polyhedron::PlaneType* planes = this->mTester.getPlanes();
167   
168   PlaneTransformer transformer;
169   transformer.set( objToWorld, scale );
170
171   mPlanes.setSize( numPlanes );
172   for( U32 i = 0; i < numPlanes; ++ i )
173      transformer.transform( planes[ i ], mPlanes[ i ] );
174
175   // Extract the silhouettes for each of the three
176   // orthographic projections.
177
178   const U32 numEdges = this->mTester.getNumEdges();
179   const typename Polyhedron::EdgeType* edges = this->mTester.getEdges();
180   const typename Polyhedron::PointType* points = this->mTester.getPoints();
181
182   for( U32 i = 0; i < 3; ++ i )
183   {
184      U32 numEdgesThisProj = 0;
185
186      // Gather edge-lines for this projection.
187
188      for( U32 n = 0; n < numEdges; ++ n )
189      {
190         const typename Polyhedron::EdgeType& edge = edges[ n ];
191
192         // Compute dot product with face normals.  With our projection
193         // pointing straight down the current axis, this is reduced to
194         // '1*normal[i]'.
195
196         F32 dotFace[ 2 ];
197
198         dotFace[ 0 ] = mPlanes[ edge.face[ 0 ] ][ i ];
199         dotFace[ 1 ] = mPlanes[ edge.face[ 1 ] ][ i ];
200
201         // Skip edge if not a silhouette edge in this view.
202
203         if( mSign( dotFace[ 0 ] ) == mSign( dotFace[ 1 ] ) )
204            continue;
205
206         // Find out which face is the front facing one.  Since we expect normals
207         // to be pointing inwards, this means a reversal of the normal back facing
208         // test and we're looking for a normal facing the *same* way as our projection.
209
210         const U32 frontFace = dotFace[ 0 ] > 0.f ? 0 : 1;
211         if( dotFace[ frontFace ] <= 0.f )
212            continue; // This face or other face is perpendicular to us.
213
214         // Now we want to find the line equation for the edge.  For that, we first need
215         // the normal.  The direction of the normal is important so that we identify
216         // the half-spaces correctly.  We want it to be pointing to the inside of the
217         // polyhedron.
218
219         Point3F v1 = points[ edge.vertex[ 0 ] ];
220         Point3F v2 = points[ edge.vertex[ 1 ] ];
221
222         v1.convolve( scale );
223         v2.convolve( scale );
224
225         objToWorld.mulP( v1 );
226         objToWorld.mulP( v2 );
227
228         Point2F q = _project( i, v1 ); // First point on line.
229         Point2F p = _project( i, v2 ); // Second point on line.
230
231         if( frontFace != 0 )
232          T3D::swap( p, q );
233
234         Point2F normal( - ( p.y - q.y ), p.x - q.x );
235         normal.normalize();
236
237         // Now compute c.
238
239         const F32 c = mDot( - q, normal );
240
241         // Add the edge.
242         
243         mEdgeLines.push_back(
244            Point3F( normal.x, normal.y, c )
245         );
246         
247         numEdgesThisProj ++;
248      }
249
250      mNumEdgeLines[ i ] = numEdgesThisProj;
251   }
252}
253
254//-----------------------------------------------------------------------------
255
256template< typename Polyhedron >
257OverlapTestResult PolyhedronBoxIntersector< Polyhedron >::test( const Box3F& box ) const
258{
259   PROFILE_SCOPE( PolyhedronBoxIntersector_test );
260
261   // -- Bounding box tests. --
262
263   // If the box does not intersect with the AABB of the polyhedron,
264   // it must be outside.
265
266   if( !mBounds.isOverlapped( box ) )
267      return GeometryOutside;
268
269   // If the polyhedron's bounding box is fully contained in the given box,
270   // the box is intersecting.
271   
272   if( box.isContained( mBounds ) )
273      return GeometryIntersecting;
274
275   // -- Face-plane tests. --
276   
277   bool insideAll = true;
278
279   // Test each of the planes to see if the bounding box lies
280   // fully in the negative space of any one of them.
281
282   const U32 numPlanes = mPlanes.size();
283   for( U32 i = 0; i < numPlanes; ++ i )
284   {
285      const PlaneF& plane = mPlanes[ i ];
286
287      PlaneF::Side boxSide = plane.whichSide( box );
288      if( boxSide == PlaneF::Back )
289         return GeometryOutside;
290
291      insideAll &= ( boxSide == PlaneF::Front );
292   }
293
294   // If the box is on the positive space of all of the polyhedron's
295   // planes, it's inside.
296
297   if( insideAll )
298      return GeometryInside;
299
300   // -- Edge-line tests. --
301
302   U32 edgeLineIndex = 0;
303   for( U32 i = 0; i < 3; ++ i )
304   {
305      // Determine the mapping of 3D to 2D for this projection.
306
307      U32 xIndex = 0;
308      U32 yIndex = 0;
309
310      switch( i )
311      {
312         case 0:  xIndex = 1; yIndex = 2; break;
313         case 1:  xIndex = 0; yIndex = 2; break;
314         case 2:  xIndex = 0; yIndex = 1; break;
315      }
316
317      // Go through the edge-lines for this projection and
318      // test the p-vertex for each edge line.
319
320      const U32 numEdgesForThisProj = mNumEdgeLines[ i ];
321      for( U32 n = 0; n < numEdgesForThisProj; ++ n, edgeLineIndex ++ )
322      {
323         const Point3F& edgeLine = mEdgeLines[ edgeLineIndex ];
324
325         // Determine the p-vertex for the current AABB/edge combo.
326         // Need to account for the axis flipping we have applied to maintain
327         // a right-handed coordinate system.
328
329         Point2F pVertex;
330
331         switch( i )
332         {
333            case 0:
334               pVertex.x = - ( edgeLine.x < 0.f ? box.maxExtents[ xIndex ] : box.minExtents[ xIndex ] );
335               pVertex.y = edgeLine.y > 0.f ? box.maxExtents[ yIndex ] : box.minExtents[ yIndex ];
336               break;
337
338            case 1:
339               pVertex.x = edgeLine.x > 0.f ? box.maxExtents[ xIndex ] : box.minExtents[ xIndex ];
340               pVertex.y = edgeLine.y > 0.f ? box.maxExtents[ yIndex ] : box.minExtents[ yIndex ];
341               break;
342
343            case 2:
344               pVertex.x = edgeLine.x > 0.f ? box.maxExtents[ xIndex ] : box.minExtents[ xIndex ];
345               pVertex.y = - ( edgeLine.y < 0.f ? box.maxExtents[ yIndex ] : box.minExtents[ yIndex ] );
346               break;
347         }
348
349         // See if the p-vertex lies inside in the negative half-space of the
350         // edge line.  If so, the AABB is not intersecting the polyhedron in
351         // this projection so we can conclude our search here.
352
353         const F32 d = edgeLine.x * pVertex.x + edgeLine.y * pVertex.y + edgeLine.z;
354         if( d < 0.f )
355            return GeometryOutside;
356      }
357   }
358
359   // Done.  Determined to be intersecting.
360
361   return GeometryIntersecting;
362}
363
364
365/// Geometric intersecting testing.
366///
367/// This class is meant to be used for testing multiple geometries against
368/// a specific geometric object.  Unlike the various intersection test routines
369/// in other classes, this class might precompute and store data that is going
370/// to be used repeatedly in the tests.  As such, Intersector can be faster
371/// in certain cases.
372///
373/// Also, intersectors are required to implement *exact* intersection tests, i.e.
374/// it is not acceptable for an Intersector to produce false positives on any
375/// of the OverlapTestResult values.
376///
377/// This class itself has no functionality.  It depends on specializations.
378template< typename Tester, typename Testee >
379struct Intersector : public IntersectorBase< Tester, Testee > {};
380
381// Specializations.
382
383template<>
384struct Intersector< AnyPolyhedron, Box3F > : public PolyhedronBoxIntersector< AnyPolyhedron > {};
385
386#endif // !_MINTERSECTOR_H_
387