Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/3DPacman_FS18/src/external/bullet/LinearMath/btConvexHull.h @ 12197

Last change on this file since 12197 was 8393, checked in by rgrieder, 14 years ago

Updated Bullet from v2.77 to v2.78.
(I'm not going to make a branch for that since the update from 2.74 to 2.77 hasn't been tested that much either).

You will HAVE to do a complete RECOMPILE! I tested with MSVC and MinGW and they both threw linker errors at me.

  • Property svn:eol-style set to native
File size: 7.3 KB
Line 
1
2/*
3Stan Melax Convex Hull Computation
4Copyright (c) 2008 Stan Melax http://www.melax.com/
5
6This software is provided 'as-is', without any express or implied warranty.
7In no event will the authors be held liable for any damages arising from the use of this software.
8Permission is granted to anyone to use this software for any purpose,
9including commercial applications, and to alter it and redistribute it freely,
10subject to the following restrictions:
11
121. 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.
132. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
143. 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
25typedef btAlignedObjectArray<unsigned int> TUIntArray;
26
27class HullResult
28{
29public:
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
48enum 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
56class HullDesc
57{
58public:
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
108enum HullError
109{
110        QE_OK,            // success!
111        QE_FAIL           // failed.
112};
113
114class 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
126class 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
151class int4
152{
153public:
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
161class PHullResult
162{
163public:
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.
184class HullLibrary
185{
186
187        btAlignedObjectArray<class btHullTriangle*> m_tris;
188
189public:
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
198private:
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
Note: See TracBrowser for help on using the repository browser.