Home | History | Annotate | Download | only in LinearMath
      1 
      2 /*
      3 Stan Melax Convex Hull Computation
      4 Copyright (c) 2008 Stan Melax http://www.melax.com/
      5 
      6 This software is provided 'as-is', without any express or implied warranty.
      7 In no event will the authors be held liable for any damages arising from the use of this software.
      8 Permission is granted to anyone to use this software for any purpose,
      9 including commercial applications, and to alter it and redistribute it freely,
     10 subject to the following restrictions:
     11 
     12 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.
     13 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
     14 3. This notice may not be removed or altered from any source distribution.
     15 */
     16 
     17 ///includes modifications/improvements by John Ratcliff, see BringOutYourDead below.
     18 
     19 #ifndef BT_CD_HULL_H
     20 #define BT_CD_HULL_H
     21 
     22 #include "btVector3.h"
     23 #include "btAlignedObjectArray.h"
     24 
     25 typedef btAlignedObjectArray<unsigned int> TUIntArray;
     26 
     27 class HullResult
     28 {
     29 public:
     30 	HullResult(void)
     31 	{
     32 		mPolygons = true;
     33 		mNumOutputVertices = 0;
     34 		mNumFaces = 0;
     35 		mNumIndices = 0;
     36 	}
     37 	bool                    mPolygons;                  // true if indices represents polygons, false indices are triangles
     38 	unsigned int            mNumOutputVertices;         // number of vertices in the output hull
     39 	btAlignedObjectArray<btVector3>	m_OutputVertices;            // array of vertices
     40 	unsigned int            mNumFaces;                  // the number of faces produced
     41 	unsigned int            mNumIndices;                // the total number of indices
     42 	btAlignedObjectArray<unsigned int>    m_Indices;                   // pointer to indices.
     43 
     44 // If triangles, then indices are array indexes into the vertex list.
     45 // If polygons, indices are in the form (number of points in face) (p1, p2, p3, ..) etc..
     46 };
     47 
     48 enum HullFlag
     49 {
     50 	QF_TRIANGLES         = (1<<0),             // report results as triangles, not polygons.
     51 	QF_REVERSE_ORDER     = (1<<1),             // reverse order of the triangle indices.
     52 	QF_DEFAULT           = QF_TRIANGLES
     53 };
     54 
     55 
     56 class HullDesc
     57 {
     58 public:
     59 	HullDesc(void)
     60 	{
     61 		mFlags          = QF_DEFAULT;
     62 		mVcount         = 0;
     63 		mVertices       = 0;
     64 		mVertexStride   = sizeof(btVector3);
     65 		mNormalEpsilon  = 0.001f;
     66 		mMaxVertices	= 4096; // maximum number of points to be considered for a convex hull.
     67 		mMaxFaces	= 4096;
     68 	};
     69 
     70 	HullDesc(HullFlag flag,
     71 		 unsigned int vcount,
     72 		 const btVector3 *vertices,
     73 		 unsigned int stride = sizeof(btVector3))
     74 	{
     75 		mFlags          = flag;
     76 		mVcount         = vcount;
     77 		mVertices       = vertices;
     78 		mVertexStride   = stride;
     79 		mNormalEpsilon  = btScalar(0.001);
     80 		mMaxVertices    = 4096;
     81 	}
     82 
     83 	bool HasHullFlag(HullFlag flag) const
     84 	{
     85 		if ( mFlags & flag ) return true;
     86 		return false;
     87 	}
     88 
     89 	void SetHullFlag(HullFlag flag)
     90 	{
     91 		mFlags|=flag;
     92 	}
     93 
     94 	void ClearHullFlag(HullFlag flag)
     95 	{
     96 		mFlags&=~flag;
     97 	}
     98 
     99 	unsigned int      mFlags;           // flags to use when generating the convex hull.
    100 	unsigned int      mVcount;          // number of vertices in the input point cloud
    101 	const btVector3  *mVertices;        // the array of vertices.
    102 	unsigned int      mVertexStride;    // the stride of each vertex, in bytes.
    103 	btScalar             mNormalEpsilon;   // the epsilon for removing duplicates.  This is a normalized value, if normalized bit is on.
    104 	unsigned int      mMaxVertices;     // maximum number of vertices to be considered for the hull!
    105 	unsigned int      mMaxFaces;
    106 };
    107 
    108 enum HullError
    109 {
    110 	QE_OK,            // success!
    111 	QE_FAIL           // failed.
    112 };
    113 
    114 class btPlane
    115 {
    116 	public:
    117 	btVector3	normal;
    118 	btScalar	dist;   // distance below origin - the D from plane equasion Ax+By+Cz+D=0
    119 			btPlane(const btVector3 &n,btScalar d):normal(n),dist(d){}
    120 			btPlane():normal(),dist(0){}
    121 
    122 };
    123 
    124 
    125 
    126 class ConvexH
    127 {
    128   public:
    129 	class HalfEdge
    130 	{
    131 	  public:
    132 		short ea;         // the other half of the edge (index into edges list)
    133 		unsigned char v;  // the vertex at the start of this edge (index into vertices list)
    134 		unsigned char p;  // the facet on which this edge lies (index into facets list)
    135 		HalfEdge(){}
    136 		HalfEdge(short _ea,unsigned char _v, unsigned char _p):ea(_ea),v(_v),p(_p){}
    137 	};
    138 	ConvexH()
    139 	{
    140 	}
    141 	~ConvexH()
    142 	{
    143 	}
    144 	btAlignedObjectArray<btVector3> vertices;
    145 	btAlignedObjectArray<HalfEdge> edges;
    146 	btAlignedObjectArray<btPlane>  facets;
    147 	ConvexH(int vertices_size,int edges_size,int facets_size);
    148 };
    149 
    150 
    151 class int4
    152 {
    153 public:
    154 	int x,y,z,w;
    155 	int4(){};
    156 	int4(int _x,int _y, int _z,int _w){x=_x;y=_y;z=_z;w=_w;}
    157 	const int& operator[](int i) const {return (&x)[i];}
    158 	int& operator[](int i) {return (&x)[i];}
    159 };
    160 
    161 class PHullResult
    162 {
    163 public:
    164 
    165 	PHullResult(void)
    166 	{
    167 		mVcount = 0;
    168 		mIndexCount = 0;
    169 		mFaceCount = 0;
    170 		mVertices = 0;
    171 	}
    172 
    173 	unsigned int mVcount;
    174 	unsigned int mIndexCount;
    175 	unsigned int mFaceCount;
    176 	btVector3*   mVertices;
    177 	TUIntArray m_Indices;
    178 };
    179 
    180 
    181 
    182 ///The HullLibrary class can create a convex hull from a collection of vertices, using the ComputeHull method.
    183 ///The btShapeHull class uses this HullLibrary to create a approximate convex mesh given a general (non-polyhedral) convex shape.
    184 class HullLibrary
    185 {
    186 
    187 	btAlignedObjectArray<class btHullTriangle*> m_tris;
    188 
    189 public:
    190 
    191 	btAlignedObjectArray<int> m_vertexIndexMapping;
    192 
    193 
    194 	HullError CreateConvexHull(const HullDesc& desc, // describes the input request
    195 				   HullResult&     result);        // contains the resulst
    196 	HullError ReleaseResult(HullResult &result); // release memory allocated for this result, we are done with it.
    197 
    198 private:
    199 
    200 	bool ComputeHull(unsigned int vcount,const btVector3 *vertices,PHullResult &result,unsigned int vlimit);
    201 
    202 	class btHullTriangle*	allocateTriangle(int a,int b,int c);
    203 	void	deAllocateTriangle(btHullTriangle*);
    204 	void b2bfix(btHullTriangle* s,btHullTriangle*t);
    205 
    206 	void removeb2b(btHullTriangle* s,btHullTriangle*t);
    207 
    208 	void checkit(btHullTriangle *t);
    209 
    210 	btHullTriangle* extrudable(btScalar epsilon);
    211 
    212 	int calchull(btVector3 *verts,int verts_count, TUIntArray& tris_out, int &tris_count,int vlimit);
    213 
    214 	int calchullgen(btVector3 *verts,int verts_count, int vlimit);
    215 
    216 	int4 FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectArray<int> &allow);
    217 
    218 	class ConvexH* ConvexHCrop(ConvexH& convex,const btPlane& slice);
    219 
    220 	void extrude(class btHullTriangle* t0,int v);
    221 
    222 	ConvexH* test_cube();
    223 
    224 	//BringOutYourDead (John Ratcliff): When you create a convex hull you hand it a large input set of vertices forming a 'point cloud'.
    225 	//After the hull is generated it give you back a set of polygon faces which index the *original* point cloud.
    226 	//The thing is, often times, there are many 'dead vertices' in the point cloud that are on longer referenced by the hull.
    227 	//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.
    228 	void BringOutYourDead(const btVector3* verts,unsigned int vcount, btVector3* overts,unsigned int &ocount,unsigned int* indices,unsigned indexcount);
    229 
    230 	bool CleanupVertices(unsigned int svcount,
    231 			     const btVector3* svertices,
    232 			     unsigned int stride,
    233 			     unsigned int &vcount, // output number of vertices
    234 			     btVector3* vertices, // location to store the results.
    235 			     btScalar  normalepsilon,
    236 			     btVector3& scale);
    237 };
    238 
    239 
    240 #endif //BT_CD_HULL_H
    241 
    242