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: HullResult(void)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 class HullDesc 56 { 57 public: HullDesc(void)58 HullDesc(void) 59 { 60 mFlags = QF_DEFAULT; 61 mVcount = 0; 62 mVertices = 0; 63 mVertexStride = sizeof(btVector3); 64 mNormalEpsilon = 0.001f; 65 mMaxVertices = 4096; // maximum number of points to be considered for a convex hull. 66 mMaxFaces = 4096; 67 }; 68 69 HullDesc(HullFlag flag, 70 unsigned int vcount, 71 const btVector3* vertices, 72 unsigned int stride = sizeof(btVector3)) 73 { 74 mFlags = flag; 75 mVcount = vcount; 76 mVertices = vertices; 77 mVertexStride = stride; 78 mNormalEpsilon = btScalar(0.001); 79 mMaxVertices = 4096; 80 } 81 HasHullFlag(HullFlag flag)82 bool HasHullFlag(HullFlag flag) const 83 { 84 if (mFlags & flag) return true; 85 return false; 86 } 87 SetHullFlag(HullFlag flag)88 void SetHullFlag(HullFlag flag) 89 { 90 mFlags |= flag; 91 } 92 ClearHullFlag(HullFlag flag)93 void ClearHullFlag(HullFlag flag) 94 { 95 mFlags &= ~flag; 96 } 97 98 unsigned int mFlags; // flags to use when generating the convex hull. 99 unsigned int mVcount; // number of vertices in the input point cloud 100 const btVector3* mVertices; // the array of vertices. 101 unsigned int mVertexStride; // the stride of each vertex, in bytes. 102 btScalar mNormalEpsilon; // the epsilon for removing duplicates. This is a normalized value, if normalized bit is on. 103 unsigned int mMaxVertices; // maximum number of vertices to be considered for the hull! 104 unsigned int mMaxFaces; 105 }; 106 107 enum HullError 108 { 109 QE_OK, // success! 110 QE_FAIL // failed. 111 }; 112 113 class btPlane 114 { 115 public: 116 btVector3 normal; 117 btScalar dist; // distance below origin - the D from plane equasion Ax+By+Cz+D=0 btPlane(const btVector3 & n,btScalar d)118 btPlane(const btVector3& n, btScalar d) : normal(n), dist(d) {} btPlane()119 btPlane() : normal(), dist(0) {} 120 }; 121 122 class ConvexH 123 { 124 public: 125 class HalfEdge 126 { 127 public: 128 short ea; // the other half of the edge (index into edges list) 129 unsigned char v; // the vertex at the start of this edge (index into vertices list) 130 unsigned char p; // the facet on which this edge lies (index into facets list) HalfEdge()131 HalfEdge() {} HalfEdge(short _ea,unsigned char _v,unsigned char _p)132 HalfEdge(short _ea, unsigned char _v, unsigned char _p) : ea(_ea), v(_v), p(_p) {} 133 }; ConvexH()134 ConvexH() 135 { 136 } ~ConvexH()137 ~ConvexH() 138 { 139 } 140 btAlignedObjectArray<btVector3> vertices; 141 btAlignedObjectArray<HalfEdge> edges; 142 btAlignedObjectArray<btPlane> facets; 143 ConvexH(int vertices_size, int edges_size, int facets_size); 144 }; 145 146 class int4 147 { 148 public: 149 int x, y, z, w; int4()150 int4(){}; int4(int _x,int _y,int _z,int _w)151 int4(int _x, int _y, int _z, int _w) 152 { 153 x = _x; 154 y = _y; 155 z = _z; 156 w = _w; 157 } 158 const int& operator[](int i) const { return (&x)[i]; } 159 int& operator[](int i) { return (&x)[i]; } 160 }; 161 162 class PHullResult 163 { 164 public: PHullResult(void)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 ///The HullLibrary class can create a convex hull from a collection of vertices, using the ComputeHull method. 181 ///The btShapeHull class uses this HullLibrary to create a approximate convex mesh given a general (non-polyhedral) convex shape. 182 class HullLibrary 183 { 184 btAlignedObjectArray<class btHullTriangle*> m_tris; 185 186 public: 187 btAlignedObjectArray<int> m_vertexIndexMapping; 188 189 HullError CreateConvexHull(const HullDesc& desc, // describes the input request 190 HullResult& result); // contains the resulst 191 HullError ReleaseResult(HullResult& result); // release memory allocated for this result, we are done with it. 192 193 private: 194 bool ComputeHull(unsigned int vcount, const btVector3* vertices, PHullResult& result, unsigned int vlimit); 195 196 class btHullTriangle* allocateTriangle(int a, int b, int c); 197 void deAllocateTriangle(btHullTriangle*); 198 void b2bfix(btHullTriangle* s, btHullTriangle* t); 199 200 void removeb2b(btHullTriangle* s, btHullTriangle* t); 201 202 void checkit(btHullTriangle* t); 203 204 btHullTriangle* extrudable(btScalar epsilon); 205 206 int calchull(btVector3* verts, int verts_count, TUIntArray& tris_out, int& tris_count, int vlimit); 207 208 int calchullgen(btVector3* verts, int verts_count, int vlimit); 209 210 int4 FindSimplex(btVector3* verts, int verts_count, btAlignedObjectArray<int>& allow); 211 212 class ConvexH* ConvexHCrop(ConvexH& convex, const btPlane& slice); 213 214 void extrude(class btHullTriangle* t0, int v); 215 216 ConvexH* test_cube(); 217 218 //BringOutYourDead (John Ratcliff): When you create a convex hull you hand it a large input set of vertices forming a 'point cloud'. 219 //After the hull is generated it give you back a set of polygon faces which index the *original* point cloud. 220 //The thing is, often times, there are many 'dead vertices' in the point cloud that are on longer referenced by the hull. 221 //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. 222 void BringOutYourDead(const btVector3* verts, unsigned int vcount, btVector3* overts, unsigned int& ocount, unsigned int* indices, unsigned indexcount); 223 224 bool CleanupVertices(unsigned int svcount, 225 const btVector3* svertices, 226 unsigned int stride, 227 unsigned int& vcount, // output number of vertices 228 btVector3* vertices, // location to store the results. 229 btScalar normalepsilon, 230 btVector3& scale); 231 }; 232 233 #endif //BT_CD_HULL_H 234