A* Pathfinding Project

Possible to use concave MeshCollider to update GraphUpdateScene.points?


#1

I’m using the GraphUpdateScene component to mark some areas on my map.
Until now I positioned all point by hand and I want to know if there’s anyway I could use a MeshCollider (concave) to extract the points, I’m being trying to figure a way to solve it for a while and can’t solve this problem.
On my game I already have the mesh colliders which define this area (which are used by another system), what I was trying to do was to read the 3d mesh and extract the top surface outter vertex and then pass that into GraphUpdateScene.points.

Below are some examples of the meshs I have (blue color is the mesh), all meshes are 3d and have about 1m height (vertex on top and bottom are always aligned and only vary on Y axis), I need to extract the green dots and remove the red ones to be able to use them, also in order so the GraphUpdateScene component doesn’t break.

autoGraph

Btw, is there any other way to go about it? I’m new to the asset so there might be an easier option.


#2

I made a script for you. It reads the mesh’s triangles, filters the ones that have normals pointing to the world’s up direction, then catch every triangle connection (edges) and remove the ones that are overlapping, giving to you only the external edges of the mesh.
I’m not sure if it is 100% accurate but worked on every mesh I tested.
Just put this script on the mesh’s GameObject and call Generate() before you bake the grid.

using System.Linq;
using System.Collections.Generic;
using UnityEngine;
using Pathfinding;

public class GraphUpdateSceneGenerator : MonoBehaviour
{
    List<VerticeConnection> verticesConnections = new List<VerticeConnection>();
    List<VerticeConnection> organizedConnections = new List<VerticeConnection>();

    public void Generate()
    {
        ReadMesh();
        CreateGraphPoints();
    }

    void ReadMesh()
    {
        ClearConnections();

        Mesh mesh = GetComponent<MeshFilter>().sharedMesh;

        List<Vector3> meshVertices = mesh.vertices.ToList();
        List<Vector3> meshNormals = mesh.normals.ToList();
        List<int> meshTriangles = mesh.triangles.ToList();

        for(int i = 0; i < meshVertices.Count; i++)
            meshVertices[i] = meshVertices[i];

        List<Triangle> triangles = new List<Triangle>();

        for(int i = 0; i < meshTriangles.Count; i+=3)
        {
            Triangle triangle = new Triangle();
            triangle.Vertices = new Vector3[] 
            {
                meshVertices[meshTriangles[i]],
                meshVertices[meshTriangles[i+1]],
                meshVertices[meshTriangles[i+2]]
            };

            triangle.Normals = new Vector3[] 
            {
                meshNormals[meshTriangles[i]],
                meshNormals[meshTriangles[i+1]],
                meshNormals[meshTriangles[i+2]]
            };
            
            triangles.Add(triangle);
        }

        foreach (Triangle triangle in triangles)
        {
            if(triangle.Normals.Count(normal => Vector3.Dot(normal, Vector3.up) > 0.9f) == 3)
                verticesConnections.AddRange(triangle.GetConnections());
        }

        foreach (VerticeConnection connectionA in verticesConnections)
        {
            foreach (VerticeConnection connectionB in verticesConnections)
            {
                if(connectionA == connectionB)
                    continue;

                if(IsSameLine(connectionA.PointA, connectionA.PointB, connectionB.PointA, connectionB.PointB))
                {
                    connectionA.Intersecting = true;    
                    connectionB.Intersecting = true;
                }
            }
        }

        organizedConnections = OrganizeConnections(verticesConnections.Where(connection => !connection.Intersecting).ToList());

        int currentZone = 1;
        VerticeConnection startingPoint = organizedConnections.First();
        for (int i = 0; i < organizedConnections.Count; i++)
        {
            VerticeConnection connection = organizedConnections[i];
            connection.Zone = currentZone;

            if(startingPoint.Zone != connection.Zone)
                startingPoint = connection;

            if(startingPoint.PointA.EquivalentTo(connection.PointB))
                currentZone++;
        }
    }

