opensim-development – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 eva 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 }