opensim-development – Blame information for rev 1
?pathlinks?
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 | } |