From 134f86e8d5c414409631b25b8c6f0ee45fbd8631 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Thu, 3 Nov 2016 21:44:39 +1000 Subject: Initial update to OpenSim 0.8.2.1 source code. --- .../ConvexDecomposition.cs | 200 +++++++++++++++++++++ 1 file changed, 200 insertions(+) create mode 100644 OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/ConvexDecomposition.cs (limited to 'OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/ConvexDecomposition.cs') diff --git a/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/ConvexDecomposition.cs b/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/ConvexDecomposition.cs new file mode 100644 index 0000000..5046bce --- /dev/null +++ b/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/ConvexDecomposition.cs @@ -0,0 +1,200 @@ +/* The MIT License + * + * Copyright (c) 2010 Intel Corporation. + * All rights reserved. + * + * Based on the convexdecomposition library from + * by John W. Ratcliff and Stan Melax. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +using System; +using System.Collections.Generic; +using System.Diagnostics; + +namespace OpenSim.Region.PhysicsModule.ConvexDecompositionDotNet +{ + public delegate void ConvexDecompositionCallback(ConvexResult result); + + public class FaceTri + { + public float3 P1; + public float3 P2; + public float3 P3; + + public FaceTri() { } + + public FaceTri(List vertices, int i1, int i2, int i3) + { + P1 = new float3(vertices[i1]); + P2 = new float3(vertices[i2]); + P3 = new float3(vertices[i3]); + } + } + + public static class ConvexDecomposition + { + private static void addTri(VertexPool vl, List list, float3 p1, float3 p2, float3 p3) + { + int i1 = vl.getIndex(p1); + int i2 = vl.getIndex(p2); + int i3 = vl.getIndex(p3); + + // do *not* process degenerate triangles! + if ( i1 != i2 && i1 != i3 && i2 != i3 ) + { + list.Add(i1); + list.Add(i2); + list.Add(i3); + } + } + + public static void calcConvexDecomposition(List vertices, List indices, ConvexDecompositionCallback callback, float masterVolume, int depth, + int maxDepth, float concavePercent, float mergePercent) + { + float4 plane = new float4(); + bool split = false; + + if (depth < maxDepth) + { + float volume = 0f; + float c = Concavity.computeConcavity(vertices, indices, ref plane, ref volume); + + if (depth == 0) + { + masterVolume = volume; + } + + float percent = (c * 100.0f) / masterVolume; + + if (percent > concavePercent) // if great than 5% of the total volume is concave, go ahead and keep splitting. + { + split = true; + } + } + + if (depth >= maxDepth || !split) + { + HullResult result = new HullResult(); + HullDesc desc = new HullDesc(); + + desc.SetHullFlag(HullFlag.QF_TRIANGLES); + + desc.Vertices = vertices; + + HullError ret = HullUtils.CreateConvexHull(desc, ref result); + + if (ret == HullError.QE_OK) + { + ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices); + callback(r); + } + + return; + } + + List ifront = new List(); + List iback = new List(); + + VertexPool vfront = new VertexPool(); + VertexPool vback = new VertexPool(); + + // ok..now we are going to 'split' all of the input triangles against this plane! + for (int i = 0; i < indices.Count / 3; i++) + { + int i1 = indices[i * 3 + 0]; + int i2 = indices[i * 3 + 1]; + int i3 = indices[i * 3 + 2]; + + FaceTri t = new FaceTri(vertices, i1, i2, i3); + + float3[] front = new float3[4]; + float3[] back = new float3[4]; + + int fcount = 0; + int bcount = 0; + + PlaneTriResult result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount); + + if (fcount > 4 || bcount > 4) + { + result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount); + } + + switch (result) + { + case PlaneTriResult.PTR_FRONT: + Debug.Assert(fcount == 3); + addTri(vfront, ifront, front[0], front[1], front[2]); + break; + case PlaneTriResult.PTR_BACK: + Debug.Assert(bcount == 3); + addTri(vback, iback, back[0], back[1], back[2]); + break; + case PlaneTriResult.PTR_SPLIT: + Debug.Assert(fcount >= 3 && fcount <= 4); + Debug.Assert(bcount >= 3 && bcount <= 4); + + addTri(vfront, ifront, front[0], front[1], front[2]); + addTri(vback, iback, back[0], back[1], back[2]); + + if (fcount == 4) + { + addTri(vfront, ifront, front[0], front[2], front[3]); + } + + if (bcount == 4) + { + addTri(vback, iback, back[0], back[2], back[3]); + } + + break; + } + } + + // ok... here we recursively call + if (ifront.Count > 0) + { + int vcount = vfront.GetSize(); + List vertices2 = vfront.GetVertices(); + for (int i = 0; i < vertices2.Count; i++) + vertices2[i] = new float3(vertices2[i]); + int tcount = ifront.Count / 3; + + calcConvexDecomposition(vertices2, ifront, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent); + } + + ifront.Clear(); + vfront.Clear(); + + if (iback.Count > 0) + { + int vcount = vback.GetSize(); + List vertices2 = vback.GetVertices(); + int tcount = iback.Count / 3; + + calcConvexDecomposition(vertices2, iback, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent); + } + + iback.Clear(); + vback.Clear(); + } + } +} -- cgit v1.1