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