diff options
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/Physics/Meshing/SimpleHull.cs | 120 |
1 files changed, 62 insertions, 58 deletions
diff --git a/OpenSim/Region/Physics/Meshing/SimpleHull.cs b/OpenSim/Region/Physics/Meshing/SimpleHull.cs index a769053..809f3d5 100644 --- a/OpenSim/Region/Physics/Meshing/SimpleHull.cs +++ b/OpenSim/Region/Physics/Meshing/SimpleHull.cs | |||
@@ -28,9 +28,8 @@ | |||
28 | 28 | ||
29 | using System; | 29 | using System; |
30 | using System.Collections.Generic; | 30 | using System.Collections.Generic; |
31 | using System.Text; | ||
32 | |||
33 | using OpenSim.Framework.Console; | 31 | using OpenSim.Framework.Console; |
32 | using OpenSim.Region.Physics.Manager; | ||
34 | 33 | ||
35 | namespace OpenSim.Region.Physics.Meshing | 34 | namespace OpenSim.Region.Physics.Meshing |
36 | { | 35 | { |
@@ -43,17 +42,18 @@ namespace OpenSim.Region.Physics.Meshing | |||
43 | // is defined by the hull lies inside or outside the simplex chain | 42 | // is defined by the hull lies inside or outside the simplex chain |
44 | public class SimpleHull | 43 | public class SimpleHull |
45 | { | 44 | { |
46 | List<Vertex> vertices = new List<Vertex>(); | 45 | private List<Vertex> vertices = new List<Vertex>(); |
47 | List<Vertex> holeVertices = new List<Vertex>(); // Only used, when the hull is hollow | 46 | private List<Vertex> holeVertices = new List<Vertex>(); // Only used, when the hull is hollow |
48 | 47 | ||
49 | // Adds a vertex to the end of the list | 48 | // Adds a vertex to the end of the list |
50 | public void AddVertex(Vertex v) { | 49 | public void AddVertex(Vertex v) |
50 | { | ||
51 | vertices.Add(v); | 51 | vertices.Add(v); |
52 | } | 52 | } |
53 | 53 | ||
54 | override public String ToString() | 54 | public override String ToString() |
55 | { | 55 | { |
56 | String result=""; | 56 | String result = ""; |
57 | foreach (Vertex v in vertices) | 57 | foreach (Vertex v in vertices) |
58 | { | 58 | { |
59 | result += "b:" + v.ToString() + "\n"; | 59 | result += "b:" + v.ToString() + "\n"; |
@@ -63,7 +63,8 @@ namespace OpenSim.Region.Physics.Meshing | |||
63 | } | 63 | } |
64 | 64 | ||
65 | 65 | ||
66 | public List<Vertex> getVertices() { | 66 | public List<Vertex> getVertices() |
67 | { | ||
67 | List<Vertex> newVertices = new List<Vertex>(); | 68 | List<Vertex> newVertices = new List<Vertex>(); |
68 | 69 | ||
69 | newVertices.AddRange(vertices); | 70 | newVertices.AddRange(vertices); |
@@ -81,27 +82,27 @@ namespace OpenSim.Region.Physics.Meshing | |||
81 | result.AddVertex(v.Clone()); | 82 | result.AddVertex(v.Clone()); |
82 | } | 83 | } |
83 | 84 | ||
84 | foreach (Vertex v in this.holeVertices) | 85 | foreach (Vertex v in holeVertices) |
85 | { | 86 | { |
86 | result.holeVertices.Add(v.Clone()); | 87 | result.holeVertices.Add(v.Clone()); |
87 | } | 88 | } |
88 | 89 | ||
89 | return result; | 90 | return result; |
90 | } | 91 | } |
91 | 92 | ||
92 | public bool IsPointIn(Vertex v1) | 93 | public bool IsPointIn(Vertex v1) |
93 | { | 94 | { |
94 | int iCounter=0; | 95 | int iCounter = 0; |
95 | List<Simplex> simplices=buildSimplexList(); | 96 | List<Simplex> simplices = buildSimplexList(); |
96 | foreach (Simplex s in simplices) | 97 | foreach (Simplex s in simplices) |
97 | { | 98 | { |
98 | // Send a ray along the positive X-Direction | 99 | // Send a ray along the positive X-Direction |
99 | // Note, that this direction must correlate with the "below" interpretation | 100 | // Note, that this direction must correlate with the "below" interpretation |
100 | // of handling for the special cases below | 101 | // of handling for the special cases below |
101 | Manager.PhysicsVector intersection = s.RayIntersect(v1, new Manager.PhysicsVector(1.0f, 0.0f, 0.0f), true); | 102 | PhysicsVector intersection = s.RayIntersect(v1, new PhysicsVector(1.0f, 0.0f, 0.0f), true); |
102 | 103 | ||
103 | if (intersection == null) | 104 | if (intersection == null) |
104 | continue; // No intersection. Done. More tests to follow otherwise | 105 | continue; // No intersection. Done. More tests to follow otherwise |
105 | 106 | ||
106 | // Did we hit the end of a simplex? | 107 | // Did we hit the end of a simplex? |
107 | // Then this can be one of two special cases: | 108 | // Then this can be one of two special cases: |
@@ -111,19 +112,21 @@ namespace OpenSim.Region.Physics.Meshing | |||
111 | // Solution: If the other vertex is "below" the ray, we don't count it | 112 | // Solution: If the other vertex is "below" the ray, we don't count it |
112 | // Thus corners pointing down are counted twice, corners pointing up are not counted | 113 | // Thus corners pointing down are counted twice, corners pointing up are not counted |
113 | // borders are counted once | 114 | // borders are counted once |
114 | if (intersection.IsIdentical(s.v1, 0.001f)) { | 115 | if (intersection.IsIdentical(s.v1, 0.001f)) |
116 | { | ||
115 | if (s.v2.Y < v1.Y) | 117 | if (s.v2.Y < v1.Y) |
116 | continue; | 118 | continue; |
117 | } | 119 | } |
118 | // Do this for the other vertex two | 120 | // Do this for the other vertex two |
119 | if (intersection.IsIdentical(s.v2, 0.001f)) { | 121 | if (intersection.IsIdentical(s.v2, 0.001f)) |
120 | if (s.v1.Y<v1.Y) | 122 | { |
123 | if (s.v1.Y < v1.Y) | ||
121 | continue; | 124 | continue; |
122 | } | 125 | } |
123 | iCounter++; | 126 | iCounter++; |
124 | } | 127 | } |
125 | 128 | ||
126 | return iCounter % 2 == 1; // Point is inside if the number of intersections is odd | 129 | return iCounter%2 == 1; // Point is inside if the number of intersections is odd |
127 | } | 130 | } |
128 | 131 | ||
129 | public bool containsPointsFrom(SimpleHull otherHull) | 132 | public bool containsPointsFrom(SimpleHull otherHull) |
@@ -138,19 +141,20 @@ namespace OpenSim.Region.Physics.Meshing | |||
138 | } | 141 | } |
139 | 142 | ||
140 | 143 | ||
141 | List<Simplex> buildSimplexList() { | 144 | private List<Simplex> buildSimplexList() |
142 | 145 | { | |
143 | List<Simplex> result = new List<Simplex>(); | 146 | List<Simplex> result = new List<Simplex>(); |
144 | 147 | ||
145 | // Not asserted but assumed: at least three vertices | 148 | // Not asserted but assumed: at least three vertices |
146 | for (int i=0; i<vertices.Count-1; i++) { | 149 | for (int i = 0; i < vertices.Count - 1; i++) |
147 | Simplex s=new Simplex(vertices[i], vertices[i+1]); | 150 | { |
151 | Simplex s = new Simplex(vertices[i], vertices[i + 1]); | ||
148 | result.Add(s); | 152 | result.Add(s); |
149 | } | 153 | } |
150 | Simplex s1=new Simplex(vertices[vertices.Count-1], vertices[0]); | 154 | Simplex s1 = new Simplex(vertices[vertices.Count - 1], vertices[0]); |
151 | result.Add(s1); | 155 | result.Add(s1); |
152 | 156 | ||
153 | if (holeVertices.Count==0) | 157 | if (holeVertices.Count == 0) |
154 | return result; | 158 | return result; |
155 | 159 | ||
156 | // Same here. At least three vertices in hole assumed | 160 | // Same here. At least three vertices in hole assumed |
@@ -159,19 +163,19 @@ namespace OpenSim.Region.Physics.Meshing | |||
159 | Simplex s = new Simplex(holeVertices[i], holeVertices[i + 1]); | 163 | Simplex s = new Simplex(holeVertices[i], holeVertices[i + 1]); |
160 | result.Add(s); | 164 | result.Add(s); |
161 | } | 165 | } |
162 | 166 | ||
163 | s1 = new Simplex(holeVertices[holeVertices.Count - 1], holeVertices[0]); | 167 | s1 = new Simplex(holeVertices[holeVertices.Count - 1], holeVertices[0]); |
164 | result.Add(s1); | 168 | result.Add(s1); |
165 | return result; | 169 | return result; |
166 | } | 170 | } |
167 | 171 | ||
168 | bool InsertVertex(Vertex v, int iAfter) | 172 | private bool InsertVertex(Vertex v, int iAfter) |
169 | { | 173 | { |
170 | vertices.Insert(iAfter + 1, v); | 174 | vertices.Insert(iAfter + 1, v); |
171 | return true; | 175 | return true; |
172 | } | 176 | } |
173 | 177 | ||
174 | Vertex getNextVertex(Vertex currentVertex) | 178 | private Vertex getNextVertex(Vertex currentVertex) |
175 | { | 179 | { |
176 | int iCurrentIndex; | 180 | int iCurrentIndex; |
177 | iCurrentIndex = vertices.IndexOf(currentVertex); | 181 | iCurrentIndex = vertices.IndexOf(currentVertex); |
@@ -185,8 +189,10 @@ namespace OpenSim.Region.Physics.Meshing | |||
185 | return vertices[iCurrentIndex]; | 189 | return vertices[iCurrentIndex]; |
186 | } | 190 | } |
187 | 191 | ||
188 | public Vertex FindVertex(Vertex vBase, float tolerance) { | 192 | public Vertex FindVertex(Vertex vBase, float tolerance) |
189 | foreach (Vertex v in vertices) { | 193 | { |
194 | foreach (Vertex v in vertices) | ||
195 | { | ||
190 | if (v.IsIdentical(vBase, tolerance)) | 196 | if (v.IsIdentical(vBase, tolerance)) |
191 | return v; | 197 | return v; |
192 | } | 198 | } |
@@ -196,32 +202,31 @@ namespace OpenSim.Region.Physics.Meshing | |||
196 | 202 | ||
197 | public void FindIntersection(Simplex s, ref Vertex Intersection, ref Vertex nextVertex) | 203 | public void FindIntersection(Simplex s, ref Vertex Intersection, ref Vertex nextVertex) |
198 | { | 204 | { |
199 | Vertex bestIntersection=null; | 205 | Vertex bestIntersection = null; |
200 | float distToV1=Single.PositiveInfinity; | 206 | float distToV1 = Single.PositiveInfinity; |
201 | Simplex bestIntersectingSimplex=null; | 207 | Simplex bestIntersectingSimplex = null; |
202 | 208 | ||
203 | List<Simplex> simple = buildSimplexList(); | 209 | List<Simplex> simple = buildSimplexList(); |
204 | foreach (Simplex sTest in simple) | 210 | foreach (Simplex sTest in simple) |
205 | { | 211 | { |
206 | Manager.PhysicsVector vvTemp = Simplex.Intersect(sTest, s, -.001f, -.001f, 0.999f, .999f); | 212 | PhysicsVector vvTemp = Simplex.Intersect(sTest, s, -.001f, -.001f, 0.999f, .999f); |
207 | 213 | ||
208 | Vertex vTemp=null; | 214 | Vertex vTemp = null; |
209 | if (vvTemp != null) | 215 | if (vvTemp != null) |
210 | vTemp = new Vertex(vvTemp); | 216 | vTemp = new Vertex(vvTemp); |
211 | 217 | ||
212 | if (vTemp!=null) { | 218 | if (vTemp != null) |
213 | 219 | { | |
214 | Manager.PhysicsVector diff=(s.v1-vTemp); | 220 | PhysicsVector diff = (s.v1 - vTemp); |
215 | float distTemp=diff.length(); | 221 | float distTemp = diff.length(); |
216 | 222 | ||
217 | if (bestIntersection==null || distTemp<distToV1) { | 223 | if (bestIntersection == null || distTemp < distToV1) |
218 | bestIntersection=vTemp; | 224 | { |
219 | distToV1=distTemp; | 225 | bestIntersection = vTemp; |
226 | distToV1 = distTemp; | ||
220 | bestIntersectingSimplex = sTest; | 227 | bestIntersectingSimplex = sTest; |
221 | } | 228 | } |
222 | |||
223 | } // end if vTemp | 229 | } // end if vTemp |
224 | |||
225 | } // end foreach | 230 | } // end foreach |
226 | 231 | ||
227 | Intersection = bestIntersection; | 232 | Intersection = bestIntersection; |
@@ -234,7 +239,6 @@ namespace OpenSim.Region.Physics.Meshing | |||
234 | 239 | ||
235 | public static SimpleHull SubtractHull(SimpleHull baseHull, SimpleHull otherHull) | 240 | public static SimpleHull SubtractHull(SimpleHull baseHull, SimpleHull otherHull) |
236 | { | 241 | { |
237 | |||
238 | SimpleHull baseHullClone = baseHull.Clone(); | 242 | SimpleHull baseHullClone = baseHull.Clone(); |
239 | SimpleHull otherHullClone = otherHull.Clone(); | 243 | SimpleHull otherHullClone = otherHull.Clone(); |
240 | bool intersects = false; | 244 | bool intersects = false; |
@@ -249,15 +253,16 @@ namespace OpenSim.Region.Physics.Meshing | |||
249 | // Insert into baseHull | 253 | // Insert into baseHull |
250 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) | 254 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) |
251 | { | 255 | { |
252 | int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count; | 256 | int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count; |
253 | Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]); | 257 | Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]); |
254 | 258 | ||
255 | for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++) | 259 | for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++) |
256 | { | 260 | { |
257 | int iOtherNext = (iOther + 1) % otherHullClone.vertices.Count; | 261 | int iOtherNext = (iOther + 1)%otherHullClone.vertices.Count; |
258 | Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]); | 262 | Simplex sOther = |
263 | new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]); | ||
259 | 264 | ||
260 | Manager.PhysicsVector intersect = Simplex.Intersect(sBase, sOther, 0.001f, -.001f, 0.999f, 1.001f); | 265 | PhysicsVector intersect = Simplex.Intersect(sBase, sOther, 0.001f, -.001f, 0.999f, 1.001f); |
261 | if (intersect != null) | 266 | if (intersect != null) |
262 | { | 267 | { |
263 | Vertex vIntersect = new Vertex(intersect); | 268 | Vertex vIntersect = new Vertex(intersect); |
@@ -278,15 +283,15 @@ namespace OpenSim.Region.Physics.Meshing | |||
278 | // Insert into otherHull | 283 | // Insert into otherHull |
279 | for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++) | 284 | for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++) |
280 | { | 285 | { |
281 | int iOtherNext = (iOther + 1) % otherHullClone.vertices.Count; | 286 | int iOtherNext = (iOther + 1)%otherHullClone.vertices.Count; |
282 | Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]); | 287 | Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]); |
283 | 288 | ||
284 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) | 289 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) |
285 | { | 290 | { |
286 | int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count; | 291 | int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count; |
287 | Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]); | 292 | Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]); |
288 | 293 | ||
289 | Manager.PhysicsVector intersect = Simplex.Intersect(sBase, sOther, -.001f, 0.001f, 1.001f, 0.999f); | 294 | PhysicsVector intersect = Simplex.Intersect(sBase, sOther, -.001f, 0.001f, 1.001f, 0.999f); |
290 | if (intersect != null) | 295 | if (intersect != null) |
291 | { | 296 | { |
292 | Vertex vIntersect = new Vertex(intersect); | 297 | Vertex vIntersect = new Vertex(intersect); |
@@ -321,8 +326,8 @@ namespace OpenSim.Region.Physics.Meshing | |||
321 | int iBase; | 326 | int iBase; |
322 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) | 327 | for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++) |
323 | { | 328 | { |
324 | int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count; | 329 | int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count; |
325 | Vertex center = new Vertex((baseHullClone.vertices[iBase] + baseHullClone.vertices[iBaseNext]) / 2.0f); | 330 | Vertex center = new Vertex((baseHullClone.vertices[iBase] + baseHullClone.vertices[iBaseNext])/2.0f); |
326 | bool isOutside = !otherHullClone.IsPointIn(center); | 331 | bool isOutside = !otherHullClone.IsPointIn(center); |
327 | if (isOutside) | 332 | if (isOutside) |
328 | { | 333 | { |
@@ -334,7 +339,7 @@ namespace OpenSim.Region.Physics.Meshing | |||
334 | 339 | ||
335 | 340 | ||
336 | if (baseStartVertex == null) // i.e. no simplex fulfilled the "outside" condition. | 341 | if (baseStartVertex == null) // i.e. no simplex fulfilled the "outside" condition. |
337 | // In otherwords, subtractHull completely embraces baseHull | 342 | // In otherwords, subtractHull completely embraces baseHull |
338 | { | 343 | { |
339 | return result; | 344 | return result; |
340 | } | 345 | } |
@@ -369,7 +374,7 @@ namespace OpenSim.Region.Physics.Meshing | |||
369 | 374 | ||
370 | if (nextVertex != null) // A node that represents an intersection | 375 | if (nextVertex != null) // A node that represents an intersection |
371 | { | 376 | { |
372 | V1 = nextVertex; // Needed to find the next vertex on the other hull | 377 | V1 = nextVertex; // Needed to find the next vertex on the other hull |
373 | onBase = !onBase; | 378 | onBase = !onBase; |
374 | } | 379 | } |
375 | 380 | ||
@@ -385,7 +390,6 @@ namespace OpenSim.Region.Physics.Meshing | |||
385 | MainLog.Instance.Debug("The resulting Hull is:\n{1}", 0, result.ToString()); | 390 | MainLog.Instance.Debug("The resulting Hull is:\n{1}", 0, result.ToString()); |
386 | 391 | ||
387 | return result; | 392 | return result; |
388 | |||
389 | } | 393 | } |
390 | } | 394 | } |
391 | } | 395 | } \ No newline at end of file |