diff options
author | Jeff Ames | 2007-11-10 21:20:55 +0000 |
---|---|---|
committer | Jeff Ames | 2007-11-10 21:20:55 +0000 |
commit | 9a4b4dae5e6097b9e70936cfaca483ec7f9120ec (patch) | |
tree | aa83f67a15d68e02e9dfa8b25a45aedf56968653 /OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs | |
parent | * Moves the Meshmerizer to a separate plugin (diff) | |
download | opensim-SC_OLD-9a4b4dae5e6097b9e70936cfaca483ec7f9120ec.zip opensim-SC_OLD-9a4b4dae5e6097b9e70936cfaca483ec7f9120ec.tar.gz opensim-SC_OLD-9a4b4dae5e6097b9e70936cfaca483ec7f9120ec.tar.bz2 opensim-SC_OLD-9a4b4dae5e6097b9e70936cfaca483ec7f9120ec.tar.xz |
removed OdePlugin/Meshing directory
Diffstat (limited to '')
-rwxr-xr-x | OpenSim/Region/Physics/OdePlugin/Meshing/SimpleHull.cs | 363 |
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 @@ | |||
1 | using System; | ||
2 | using System.Collections.Generic; | ||
3 | using System.Text; | ||
4 | |||
5 | using OpenSim.Framework.Console; | ||
6 | |||
7 | namespace 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 | } | ||