mPolyhedron.h

Public Typedefs

PolyhedronImpl< PolyhedronUnmanagedVectorData >

AnyPolyhedron 

PolyhedronImpl

Polyhedron 

Public Typedefs

typedef PolyhedronImpl< PolyhedronUnmanagedVectorData > AnyPolyhedron 

The polyhedron type to which all other polyhedron types should be convertible.

typedef PolyhedronImpl Polyhedron 

Default polyhedron type.

  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 _MPOLYHEDRON_H_
 25#define _MPOLYHEDRON_H_
 26
 27#ifndef _MPOINT3_H_
 28#include "math/mPoint3.h"
 29#endif
 30
 31#ifndef _MPLANE_H_
 32#include "math/mPlane.h"
 33#endif
 34
 35#ifndef _MPLANESET_H_
 36#include "math/mPlaneSet.h"
 37#endif
 38
 39#ifndef _TVECTOR_H_
 40#include "core/util/tVector.h"
 41#endif
 42
 43#ifndef _TUNMANAGEDVECTOR_H_
 44#include "core/util/tUnmanagedVector.h"
 45#endif
 46
 47#ifndef _TFIXEDSIZEVECTOR_H_
 48#include "core/util/tFixedSizeVector.h"
 49#endif
 50
 51#ifndef _MCONSTANTS_H_
 52#include "math/mConstants.h"
 53#endif
 54
 55
 56/// @file
 57/// Templated polyhedron code to allow all code to use a central definition of polyhedrons and
 58/// their functionality (intersection, clipping, etc.) yet still maintain full control over how
 59/// to create and store their data.
 60
 61
 62
 63struct PolyhedronUnmanagedVectorData;
 64template< typename Base > struct PolyhedronImpl;
 65
 66
 67/// The polyhedron type to which all other polyhedron types should be convertible.
 68typedef PolyhedronImpl< PolyhedronUnmanagedVectorData> AnyPolyhedron;
 69
 70
 71
 72/// Base class for helping to abstract over how a polyhedron
 73/// stores and updates its data.
 74///
 75/// The PolyhedronData class hierarchy is designed to give users of PolyhedronImpl
 76/// maximum freedom in modifying those behaviors.  This leads to some duplicating
 77/// in the various PolyhedronData classes but it ultimately provides greater control.
 78///
 79/// All accesses to the data go through accessors on the base classes.  This gives
 80/// the base class the freedom to implement lazy updates, for example.
 81///
 82/// A given base implementation is also free to store additional data or derive extended
 83/// classes from the base classes expected for points (Point3F), edges (Edge), and planes
 84/// (PlaneF).  If a class does that, it loses the ability to trivially convert to
 85/// AnyPolyhedron, though.
 86struct PolyhedronData
 87{
 88      /// Winged edge.
 89      ///
 90      /// @note Must be oriented clockwise for face[0]!  This is important!
 91      struct Edge
 92      {
 93         /// Index into plane vector for the two planes that go through this
 94         /// edge.
 95         U32 face[ 2 ];
 96
 97         /// Index into point vector for the beginning and end point of the edge.
 98         /// @note The vector "vertex[ 1 ] - vertex[ 0 ]" must be oriented such that
 99         ///   it defines a *clockwise* orientation for face[ 0 ].  This is important!
100         U32 vertex[ 2 ];
101
102         Edge() { std::fill_n(face, 2, 0), std::fill_n(vertex, 2, 0); }
103         Edge( U32 face1, U32 face2, U32 vertex1, U32 vertex2 )
104         {
105            face[ 0 ] = face1;
106            face[ 1 ] = face2;
107            vertex[ 0 ] = vertex1;
108            vertex[ 1 ] = vertex2;
109         }
110      };
111
112      typedef Edge EdgeType;
113      typedef PlaneF PlaneType;
114      typedef Point3F PointType;
115
116      template< typename Polyhedron >
117      static void buildBoxData( Polyhedron& poly, const MatrixF& mat, const Box3F& box, bool invertNormals = false );
118};
119
120/// Polyhedron data stored in Vectors.
121struct PolyhedronVectorData : public PolyhedronData
122{
123      typedef Vector< PlaneF> PlaneListType;
124      typedef Vector< Point3F> PointListType;
125      typedef Vector< Edge> EdgeListType;
126
127      /// List of planes.  Note that by default, the normals facing *inwards*.
128      PlaneListType mPlaneList;
129
130      /// List of vertices.
131      PointListType mPointList;
132
133      /// List of edges.
134      EdgeListType mEdgeList;
135
136      PolyhedronVectorData()
137      {
138         VECTOR_SET_ASSOCIATION(mPointList);
139         VECTOR_SET_ASSOCIATION(mPlaneList);
140         VECTOR_SET_ASSOCIATION(mEdgeList);
141      }
142
143      /// @name Accessors
144      /// @{
145
146      /// Return the number of planes that make up this polyhedron.
147      U32 getNumPlanes() const { return mPlaneList.size(); }
148
149      /// Return the planes that make up the polyhedron.
150      /// @note The normals of these planes are facing *inwards*.
151      PlaneF* getPlanes() const { return mPlaneList.address(); }
152
153      /// Return the number of points that this polyhedron has.
154      U32 getNumPoints() const { return mPointList.size(); }
155
156      /// 
157      Point3F* getPoints() const { return mPointList.address(); }
158
159      /// Return the number of edges that this polyhedron has.
160      U32 getNumEdges() const { return mEdgeList.size(); }
161
162      ///
163      Edge* getEdges() const { return mEdgeList.address(); }
164
165      /// @}
166
167      /// Conversion to the common polyhedron type.
168      operator AnyPolyhedron() const;
169
170      void buildBox( const MatrixF& mat, const Box3F& box, bool invertNormals = false )
171      {
172       mPointList.setSize( 8 );
173       mPlaneList.setSize( 6 );
174       mEdgeList.setSize( 12 );
175
176         buildBoxData( *this, mat, box, invertNormals );
177      }
178
179      /// Build a polyhedron from the given set of planes.
180      void buildFromPlanes( const PlaneSetF& planes );
181};
182
183/// Polyhedron data stored as raw points with memory
184/// being managed externally.
185struct PolyhedronUnmanagedVectorData : public PolyhedronData
186{
187      typedef UnmanagedVector< PlaneF> PlaneListType;
188      typedef UnmanagedVector< Point3F> PointListType;
189      typedef UnmanagedVector< Edge> EdgeListType;
190
191   protected:
192
193      /// List of planes.  Note that by default, the normals facing *inwards*.
194      PlaneListType mPlaneList;
195
196      /// List of vertices.
197      PointListType mPointList;
198
199      /// List of edges.
200      EdgeListType mEdgeList;
201
202   public:
203
204      /// @name Accessors
205      /// @{
206
207      /// Return the number of planes that make up this polyhedron.
208      U32 getNumPlanes() const { return mPlaneList.size(); }
209
210      /// Return the planes that make up the polyhedron.
211      /// @note The normals of these planes are facing *inwards*.
212      const PlaneF* getPlanes() const { return mPlaneList.address(); }
213      PlaneF* getPlanes() { return mPlaneList.address(); }
214
215      /// Return the number of points that this polyhedron has.
216      U32 getNumPoints() const { return mPointList.size(); }
217
218      /// 
219      const Point3F* getPoints() const { return mPointList.address(); }
220      Point3F* getPoints() { return mPointList.address(); }
221
222      /// Return the number of edges that this polyhedron has.
223      U32 getNumEdges() const { return mEdgeList.size(); }
224
225      ///
226      const Edge* getEdges() const { return mEdgeList.address(); }
227      Edge* getEdges() { return mEdgeList.address(); }
228
229      /// @}
230};
231
232/// Polyhedron data stored in fixed size arrays.
233template< S32 NUM_PLANES, S32 NUM_POINTS, S32 NUM_EDGES >
234struct PolyhedronFixedVectorData : public PolyhedronData
235{
236      typedef FixedSizeVector< PlaneF, NUM_PLANES> PlaneListType;
237      typedef FixedSizeVector< Point3F, NUM_POINTS> PointListType;
238      typedef FixedSizeVector< Edge, NUM_EDGES> EdgeListType;
239
240   protected:
241
242      /// List of planes.  Note that by default, the normals facing *inwards*.
243      PlaneListType mPlaneList;
244
245      /// List of vertices.
246      PointListType mPointList;
247
248      /// List of edges.
249      EdgeListType mEdgeList;
250
251   public:
252
253
254      /// @name Accessors
255      /// @{
256
257      /// Return the number of planes that make up this polyhedron.
258      U32 getNumPlanes() const { return mPlaneList.size(); }
259
260      /// Return the planes that make up the polyhedron.
261      /// @note The normals of these planes are facing *inwards*.
262      PlaneF* getPlanes() const { return mPlaneList.address(); }
263
264      /// Return the number of points that this polyhedron has.
265      U32 getNumPoints() const { return mPointList.size(); }
266
267      /// 
268      Point3F* getPoints() const { return mPointList.address(); }
269
270      /// Return the number of edges that this polyhedron has.
271      U32 getNumEdges() const { return mEdgeList.size(); }
272
273      ///
274      Edge* getEdges() const { return mEdgeList.address(); }
275
276      /// @}
277
278      /// Conversion to the common polyhedron type.
279      operator AnyPolyhedron() const;
280};
281
282
283/// A polyhedron.
284///
285/// Polyhedrons are stored as both sets of planes as well sets of edges and vertices (basically
286/// a winged-edge format).
287///
288/// Polyhedrons must be convex.
289///
290/// @note The default orientation for the plane normals of a polyhedron is *inwards*.
291template< typename Base = PolyhedronVectorData >
292struct PolyhedronImpl : public Base
293{
294      typedef typename Base::Edge Edge;
295
296      typedef typename Base::PlaneListType PlaneListType;
297      typedef typename Base::PointListType PointListType;
298      typedef typename Base::EdgeListType EdgeListType;
299
300      /// Construct an empty polyhedron.
301      PolyhedronImpl() {}
302
303      /// Construct a polyhedron described by the given planes and edges.
304      PolyhedronImpl( PlaneListType planes, PointListType points, EdgeListType edges )
305      {
306         this->mPlaneList = planes;
307         this->mPointList = points;
308         this->mEdgeList = edges;
309      }
310
311      /// Return the AABB around the polyhedron.
312      Box3F getBounds() const
313      {
314         return Box3F::aroundPoints( this->getPoints(), this->getNumPoints() );
315      }
316
317      /// Return the median point of all points defined on the polyhedron.
318      Point3F getCenterPoint() const;
319
320      /// @name Transform
321      /// @{
322
323      /// Transform the polyhedron using the given transform matrix and scale.
324      void transform( const MatrixF& matrix, const Point3F& scale = Point3F::One );
325
326      /// @}
327
328      /// @name Containment
329      /// @{
330
331      /// @see PlaneSet::isContained(const Point3F&,F32)
332      bool isContained( const Point3F& point, F32 epsilon = 0.f ) const
333      {
334         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( point, epsilon );
335      }
336
337      /// @see PlaneSet::isContained(const Point3F*,U32)
338      bool isContained( const Point3F* points, U32 numPoints ) const
339      {
340         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( points, numPoints );
341      }
342
343      /// @see PlaneSet::isContained(const Box3F&)
344      bool isContained( const Box3F& aabb ) const
345      {
346         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( aabb );
347      }
348
349      /// @see PlaneSet::isContained(const SphereF&)
350      bool isContained( const SphereF& sphere ) const
351      {
352         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( sphere );
353      }
354
355      /// @see PlaneSet::isContained(const OrientedBox3F&)
356      bool isContained( const OrientedBox3F& obb ) const
357      {
358         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( obb );
359      }
360
361      /// @}
362
363      /// @name Intersection
364      /// All of these intersection methods are approximate in that they can produce
365      /// false positives on GeometryIntersecting.  For precise testing, use Intersector.
366      /// @{
367
368      /// @see PlaneSet::testPotentialIntersection(const Box3F&)
369      OverlapTestResult testPotentialIntersection( const Box3F& aabb ) const
370      {
371         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( aabb );
372      }
373
374      /// @see PlaneSet::testPotentialIntersection(const SphereF&)
375      OverlapTestResult testPotentialIntersection( const SphereF& sphere ) const
376      {
377         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( sphere );
378      }
379
380      /// @see PlaneSet::testPotentialIntersection(const OrientedBox3F&)
381      OverlapTestResult testPotentialIntersection( const OrientedBox3F& obb ) const
382      {
383         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( obb );
384      }
385
386      /// @see PlaneSet::testPlanes
387      U32 testPlanes( const Box3F& bounds, U32 planeMask = 0xFFFFFFFF, F32 expand = 0.0f ) const
388      {
389         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPlanes( bounds, planeMask, expand );
390      }
391
392      /// @}
393
394      /// @name Clipping
395      /// Functionality to clip other geometries against the polyhedron.
396      /// @{
397
398      /// @see PlaneSet::clipSegment
399      bool clipSegment( Point3F& pnt0, Point3F& pnt1 ) const
400      {
401         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).clipSegment( pnt0, pnt1 );
402      }
403
404      /// @see PlaneSet::clipPolygon
405      U32 clipPolygon( const Point3F* inVertices, U32 inNumVertices, Point3F* outVertices, U32 maxOutVertices ) const
406      {
407         return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).clipPolygon( inVertices, inNumVertices, outVertices, maxOutVertices );
408      }
409
410      /// @}
411
412      /// @name Construction
413      /// Operations for constructing solids and polygons through boolean operations involving
414      /// the polyhedron.
415      /// @{
416
417      /// Build the intersection of this polyhedron with the given plane.  The result is a
418      /// polygon.
419      ///
420      /// @param plane Plane to intersect the polyhedron with.
421      /// @param outPoints (out) Array where the resulting polygon points are stored.  A safe size is to
422      ///   just allocate as many points as there are edges in the polyhedron.  If you know the maximum
423      ///   number of vertices that can result from the intersection (for example, 4 for a box), then
424      ///   it is ok to only allocate that much.
425      /// @param maxOutPoints Number of points that can be stored in @a outPoints.  If insufficient, the
426      ///   return value will be 0.
427      ///
428      /// @return The number of points written to @a outPoints.  If there is no intersection between the
429      ///   given plane and the polyhedron, this will be zero.
430      ///
431      /// @note The resulting points will be ordered to form a proper polygon but there is no guarantee
432      ///   on which direction the ordering is in compared to the plane.
433      U32 constructIntersection( const PlaneF& plane, Point3F* outPoints, U32 maxOutPoints ) const;
434
435      /// @}
436
437      /// @name Extraction
438      /// @{
439      
440      /// Extract the polygon for the given plane.
441      ///
442      /// The resulting indices will be CW ordered if the plane normals on the polyhedron are facing
443      /// inwards and CCW ordered otherwise.
444      ///
445      /// @param plane Index of the plane on the polyhedron.
446      /// @param outIndices Array where the resulting vertex indices will be stored.  Must have
447      ///   enough room.  If you don't know the exact size that you need, just allocate one index
448      ///   for any point in the mesh.
449      /// @param maxOutIndices The number of indices that can be stored in @a outIndices.  If insufficient,
450      ///   the return value will be 0.
451      ///
452      /// @return Number of indices written to @a outIndices.
453      ///
454      /// @note This method relies on correct CW ordering of edges with respect to face[0].
455      template< typename IndexType >
456      U32 extractFace( U32 plane, IndexType* outIndices, U32 maxOutIndices ) const;
457
458      /// @}
459
460   protected:
461
462      template< typename P >
463      OverlapTestResult _testOverlap( const P& bounds ) const;
464};
465
466/// Default polyhedron type.
467typedef PolyhedronImpl<> Polyhedron;
468
469
470//-----------------------------------------------------------------------------
471
472inline PolyhedronVectorData::operator AnyPolyhedron() const
473{
474   return AnyPolyhedron(
475      AnyPolyhedron::PlaneListType( getPlanes(), getNumPlanes() ),
476      AnyPolyhedron::PointListType( getPoints(), getNumPoints() ),
477      AnyPolyhedron::EdgeListType( getEdges(), getNumEdges() )
478   );
479}
480
481//-----------------------------------------------------------------------------
482
483template< S32 NUM_PLANES, S32 NUM_POINTS, S32 NUM_EDGES >
484inline PolyhedronFixedVectorData< NUM_PLANES, NUM_POINTS, NUM_EDGES >::operator AnyPolyhedron() const
485{
486   return AnyPolyhedron(
487      AnyPolyhedron::PlaneListType( getPlanes(), getNumPlanes() ),
488      AnyPolyhedron::PointListType( getPoints(), getNumPoints() ),
489      AnyPolyhedron::EdgeListType( getEdges(), getNumEdges() )
490   );
491}
492
493#endif // !_MPOLYHEDRON_H_
494