ConvexBuilder.cs 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411
  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. using System;
  28. using System.Collections.Generic;
  29. using System.Diagnostics;
  30. namespace OpenSim.Region.PhysicsModules.ConvexDecompositionDotNet
  31. {
  32. public class DecompDesc
  33. {
  34. public List<float3> mVertices;
  35. public List<int> mIndices;
  36. // options
  37. public uint mDepth; // depth to split, a maximum of 10, generally not over 7.
  38. public float mCpercent; // the concavity threshold percentage. 0=20 is reasonable.
  39. public float mPpercent; // the percentage volume conservation threshold to collapse hulls. 0-30 is reasonable.
  40. // hull output limits.
  41. public uint mMaxVertices; // maximum number of vertices in the output hull. Recommended 32 or less.
  42. public float mSkinWidth; // a skin width to apply to the output hulls.
  43. public ConvexDecompositionCallback mCallback; // the interface to receive back the results.
  44. public DecompDesc()
  45. {
  46. mDepth = 5;
  47. mCpercent = 5;
  48. mPpercent = 5;
  49. mMaxVertices = 32;
  50. }
  51. }
  52. public class CHull
  53. {
  54. public float[] mMin = new float[3];
  55. public float[] mMax = new float[3];
  56. public float mVolume;
  57. public float mDiagonal;
  58. public ConvexResult mResult;
  59. public CHull(ConvexResult result)
  60. {
  61. mResult = new ConvexResult(result);
  62. mVolume = Concavity.computeMeshVolume(result.HullVertices, result.HullIndices);
  63. mDiagonal = getBoundingRegion(result.HullVertices, mMin, mMax);
  64. float dx = mMax[0] - mMin[0];
  65. float dy = mMax[1] - mMin[1];
  66. float dz = mMax[2] - mMin[2];
  67. dx *= 0.1f; // inflate 1/10th on each edge
  68. dy *= 0.1f; // inflate 1/10th on each edge
  69. dz *= 0.1f; // inflate 1/10th on each edge
  70. mMin[0] -= dx;
  71. mMin[1] -= dy;
  72. mMin[2] -= dz;
  73. mMax[0] += dx;
  74. mMax[1] += dy;
  75. mMax[2] += dz;
  76. }
  77. public void Dispose()
  78. {
  79. mResult = null;
  80. }
  81. public bool overlap(CHull h)
  82. {
  83. return overlapAABB(mMin, mMax, h.mMin, h.mMax);
  84. }
  85. // returns the d1Giagonal distance
  86. private static float getBoundingRegion(List<float3> points, float[] bmin, float[] bmax)
  87. {
  88. float3 first = points[0];
  89. bmin[0] = first.x;
  90. bmin[1] = first.y;
  91. bmin[2] = first.z;
  92. bmax[0] = first.x;
  93. bmax[1] = first.y;
  94. bmax[2] = first.z;
  95. for (int i = 1; i < points.Count; i++)
  96. {
  97. float3 p = points[i];
  98. if (p[0] < bmin[0]) bmin[0] = p[0];
  99. if (p[1] < bmin[1]) bmin[1] = p[1];
  100. if (p[2] < bmin[2]) bmin[2] = p[2];
  101. if (p[0] > bmax[0]) bmax[0] = p[0];
  102. if (p[1] > bmax[1]) bmax[1] = p[1];
  103. if (p[2] > bmax[2]) bmax[2] = p[2];
  104. }
  105. float dx = bmax[0] - bmin[0];
  106. float dy = bmax[1] - bmin[1];
  107. float dz = bmax[2] - bmin[2];
  108. return (float)Math.Sqrt(dx * dx + dy * dy + dz * dz);
  109. }
  110. // return true if the two AABB's overlap.
  111. private static bool overlapAABB(float[] bmin1, float[] bmax1, float[] bmin2, float[] bmax2)
  112. {
  113. if (bmax2[0] < bmin1[0]) return false; // if the maximum is less than our minimum on any axis
  114. if (bmax2[1] < bmin1[1]) return false;
  115. if (bmax2[2] < bmin1[2]) return false;
  116. if (bmin2[0] > bmax1[0]) return false; // if the minimum is greater than our maximum on any axis
  117. if (bmin2[1] > bmax1[1]) return false; // if the minimum is greater than our maximum on any axis
  118. if (bmin2[2] > bmax1[2]) return false; // if the minimum is greater than our maximum on any axis
  119. return true; // the extents overlap
  120. }
  121. }
  122. public class ConvexBuilder
  123. {
  124. public List<CHull> mChulls = new List<CHull>();
  125. private ConvexDecompositionCallback mCallback;
  126. private int MAXDEPTH = 8;
  127. private float CONCAVE_PERCENT = 1f;
  128. private float MERGE_PERCENT = 2f;
  129. public ConvexBuilder(ConvexDecompositionCallback callback)
  130. {
  131. mCallback = callback;
  132. }
  133. public void Dispose()
  134. {
  135. int i;
  136. for (i = 0; i < mChulls.Count; i++)
  137. {
  138. CHull cr = mChulls[i];
  139. cr.Dispose();
  140. }
  141. }
  142. public bool isDuplicate(uint i1, uint i2, uint i3, uint ci1, uint ci2, uint ci3)
  143. {
  144. uint dcount = 0;
  145. Debug.Assert(i1 != i2 && i1 != i3 && i2 != i3);
  146. Debug.Assert(ci1 != ci2 && ci1 != ci3 && ci2 != ci3);
  147. if (i1 == ci1 || i1 == ci2 || i1 == ci3)
  148. dcount++;
  149. if (i2 == ci1 || i2 == ci2 || i2 == ci3)
  150. dcount++;
  151. if (i3 == ci1 || i3 == ci2 || i3 == ci3)
  152. dcount++;
  153. return dcount == 3;
  154. }
  155. public void getMesh(ConvexResult cr, VertexPool vc, List<int> indices)
  156. {
  157. List<int> src = cr.HullIndices;
  158. for (int i = 0; i < src.Count / 3; i++)
  159. {
  160. int i1 = src[i * 3 + 0];
  161. int i2 = src[i * 3 + 1];
  162. int i3 = src[i * 3 + 2];
  163. float3 p1 = cr.HullVertices[i1];
  164. float3 p2 = cr.HullVertices[i2];
  165. float3 p3 = cr.HullVertices[i3];
  166. i1 = vc.getIndex(p1);
  167. i2 = vc.getIndex(p2);
  168. i3 = vc.getIndex(p3);
  169. }
  170. }
  171. public CHull canMerge(CHull a, CHull b)
  172. {
  173. if (!a.overlap(b)) // if their AABB's (with a little slop) don't overlap, then return.
  174. return null;
  175. CHull ret = null;
  176. // ok..we are going to combine both meshes into a single mesh
  177. // and then we are going to compute the concavity...
  178. VertexPool vc = new VertexPool();
  179. List<int> indices = new List<int>();
  180. getMesh(a.mResult, vc, indices);
  181. getMesh(b.mResult, vc, indices);
  182. int vcount = vc.GetSize();
  183. List<float3> vertices = vc.GetVertices();
  184. int tcount = indices.Count / 3;
  185. //don't do anything if hull is empty
  186. if (tcount == 0)
  187. {
  188. vc.Clear();
  189. return null;
  190. }
  191. HullResult hresult = new HullResult();
  192. HullDesc desc = new HullDesc();
  193. desc.SetHullFlag(HullFlag.QF_TRIANGLES);
  194. desc.Vertices = vertices;
  195. HullError hret = HullUtils.CreateConvexHull(desc, ref hresult);
  196. if (hret == HullError.QE_OK)
  197. {
  198. float combineVolume = Concavity.computeMeshVolume(hresult.OutputVertices, hresult.Indices);
  199. float sumVolume = a.mVolume + b.mVolume;
  200. float percent = (sumVolume * 100) / combineVolume;
  201. if (percent >= (100.0f - MERGE_PERCENT))
  202. {
  203. ConvexResult cr = new ConvexResult(hresult.OutputVertices, hresult.Indices);
  204. ret = new CHull(cr);
  205. }
  206. }
  207. vc.Clear();
  208. return ret;
  209. }
  210. public bool combineHulls()
  211. {
  212. bool combine = false;
  213. sortChulls(mChulls); // sort the convex hulls, largest volume to least...
  214. List<CHull> output = new List<CHull>(); // the output hulls...
  215. int i;
  216. for (i = 0; i < mChulls.Count && !combine; ++i)
  217. {
  218. CHull cr = mChulls[i];
  219. int j;
  220. for (j = 0; j < mChulls.Count; j++)
  221. {
  222. CHull match = mChulls[j];
  223. if (cr != match) // don't try to merge a hull with itself, that be stoopid
  224. {
  225. CHull merge = canMerge(cr, match); // if we can merge these two....
  226. if (merge != null)
  227. {
  228. output.Add(merge);
  229. ++i;
  230. while (i != mChulls.Count)
  231. {
  232. CHull cr2 = mChulls[i];
  233. if (cr2 != match)
  234. {
  235. output.Add(cr2);
  236. }
  237. i++;
  238. }
  239. cr.Dispose();
  240. match.Dispose();
  241. combine = true;
  242. break;
  243. }
  244. }
  245. }
  246. if (combine)
  247. {
  248. break;
  249. }
  250. else
  251. {
  252. output.Add(cr);
  253. }
  254. }
  255. if (combine)
  256. {
  257. mChulls.Clear();
  258. mChulls = output;
  259. output.Clear();
  260. }
  261. return combine;
  262. }
  263. public int process(DecompDesc desc)
  264. {
  265. int ret = 0;
  266. MAXDEPTH = (int)desc.mDepth;
  267. CONCAVE_PERCENT = desc.mCpercent;
  268. MERGE_PERCENT = desc.mPpercent;
  269. ConvexDecomposition.calcConvexDecomposition(desc.mVertices, desc.mIndices, ConvexDecompResult, 0f, 0, MAXDEPTH, CONCAVE_PERCENT, MERGE_PERCENT);
  270. while (combineHulls()) // keep combinging hulls until I can't combine any more...
  271. ;
  272. int i;
  273. for (i = 0; i < mChulls.Count; i++)
  274. {
  275. CHull cr = mChulls[i];
  276. // before we hand it back to the application, we need to regenerate the hull based on the
  277. // limits given by the user.
  278. ConvexResult c = cr.mResult; // the high resolution hull...
  279. HullResult result = new HullResult();
  280. HullDesc hdesc = new HullDesc();
  281. hdesc.SetHullFlag(HullFlag.QF_TRIANGLES);
  282. hdesc.Vertices = c.HullVertices;
  283. hdesc.MaxVertices = desc.mMaxVertices; // maximum number of vertices allowed in the output
  284. if (desc.mSkinWidth != 0f)
  285. {
  286. hdesc.SkinWidth = desc.mSkinWidth;
  287. hdesc.SetHullFlag(HullFlag.QF_SKIN_WIDTH); // do skin width computation.
  288. }
  289. HullError ret2 = HullUtils.CreateConvexHull(hdesc, ref result);
  290. if (ret2 == HullError.QE_OK)
  291. {
  292. ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices);
  293. r.mHullVolume = Concavity.computeMeshVolume(result.OutputVertices, result.Indices); // the volume of the hull.
  294. // compute the best fit OBB
  295. //computeBestFitOBB(result.mNumOutputVertices, result.mOutputVertices, sizeof(float) * 3, r.mOBBSides, r.mOBBTransform);
  296. //r.mOBBVolume = r.mOBBSides[0] * r.mOBBSides[1] * r.mOBBSides[2]; // compute the OBB volume.
  297. //fm_getTranslation(r.mOBBTransform, r.mOBBCenter); // get the translation component of the 4x4 matrix.
  298. //fm_matrixToQuat(r.mOBBTransform, r.mOBBOrientation); // extract the orientation as a quaternion.
  299. //r.mSphereRadius = computeBoundingSphere(result.mNumOutputVertices, result.mOutputVertices, r.mSphereCenter);
  300. //r.mSphereVolume = fm_sphereVolume(r.mSphereRadius);
  301. mCallback(r);
  302. }
  303. result = null;
  304. cr.Dispose();
  305. }
  306. ret = mChulls.Count;
  307. mChulls.Clear();
  308. return ret;
  309. }
  310. public void ConvexDecompResult(ConvexResult result)
  311. {
  312. CHull ch = new CHull(result);
  313. mChulls.Add(ch);
  314. }
  315. public void sortChulls(List<CHull> hulls)
  316. {
  317. hulls.Sort(delegate(CHull a, CHull b) { return a.mVolume.CompareTo(b.mVolume); });
  318. }
  319. }
  320. }