#if UNITY_EDITOR
using Newtonsoft.Json;
using Newtonsoft.Json.Linq;
using System;
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;

[InitializeOnLoad]
public static class ThreeJsNavMeshBootstrap
{
    static ThreeJsNavMeshBootstrap()
    {
        JsonConvert.DefaultSettings = () =>
        {
            var settings = new JsonSerializerSettings();
            settings.Converters.Add(new Vector3Converter());
            return settings;
        };
    }
}

public class Vector3Converter : JsonConverter<Vector3>
{
    public override void WriteJson(JsonWriter writer, Vector3 value, JsonSerializer serializer)
    {
        writer.WriteStartObject();
        writer.WritePropertyName("x");
        writer.WriteValue(value.x);
        writer.WritePropertyName("y");
        writer.WriteValue(value.y);
        writer.WritePropertyName("z");
        writer.WriteValue(value.z);
        writer.WriteEndObject();
    }

    public override Vector3 ReadJson(
        JsonReader reader,
        Type objectType,
        Vector3 existingValue,
        bool hasExistingValue,
        JsonSerializer serializer)
    {
        JObject obj = JObject.Load(reader);

        return new Vector3(
            obj["x"]?.Value<float>() ?? 0f,
            obj["y"]?.Value<float>() ?? 0f,
            obj["z"]?.Value<float>() ?? 0f
        );
    }
}

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 ThreeJSPathFindingZone();
            zone.vertices = triangulation.vertices.Select(ver => new Vector3(ver.x, ver.y, -ver.z)).ToList();
            
            List<int> namedAreas = new List<int>();

            {
                string[] s_namedAreas = NavMesh.GetAreaNames();
                foreach (string name in s_namedAreas)
                {
                    namedAreas.Add(NavMesh.GetAreaFromName(name));
                }
            }

            for (var i = 0; i < 32; i++)
            {
                zone.areas.Add(new ThreeJSArea()
                {
                    id = i,
                    name = namedAreas.Contains(i) ? NavMesh.GetAreaNames()[i] : "",
                    cost = NavMesh.GetAreaCost(i)

                });
            }

            for (var i = 0; i < triangulation.areas.Length; i++)
            {
                var node = new ThreeJSPathFindingNode();
                node.id = zone.group.nodes.Count;
                node.cost = NavMesh.GetAreaCost(triangulation.areas[i]);
                node.areatype = NavMesh.GetAreaNames()[triangulation.areas[i]];
                node.area = triangulation.areas[i];

                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 = convexPolygon.ToList();
                node.vertices.AddRange(convexPolygon.Select(vid => new Vector3(triangulation.vertices[vid].x, triangulation.vertices[vid].y, -triangulation.vertices[vid].z)));
                node.vertices.ForEach(vertex =>
                {
                    node.minX = Mathf.Min(node.minX, vertex.x);
                    node.minY = Mathf.Min(node.minY, vertex.y);
                    node.minZ = Mathf.Min(node.minZ, vertex.z);
                    node.maxX = Mathf.Max(node.maxX, vertex.x);
                    node.maxY = Mathf.Max(node.maxY, vertex.y);
                    node.maxZ = Mathf.Max(node.maxZ, vertex.z);
                });
                // TODO: Handle quad centroid better
                foreach (var vid in convexPolygon)
                {
                    node.centroid += triangulation.vertices[vid];
                }
                node.centroid = node.centroid / convexPolygon.Length;
                node.centroid.Scale(new Vector3(1, 1, -1));


                zone.group.nodes.Add(node);
            }

            var areaNodeCount = zone.group.nodes.Count;

            for (var i = 0; i < zone.group.nodes.Count; i++)
            {
                for (var j = i + 1; j < zone.group.nodes.Count; j++)
                {
                    var node1vertices = zone.group.nodes[i].vertexIds;
                    var node2vertices = zone.group.nodes[j].vertexIds;

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

                    if (sharedEdges.Length == 2)
                    {
                        var nodeA = zone.group.nodes[i];
                        var nodeB = zone.group.nodes[j];

                        nodeA.neighbours.Add(j);
                        nodeB.neighbours.Add(i);

                        var centroidA = new Vector3(
                            nodeA.centroid.x,
                            nodeA.centroid.y,
                            -nodeA.centroid.z
                        );
                        var centroidB = new Vector3(
                            nodeB.centroid.x,
                            nodeB.centroid.y,
                            -nodeB.centroid.z
                        );

                        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.Add(new int[] {
                                sharedEdges.ElementAt(0),
                                sharedEdges.ElementAt(1)
                            });
                        else
                            nodeA.portals.Add(new int[] {
                                sharedEdges.ElementAt(1),
                                sharedEdges.ElementAt(0)
                            });

                        if (Vector3.Cross(portal1 - centroidB, portal2 - centroidB).y > 0)
                            nodeB.portals.Add(new int[] {
                                sharedEdges.ElementAt(0),
                                sharedEdges.ElementAt(1)
                            });
                        else
                            nodeB.portals.Add(new int[] {
                                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
                zone.vertices.Add(new Vector3(startPortalLeft.x, startPortalLeft.y, -startPortalLeft.z));
                int startPortalLeftIndex = zone.vertices.Count - 1;
                zone.vertices.Add(new Vector3(startPortalRight.x, startPortalRight.y, -startPortalRight.z));
                int startPortalRightIndex = zone.vertices.Count - 1;
                zone.vertices.Add(new Vector3(endPortalLeft.x, endPortalLeft.y, -endPortalLeft.z));
                int endPortalLeftIndex = zone.vertices.Count - 1;
                zone.vertices.Add(new Vector3(endPortalRight.x, endPortalRight.y, -endPortalRight.z));
                int endPortalRightIndex = zone.vertices.Count - 1;

                var linkNode = new ThreeJSPathFindingNode();
                var linkNodeID = zone.group.nodes.Count;
                linkNode.id = linkNodeID;
                linkNode.cost = (navMeshLink.costModifier > 0 ? navMeshLink.costModifier : NavMesh.GetAreaCost(navMeshLink.area));
                linkNode.areatype = NavMesh.GetAreaNames()[navMeshLink.area];
                linkNode.area = navMeshLink.area;
                linkNode.type = ("link");
                linkNode.vertexIds.AddRange(new int[] {
                    startPortalLeftIndex,
                    startPortalRightIndex,
                    endPortalLeftIndex,
                    endPortalRightIndex
                });
                linkNode.vertices.AddRange(new Vector3[]
                {
                    new Vector3(startPortalLeft.x, startPortalLeft.y, -startPortalLeft.z),
                    new Vector3(startPortalRight.x, startPortalRight.y, -startPortalRight.z),
                    new Vector3(endPortalLeft.x, endPortalLeft.y, -endPortalLeft.z),
                    new Vector3(endPortalRight.x, endPortalRight.y, -endPortalRight.z)
                });

                linkNode.minX = Mathf.Min(startPortalLeft.x, startPortalRight.x, endPortalLeft.x, endPortalRight.x);
                linkNode.minY = Mathf.Min(startPortalLeft.y, startPortalRight.y, endPortalLeft.y, endPortalRight.y);
                linkNode.minZ = Mathf.Min(-startPortalLeft.z, -startPortalRight.z, -endPortalLeft.z, -endPortalRight.z);
                linkNode.maxX = Mathf.Max(startPortalLeft.x, startPortalRight.x, endPortalLeft.x, endPortalRight.x);
                linkNode.maxY = Mathf.Max(startPortalLeft.y, startPortalRight.y, endPortalLeft.y, endPortalRight.y);
                linkNode.maxZ = Mathf.Max(-startPortalLeft.z, -startPortalRight.z, -endPortalLeft.z, -endPortalRight.z);

                var linkNodeCentroid = (startPortal + endPortal) / 2;
                linkNode.centroid.Set(
                    linkNodeCentroid.x,
                    linkNodeCentroid.y,
                    -linkNodeCentroid.z
                );

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

                for (var i = 0; i < areaNodeCount; i++)
                {
                    var convexPolygon = zone.group.nodes[i].vertexIds;
                    for (var j = 2; j < convexPolygon.Count; 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.group.nodes[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.Add(linkNodeID);
                            Vector3 centroid = (v0 + v1 + v2) / 3;
                            if (Vector3.Cross(startPortalLeft - centroid, startPortalRight - centroid).y > 0)
                                StartNode.portals.Add(new int[] {
                                    startPortalLeftIndex,
                                    startPortalRightIndex
                                });
                            else
                                StartNode.portals.Add(new int[] {
                                    startPortalRightIndex,
                                    startPortalLeftIndex
                                });

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

                        if (endNodeID == -1 && IsPointInNode(endPortal, v0, v1, v2))
                        {
                            EndNode = zone.group.nodes[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.Add(endNodeID);
                            if (Vector3.Cross(endPortalLeft - linkNodeCentroid, endPortalRight - linkNodeCentroid).y > 0)
                                linkNode.portals.Add(new int[] {
                                    endPortalLeftIndex,
                                    endPortalRightIndex
                                });
                            else
                                linkNode.portals.Add(new int[] {
                                    endPortalRightIndex,
                                    endPortalLeftIndex
                                });

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

                        if (startNodeID != -1 && endNodeID != -1)
                        {
                            //// Connect as neighbours
                            //(StartNode.neighbours).Add(endNodeID);
                            //if navMeshLink.bidirectional
                            //    EndNode.neighbours.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).Add(new JArray(pAIndex, pBIndex));
                            //if navMeshLink.bidirectional
                            //    EndNode.portals.Add(new int[] {pBIndex, pAIndex));

                            break;
                        }
                    }

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

                zone.group.nodes.Add(linkNode);
            }

            // Create Bounding Volume Hierarchy from Axis Aligned Bounding Box
            {
                // Build Top-Down
                ThreeJSPathFindingHierarchyNode topHierarchyNode = new ThreeJSPathFindingHierarchyNode();

                foreach (var node in zone.group.nodes)
                {
                    topHierarchyNode.AddNodeChild(node);
                }

                topHierarchyNode.Build();

                zone.hierarchies.nodes = topHierarchyNode.Flat();

                var level = topHierarchyNode.Level();

                var nodeCount = 0;

                zone.hierarchies.nodes.ForEach(hNode =>
                {
                    hNode.id = nodeCount++;
                });
            }

            var buildLocation = CreateBuildLocation(selectedAssetBundles[0].assetBundleName);
            if (!Directory.Exists(buildLocation))
                Directory.CreateDirectory(buildLocation);
            File.WriteAllText(buildLocation + $"/{selectedAssetBundles[0].assetBundleName}.TJSNM", JObject.FromObject(zone).ToString(Formatting.None));
            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();
    }

    #region Helpers

    /// <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>
    /// 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, List<int> indices1, List<int> indices2)
    {
        List<int> shareEdge = new List<int>();

        for (int i = 0; i < indices1.Count; i++)
        {
            for (int j = 0; j < indices2.Count; j++)
            {
                var a1 = indices1[i];
                var a2 = i == indices1.Count - 1 ? indices1[0] : indices1[i + 1];
                var b1 = indices2[j];
                var b2 = j == indices2.Count - 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;
    }

    #endregion
}

#region Data Structures

public class ThreeJSPathFindingZone
{
    public List<ThreeJSArea> areas = new List<ThreeJSArea>();
    public List<Vector3> vertices = new List<Vector3>();
    [JsonProperty("groups")]
    public ThreeJSPathFindingGroup group = new ThreeJSPathFindingGroup();
    public ThreeJSPathFindingHierarchy hierarchies = new ThreeJSPathFindingHierarchy();
}

public class ThreeJSArea
{
    public int id = 0;
    public string name = "";
    public float cost = 1f;

}

public class ThreeJSPathFindingGroup
{
    [JsonProperty("0")]
    public List<ThreeJSPathFindingNode> nodes = new List<ThreeJSPathFindingNode>();
}

public class ThreeJSPathFindingNode
{
    public int id;
    public float cost = 1;
    [Obsolete("Legacy property, use ThreeJSPathFindingNode.area instead", false)]
    public string areatype = NavMesh.GetAreaNames()[0];
    public int area = 0;

    /// <summary>
    /// "type" can be "surface" or "link"
    /// </summary>
    public string type = "surface";
    public List<int> vertexIds = new List<int>();

    [JsonIgnore] public float minX = float.MaxValue;
    [JsonIgnore] public float minY = float.MinValue;
    [JsonIgnore] public float minZ = float.MaxValue;
    [JsonIgnore] public float maxX = float.MinValue;
    [JsonIgnore] public float maxY = float.MaxValue;
    [JsonIgnore] public float maxZ = float.MinValue;

    public Vector3 centroid = new Vector3();

    public List<int> neighbours = new List<int>();
    public List<int[]> portals = new List<int[]>();

    [JsonIgnore]
    public List<Vector3> vertices = new List<Vector3>();
}

public class ThreeJSPathFindingHierarchy
{
    [JsonProperty("0")]
    public List<ThreeJSPathFindingHierarchyNode> nodes = new List<ThreeJSPathFindingHierarchyNode>();
}

public class ThreeJSPathFindingHierarchyNode
{
    public int id;
    public float minX;
    public float minY;
    public float minZ;
    public float maxX;
    public float maxY;
    public float maxZ;
    public Vector3 center;

    private List<ThreeJSPathFindingHierarchyNode> _hierarchyChild = new List<ThreeJSPathFindingHierarchyNode>();
    private List<ThreeJSPathFindingNode> _nodeChild = new List<ThreeJSPathFindingNode>();

    public List<int> hierarchyChildId
    {
        get
        {
            List<int> id = new List<int>();
            foreach (var child in _hierarchyChild)
            {
                id.Add(child.id);
            }
            return id;
        }
    }

    public List<int> nodeChildId
    {
        get
        {
            List<int> id = new List<int>();
            if (hierarchyChildId.Count < 1)
            {
                foreach (var child in _nodeChild)
                {
                    id.Add(child.id);
                }
            }
            return id;
        }
    }

    public void AddNodeChild(ThreeJSPathFindingNode node)
    {
        if (_nodeChild.Contains(node))
        {
            Debug.LogError("Node already added as child.");
            return;
        }

        _nodeChild.Add(node);
    }

    public int Level()
    {
        int maxChildLevel = 0;

        foreach (var child in _hierarchyChild)
        {
            int childLevel = child.Level();
            if (childLevel > maxChildLevel)
            {
                maxChildLevel = childLevel;
            }
        }

        return maxChildLevel + 1;
    }

    private void Recalculate()
    {
        minX = float.MaxValue;
        minY = float.MaxValue;
        minZ = float.MaxValue;
        maxX = float.MinValue;
        maxY = float.MinValue;
        maxZ = float.MinValue;
        center = new Vector3();

        foreach (var node in _nodeChild)
        {
            minX = Mathf.Min(minX, node.minX);
            minY = Mathf.Min(minY, node.minY);
            minZ = Mathf.Min(minZ, node.minZ);
            maxX = Mathf.Max(maxX, node.maxX);
            maxY = Mathf.Max(maxY, node.maxY);
            maxZ = Mathf.Max(maxZ, node.maxZ);
        }

        if (maxX < minX || maxY < minY || maxZ < minZ)
        {
            Debug.Log("Here");
        }
        center = new Vector3(
            (minX + maxX) / 2,
            (minY + maxY) / 2,
            (minZ + maxZ) / 2
        );
        return;
    }

    public void Build()
    {
        Recalculate();

        foreach (var child in _hierarchyChild)
        {
            child.Dispose();
        }
        _hierarchyChild.Clear();

        if (_nodeChild.Count < 2)
        {
            return;
        }

        float maxSize = Mathf.Max(maxX - minX, maxY - minY, maxZ - minZ);

        int longestAxis = 1;

        if (maxX - minX == maxSize)
            longestAxis = 1;
        else if (maxY - minY == maxSize)
            longestAxis = 2;
        else if (maxZ - minZ == maxSize)
            longestAxis = 3;

        switch (longestAxis)
        {
            case 1:
                _nodeChild.Sort((a, b) => { return Mathf.RoundToInt(a.centroid.x - b.centroid.x); });
                break;
            case 2:
                _nodeChild.Sort((a, b) => { return Mathf.RoundToInt(a.centroid.y - b.centroid.y); });
                break;
            case 3:
                _nodeChild.Sort((a, b) => { return Mathf.RoundToInt(a.centroid.z - b.centroid.z); });
                break;
            default:
                break;
        }

        int halfCount = Mathf.CeilToInt(_nodeChild.Count / 2f);

        ThreeJSPathFindingHierarchyNode left = new ThreeJSPathFindingHierarchyNode();

        for (int i = 0; i < halfCount; i++)
        {
            left.AddNodeChild(_nodeChild[i]);
        }
        left.Build();

        ThreeJSPathFindingHierarchyNode right = new ThreeJSPathFindingHierarchyNode();

        for (int i = halfCount; i < _nodeChild.Count; i++)
        {
            right.AddNodeChild(_nodeChild[i]);
        }
        right.Build();

        _hierarchyChild.Add(left);
        _hierarchyChild.Add(right);
    }

    public void Dispose()
    {
        _nodeChild.Clear();
        foreach (var child in _hierarchyChild)
        {
            child.Dispose();
        }
        _hierarchyChild.Clear();
    }

    public List<ThreeJSPathFindingHierarchyNode> Flat()
    {
        List<ThreeJSPathFindingHierarchyNode> list = new List<ThreeJSPathFindingHierarchyNode>();

        list.Add(this);

        foreach (var child in _hierarchyChild)
        {
            list.AddRange(child.Flat());
        }

        return list;
    }
}

#endregion

#region Utility

#endregion

#endif
