How to find connected mesh triangles?

I have an object that I’m raycasting to, and when I hit a button I want to start a “signal” on the mesh surface, starting from the triangle that the raycast hit. The signal is just vertex coloring: I want the first triangle to turn yellow and then I want yellow to spread outwards from the triangle to other triangles that are touching it, and then to the triangles that are touching those, etc. Like so.

My problem is that the triangle array isn’t really sorted like that. Triangles that share a face share two vertices. I printed out the triangle array of the default sphere mesh, and it seems like touching triangles are near each other in the triangle array, but not necessarily and not predictably near each other.

Is there a convenient way to do this, besides for parsing through the entire triangle array and looking for matches? I’d like to do this with a 14,000+ vertex geometry eventually, so if you can’t rely on the touching triangles to be near each other in the array, that would be quite a performance cost to find the touching triangles.

No, there’s no way around analysing the actual triangles. However you can store the neighbor information in a dictionary. To do this you probably want to first create a dictionary with all edges. That way you can simply iterate through all triangles and first store which edge is shared by which two triangles. Once you have that you can simply look up each of the 3 edges for each triangle to determine the 3 neighbor triangles. So at the end you have a dictionary which gives you a list of 3 triangle indices for each triangle which will be the neighbors of each triangle.

Keep in mind that finding shared edges of triangles which do not share the same vertices is a bit more tricky. So it depends on what kind of mesh you have and if the vertices are actually shared between the neighbors. If you have a fully shared mesh you don’t need to access the vertices at all since all you need are the indices of the triangles. However if your mesh might have “seams” (different UVs, normals, colors, …) you have to manually match the different vertices based on their positions. In this case it gets a bit tricky since identifying the same edges is more complicated. In this case you may need another step to create a vertices lookup to determine which vertices are actually the same.

I just had some time and quickly wrote this helper class:

public class MeshTriangleNeighbors
{
    public class Vertex
    {
        public Vector3 position;
    }

    public struct Edge
    {
        public Vertex v1;
        public Vertex v2;
        public Edge(Vertex aV1, Vertex aV2)
        {
            // ensure the same order to guarantee equality
            if (aV1.GetHashCode() > aV2.GetHashCode())
            {
                v1 = aV1; v2 = aV2;
            }
            else
            {
                v1 = aV2; v2 = aV1;
            }
        }
    }
    public class TrianglePair
    {
        public int t1 = -1;
        public int t2 = -1;
        public bool Add(int aTriangleIndex)
        {
            if (t1 == -1)
                t1 = aTriangleIndex;
            else if (t2 == -1)
                t2 = aTriangleIndex;
            else
                return false;
            return true;
        }

    }
    public class Neighbors
    {
        public int t1 = -1;
        public int t2 = -1;
        public int t3 = -1;
    }



    Dictionary<int, Vertex> verticesLookup = new Dictionary<int, Vertex>();
    Dictionary<Edge, TrianglePair> edges;

    // mesh vertex index as key
    public static List<Vertex> FindSharedVertices(Vector3[] aVertices)
    {
        var list = new List<Vertex>();
        for (int i = 0; i < aVertices.Length; i++)
        {
            Vertex v = null;
            foreach(var item in list)
            {
                if ((item.position - aVertices*).sqrMagnitude < 0.0001f)*

{
v = item;
break;
}
}
if (v == null)
{
v = new Vertex { position = aVertices };
}
list.Add(v);
}
return list;
}
public static Dictionary<Edge, TrianglePair> CreateEdgeList(List aTriangles )
{
var res = new Dictionary<Edge, TrianglePair>();
int count = aTriangles.Count / 3;
for(int i = 0; i < count; i++)
{
Vertex v1 = aTriangles[i*3 ];
Vertex v2 = aTriangles[i*3 + 1];
Vertex v3 = aTriangles[i*3 + 2];
TrianglePair p;
Edge e;
e = new Edge(v1, v2);
if (!res.TryGetValue(e, out p))
{
p = new TrianglePair();
res.Add(e, p);
}
p.Add(i);
e = new Edge(v2, v3);
if (!res.TryGetValue(e, out p))
{
p = new TrianglePair();
res.Add(e, p);
}
p.Add(i);
e = new Edge(v3, v1);
if (!res.TryGetValue(e, out p))
{
p = new TrianglePair();
res.Add(e, p);
}
p.Add(i);
}
return res;
}

public static List GetNeighbors(Dictionary<Edge, TrianglePair> aEdgeList, List aTriangles)
{
var res = new List();
int count = aTriangles.Count / 3;
for (int i = 0; i < count; i++)
{
Vertex v1 = aTriangles[i * 3 ];
Vertex v2 = aTriangles[i * 3 + 1];
Vertex v3 = aTriangles[i * 3 + 2];
TrianglePair p;
if (aEdgeList.TryGetValue(new Edge(v1, v2), out p))
{
if (p.t1 == i)
res.Add(p.t2);
else
res.Add(p.t1);
}
else
res.Add(-1);
if (aEdgeList.TryGetValue(new Edge(v2, v3), out p))
{
if (p.t1 == i)
res.Add(p.t2);
else
res.Add(p.t1);
}
else
res.Add(-1);
if (aEdgeList.TryGetValue(new Edge(v3, v1), out p))
{
if (p.t1 == i)
res.Add(p.t2);
else
res.Add(p.t1);
}
else
res.Add(-1);
}
return res;
}
public static List GetNeighbors(Mesh aMesh)
{
var vertexList = FindSharedVertices(aMesh.vertices);
var tris = aMesh.triangles;
var triangles = new List(tris.Length);
foreach (var t in tris)
triangles.Add(vertexList[t]);
var edges = CreateEdgeList(triangles);
return GetNeighbors(edges, triangles);
}
}
With this class you can simply use MeshTriangleNeighbors.GetNeighbors(mesh); to get a List with all the neighbor information. The returned List is designed similar to the triangles array, but instead of referencing vertices, each triple of numbers represent the 3 neighbor triangle indices for a triangle. Note that i did not store the first vertex index of the triangle, but the actual triangle index (first vertex index divided by 3). For example
*[0] : 2 // *
[1] : 1 // First triangle neighbors
[2] : 3 // /
*[3] : 0 // *
[4] : 4 // Second triangle neighbors
[5] : 6 // /

Since a mesh can not be closed (or if splitted vertices are too far apart so they aren’t recognised as the same) it’s possible that a triangle doesn’t have 3 neighbors. If an edge of a triangle doesn’t have a “partner”, the index will be “-1”. For example the default quad mesh in Unity (only two triangles) only has one shared edge. The result looks like this: [1,-1,-1,0,-1,-1] So the first triangle (index 0) has one neighbor (index 1) and the second triangle (index 1) has one neighbor (index 0). All other edges (the 4 borders of the quad) do not have a neighbor. When tested with the sphere, cube or capsule mesh every triangle has 3 neighbors as they are closed meshes.
Note that 0.0001f in the “FindSharedVertices” method determines when two or more vertices are considered “equal”. In most cases splitted vertices should have exactly the same position. However in some cases there might be a small error. Note that this threshold is the squared distance, so the actual tolerance is 0.01
Keep in mind that calling “GetNeighbors” creates quite a bit of garbage when called. Though only the resulting List<int> is required in the end. You should use this method only once at start or you could even calculate the list at edit time and store it somewhere

People are paranoyed with arrays. Don’t ever listen to those with actual C# background.
Array is something you don’t want to use, because that is, well, casual, boring and casual.
All you need is a script that holds connected triangles info.
14.000 trix mesh, well, 14000 scripts, but you enable those only if a triangle is activated. And you activate first one on raycast.