#if UNITY_EDITOR
using Newtonsoft.Json.Linq;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;
using Unity.AI.Navigation;
using UnityEditor;
using UnityEngine;
using UnityEngine.AI;

public class BuildThreeJsNavMesh
{
    const float floatPointPrecision = 1e3f;
    const float overlapThreshold = 0.5f;

    [MenuItem("Asset Bundle/Build ThreeJS NavMesh")]
    static async void Builds_ThreeJS_NavMesh()
    {
        string[] selectedBundleGUIDs = Selection.assetGUIDs;

        List<AssetImporter> selectedAssetBundles = GetSelectedBundles(selectedBundleGUIDs);

        if (selectedAssetBundles.Count > 1 || selectedAssetBundles.Count == 0)
        {
            UnityEngine.Debug.Log("Please select only 1 prefab");
            return;
        }

        if (string.IsNullOrEmpty(selectedAssetBundles[0].assetBundleName))
        {
            UnityEngine.Debug.Log("Please enter asset bundle name");
            return;
        }

        var assets = Selection.GetFiltered<GameObject>(SelectionMode.Assets);

        var asset = PrefabUtility.InstantiatePrefab(assets[0]) as GameObject;

        //asset.transform.localScale = new Vector3(1, 1, -1);

        var navMeshSurfaces = asset.GetComponentsInChildren<NavMeshSurface>().ToList();

        var navMeshLinks = asset.GetComponentsInChildren<NavMeshLink>().ToList();

        foreach (var navMeshSurface in navMeshSurfaces)
        {
            GameObject.FindObjectsByType<NavMeshSurface>(FindObjectsSortMode.None).Where(surface => surface.navMeshData != null).ToList().ForEach(surface => surface.RemoveData());
            navMeshSurface.AddData();

            await Task.Yield(); // Wait for navmesh to be built

            NavMeshTriangulation triangulation = NavMesh.CalculateTriangulation();

            // Create a json object contain data
            var zone = new JObject();
            zone["vertices"] = JArray.FromObject(
                triangulation.vertices.Select((vec) =>
                {
                    return new JObject()
                    {
                        ["x"] = vec.x,
                        ["y"] = vec.y,
                        ["z"] = -vec.z
                    };
                })
            );
            zone["groups"] = new JArray { new JArray() };

            for (var i = 0; i < triangulation.areas.Length; i++)
            {
                var node = new JObject();
                node["id"] = (zone["groups"][0] as JArray).Count;
                node["cost"] = JToken.FromObject(NavMesh.GetAreaCost(triangulation.areas[i]));
                node["areatype"] = JToken.FromObject(NavMesh.GetAreaNames()[triangulation.areas[i]]);
                node["type"] = JToken.FromObject("surface");

                int[] convexPolygon = new int[]
                {
                    triangulation.indices[3 * i],
                    triangulation.indices[3 * i + 1],
                    triangulation.indices[3 * i + 2]
                };

                bool checkConvexPolygon = true;

                var v0 = triangulation.vertices[triangulation.indices[3 * i]];
                var v1 = triangulation.vertices[triangulation.indices[3 * i + 1]];
                var v2 = triangulation.vertices[triangulation.indices[3 * i + 2]];
                Vector3 normal = Vector3.Cross(v2 - v0, v1 - v0).normalized;

                // Check if subsequence triangle can be join to make a convex polygon
                while (checkConvexPolygon)
                {
                    if (i == triangulation.areas.Length - 1)
                        break;

                    // Condition to check, set to **false** to check
                    bool check_ShareVertices = false;   // Should share a edge
                    bool check_SharePlane = true;      // Should be on a same plane
                    bool check_Convex = true;          // Should create a convex polygon if join

                    int[] triangle = new int[]
                    {
                        triangulation.indices[3 * i + 3],
                        triangulation.indices[3 * i + 4],
                        triangulation.indices[3 * i + 5]
                    };

                    //if (convexPolygon.Intersect(triangle).Count() == 2)
                    //    check_ShareVertices = true;

                    if (convexPolygon.Intersect(triangle).Count() > 0)
                    {
                        check_ShareVertices = true;

                        var t0 = triangulation.vertices[triangulation.indices[3 * i + 3]];
                        var t1 = triangulation.vertices[triangulation.indices[3 * i + 4]];
                        var t2 = triangulation.vertices[triangulation.indices[3 * i + 5]];

                        Vector3 t_normal = Vector3.Cross(t2 - t0, t1 - t0).normalized;

                        if (Vector3.Angle(normal, t_normal) < 1e-8)    // Degrees
                        {
                            check_SharePlane = true;

                            Vector3 convexPointNextToFirstPoint = triangulation.vertices[convexPolygon.ElementAt(1)];
                            Vector3 convexPointPriorToLastPoint = triangulation.vertices[convexPolygon.ElementAt(convexPolygon.Length - 2)];

                            bool signAngle1 = Vector3.SignedAngle(t2 - t0, convexPointNextToFirstPoint - t0, normal) > 0;
                            bool signAngle2 = Vector3.SignedAngle(t2 - t1, convexPointPriorToLastPoint - t1, normal) < 0;

                            if (signAngle1 && signAngle2)
                                check_Convex = true;
                        }
                    }

                    if (check_ShareVertices && check_SharePlane && check_Convex)
                    {
                        // Join triangle to make convex polygon
                        foreach (var index in triangle)
                        {
                            if (!convexPolygon.Contains(index))
                            {
                                convexPolygon = convexPolygon.Append(index).ToArray();
                            }
                        }
                        i++;
                    }
                    else
                    {
                        checkConvexPolygon = false;
                    }
                }

                node["vertexIds"] = new JArray(convexPolygon);
                // TODO: Handle quad centroid better
                var centroid = Vector3.zero;
                foreach (var vid in convexPolygon)
                {
                    centroid += triangulation.vertices[vid];
                }
                centroid = centroid / convexPolygon.Length;
                node["centroid"] = JToken.FromObject(new JObject()
                {
                    ["x"] = centroid.x,
                    ["y"] = centroid.y,
                    ["z"] = -centroid.z
                });

                node["neighbours"] = new JArray();
                node["portals"] = new JArray();

                (zone["groups"][0] as JArray).Add(node);
            }

            var areaNodeCount = (zone["groups"][0] as JArray).Count;

            for (var i = 0; i < (zone["groups"][0] as JArray).Count; i++)
            {
                for (var j = i + 1; j < (zone["groups"][0] as JArray).Count; j++)
                {
                    var node1vertices = ((zone["groups"][0] as JArray)[i]["vertexIds"] as JArray).ToObject<int[]>();
                    var node2vertices = ((zone["groups"][0] as JArray)[j]["vertexIds"] as JArray).ToObject<int[]>();

                    var sharedEdges = FindShareEdge(ref triangulation.vertices, node1vertices, node2vertices);

                    if (sharedEdges.Length == 2)
                    {
                        var nodeA = (zone["groups"][0] as JArray)[i];
                        var nodeB = (zone["groups"][0] as JArray)[j];

                        (nodeA["neighbours"] as JArray).Add(j);
                        (nodeB["neighbours"] as JArray).Add(i);

                        var centroidA = new Vector3(
                            nodeA["centroid"]["x"].Value<float>(),
                            nodeA["centroid"]["y"].Value<float>(),
                            -nodeA["centroid"]["z"].Value<float>()
                        );
                        var centroidB = new Vector3(
                            nodeB["centroid"]["x"].Value<float>(),
                            nodeB["centroid"]["y"].Value<float>(),
                            -nodeB["centroid"]["z"].Value<float>()
                        );

                        var portal1 = triangulation.vertices[sharedEdges.ElementAt(1)];
                        var portal2 = triangulation.vertices[sharedEdges.ElementAt(0)];

                        if (Vector3.Cross(portal1 - centroidA, portal2 - centroidA).y > 0)
                            (nodeA["portals"] as JArray).Add(new JArray(
                                sharedEdges.ElementAt(0),
                                sharedEdges.ElementAt(1)
                            ));
                        else
                            (nodeA["portals"] as JArray).Add(new JArray(
                                sharedEdges.ElementAt(1),
                                sharedEdges.ElementAt(0)
                            ));

                        if (Vector3.Cross(portal1 - centroidB, portal2 - centroidB).y > 0)
                            (nodeB["portals"] as JArray).Add(new JArray(
                                sharedEdges.ElementAt(0),
                                sharedEdges.ElementAt(1)
                            ));
                        else
                            (nodeB["portals"] as JArray).Add(new JArray(
                                sharedEdges.ElementAt(1),
                                sharedEdges.ElementAt(0)
                            ));
                    }
                }
            }

            // Workout the offmeshlink
            foreach (var navMeshLink in navMeshLinks)
            {
                if (!navMeshLink.isActiveAndEnabled)
                    continue;

                if (!navMeshLink.startTransform)
                    navMeshLink.startPoint = new Vector3(
                        navMeshLink.startPoint.x,
                        navMeshLink.startPoint.y,
                        navMeshLink.startPoint.z
                    );
                if (!navMeshLink.endTransform)
                    navMeshLink.endPoint = new Vector3(
                        navMeshLink.endPoint.x,
                        navMeshLink.endPoint.y,
                        navMeshLink.endPoint.z
                    );

                navMeshLink.UpdateLink();

                await Task.Yield();

                // Consider each link as two triangles forming a rectangular area in 3D space
                // We find a number of triangles that intersect with this area and link them together
                // Local start position
                Vector3 linkStart = navMeshLink.startTransform ?
                    navMeshLink.transform.InverseTransformVector(navMeshLink.startTransform.position) :
                    navMeshLink.startPoint;
                // Local end position
                Vector3 linkEnd = navMeshLink.endTransform ?
                    navMeshLink.transform.InverseTransformVector(navMeshLink.endTransform.position) :
                    navMeshLink.endPoint;

                // Local right direction relative to link start and link end
                Vector3 linkRight = Vector3.Cross(Vector3.up, (linkEnd - linkStart)).normalized;

                // Link width multiplier
                float useWidth = (linkRight != Vector3.zero && navMeshLink.width > 0f) ? 1f : 0f;

                // World portal
                //Vector3 startPortalLeft = navMeshLink.transform.TransformPoint(linkStart + linkRight * navMeshLink.width * useWidth / 2);
                //Vector3 startPortalRight = navMeshLink.transform.TransformPoint(linkStart - linkRight * navMeshLink.width * useWidth / 2);
                Vector3 startPortalLeft = navMeshLink.transform.TransformPoint(linkStart + linkRight * 0.1f / 2);
                Vector3 startPortalRight = navMeshLink.transform.TransformPoint(linkStart - linkRight * 0.1f / 2);
                Vector3 startPortal = (startPortalLeft + startPortalRight) / 2;

                //Vector3 endPortalLeft = navMeshLink.transform.TransformPoint(linkEnd + linkRight * navMeshLink.width * useWidth / 2);
                //Vector3 endPortalRight = navMeshLink.transform.TransformPoint(linkEnd - linkRight * navMeshLink.width * useWidth / 2);
                Vector3 endPortalLeft = navMeshLink.transform.TransformPoint(linkEnd + linkRight * 0.1f / 2);
                Vector3 endPortalRight = navMeshLink.transform.TransformPoint(linkEnd - linkRight * 0.1f / 2);
                Vector3 endPortal = (endPortalLeft + endPortalRight) / 2;

                // Add vertices
                int startPortalLeftIndex = AddExtraVertex(zone["vertices"] as JArray, startPortalLeft);
                int startPortalRightIndex = AddExtraVertex(zone["vertices"] as JArray, startPortalRight);
                int endPortalLeftIndex = AddExtraVertex(zone["vertices"] as JArray, endPortalRight);
                int endPortalRightIndex = AddExtraVertex(zone["vertices"] as JArray, endPortalLeft);

                var linkNode = new JObject();
                var linkNodeID = (zone["groups"][0] as JArray).Count;
                linkNode["id"] = linkNodeID;
                linkNode["cost"] = JToken.FromObject(navMeshLink.costModifier > 0 ? navMeshLink.costModifier : NavMesh.GetAreaCost(navMeshLink.area));
                linkNode["areatype"] = JToken.FromObject(NavMesh.GetAreaNames()[navMeshLink.area]);
                linkNode["type"] = JToken.FromObject("link");
                linkNode["vertexIds"] = new JArray(
                    startPortalLeftIndex,
                    startPortalRightIndex,
                    endPortalLeftIndex,
                    endPortalRightIndex
                );

                var linkNodeCentroid = (startPortal + endPortal) / 2;
                linkNode["centroid"] = JToken.FromObject(new JObject()
                {
                    ["x"] = linkNodeCentroid.x,
                    ["y"] = linkNodeCentroid.y,
                    ["z"] = -linkNodeCentroid.z
                });
                linkNode["neighbours"] = new JArray();
                linkNode["portals"] = new JArray();

                JToken StartNode = null;
                JToken EndNode = null;
                int startNodeID = -1;
                int endNodeID = -1;

                for (var i = 0; i < areaNodeCount; i++)
                {
                    var convexPolygon = zone["groups"][0][i]["vertexIds"].ToObject<int[]>();
                    for (var j = 2; j < convexPolygon.Length; j++)
                    {
                        Vector3 v0 = triangulation.vertices[convexPolygon[0]];
                        Vector3 v1 = triangulation.vertices[convexPolygon[j - 1]];
                        Vector3 v2 = triangulation.vertices[convexPolygon[j]];

                        if (startNodeID == -1 && IsPointInNode(startPortal, v0, v1, v2))
                        {
                            StartNode = zone["groups"][0][i];
                            startNodeID = i;

                            // TODO: Some time portals order got mix-up, cause the render line to go haywire, it worth looking into this, if i got the time.
                            (StartNode["neighbours"] as JArray).Add(linkNodeID);
                            Vector3 centroid = (v0 + v1 + v2) / 3;
                            if (Vector3.Cross(startPortalLeft - centroid, startPortalRight - centroid).y > 0)
                                (StartNode["portals"] as JArray).Add(new JArray(
                                    startPortalLeftIndex,
                                    startPortalRightIndex
                                ));
                            else
                                (StartNode["portals"] as JArray).Add(new JArray(
                                    startPortalRightIndex,
                                    startPortalLeftIndex
                                ));

                            if (navMeshLink.bidirectional)
                            {
                                (linkNode["neighbours"] as JArray).Add(startNodeID);
                                if (Vector3.Cross(startPortalLeft - linkNodeCentroid, startPortalRight - linkNodeCentroid).y > 0)
                                    (linkNode["portals"] as JArray).Add(new JArray(
                                        startPortalLeftIndex,
                                        startPortalRightIndex
                                    ));
                                else
                                    (linkNode["portals"] as JArray).Add(new JArray(
                                        startPortalRightIndex,
                                        startPortalLeftIndex
                                    ));
                            }
                        }

                        if (endNodeID == -1 && IsPointInNode(endPortal, v0, v1, v2))
                        {
                            EndNode = zone["groups"][0][i];
                            endNodeID = i;

                            // TODO: Some time portals order got mix-up, cause the render line to go haywire, it worth looking into this, if i got the time.
                            (linkNode["neighbours"] as JArray).Add(endNodeID);
                            if (Vector3.Cross(endPortalLeft - linkNodeCentroid, endPortalRight - linkNodeCentroid).y > 0)
                                (linkNode["portals"] as JArray).Add(new JArray(
                                    endPortalLeftIndex,
                                    endPortalRightIndex
                                ));
                            else
                                (linkNode["portals"] as JArray).Add(new JArray(
                                    endPortalRightIndex,
                                    endPortalLeftIndex
                                ));

                            if (navMeshLink.bidirectional)
                            {
                                Vector3 centroid = (v0 + v1 + v2) / 3;
                                (EndNode["neighbours"] as JArray).Add(linkNodeID);
                                if (Vector3.Cross(endPortalLeft - centroid, endPortalRight - centroid).y > 0)
                                    (EndNode["portals"] as JArray).Add(new JArray(
                                    endPortalLeftIndex,
                                    endPortalRightIndex
                                    ));
                                else
                                    (EndNode["portals"] as JArray).Add(new JArray(
                                    endPortalRightIndex,
                                    endPortalLeftIndex
                                    ));
                            }
                        }

                        if (startNodeID != -1 && endNodeID != -1)
                        {
                            //// Connect as neighbours
                            //(StartNode["neighbours"] as JArray).Add(endNodeID);
                            //if (navMeshLink.bidirectional)
                            //    (EndNode["neighbours"] as JArray).Add(startNodeID);

                            //float portalLength = 0.1f; // total length of portal segment

                            //// Direction from start to end
                            //Vector3 dir = (endPortal - startPortal).normalized;

                            //// Avoid collinearity
                            //Vector3 up = Mathf.Abs(Vector3.Dot(Vector3.up, dir)) > 0.99f
                            //    ? Vector3.forward
                            //    : Vector3.up;

                            //Vector3 right = Vector3.Cross(dir, up).normalized;
                            //// Compute portal endpoints
                            //Vector3 portalA = startPortal + right * (portalLength * 0.5f);
                            //Vector3 portalB = startPortal - right * (portalLength * 0.5f);

                            //// Add to triangulation vertices
                            //JArray zoneVertices = (JArray)zone["vertices"];

                            //int pAIndex = AddExtraVertex(zoneVertices, portalA);
                            //int pBIndex = AddExtraVertex(zoneVertices, portalB);

                            //(StartNode["portals"] as JArray).Add(new JArray(pAIndex, pBIndex));
                            //if (navMeshLink.bidirectional)
                            //    (EndNode["portals"] as JArray).Add(new JArray(pBIndex, pAIndex));

                            break;
                        }
                    }

                    if (startNodeID != -1 && endNodeID != -1)
                        break;
                }

                (zone["groups"][0] as JArray).Add(linkNode);
            }

            var buildLocation = CreateBuildLocation(selectedAssetBundles[0].assetBundleName);
            if (!Directory.Exists(buildLocation))
                Directory.CreateDirectory(buildLocation);
            File.WriteAllText(buildLocation + $"/{selectedAssetBundles[0].assetBundleName}.TJSNM", zone.ToString());
            System.Diagnostics.Process.Start(Path.GetFullPath(buildLocation));
            break;
        }

        if (!Application.isPlaying)
        {
            UnityEngine.Object.DestroyImmediate(asset);
        }
        else
        {
            UnityEngine.Object.Destroy(asset);
        }

        GameObject.FindObjectsByType<NavMeshSurface>(FindObjectsSortMode.None).Where(surface => surface.navMeshData != null).ToList().ForEach(surface => surface.RemoveData());
        GameObject.FindObjectsByType<NavMeshSurface>(FindObjectsSortMode.None).Where(surface => surface.navMeshData != null).ToList().ForEach(surface => surface.AddData());
        Resources.UnloadUnusedAssets();
    }

