Using Triangle.Net to make a closer point system in Unity 3D

[AlixGith]

Hi,

I need some help for my open-source RTS retro game.

My question is : Is there a way to use the Transform component (actual position component in unity3D) instead of only its position copy ?

I was also wondering if : the index of each points inside the pre-triangulation List will be the same as the index of each points inside the after-triangulation List ?

I'm usign Triangle.NET to triangulate a set of points.

I'm coding with Unity3D and the goal is to get, after the triangulation, the closer point for each point. And so, the unit will attack the closest point enemy.

The result of the triangulation :

The library seem to only take "vertex" type.

Cause I can get a closer point between the triangulated points but they will have nothing to do anymore with the Unit component at first. I can archive to attach back the triangulated point to the component unit with some tricks but it will consume so much memory.

The whole code :

    public List<Transform> All_unit = new List<Transform>();
    public List<Vector3> vertices = new List<Vector3>();

    LineRenderer lineRenderer;

    void Start()
    {
        // Create a LineRenderer to display on screen
            lineRenderer = gameObject.GetComponent<LineRenderer>();
            lineRenderer.widthMultiplier = 2f;

    }
    void Update() 
    {
        if(All_unit !=null)
        {

            lineRenderer.positionCount = 0;
            vertices.Clear(); 

            // Copy the position 
            for (int i = 0; i < All_unit.Count; i++)
            {
                vertices.Add(All_unit[i].position);

            }

            // Perform Delaunay triangulation on vertices

            var input = new Polygon(All_unit.Count);

            foreach (var vertex in vertices)
            {
                input.Add(new Vertex(vertex.x, vertex.z));

            }

            // Generate mesh.
            var options = new ConstraintOptions() { ConformingDelaunay = true};
            var quality = new QualityOptions() { MinimumAngle = 30 };

            var mesh = input.Triangulate(options, quality);
            List<Vector3> newvertices = new List<Vector3>(); 

            foreach (var vertex in mesh.Vertices)
            {
                newvertices.Add(new Vector3((float)vertex.X, 0, (float)vertex.Y));
            }

            lineRenderer.positionCount = mesh.Triangles.Count*3;

// GET ALL THE Point from the triangulation in order to display it 

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

            foreach(var triangle in mesh.Triangles)
            {
                int label = triangle.Label;

                if (label < 0 )
                {
                    Debug.Log("MFEM element attributes must be positive.");
                }else{
                    if(triangle.GetVertexID(0) < newvertices.Count && triangle.GetVertexID(0) >=0 )
                        {positions_upt.Add(newvertices[triangle.GetVertexID(0)]);}
                    if(triangle.GetVertexID(1) < newvertices.Count && triangle.GetVertexID(1) >=0 )
                        {positions_upt.Add(newvertices[triangle.GetVertexID(1)]);}
                    if(triangle.GetVertexID(2) < newvertices.Count && triangle.GetVertexID(2) >=0 )
                        {positions_upt.Add(newvertices[triangle.GetVertexID(2)]);}
                }

            }

            lineRenderer.SetPositions(positions_upt.ToArray()); 

            // Find closest points // PROBLEM HERE // Positions_upt is only a list of x,y,z positions points and I don't know where to locate inside it the unit transform position. 
            /*
            for (int i = 0; i < positions_upt.Count; i++)
            {
                // ?
            }
            */

        }
    }

[wo80]

To simplify matters, I'd suggest to use lookup tables mapping between Triangle.NET vertices and Unity objects. Use the following code to get started (note that I do not have Unity installed, so this is not tested):

class Test
{
    // Unity objects.
    List<Transform> All_unit = new List<Transform>();

    // Triangle.NET vertices (class instance for better memory performance).
    List<Vertex> vertices = new List<Vertex>();

    // For better memory performance.
    TrianglePool trianglePool = new TrianglePool();
    ITriangulator triangulator = new Dwyer();

    // To find nearest neighbors.
    VertexCirculator vertexCirculator;

    // Map vertex id to Unity object
    Dictionary<int, Transform> triToUnityMap = new Dictionary<int, Transform>();

    // Map Unity object name to vertex
    Dictionary<string, Vertex> unityToTriMap = new Dictionary<string, Vertex>();

    LineRenderer lineRenderer;

    void Start()
    {
        // Create a LineRenderer to display on screen
        lineRenderer = gameObject.GetComponent<LineRenderer>();
        lineRenderer.widthMultiplier = 2f;
    }

