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. --- .../ConvexDecompositionDotNet/Concavity.cs | 233 +++++++++++++++++++++ 1 file changed, 233 insertions(+) create mode 100644 OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/Concavity.cs (limited to 'OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/Concavity.cs') diff --git a/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/Concavity.cs b/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/Concavity.cs new file mode 100644 index 0000000..4140d25 --- /dev/null +++ b/OpenSim/Region/PhysicsModules/ConvexDecompositionDotNet/Concavity.cs @@ -0,0 +1,233 @@ +/* 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.Text; + +namespace OpenSim.Region.PhysicsModule.ConvexDecompositionDotNet +{ + public static class Concavity + { + // compute's how 'concave' this object is and returns the total volume of the + // convex hull as well as the volume of the 'concavity' which was found. + public static float computeConcavity(List vertices, List indices, ref float4 plane, ref float volume) + { + float cret = 0f; + volume = 1f; + + HullResult result = new HullResult(); + HullDesc desc = new HullDesc(); + + desc.MaxFaces = 256; + desc.MaxVertices = 256; + desc.SetHullFlag(HullFlag.QF_TRIANGLES); + desc.Vertices = vertices; + + HullError ret = HullUtils.CreateConvexHull(desc, ref result); + + if (ret == HullError.QE_OK) + { + volume = computeMeshVolume2(result.OutputVertices, result.Indices); + + // ok..now..for each triangle on the original mesh.. + // we extrude the points to the nearest point on the hull. + List tris = new List(); + + for (int i = 0; i < result.Indices.Count / 3; i++) + { + int i1 = result.Indices[i * 3 + 0]; + int i2 = result.Indices[i * 3 + 1]; + int i3 = result.Indices[i * 3 + 2]; + + float3 p1 = result.OutputVertices[i1]; + float3 p2 = result.OutputVertices[i2]; + float3 p3 = result.OutputVertices[i3]; + + CTri t = new CTri(p1, p2, p3, i1, i2, i3); + tris.Add(t); + } + + // we have not pre-computed the plane equation for each triangle in the convex hull.. + float totalVolume = 0; + + List ftris = new List(); // 'feature' triangles. + List input_mesh = new List(); + + 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]; + + float3 p1 = vertices[i1]; + float3 p2 = vertices[i2]; + float3 p3 = vertices[i3]; + + CTri t = new CTri(p1, p2, p3, i1, i2, i3); + input_mesh.Add(t); + } + + 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]; + + float3 p1 = vertices[i1]; + float3 p2 = vertices[i2]; + float3 p3 = vertices[i3]; + + CTri t = new CTri(p1, p2, p3, i1, i2, i3); + + featureMatch(t, tris, input_mesh); + + if (t.mConcavity > 0.05f) + { + float v = t.getVolume(); + totalVolume += v; + ftris.Add(t); + } + } + + SplitPlane.computeSplitPlane(vertices, indices, ref plane); + cret = totalVolume; + } + + return cret; + } + + public static bool featureMatch(CTri m, List tris, List input_mesh) + { + bool ret = false; + float neardot = 0.707f; + m.mConcavity = 0; + + for (int i = 0; i < tris.Count; i++) + { + CTri t = tris[i]; + + if (t.samePlane(m)) + { + ret = false; + break; + } + + float dot = float3.dot(t.mNormal, m.mNormal); + + if (dot > neardot) + { + float d1 = t.planeDistance(m.mP1); + float d2 = t.planeDistance(m.mP2); + float d3 = t.planeDistance(m.mP3); + + if (d1 > 0.001f || d2 > 0.001f || d3 > 0.001f) // can't be near coplaner! + { + neardot = dot; + + t.raySect(m.mP1, m.mNormal, ref m.mNear1); + t.raySect(m.mP2, m.mNormal, ref m.mNear2); + t.raySect(m.mP3, m.mNormal, ref m.mNear3); + + ret = true; + } + } + } + + if (ret) + { + m.mC1 = m.mP1.Distance(m.mNear1); + m.mC2 = m.mP2.Distance(m.mNear2); + m.mC3 = m.mP3.Distance(m.mNear3); + + m.mConcavity = m.mC1; + + if (m.mC2 > m.mConcavity) + m.mConcavity = m.mC2; + if (m.mC3 > m.mConcavity) + m.mConcavity = m.mC3; + } + + return ret; + } + + private static float det(float3 p1, float3 p2, float3 p3) + { + return p1.x * p2.y * p3.z + p2.x * p3.y * p1.z + p3.x * p1.y * p2.z - p1.x * p3.y * p2.z - p2.x * p1.y * p3.z - p3.x * p2.y * p1.z; + } + + public static float computeMeshVolume(List vertices, List indices) + { + float volume = 0f; + + for (int i = 0; i < indices.Count / 3; i++) + { + float3 p1 = vertices[indices[i * 3 + 0]]; + float3 p2 = vertices[indices[i * 3 + 1]]; + float3 p3 = vertices[indices[i * 3 + 2]]; + + volume += det(p1, p2, p3); // compute the volume of the tetrahedran relative to the origin. + } + + volume *= (1.0f / 6.0f); + if (volume < 0f) + return -volume; + return volume; + } + + public static float computeMeshVolume2(List vertices, List indices) + { + float volume = 0f; + + float3 p0 = vertices[0]; + for (int i = 0; i < indices.Count / 3; i++) + { + float3 p1 = vertices[indices[i * 3 + 0]]; + float3 p2 = vertices[indices[i * 3 + 1]]; + float3 p3 = vertices[indices[i * 3 + 2]]; + + volume += tetVolume(p0, p1, p2, p3); // compute the volume of the tetrahedron relative to the root vertice + } + + return volume * (1.0f / 6.0f); + } + + private static float tetVolume(float3 p0, float3 p1, float3 p2, float3 p3) + { + float3 a = p1 - p0; + float3 b = p2 - p0; + float3 c = p3 - p0; + + float3 cross = float3.cross(b, c); + float volume = float3.dot(a, cross); + + if (volume < 0f) + return -volume; + return volume; + } + } +} -- cgit v1.1