    static int AddExtraVertex(JArray zoneVertices, Vector3 v)
    {
        var jv = new JObject()
        {
            ["x"] = v.x,
            ["y"] = v.y,
            ["z"] = -v.z
        };
        zoneVertices.Add(jv);
        return zoneVertices.Count - 1; // index of newly added vertex
    }
    /// <summary>
    /// Check if the point lie with the triangle defined by v1,v2,v3
    /// Method allow for some misplacement defined by <see cref="overlapThreshold"/>
    /// </summary>
    static bool IsPointInNode(Vector3 point, Vector3 v1, Vector3 v2, Vector3 v3)
    {
        return IsPointInTriangle(v1, v2, v3, point) && Mathf.Abs(DistancePointToPlane(point, v1, v2, v3)) < overlapThreshold;
    }

    /// <summary>
    /// Check if the line segment p1-p2 intersect with the triangle defined by v1,v2,v3
    /// If it is, return the overlap segment in Overlap1 and Overlap2
    /// Method allow for some misplacement defined by <see cref="overlapThreshold"/>
    /// </summary>
    static bool IsLineInNode(Vector3 p1, Vector3 p2, Vector3 v1, Vector3 v2, Vector3 v3, out Vector3 Overlap1, out Vector3 Overlap2)
    {
        float p1_distance = DistancePointToPlane(p1, v1, v2, v3);
        float p2_distance = DistancePointToPlane(p2, v1, v2, v3);

        if (p1_distance * p2_distance > 0 &&
            Mathf.Abs(p1_distance) > overlapThreshold &&
            Mathf.Abs(p2_distance) > overlapThreshold)
        {
            Overlap1 = Vector3.zero;
            Overlap2 = Vector3.zero;
            return false;
        }

        if (Mathf.Abs(p1_distance) > overlapThreshold)
        {
            float sign = p1_distance / Mathf.Abs(p1_distance);
            float t = (p1_distance - sign * overlapThreshold) / Mathf.Abs((p1_distance - p2_distance));
            p1 = p1 + (p2 - p1) * t;
        }

        if (Mathf.Abs(p2_distance) > overlapThreshold)
        {
            p1_distance = DistancePointToPlane(p1, v1, v2, v3);
            float sign = p2_distance / Mathf.Abs(p2_distance);
            float t = (p2_distance - sign * overlapThreshold) / Mathf.Abs((p2_distance - p1_distance));
            p2 = p2 + (p1 - p2) * t;
        }

        bool p1_in = IsPointInTriangle(v1, v2, v3, p1);
        bool p2_in = IsPointInTriangle(v1, v2, v3, p2);

        if (p1_in && p2_in)
        {
            Overlap1 = p1;
            Overlap2 = p2;
            return true;
        }

        Vector3 b1 = GetBarycentric(v1, v2, v3, p1);
        Vector3 b2 = GetBarycentric(v1, v2, v3, p2);

        if (ClipBarycentricSegmentToTriangle(ref b1, ref b2))
        {
            Overlap1 = b1.x * v1 + b1.y * v2 + b1.z * v3;
            Overlap2 = b2.x * v1 + b2.y * v2 + b2.z * v3;
            return true;
        }
        else
        {
            Overlap1 = Vector3.zero;
            Overlap2 = Vector3.zero;
            return false;
        }
    }

