Concavity.cs 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233
  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.Text;
  30. namespace OpenSim.Region.PhysicsModule.ConvexDecompositionDotNet
  31. {
  32. public static class Concavity
  33. {
  34. // compute's how 'concave' this object is and returns the total volume of the
  35. // convex hull as well as the volume of the 'concavity' which was found.
  36. public static float computeConcavity(List<float3> vertices, List<int> indices, ref float4 plane, ref float volume)
  37. {
  38. float cret = 0f;
  39. volume = 1f;
  40. HullResult result = new HullResult();
  41. HullDesc desc = new HullDesc();
  42. desc.MaxFaces = 256;
  43. desc.MaxVertices = 256;
  44. desc.SetHullFlag(HullFlag.QF_TRIANGLES);
  45. desc.Vertices = vertices;
  46. HullError ret = HullUtils.CreateConvexHull(desc, ref result);
  47. if (ret == HullError.QE_OK)
  48. {
  49. volume = computeMeshVolume2(result.OutputVertices, result.Indices);
  50. // ok..now..for each triangle on the original mesh..
  51. // we extrude the points to the nearest point on the hull.
  52. List<CTri> tris = new List<CTri>();
  53. for (int i = 0; i < result.Indices.Count / 3; i++)
  54. {
  55. int i1 = result.Indices[i * 3 + 0];
  56. int i2 = result.Indices[i * 3 + 1];
  57. int i3 = result.Indices[i * 3 + 2];
  58. float3 p1 = result.OutputVertices[i1];
  59. float3 p2 = result.OutputVertices[i2];
  60. float3 p3 = result.OutputVertices[i3];
  61. CTri t = new CTri(p1, p2, p3, i1, i2, i3);
  62. tris.Add(t);
  63. }
  64. // we have not pre-computed the plane equation for each triangle in the convex hull..
  65. float totalVolume = 0;
  66. List<CTri> ftris = new List<CTri>(); // 'feature' triangles.
  67. List<CTri> input_mesh = new List<CTri>();
  68. for (int i = 0; i < indices.Count / 3; i++)
  69. {
  70. int i1 = indices[i * 3 + 0];
  71. int i2 = indices[i * 3 + 1];
  72. int i3 = indices[i * 3 + 2];
  73. float3 p1 = vertices[i1];
  74. float3 p2 = vertices[i2];
  75. float3 p3 = vertices[i3];
  76. CTri t = new CTri(p1, p2, p3, i1, i2, i3);
  77. input_mesh.Add(t);
  78. }
  79. for (int i = 0; i < indices.Count / 3; i++)
  80. {
  81. int i1 = indices[i * 3 + 0];
  82. int i2 = indices[i * 3 + 1];
  83. int i3 = indices[i * 3 + 2];
  84. float3 p1 = vertices[i1];
  85. float3 p2 = vertices[i2];
  86. float3 p3 = vertices[i3];
  87. CTri t = new CTri(p1, p2, p3, i1, i2, i3);
  88. featureMatch(t, tris, input_mesh);
  89. if (t.mConcavity > 0.05f)
  90. {
  91. float v = t.getVolume();
  92. totalVolume += v;
  93. ftris.Add(t);
  94. }
  95. }
  96. SplitPlane.computeSplitPlane(vertices, indices, ref plane);
  97. cret = totalVolume;
  98. }
  99. return cret;
  100. }
  101. public static bool featureMatch(CTri m, List<CTri> tris, List<CTri> input_mesh)
  102. {
  103. bool ret = false;
  104. float neardot = 0.707f;
  105. m.mConcavity = 0;
  106. for (int i = 0; i < tris.Count; i++)
  107. {
  108. CTri t = tris[i];
  109. if (t.samePlane(m))
  110. {
  111. ret = false;
  112. break;
  113. }
  114. float dot = float3.dot(t.mNormal, m.mNormal);
  115. if (dot > neardot)
  116. {
  117. float d1 = t.planeDistance(m.mP1);
  118. float d2 = t.planeDistance(m.mP2);
  119. float d3 = t.planeDistance(m.mP3);
  120. if (d1 > 0.001f || d2 > 0.001f || d3 > 0.001f) // can't be near coplaner!
  121. {
  122. neardot = dot;
  123. t.raySect(m.mP1, m.mNormal, ref m.mNear1);
  124. t.raySect(m.mP2, m.mNormal, ref m.mNear2);
  125. t.raySect(m.mP3, m.mNormal, ref m.mNear3);
  126. ret = true;
  127. }
  128. }
  129. }
  130. if (ret)
  131. {
  132. m.mC1 = m.mP1.Distance(m.mNear1);
  133. m.mC2 = m.mP2.Distance(m.mNear2);
  134. m.mC3 = m.mP3.Distance(m.mNear3);
  135. m.mConcavity = m.mC1;
  136. if (m.mC2 > m.mConcavity)
  137. m.mConcavity = m.mC2;
  138. if (m.mC3 > m.mConcavity)
  139. m.mConcavity = m.mC3;
  140. }
  141. return ret;
  142. }
  143. private static float det(float3 p1, float3 p2, float3 p3)
  144. {
  145. return p1.x * p2.y * p3.z + p2.x * p3.y * p1.z + p3.x * p1.y * p2.z - p1.x * p3.y * p2.z - p2.x * p1.y * p3.z - p3.x * p2.y * p1.z;
  146. }
  147. public static float computeMeshVolume(List<float3> vertices, List<int> indices)
  148. {
  149. float volume = 0f;
  150. for (int i = 0; i < indices.Count / 3; i++)
  151. {
  152. float3 p1 = vertices[indices[i * 3 + 0]];
  153. float3 p2 = vertices[indices[i * 3 + 1]];
  154. float3 p3 = vertices[indices[i * 3 + 2]];
  155. volume += det(p1, p2, p3); // compute the volume of the tetrahedran relative to the origin.
  156. }
  157. volume *= (1.0f / 6.0f);
  158. if (volume < 0f)
  159. return -volume;
  160. return volume;
  161. }
  162. public static float computeMeshVolume2(List<float3> vertices, List<int> indices)
  163. {
  164. float volume = 0f;
  165. float3 p0 = vertices[0];
  166. for (int i = 0; i < indices.Count / 3; i++)
  167. {
  168. float3 p1 = vertices[indices[i * 3 + 0]];
  169. float3 p2 = vertices[indices[i * 3 + 1]];
  170. float3 p3 = vertices[indices[i * 3 + 2]];
  171. volume += tetVolume(p0, p1, p2, p3); // compute the volume of the tetrahedron relative to the root vertice
  172. }
  173. return volume * (1.0f / 6.0f);
  174. }
  175. private static float tetVolume(float3 p0, float3 p1, float3 p2, float3 p3)
  176. {
  177. float3 a = p1 - p0;
  178. float3 b = p2 - p0;
  179. float3 c = p3 - p0;
  180. float3 cross = float3.cross(b, c);
  181. float volume = float3.dot(a, cross);
  182. if (volume < 0f)
  183. return -volume;
  184. return volume;
  185. }
  186. }
  187. }