Extras/ConvexDecomposition/ConvexBuilder.cpp

   1 #include "float_math.h"
   2 #include "ConvexBuilder.h"
   3 #include "meshvolume.h"
   4 #include "bestfit.h"
   5 #include <assert.h>
   6 #include "cd_hull.h"
   7
   8 #include "fitsphere.h"
   9 #include "bestfitobb.h"
  10
  11 unsigned int MAXDEPTH = 8 ;
  12 float CONCAVE_PERCENT = 1.0f ;
  13 float MERGE_PERCENT   = 2.0f ;
  14
  15 CHull::CHull(const ConvexResult &result)
  16 {
  17         mResult = new ConvexResult(result);
  18         mVolume = computeMeshVolume( result.mHullVertices, result.mHullTcount, result.mHullIndices );
  19
  20         mDiagonal = getBoundingRegion( result.mHullVcount, result.mHullVertices, sizeof(float)*3, mMin, mMax );
  21
  22         float dx = mMax[0] - mMin[0];
  23         float dy = mMax[1] - mMin[1];
  24         float dz = mMax[2] - mMin[2];
  25
  26         dx*=0.1f; // inflate 1/10th on each edge
  27         dy*=0.1f; // inflate 1/10th on each edge
  28         dz*=0.1f; // inflate 1/10th on each edge
  29
  30         mMin[0]-=dx;
  31         mMin[1]-=dy;
  32         mMin[2]-=dz;
  33
  34         mMax[0]+=dx;
  35         mMax[1]+=dy;
  36         mMax[2]+=dz;
  37
  38
  39 }
  40
  41 CHull::~CHull(void)
  42 {
  43         delete mResult;
  44 }
  45
  46 bool CHull::overlap(const CHull &h) const
  47 {
  48         return overlapAABB(mMin,mMax, h.mMin, h.mMax );
  49 }
  50
  51
  52
  53
  54 ConvexBuilder::ConvexBuilder(ConvexDecompInterface *callback)
  55 {
  56         mCallback = callback;
  57 }
  58
  59 ConvexBuilder::~ConvexBuilder(void)
  60 {
  61         int i;
  62         for (i=0;i<mChulls.size();i++)
  63         {
  64                 CHull *cr = mChulls[i];
  65                 delete cr;
  66         }
  67 }
  68
  69 bool ConvexBuilder::isDuplicate(unsigned int i1,unsigned int i2,unsigned int i3,
  70                                                                 unsigned int ci1,unsigned int ci2,unsigned int ci3)
  71 {
  72         unsigned int dcount = 0;
  73
  74         assert( i1 != i2 && i1 != i3 && i2 != i3 );
  75         assert( ci1 != ci2 && ci1 != ci3 && ci2 != ci3 );
  76
  77         if ( i1 == ci1 || i1 == ci2 || i1 == ci3 ) dcount++;
  78         if ( i2 == ci1 || i2 == ci2 || i2 == ci3 ) dcount++;
  79         if ( i3 == ci1 || i3 == ci2 || i3 == ci3 ) dcount++;
  80
  81         return dcount == 3;
  82 }
  83
  84 void ConvexBuilder::getMesh(const ConvexResult &cr,VertexLookup vc,UintVector &indices)
  85 {
  86         unsigned int *src = cr.mHullIndices;
  87
  88         for (unsigned int i=0; i<cr.mHullTcount; i++)
  89         {
  90                 unsigned int i1 = *src++;
  91                 unsigned int i2 = *src++;
  92                 unsigned int i3 = *src++;
  93
  94                 const float *p1 = &cr.mHullVertices[i1*3];
  95                 const float *p2 = &cr.mHullVertices[i2*3];
  96                 const float *p3 = &cr.mHullVertices[i3*3];
  97
  98                 i1 = Vl_getIndex(vc,p1);
  99                 i2 = Vl_getIndex(vc,p2);
 100                 i3 = Vl_getIndex(vc,p3);
 101
 102 #if 0
 103                 bool duplicate = false;
 104
 105                 unsigned int tcount = indices.size()/3;
 106                 for (unsigned int j=0; j<tcount; j++)
 107                 {
 108                         unsigned int ci1 = indices[j*3+0];
 109                         unsigned int ci2 = indices[j*3+1];
 110                         unsigned int ci3 = indices[j*3+2];
 111                         if ( isDuplicate(i1,i2,i3, ci1, ci2, ci3 ) )
 112                         {
 113                                 duplicate = true;
 114                                 break;
 115                         }
 116                 }
 117
 118                 if ( !duplicate )
 119                 {
 120                         indices.push_back(i1);
 121                         indices.push_back(i2);
 122                         indices.push_back(i3);
 123                 }
 124 #endif
 125
 126         }
 127 }
 128
 129 CHull * ConvexBuilder::canMerge(CHull *a,CHull *b)
 130 {
 131
 132         if ( !a->overlap(*b) ) return 0; // if their AABB's (with a little slop) don't overlap, then return.
 133
 134         CHull *ret = 0;
 135
 136         // ok..we are going to combine both meshes into a single mesh
 137         // and then we are going to compute the concavity...
 138
 139         VertexLookup vc = Vl_createVertexLookup();
 140
 141         UintVector indices;
 142
 143         getMesh( *a->mResult, vc, indices );
 144         getMesh( *b->mResult, vc, indices );
 145
 146         unsigned int vcount = Vl_getVcount(vc);
 147         const float *vertices = Vl_getVertices(vc);
 148         unsigned int tcount = indices.size()/3;
 149
 150         //don't do anything if hull is empty
 151         if (!tcount)
 152         {
 153                 Vl_releaseVertexLookup (vc);
 154                 return 0;
 155         }
 156
 157         HullResult hresult;
 158         HullLibrary hl;
 159         HullDesc   desc;
 160
 161         desc.SetHullFlag(QF_TRIANGLES);
 162
 163         desc.mVcount       = vcount;
 164         desc.mVertices     = vertices;
 165         desc.mVertexStride = sizeof(float)*3;
 166
 167         HullError hret = hl.CreateConvexHull(desc,hresult);
 168
 169         if ( hret == QE_OK )
 170         {
 171
 172                 float combineVolume  = computeMeshVolume( hresult.mOutputVertices, hresult.mNumFaces, hresult.mIndices );
 173                 float sumVolume      = a->mVolume + b->mVolume;
 174
 175                 float percent = (sumVolume*100) / combineVolume;
 176                 if ( percent >= (100.0f-MERGE_PERCENT) )
 177                 {
 178                         ConvexResult cr(hresult.mNumOutputVertices, hresult.mOutputVertices, hresult.mNumFaces, hresult.mIndices);
 179                         ret = new CHull(cr);
 180                 }
 181         }
 182
 183
 184         Vl_releaseVertexLookup(vc);
 185
 186         return ret;
 187 }
 188
 189 bool ConvexBuilder::combineHulls(void)
 190 {
 191
 192         bool combine = false;
 193
 194         sortChulls(mChulls); // sort the convex hulls, largest volume to least...
 195
 196         CHullVector output; // the output hulls...
 197
 198
 199         int i;
 200
 201         for (i=0;i<mChulls.size() && !combine; ++i)
 202         {
 203                 CHull *cr = mChulls[i];
 204
 205                 int j;
 206                 for (j=0;j<mChulls.size();j++)
 207                 {
 208                         CHull *match = mChulls[j];
 209
 210                         if ( cr != match ) // don't try to merge a hull with itself, that be stoopid
 211                         {
 212
 213                                 CHull *merge = canMerge(cr,match); // if we can merge these two....
 214
 215                                 if ( merge )
 216                                 {
 217
 218                                         output.push_back(merge);
 219
 220
 221                                         ++i;
 222                                         while ( i != mChulls.size() )
 223                                         {
 224                                                 CHull *cr = mChulls[i];
 225                                                 if ( cr != match )
 226                                                 {
 227                                                         output.push_back(cr);
 228                                                 }
 229                                                 i++;
 230                                         }
 231
 232                                         delete cr;
 233                                         delete match;
 234                                         combine = true;
 235                                         break;
 236                                 }
 237                         }
 238                 }
 239
 240                 if ( combine )
 241                 {
 242                         break;
 243                 }
 244                 else
 245                 {
 246                         output.push_back(cr);
 247                 }
 248
 249         }
 250
 251         if ( combine )
 252         {
 253                 mChulls.clear();
 254                 mChulls.copyFromArray(output);
 255                 output.clear();
 256         }
 257
 258
 259         return combine;
 260 }
 261
 262 unsigned int ConvexBuilder::process(const DecompDesc &desc)
 263 {
 264
 265         unsigned int ret = 0;
 266
 267         MAXDEPTH        = desc.mDepth;
 268         CONCAVE_PERCENT = desc.mCpercent;
 269         MERGE_PERCENT   = desc.mPpercent;
 270
 271
 272         calcConvexDecomposition(desc.mVcount, desc.mVertices, desc.mTcount, desc.mIndices,this,0,0);
 273
 274
 275         while ( combineHulls() ); // keep combinging hulls until I can't combine any more...
 276
 277         int i;
 278         for (i=0;i<mChulls.size();i++)
 279         {
 280                 CHull *cr = mChulls[i];
 281
 282                 // before we hand it back to the application, we need to regenerate the hull based on the
 283                 // limits given by the user.
 284
 285                 const ConvexResult &c = *cr->mResult; // the high resolution hull...
 286
 287                 HullResult result;
 288                 HullLibrary hl;
 289                 HullDesc   hdesc;
 290
 291                 hdesc.SetHullFlag(QF_TRIANGLES);
 292
 293                 hdesc.mVcount       = c.mHullVcount;
 294                 hdesc.mVertices     = c.mHullVertices;
 295                 hdesc.mVertexStride = sizeof(float)*3;
 296                 hdesc.mMaxVertices  = desc.mMaxVertices; // maximum number of vertices allowed in the output
 297
 298                 if ( desc.mSkinWidth  )
 299                 {
 300                         hdesc.mSkinWidth = desc.mSkinWidth;
 301                         hdesc.SetHullFlag(QF_SKIN_WIDTH); // do skin width computation.
 302                 }
 303
 304                 HullError ret = hl.CreateConvexHull(hdesc,result);
 305
 306                 if ( ret == QE_OK )
 307                 {
 308                         ConvexResult r(result.mNumOutputVertices, result.mOutputVertices, result.mNumFaces, result.mIndices);
 309
 310                         r.mHullVolume = computeMeshVolume( result.mOutputVertices, result.mNumFaces, result.mIndices ); // the volume of the hull.
 311
 312                         // compute the best fit OBB
 313                         computeBestFitOBB( result.mNumOutputVertices, result.mOutputVertices, sizeof(float)*3, r.mOBBSides, r.mOBBTransform );
 314
 315                         r.mOBBVolume = r.mOBBSides[0] * r.mOBBSides[1] *r.mOBBSides[2]; // compute the OBB volume.
 316
 317                         fm_getTranslation( r.mOBBTransform, r.mOBBCenter );      // get the translation component of the 4x4 matrix.
 318
 319                         fm_matrixToQuat( r.mOBBTransform, r.mOBBOrientation );   // extract the orientation as a quaternion.
 320
 321                         r.mSphereRadius = computeBoundingSphere( result.mNumOutputVertices, result.mOutputVertices, r.mSphereCenter );
 322                         r.mSphereVolume = fm_sphereVolume( r.mSphereRadius );
 323
 324
 325                         mCallback->ConvexDecompResult(r);
 326                 }
 327
 328                 hl.ReleaseResult (result);
 329
 330
 331                 delete cr;
 332         }
 333
 334         ret = mChulls.size();
 335
 336         mChulls.clear();
 337
 338         return ret;
 339 }
 340
 341
 342 void ConvexBuilder::ConvexDebugTri(const float *p1,const float *p2,const float *p3,unsigned int color)
 343 {
 344         mCallback->ConvexDebugTri(p1,p2,p3,color);
 345 }
 346
 347 void ConvexBuilder::ConvexDebugOBB(const float *sides, const float *matrix,unsigned int color)
 348 {
 349         mCallback->ConvexDebugOBB(sides,matrix,color);
 350 }
 351 void ConvexBuilder::ConvexDebugPoint(const float *p,float dist,unsigned int color)
 352 {
 353         mCallback->ConvexDebugPoint(p,dist,color);
 354 }
 355
 356 void ConvexBuilder::ConvexDebugBound(const float *bmin,const float *bmax,unsigned int color)
 357 {
 358         mCallback->ConvexDebugBound(bmin,bmax,color);
 359 }
 360
 361 void ConvexBuilder::ConvexDecompResult(ConvexResult &result)
 362 {
 363         CHull *ch = new CHull(result);
 364         mChulls.push_back(ch);
 365 }
 366
 367 void ConvexBuilder::sortChulls(CHullVector &hulls)
 368 {
 369         hulls.quickSort(CHullSort());
 370         //hulls.heapSort(CHullSort());
 371 }
 372
 373