clockwerk-opensim-stable – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | vero | 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 | } |