From 302d72701da35b6d481a538c4cb953976d7e9044 Mon Sep 17 00:00:00 2001 From: Robert Adams Date: Mon, 20 Jun 2011 17:14:59 -0700 Subject: BulletSim initial checkin --- .../ConvexDecompositionDotNet/ConvexBuilder.cs | 411 +++++++++++++++++++++ 1 file changed, 411 insertions(+) create mode 100644 OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs (limited to 'OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs') diff --git a/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs new file mode 100644 index 0000000..dfaede1 --- /dev/null +++ b/OpenSim/Region/Physics/ConvexDecompositionDotNet/ConvexBuilder.cs @@ -0,0 +1,411 @@ +/* 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.Physics.ConvexDecompositionDotNet +{ + public class DecompDesc + { + public List mVertices; + public List mIndices; + + // options + public uint mDepth; // depth to split, a maximum of 10, generally not over 7. + public float mCpercent; // the concavity threshold percentage. 0=20 is reasonable. + public float mPpercent; // the percentage volume conservation threshold to collapse hulls. 0-30 is reasonable. + + // hull output limits. + public uint mMaxVertices; // maximum number of vertices in the output hull. Recommended 32 or less. + public float mSkinWidth; // a skin width to apply to the output hulls. + + public ConvexDecompositionCallback mCallback; // the interface to receive back the results. + + public DecompDesc() + { + mDepth = 5; + mCpercent = 5; + mPpercent = 5; + mMaxVertices = 32; + } + } + + public class CHull + { + public float[] mMin = new float[3]; + public float[] mMax = new float[3]; + public float mVolume; + public float mDiagonal; + public ConvexResult mResult; + + public CHull(ConvexResult result) + { + mResult = new ConvexResult(result); + mVolume = Concavity.computeMeshVolume(result.HullVertices, result.HullIndices); + + mDiagonal = getBoundingRegion(result.HullVertices, mMin, mMax); + + float dx = mMax[0] - mMin[0]; + float dy = mMax[1] - mMin[1]; + float dz = mMax[2] - mMin[2]; + + dx *= 0.1f; // inflate 1/10th on each edge + dy *= 0.1f; // inflate 1/10th on each edge + dz *= 0.1f; // inflate 1/10th on each edge + + mMin[0] -= dx; + mMin[1] -= dy; + mMin[2] -= dz; + + mMax[0] += dx; + mMax[1] += dy; + mMax[2] += dz; + } + + public void Dispose() + { + mResult = null; + } + + public bool overlap(CHull h) + { + return overlapAABB(mMin, mMax, h.mMin, h.mMax); + } + + // returns the d1Giagonal distance + private static float getBoundingRegion(List points, float[] bmin, float[] bmax) + { + float3 first = points[0]; + + bmin[0] = first.x; + bmin[1] = first.y; + bmin[2] = first.z; + + bmax[0] = first.x; + bmax[1] = first.y; + bmax[2] = first.z; + + for (int i = 1; i < points.Count; i++) + { + float3 p = points[i]; + + if (p[0] < bmin[0]) bmin[0] = p[0]; + if (p[1] < bmin[1]) bmin[1] = p[1]; + if (p[2] < bmin[2]) bmin[2] = p[2]; + + if (p[0] > bmax[0]) bmax[0] = p[0]; + if (p[1] > bmax[1]) bmax[1] = p[1]; + if (p[2] > bmax[2]) bmax[2] = p[2]; + } + + float dx = bmax[0] - bmin[0]; + float dy = bmax[1] - bmin[1]; + float dz = bmax[2] - bmin[2]; + + return (float)Math.Sqrt(dx * dx + dy * dy + dz * dz); + } + + // return true if the two AABB's overlap. + private static bool overlapAABB(float[] bmin1, float[] bmax1, float[] bmin2, float[] bmax2) + { + if (bmax2[0] < bmin1[0]) return false; // if the maximum is less than our minimum on any axis + if (bmax2[1] < bmin1[1]) return false; + if (bmax2[2] < bmin1[2]) return false; + + if (bmin2[0] > bmax1[0]) return false; // if the minimum is greater than our maximum on any axis + if (bmin2[1] > bmax1[1]) return false; // if the minimum is greater than our maximum on any axis + if (bmin2[2] > bmax1[2]) return false; // if the minimum is greater than our maximum on any axis + + return true; // the extents overlap + } + } + + public class ConvexBuilder + { + public List mChulls = new List(); + private ConvexDecompositionCallback mCallback; + + private int MAXDEPTH = 8; + private float CONCAVE_PERCENT = 1f; + private float MERGE_PERCENT = 2f; + + public ConvexBuilder(ConvexDecompositionCallback callback) + { + mCallback = callback; + } + + public void Dispose() + { + int i; + for (i = 0; i < mChulls.Count; i++) + { + CHull cr = mChulls[i]; + cr.Dispose(); + } + } + + public bool isDuplicate(uint i1, uint i2, uint i3, uint ci1, uint ci2, uint ci3) + { + uint dcount = 0; + + Debug.Assert(i1 != i2 && i1 != i3 && i2 != i3); + Debug.Assert(ci1 != ci2 && ci1 != ci3 && ci2 != ci3); + + if (i1 == ci1 || i1 == ci2 || i1 == ci3) + dcount++; + if (i2 == ci1 || i2 == ci2 || i2 == ci3) + dcount++; + if (i3 == ci1 || i3 == ci2 || i3 == ci3) + dcount++; + + return dcount == 3; + } + + public void getMesh(ConvexResult cr, VertexPool vc, List indices) + { + List src = cr.HullIndices; + + for (int i = 0; i < src.Count / 3; i++) + { + int i1 = src[i * 3 + 0]; + int i2 = src[i * 3 + 1]; + int i3 = src[i * 3 + 2]; + + float3 p1 = cr.HullVertices[i1]; + float3 p2 = cr.HullVertices[i2]; + float3 p3 = cr.HullVertices[i3]; + + i1 = vc.getIndex(p1); + i2 = vc.getIndex(p2); + i3 = vc.getIndex(p3); + } + } + + public CHull canMerge(CHull a, CHull b) + { + if (!a.overlap(b)) // if their AABB's (with a little slop) don't overlap, then return. + return null; + + CHull ret = null; + + // ok..we are going to combine both meshes into a single mesh + // and then we are going to compute the concavity... + + VertexPool vc = new VertexPool(); + + List indices = new List(); + + getMesh(a.mResult, vc, indices); + getMesh(b.mResult, vc, indices); + + int vcount = vc.GetSize(); + List vertices = vc.GetVertices(); + int tcount = indices.Count / 3; + + //don't do anything if hull is empty + if (tcount == 0) + { + vc.Clear(); + return null; + } + + HullResult hresult = new HullResult(); + HullDesc desc = new HullDesc(); + + desc.SetHullFlag(HullFlag.QF_TRIANGLES); + desc.Vertices = vertices; + + HullError hret = HullUtils.CreateConvexHull(desc, ref hresult); + + if (hret == HullError.QE_OK) + { + float combineVolume = Concavity.computeMeshVolume(hresult.OutputVertices, hresult.Indices); + float sumVolume = a.mVolume + b.mVolume; + + float percent = (sumVolume * 100) / combineVolume; + if (percent >= (100.0f - MERGE_PERCENT)) + { + ConvexResult cr = new ConvexResult(hresult.OutputVertices, hresult.Indices); + ret = new CHull(cr); + } + } + + vc.Clear(); + return ret; + } + + public bool combineHulls() + { + bool combine = false; + + sortChulls(mChulls); // sort the convex hulls, largest volume to least... + + List output = new List(); // the output hulls... + + int i; + for (i = 0; i < mChulls.Count && !combine; ++i) + { + CHull cr = mChulls[i]; + + int j; + for (j = 0; j < mChulls.Count; j++) + { + CHull match = mChulls[j]; + + if (cr != match) // don't try to merge a hull with itself, that be stoopid + { + + CHull merge = canMerge(cr, match); // if we can merge these two.... + + if (merge != null) + { + output.Add(merge); + + ++i; + while (i != mChulls.Count) + { + CHull cr2 = mChulls[i]; + if (cr2 != match) + { + output.Add(cr2); + } + i++; + } + + cr.Dispose(); + match.Dispose(); + combine = true; + break; + } + } + } + + if (combine) + { + break; + } + else + { + output.Add(cr); + } + } + + if (combine) + { + mChulls.Clear(); + mChulls = output; + output.Clear(); + } + + return combine; + } + + public int process(DecompDesc desc) + { + int ret = 0; + + MAXDEPTH = (int)desc.mDepth; + CONCAVE_PERCENT = desc.mCpercent; + MERGE_PERCENT = desc.mPpercent; + + ConvexDecomposition.calcConvexDecomposition(desc.mVertices, desc.mIndices, ConvexDecompResult, 0f, 0, MAXDEPTH, CONCAVE_PERCENT, MERGE_PERCENT); + + while (combineHulls()) // keep combinging hulls until I can't combine any more... + ; + + int i; + for (i = 0; i < mChulls.Count; i++) + { + CHull cr = mChulls[i]; + + // before we hand it back to the application, we need to regenerate the hull based on the + // limits given by the user. + + ConvexResult c = cr.mResult; // the high resolution hull... + + HullResult result = new HullResult(); + HullDesc hdesc = new HullDesc(); + + hdesc.SetHullFlag(HullFlag.QF_TRIANGLES); + + hdesc.Vertices = c.HullVertices; + hdesc.MaxVertices = desc.mMaxVertices; // maximum number of vertices allowed in the output + + if (desc.mSkinWidth != 0f) + { + hdesc.SkinWidth = desc.mSkinWidth; + hdesc.SetHullFlag(HullFlag.QF_SKIN_WIDTH); // do skin width computation. + } + + HullError ret2 = HullUtils.CreateConvexHull(hdesc, ref result); + + if (ret2 == HullError.QE_OK) + { + ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices); + + r.mHullVolume = Concavity.computeMeshVolume(result.OutputVertices, result.Indices); // the volume of the hull. + + // compute the best fit OBB + //computeBestFitOBB(result.mNumOutputVertices, result.mOutputVertices, sizeof(float) * 3, r.mOBBSides, r.mOBBTransform); + + //r.mOBBVolume = r.mOBBSides[0] * r.mOBBSides[1] * r.mOBBSides[2]; // compute the OBB volume. + + //fm_getTranslation(r.mOBBTransform, r.mOBBCenter); // get the translation component of the 4x4 matrix. + + //fm_matrixToQuat(r.mOBBTransform, r.mOBBOrientation); // extract the orientation as a quaternion. + + //r.mSphereRadius = computeBoundingSphere(result.mNumOutputVertices, result.mOutputVertices, r.mSphereCenter); + //r.mSphereVolume = fm_sphereVolume(r.mSphereRadius); + + mCallback(r); + } + + result = null; + cr.Dispose(); + } + + ret = mChulls.Count; + + mChulls.Clear(); + + return ret; + } + + public void ConvexDecompResult(ConvexResult result) + { + CHull ch = new CHull(result); + mChulls.Add(ch); + } + + public void sortChulls(List hulls) + { + hulls.Sort(delegate(CHull a, CHull b) { return a.mVolume.CompareTo(b.mVolume); }); + } + } +} -- cgit v1.1