aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs')
-rw-r--r--OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs560
1 files changed, 560 insertions, 0 deletions
diff --git a/OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs b/OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs
new file mode 100644
index 0000000..28dca41
--- /dev/null
+++ b/OpenSim/Region/Physics/OdePlugin/Meshing\/Meshmerizer.cs
@@ -0,0 +1,560 @@
1using System;
2using System.Globalization;
3using System.Diagnostics;
4using System.Collections.Generic;
5using System.Text;
6using System.Runtime.InteropServices;
7
8using OpenSim.Framework.Types;
9using OpenSim.Region.Physics.Manager;
10
11namespace OpenSim.Region.Physics.OdePlugin
12{
13 public class Mesh
14 {
15 public List<Vertex> vertices;
16 public List<Triangle> triangles;
17
18 public float[] normals;
19
20 public Mesh()
21 {
22 vertices = new List<Vertex>();
23 triangles = new List<Triangle>();
24 }
25
26 public void Add(Triangle triangle)
27 {
28 int i;
29 i = vertices.IndexOf(triangle.v1);
30 if (i < 0)
31 throw new ArgumentException("Vertex v1 not known to mesh");
32 i = vertices.IndexOf(triangle.v2);
33 if (i < 0)
34 throw new ArgumentException("Vertex v2 not known to mesh");
35 i = vertices.IndexOf(triangle.v3);
36 if (i < 0)
37 throw new ArgumentException("Vertex v3 not known to mesh");
38
39 triangles.Add(triangle);
40 }
41
42 public void Add(Vertex v)
43 {
44 vertices.Add(v);
45 }
46
47
48 public float[] getVertexListAsFloat()
49 {
50 float[] result = new float[vertices.Count * 3];
51 for (int i = 0; i < vertices.Count; i++)
52 {
53 Vertex v = vertices[i];
54 PhysicsVector point = v.point;
55 result[3 * i + 0] = point.X;
56 result[3 * i + 1] = point.Y;
57 result[3 * i + 2] = point.Z;
58 }
59 GCHandle.Alloc(result, GCHandleType.Pinned);
60 return result;
61 }
62
63 public int[] getIndexListAsInt()
64 {
65 int[] result = new int[triangles.Count * 3];
66 for (int i = 0; i < triangles.Count; i++)
67 {
68 Triangle t = triangles[i];
69 result[3 * i + 0] = vertices.IndexOf(t.v1);
70 result[3 * i + 1] = vertices.IndexOf(t.v2);
71 result[3 * i + 2] = vertices.IndexOf(t.v3);
72 }
73 GCHandle.Alloc(result, GCHandleType.Pinned);
74 return result;
75 }
76
77
78 public void Append(Mesh newMesh)
79 {
80 foreach (Vertex v in newMesh.vertices)
81 vertices.Add(v);
82
83 foreach (Triangle t in newMesh.triangles)
84 Add(t);
85
86 }
87 }
88
89
90
91 public class Meshmerizer
92 {
93
94 static List<Triangle> FindInfluencedTriangles(List<Triangle> triangles, Vertex v)
95 {
96 List<Triangle> influenced = new List<Triangle>();
97 foreach (Triangle t in triangles)
98 {
99 float dx, dy;
100
101 if (t.isInCircle(v.point.X, v.point.Y))
102 {
103 influenced.Add(t);
104 }
105 }
106 return influenced;
107 }
108
109
110 static void InsertVertices(List<Vertex> vertices, int usedForSeed, List<Triangle> triangles, List<int> innerBorders)
111 {
112 // This is a variant of the delaunay algorithm
113 // each time a new vertex is inserted, all triangles that are influenced by it are deleted
114 // and replaced by new ones including the new vertex
115 // It is not very time efficient but easy to implement.
116
117 int iCurrentVertex;
118 int iMaxVertex=vertices.Count;
119 for (iCurrentVertex = usedForSeed; iCurrentVertex < iMaxVertex; iCurrentVertex++)
120 {
121 // Background: A triangle mesh fulfills the delaunay condition if (iff!)
122 // each circumlocutory circle (i.e. the circle that touches all three corners)
123 // of each triangle is empty of other vertices.
124 // Obviously a single (seeding) triangle fulfills this condition.
125 // If we now add one vertex, we need to reconstruct all triangles, that
126 // do not fulfill this condition with respect to the new triangle
127
128 // Find the triangles that are influenced by the new vertex
129 Vertex v=vertices[iCurrentVertex];
130 List<Triangle> influencedTriangles=FindInfluencedTriangles(triangles, v);
131
132 List<Simplex> simplices = new List<Simplex>();
133
134 // Reconstruction phase. First step, dissolve each triangle into it's simplices,
135 // i.e. it's "border lines"
136 // Goal is to find "inner" borders and delete them, while the hull gets conserved.
137 // Inner borders are special in the way that they always come twice, which is how we detect them
138 foreach (Triangle t in influencedTriangles)
139 {
140 List<Simplex> newSimplices = t.GetSimplices();
141 simplices.AddRange(newSimplices);
142 triangles.Remove(t);
143 }
144 // Now sort the simplices. That will make identical ones side by side in the list
145 simplices.Sort();
146
147 // Look for duplicate simplices here.
148 // Remember, they are directly side by side in the list right now
149 int iSimplex;
150 List<Simplex> innerSimplices=new List<Simplex>();
151 for (iSimplex = 1; iSimplex < simplices.Count; iSimplex++) // Startindex=1, so we can refer backwards
152 {
153 if (simplices[iSimplex - 1].CompareTo(simplices[iSimplex])==0)
154 {
155 innerSimplices.Add(simplices[iSimplex - 1]);
156 innerSimplices.Add(simplices[iSimplex]);
157 }
158 }
159
160 foreach (Simplex s in innerSimplices)
161 {
162 simplices.Remove(s);
163 }
164
165 // each simplex still in the list belongs to the hull of the region in question
166 // The new vertex (yes, we still deal with verices here :-) ) forms a triangle
167 // With each of these simplices. Build the new triangles and add them to the list
168 foreach (Simplex s in simplices)
169 {
170 Triangle t = new Triangle(s.v1, s.v2, vertices[iCurrentVertex]);
171 triangles.Add(t);
172 }
173 }
174
175 // At this point all vertices should be inserted into the mesh
176 // But the areas, that should be kept free still are filled with triangles
177 // We have to remove them. For this we have a list of indices to vertices.
178 // Each triangle that solemnly constists of vertices from the inner border
179 // are deleted
180
181 List<Triangle> innerTriangles = new List<Triangle>();
182 foreach (Triangle t in triangles)
183 {
184 if (
185 innerBorders.Contains(vertices.IndexOf(t.v1))
186 && innerBorders.Contains(vertices.IndexOf(t.v2))
187 && innerBorders.Contains(vertices.IndexOf(t.v3))
188 )
189 innerTriangles.Add(t);
190 }
191 foreach (Triangle t in innerTriangles)
192 {
193 triangles.Remove(t);
194 }
195 }
196
197
198 static Mesh CreateBoxMeshX(PrimitiveBaseShape primShape, PhysicsVector size)
199 // Builds the x (+ and -) surfaces of a box shaped prim
200 {
201 UInt16 hollowFactor = primShape.ProfileHollow;
202 Mesh meshMX = new Mesh();
203
204
205 // Surface 0, -X
206 meshMX.Add(new Vertex("-X-Y-Z", -size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
207 meshMX.Add(new Vertex("-X+Y-Z", -size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
208 meshMX.Add(new Vertex("-X-Y+Z", -size.X / 2.0f, -size.Y / 2.0f, +size.Z / 2.0f));
209 meshMX.Add(new Vertex("-X+Y+Z", -size.X / 2.0f, +size.Y / 2.0f, +size.Z / 2.0f));
210
211 meshMX.Add(new Triangle(meshMX.vertices[0], meshMX.vertices[2], meshMX.vertices[1]));
212 meshMX.Add(new Triangle(meshMX.vertices[1], meshMX.vertices[2], meshMX.vertices[3]));
213
214
215 Mesh meshPX = new Mesh();
216 // Surface 1, +X
217 meshPX.Add(new Vertex("+X-Y-Z", +size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
218 meshPX.Add(new Vertex("+X+Y-Z", +size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
219 meshPX.Add(new Vertex("+X-Y+Z", +size.X / 2.0f, -size.Y / 2.0f, +size.Z / 2.0f));
220 meshPX.Add(new Vertex("+X+Y+Z", +size.X / 2.0f, +size.Y / 2.0f, +size.Z / 2.0f));
221
222
223 meshPX.Add(new Triangle(meshPX.vertices[0], meshPX.vertices[1], meshPX.vertices[2]));
224 meshPX.Add(new Triangle(meshPX.vertices[2], meshPX.vertices[1], meshPX.vertices[3]));
225
226
227 if (hollowFactor > 0)
228 {
229 float hollowFactorF = (float)hollowFactor / (float)50000;
230
231 Vertex IPP;
232 Vertex IPM;
233 Vertex IMP;
234 Vertex IMM;
235
236 IPP = new Vertex("Inner-X+Y+Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
237 IPM = new Vertex("Inner-X+Y-Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
238 IMP = new Vertex("Inner-X-Y+Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
239 IMM = new Vertex("Inner-X-Y-Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
240
241 meshMX.Add(IPP);
242 meshMX.Add(IPM);
243 meshMX.Add(IMP);
244 meshMX.Add(IMM);
245
246 meshMX.Add(new Triangle(IPP, IMP, IPM));
247 meshMX.Add(new Triangle(IPM, IMP, IMM));
248
249 foreach (Triangle t in meshMX.triangles)
250 {
251 PhysicsVector n = t.getNormal();
252 }
253
254
255
256 IPP = new Vertex("Inner+X+Y+Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
257 IPM = new Vertex("Inner+X+Y-Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
258 IMP = new Vertex("Inner+X-Y+Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
259 IMM = new Vertex("Inner+X-Y-Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
260
261 meshPX.Add(IPP);
262 meshPX.Add(IPM);
263 meshPX.Add(IMP);
264 meshPX.Add(IMM);
265
266 meshPX.Add(new Triangle(IPP, IPM, IMP));
267 meshPX.Add(new Triangle(IMP, IPM, IMM));
268
269 foreach (Triangle t in meshPX.triangles)
270 {
271 PhysicsVector n = t.getNormal();
272 }
273 }
274
275 Mesh result = new Mesh();
276 result.Append(meshMX);
277 result.Append(meshPX);
278
279 return result;
280 }
281
282
283
284 static Mesh CreateBoxMeshY(PrimitiveBaseShape primShape, PhysicsVector size)
285 // Builds the y (+ and -) surfaces of a box shaped prim
286 {
287 UInt16 hollowFactor = primShape.ProfileHollow;
288
289 // (M)inus Y
290 Mesh MeshMY = new Mesh();
291 MeshMY.Add(new Vertex("-X-Y-Z", -size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
292 MeshMY.Add(new Vertex("+X-Y-Z", +size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
293 MeshMY.Add(new Vertex("-X-Y+Z", -size.X / 2.0f, -size.Y / 2.0f, +size.Z / 2.0f));
294 MeshMY.Add(new Vertex("+X-Y+Z", +size.X / 2.0f, -size.Y / 2.0f, +size.Z / 2.0f));
295
296 MeshMY.Add(new Triangle(MeshMY.vertices[0], MeshMY.vertices[1], MeshMY.vertices[2]));
297 MeshMY.Add(new Triangle(MeshMY.vertices[2], MeshMY.vertices[1], MeshMY.vertices[3]));
298
299 // (P)lus Y
300 Mesh MeshPY = new Mesh();
301
302 MeshPY.Add(new Vertex("-X+Y-Z", -size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
303 MeshPY.Add(new Vertex("+X+Y-Z", +size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
304 MeshPY.Add(new Vertex("-X+Y+Z", -size.X / 2.0f, +size.Y / 2.0f, +size.Z / 2.0f));
305 MeshPY.Add(new Vertex("+X+Y+Z", +size.X / 2.0f, +size.Y / 2.0f, +size.Z / 2.0f));
306
307 MeshPY.Add(new Triangle(MeshPY.vertices[1], MeshPY.vertices[0], MeshPY.vertices[2]));
308 MeshPY.Add(new Triangle(MeshPY.vertices[1], MeshPY.vertices[2], MeshPY.vertices[3]));
309
310 if (hollowFactor > 0)
311 {
312 float hollowFactorF = (float)hollowFactor / (float)50000;
313
314 Vertex IPP;
315 Vertex IPM;
316 Vertex IMP;
317 Vertex IMM;
318
319 IPP = new Vertex("Inner+X-Y+Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
320 IPM = new Vertex("Inner+X-Y-Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
321 IMP = new Vertex("Inner-X-Y+Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
322 IMM = new Vertex("Inner-X-Y-Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
323
324 MeshMY.Add(IPP);
325 MeshMY.Add(IPM);
326 MeshMY.Add(IMP);
327 MeshMY.Add(IMM);
328
329 MeshMY.Add(new Triangle(IPP, IPM, IMP));
330 MeshMY.Add(new Triangle(IMP, IPM, IMM));
331
332 foreach (Triangle t in MeshMY.triangles)
333 {
334 PhysicsVector n = t.getNormal();
335 }
336
337
338
339 IPP = new Vertex("Inner+X+Y+Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
340 IPM=new Vertex("Inner+X+Y-Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
341 IMP=new Vertex("Inner-X+Y+Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, +size.Z / 2.0f);
342 IMM=new Vertex("Inner-X+Y-Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, -size.Z / 2.0f);
343
344 MeshPY.Add(IPP);
345 MeshPY.Add(IPM);
346 MeshPY.Add(IMP);
347 MeshPY.Add(IMM);
348
349 MeshPY.Add(new Triangle(IPM, IPP, IMP));
350 MeshPY.Add(new Triangle(IMP, IMM, IPM));
351
352 foreach (Triangle t in MeshPY.triangles)
353 {
354 PhysicsVector n = t.getNormal();
355 }
356
357
358
359 }
360
361
362 Mesh result = new Mesh();
363 result.Append(MeshMY);
364 result.Append(MeshPY);
365
366 return result;
367 }
368
369 static Mesh CreateBoxMeshZ(PrimitiveBaseShape primShape, PhysicsVector size)
370 // Builds the z (+ and -) surfaces of a box shaped prim
371 {
372 UInt16 hollowFactor = primShape.ProfileHollow;
373
374 // Base, i.e. outer shape
375 // (M)inus Z
376 Mesh MZ = new Mesh();
377
378 MZ.Add(new Vertex("-X-Y-Z", -size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
379 MZ.Add(new Vertex("+X-Y-Z", +size.X / 2.0f, -size.Y / 2.0f, -size.Z / 2.0f));
380 MZ.Add(new Vertex("-X+Y-Z", -size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
381 MZ.Add(new Vertex("+X+Y-Z", +size.X / 2.0f, +size.Y / 2.0f, -size.Z / 2.0f));
382
383
384 MZ.Add(new Triangle(MZ.vertices[1], MZ.vertices[0], MZ.vertices[2]));
385 MZ.Add(new Triangle(MZ.vertices[1], MZ.vertices[2], MZ.vertices[3]));
386
387 // (P)lus Z
388 Mesh PZ = new Mesh();
389
390 PZ.Add(new Vertex("-X-Y+Z", -size.X / 2.0f, -size.Y / 2.0f, 0.0f));
391 PZ.Add(new Vertex("+X-Y+Z", +size.X / 2.0f, -size.Y / 2.0f, 0.0f));
392 PZ.Add(new Vertex("-X+Y+Z", -size.X / 2.0f, +size.Y / 2.0f, 0.0f));
393 PZ.Add(new Vertex("+X+Y+Z", +size.X / 2.0f, +size.Y / 2.0f, 0.0f));
394
395 // Surface 5, +Z
396 PZ.Add(new Triangle(PZ.vertices[0], PZ.vertices[1], PZ.vertices[2]));
397 PZ.Add(new Triangle(PZ.vertices[2], PZ.vertices[1], PZ.vertices[3]));
398
399 if (hollowFactor > 0)
400 {
401 float hollowFactorF = (float)hollowFactor / (float)50000;
402
403 MZ.Add(new Vertex("-X-Y-Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, 0.0f));
404 MZ.Add(new Vertex("-X+Y-Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, 0.0f));
405 MZ.Add(new Vertex("-X-Y+Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, 0.0f));
406 MZ.Add(new Vertex("-X+Y+Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, 0.0f));
407
408 List<int> innerBorders = new List<int>();
409 innerBorders.Add(4);
410 innerBorders.Add(5);
411 innerBorders.Add(6);
412 innerBorders.Add(7);
413
414 InsertVertices(MZ.vertices, 4, MZ.triangles, innerBorders);
415
416 PZ.Add(new Vertex("-X-Y-Z", -size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, 0.0f));
417 PZ.Add(new Vertex("-X+Y-Z", +size.X * hollowFactorF / 2.0f, -size.Y * hollowFactorF / 2.0f, 0.0f));
418 PZ.Add(new Vertex("-X-Y+Z", -size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, 0.0f));
419 PZ.Add(new Vertex("-X+Y+Z", +size.X * hollowFactorF / 2.0f, +size.Y * hollowFactorF / 2.0f, 0.0f));
420
421 innerBorders = new List<int>();
422 innerBorders.Add(4);
423 innerBorders.Add(5);
424 innerBorders.Add(6);
425 innerBorders.Add(7);
426
427 InsertVertices(PZ.vertices, 4, PZ.triangles, innerBorders);
428
429 }
430
431 foreach (Vertex v in PZ.vertices)
432 {
433 v.point.Z = size.Z / 2.0f;
434 }
435 foreach (Vertex v in MZ.vertices)
436 {
437 v.point.Z = -size.Z / 2.0f;
438 }
439
440 foreach (Triangle t in MZ.triangles)
441 {
442 PhysicsVector n = t.getNormal();
443 if (n.Z > 0.0)
444 t.invertNormal();
445 }
446
447 foreach (Triangle t in PZ.triangles)
448 {
449 PhysicsVector n = t.getNormal();
450 if (n.Z < 0.0)
451 t.invertNormal();
452 }
453
454 Mesh result = new Mesh();
455 result.Append(MZ);
456 result.Append(PZ);
457
458 return result;
459 }
460
461 static Mesh CreateBoxMesh(PrimitiveBaseShape primShape, PhysicsVector size)
462 {
463 Mesh result = new Mesh();
464
465
466
467 Mesh MeshX = Meshmerizer.CreateBoxMeshX(primShape, size);
468 Mesh MeshY = Meshmerizer.CreateBoxMeshY(primShape, size);
469 Mesh MeshZ = Meshmerizer.CreateBoxMeshZ(primShape, size);
470
471 result.Append(MeshX);
472 result.Append(MeshY);
473 result.Append(MeshZ);
474
475 return result;
476 }
477
478
479 public static void CalcNormals(Mesh mesh)
480 {
481 int iTriangles = mesh.triangles.Count;
482
483 mesh.normals = new float[iTriangles*3];
484
485 int i=0;
486 foreach (Triangle t in mesh.triangles)
487 {
488
489 float ux, uy, uz;
490 float vx, vy, vz;
491 float wx, wy, wz;
492
493 ux = t.v1.point.X;
494 uy = t.v1.point.Y;
495 uz = t.v1.point.Z;
496
497 vx = t.v2.point.X;
498 vy = t.v2.point.Y;
499 vz = t.v2.point.Z;
500
501 wx = t.v3.point.X;
502 wy = t.v3.point.Y;
503 wz = t.v3.point.Z;
504
505 // Vectors for edges
506 float e1x, e1y, e1z;
507 float e2x, e2y, e2z;
508
509 e1x = ux - vx;
510 e1y = uy - vy;
511 e1z = uz - vz;
512
513 e2x = ux - wx;
514 e2y = uy - wy;
515 e2z = uz - wz;
516
517
518 // Cross product for normal
519 float nx, ny, nz;
520 nx = e1y * e2z - e1z * e2y;
521 ny = e1z * e2x - e1x * e2z;
522 nz = e1x * e2y - e1y * e2x;
523
524 // Length
525 float l = (float)Math.Sqrt(nx * nx + ny * ny + nz * nz);
526
527 // Normalized "normal"
528 nx /= l;
529 ny /= l;
530 nz /= l;
531
532 mesh.normals[i] = nx;
533 mesh.normals[i + 1] = ny;
534 mesh.normals[i + 2] = nz;
535
536 i+=3;
537 }
538 }
539
540 public static Mesh CreateMesh(PrimitiveBaseShape primShape, PhysicsVector size)
541 {
542 Mesh mesh = null;
543
544 switch (primShape.ProfileShape)
545 {
546 case ProfileShape.Square:
547 mesh=CreateBoxMesh(primShape, size);
548 CalcNormals(mesh);
549 break;
550 default:
551 mesh=null;
552 break;
553 }
554
555 return mesh;
556
557 }
558 }
559}
560
generated by cgit v1.1 at 2024-11-10 21:50:46 +0000