clockwerk-opensim – Blame information for rev 1

Subversion Repositories:
Rev:
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 }