Tag Archives: Unity

Finding linked faces within a 3d model with Unity C#

Recently I’ve been developing a global environment material shader. One of the main features of the shader is that it takes in relevant data through vertex information, so that all meshes can share the same material (in Unity3d C#). I thought it would be convenient to be able to tag mesh data inside the Unity editor per vertex, face or mesh within a mesh for multi-material models.

For something as useful as selecting meshes within a mesh, also known as elements in 3ds max or linked faces in Blender, there isn’t much information online about how to select them in code. So about a half day of thinking, coding and trial and error, I thought I’d post this solution for others seeking to implement the algorithm.

Problem: How do you get all the vertices of each unique surface within a mesh?
Solution: Given a single triangle face i of vertices, find all vertices of other faces containing i. Then run the same algorithm for each of the vertices found and output the list of all found vertices at the end of recursion.

I made a monobehaviour class called SetVertexColors. This class is assigned to the object which is meant to be edited.

First, a helper function to identify whether two faces are connected.

        /// <summary>
        /// Given two faces, return whether they share any common vertices.
        /// </summary>

        /// <param name="faceA">Face represented as array of vertex indices.</param>
        /// <param name="faceB">Face represented as array of vertex indices.</param>
        /// <returns>bool - whether the faces are connected. </returns>
        bool IsConnected(int[] faceA, int[] faceB)
        {
            for (int i = 0; i < faceA.Length; i++)
                for (int j = 0; j < faceB.Length; j++)
                    if (faceA[i] == faceB[j])
                        return true;
            return false;
        }
 

The magic happens in the below recursive function. It finds each linked face to the first face by iterating the index buffer, then recursively runs the same algorithm adding to the result.

My first instinct was to use a Hashset for the result so that there would not be duplicate values, though I thought List would be ok here since in Unity the vertex buffer is only 16 bits large, and it is the easiest container type to work with. Using a Hashset would have also resulted in another copy at the end for returning an array.

Also by using List in Unity with Mesh.GetTriangles() and managing it yourself, you can avoid copying the triangles buffer to a new array every time it is queried.

        /// <summary>
        /// Given a single triangle face of vertex indices, 
        /// returns a list of all the vertices of all linked faces.
        /// </summary>

        /// <param name="pickedTriangle">The known triangle to find linked faces from.</param>
        /// <param name="triangles">The index buffer triangle list of all vertices in the mesh.</param>
        /// <returns>List<int> - List of all the triangle face indices that represent the surface element.</returns>
        public List<int> GetElement(int[] pickedTriangle, List<int> triangles)
        {
            // Create the return result list, starting with the current picked face
            List<int> result = new List<int>(pickedTriangle);

            // Iterate through the triangle list index buffer by triangle (iterations of 3)
            for (int i = 0; i < triangles.Count; i += 3)
            {
                // Select the (i)th triangle in the index buffer
                int[] curTriangle = new int[3] { triangles[i], triangles[i + 1], triangles[i + 2] };

                // Check if faces are linked
                if (IsConnected(curTriangle, pickedTriangle))
                {
                    // Recursively add all the linked faces to the result
                    result.AddRange(GetElement(curTriangle, triangles));
                }
            }

            return result;
        }

For anyone interested that is also using Unity3d, here is my Editor script code for selecting a face in the scene view to pass to this function. The ray to face intersection triangle picking code is based on the Möller–Trumbore intersection algorithm, which is available here on Wikipedia.

using System.Collections.Generic;
using UnityEngine;
using UnityEditor;

namespace Cyberdeck.Graphics
{
    [CustomEditor(typeof(SetVertexColors))]
    public class SetVertexColorsEditor : Editor
    {
        List<List<int>> m_triangles;
        List<Vector3> m_vertices;

        public void OnSceneGUI()
        {

            if (Event.current.type != EventType.MouseDown)
                return;

            if (Event.current.button != 0)
                return;

            SetVertexColors _target = (SetVertexColors)target;
            Ray ray = HandleUtility.GUIPointToWorldRay(Event.current.mousePosition);
            MeshFilter mf = _target.GetComponent(typeof(MeshFilter)) as MeshFilter;
            Mesh mesh = mf.sharedMesh;

            // Initialize temp buffer data if it doesn't exist
            if (m_triangles == null)
            {
                m_triangles = new List<List<int>>(mesh.vertexCount / 3);
                for (int i = 0; i < mesh.subMeshCount; i++)
                    m_triangles.Add(new List<int>());
            }
            if (m_vertices == null)
                m_vertices = new List<Vector3>(mesh.vertexCount);

            // Retrieve vertex positions from mesh. Using List prevents subsequent copying
            mesh.GetVertices(m_vertices);

            // Accumulate all of the faces an infinite ray may penetrate.
            List<Vector4> candidates = new List<Vector4>();
            for (int i = 0; i < mesh.subMeshCount; i++)
            {
                List<int> triangles = m_triangles[i];
                mesh.GetTriangles(triangles, i);

                for (int j = 0; j < triangles.Count; j += 3) 
                {
                   Vector3 p1 = m_vertices[triangles[j]];
                   Vector3 p2 = m_vertices[triangles[j + 1]];
                   Vector3 p3 = m_vertices[triangles[j + 2]];
                   p1 = _target.transform.TransformPoint(p1);
                   p2 = _target.transform.TransformPoint(p2);
                   p3 = _target.transform.TransformPoint(p3);
                   float dist = Intersect(p1, p2, p3, ray.origin, Vector3.Normalize(ray.direction));

                   if (dist >= 0)
                      candidates.Add(new Vector4(triangles[j], triangles[j + 1], triangles[j + 2], dist));
                }
            }

            // If no intersections occured, user did not click on the mesh
            if (candidates.Count == 0)
                return;

            // Sort the candidate faces for the closest one, which is the intuitivey picked face
            Vector4 best = new Vector4(0, 0, 0, float.MaxValue);
            for (int j = 0; j < candidates.Count; j++)
                if (candidates[j].w < best.w)
                    best = candidates[j];

            int[] pickedFace = new int[] { (int)best.x, (int)best.y, (int)best.z };
            List<int> element = _target.GetElement(pickedFace, new List<int>(mesh.triangles), false);

            // Calls the GetElement function, as well as setting vertex colors to the picked element.
            _target.Apply(element);

            Event.current.Use();
        }

        /// <summary>
        /// Checks if the specified ray hits the triagnlge descibed by p1, p2 and p3.
        /// Möller–Trumbore ray-triangle intersection algorithm implementation.
        /// </summary>

        /// <param name="V1">Vertex 1 of the triangle.</param>
        /// <param name="V2">Vertex 2 of the triangle.</param>
        /// <param name="V3">Vertex 3 of the triangle.</param>
        /// <param name="ray">The ray to test hit for.</param>
        /// <returns><c>true</c> when the ray hits the triangle, otherwise <c>false</c></returns>
        public static float Intersect(Vector3 V1, Vector3 V2, Vector3 V3, Vector3 O, Vector3 D, bool backfaceCulling = true)
        {
            Vector3 e1, e2; //Edge1, Edge2
            Vector3 P, Q, T;
            float det, inv_det;
            float t, u, v;

            //Find vectors for two edges sharing V1
            e1 = V2 - V1;
            e2 = V3 - V1;

            //Begin calculating determinant - also used to calculate u parameter
            P = Vector3.Cross(D, e2);

            //if determinant is near zero, ray lies in plane of triangle or ray is parallel to plane of triangle
            det = Vector3.Dot(e1, P);

            //if determinant is near zero, ray lies in plane of triangle otherwise not
            // if the determinant is negative the triangle is backfacing
            // if the determinant is close to 0, the ray misses the triangle
            if (backfaceCulling)
                if (det < Mathf.Epsilon) return -1f;
                else
                if (Mathf.Abs(det) < Mathf.Epsilon) return -1f;

            inv_det = 1.0f / det;

            //calculate distance from V1 to ray origin
            T = O - V1;

            //Calculate u parameter and test bound
            u = Vector3.Dot(T, P) * inv_det;

            //The intersection lies outside of the triangle
            if (u < 0f || u > 1f) return -1f;

            //Prepare to test v parameter
            Q = Vector3.Cross(T, e1);

            //Calculate V parameter and test bound
            v = Vector3.Dot(D, Q) * inv_det;

            //The intersection lies outside of the triangle
            if (v < 0f || u + v > 1f) return -1f;


            t = Vector3.Dot(e2, Q) * inv_det;
            return t;
        }

    }
}

In this sample, I changed vertex colors on the mesh beyond just picking. Here is the full class to allow that functionality paired with the editor script.

namespace Cyberdeck.Graphics
{
    [ExecuteInEditMode()]
    public class SetVertexColors : MonoBehaviour
    {
        public Color32 m_color;
        private Color32 m_prevColor;
        private List<Color32> m_colorsOut;
        private Mesh m_mesh;
        private List<List<int>> m_triangles;

        void Initialize()
        {
            if (m_mesh == null)
                m_mesh = GetComponent<MeshFilter>().sharedMesh;

            if (m_triangles == null || m_triangles.Count != m_mesh.subMeshCount)
            {
                m_triangles = new List<List<int>>(m_mesh.subMeshCount);
                for (int i = 0; i < m_mesh.subMeshCount; i++)
                {
                    m_triangles.Add(new List<int>());
                    m_mesh.GetTriangles(m_triangles[i], i);
                }
            }

            if (m_colorsOut == null)
            {
                m_colorsOut = new List<Color32>(new Color32[m_mesh.vertexCount]);
                m_mesh.GetColors(m_colorsOut);
            }

            if (m_colorsOut.Count != m_mesh.vertexCount)
            {
                m_colorsOut = new List<Color32>(new Color32[m_mesh.vertexCount]);
            }
        }

        public void Apply(List<int> element)
        {
            Initialize();

            m_prevColor = m_color;

            // Only set the colors for the selected element indices
            for (int i = 0; i < element.Count; i++)
                m_colorsOut[element[i]] = m_color;
            m_mesh.SetColors(m_colorsOut);
        }

        /// <summary>
        /// Given a single triangle face of vertex indices, 
        /// returns a list of all the vertices of all linked faces.
        /// </summary>
        /// <param name="pickedTriangle">The known triangle to find linked faces from.</param>
        /// <param name="triangles">The index buffer triangle list of all vertices in the mesh.</param>
        /// <param name="isDestructive"></param>
        /// <returns></returns>
        public List<int> GetElement(int[] pickedTriangle, List<int> triangles, bool isDestructive = true)
        {
            // Create the return result list, starting with the current picked face
            List<int> result = new List<int>(pickedTriangle);

            // Iterate through the triangle list index buffer by triangle (iterations of 3)
            for (int i = 0; i < triangles.Count; i += 3)
            {
                // Select the (i)th triangle in the index buffer
                int[] curTriangle = new int[3] { triangles[i], triangles[i + 1], triangles[i + 2] };

                // Check if faces are linked
                if (IsConnected(curTriangle, pickedTriangle))
                {
                    if (isDestructive)
                    {
                        triangles[i] = -1;
                        triangles[i + 1] = -1;
                        triangles[i + 2] = -1;
                    }

                    // Recursively add all the linked faces to the result
                    result.AddRange(GetElement(curTriangle, triangles));
                }
            }

            return result;
        }

        /// <summary>
        /// Given two faces, return whether they share any common vertices.
        /// </summary>
        /// <param name="faceA">Face represented as array of vertex indices.</param>
        /// <param name="faceB">Face represented as array of vertex indices.</param>
        /// <returns>bool - whether the faces are connected. </returns>
        bool IsConnected(int[] faceA, int[] faceB)
        {
            for (int i = 0; i < faceA.Length; i++)
                for (int j = 0; j < faceB.Length; j++)
                    if (faceA[i] == faceB[j])
                        return true;
            return false;
        }

    }
}