    void Update()
    {
        if (All_unit == null || All_unit.Count == 0) return;

        int count = All_unit.Count;

        lineRenderer.positionCount = 0;

        vertices.Clear();
        triToUnityMap.Clear();

        if (vertices.Capacity < count)
        {
            vertices.EnsureCapacity(count);
            triToUnityMap.EnsureCapacity(count);
            unityToTriMap.EnsureCapacity(count);
        }

        // Copy the position
        for (int i = 0; i < All_unit.Count; i++)
        {
            var unit = All_unit[i];

            // IMPORTANT: set correct vertex id.
            var vertex = new Vertex(unit.position.x, unit.position.z) { ID = i };

            vertices.Add(vertex);
            triToUnityMap.Add(i, unit);

            // IMPORTANT: in case you haven't set names for the Unity objects
            //            you have to do it here!
            //unit.name = i.ToString();
            unityToTriMap.Add(unit.name, vertex);
        }

        // Perform Delaunay triangulation on vertices

        // IMPORTANT: if you do not plan to create a Voronoi diagram, you do not
        //            need the ConformingDelaunay option!
        //var options = new ConstraintOptions() { ConformingDelaunay = true };

        // IMPORTANT: if you plan to use the mesh for nearest neighbor search, do
        //            not impose quality options!
        //var quality = new QualityOptions() { MinimumAngle = 30 };

        var mesh = (Mesh)triangulator.Triangulate(vertices, new Configuration(
            () => RobustPredicates.Default,
            () => trianglePool.Restart()));

        vertexCirculator = new VertexCirculator(mesh);

        // GET ALL THE Point from the triangulation in order to display it 

        var positions_upt = new List<Vector3>();

        foreach (var edge in mesh.Edges)
        {
            positions_upt.Add(triToUnityMap[edge.P0].position);
            positions_upt.Add(triToUnityMap[edge.P1].position);
        }

        lineRenderer.SetPositions(positions_upt.ToArray());
    }

    public Transform FindClosest(Transform obj)
    {
        if (vertexCirculator == null)
        {
            throw new Exception("Vertex circulator is null.");
        }

        var vertex = unityToTriMap[obj.name];

        Vertex closest = null;
        double closestDist = double.MaxValue;

        foreach (var neighbor in vertexCirculator.EnumerateVertices(vertex))
        {
            var dx = (vertex.X - neighbor.X);
            var dy = (vertex.Y - neighbor.Y);

            var squareDist = dx * dx + dy * dy;

            if (squareDist < closestDist)
            {
                closest = neighbor;
                closestDist = squareDist;
            }
        }

        if (closest == null)
        {
            throw new Exception("Unconnected vertex? Check mesh topology!");
        }

        return triToUnityMap[closest.ID];
    }
}

[AlixGith]

First, Thanks a lot for the answer ! I was thinking about two distinct list and dictionnaries but I'm lacking of knowledges on these, you save my life.

I'll try this as soon as possible and get back to you.

One final question, talking about better memory performance, do you think that this method is better than a constant linear closest distance computation as you are the owner of the library ? I'm doing this because I believe so : if I've a thousand unit in-game, it will be a mess to compare distance between each point and find closest.

[wo80]

One final question, talking about better memory performance, do you think that this method is better than a constant linear closest distance computation as you are the owner of the library ? I'm doing this because I believe so : if I've a thousand unit in-game, it will be a mess to compare distance between each point and find closest.

Well, the problem you are trying to solve is nearest neighbor search, or in your case all-nearest-neighbors. For n vertices, the naive approach you are describing will take O(n^2), which you want to avoid by all means. Delaunay takes O(n*log(n)), which makes a significant difference.

There are of course alternatives, for example using spatial data structures like quadtrees, which most likely will perform even better.

[wo80]

Here's a simplified version. In case you do all the nearest neighbor search inside the Update() method, there's no need for the dictionaries since the mapping between Unity and Triangle.NET objects is given implicitly by their array indices:

class Test
{
    // Unity objects.
    List<Transform> All_unit = new List<Transform>();

    // Triangle.NET vertices (class instance for better memory performance).
    List<Vertex> vertices = new List<Vertex>();

    // For better memory performance.
    TrianglePool trianglePool = new TrianglePool();
    ITriangulator triangulator = new Dwyer();