    /// <summary>
    /// Clip the segment defined by barycentric coordinates b1 and b2 to the triangle defined by u,v,w >= 0
    /// </summary>
    /// <returns>True if barycentric segment intersect with the triangle</returns>
    static bool ClipBarycentricSegmentToTriangle(ref Vector3 b1, ref Vector3 b2)
    {
        float tEnter = 0f;
        float tExit = 1f;

        Vector3 d = b2 - b1;

        // We must satisfy: u >= 0, v >= 0, w >= 0
        for (int i = 0; i < 3; i++)
        {
            float bi = b1[i];
            float di = d[i];

            if (Mathf.Abs(di) < 1e-8f)
            {
                // Segment parallel to this boundary
                if (bi < 0f)
                    return false; // Fully outside
            }
            else
            {
                float t = -bi / di;

                if (di > 0f)
                    tEnter = Mathf.Max(tEnter, t);
                else
                    tExit = Mathf.Min(tExit, t);

                if (tEnter > tExit)
                    return false; // No overlap
            }
        }

        // Compute clipped barycentric points
        Vector3 newB1 = b1 + d * tEnter;
        Vector3 newB2 = b1 + d * tExit;

        b1 = newB1;
        b2 = newB2;
        return true;
    }

    /// <summary>
    /// Compute barycentric coordinates (u, v, w) of P with respect to triangle ABC,
    /// without consider distance from P to ABC Plane. Meaning it return the same value
    /// if P in on the plane or 100km away from the Plane (Pendicularly).
    /// </summary>
    static Vector3 GetBarycentric(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
    {
        Vector3 v0 = B - A;
        Vector3 v1 = C - A;
        Vector3 v2 = P - A;

        float d00 = Vector3.Dot(v0, v0);
        float d01 = Vector3.Dot(v0, v1);
        float d11 = Vector3.Dot(v1, v1);
        float d20 = Vector3.Dot(v2, v0);
        float d21 = Vector3.Dot(v2, v1);

        float denom = d00 * d11 - d01 * d01;
        if (Mathf.Abs(denom) < 1e-8f)
            return new Vector3(-1, -1, -1); // Degenerate triangle

        float v = (d11 * d20 - d01 * d21) / denom;
        float w = (d00 * d21 - d01 * d20) / denom;
        float u = 1.0f - v - w;

        return new Vector3(u, v, w);
    }

    /// <summary>
    /// Check if P is inside of triangle ABC (using barycentrics)    
    /// without consider distance from P to ABC Plane. Meaning it return the same value
    /// if P in on the plane or 100km away from the Plane (Pendicularly).
    /// </summary>
    static bool IsPointInTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
    {
        Vector3 bary = GetBarycentric(A, B, C, P);
        return bary.x >= -1e-3f && bary.y >= -1e-3f && bary.z >= -1e-3f &&
               bary.x <= 1 + 1e-3f && bary.y <= 1 + 1e-3f && bary.z <= 1 + 1e-3f;
    }

    /// <summary>
    /// Compute the perpendicular distance from point to plane defined by triangle ABC
    /// </summary>
    /// <returns>Positive value if point is on the same side as the normal direction (y-up if possible), negative otherwise.</returns>
    public static float DistancePointToPlane(Vector3 point, Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 normal = Vector3.Cross(b - a, c - a).normalized;
        if (normal.y < 0)
            normal = -normal;
        return Vector3.Dot(point - a, normal);
    }

    /// <summary>
    /// Find the shared edge between two triangles defined by their vertex indices.
    /// The shared edge should be overlap by some extent.
    /// </summary>
    /// <returns>Array of index of pair repersent shared (overlap) edges.</returns>
    static int[] FindShareEdge(ref Vector3[] verticies, int[] indices1, int[] indices2)
    {
        List<int> shareEdge = new List<int>();

        for (int i = 0; i < indices1.Length; i++)
        {
            for (int j = 0; j < indices2.Length; j++)
            {
                var a1 = indices1[i];
                var a2 = i == indices1.Length - 1 ? indices1[0] : indices1[i + 1];
                var b1 = indices2[j];
                var b2 = j == indices2.Length - 1 ? indices2[0] : indices2[j + 1];
                shareEdge.AddRange(FindShareEdge(ref verticies, a1, a2, b1, b2));
            }
        }

        return shareEdge.ToArray();
    }

    /// <summary>
    /// Find the shared edge between two line segments (a1-a2) and (b1-b2).
    /// Allow for some misplacement.
    /// </summary>
    static int[] FindShareEdge(ref Vector3[] verticies, int a1, int a2, int b1, int b2)
    {
        Vector3 A1 = verticies[a1];
        Vector3 A2 = verticies[a2];
        Vector3 B1 = verticies[b1];
        Vector3 B2 = verticies[b2];

        // Check if B1 and B2 are somewhat on the line A1A2
        Vector3 A1A2 = A2 - A1;
        Vector3 dirB1 = B1 - A1;
        Vector3 dirB2 = B2 - A1;

        if (Vector3.Cross(A1A2, dirB1).sqrMagnitude > 1e-3f) return new int[0];
        if (Vector3.Cross(A1A2, dirB2).sqrMagnitude > 1e-3f) return new int[0];

        // Project B1 and B2 onto line A1A2 and get their t value
        // t = 0 at A1, t = 1 at A2
        float A1A2_Mag = A1A2.magnitude;

        float B1_t = Mathf.Round(Vector3.Dot(dirB1, A1A2) / (A1A2_Mag * A1A2_Mag) * floatPointPrecision) / floatPointPrecision;
        float B2_t = Mathf.Round(Vector3.Dot(dirB2, A1A2) / (A1A2_Mag * A1A2_Mag) * floatPointPrecision) / floatPointPrecision;

        // From t value, determine the overlap
        if (B1_t <= 0 && 0 < B2_t && B2_t <= 1)
        {
            return new int[] { a1, b2 };    // B1---A1---B2---A2
        }
        if (B2_t <= 0 && 0 < B1_t && B1_t <= 1)
        {
            return new int[] { a1, b1 };    // B2---A1---B1---A2
        }

        if (B1_t <= 0 && 1 <= B2_t)
        {
            return new int[] { a1, a2 };    // B1---A1---A2---B2
        }
        if (B2_t <= 0 && 1 <= B1_t)
        {
            return new int[] { a1, a2 };    // B2---A1---A2---B1
        }

        if (0 <= B1_t && B1_t < B2_t && B2_t <= 1)
        {
            return new int[] { b1, b2 };    // A1---B1---B2---A2
        }
        if (0 <= B2_t && B2_t < B1_t && B1_t <= 1)
        {
            return new int[] { b2, b1 };    // A1---B2---B1---A2
        }

        if (0 <= B1_t && B1_t < 1 && 1 <= B2_t)
        {
            return new int[] { b1, a2 };    // A1---B1---A2---B2
        }
        if (0 <= B2_t && B2_t < 1 && 1 <= B1_t)
        {
            return new int[] { b2, a2 };    // A1---B2---A2---B1
        }

        // No overlap found
        return new int[0];
    }

    private static string CreateBuildLocation(string bundleName)
    {
        if (!Directory.Exists("./AssetBundleBuilds"))
        {
            Directory.CreateDirectory("./AssetBundleBuilds");
        }

        string buildLocation = "./AssetBundleBuilds/" + bundleName;
        return buildLocation;
    }

    private static List<AssetImporter> GetSelectedBundles(string[] selectedBundleGUIDs)
    {
        List<AssetImporter> selectedAssetBundles = new List<AssetImporter>();
        foreach (string bundleGUID in selectedBundleGUIDs)
        {
            // Get the path of the bundle asset
            string bundlePath = AssetDatabase.GUIDToAssetPath(bundleGUID);
            AssetImporter assetImporter = AssetImporter.GetAtPath(bundlePath);
            selectedAssetBundles.Add(assetImporter);
        }
        return selectedAssetBundles;
    }
}
#endif
