Back to index

supertuxkart  0.5+dfsg1
btConvexHull.h
Go to the documentation of this file.
00001 
00002 /*
00003 Stan Melax Convex Hull Computation
00004 Copyright (c) 2008 Stan Melax http://www.melax.com/
00005 
00006 This software is provided 'as-is', without any express or implied warranty.
00007 In no event will the authors be held liable for any damages arising from the use of this software.
00008 Permission is granted to anyone to use this software for any purpose, 
00009 including commercial applications, and to alter it and redistribute it freely, 
00010 subject to the following restrictions:
00011 
00012 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.
00013 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
00014 3. This notice may not be removed or altered from any source distribution.
00015 */
00016 
00018 
00019 #ifndef CD_HULL_H
00020 #define CD_HULL_H
00021 
00022 #include "LinearMath/btVector3.h"
00023 #include "LinearMath/btAlignedObjectArray.h"
00024 
00025 typedef btAlignedObjectArray<unsigned int> TUIntArray;
00026 
00027 class HullResult
00028 {
00029 public:
00030        HullResult(void)
00031        {
00032               mPolygons = true;
00033               mNumOutputVertices = 0;
00034               mNumFaces = 0;
00035               mNumIndices = 0;
00036        }
00037        bool                    mPolygons;                  // true if indices represents polygons, false indices are triangles
00038        unsigned int            mNumOutputVertices;         // number of vertices in the output hull
00039        btAlignedObjectArray<btVector3>    m_OutputVertices;            // array of vertices
00040        unsigned int            mNumFaces;                  // the number of faces produced
00041        unsigned int            mNumIndices;                // the total number of indices
00042        btAlignedObjectArray<unsigned int>    m_Indices;                   // pointer to indices.
00043 
00044 // If triangles, then indices are array indexes into the vertex list.
00045 // If polygons, indices are in the form (number of points in face) (p1, p2, p3, ..) etc..
00046 };
00047 
00048 enum HullFlag
00049 {
00050        QF_TRIANGLES         = (1<<0),             // report results as triangles, not polygons.
00051        QF_REVERSE_ORDER     = (1<<1),             // reverse order of the triangle indices.
00052        QF_DEFAULT           = QF_TRIANGLES
00053 };
00054 
00055 
00056 class HullDesc
00057 {
00058 public:
00059        HullDesc(void)
00060        {
00061               mFlags          = QF_DEFAULT;
00062               mVcount         = 0;
00063               mVertices       = 0;
00064               mVertexStride   = sizeof(btVector3);
00065               mNormalEpsilon  = 0.001f;
00066               mMaxVertices  = 4096; // maximum number of points to be considered for a convex hull.
00067               mMaxFaces     = 4096;
00068        };
00069 
00070        HullDesc(HullFlag flag,
00071                unsigned int vcount,
00072                const btVector3 *vertices,
00073                unsigned int stride = sizeof(btVector3))
00074        {
00075               mFlags          = flag;
00076               mVcount         = vcount;
00077               mVertices       = vertices;
00078               mVertexStride   = stride;
00079               mNormalEpsilon  = btScalar(0.001);
00080               mMaxVertices    = 4096;
00081        }
00082 
00083        bool HasHullFlag(HullFlag flag) const
00084        {
00085               if ( mFlags & flag ) return true;
00086               return false;
00087        }
00088 
00089        void SetHullFlag(HullFlag flag)
00090        {
00091               mFlags|=flag;
00092        }
00093 
00094        void ClearHullFlag(HullFlag flag)
00095        {
00096               mFlags&=~flag;
00097        }
00098 
00099        unsigned int      mFlags;           // flags to use when generating the convex hull.
00100        unsigned int      mVcount;          // number of vertices in the input point cloud
00101        const btVector3  *mVertices;        // the array of vertices.
00102        unsigned int      mVertexStride;    // the stride of each vertex, in bytes.
00103        btScalar             mNormalEpsilon;   // the epsilon for removing duplicates.  This is a normalized value, if normalized bit is on.
00104        unsigned int      mMaxVertices;     // maximum number of vertices to be considered for the hull!
00105        unsigned int      mMaxFaces;
00106 };
00107 
00108 enum HullError
00109 {
00110        QE_OK,            // success!
00111        QE_FAIL           // failed.
00112 };
00113 
00114 class btPlane
00115 {
00116        public:
00117        btVector3     normal;
00118        btScalar      dist;   // distance below origin - the D from plane equasion Ax+By+Cz+D=0
00119                      btPlane(const btVector3 &n,btScalar d):normal(n),dist(d){}
00120                      btPlane():normal(),dist(0){}
00121        
00122 };
00123 
00124 
00125 
00126 class ConvexH 
00127 {
00128   public:
00129        class HalfEdge
00130        {
00131          public:
00132               short ea;         // the other half of the edge (index into edges list)
00133               unsigned char v;  // the vertex at the start of this edge (index into vertices list)
00134               unsigned char p;  // the facet on which this edge lies (index into facets list)
00135               HalfEdge(){}
00136               HalfEdge(short _ea,unsigned char _v, unsigned char _p):ea(_ea),v(_v),p(_p){}
00137        };
00138        ConvexH()
00139        {
00140               int i;
00141               i=0;
00142        }
00143        ~ConvexH()
00144        {
00145               int i;
00146               i=0;
00147        }
00148        btAlignedObjectArray<btVector3> vertices;
00149        btAlignedObjectArray<HalfEdge> edges;
00150        btAlignedObjectArray<btPlane>  facets;
00151        ConvexH(int vertices_size,int edges_size,int facets_size);
00152 };
00153 
00154 
00155 class int4
00156 {
00157 public:
00158        int x,y,z,w;
00159        int4(){};
00160        int4(int _x,int _y, int _z,int _w){x=_x;y=_y;z=_z;w=_w;}
00161        const int& operator[](int i) const {return (&x)[i];}
00162        int& operator[](int i) {return (&x)[i];}
00163 };
00164 
00165 class PHullResult
00166 {
00167 public:
00168 
00169        PHullResult(void)
00170        {
00171               mVcount = 0;
00172               mIndexCount = 0;
00173               mFaceCount = 0;
00174               mVertices = 0;
00175        }
00176 
00177        unsigned int mVcount;
00178        unsigned int mIndexCount;
00179        unsigned int mFaceCount;
00180        btVector3*   mVertices;
00181        TUIntArray m_Indices;
00182 };
00183 
00184 
00185 
00186 class HullLibrary
00187 {
00188 
00189        btAlignedObjectArray<class Tri*> m_tris;
00190 
00191 public:
00192 
00193        HullError CreateConvexHull(const HullDesc& desc, // describes the input request
00194                                HullResult&     result);        // contains the resulst
00195        HullError ReleaseResult(HullResult &result); // release memory allocated for this result, we are done with it.
00196 
00197 private:
00198 
00199        bool ComputeHull(unsigned int vcount,const btVector3 *vertices,PHullResult &result,unsigned int vlimit);
00200 
00201        class Tri*    allocateTriangle(int a,int b,int c);
00202        void   deAllocateTriangle(Tri*);
00203        void b2bfix(Tri* s,Tri*t);
00204 
00205        void removeb2b(Tri* s,Tri*t);
00206 
00207        void checkit(Tri *t);
00208 
00209        Tri* extrudable(btScalar epsilon);
00210 
00211        int calchull(btVector3 *verts,int verts_count, TUIntArray& tris_out, int &tris_count,int vlimit);
00212 
00213        int calchullgen(btVector3 *verts,int verts_count, int vlimit);
00214 
00215        int4 FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectArray<int> &allow);
00216 
00217        class ConvexH* ConvexHCrop(ConvexH& convex,const btPlane& slice);
00218 
00219        void extrude(class Tri* t0,int v);
00220 
00221        ConvexH* test_cube();
00222 
00223        //BringOutYourDead (John Ratcliff): When you create a convex hull you hand it a large input set of vertices forming a 'point cloud'. 
00224        //After the hull is generated it give you back a set of polygon faces which index the *original* point cloud.
00225        //The thing is, often times, there are many 'dead vertices' in the point cloud that are on longer referenced by the hull.
00226        //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.
00227        void BringOutYourDead(const btVector3* verts,unsigned int vcount, btVector3* overts,unsigned int &ocount,unsigned int* indices,unsigned indexcount);
00228 
00229        bool CleanupVertices(unsigned int svcount,
00230                           const btVector3* svertices,
00231                           unsigned int stride,
00232                           unsigned int &vcount, // output number of vertices
00233                           btVector3* vertices, // location to store the results.
00234                           btScalar  normalepsilon,
00235                           btVector3& scale);
00236 };
00237 
00238 
00239 #endif
00240