    // To find nearest neighbours.
    VertexCirculator vertexCirculator;

    LineRenderer lineRenderer;

    void Start()
    {
        // Create a LineRenderer to display on screen
        lineRenderer = gameObject.GetComponent<LineRenderer>();
        lineRenderer.widthMultiplier = 2f;
    }

    void Update()
    {
        if (All_unit == null || All_unit.Count == 0) return;

        int count = All_unit.Count;

        lineRenderer.positionCount = 0;

        vertices.Clear();

        if (vertices.Capacity < count)
        {
            vertices.EnsureCapacity(count);
        }

        // Copy the position
        for (int i = 0; i < count; i++)
        {
            var pos = All_unit[i].position;

            // IMPORTANT: set correct vertex id (corresponding to index in All_unit).
            //            This will automatically establish the mapping between Unity
            //            and Triangle.NET objects.

            vertices.Add(new Vertex(pos.x, pos.z) { ID = i });
        }

        // Perform Delaunay triangulation on vertices

        var mesh = (Mesh)triangulator.Triangulate(vertices, new Configuration(
            () => RobustPredicates.Default,
            () => trianglePool.Restart()));

        vertexCirculator = new VertexCirculator(mesh);

        // GET ALL THE Point from the triangulation in order to display it 

        var positions_upt = new List<Vector3>();

        foreach (var edge in mesh.Edges)
        {
            positions_upt.Add(All_unit[edge.P0].position);
            positions_upt.Add(All_unit[edge.P1].position);
        }

        lineRenderer.SetPositions(positions_upt.ToArray());

        // Find all nearest neighbors
        for (int i = 0; i < count; i++)
        {
            int closedId = FindClosest(vertices[i]);

            if (closedId < 0)
            {
                // Something went wrong
            }
            else
            {
                var closest = All_unit[closedId];
            }
        }
    }

    int FindClosest(Vertex vertex)
    {
        Vertex closest = null;
        double closestDist = double.MaxValue;

        foreach (var neighbor in vertexCirculator.EnumerateVertices(vertex))
        {
            var dx = (vertex.X - neighbor.X);
            var dy = (vertex.Y - neighbor.Y);

            var squareDist = dx * dx + dy * dy;

            if (squareDist < closestDist)
            {
                closest = neighbor;
                closestDist = squareDist;
            }
        }

        return closest == null ? -1 : closest.ID;
    }
}

[AlixGith]

Okay, so far, i've managed to do many things out of your code. Thanks a lot. I've made some modification to the triangulation so i get the information I want :

