dali-physics/third-party/bullet3/src/LinearMath/btConvexHull.h

   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 class HullDesc
  56 {
  57 public:
  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
  82         bool HasHullFlag(HullFlag flag) const
  83         {
  84                 if (mFlags & flag) return true;
  85                 return false;
  86         }
  87
  88         void SetHullFlag(HullFlag flag)
  89         {
  90                 mFlags |= flag;
  91         }
  92
  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
 118         btPlane(const btVector3& n, btScalar d) : normal(n), dist(d) {}
 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)
 131                 HalfEdge() {}
 132                 HalfEdge(short _ea, unsigned char _v, unsigned char _p) : ea(_ea), v(_v), p(_p) {}
 133         };
 134         ConvexH()
 135         {
 136         }
 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;
 150         int4(){};
 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:
 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