aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/Physics/Meshing/SimpleHull.cs
diff options
context:
space:
mode:
authorDahlia Trimble2008-11-29 11:02:14 +0000
committerDahlia Trimble2008-11-29 11:02:14 +0000
commitfdd238833163eb947986bfcdd09da82f6949a5f2 (patch)
tree6b90177758405f6106f4f5d4d75e3b98bf08053c /OpenSim/Region/Physics/Meshing/SimpleHull.cs
parentComment the ScriptSponsor and restore the indefinite lifetime for (diff)
downloadopensim-SC-fdd238833163eb947986bfcdd09da82f6949a5f2.zip
opensim-SC-fdd238833163eb947986bfcdd09da82f6949a5f2.tar.gz
opensim-SC-fdd238833163eb947986bfcdd09da82f6949a5f2.tar.bz2
opensim-SC-fdd238833163eb947986bfcdd09da82f6949a5f2.tar.xz
Update meshing code to sync with current PrimMesher.cs on forge.
Migrate sculpt meshing code to primMesher version. This should result in more accurate physical sculpted prim proxies. Remove much obsolete code from Region/Physics/Meshing
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}