`public class triangulation_code : MonoBehaviour { public List All_unit = new List(); public GameObject All_unit_Mother;

// Triangle.NET vertices (class instance for better memory performance).
List<Vertex> vertices = new List<Vertex>();

// For better memory performance.
TrianglePool trianglePool = new TrianglePool();
ITriangulator triangulator = new Dwyer();

// To find nearest neighbours.
VertexCirculator vertexCirculator;

LineRenderer lineRenderer;

void Start()
{
    // Create a LineRenderer
    lineRenderer = gameObject.GetComponent<LineRenderer>();
    lineRenderer.widthMultiplier = 2f;

}

void LateUpdate() 
{
    if(All_unit !=null || All_unit.Count >2)
    {
        All_unit.Clear();
        foreach (Transform tr in All_unit_Mother.transform.GetComponentsInChildren<Transform>(true))
        {
            if(tr.gameObject.GetComponent<UnityEngine.AI.NavMeshAgent>())
            All_unit.Add(tr); 
        }
        int count = All_unit.Count;

        lineRenderer.positionCount = 0;

        //octree = new PointOctree<Vector3>(bounds.size.x, bounds.center, 0);
        vertices.Clear(); 
        /*
        if (vertices.Capacity < count)
        {
            vertices.EnsureCapacity(count);
        }*/

        // Copy the position
        for (int i = 0; i < count; i++)
        {
            if(All_unit[i] != null)
            {

            var pos = All_unit[i].position;

            // IMPORTANT: set correct vertex id (corresponding to index in All_unit).
            //            This will automatically establish the mapping between Unity
            //            and Triangle.NET objects.

            vertices.Add(new Vertex(pos.x, pos.z) { ID = i });

            }else{
                return;
            }
        }

        // Perform Delaunay triangulation on vertices
        var mesh = (TriangleNet.Mesh)triangulator.Triangulate(vertices, new Configuration(
            () => RobustPredicates.Default,
            () => trianglePool.Restart()));

        vertexCirculator = new VertexCirculator(mesh);

        lineRenderer.positionCount = mesh.Triangles.Count*3;

        // GET ALL THE Point from the triangulation in order to display it 

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

        foreach (var vertex in mesh.Vertices)
        {
            newvertices.Add(new Vector3((float)vertex.X, 0, (float)vertex.Y));
        }

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

        foreach(var triangle in mesh.Triangles)
        {
            int label = triangle.Label;

            if (label < 0 )
            {
                Debug.Log("MFEM element attributes must be positive.");
            }else{
                if(triangle.GetVertexID(0) < newvertices.Count && triangle.GetVertexID(0) >=0 )
                    {positions_upt.Add(newvertices[triangle.GetVertexID(0)]);}
                if(triangle.GetVertexID(1) < newvertices.Count && triangle.GetVertexID(1) >=0 )
                    {positions_upt.Add(newvertices[triangle.GetVertexID(1)]);}
                if(triangle.GetVertexID(2) < newvertices.Count && triangle.GetVertexID(2) >=0 )
                    {positions_upt.Add(newvertices[triangle.GetVertexID(2)]);}
            }

        }

        lineRenderer.SetPositions(positions_upt.ToArray()); 
        // Find all nearest neighbors
        for (int i = 0; i < count; i++)
        {
            int closedId = FindClosest(vertices[i], All_unit[i].gameObject.GetComponent<Unit_base_class>().range_sight+10, (byte)All_unit[i].gameObject.GetComponent<Unit_base_class>().color_team);

            if (closedId < 0)
            {
                // Something went wrong
            }
            else
            {
                var closest = All_unit[closedId];

                if(closest!=null && All_unit[i].gameObject.GetComponent<Unit_base_class>().selected == false)
                {
                    if(All_unit[i].gameObject.GetComponent<Unit_base_class>().color_team != closest.gameObject.GetComponentInParent<Unit_base_class>().color_team)
                    {
                        All_unit[i].gameObject.GetComponent<Unit_base_class>().cible_unit = closest.transform; 
                    }
                }
            }
        }

    }
}

int FindClosest(Vertex vertex, float range_dist, byte color)
{
    Vertex closest = null;
    double closestDist = double.MaxValue;

    foreach (var neighbor in vertexCirculator.EnumerateVertices(vertex))
    {
        var neighbor_temp = new Vector3((float)neighbor.X, 0, (float)neighbor.Y);
        var vertex_vector3 = new Vector3((float)vertex.X, 0, (float)vertex.Y);
        float dist = Vector3.Distance(neighbor_temp, vertex_vector3);

        if (dist < closestDist && dist <= range_dist && All_unit[neighbor.ID].gameObject.GetComponentInParent<Unit_base_class>().color_team != color)
        {
            closest = neighbor;
            closestDist = dist;
        }
    }

    return closest == null ? -1 : closest.ID;
}

} `

This allow me to make a distance and contact closer point for unit interaction. I wonder if this could work with out of thousands units... Gotta test out :) I think this issue is closed now. Waiting for your respond. thanks again.

[wo80]

One remark maybe: I guess the line rendering code is just added for debugging, so this is not important, but

foreach(var triangle in mesh.Triangles)
{
    int label = triangle.Label;

    if (label < 0 )
    {
        Debug.Log("MFEM element attributes must be positive.");
    }else{
        if(triangle.GetVertexID(0) < newvertices.Count && triangle.GetVertexID(0) >=0 )
            {positions_upt.Add(newvertices[triangle.GetVertexID(0)]);}
        if(triangle.GetVertexID(1) < newvertices.Count && triangle.GetVertexID(1) >=0 )
            {positions_upt.Add(newvertices[triangle.GetVertexID(1)]);}
        if(triangle.GetVertexID(2) < newvertices.Count && triangle.GetVertexID(2) >=0 )
            {positions_upt.Add(newvertices[triangle.GetVertexID(2)]);}
    }
}

doesn't make much sense to me. Try the code I already suggested above

foreach (var edge in mesh.Edges)
{
    positions_upt.Add(All_unit[edge.P0].position);
    positions_upt.Add(All_unit[edge.P1].position);
}