clockwerk-opensim – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | vero | 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 | } |