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