1 files changed, 411 insertions, 0 deletions

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 
+ * <http://codesuppository.googlecode.com> 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<float3> mVertices;
+        public List<int> 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<float3> 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<CHull> mChulls = new List<CHull>();
+        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<int> indices)
+        {
+            List<int> 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<int> indices = new List<int>();
+
+            getMesh(a.mResult, vc, indices);
+            getMesh(b.mResult, vc, indices);
+
+            int vcount = vc.GetSize();
+            List<float3> 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<CHull> output = new List<CHull>(); // 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<CHull> hulls)
+        {
+            hulls.Sort(delegate(CHull a, CHull b) { return a.mVolume.CompareTo(b.mVolume); });
+        }
+    }
+}