mPolyhedron.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492
  1. //-----------------------------------------------------------------------------
  2. // Copyright (c) 2012 GarageGames, LLC
  3. //
  4. // Permission is hereby granted, free of charge, to any person obtaining a copy
  5. // of this software and associated documentation files (the "Software"), to
  6. // deal in the Software without restriction, including without limitation the
  7. // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  8. // sell copies of the Software, and to permit persons to whom the Software is
  9. // furnished to do so, subject to the following conditions:
  10. //
  11. // The above copyright notice and this permission notice shall be included in
  12. // all copies or substantial portions of the Software.
  13. //
  14. // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15. // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16. // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17. // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18. // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19. // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  20. // IN THE SOFTWARE.
  21. //-----------------------------------------------------------------------------
  22. #ifndef _MPOLYHEDRON_H_
  23. #define _MPOLYHEDRON_H_
  24. #ifndef _MPOINT3_H_
  25. #include "math/mPoint3.h"
  26. #endif
  27. #ifndef _MPLANE_H_
  28. #include "math/mPlane.h"
  29. #endif
  30. #ifndef _MPLANESET_H_
  31. #include "math/mPlaneSet.h"
  32. #endif
  33. #ifndef _TVECTOR_H_
  34. #include "core/util/tVector.h"
  35. #endif
  36. #ifndef _TUNMANAGEDVECTOR_H_
  37. #include "core/util/tUnmanagedVector.h"
  38. #endif
  39. #ifndef _TFIXEDSIZEVECTOR_H_
  40. #include "core/util/tFixedSizeVector.h"
  41. #endif
  42. #ifndef _MCONSTANTS_H_
  43. #include "math/mConstants.h"
  44. #endif
  45. /// @file
  46. /// Templated polyhedron code to allow all code to use a central definition of polyhedrons and
  47. /// their functionality (intersection, clipping, etc.) yet still maintain full control over how
  48. /// to create and store their data.
  49. struct PolyhedronUnmanagedVectorData;
  50. template< typename Base > struct PolyhedronImpl;
  51. /// The polyhedron type to which all other polyhedron types should be convertible.
  52. typedef PolyhedronImpl< PolyhedronUnmanagedVectorData > AnyPolyhedron;
  53. /// Base class for helping to abstract over how a polyhedron
  54. /// stores and updates its data.
  55. ///
  56. /// The PolyhedronData class hierarchy is designed to give users of PolyhedronImpl
  57. /// maximum freedom in modifying those behaviors. This leads to some duplicating
  58. /// in the various PolyhedronData classes but it ultimately provides greater control.
  59. ///
  60. /// All accesses to the data go through accessors on the base classes. This gives
  61. /// the base class the freedom to implement lazy updates, for example.
  62. ///
  63. /// A given base implementation is also free to store additional data or derive extended
  64. /// classes from the base classes expected for points (Point3F), edges (Edge), and planes
  65. /// (PlaneF). If a class does that, it loses the ability to trivially convert to
  66. /// AnyPolyhedron, though.
  67. struct PolyhedronData
  68. {
  69. /// Winged edge.
  70. ///
  71. /// @note Must be oriented clockwise for face[0]! This is important!
  72. struct Edge
  73. {
  74. /// Index into plane vector for the two planes that go through this
  75. /// edge.
  76. U32 face[ 2 ];
  77. /// Index into point vector for the beginning and end point of the edge.
  78. /// @note The vector "vertex[ 1 ] - vertex[ 0 ]" must be oriented such that
  79. /// it defines a *clockwise* orientation for face[ 0 ]. This is important!
  80. U32 vertex[ 2 ];
  81. Edge() {}
  82. Edge( U32 face1, U32 face2, U32 vertex1, U32 vertex2 )
  83. {
  84. face[ 0 ] = face1;
  85. face[ 1 ] = face2;
  86. vertex[ 0 ] = vertex1;
  87. vertex[ 1 ] = vertex2;
  88. }
  89. };
  90. typedef Edge EdgeType;
  91. typedef PlaneF PlaneType;
  92. typedef Point3F PointType;
  93. template< typename Polyhedron >
  94. static void buildBoxData( Polyhedron& poly, const MatrixF& mat, const Box3F& box, bool invertNormals = false );
  95. };
  96. /// Polyhedron data stored in Vectors.
  97. struct PolyhedronVectorData : public PolyhedronData
  98. {
  99. typedef Vector< PlaneF > PlaneListType;
  100. typedef Vector< Point3F > PointListType;
  101. typedef Vector< Edge > EdgeListType;
  102. /// List of planes. Note that by default, the normals facing *inwards*.
  103. PlaneListType planeList;
  104. /// List of vertices.
  105. PointListType pointList;
  106. /// List of edges.
  107. EdgeListType edgeList;
  108. PolyhedronVectorData()
  109. {
  110. VECTOR_SET_ASSOCIATION( pointList );
  111. VECTOR_SET_ASSOCIATION( planeList );
  112. VECTOR_SET_ASSOCIATION( edgeList );
  113. }
  114. /// @name Accessors
  115. /// @{
  116. /// Return the number of planes that make up this polyhedron.
  117. U32 getNumPlanes() const { return planeList.size(); }
  118. /// Return the planes that make up the polyhedron.
  119. /// @note The normals of these planes are facing *inwards*.
  120. PlaneF* getPlanes() const { return planeList.address(); }
  121. /// Return the number of points that this polyhedron has.
  122. U32 getNumPoints() const { return pointList.size(); }
  123. ///
  124. Point3F* getPoints() const { return pointList.address(); }
  125. /// Return the number of edges that this polyhedron has.
  126. U32 getNumEdges() const { return edgeList.size(); }
  127. ///
  128. Edge* getEdges() const { return edgeList.address(); }
  129. /// @}
  130. /// Conversion to the common polyhedron type.
  131. operator AnyPolyhedron() const;
  132. void buildBox( const MatrixF& mat, const Box3F& box, bool invertNormals = false )
  133. {
  134. pointList.setSize( 8 );
  135. planeList.setSize( 6 );
  136. edgeList.setSize( 12 );
  137. buildBoxData( *this, mat, box, invertNormals );
  138. }
  139. /// Build a polyhedron from the given set of planes.
  140. void buildFromPlanes( const PlaneSetF& planes );
  141. };
  142. /// Polyhedron data stored as raw points with memory
  143. /// being managed externally.
  144. struct PolyhedronUnmanagedVectorData : public PolyhedronData
  145. {
  146. typedef UnmanagedVector< PlaneF > PlaneListType;
  147. typedef UnmanagedVector< Point3F > PointListType;
  148. typedef UnmanagedVector< Edge > EdgeListType;
  149. protected:
  150. /// List of planes. Note that by default, the normals facing *inwards*.
  151. PlaneListType planeList;
  152. /// List of vertices.
  153. PointListType pointList;
  154. /// List of edges.
  155. EdgeListType edgeList;
  156. public:
  157. /// @name Accessors
  158. /// @{
  159. /// Return the number of planes that make up this polyhedron.
  160. U32 getNumPlanes() const { return planeList.size(); }
  161. /// Return the planes that make up the polyhedron.
  162. /// @note The normals of these planes are facing *inwards*.
  163. const PlaneF* getPlanes() const { return planeList.address(); }
  164. PlaneF* getPlanes() { return planeList.address(); }
  165. /// Return the number of points that this polyhedron has.
  166. U32 getNumPoints() const { return pointList.size(); }
  167. ///
  168. const Point3F* getPoints() const { return pointList.address(); }
  169. Point3F* getPoints() { return pointList.address(); }
  170. /// Return the number of edges that this polyhedron has.
  171. U32 getNumEdges() const { return edgeList.size(); }
  172. ///
  173. const Edge* getEdges() const { return edgeList.address(); }
  174. Edge* getEdges() { return edgeList.address(); }
  175. /// @}
  176. };
  177. /// Polyhedron data stored in fixed size arrays.
  178. template< S32 NUM_PLANES, S32 NUM_POINTS, S32 NUM_EDGES >
  179. struct PolyhedronFixedVectorData : public PolyhedronData
  180. {
  181. typedef FixedSizeVector< PlaneF, NUM_PLANES > PlaneListType;
  182. typedef FixedSizeVector< Point3F, NUM_POINTS > PointListType;
  183. typedef FixedSizeVector< Edge, NUM_EDGES > EdgeListType;
  184. protected:
  185. /// List of planes. Note that by default, the normals facing *inwards*.
  186. PlaneListType planeList;
  187. /// List of vertices.
  188. PointListType pointList;
  189. /// List of edges.
  190. EdgeListType edgeList;
  191. public:
  192. /// @name Accessors
  193. /// @{
  194. /// Return the number of planes that make up this polyhedron.
  195. U32 getNumPlanes() const { return planeList.size(); }
  196. /// Return the planes that make up the polyhedron.
  197. /// @note The normals of these planes are facing *inwards*.
  198. PlaneF* getPlanes() const { return planeList.address(); }
  199. /// Return the number of points that this polyhedron has.
  200. U32 getNumPoints() const { return pointList.size(); }
  201. ///
  202. Point3F* getPoints() const { return pointList.address(); }
  203. /// Return the number of edges that this polyhedron has.
  204. U32 getNumEdges() const { return edgeList.size(); }
  205. ///
  206. Edge* getEdges() const { return edgeList.address(); }
  207. /// @}
  208. /// Conversion to the common polyhedron type.
  209. operator AnyPolyhedron() const;
  210. };
  211. /// A polyhedron.
  212. ///
  213. /// Polyhedrons are stored as both sets of planes as well sets of edges and vertices (basically
  214. /// a winged-edge format).
  215. ///
  216. /// Polyhedrons must be convex.
  217. ///
  218. /// @note The default orientation for the plane normals of a polyhedron is *inwards*.
  219. template< typename Base = PolyhedronVectorData >
  220. struct PolyhedronImpl : public Base
  221. {
  222. typedef typename Base::Edge Edge;
  223. typedef typename Base::PlaneListType PlaneListType;
  224. typedef typename Base::PointListType PointListType;
  225. typedef typename Base::EdgeListType EdgeListType;
  226. /// Construct an empty polyhedron.
  227. PolyhedronImpl() {}
  228. /// Construct a polyhedron described by the given planes and edges.
  229. PolyhedronImpl( PlaneListType planes, PointListType points, EdgeListType edges )
  230. {
  231. this->planeList = planes;
  232. this->pointList = points;
  233. this->edgeList = edges;
  234. }
  235. /// Return the AABB around the polyhedron.
  236. Box3F getBounds() const
  237. {
  238. return Box3F::aroundPoints( this->getPoints(), this->getNumPoints() );
  239. }
  240. /// Return the median point of all points defined on the polyhedron.
  241. Point3F getCenterPoint() const;
  242. /// @name Transform
  243. /// @{
  244. /// Transform the polyhedron using the given transform matrix and scale.
  245. void transform( const MatrixF& matrix, const Point3F& scale = Point3F::One );
  246. /// @}
  247. /// @name Containment
  248. /// @{
  249. /// @see PlaneSet::isContained(const Point3F&,F32)
  250. bool isContained( const Point3F& point, F32 epsilon = 0.f ) const
  251. {
  252. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( point, epsilon );
  253. }
  254. /// @see PlaneSet::isContained(const Point3F*,U32)
  255. bool isContained( const Point3F* points, U32 numPoints ) const
  256. {
  257. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( points, numPoints );
  258. }
  259. /// @see PlaneSet::isContained(const Box3F&)
  260. bool isContained( const Box3F& aabb ) const
  261. {
  262. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( aabb );
  263. }
  264. /// @see PlaneSet::isContained(const SphereF&)
  265. bool isContained( const SphereF& sphere ) const
  266. {
  267. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( sphere );
  268. }
  269. /// @see PlaneSet::isContained(const OrientedBox3F&)
  270. bool isContained( const OrientedBox3F& obb ) const
  271. {
  272. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).isContained( obb );
  273. }
  274. /// @}
  275. /// @name Intersection
  276. /// All of these intersection methods are approximate in that they can produce
  277. /// false positives on GeometryIntersecting. For precise testing, use Intersector.
  278. /// @{
  279. /// @see PlaneSet::testPotentialIntersection(const Box3F&)
  280. OverlapTestResult testPotentialIntersection( const Box3F& aabb ) const
  281. {
  282. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( aabb );
  283. }
  284. /// @see PlaneSet::testPotentialIntersection(const SphereF&)
  285. OverlapTestResult testPotentialIntersection( const SphereF& sphere ) const
  286. {
  287. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( sphere );
  288. }
  289. /// @see PlaneSet::testPotentialIntersection(const OrientedBox3F&)
  290. OverlapTestResult testPotentialIntersection( const OrientedBox3F& obb ) const
  291. {
  292. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPotentialIntersection( obb );
  293. }
  294. /// @see PlaneSet::testPlanes
  295. U32 testPlanes( const Box3F& bounds, U32 planeMask = 0xFFFFFFFF, F32 expand = 0.0f ) const
  296. {
  297. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).testPlanes( bounds, planeMask, expand );
  298. }
  299. /// @}
  300. /// @name Clipping
  301. /// Functionality to clip other geometries against the polyhedron.
  302. /// @{
  303. /// @see PlaneSet::clipSegment
  304. bool clipSegment( Point3F& pnt0, Point3F& pnt1 ) const
  305. {
  306. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).clipSegment( pnt0, pnt1 );
  307. }
  308. /// @see PlaneSet::clipPolygon
  309. U32 clipPolygon( const Point3F* inVertices, U32 inNumVertices, Point3F* outVertices, U32 maxOutVertices ) const
  310. {
  311. return PlaneSetF( this->getPlanes(), this->getNumPlanes() ).clipPolygon( inVertices, inNumVertices, outVertices, maxOutVertices );
  312. }
  313. /// @}
  314. /// @name Construction
  315. /// Operations for constructing solids and polygons through boolean operations involving
  316. /// the polyhedron.
  317. /// @{
  318. /// Build the intersection of this polyhedron with the given plane. The result is a
  319. /// polygon.
  320. ///
  321. /// @param plane Plane to intersect the polyhedron with.
  322. /// @param outPoints (out) Array where the resulting polygon points are stored. A safe size is to
  323. /// just allocate as many points as there are edges in the polyhedron. If you know the maximum
  324. /// number of vertices that can result from the intersection (for example, 4 for a box), then
  325. /// it is ok to only allocate that much.
  326. /// @param maxOutPoints Number of points that can be stored in @a outPoints. If insufficient, the
  327. /// return value will be 0.
  328. ///
  329. /// @return The number of points written to @a outPoints. If there is no intersection between the
  330. /// given plane and the polyhedron, this will be zero.
  331. ///
  332. /// @note The resulting points will be ordered to form a proper polygon but there is no guarantee
  333. /// on which direction the ordering is in compared to the plane.
  334. U32 constructIntersection( const PlaneF& plane, Point3F* outPoints, U32 maxOutPoints ) const;
  335. /// @}
  336. /// @name Extraction
  337. /// @{
  338. /// Extract the polygon for the given plane.
  339. ///
  340. /// The resulting indices will be CW ordered if the plane normals on the polyhedron are facing
  341. /// inwards and CCW ordered otherwise.
  342. ///
  343. /// @param plane Index of the plane on the polyhedron.
  344. /// @param outIndices Array where the resulting vertex indices will be stored. Must have
  345. /// enough room. If you don't know the exact size that you need, just allocate one index
  346. /// for any point in the mesh.
  347. /// @param maxOutIndices The number of indices that can be stored in @a outIndices. If insufficient,
  348. /// the return value will be 0.
  349. ///
  350. /// @return Number of indices written to @a outIndices.
  351. ///
  352. /// @note This method relies on correct CW ordering of edges with respect to face[0].
  353. template< typename IndexType >
  354. U32 extractFace( U32 plane, IndexType* outIndices, U32 maxOutIndices ) const;
  355. /// @}
  356. protected:
  357. template< typename P >
  358. OverlapTestResult _testOverlap( const P& bounds ) const;
  359. };
  360. /// Default polyhedron type.
  361. typedef PolyhedronImpl<> Polyhedron;
  362. //-----------------------------------------------------------------------------
  363. inline PolyhedronVectorData::operator AnyPolyhedron() const
  364. {
  365. return AnyPolyhedron(
  366. AnyPolyhedron::PlaneListType( getPlanes(), getNumPlanes() ),
  367. AnyPolyhedron::PointListType( getPoints(), getNumPoints() ),
  368. AnyPolyhedron::EdgeListType( getEdges(), getNumEdges() )
  369. );
  370. }
  371. //-----------------------------------------------------------------------------
  372. template< S32 NUM_PLANES, S32 NUM_POINTS, S32 NUM_EDGES >
  373. inline PolyhedronFixedVectorData< NUM_PLANES, NUM_POINTS, NUM_EDGES >::operator AnyPolyhedron() const
  374. {
  375. return AnyPolyhedron(
  376. AnyPolyhedron::PlaneListType( getPlanes(), getNumPlanes() ),
  377. AnyPolyhedron::PointListType( getPoints(), getNumPoints() ),
  378. AnyPolyhedron::EdgeListType( getEdges(), getNumEdges() )
  379. );
  380. }
  381. #endif // !_MPOLYHEDRON_H_