bullet: Update to current svn, r2636
[blender.git] / extern / bullet2 / 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
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