diff options
author | Robert Adams | 2011-06-20 17:14:59 -0700 |
---|---|---|
committer | Dan Lake | 2011-06-20 17:24:42 -0700 |
commit | 302d72701da35b6d481a538c4cb953976d7e9044 (patch) | |
tree | fe11403b00e640da659c48dddbc9646860380ccd /OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexDecomposition.cs | |
parent | Merge branch 'master' of ssh://opensimulator.org/var/git/opensim (diff) | |
download | opensim-SC-302d72701da35b6d481a538c4cb953976d7e9044.zip opensim-SC-302d72701da35b6d481a538c4cb953976d7e9044.tar.gz opensim-SC-302d72701da35b6d481a538c4cb953976d7e9044.tar.bz2 opensim-SC-302d72701da35b6d481a538c4cb953976d7e9044.tar.xz |
BulletSim initial checkin
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexDecomposition.cs | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexDecomposition.cs b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexDecomposition.cs new file mode 100644 index 0000000..2e2bb70 --- /dev/null +++ b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexDecomposition.cs | |||
@@ -0,0 +1,200 @@ | |||
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.Diagnostics; | ||
31 | |||
32 | namespace OpenSim.Region.Physics.ConvexDecompositionDotNet | ||
33 | { | ||
34 | public delegate void ConvexDecompositionCallback(ConvexResult result); | ||
35 | |||
36 | public class FaceTri | ||
37 | { | ||
38 | public float3 P1; | ||
39 | public float3 P2; | ||
40 | public float3 P3; | ||
41 | |||
42 | public FaceTri() { } | ||
43 | |||
44 | public FaceTri(List<float3> vertices, int i1, int i2, int i3) | ||
45 | { | ||
46 | P1 = new float3(vertices[i1]); | ||
47 | P2 = new float3(vertices[i2]); | ||
48 | P3 = new float3(vertices[i3]); | ||
49 | } | ||
50 | } | ||
51 | |||
52 | public static class ConvexDecomposition | ||
53 | { | ||
54 | private static void addTri(VertexPool vl, List<int> list, float3 p1, float3 p2, float3 p3) | ||
55 | { | ||
56 | int i1 = vl.getIndex(p1); | ||
57 | int i2 = vl.getIndex(p2); | ||
58 | int i3 = vl.getIndex(p3); | ||
59 | |||
60 | // do *not* process degenerate triangles! | ||
61 | if ( i1 != i2 && i1 != i3 && i2 != i3 ) | ||
62 | { | ||
63 | list.Add(i1); | ||
64 | list.Add(i2); | ||
65 | list.Add(i3); | ||
66 | } | ||
67 | } | ||
68 | |||
69 | public static void calcConvexDecomposition(List<float3> vertices, List<int> indices, ConvexDecompositionCallback callback, float masterVolume, int depth, | ||
70 | int maxDepth, float concavePercent, float mergePercent) | ||
71 | { | ||
72 | float4 plane = new float4(); | ||
73 | bool split = false; | ||
74 | |||
75 | if (depth < maxDepth) | ||
76 | { | ||
77 | float volume = 0f; | ||
78 | float c = Concavity.computeConcavity(vertices, indices, ref plane, ref volume); | ||
79 | |||
80 | if (depth == 0) | ||
81 | { | ||
82 | masterVolume = volume; | ||
83 | } | ||
84 | |||
85 | float percent = (c * 100.0f) / masterVolume; | ||
86 | |||
87 | if (percent > concavePercent) // if great than 5% of the total volume is concave, go ahead and keep splitting. | ||
88 | { | ||
89 | split = true; | ||
90 | } | ||
91 | } | ||
92 | |||
93 | if (depth >= maxDepth || !split) | ||
94 | { | ||
95 | HullResult result = new HullResult(); | ||
96 | HullDesc desc = new HullDesc(); | ||
97 | |||
98 | desc.SetHullFlag(HullFlag.QF_TRIANGLES); | ||
99 | |||
100 | desc.Vertices = vertices; | ||
101 | |||
102 | HullError ret = HullUtils.CreateConvexHull(desc, ref result); | ||
103 | |||
104 | if (ret == HullError.QE_OK) | ||
105 | { | ||
106 | ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices); | ||
107 | callback(r); | ||
108 | } | ||
109 | |||
110 | return; | ||
111 | } | ||
112 | |||
113 | List<int> ifront = new List<int>(); | ||
114 | List<int> iback = new List<int>(); | ||
115 | |||
116 | VertexPool vfront = new VertexPool(); | ||
117 | VertexPool vback = new VertexPool(); | ||
118 | |||
119 | // ok..now we are going to 'split' all of the input triangles against this plane! | ||
120 | for (int i = 0; i < indices.Count / 3; i++) | ||
121 | { | ||
122 | int i1 = indices[i * 3 + 0]; | ||
123 | int i2 = indices[i * 3 + 1]; | ||
124 | int i3 = indices[i * 3 + 2]; | ||
125 | |||
126 | FaceTri t = new FaceTri(vertices, i1, i2, i3); | ||
127 | |||
128 | float3[] front = new float3[4]; | ||
129 | float3[] back = new float3[4]; | ||
130 | |||
131 | int fcount = 0; | ||
132 | int bcount = 0; | ||
133 | |||
134 | PlaneTriResult result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount); | ||
135 | |||
136 | if (fcount > 4 || bcount > 4) | ||
137 | { | ||
138 | result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount); | ||
139 | } | ||
140 | |||
141 | switch (result) | ||
142 | { | ||
143 | case PlaneTriResult.PTR_FRONT: | ||
144 | Debug.Assert(fcount == 3); | ||
145 | addTri(vfront, ifront, front[0], front[1], front[2]); | ||
146 | break; | ||
147 | case PlaneTriResult.PTR_BACK: | ||
148 | Debug.Assert(bcount == 3); | ||
149 | addTri(vback, iback, back[0], back[1], back[2]); | ||
150 | break; | ||
151 | case PlaneTriResult.PTR_SPLIT: | ||
152 | Debug.Assert(fcount >= 3 && fcount <= 4); | ||
153 | Debug.Assert(bcount >= 3 && bcount <= 4); | ||
154 | |||
155 | addTri(vfront, ifront, front[0], front[1], front[2]); | ||
156 | addTri(vback, iback, back[0], back[1], back[2]); | ||
157 | |||
158 | if (fcount == 4) | ||
159 | { | ||
160 | addTri(vfront, ifront, front[0], front[2], front[3]); | ||
161 | } | ||
162 | |||
163 | if (bcount == 4) | ||
164 | { | ||
165 | addTri(vback, iback, back[0], back[2], back[3]); | ||
166 | } | ||
167 | |||
168 | break; | ||
169 | } | ||
170 | } | ||
171 | |||
172 | // ok... here we recursively call | ||
173 | if (ifront.Count > 0) | ||
174 | { | ||
175 | int vcount = vfront.GetSize(); | ||
176 | List<float3> vertices2 = vfront.GetVertices(); | ||
177 | for (int i = 0; i < vertices2.Count; i++) | ||
178 | vertices2[i] = new float3(vertices2[i]); | ||
179 | int tcount = ifront.Count / 3; | ||
180 | |||
181 | calcConvexDecomposition(vertices2, ifront, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent); | ||
182 | } | ||
183 | |||
184 | ifront.Clear(); | ||
185 | vfront.Clear(); | ||
186 | |||
187 | if (iback.Count > 0) | ||
188 | { | ||
189 | int vcount = vback.GetSize(); | ||
190 | List<float3> vertices2 = vback.GetVertices(); | ||
191 | int tcount = iback.Count / 3; | ||
192 | |||
193 | calcConvexDecomposition(vertices2, iback, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent); | ||
194 | } | ||
195 | |||
196 | iback.Clear(); | ||
197 | vback.Clear(); | ||
198 | } | ||
199 | } | ||
200 | } | ||