    void CreateGraphPoints()
    {
        DestroyGraphs();

        if(organizedConnections == null || organizedConnections.Count == 0)
            return;

        int zone = organizedConnections.First().Zone;
        List<VerticeConnection> zoneConnections = organizedConnections.Where(connection => connection.Zone == zone).ToList();

        while(zoneConnections != null && zoneConnections.Count > 0)
        {
            GraphUpdateScene gus = gameObject.AddComponent<GraphUpdateScene>();
            gus.convex = false;
            gus.modifyTag = true;
            gus.setTag = 0;

            List<Vector3> points = new List<Vector3>();

            foreach (VerticeConnection connection in zoneConnections)
                points.Add(connection.PointA);
            
            gus.points = points.ToArray();
            zone++;
            zoneConnections = organizedConnections.Where(connection => connection.Zone == zone).ToList();
        }
    }

    void ClearConnections()
    {
        verticesConnections.Clear();
        organizedConnections.Clear();
    }

    void DestroyGraphs()
    {
        GraphUpdateScene[] components = GetComponents<GraphUpdateScene>();
        for (int i = components.Length - 1; i >= 0; i--)
            DestroyImmediate(components[i]);
    }

    List<VerticeConnection> OrganizeConnections(List<VerticeConnection> connections)
    {
        List<VerticeConnection> newList = new List<VerticeConnection>();
        List<VerticeConnection> pendentConnections = connections;

        VerticeConnection firstConnection = connections.First();

        int connectionsCount = connections.Count;
        int currentCount = 2;

        newList.Add(firstConnection);
        pendentConnections.Remove(firstConnection);
        
        while(currentCount <= connectionsCount)
        {
            Vector3 lastPosition = newList.Last().PointB;
            VerticeConnection nextConnection = pendentConnections.FirstOrDefault(connection => connection.PointA.EquivalentTo(lastPosition) || connection.PointB.EquivalentTo(lastPosition));

            if(nextConnection == null)
                nextConnection = pendentConnections.First();
                
            VerticeConnection fixedConnection;

            if (nextConnection.PointA.EquivalentTo(lastPosition))
                fixedConnection = new VerticeConnection(nextConnection.PointA, nextConnection.PointB);
            else
                fixedConnection = new VerticeConnection(nextConnection.PointB, nextConnection.PointA);

            currentCount++;

            newList.Add(fixedConnection);
            pendentConnections.Remove(nextConnection);
        }

        return newList;
    }

    private void OnDrawGizmos() 
    {
        
    }	

    class Triangle 
    {
        public Vector3[] Vertices;
        public Vector3[] Normals;

        public List<VerticeConnection> GetConnections()
        {
            List<VerticeConnection> connections = new List<VerticeConnection>();
            
            connections.Add(new VerticeConnection(Vertices[0], Vertices[1]));
            connections.Add(new VerticeConnection(Vertices[1], Vertices[2]));
            connections.Add(new VerticeConnection(Vertices[2], Vertices[0]));

            return connections;
        }
    }

    class VerticeConnection 
    {
        public Vector3 PointA;
        public Vector3 PointB;

        public bool Intersecting = false;

        public int Zone;

        public VerticeConnection(Vector3 pointA, Vector3 pointB)
        {
            PointA = pointA;
            PointB = pointB;
        }   
    }
}
public static bool IsSameLine(Vector3 pointA1, Vector3 pointA2, Vector3 pointB1, Vector3 pointB2)
{
        return pointA1.EquivalentTo(pointB1) && pointA2.EquivalentTo(pointB2) || pointA2.EquivalentTo(pointB1) && pointA1.EquivalentTo(pointB2);
}
public static bool EquivalentTo (this Vector3 pointA, Vector3 pointB)
{
    return return (pointA - pointB).sqrMagnitude <= 0.01f;
}

#3

Sorry for the late answer. I have been traveling and have not been able to answer support requests for some time.

Looks like orlandobatista already made a script for you. Nice!

I was just going to add that the NavmeshCut.CalculateMeshContour method does pretty much exactly this. It does not extract the top facing triangles, however it does filter out the inner vertices and extracts the contours of the mesh. I think the NavmeshCut.CalculateMeshContour version is much faster than @orlandobatista’s version. It does however require that the mesh uses soft normals everywhere, which might not work for you.