diff options
Diffstat (limited to 'OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs')
-rw-r--r-- | OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs | 411 |
1 files changed, 411 insertions, 0 deletions
diff --git a/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs new file mode 100644 index 0000000..dfaede1 --- /dev/null +++ b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs | |||
@@ -0,0 +1,411 @@ | |||
1 | /* The MIT License | ||
2 | * | ||
3 | * Copyright (c) 2010 Intel Corporation. | ||
4 | * All rights reserved. | ||
5 | * | ||
6 | * Based on the convexdecomposition library from | ||
7 | * <http://codesuppository.googlecode.com> by John W. Ratcliff and Stan Melax. | ||
8 | * | ||
9 | * Permission is hereby granted, free of charge, to any person obtaining a copy | ||
10 | * of this software and associated documentation files (the "Software"), to deal | ||
11 | * in the Software without restriction, including without limitation the rights | ||
12 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | ||
13 | * copies of the Software, and to permit persons to whom the Software is | ||
14 | * furnished to do so, subject to the following conditions: | ||
15 | * | ||
16 | * The above copyright notice and this permission notice shall be included in | ||
17 | * all copies or substantial portions of the Software. | ||
18 | * | ||
19 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | ||
20 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | ||
21 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | ||
22 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | ||
23 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | ||
24 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | ||
25 | * THE SOFTWARE. | ||
26 | */ | ||
27 | |||
28 | using System; | ||
29 | using System.Collections.Generic; | ||
30 | using System.Diagnostics; | ||
31 | |||
32 | namespace OpenSim.Region.Physics.ConvexDecompositionDotNet | ||
33 | { | ||
34 | public class DecompDesc | ||
35 | { | ||
36 | public List<float3> mVertices; | ||
37 | public List<int> mIndices; | ||
38 | |||
39 | // options | ||
40 | public uint mDepth; // depth to split, a maximum of 10, generally not over 7. | ||
41 | public float mCpercent; // the concavity threshold percentage. 0=20 is reasonable. | ||
42 | public float mPpercent; // the percentage volume conservation threshold to collapse hulls. 0-30 is reasonable. | ||
43 | |||
44 | // hull output limits. | ||
45 | public uint mMaxVertices; // maximum number of vertices in the output hull. Recommended 32 or less. | ||
46 | public float mSkinWidth; // a skin width to apply to the output hulls. | ||
47 | |||
48 | public ConvexDecompositionCallback mCallback; // the interface to receive back the results. | ||
49 | |||
50 | public DecompDesc() | ||
51 | { | ||
52 | mDepth = 5; | ||
53 | mCpercent = 5; | ||
54 | mPpercent = 5; | ||
55 | mMaxVertices = 32; | ||
56 | } | ||
57 | } | ||
58 | |||
59 | public class CHull | ||
60 | { | ||
61 | public float[] mMin = new float[3]; | ||
62 | public float[] mMax = new float[3]; | ||
63 | public float mVolume; | ||
64 | public float mDiagonal; | ||
65 | public ConvexResult mResult; | ||
66 | |||
67 | public CHull(ConvexResult result) | ||
68 | { | ||
69 | mResult = new ConvexResult(result); | ||
70 | mVolume = Concavity.computeMeshVolume(result.HullVertices, result.HullIndices); | ||
71 | |||
72 | mDiagonal = getBoundingRegion(result.HullVertices, mMin, mMax); | ||
73 | |||
74 | float dx = mMax[0] - mMin[0]; | ||
75 | float dy = mMax[1] - mMin[1]; | ||
76 | float dz = mMax[2] - mMin[2]; | ||
77 | |||
78 | dx *= 0.1f; // inflate 1/10th on each edge | ||
79 | dy *= 0.1f; // inflate 1/10th on each edge | ||
80 | dz *= 0.1f; // inflate 1/10th on each edge | ||
81 | |||
82 | mMin[0] -= dx; | ||
83 | mMin[1] -= dy; | ||
84 | mMin[2] -= dz; | ||
85 | |||
86 | mMax[0] += dx; | ||
87 | mMax[1] += dy; | ||
88 | mMax[2] += dz; | ||
89 | } | ||
90 | |||
91 | public void Dispose() | ||
92 | { | ||
93 | mResult = null; | ||
94 | } | ||
95 | |||
96 | public bool overlap(CHull h) | ||
97 | { | ||
98 | return overlapAABB(mMin, mMax, h.mMin, h.mMax); | ||
99 | } | ||
100 | |||
101 | // returns the d1Giagonal distance | ||
102 | private static float getBoundingRegion(List<float3> points, float[] bmin, float[] bmax) | ||
103 | { | ||
104 | float3 first = points[0]; | ||
105 | |||
106 | bmin[0] = first.x; | ||
107 | bmin[1] = first.y; | ||
108 | bmin[2] = first.z; | ||
109 | |||
110 | bmax[0] = first.x; | ||
111 | bmax[1] = first.y; | ||
112 | bmax[2] = first.z; | ||
113 | |||
114 | for (int i = 1; i < points.Count; i++) | ||
115 | { | ||
116 | float3 p = points[i]; | ||
117 | |||
118 | if (p[0] < bmin[0]) bmin[0] = p[0]; | ||
119 | if (p[1] < bmin[1]) bmin[1] = p[1]; | ||
120 | if (p[2] < bmin[2]) bmin[2] = p[2]; | ||
121 | |||
122 | if (p[0] > bmax[0]) bmax[0] = p[0]; | ||
123 | if (p[1] > bmax[1]) bmax[1] = p[1]; | ||
124 | if (p[2] > bmax[2]) bmax[2] = p[2]; | ||
125 | } | ||
126 | |||
127 | float dx = bmax[0] - bmin[0]; | ||
128 | float dy = bmax[1] - bmin[1]; | ||
129 | float dz = bmax[2] - bmin[2]; | ||
130 | |||
131 | return (float)Math.Sqrt(dx * dx + dy * dy + dz * dz); | ||
132 | } | ||
133 | |||
134 | // return true if the two AABB's overlap. | ||
135 | private static bool overlapAABB(float[] bmin1, float[] bmax1, float[] bmin2, float[] bmax2) | ||
136 | { | ||
137 | if (bmax2[0] < bmin1[0]) return false; // if the maximum is less than our minimum on any axis | ||
138 | if (bmax2[1] < bmin1[1]) return false; | ||
139 | if (bmax2[2] < bmin1[2]) return false; | ||
140 | |||
141 | if (bmin2[0] > bmax1[0]) return false; // if the minimum is greater than our maximum on any axis | ||
142 | if (bmin2[1] > bmax1[1]) return false; // if the minimum is greater than our maximum on any axis | ||
143 | if (bmin2[2] > bmax1[2]) return false; // if the minimum is greater than our maximum on any axis | ||
144 | |||
145 | return true; // the extents overlap | ||
146 | } | ||
147 | } | ||
148 | |||
149 | public class ConvexBuilder | ||
150 | { | ||
151 | public List<CHull> mChulls = new List<CHull>(); | ||
152 | private ConvexDecompositionCallback mCallback; | ||
153 | |||
154 | private int MAXDEPTH = 8; | ||
155 | private float CONCAVE_PERCENT = 1f; | ||
156 | private float MERGE_PERCENT = 2f; | ||
157 | |||
158 | public ConvexBuilder(ConvexDecompositionCallback callback) | ||
159 | { | ||
160 | mCallback = callback; | ||
161 | } | ||
162 | |||
163 | public void Dispose() | ||
164 | { | ||
165 | int i; | ||
166 | for (i = 0; i < mChulls.Count; i++) | ||
167 | { | ||
168 | CHull cr = mChulls[i]; | ||
169 | cr.Dispose(); | ||
170 | } | ||
171 | } | ||
172 | |||
173 | public bool isDuplicate(uint i1, uint i2, uint i3, uint ci1, uint ci2, uint ci3) | ||
174 | { | ||
175 | uint dcount = 0; | ||
176 | |||
177 | Debug.Assert(i1 != i2 && i1 != i3 && i2 != i3); | ||
178 | Debug.Assert(ci1 != ci2 && ci1 != ci3 && ci2 != ci3); | ||
179 | |||
180 | if (i1 == ci1 || i1 == ci2 || i1 == ci3) | ||
181 | dcount++; | ||
182 | if (i2 == ci1 || i2 == ci2 || i2 == ci3) | ||
183 | dcount++; | ||
184 | if (i3 == ci1 || i3 == ci2 || i3 == ci3) | ||
185 | dcount++; | ||
186 | |||
187 | return dcount == 3; | ||
188 | } | ||
189 | |||
190 | public void getMesh(ConvexResult cr, VertexPool vc, List<int> indices) | ||
191 | { | ||
192 | List<int> src = cr.HullIndices; | ||
193 | |||
194 | for (int i = 0; i < src.Count / 3; i++) | ||
195 | { | ||
196 | int i1 = src[i * 3 + 0]; | ||
197 | int i2 = src[i * 3 + 1]; | ||
198 | int i3 = src[i * 3 + 2]; | ||
199 | |||
200 | float3 p1 = cr.HullVertices[i1]; | ||
201 | float3 p2 = cr.HullVertices[i2]; | ||
202 | float3 p3 = cr.HullVertices[i3]; | ||
203 | |||
204 | i1 = vc.getIndex(p1); | ||
205 | i2 = vc.getIndex(p2); | ||
206 | i3 = vc.getIndex(p3); | ||
207 | } | ||
208 | } | ||
209 | |||
210 | public CHull canMerge(CHull a, CHull b) | ||
211 | { | ||
212 | if (!a.overlap(b)) // if their AABB's (with a little slop) don't overlap, then return. | ||
213 | return null; | ||
214 | |||
215 | CHull ret = null; | ||
216 | |||
217 | // ok..we are going to combine both meshes into a single mesh | ||
218 | // and then we are going to compute the concavity... | ||
219 | |||
220 | VertexPool vc = new VertexPool(); | ||
221 | |||
222 | List<int> indices = new List<int>(); | ||
223 | |||
224 | getMesh(a.mResult, vc, indices); | ||
225 | getMesh(b.mResult, vc, indices); | ||
226 | |||
227 | int vcount = vc.GetSize(); | ||
228 | List<float3> vertices = vc.GetVertices(); | ||
229 | int tcount = indices.Count / 3; | ||
230 | |||
231 | //don't do anything if hull is empty | ||
232 | if (tcount == 0) | ||
233 | { | ||
234 | vc.Clear(); | ||
235 | return null; | ||
236 | } | ||
237 | |||
238 | HullResult hresult = new HullResult(); | ||
239 | HullDesc desc = new HullDesc(); | ||
240 | |||
241 | desc.SetHullFlag(HullFlag.QF_TRIANGLES); | ||
242 | desc.Vertices = vertices; | ||
243 | |||
244 | HullError hret = HullUtils.CreateConvexHull(desc, ref hresult); | ||
245 | |||
246 | if (hret == HullError.QE_OK) | ||
247 | { | ||
248 | float combineVolume = Concavity.computeMeshVolume(hresult.OutputVertices, hresult.Indices); | ||
249 | float sumVolume = a.mVolume + b.mVolume; | ||
250 | |||
251 | float percent = (sumVolume * 100) / combineVolume; | ||
252 | if (percent >= (100.0f - MERGE_PERCENT)) | ||
253 | { | ||
254 | ConvexResult cr = new ConvexResult(hresult.OutputVertices, hresult.Indices); | ||
255 | ret = new CHull(cr); | ||
256 | } | ||
257 | } | ||
258 | |||
259 | vc.Clear(); | ||
260 | return ret; | ||
261 | } | ||
262 | |||
263 | public bool combineHulls() | ||
264 | { | ||
265 | bool combine = false; | ||
266 | |||
267 | sortChulls(mChulls); // sort the convex hulls, largest volume to least... | ||
268 | |||
269 | List<CHull> output = new List<CHull>(); // the output hulls... | ||
270 | |||
271 | int i; | ||
272 | for (i = 0; i < mChulls.Count && !combine; ++i) | ||
273 | { | ||
274 | CHull cr = mChulls[i]; | ||
275 | |||
276 | int j; | ||
277 | for (j = 0; j < mChulls.Count; j++) | ||
278 | { | ||
279 | CHull match = mChulls[j]; | ||
280 | |||
281 | if (cr != match) // don't try to merge a hull with itself, that be stoopid | ||
282 | { | ||
283 | |||
284 | CHull merge = canMerge(cr, match); // if we can merge these two.... | ||
285 | |||
286 | if (merge != null) | ||
287 | { | ||
288 | output.Add(merge); | ||
289 | |||
290 | ++i; | ||
291 | while (i != mChulls.Count) | ||
292 | { | ||
293 | CHull cr2 = mChulls[i]; | ||
294 | if (cr2 != match) | ||
295 | { | ||
296 | output.Add(cr2); | ||
297 | } | ||
298 | i++; | ||
299 | } | ||
300 | |||
301 | cr.Dispose(); | ||
302 | match.Dispose(); | ||
303 | combine = true; | ||
304 | break; | ||
305 | } | ||
306 | } | ||
307 | } | ||
308 | |||
309 | if (combine) | ||
310 | { | ||
311 | break; | ||
312 | } | ||
313 | else | ||
314 | { | ||
315 | output.Add(cr); | ||
316 | } | ||
317 | } | ||
318 | |||
319 | if (combine) | ||
320 | { | ||
321 | mChulls.Clear(); | ||
322 | mChulls = output; | ||
323 | output.Clear(); | ||
324 | } | ||
325 | |||
326 | return combine; | ||
327 | } | ||
328 | |||
329 | public int process(DecompDesc desc) | ||
330 | { | ||
331 | int ret = 0; | ||
332 | |||
333 | MAXDEPTH = (int)desc.mDepth; | ||
334 | CONCAVE_PERCENT = desc.mCpercent; | ||
335 | MERGE_PERCENT = desc.mPpercent; | ||
336 | |||
337 | ConvexDecomposition.calcConvexDecomposition(desc.mVertices, desc.mIndices, ConvexDecompResult, 0f, 0, MAXDEPTH, CONCAVE_PERCENT, MERGE_PERCENT); | ||
338 | |||
339 | while (combineHulls()) // keep combinging hulls until I can't combine any more... | ||
340 | ; | ||
341 | |||
342 | int i; | ||
343 | for (i = 0; i < mChulls.Count; i++) | ||
344 | { | ||
345 | CHull cr = mChulls[i]; | ||
346 | |||
347 | // before we hand it back to the application, we need to regenerate the hull based on the | ||
348 | // limits given by the user. | ||
349 | |||
350 | ConvexResult c = cr.mResult; // the high resolution hull... | ||
351 | |||
352 | HullResult result = new HullResult(); | ||
353 | HullDesc hdesc = new HullDesc(); | ||
354 | |||
355 | hdesc.SetHullFlag(HullFlag.QF_TRIANGLES); | ||
356 | |||
357 | hdesc.Vertices = c.HullVertices; | ||
358 | hdesc.MaxVertices = desc.mMaxVertices; // maximum number of vertices allowed in the output | ||
359 | |||
360 | if (desc.mSkinWidth != 0f) | ||
361 | { | ||
362 | hdesc.SkinWidth = desc.mSkinWidth; | ||
363 | hdesc.SetHullFlag(HullFlag.QF_SKIN_WIDTH); // do skin width computation. | ||
364 | } | ||
365 | |||
366 | HullError ret2 = HullUtils.CreateConvexHull(hdesc, ref result); | ||
367 | |||
368 | if (ret2 == HullError.QE_OK) | ||
369 | { | ||
370 | ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices); | ||
371 | |||
372 | r.mHullVolume = Concavity.computeMeshVolume(result.OutputVertices, result.Indices); // the volume of the hull. | ||
373 | |||
374 | // compute the best fit OBB | ||
375 | //computeBestFitOBB(result.mNumOutputVertices, result.mOutputVertices, sizeof(float) * 3, r.mOBBSides, r.mOBBTransform); | ||
376 | |||
377 | //r.mOBBVolume = r.mOBBSides[0] * r.mOBBSides[1] * r.mOBBSides[2]; // compute the OBB volume. | ||
378 | |||
379 | //fm_getTranslation(r.mOBBTransform, r.mOBBCenter); // get the translation component of the 4x4 matrix. | ||
380 | |||
381 | //fm_matrixToQuat(r.mOBBTransform, r.mOBBOrientation); // extract the orientation as a quaternion. | ||
382 | |||
383 | //r.mSphereRadius = computeBoundingSphere(result.mNumOutputVertices, result.mOutputVertices, r.mSphereCenter); | ||
384 | //r.mSphereVolume = fm_sphereVolume(r.mSphereRadius); | ||
385 | |||
386 | mCallback(r); | ||
387 | } | ||
388 | |||
389 | result = null; | ||
390 | cr.Dispose(); | ||
391 | } | ||
392 | |||
393 | ret = mChulls.Count; | ||
394 | |||
395 | mChulls.Clear(); | ||
396 | |||
397 | return ret; | ||
398 | } | ||
399 | |||
400 | public void ConvexDecompResult(ConvexResult result) | ||
401 | { | ||
402 | CHull ch = new CHull(result); | ||
403 | mChulls.Add(ch); | ||
404 | } | ||
405 | |||
406 | public void sortChulls(List<CHull> hulls) | ||
407 | { | ||
408 | hulls.Sort(delegate(CHull a, CHull b) { return a.mVolume.CompareTo(b.mVolume); }); | ||
409 | } | ||
410 | } | ||
411 | } | ||