ConvexDecomposition.cs 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  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 delegate void ConvexDecompositionCallback(ConvexResult result);
  33. public class FaceTri
  34. {
  35. public float3 P1;
  36. public float3 P2;
  37. public float3 P3;
  38. public FaceTri() { }
  39. public FaceTri(List<float3> vertices, int i1, int i2, int i3)
  40. {
  41. P1 = new float3(vertices[i1]);
  42. P2 = new float3(vertices[i2]);
  43. P3 = new float3(vertices[i3]);
  44. }
  45. }
  46. public static class ConvexDecomposition
  47. {
  48. private static void addTri(VertexPool vl, List<int> list, float3 p1, float3 p2, float3 p3)
  49. {
  50. int i1 = vl.getIndex(p1);
  51. int i2 = vl.getIndex(p2);
  52. int i3 = vl.getIndex(p3);
  53. // do *not* process degenerate triangles!
  54. if ( i1 != i2 && i1 != i3 && i2 != i3 )
  55. {
  56. list.Add(i1);
  57. list.Add(i2);
  58. list.Add(i3);
  59. }
  60. }
  61. public static void calcConvexDecomposition(List<float3> vertices, List<int> indices, ConvexDecompositionCallback callback, float masterVolume, int depth,
  62. int maxDepth, float concavePercent, float mergePercent)
  63. {
  64. float4 plane = new float4();
  65. bool split = false;
  66. if (depth < maxDepth)
  67. {
  68. float volume = 0f;
  69. float c = Concavity.computeConcavity(vertices, indices, ref plane, ref volume);
  70. if (depth == 0)
  71. {
  72. masterVolume = volume;
  73. }
  74. float percent = (c * 100.0f) / masterVolume;
  75. if (percent > concavePercent) // if great than 5% of the total volume is concave, go ahead and keep splitting.
  76. {
  77. split = true;
  78. }
  79. }
  80. if (depth >= maxDepth || !split)
  81. {
  82. HullResult result = new HullResult();
  83. HullDesc desc = new HullDesc();
  84. desc.SetHullFlag(HullFlag.QF_TRIANGLES);
  85. desc.Vertices = vertices;
  86. HullError ret = HullUtils.CreateConvexHull(desc, ref result);
  87. if (ret == HullError.QE_OK)
  88. {
  89. ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices);
  90. callback(r);
  91. }
  92. return;
  93. }
  94. List<int> ifront = new List<int>();
  95. List<int> iback = new List<int>();
  96. VertexPool vfront = new VertexPool();
  97. VertexPool vback = new VertexPool();
  98. // ok..now we are going to 'split' all of the input triangles against this plane!
  99. for (int i = 0; i < indices.Count / 3; i++)
  100. {
  101. int i1 = indices[i * 3 + 0];
  102. int i2 = indices[i * 3 + 1];
  103. int i3 = indices[i * 3 + 2];
  104. FaceTri t = new FaceTri(vertices, i1, i2, i3);
  105. float3[] front = new float3[4];
  106. float3[] back = new float3[4];
  107. int fcount = 0;
  108. int bcount = 0;
  109. PlaneTriResult result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount);
  110. if (fcount > 4 || bcount > 4)
  111. {
  112. result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount);
  113. }
  114. switch (result)
  115. {
  116. case PlaneTriResult.PTR_FRONT:
  117. Debug.Assert(fcount == 3);
  118. addTri(vfront, ifront, front[0], front[1], front[2]);
  119. break;
  120. case PlaneTriResult.PTR_BACK:
  121. Debug.Assert(bcount == 3);
  122. addTri(vback, iback, back[0], back[1], back[2]);
  123. break;
  124. case PlaneTriResult.PTR_SPLIT:
  125. Debug.Assert(fcount >= 3 && fcount <= 4);
  126. Debug.Assert(bcount >= 3 && bcount <= 4);
  127. addTri(vfront, ifront, front[0], front[1], front[2]);
  128. addTri(vback, iback, back[0], back[1], back[2]);
  129. if (fcount == 4)
  130. {
  131. addTri(vfront, ifront, front[0], front[2], front[3]);
  132. }
  133. if (bcount == 4)
  134. {
  135. addTri(vback, iback, back[0], back[2], back[3]);
  136. }
  137. break;
  138. }
  139. }
  140. // ok... here we recursively call
  141. if (ifront.Count > 0)
  142. {
  143. int vcount = vfront.GetSize();
  144. List<float3> vertices2 = vfront.GetVertices();
  145. for (int i = 0; i < vertices2.Count; i++)
  146. vertices2[i] = new float3(vertices2[i]);
  147. int tcount = ifront.Count / 3;
  148. calcConvexDecomposition(vertices2, ifront, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent);
  149. }
  150. ifront.Clear();
  151. vfront.Clear();
  152. if (iback.Count > 0)
  153. {
  154. int vcount = vback.GetSize();
  155. List<float3> vertices2 = vback.GetVertices();
  156. int tcount = iback.Count / 3;
  157. calcConvexDecomposition(vertices2, iback, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent);
  158. }
  159. iback.Clear();
  160. vback.Clear();
  161. }
  162. }
  163. }