← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/bullet/Extras/ConvexDecomposition/ConvexBuilder.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
tests/bullet/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 = 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