koobas.hobune.stream
Optimizing Mesh Splitting Code
I have written some code that generates a simple quad, then I borrowed code from the UnifyCommunity that subdivides meshes and keeps the vertices shared, then modified it to subdivide a very specific way, and finally I added another static function that splits the mesh into four separate meshes. The function that splits the subdivided quad runs fine up until the quad has more than 1k vertices, then it's lack of optimization begins to really show. Basically I want to know how I can get my split function to run far faster than it does as I will have to be splitting several high vertex count meshes frequently. Code to reproduce what I am doing can be found below.
Mesh Controller Script: Add this code to an empty gameObject and assign a material for the objectMaterial variable. A quad will be generated in play mode and the "u" key can be used to subdivide the quad and the "i" key can be used to split it.
using UnityEngine;
using System.Collections;
public class MeshController : MonoBehaviour {
public Material objectMaterial; //assign a material here
void Start () {
if(transform.parent == null){
gameObject.AddComponent("MeshRenderer");
gameObject.AddComponent("MeshFilter");
gameObject.AddComponent("MeshCollider");
Mesh mesh = new Mesh();
Vector3[] vertices = new Vector3[]
{
new Vector3(1, 0, 1),
new Vector3(1, 0, -1),
new Vector3(-1, 0, 1),
new Vector3(-1, 0, -1),
};
Color[] colors = new Color[]
{
Color.white,
Color.white,
Color.white,
Color.white,
};
Vector2[] uv = new Vector2[]
{
new Vector2(1, 1),
new Vector2(1, 0),
new Vector2(0, 1),
new Vector2(0, 0),
};
int[] triangles = new int[]
{
0, 1, 2,
2, 1, 3,
};
Vector3[] normals = new Vector3[ vertices.Length ];
for( int n = 0; n < normals.Length; n++ )
normals[n] = Vector3.up;
mesh.vertices = vertices;
mesh.normals = normals;
mesh.colors = colors;
mesh.uv = uv;
mesh.triangles = triangles;
GetComponent<MeshFilter>().mesh = mesh;
GetComponent<MeshCollider>().mesh = mesh;
gameObject.renderer.material = objectMaterial;
}
}
void Update () {
if(Input.GetKeyDown("u")){
MeshSubdiv.Subdivide(gameObject.GetComponent<MeshFilter>().mesh);
}
if(Input.GetKeyDown("i")){
if(GetComponent<MeshRenderer>().enabled == true){
Mesh[] splitFaces = new Mesh[4];
splitFaces = MeshSubdiv.Split(gameObject.GetComponent<MeshFilter>().mesh);
for(int i = 0; i < 4; i++){
GameObject newFace = new GameObject();
newFace.transform.position = transform.position;
newFace.transform.rotation = transform.rotation;
newFace.name = "Face" + (i +1);
newFace.transform.parent = gameObject.transform;
newFace.AddComponent("MeshRenderer");
newFace.AddComponent("MeshFilter");
newFace.GetComponent<MeshFilter>().mesh = splitFaces[i];
newFace.AddComponent("MeshController");
newFace.renderer.material = gameObject.renderer.material;
newFace.AddComponent("MeshCollider");
newFace.GetComponent<MeshCollider>().mesh = splitFaces[i];
}
GetComponent<MeshRenderer>().enabled = false;
GetComponent<MeshCollider>().enabled = false;
//gameObject.tag = ("Untagged");
}
}
}
}
MeshSubdiv Script: This script is where all the subdivision and splitting happens. The "Split" function is where things get slow, after some testing I think that using "list.IndexOf" and "list.Contains" are what's making it slow.. A quad will be generated in play mode and the "u" key can be used to subdivide the quad and the "i" key can be used to split it.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public static class MeshSubdiv
{
static List<Vector3> vertices;
static List<Vector3> normals;
static List<Color> colors;
static List<Vector2> uv;
static List<Vector2> uv1;
static List<Vector2> uv2;
static List<int> indices;
static Dictionary<uint,int> newVectices;
static Dictionary<int,int> newVectices2;
static void InitArrays(Mesh mesh) //for subdivision
{
vertices = new List<Vector3>(mesh.vertices);
normals = new List<Vector3>(mesh.normals);
colors = new List<Color>(mesh.colors);
uv = new List<Vector2>(mesh.uv);
uv1 = new List<Vector2>(mesh.uv1);
uv2 = new List<Vector2>(mesh.uv2);
indices = new List<int>();
}
static void InitArrays2(Mesh mesh) //for mesh splitting
{
vertices = new List<Vector3>(mesh.vertices);
normals = new List<Vector3>(mesh.normals);
colors = new List<Color>(mesh.colors);
uv = new List<Vector2>(mesh.uv);
uv1 = new List<Vector2>(mesh.uv1);
uv2 = new List<Vector2>(mesh.uv2);
indices = new List<int>(mesh.triangles);
}
static void CleanUp()
{
vertices = null;
normals = null;
colors = null;
uv = null;
uv1 = null;
uv2 = null;
indices = null;
}
static int GetNewVertex(int i1, int i2)
{
int newIndex = vertices.Count;
uint t1 = ((uint)i1 << 16) | (uint)i2;
uint t2 = ((uint)i2 << 16) | (uint)i1;
if (newVectices.ContainsKey(t2))
return newVectices[t2];
if (newVectices.ContainsKey(t1))
return newVectices[t1];
newVectices.Add(t1,newIndex);
vertices.Add((vertices[i1] + vertices[i2]) * 0.5f);
if (normals.Count>0)
normals.Add((normals[i1] + normals[i2]).normalized);
if (colors.Count>0)
colors.Add((colors[i1] + colors[i2]) * 0.5f);
if (uv.Count>0)
uv.Add((uv[i1] + uv[i2])*0.5f);
if (uv1.Count>0)
uv1.Add((uv1[i1] + uv1[i2])*0.5f);
if (uv2.Count>0)
uv2.Add((uv2[i1] + uv2[i2])*0.5f);
return newIndex;
}
public static void Subdivide(Mesh mesh)
{
newVectices = new Dictionary<uint,int>();
InitArrays(mesh);
int[] triangles = mesh.triangles;
for (int i = 0; i < triangles.Length; i += 6)
{
int i0 = triangles[i + 0];
int i1 = triangles[i + 1];
int i2 = triangles[i + 2];
int i3 = triangles[i + 3];
int i4 = triangles[i + 4];
int i5 = triangles[i + 5];
int m0 = GetNewVertex(i0, i1);
int m1 = GetNewVertex(i1, i2);
int m2 = GetNewVertex(i0, i2);
int m3 = GetNewVertex(i3, i4);
int m4 = GetNewVertex(i4, i5);
int m5 = GetNewVertex(i3, i5);
indices.Add(m0); indices.Add(i1); indices.Add(m1);
indices.Add(m3); indices.Add(i4); indices.Add(m4);
indices.Add(m3); indices.Add(m4); indices.Add(m5);
indices.Add(m5); indices.Add(m4); indices.Add(i5);
indices.Add(i0); indices.Add(m0); indices.Add(m2);
indices.Add(m2); indices.Add(m0); indices.Add(m1);
indices.Add(m2); indices.Add(m1); indices.Add(i2);
indices.Add(i3); indices.Add(m3); indices.Add(m5);
}
mesh.vertices = vertices.ToArray();
if (normals.Count > 0)
mesh.normals = normals.ToArray();
if (colors.Count>0)
mesh.colors = colors.ToArray();
if (uv.Count>0)
mesh.uv = uv.ToArray();
if (uv1.Count>0)
mesh.uv1 = uv1.ToArray();
if (uv2.Count>0)
mesh.uv2 = uv2.ToArray();
mesh.triangles = indices.ToArray();
CleanUp();
}
//Mesh Split Function
public static Mesh[] Split(Mesh mesh)
{
InitArrays2(mesh);
Mesh[] meshList = new Mesh[4];
for(int n = 0; n < 4; n++){
List<Vector3> newVertices = new List<Vector3>();
List<Vector3> newNormals = new List<Vector3>();
List<Color> newColors = new List<Color>();
List<Vector2> newUv = new List<Vector2>();
List<Vector2> newUv1 = new List<Vector2>();
List<Vector2> newUv2 = new List<Vector2>();
List<int> newIndices = new List<int>();
newVectices2 = new Dictionary<int,int>();
for(int i = 0 + (n * (indices.Count/4)); i < ((indices.Count/4) * (n + 1)); i += 6){
for(int x = 0; x < 6; x++){
int curIndex = indices[i+x];
if(!newVectices2.ContainsKey(curIndex)){
newVertices.Add (vertices[indices[i+x]]);
newNormals.Add (normals[indices[i+x]]);
//newColors.Add (colors[indices[i+x]]); no mesh colors
newUv.Add (uv[indices[i+x]]);
//newUv1.Add (uv1[indices[i+x]]); no uv1
//newUv2.Add (uv2[indices[i+x]]); no uv2
newIndices.Add (newVertices.Count-1);
newVectices2.Add (curIndex, newVertices.Count-1);
}else{
newIndices.Add ((int)newVectices2[curIndex]);
}
}
}
Mesh newMesh = new Mesh();
newMesh.vertices = newVertices.ToArray();
if(newNormals.Count > 0)
newMesh.normals = newNormals.ToArray();
if(newColors.Count > 0)
newMesh.colors = newColors.ToArray();
if(newUv.Count > 0)
newMesh.uv = newUv.ToArray();
if(newUv1.Count > 0)
newMesh.uv1 = newUv1.ToArray();
if(newUv2.Count > 0)
newMesh.uv2 = newUv2.ToArray();
newMesh.triangles = newIndices.ToArray();
meshList[n] = newMesh;
}
CleanUp();
return meshList;
}
//Mesh Split Function
public static Mesh DuplicateMesh(Mesh mesh)
{
return (Mesh)UnityEngine.Object.Instantiate(mesh);
}
}
I might also add that the reason I have my splitting code set up the way it is, is so that I don't have duplicated vertices. If I removed the if statement and the else condition it would work fast enough but I would have way more vertices.
You're right that IndexOf and Contains are slow, (they're basically looping through every item and checking if it is the right one- and it might even be faster if you just did that explicitly with a for loop and put a break in it ) but I am not sure how to get rid of them.
I think all you can do is try to come up with a smarter script which already knows the index of what you're getting the IndexOf, (using another Dictionary?) and makes sure the list that already only Contains what it is supposed to contain, before you get to that point.
I tried using an explicit loop and it sped up a little bit, but it was still not adequate. Then I tried using a dictionary as $$anonymous$$iloblargh said and it's a lot faster now. I still don't think it's fast enough though, so I'm wondering if using Vector3's as dictionary keys is slower than using ints. If it is, then how could I generate a unique id for each Vector3 that could be reproduced whenever that exact same Vector3 has to be processed through the unique id generator?
Edit:
Wait, how could I just produce an integer from a Vector3 by appending the values on the three axes together? For example: x = 1, y = 2, z =3, int = 123.
Edit 2:
The above won't work simply because of negative values. I'll try it with strings ins$$anonymous$$d of floats (ints wouldn't work as well).
Edit 3
I'm not trying to spam or anything but using integers for the dictionary keys isn't noticeably faster, I've updated my code above and it uses the vertex index in the original mesh as the "unique id." At this point I've exhausted all of my ideas. Help?
Okay this is a continuation of this question, how could I adapt my code above, the mesh splitting function, to keep the indices properly ordered after splitting. By 'properly' I mean that if a quad on subdivision level 4 is split (with the resultant ones on level 3) then the indices will differ from one that was subdivided to level 3. Ins$$anonymous$$d I want the indices to be the same. But I still want it to have shared vertices.
There are a couple of things you can do to improve your performance.
1) You are creating new lists with InitArrays.
You should replace this with List.Clear(). This prevents further memory allocations every time you initialize.
Also you should not destroy then on cleanup if you want to reuse them.
2) You can replace the ContainsKey with TryGetValue. Its a slightly faster, but can have huge impact on performance depending on the number of hit/misses, and number of calls.
More info here: http://stackoverflow.com/questions/9382681/what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem
3) newFace.name = "Face" + (i +1);
Probably unnoticeable, but since every tick counts... contatenating strings takes some toll on memory allocation.
(that statement is actually creating 2 extra strings)
You can replace with: String.Format("Face{0}", (i+1))
4) for(int i = 0 + (n (indices.Count/4)); i < ((indices.Count/4) (n + 1)); i += 6)
You should remove the calculations from the loop:
int fromVal = (n (indices.Count/4));
int toVal = ((indices.Count/4) (n + 1));
for(int i = fromVal; i < toVal; i += 6)...
5) On your Split function, you have: int curIndex = indices[i+x];
but you are not using it in every indices[i+x]
EDIT: just noticed that every time you: (something[i1] + something[i2]) * 0.5f can be replaced by the much faster: (something[i1] + something[i2]) >> 1
These all add up on your performance.
I hope this helps!
