1 #ifndef CONVEX_DECOMPOSITION_H 2 3 #define CONVEX_DECOMPOSITION_H 4 5 /*---------------------------------------------------------------------- 6 Copyright (c) 2004 Open Dynamics Framework Group 7 www.physicstools.org 8 All rights reserved. 9 10 Redistribution and use in source and binary forms, with or without modification, are permitted provided 11 that the following conditions are met: 12 13 Redistributions of source code must retain the above copyright notice, this list of conditions 14 and the following disclaimer. 15 16 Redistributions in binary form must reproduce the above copyright notice, 17 this list of conditions and the following disclaimer in the documentation 18 and/or other materials provided with the distribution. 19 20 Neither the name of the Open Dynamics Framework Group nor the names of its contributors may 21 be used to endorse or promote products derived from this software without specific prior written permission. 22 23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES, 24 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 25 DISCLAIMED. IN NO EVENT SHALL THE INTEL OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 26 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 27 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER 28 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 -----------------------------------------------------------------------*/ 31 32 // http://codesuppository.blogspot.com 33 // 34 // mailto: jratcliff@infiniplex.net 35 // 36 // http://www.amillionpixels.us 37 // 38 39 #ifdef _WIN32 40 #include <memory.h> //memcpy 41 #endif 42 #include <string.h> 43 #include <stdio.h> 44 #include "LinearMath/btAlignedObjectArray.h" 45 46 extern unsigned int MAXDEPTH; 47 extern float CONCAVE_PERCENT; 48 extern float MERGE_PERCENT; 49 50 typedef btAlignedObjectArray<unsigned int> UintVector; 51 52 namespace ConvexDecomposition 53 { 54 class ConvexResult 55 { 56 public: ConvexResult(void)57 ConvexResult(void) 58 { 59 mHullVcount = 0; 60 mHullVertices = 0; 61 mHullTcount = 0; 62 mHullIndices = 0; 63 } 64 ConvexResult(unsigned int hvcount,const float * hvertices,unsigned int htcount,const unsigned int * hindices)65 ConvexResult(unsigned int hvcount, const float *hvertices, unsigned int htcount, const unsigned int *hindices) 66 { 67 mHullVcount = hvcount; 68 if (mHullVcount) 69 { 70 mHullVertices = new float[mHullVcount * sizeof(float) * 3]; 71 memcpy(mHullVertices, hvertices, sizeof(float) * 3 * mHullVcount); 72 } 73 else 74 { 75 mHullVertices = 0; 76 } 77 78 mHullTcount = htcount; 79 80 if (mHullTcount) 81 { 82 mHullIndices = new unsigned int[sizeof(unsigned int) * mHullTcount * 3]; 83 memcpy(mHullIndices, hindices, sizeof(unsigned int) * mHullTcount * 3); 84 } 85 else 86 { 87 mHullIndices = 0; 88 } 89 } 90 ConvexResult(const ConvexResult & r)91 ConvexResult(const ConvexResult &r) 92 { 93 mHullVcount = r.mHullVcount; 94 if (mHullVcount) 95 { 96 mHullVertices = new float[mHullVcount * sizeof(float) * 3]; 97 memcpy(mHullVertices, r.mHullVertices, sizeof(float) * 3 * mHullVcount); 98 } 99 else 100 { 101 mHullVertices = 0; 102 } 103 mHullTcount = r.mHullTcount; 104 if (mHullTcount) 105 { 106 mHullIndices = new unsigned int[sizeof(unsigned int) * mHullTcount * 3]; 107 memcpy(mHullIndices, r.mHullIndices, sizeof(unsigned int) * mHullTcount * 3); 108 } 109 else 110 { 111 mHullIndices = 0; 112 } 113 } 114 ~ConvexResult(void)115 ~ConvexResult(void) 116 { 117 delete[] mHullVertices; 118 delete[] mHullIndices; 119 } 120 121 // the convex hull. 122 unsigned int mHullVcount; 123 float *mHullVertices; 124 unsigned int mHullTcount; 125 unsigned int *mHullIndices; 126 127 float mHullVolume; // the volume of the convex hull. 128 129 float mOBBSides[3]; // the width, height and breadth of the best fit OBB 130 float mOBBCenter[3]; // the center of the OBB 131 float mOBBOrientation[4]; // the quaternion rotation of the OBB. 132 float mOBBTransform[16]; // the 4x4 transform of the OBB. 133 float mOBBVolume; // the volume of the OBB 134 135 float mSphereRadius; // radius and center of best fit sphere 136 float mSphereCenter[3]; 137 float mSphereVolume; // volume of the best fit sphere 138 }; 139 140 class ConvexDecompInterface 141 { 142 public: ~ConvexDecompInterface()143 virtual ~ConvexDecompInterface(){}; ConvexDebugTri(const float * p1,const float * p2,const float * p3,unsigned int color)144 virtual void ConvexDebugTri(const float *p1, const float *p2, const float *p3, unsigned int color){}; ConvexDebugPoint(const float * p,float dist,unsigned int color)145 virtual void ConvexDebugPoint(const float *p, float dist, unsigned int color){}; ConvexDebugBound(const float * bmin,const float * bmax,unsigned int color)146 virtual void ConvexDebugBound(const float *bmin, const float *bmax, unsigned int color){}; ConvexDebugOBB(const float * sides,const float * matrix,unsigned int color)147 virtual void ConvexDebugOBB(const float *sides, const float *matrix, unsigned int color){}; 148 149 virtual void ConvexDecompResult(ConvexResult &result) = 0; 150 }; 151 152 // just to avoid passing a zillion parameters to the method the 153 // options are packed into this descriptor. 154 class DecompDesc 155 { 156 public: DecompDesc(void)157 DecompDesc(void) 158 { 159 mVcount = 0; 160 mVertices = 0; 161 mTcount = 0; 162 mIndices = 0; 163 mDepth = 5; 164 mCpercent = 5; 165 mPpercent = 5; 166 mMaxVertices = 32; 167 mSkinWidth = 0; 168 mCallback = 0; 169 } 170 171 // describes the input triangle. 172 unsigned int mVcount; // the number of vertices in the source mesh. 173 const float *mVertices; // start of the vertex position array. Assumes a stride of 3 floats. 174 unsigned int mTcount; // the number of triangles in the source mesh. 175 unsigned int *mIndices; // the indexed triangle list array (zero index based) 176 177 // options 178 unsigned int mDepth; // depth to split, a maximum of 10, generally not over 7. 179 float mCpercent; // the concavity threshold percentage. 0=20 is reasonable. 180 float mPpercent; // the percentage volume conservation threshold to collapse hulls. 0-30 is reasonable. 181 182 // hull output limits. 183 unsigned int mMaxVertices; // maximum number of vertices in the output hull. Recommended 32 or less. 184 float mSkinWidth; // a skin width to apply to the output hulls. 185 186 ConvexDecompInterface *mCallback; // the interface to receive back the results. 187 }; 188 189 // perform approximate convex decomposition on a mesh. 190 unsigned int performConvexDecomposition(const DecompDesc &desc); // returns the number of hulls produced. 191 192 void calcConvexDecomposition(unsigned int vcount, 193 const float *vertices, 194 unsigned int tcount, 195 const unsigned int *indices, 196 ConvexDecompInterface *callback, 197 float masterVolume, 198 unsigned int depth); 199 200 } // namespace ConvexDecomposition 201 202 #endif 203