| |
| /* |
| Stan Melax Convex Hull Computation |
| Copyright (c) 2008 Stan Melax http://www.melax.com/ |
| |
| This software is provided 'as-is', without any express or implied warranty. |
| In no event will the authors be held liable for any damages arising from the use of this software. |
| Permission is granted to anyone to use this software for any purpose, |
| including commercial applications, and to alter it and redistribute it freely, |
| subject to the following restrictions: |
| |
| 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. |
| 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. |
| 3. This notice may not be removed or altered from any source distribution. |
| */ |
| |
| ///includes modifications/improvements by John Ratcliff, see BringOutYourDead below. |
| |
| #ifndef CD_HULL_H |
| #define CD_HULL_H |
| |
| #include "LinearMath/btVector3.h" |
| #include "LinearMath/btAlignedObjectArray.h" |
| |
| typedef btAlignedObjectArray<unsigned int> TUIntArray; |
| |
| class HullResult |
| { |
| public: |
| HullResult(void) |
| { |
| mPolygons = true; |
| mNumOutputVertices = 0; |
| mNumFaces = 0; |
| mNumIndices = 0; |
| } |
| bool mPolygons; // true if indices represents polygons, false indices are triangles |
| unsigned int mNumOutputVertices; // number of vertices in the output hull |
| btAlignedObjectArray<btVector3> m_OutputVertices; // array of vertices |
| unsigned int mNumFaces; // the number of faces produced |
| unsigned int mNumIndices; // the total number of indices |
| btAlignedObjectArray<unsigned int> m_Indices; // pointer to indices. |
| |
| // If triangles, then indices are array indexes into the vertex list. |
| // If polygons, indices are in the form (number of points in face) (p1, p2, p3, ..) etc.. |
| }; |
| |
| enum HullFlag |
| { |
| QF_TRIANGLES = (1<<0), // report results as triangles, not polygons. |
| QF_REVERSE_ORDER = (1<<1), // reverse order of the triangle indices. |
| QF_DEFAULT = QF_TRIANGLES |
| }; |
| |
| |
| class HullDesc |
| { |
| public: |
| HullDesc(void) |
| { |
| mFlags = QF_DEFAULT; |
| mVcount = 0; |
| mVertices = 0; |
| mVertexStride = sizeof(btVector3); |
| mNormalEpsilon = 0.001f; |
| mMaxVertices = 4096; // maximum number of points to be considered for a convex hull. |
| mMaxFaces = 4096; |
| }; |
| |
| HullDesc(HullFlag flag, |
| unsigned int vcount, |
| const btVector3 *vertices, |
| unsigned int stride = sizeof(btVector3)) |
| { |
| mFlags = flag; |
| mVcount = vcount; |
| mVertices = vertices; |
| mVertexStride = stride; |
| mNormalEpsilon = btScalar(0.001); |
| mMaxVertices = 4096; |
| } |
| |
| bool HasHullFlag(HullFlag flag) const |
| { |
| if ( mFlags & flag ) return true; |
| return false; |
| } |
| |
| void SetHullFlag(HullFlag flag) |
| { |
| mFlags|=flag; |
| } |
| |
| void ClearHullFlag(HullFlag flag) |
| { |
| mFlags&=~flag; |
| } |
| |
| unsigned int mFlags; // flags to use when generating the convex hull. |
| unsigned int mVcount; // number of vertices in the input point cloud |
| const btVector3 *mVertices; // the array of vertices. |
| unsigned int mVertexStride; // the stride of each vertex, in bytes. |
| btScalar mNormalEpsilon; // the epsilon for removing duplicates. This is a normalized value, if normalized bit is on. |
| unsigned int mMaxVertices; // maximum number of vertices to be considered for the hull! |
| unsigned int mMaxFaces; |
| }; |
| |
| enum HullError |
| { |
| QE_OK, // success! |
| QE_FAIL // failed. |
| }; |
| |
| class btPlane |
| { |
| public: |
| btVector3 normal; |
| btScalar dist; // distance below origin - the D from plane equasion Ax+By+Cz+D=0 |
| btPlane(const btVector3 &n,btScalar d):normal(n),dist(d){} |
| btPlane():normal(),dist(0){} |
| |
| }; |
| |
| |
| |
| class ConvexH |
| { |
| public: |
| class HalfEdge |
| { |
| public: |
| short ea; // the other half of the edge (index into edges list) |
| unsigned char v; // the vertex at the start of this edge (index into vertices list) |
| unsigned char p; // the facet on which this edge lies (index into facets list) |
| HalfEdge(){} |
| HalfEdge(short _ea,unsigned char _v, unsigned char _p):ea(_ea),v(_v),p(_p){} |
| }; |
| ConvexH() |
| { |
| } |
| ~ConvexH() |
| { |
| } |
| btAlignedObjectArray<btVector3> vertices; |
| btAlignedObjectArray<HalfEdge> edges; |
| btAlignedObjectArray<btPlane> facets; |
| ConvexH(int vertices_size,int edges_size,int facets_size); |
| }; |
| |
| |
| class int4 |
| { |
| public: |
| int x,y,z,w; |
| int4(){}; |
| int4(int _x,int _y, int _z,int _w){x=_x;y=_y;z=_z;w=_w;} |
| const int& operator[](int i) const {return (&x)[i];} |
| int& operator[](int i) {return (&x)[i];} |
| }; |
| |
| class PHullResult |
| { |
| public: |
| |
| PHullResult(void) |
| { |
| mVcount = 0; |
| mIndexCount = 0; |
| mFaceCount = 0; |
| mVertices = 0; |
| } |
| |
| unsigned int mVcount; |
| unsigned int mIndexCount; |
| unsigned int mFaceCount; |
| btVector3* mVertices; |
| TUIntArray m_Indices; |
| }; |
| |
| |
| |
| ///The HullLibrary class can create a convex hull from a collection of vertices, using the ComputeHull method. |
| ///The btShapeHull class uses this HullLibrary to create a approximate convex mesh given a general (non-polyhedral) convex shape. |
| class HullLibrary |
| { |
| |
| btAlignedObjectArray<class btHullTriangle*> m_tris; |
| |
| public: |
| |
| btAlignedObjectArray<int> m_vertexIndexMapping; |
| |
| |
| HullError CreateConvexHull(const HullDesc& desc, // describes the input request |
| HullResult& result); // contains the resulst |
| HullError ReleaseResult(HullResult &result); // release memory allocated for this result, we are done with it. |
| |
| private: |
| |
| bool ComputeHull(unsigned int vcount,const btVector3 *vertices,PHullResult &result,unsigned int vlimit); |
| |
| class btHullTriangle* allocateTriangle(int a,int b,int c); |
| void deAllocateTriangle(btHullTriangle*); |
| void b2bfix(btHullTriangle* s,btHullTriangle*t); |
| |
| void removeb2b(btHullTriangle* s,btHullTriangle*t); |
| |
| void checkit(btHullTriangle *t); |
| |
| btHullTriangle* extrudable(btScalar epsilon); |
| |
| int calchull(btVector3 *verts,int verts_count, TUIntArray& tris_out, int &tris_count,int vlimit); |
| |
| int calchullgen(btVector3 *verts,int verts_count, int vlimit); |
| |
| int4 FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectArray<int> &allow); |
| |
| class ConvexH* ConvexHCrop(ConvexH& convex,const btPlane& slice); |
| |
| void extrude(class btHullTriangle* t0,int v); |
| |
| ConvexH* test_cube(); |
| |
| //BringOutYourDead (John Ratcliff): When you create a convex hull you hand it a large input set of vertices forming a 'point cloud'. |
| //After the hull is generated it give you back a set of polygon faces which index the *original* point cloud. |
| //The thing is, often times, there are many 'dead vertices' in the point cloud that are on longer referenced by the hull. |
| //The routine 'BringOutYourDead' find only the referenced vertices, copies them to an new buffer, and re-indexes the hull so that it is a minimal representation. |
| void BringOutYourDead(const btVector3* verts,unsigned int vcount, btVector3* overts,unsigned int &ocount,unsigned int* indices,unsigned indexcount); |
| |
| bool CleanupVertices(unsigned int svcount, |
| const btVector3* svertices, |
| unsigned int stride, |
| unsigned int &vcount, // output number of vertices |
| btVector3* vertices, // location to store the results. |
| btScalar normalepsilon, |
| btVector3& scale); |
| }; |
| |
| |
| #endif |
| |