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