Loop through triangles performance issue

Unity Engine
, , ,
1

Context: I am making an AR game with meshing. I want to have a cutout of the realtime generated meshes. Right now I followed a tutorial, which works, but performance is really bad. This is mostly because GC and allocations. The performance issue arrives from a.GetValue(i).
Is there any way how to properly do this with decent performance (a lag spike is fine, but right now it takes 3-15 seconds to load the cutout.
I use render textures to make a ‘portal’ in AR. The portal is wrapped onto real life geometry with the realtime meshing.

Here is the code used:

trackedObject = collision.transform;

        mesh = new Mesh { name = "portalMesh" };
        GameObject go = Instantiate(gameObject, gameObject.transform.parent);
        go.layer = LayerMask.NameToLayer("Stencil");
        Destroy(go.GetComponent<PortalMeshGenerator>());
        Destroy(go.GetComponent<MeshCollider>());
        filter = go.GetComponent<MeshFilter>();
        go.GetComponent<Renderer>().material.shader = shader;
        //go.GetComponent<Renderer>().material = null;
        orignormals = filter.mesh.normals;
        origvertices = filter.mesh.vertices;
        origuvs = filter.mesh.uv;
        origtriangles = filter.mesh.triangles;

        vertices = new Vector3[origvertices.Length];
        normals = new Vector3[orignormals.Length];
        uvs = new Vector2[origuvs.Length];
        triangles = new int[origtriangles.Length];
        trianglesDisabled = new bool[origtriangles.Length];

        orignormals.CopyTo(normals, 0);
        origvertices.CopyTo(vertices, 0);
        origtriangles.CopyTo(triangles, 0);
        origuvs.CopyTo(uvs, 0);

        trisWithVertex = new List<int>[origvertices.Length];
        for (int i = 0; i < origvertices.Length; ++i)
        {
            trisWithVertex[i] = origtriangles.IndexOf(i); //Performance issue
        }
        filter.mesh = GenerateMeshWithHoles();

        go.transform.position = transform.position;

public static List<int> IndexOf(this Array a, object o)
    {
        List<int> result = new List<int>();
        for (int i = 0; i < a.Length; ++i)
        {
            if (a.GetValue(i).Equals(o)) // performance issue
            {
                result.Add(i);
            }
        }
        result.Sort();
        return result;
    }
2

Well, your IndexOf extension method is way to “generic” and not actuall “generic” ^^. Your argument o is of type object. So since you check for an integer, that argument has to be boxed as well. Likewise, as you already said, GetValue of the Array class also returns an object, so the element also needs to be boxed each iteration. So the first improvement would be to actually create a generic variant:

    public static List<int> IndicesOf<T>(this T[] aArray, T aValue)
    {
        List<int> result = new List<int>();
        for (int i = 0; i < aArray.Length; ++i)
        {
            if (Comparer<T>.Default.Compare(aArray[i], aValue) == 0)
            {
                result.Add(i);
            }
        }
        return result;
    }

Note I renamed the method to IndicesOf as it does not return an index but a list of indices. I also removed the Sort call as this is completely pointless since the default Sort would sort the numbers in ascending order. However since we go through the indices in ascending order and add them in exactly that order, the elements would already be sorted.

This should reduce the amount of garbage created quite a bit as well as boost the actual runtime.

However you still allocate a List for every vertex of your mesh. We don’t know how large your mesh is, but this of course also adds up. Keep in mind that the amount of memory allocated is most the time not as important as the number of allocations. Having 1 object that requires 20MB is far better than having 200000 objects with 100B. So depending on the number of indices per vertex (those usually shouldn’t be too high) you could try using something like my StructList. So instead of having an array of integer Lists, you could have an array of StructList16. Each StructList16 is essentially just a struct with a fix capacity of 16 elements, so all elements in our array have the same size, namely 64 bytes. It has the most of the same methods as a normal “List” but is actually a struct. It even has a struct Enumerator so you can use foreach without any allocation. However you can not use linq without a memory allocation since linq only works on the IEnumerable interfaces and interfaces always requires a reference type. Structs could implement interfaces but always need to be boxed.

Also it should be obvious, if you would need more than 16 elements per vertex, this would not work as those lists have a fix capacity that can not change. So depending on your usecase this may not be a viable solution. Also keep in mind that the code that is using your “trisWithVertex” array may also need to be adjusted.

We don’t know how you actually use the “trisWithVertex” array. Though usually creating lookup tables / dictionaries is better for performance. Though it depends on your algorithm and using a dictionary is not always possible.

3

Thanks a lot!
I will try and implement this tomorrow (right now too fried after a workday), since I couldn’t get it working right now.

If you are curious, this is the rest from the code:

Mesh GenerateMeshWithHoles()
    {
        Vector3 trackPos = trackedObject.position;
        for (int i = 0; i < origvertices.Length; ++i)
        {
            Vector3 v = new Vector3(origvertices[i].x * transform.localScale.x, origvertices[i].y * transform.localScale.y, origvertices[i].z * transform.localScale.z);
            if ((v + transform.position - trackPos).magnitude > minDistance)
            {
                for (int j = 0; j < trisWithVertex[i].Count; ++j)
                {
                    int value = trisWithVertex[i][j];
                    int remainder = value % 3;
                    trianglesDisabled[value - remainder] = true;
                    trianglesDisabled[value - remainder + 1] = true;
                    trianglesDisabled[value - remainder + 2] = true;
                }
            }
        }
        triangles = origtriangles;
        triangles = triangles.RemoveAllSpecifiedIndicesFromArray(trianglesDisabled).ToArray();

        mesh.SetVertices(vertices.ToList<Vector3>());
        mesh.SetNormals(normals.ToList());
        mesh.SetUVs(0, uvs.ToList());
        mesh.SetTriangles(triangles, 0);
        for (int i = 0; i < trianglesDisabled.Length; ++i)
            trianglesDisabled[i] = false;
        return mesh;
    }

The code originally was to redo the hole generation each frame on a plane, but I only generate the mesh once, since we don’t need more.

This is the guide originally used (but I flipped it to make a cutout instead of a hole):
https://www.youtube.com/watch?v=4r9IwX17UbY

4

As I thought, this is a very inefficient way of removing triangles ^^. In fact, you’re not actually deleting the vertices from the vertices array which would require a complete remesh, instead you’re just removing the triangles which have vertices within a certain threshold of that other object. This can be implemented way faster and simpler.

A few steps:

  • Avoid using arrays. Unity’s Mesh class now has GetVertices and GetTriangles which work directly with Lists. This often simplifies a lot code and if the code needs to run every frame, it avoids memory allocation all together when you reuse the Lists.
  • Just directly iterate through the triangles. Check if one of the 3 vertices is under shte threshold and remove it.
  • The distance check can be simplified in two ways. First of all instead of manually converting all the vertices into worldspace (you’re currently missing the rotation anyways), it’s much easier to convert the reference location from worldspace into local space. That way we can simply do the distance check in local space. Also instead of using “magnitude” you can use sqrMagnitude and the square of the threshold. The result is the same but doesn’t require a square root.
  • Since the order of the triangles inside the triangles array / List usually doesn’t matter, removing triangles from a list can actually be done in O(1) time complexity. The trick is to swap the triangle you want to remove with the last triangle in the list. Removing the last triangle is O(1) since it just has to reduce the internal count. So effectively we just copy the last triangle to the one we want to remove and remove the last 3 values from the list. Note for this to work without any extra efford, we should always iterate through the triangles list backwards, starting with the last and going downwards towards 0.
  • Since you essentially want a duplicate mesh, just with altered triangle array, the easiest way to get that mesh is to simply Instantiate the mesh which gives you an exact copy. Now you just have to adjust / generate the triangles List and only set the new triangles and you’re done.

So the whole process of removing triangles, when we cache the vertices and triangles arrays / lists, can be done without any memory allocation (besides the first one).

I quickly created this script:
CutoutMesh

public class CutoutMesh : MonoBehaviour
{
    public Transform referenceObject;
    public float minDist = 0;
    public float maxDist = float.PositiveInfinity;
    public bool GenerateOnStart = true;
    public bool AutoUpdate = false;
    private List<Vector3> vertices;
    private List<int> origTris;
    private List<int> carvedTris;
    private Mesh carvedMesh;

    public void Start()
    {
        var mf = GetComponent<MeshFilter>();
        if (mf == null)
        {
            enabled = false;
            throw new System.Exception("No MeshFilter found on gameobject");
        }
        carvedMesh = Mesh.Instantiate(mf.sharedMesh);
        mf.sharedMesh = carvedMesh;

        vertices = new List<Vector3>(carvedMesh.vertexCount);
        carvedMesh.GetVertices(vertices);
        origTris = new List<int>((int)carvedMesh.GetIndexCount(0));
        carvedMesh.GetTriangles(origTris, 0);
        carvedTris = new List<int>(origTris.Count);
        if (GenerateOnStart)
            UpdateCarvedMesh();
    }

    private void Update()
    {
        if (AutoUpdate)
            UpdateCarvedMesh();
    }

    private static bool CheckVertex(Vector3 v1, Vector3 refPos, float aMin, float aMax)
    {
        float sDist = (v1 - refPos).sqrMagnitude;
        return (sDist > aMax || sDist < aMin);
    }

    public void UpdateCarvedMesh()
    {
        if (referenceObject == null)
            throw new System.Exception("referenceObject can not be null. You have to assign it in the inspector");
        var refPos = transform.InverseTransformPoint(referenceObject.position);
        var sqrMin = minDist * minDist;
        var sqrMax = maxDist * maxDist;
        carvedTris.Clear();
        for(int i = 0; i < origTris.Count; i+=3)
        {
            var v1 = vertices[origTris[i]];
            var v2 = vertices[origTris[i+1]];
            var v3 = vertices[origTris[i+2]];
            if (CheckVertex(v1, refPos, sqrMin, sqrMax) ||
                CheckVertex(v2, refPos, sqrMin, sqrMax) ||
                CheckVertex(v3, refPos, sqrMin, sqrMax))
                continue;
            carvedTris.Add(origTris[i]);
            carvedTris.Add(origTris[i+1]);
            carvedTris.Add(origTris[i+2]);
        }
        carvedMesh.SetTriangles(carvedTris, 0);
    }
}

Note since I cached the original triangle list, we can simply go the other way round. Start with an empty triangle list and simply add those triangles that we do not want to discard. The script now has two thresholds, one min and one max distance. min is by default set to 0 and max to infinity. So it would include the whole mesh. So you can set a min and max radius what you want to include / exclude. Since you want to have a max distance and only include triangles which are inside the threshold, leave min and 0 and set max to your desired threshold.

1 Like
5

Just tried it on a default capsule mesh and it works as expected. Though I thought you may want to include a mode like this

    public enum EMode { Touching, Enclosing }
    public EMode mode = EMode.Touching;

and the if statement inside the loop would be replaced by

            if (mode == EMode.Enclosing)
            {
                if (CheckVertex(v1, refPos, sqrMin, sqrMax) ||
                    CheckVertex(v2, refPos, sqrMin, sqrMax) ||
                    CheckVertex(v3, refPos, sqrMin, sqrMax))
                    continue;
            }
            else
            {
                if (CheckVertex(v1, refPos, sqrMin, sqrMax) &&
                    CheckVertex(v2, refPos, sqrMin, sqrMax) &&
                    CheckVertex(v3, refPos, sqrMin, sqrMax))
                    continue;
            }

This way only triangles are included when they are fully enclosed (all 3 vertices are inside the valid volume) or when at least one vertex is “touching”. The logic for removing the triangles is essentially inverted. So if the mode is “Touching” only triangle where all 3 vertices are outside the volume are rejected while the mode “Enclosing” would remove any triangles where at least one of the vertices is outside the volume.

1 Like
6

Wow. That original implementation looks like an IsEven() meme. Where on earth did you get it?

7

The video is in this thread (;
It was the only solution I could find that actually worked easily (school project, so there is time pressure

8

And thanks a bunch again! Will look into implementing this tomorrow.
Sadly the mesh is being generated in real time with Lightship AR, so I assume the Start needs to go into OnCollisionEnter (where I trigger the remesh etc)?

9

Just implemented it and it works amazing!
Solid 20.000-100.000 times faster

10

I want to make a video about cutting out meshes with a git repo attached to it (making it a unity asset would be a bit much probably).
Could I credit you somewhere in the description/readme? If so, what links should I use

1 Like
11

:slight_smile: No need to give credit, though a link to this thread may be helpful for others.

2 Likes