aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/Physics/Meshing/SimpleHull.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Region/Physics/Meshing/SimpleHull.cs')
-rw-r--r--OpenSim/Region/Physics/Meshing/SimpleHull.cs394
1 files changed, 0 insertions, 394 deletions
diff --git a/OpenSim/Region/Physics/Meshing/SimpleHull.cs b/OpenSim/Region/Physics/Meshing/SimpleHull.cs
deleted file mode 100644
index 5eeadae..0000000
--- a/OpenSim/Region/Physics/Meshing/SimpleHull.cs
+++ /dev/null
@@ -1,394 +0,0 @@
1/*
2 * Copyright (c) Contributors, http://opensimulator.org/
3 * See CONTRIBUTORS.TXT for a full list of copyright holders.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the OpenSim Project nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28using System;
29using System.Collections.Generic;
30using OpenSim.Region.Physics.Manager;
31
32namespace OpenSim.Region.Physics.Meshing
33{
34 // A simple hull is a set of vertices building up to simplices that border a region
35 // The word simple referes to the fact, that this class assumes, that all simplices
36 // do not intersect
37 // Simple hulls can be added and subtracted.
38 // Vertices can be checked to lie inside a hull
39 // Also note, that the sequence of the vertices is important and defines if the region that
40 // is defined by the hull lies inside or outside the simplex chain
41 public class SimpleHull
42 {
43 //private static readonly log4net.ILog m_log = log4net.LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);
44
45 private List<Vertex> vertices = new List<Vertex>();
46 private List<Vertex> holeVertices = new List<Vertex>(); // Only used, when the hull is hollow
47
48 // Adds a vertex to the end of the list
49 public void AddVertex(Vertex v)
50 {
51 vertices.Add(v);
52 }
53
54 public override String ToString()
55 {
56 String result = String.Empty;
57 foreach (Vertex v in vertices)
58 {
59 result += "b:" + v.ToString() + "\n";
60 }
61
62 return result;
63 }
64
65
66 public List<Vertex> getVertices()
67 {
68 List<Vertex> newVertices = new List<Vertex>();
69
70 newVertices.AddRange(vertices);
71 newVertices.Add(null);
72 newVertices.AddRange(holeVertices);
73
74 return newVertices;
75 }
76
77 public SimpleHull Clone()
78 {
79 SimpleHull result = new SimpleHull();
80 foreach (Vertex v in vertices)
81 {
82 result.AddVertex(v.Clone());
83 }
84
85 foreach (Vertex v in holeVertices)
86 {
87 result.holeVertices.Add(v.Clone());
88 }
89
90 return result;
91 }
92
93 public bool IsPointIn(Vertex v1)
94 {
95 int iCounter = 0;
96 List<Simplex> simplices = buildSimplexList();
97 foreach (Simplex s in simplices)
98 {
99 // Send a ray along the positive X-Direction
100 // Note, that this direction must correlate with the "below" interpretation
101 // of handling for the special cases below
102 PhysicsVector intersection = s.RayIntersect(v1, new PhysicsVector(1.0f, 0.0f, 0.0f), true);
103
104 if (intersection == null)
105 continue; // No intersection. Done. More tests to follow otherwise
106
107 // Did we hit the end of a simplex?
108 // Then this can be one of two special cases:
109 // 1. we go through a border exactly at a joint
110 // 2. we have just marginally touched a corner
111 // 3. we can slide along a border
112 // Solution: If the other vertex is "below" the ray, we don't count it
113 // Thus corners pointing down are counted twice, corners pointing up are not counted
114 // borders are counted once
115 if (intersection.IsIdentical(s.v1, 0.001f))
116 {
117 if (s.v2.Y < v1.Y)
118 continue;
119 }
120 // Do this for the other vertex two
121 if (intersection.IsIdentical(s.v2, 0.001f))
122 {
123 if (s.v1.Y < v1.Y)
124 continue;
125 }
126 iCounter++;
127 }
128
129 return iCounter%2 == 1; // Point is inside if the number of intersections is odd
130 }
131
132 public bool containsPointsFrom(SimpleHull otherHull)
133 {
134 foreach (Vertex v in otherHull.vertices)
135 {
136 if (IsPointIn(v))
137 return true;
138 }
139
140 return false;
141 }
142
143
144 private List<Simplex> buildSimplexList()
145 {
146 List<Simplex> result = new List<Simplex>();
147
148 // Not asserted but assumed: at least three vertices
149 for (int i = 0; i < vertices.Count - 1; i++)
150 {
151 Simplex s = new Simplex(vertices[i], vertices[i + 1]);
152 result.Add(s);
153 }
154 Simplex s1 = new Simplex(vertices[vertices.Count - 1], vertices[0]);
155 result.Add(s1);
156
157 if (holeVertices.Count == 0)
158 return result;
159
160 // Same here. At least three vertices in hole assumed
161 for (int i = 0; i < holeVertices.Count - 1; i++)
162 {
163 Simplex s = new Simplex(holeVertices[i], holeVertices[i + 1]);
164 result.Add(s);
165 }
166
167 s1 = new Simplex(holeVertices[holeVertices.Count - 1], holeVertices[0]);
168 result.Add(s1);
169 return result;
170 }
171
172// TODO: unused
173// private bool InsertVertex(Vertex v, int iAfter)
174// {
175// vertices.Insert(iAfter + 1, v);
176// return true;
177// }
178
179 private Vertex getNextVertex(Vertex currentVertex)
180 {
181 int iCurrentIndex;
182 iCurrentIndex = vertices.IndexOf(currentVertex);
183
184 // Error handling for iCurrentIndex==-1 should go here (and probably never will)
185
186 iCurrentIndex++;
187 if (iCurrentIndex == vertices.Count)
188 iCurrentIndex = 0;
189
190 return vertices[iCurrentIndex];
191 }
192
193 public Vertex FindVertex(Vertex vBase, float tolerance)
194 {
195 foreach (Vertex v in vertices)
196 {
197 if (v.IsIdentical(vBase, tolerance))
198 return v;
199 }
200
201 return null;
202 }
203
204 public void FindIntersection(Simplex s, ref Vertex Intersection, ref Vertex nextVertex)
205 {
206 Vertex bestIntersection = null;
207 float distToV1 = Single.PositiveInfinity;
208 Simplex bestIntersectingSimplex = null;
209
210 List<Simplex> simple = buildSimplexList();
211 foreach (Simplex sTest in simple)
212 {
213 PhysicsVector vvTemp = Simplex.Intersect(sTest, s, -.001f, -.001f, 0.999f, .999f);
214
215 Vertex vTemp = null;
216 if (vvTemp != null)
217 vTemp = new Vertex(vvTemp);
218
219 if (vTemp != null)
220 {
221 PhysicsVector diff = (s.v1 - vTemp);
222 float distTemp = diff.length();
223
224 if (bestIntersection == null || distTemp < distToV1)
225 {
226 bestIntersection = vTemp;
227 distToV1 = distTemp;
228 bestIntersectingSimplex = sTest;
229 }
230 }
231 }
232
233 Intersection = bestIntersection;
234 if (bestIntersectingSimplex != null)
235 nextVertex = bestIntersectingSimplex.v2;
236 else
237 nextVertex = null;
238 }
239
240
241 public static SimpleHull SubtractHull(SimpleHull baseHull, SimpleHull otherHull)
242 {
243 SimpleHull baseHullClone = baseHull.Clone();
244 SimpleHull otherHullClone = otherHull.Clone();
245 bool intersects = false;
246
247 //m_log.Debug("State before intersection detection");
248 //m_log.DebugFormat("The baseHull is:\n{1}", 0, baseHullClone.ToString());
249 //m_log.DebugFormat("The otherHull is:\n{1}", 0, otherHullClone.ToString());
250
251 {
252 int iBase, iOther;
253
254 // Insert into baseHull
255 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
256 {
257 int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count;
258 Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]);
259
260 for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++)
261 {
262 int iOtherNext = (iOther + 1)%otherHullClone.vertices.Count;
263 Simplex sOther =
264 new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]);
265
266 PhysicsVector intersect = Simplex.Intersect(sBase, sOther, 0.001f, -.001f, 0.999f, 1.001f);
267 if (intersect != null)
268 {
269 Vertex vIntersect = new Vertex(intersect);
270 baseHullClone.vertices.Insert(iBase + 1, vIntersect);
271 sBase.v2 = vIntersect;
272 intersects = true;
273 }
274 }
275 }
276 }
277
278 //m_log.Debug("State after intersection detection for the base hull");
279 //m_log.DebugFormat("The baseHull is:\n{1}", 0, baseHullClone.ToString());
280
281 {
282 int iOther, iBase;
283
284 // Insert into otherHull
285 for (iOther = 0; iOther < otherHullClone.vertices.Count; iOther++)
286 {
287 int iOtherNext = (iOther + 1)%otherHullClone.vertices.Count;
288 Simplex sOther = new Simplex(otherHullClone.vertices[iOther], otherHullClone.vertices[iOtherNext]);
289
290 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
291 {
292 int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count;
293 Simplex sBase = new Simplex(baseHullClone.vertices[iBase], baseHullClone.vertices[iBaseNext]);
294
295 PhysicsVector intersect = Simplex.Intersect(sBase, sOther, -.001f, 0.001f, 1.001f, 0.999f);
296 if (intersect != null)
297 {
298 Vertex vIntersect = new Vertex(intersect);
299 otherHullClone.vertices.Insert(iOther + 1, vIntersect);
300 sOther.v2 = vIntersect;
301 intersects = true;
302 }
303 }
304 }
305 }
306
307 //m_log.Debug("State after intersection detection for the base hull");
308 //m_log.DebugFormat("The otherHull is:\n{1}", 0, otherHullClone.ToString());
309
310 bool otherIsInBase = baseHullClone.containsPointsFrom(otherHullClone);
311 if (!intersects && otherIsInBase)
312 {
313 // We have a hole here
314 baseHullClone.holeVertices = otherHullClone.vertices;
315 return baseHullClone;
316 }
317
318 SimpleHull result = new SimpleHull();
319
320 // Find a good starting Simplex from baseHull
321 // A good starting simplex is one that is outside otherHull
322 // Such a simplex must exist, otherwise the result will be empty
323 Vertex baseStartVertex = null;
324 {
325 int iBase;
326 for (iBase = 0; iBase < baseHullClone.vertices.Count; iBase++)
327 {
328 int iBaseNext = (iBase + 1)%baseHullClone.vertices.Count;
329 Vertex center = new Vertex((baseHullClone.vertices[iBase] + baseHullClone.vertices[iBaseNext])/2.0f);
330 bool isOutside = !otherHullClone.IsPointIn(center);
331 if (isOutside)
332 {
333 baseStartVertex = baseHullClone.vertices[iBaseNext];
334 break;
335 }
336 }
337 }
338
339
340 if (baseStartVertex == null) // i.e. no simplex fulfilled the "outside" condition.
341 // In otherwords, subtractHull completely embraces baseHull
342 {
343 return result;
344 }
345
346 // The simplex that *starts* with baseStartVertex is outside the cutting hull,
347 // so we can start our walk with the next vertex without loosing a branch
348 Vertex V1 = baseStartVertex;
349 bool onBase = true;
350
351 // And here is how we do the magic :-)
352 // Start on the base hull.
353 // Walk the vertices in the positive direction
354 // For each vertex check, whether it is a vertex shared with the other hull
355 // if this is the case, switch over to walking the other vertex list.
356 // Note: The other hull *must* go backwards to our starting point (via several orther vertices)
357 // Thus it is important that the cutting hull has the inverse directional sense than the
358 // base hull!!!!!!!!! (means if base goes CW around it's center cutting hull must go CCW)
359
360 bool done = false;
361 while (!done)
362 {
363 result.AddVertex(V1);
364 Vertex nextVertex = null;
365 if (onBase)
366 {
367 nextVertex = otherHullClone.FindVertex(V1, 0.001f);
368 }
369 else
370 {
371 nextVertex = baseHullClone.FindVertex(V1, 0.001f);
372 }
373
374 if (nextVertex != null) // A node that represents an intersection
375 {
376 V1 = nextVertex; // Needed to find the next vertex on the other hull
377 onBase = !onBase;
378 }
379
380 if (onBase)
381 V1 = baseHullClone.getNextVertex(V1);
382 else
383 V1 = otherHullClone.getNextVertex(V1);
384
385 if (V1 == baseStartVertex)
386 done = true;
387 }
388
389 //m_log.DebugFormat("The resulting Hull is:\n{1}", 0, result.ToString());
390
391 return result;
392 }
393 }
394}
generated by cgit v1.1 at 2024-07-08 13:06:57 +0000