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