aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs')
-rwxr-xr-xOpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs363
1 files changed, 0 insertions, 363 deletions
diff --git a/OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs b/OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs
deleted file mode 100755
index 2caa818..0000000
--- a/OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs
+++ /dev/null
@@ -1,363 +0,0 @@
1using System;
2using System.Collections.Generic;
3using System.Text;
4
5using OpenSim.Framework.Console;
6
7namespace OpenSim.Region.Physics.OdePlugin.Meshing
8{
9 // A simple hull is a set of vertices building up to simplices that border a region
10 // The word simple referes to the fact, that this class assumes, that all simplices
11 // do not intersect
12 // Simple hulls can be added and subtracted.
13 // Vertices can be checked to lie inside a hull
14 // Also note, that the sequence of the vertices is important and defines if the region that
15 // is defined by the hull lies inside or outside the simplex chain
16 public class SimpleHull
17 {
18 List<Vertex> vertices = new List<Vertex>();
19 List<Vertex> holeVertices = new List<Vertex>(); // Only used, when the hull is hollow
20
21 // Adds a vertex to the end of the list
22 public void AddVertex(Vertex v) {
23 vertices.Add(v);
24 }
25
26 override public String ToString()
27 {
28 String result="";
29 foreach (Vertex v in vertices)
30 {
31 result += "b:" + v.ToString() + "\n";
32 }
33
34 return result;
35 }
36
37
38 public List<Vertex> getVertices() {
39 List<Vertex> newVertices = new List<Vertex>();
40
41 newVertices.AddRange(vertices);
42 newVertices.Add(null);
43 newVertices.AddRange(holeVertices);
44
45 return newVertices;
46 }
47
48 public SimpleHull Clone()
49 {
50 SimpleHull result = new SimpleHull();
51 foreach (Vertex v in vertices)
52 {
53 result.AddVertex(v.Clone());
54 }
55
56 foreach (Vertex v in this.holeVertices)
57 {
58 result.holeVertices.Add(v.Clone());
59 }
60
61 return result;
62 }
63
64 public bool IsPointIn(Vertex v1)
65 {
66 int iCounter=0;
67 List<Simplex> simplices=buildSimplexList();
68 foreach (Simplex s in simplices)
69 {
70 // Send a ray along the positive X-Direction
71 // Note, that this direction must correlate with the "below" interpretation
72 // of handling for the special cases below
73 Manager.PhysicsVector intersection = s.RayIntersect(v1, new Manager.PhysicsVector(1.0f, 0.0f, 0.0f), true);
74
75 if (intersection == null)
76 continue; // No intersection. Done. More tests to follow otherwise
77
78 // Did we hit the end of a simplex?
79 // Then this can be one of two special cases:
80 // 1. we go through a border exactly at a joint
81 // 2. we have just marginally touched a corner
82 // 3. we can slide along a border
83 // Solution: If the other vertex is "below" the ray, we don't count it
84 // Thus corners pointing down are counted twice, corners pointing up are not counted
85 // borders are counted once
86 if (intersection.IsIdentical(s.v1, 0.001f)) {
87 if (s.v2.Y < v1.Y)
88 continue;
89 }
90 // Do this for the other vertex two
91 if (intersection.IsIdentical(s.v2, 0.001f)) {
92 if (s.v1.Y<v1.Y)
93 continue;
94 }
95 iCounter++;
96 }
97
98 return iCounter % 2 == 1; // Point is inside if the number of intersections is odd
99 }
100
101 public bool containsPointsFrom(SimpleHull otherHull)
102 {
103 foreach (Vertex v in otherHull.vertices)
104 {
105 if (IsPointIn(v))
106 return true;
107 }
108
109 return false;
110 }
111
112
113 List<Simplex> buildSimplexList() {
114
115 List<Simplex> result = new List<Simplex>();
116
117 // Not asserted but assumed: at least three vertices
118 for (int i=0; i<vertices.Count-1; i++) {
119 Simplex s=new Simplex(vertices[i], vertices[i+1]);
120 result.Add(s);
121 }
122 Simplex s1=new Simplex(vertices[vertices.Count-1], vertices[0]);
123 result.Add(s1);
124
125 if (holeVertices.Count==0)
126 return result;
127
128 // Same here. At least three vertices in hole assumed
129 for (int i = 0; i < holeVertices.Count - 1; i++)
130 {
131 Simplex s = new Simplex(holeVertices[i], holeVertices[i + 1]);
132 result.Add(s);
133 }
134
135 s1 = new Simplex(holeVertices[holeVertices.Count - 1], holeVertices[0]);
136 result.Add(s1);
137 return result;
138 }
139
140 bool InsertVertex(Vertex v, int iAfter)
141 {
142 vertices.Insert(iAfter + 1, v);
143 return true;
144 }
145
146 Vertex getNextVertex(Vertex currentVertex)
147 {
148 int iCurrentIndex;
149 iCurrentIndex = vertices.IndexOf(currentVertex);
150
151 // Error handling for iCurrentIndex==-1 should go here (and probably never will)
152
153 iCurrentIndex++;
154 if (iCurrentIndex == vertices.Count)
155 iCurrentIndex = 0;
156
157 return vertices[iCurrentIndex];
158 }
159
160 public Vertex FindVertex(Vertex vBase, float tolerance) {
161 foreach (Vertex v in vertices) {
162 if (v.IsIdentical(vBase, tolerance))
163 return v;
164 }
165
166 return null;
167 }
168
169 public void FindIntersection(Simplex s, ref Vertex Intersection, ref Vertex nextVertex)
170 {
171 Vertex bestIntersection=null;
172 float distToV1=Single.PositiveInfinity;
173 Simplex bestIntersectingSimplex=null;
174
175 List<Simplex> simple = buildSimplexList();
176 foreach (Simplex sTest in simple)
177 {
178 Manager.PhysicsVector vvTemp = Simplex.Intersect(sTest, s, -.001f, -.001f, 0.999f, .999f);
179
180 Vertex vTemp=null;
181 if (vvTemp != null)
182 vTemp = new Vertex(vvTemp);
183
184 if (vTemp!=null) {
185
186 Manager.PhysicsVector diff=(s.v1-vTemp);
187 float distTemp=diff.length();
188
189 if (bestIntersection==null || distTemp<distToV1) {
190 bestIntersection=vTemp;
191 distToV1=distTemp;
192 bestIntersectingSimplex = sTest;
193 }
194
195 } // end if vTemp
196
197 } // end foreach
198
199 Intersection = bestIntersection;
200 if (bestIntersectingSimplex != null)
201 nextVertex = bestIntersectingSimplex.v2;
202 else
203 nextVertex = null;
204 }
205
206
207 public static SimpleHull SubtractHull(SimpleHull baseHull, SimpleHull otherHull)
208 {
209
210 SimpleHull baseHullClone = baseHull.Clone();
211 SimpleHull otherHullClone = otherHull.Clone();
212 bool intersects = false;
213
214 MainLog.Instance.Debug("State before intersection detection");
215 MainLog.Instance.Debug("The baseHull is:\n{1}", 0, baseHullClone.ToString());
216 MainLog.Instance.Debug("The otherHull is:\n{1}", 0, otherHullClone.ToString());
217
218 {
219 int iBase, iOther;
220
221 // Insert into baseHull
222 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
223 {
224 int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count;
225 Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]);
226
227 for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++)
228 {
229 int iOtherNext = (iOther + 1) % otherHullClone.vertices.Count;
230 Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]);
231
232 Manager.PhysicsVector intersect = Simplex.Intersect(sBase, sOther, 0.001f, -.001f, 0.999f, 1.001f);
233 if (intersect != null)
234 {
235 Vertex vIntersect = new Vertex(intersect);
236 baseHullClone.vertices.Insert(iBase + 1, vIntersect);
237 sBase.v2 = vIntersect;
238 intersects = true;
239 }
240 }
241 }
242 }
243
244 MainLog.Instance.Debug("State after intersection detection for the base hull");
245 MainLog.Instance.Debug("The baseHull is:\n{1}", 0, baseHullClone.ToString());
246
247 {
248 int iOther, iBase;
249
250 // Insert into otherHull
251 for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++)
252 {
253 int iOtherNext = (iOther + 1) % otherHullClone.vertices.Count;
254 Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]);
255
256 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
257 {
258 int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count;
259 Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]);
260
261 Manager.PhysicsVector intersect = Simplex.Intersect(sBase, sOther, -.001f, 0.001f, 1.001f, 0.999f);
262 if (intersect != null)
263 {
264 Vertex vIntersect = new Vertex(intersect);
265 otherHullClone.vertices.Insert(iOther + 1, vIntersect);
266 sOther.v2 = vIntersect;
267 intersects = true;
268 }
269 }
270 }
271 }
272
273 MainLog.Instance.Debug("State after intersection detection for the base hull");
274 MainLog.Instance.Debug("The otherHull is:\n{1}", 0, otherHullClone.ToString());
275
276
277 bool otherIsInBase = baseHullClone.containsPointsFrom(otherHullClone);
278 if (!intersects && otherIsInBase)
279 {
280 // We have a hole here
281 baseHullClone.holeVertices = otherHullClone.vertices;
282 return baseHullClone;
283 }
284
285
286 SimpleHull result = new SimpleHull();
287
288 // Find a good starting Simplex from baseHull
289 // A good starting simplex is one that is outside otherHull
290 // Such a simplex must exist, otherwise the result will be empty
291 Vertex baseStartVertex = null;
292 {
293 int iBase;
294 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
295 {
296 int iBaseNext = (iBase + 1) % baseHullClone.vertices.Count;
297 Vertex center = new Vertex((baseHullClone.vertices[iBase] + baseHullClone.vertices[iBaseNext]) / 2.0f);
298 bool isOutside = !otherHullClone.IsPointIn(center);
299 if (isOutside)
300 {
301 baseStartVertex = baseHullClone.vertices[iBaseNext];
302 break;
303 }
304 }
305 }
306
307
308 if (baseStartVertex == null) // i.e. no simplex fulfilled the "outside" condition.
309 // In otherwords, subtractHull completely embraces baseHull
310 {
311 return result;
312 }
313
314 // The simplex that *starts* with baseStartVertex is outside the cutting hull,
315 // so we can start our walk with the next vertex without loosing a branch
316 Vertex V1 = baseStartVertex;
317 bool onBase = true;
318
319 // And here is how we do the magic :-)
320 // Start on the base hull.
321 // Walk the vertices in the positive direction
322 // For each vertex check, whether it is a vertex shared with the other hull
323 // if this is the case, switch over to walking the other vertex list.
324 // Note: The other hull *must* go backwards to our starting point (via several orther vertices)
325 // Thus it is important that the cutting hull has the inverse directional sense than the
326 // base hull!!!!!!!!! (means if base goes CW around it's center cutting hull must go CCW)
327
328 bool done = false;
329 while (!done)
330 {
331 result.AddVertex(V1);
332 Vertex nextVertex = null;
333 if (onBase)
334 {
335 nextVertex = otherHullClone.FindVertex(V1, 0.001f);
336 }
337 else
338 {
339 nextVertex = baseHullClone.FindVertex(V1, 0.001f);
340 }
341
342 if (nextVertex != null) // A node that represents an intersection
343 {
344 V1 = nextVertex; // Needed to find the next vertex on the other hull
345 onBase = !onBase;
346 }
347
348 if (onBase)
349 V1 = baseHullClone.getNextVertex(V1);
350 else
351 V1 = otherHullClone.getNextVertex(V1);
352
353 if (V1 == baseStartVertex)
354 done = true;
355 }
356
357 MainLog.Instance.Debug("The resulting Hull is:\n{1}", 0, result.ToString());
358
359 return result;
360
361 }
362 }
363}
generated by cgit v1.1 at 2024-07-07 18:58:01 +0000