Dynamic Mesh Combining in Unity with C#

Add and remove trees from the combined meshes

In this part of the tutorial you will learn how to add and remove meshes from combined meshes.

Part 1. How do you modify a combined mesh?

Adding and removing trees is easy if we are not dealing with combined meshes. It is not difficult to remove a mesh from a combined mesh and it is not difficult to add a mesh to a combined mesh. But there's a Swedish expression saying that you "need to have your tongue at the correct position in your mouth," meaning it's easy to get lost among the arrays and vertices we are going to use if you are not focusing.

Before we begin with the adding and removing of trees we have to learn how to identify a tree mesh in a combined mesh (I'm saying "tree," but I'm meaning the tree's wood mesh and leaf mesh). We can easily identify in which mesh a tree has been combined, because we have saved that list position. But how do we identify the tree mesh in the combined mesh? The answer is that we have to search through all vertices of the combined mesh and see when a vertice matches a vertice in a single tree. This will only work if no trees have the same position, which we here assume they don't have.

So create a new script called "ModifyMesh" and add the following:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class ModifyMesh
{
    static float tolerance = 0.0001f;
  
    //Removes a mesh from another mesh that contains the same mesh (at the same position) 
    //but also other meshes at other positions
    //Can add the parameter moveVec if we know we have moved the mesh we want to remove a certain distance
    public static void RemoveVerticesFromMesh(Transform currentObject, Transform objectToRemove, Vector3 moveVec = default(Vector3))
    {
        MeshFilter currentMeshFilter = currentObject.GetComponent<MeshFilter>();
        
        //The vertices and triangles belonging to the mesh we are going to modify
        //From array to list so we can modify them - Requires "using System.Linq;" 
        List<Vector3> currentVertices = currentMeshFilter.mesh.vertices.ToList<Vector3>();
        
        List<int> currentTriangles = currentMeshFilter.mesh.triangles.ToList<int>();

        //The vertices we are going to remove from the mesh
        Mesh objectToRemoveMesh = objectToRemove.GetComponent<MeshFilter>().mesh;

        Vector3[] verticesToRemove = objectToRemoveMesh.vertices;

        int nrOfVerticesToRemove = verticesToRemove.Length;


        //First find the position where we should begin to remove vertices
        int minVerticePos = 0;

        //From local to global
        Vector3 firstVertPosToRemove = objectToRemove.transform.TransformPoint(verticesToRemove[0]);

        //From global to local of the combined mesh or we have to do do it each time in the loop, which is slower
        firstVertPosToRemove = currentObject.InverseTransformPoint(firstVertPosToRemove) + moveVec;

        for (int i = 0; i < currentVertices.Count; i++)
        {
            //We now know where the mesh we want to remove begins in the combined mesh
            //if (currentVertices[i] == firstVertPosToRemove)
            //The above is sometimes not working because of rounding errors, so use a tolerance
            if ((currentVertices[i] - firstVertPosToRemove).sqrMagnitude < tolerance)
            {
                minVerticePos = i;
                break;
            }
        }

        //Remove the vertices that we dont need
        currentVertices.RemoveRange(minVerticePos, nrOfVerticesToRemove);


        //Change the number of the triangles by first finding the position where 
        //we should begin to remove triangles, while at the same time shifting
        //the triangles that comes after the ones we are removing, so they point
        //at the correct vertices
        int minTrianglePos = 0;

        bool hasFoundStart = false;

        int firstTrianglePos = objectToRemoveMesh.triangles[0] + minVerticePos;

        int upperLimit = minVerticePos + nrOfVerticesToRemove;

        for (int i = 0; i < currentTriangles.Count; i++)
        {
            int currentTrianglePos = currentTriangles[i];

            if (currentTrianglePos == firstTrianglePos && !hasFoundStart)
            {
                hasFoundStart = true;
                minTrianglePos = i;
            }

            //Change which vertices the triangles are being built from
            //We only need to shift the triangles that come after the triangles we remove
            if (currentTrianglePos >= upperLimit)
            {
                currentTriangles[i] = currentTrianglePos - nrOfVerticesToRemove;
            }
        }
        
        //Remove the triangles we dont need
        currentTriangles.RemoveRange(minTrianglePos, objectToRemoveMesh.triangles.Length);


        //Now we can create the new mesh
        //Important to clear or create a new mesh it will complain about the triangles
        //being the wrong size even though they arent
        currentMeshFilter.mesh.Clear();

        currentMeshFilter.mesh.vertices = currentVertices.ToArray();
        currentMeshFilter.mesh.triangles = currentTriangles.ToArray();
    }
}

When we are searching through the vertices that belongs to the combined mesh and trying to match coordinates with the mesh that belongs to the tree, the problem is that because of rounding errors, these coordinates will not always match 100 percent. So instead we have to use a tolerance, which I've assumed to be 0.0001. That means that if the coordinate in the combined mesh matches the coordinate in the tree mesh, then we assume we have found the tree in the combined mesh.

Next step is removing the vertices that belongs to the tree from the combined mesh. That's easy because we now know where the tree's vertices begins in the long list of vertices and how many vertices a single tree has. But a mesh also consists of a long list of triangles that are building up the final mesh, so we have to modify that list as well. But that's easy because we know the position of the first vertice we are going to remove, and then we have to modify all triangles that come after the mesh we have removed so they point at the vertices that are still there. Then we just add the new vertices and triangles to the combined mesh.

The problem is that the above is slow. If we are going to remove many trees at the same time, we have to cheat by hiding the trees below the ground. So add the following method to "ModifyMesh":

//Moves a mesh away from another mesh that contains the same mesh (at the same position) 
//but also other meshes at other positions
public static void MoveVerticesOutOfTheWay(Transform currentObject, Transform objectToRemove, Vector3 moveVec)
{
	MeshFilter currentMeshFilter = currentObject.GetComponent<MeshFilter>();

	//The vertices belonging to the mesh we are going to modify
	Vector3[] currentVertices = currentMeshFilter.mesh.vertices;

	//The vertices we are going to move
	Vector3[] verticesToRemove = objectToRemove.GetComponent<MeshFilter>().mesh.vertices;

	//Find the position of the first vertice we are going to remove, but in local pos of the mesh
	//we are going to remove it from
	//From local to global
	Vector3 firstVertPosToRemove = objectToRemove.transform.TransformPoint(verticesToRemove[0]);
	//From global to local of the combined mesh
	firstVertPosToRemove = currentObject.InverseTransformPoint(firstVertPosToRemove);
   
	//Find the first vertice in the combined mesh
	for (int i = 0; i < currentVertices.Length; i++)
	{
		//We now know where the mesh we want to move begins
		//if (currentVertices[i] == firstVertPosToRemove)
		//The above is sometimes not working because of rounding errors, so use a tolerance
		if ((currentVertices[i] - firstVertPosToRemove).sqrMagnitude < tolerance)
		{
			//Move the vertices
			for (int j = 0; j < verticesToRemove.Length; j++)
			{
				currentVertices[i + j] += moveVec;
			}
			
			break;
		}
	}

	//Add the modified vertices to the combined mesh
	currentMeshFilter.mesh.vertices = currentVertices;
}

The above method is similar to the method that removes a mesh from a combined mesh. The difference is that we are just moodifying the vertices by moving them with a certain distance determined by a vector. It will make the code much faster.

Part 2. Remove trees

With the above in mind, you may understand that to be able to remove a tree, we first have to hide all trees we want to remove in one frame and then remove the hidden trees over several frames. So create a script called "TutorialAddRemoveTrees" and add the following (it will include some code we need to add trees, but it's less messy to add everything at the same time):

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

public class TutorialAddRemoveTrees : MonoBehaviour
{
    //Used in the coroutine to set if we should add new trees
    bool shouldAddTrees = false;
    
    //Slow to add trees to combined meshes, so spread out over several frames
    List<GameObject>waitingListAddTree = new List<GameObject>();
    //If we want to remove the trees completely, and not just hide them
    List<GameObject> waitingListRemoveTree = new List<GameObject>();

    //How far away should we move a tree that has been removed?
    Vector3 moveVec = new Vector3(0f, -40f, 0f);

    void Start() 
    {
        //Add trees when pressing mouse button
        StartCoroutine("AddNewTrees");
        //Add recently instantiated trees to a combined mesh
        //or remove trees from combined mesh
        StartCoroutine("AddRemoveTreesToFromCombinedMesh");
    }
		
    void Update() 
    {
        //Remove trees with right mouse button
        if (Input.GetMouseButton(1))
        {
            RemoveTrees();
        }
        //Add trees with left mouse button
        if (Input.GetMouseButton(0))
        {
            shouldAddTrees = true;
        }
    }

    //Add/remove trees in the waiting list to/from a combined mesh
    IEnumerator AddRemoveTreesToFromCombinedMesh()
    {
        while (true)
        {
            //Add tree to combined mesh
            if (waitingListAddTree.Count > 0)
            {
                AddTreeToCombinedMesh(waitingListAddTree[0]);

                waitingListAddTree.RemoveAt(0);

                yield return new WaitForSeconds(0.1f);
            }


            //Remove tree from combined mesh
            if (waitingListRemoveTree.Count > 0)
            {
                RemoveTreeCompletely(waitingListRemoveTree[0]);

                yield return new WaitForSeconds(0.1f);
            }

            yield return null;    
        }
    }
}

We are later on going to add trees with a coroutine, and the idea will then be similar to when we remove trees, but more of that later. What you will see is that we have waiting lists we are going to fill with trees that we are going to remove (and are now hidden) and trees we are going to combine into combined meshes, but have now just been instantiated, which is faster.

To be able to remove trees you will need the following methods:

//Remove trees within the radius of the circle
void RemoveTrees()
{
	//The current cicle radius
	float radius = TutorialMouseMarker.current.projector.orthographicSize;

	//All trees we have in our forest
	List<GameObject> allTrees = TutorialCreateForest.current.allTrees;
	
	//Position of the mouse
	Vector3 mousePos = TutorialMouseMarker.current.circleObj.transform.position;
	//Make sure we operate in 2d space
	mousePos.y = 0f;
	
	//Loop through all trees
	for (int i = 0; i < allTrees.Count; i++)
	{
		GameObject currentTree = allTrees[i];

		Vector3 treePos = currentTree.transform.position;
		//Make sure we operate in 2d space
		treePos.y = 0f;

		//The distance Sqr between the tree and the center of the mouse
		//Remember that sqr is faster than sqrt!
		float distSqr = (treePos - mousePos).sqrMagnitude;

		//If the tree is within the circle radius
		if(distSqr < radius * radius)
		{
			//Remove the tree from our list with trees so we are not selecting it again
			TutorialCreateForest.current.allTrees.Remove(currentTree);
			//Also remove the tree from the waiting list if it is waiting to be added to a combined mesh
			waitingListAddTree.Remove(currentTree);
			//But add it to the list with trees we want to remove completely
			waitingListRemoveTree.Add(currentTree);
			//Move the tree out of the way
			MoveTree(currentTree);
		}
	}
}

//Moves one tree so we cant see it anymore
void MoveTree(GameObject currentTree)
{
	//First get which list this tree is in
	int listPos = currentTree.GetComponent<TreeData>().listPos;

	//Does this tree belong to a list?
	if (listPos == -1)
	{
		//Just deactivate the tree if it doesnt belong to a list
		currentTree.SetActive(false);
	}
	//Tree belongs to a list, so we have to move the vertices in the combined mesh
	else
	{
		//Get the combined object in which this tree is a part of
		GameObject combinedObjWood = TutorialCreateForest.current.combinedWoodList[listPos];
		GameObject combinedObjLeaf = TutorialCreateForest.current.combinedLeafList[listPos];

		//Find the wood and leaf meshes inside of this tree
		Transform woodObj = null;
		Transform leafObj = null;

		GetWoodandLeaf(currentTree, out woodObj, out leafObj);

		//Move it
		ModifyMesh.MoveVerticesOutOfTheWay(combinedObjWood.transform, woodObj, moveVec);
		ModifyMesh.MoveVerticesOutOfTheWay(combinedObjLeaf.transform, leafObj, moveVec);
	}
}

//Removes one tree completely from the game
void RemoveTreeCompletely(GameObject currentTree)
{
	//First get which list this tree is in
	int listPos = currentTree.GetComponent<TreeData>().listPos;

	//If the tree belongs to a list, remove it from the combined mesh
	if (listPos != -1)
	{
		//Get the combined object in which this tree is a part of
		GameObject combinedObjWood = TutorialCreateForest.current.combinedWoodList[listPos];
		GameObject combinedObjLeaf = TutorialCreateForest.current.combinedLeafList[listPos];

		//Find the wood and leaf meshes inside of this tree
		Transform woodObj = null;
		Transform leafObj = null;

		GetWoodandLeaf(currentTree, out woodObj, out leafObj);

		//Remove the wood and leaf from the combined mesh
		ModifyMesh.RemoveVerticesFromMesh(combinedObjWood.transform, woodObj, moveVec);
		ModifyMesh.RemoveVerticesFromMesh(combinedObjLeaf.transform, leafObj, moveVec);
		//Also need to recalculate normals
		combinedObjWood.GetComponent<MeshFilter>().mesh.RecalculateNormals();
		combinedObjLeaf.GetComponent<MeshFilter>().mesh.RecalculateNormals();
	}

	//Remove the tree from the waiting list
	waitingListRemoveTree.Remove(currentTree);
	//Destroy the tree
	Destroy(currentTree);
}

So when we hold the right mouse button, we search through the list of all single trees we have in our forest and check if they are within the radius of our Tree Brush tool. If so, we remove the tree from the list of all trees, we hide the tree below the ground, and then we add the tree to the waiting list so we can remove it completely later on.

We will also need this help method that will help us to get the child leaf and child wood transform from each individual tree:

//Finds the tree's leaf and wood children
void GetWoodandLeaf(GameObject currentTree, out Transform woodObj, out Transform leafObj)
{
	woodObj = null;
	leafObj = null;

	//Find the wood and leaf meshes inside of this tree
	MeshFilter[] meshFilters = currentTree.GetComponentsInChildren<MeshFilter>(true);

	for (int j = 0; j < meshFilters.Length; j++)
	{
		MeshFilter meshFilter = meshFilters[j];

		//Is it wood or leaf?
		//Modify the material name, because Unity adds (Instance) to the end of the name
		string materialName = meshFilter.GetComponent<MeshRenderer>().material.name.Replace(" (Instance)", "");

		if (materialName == "Leaf")
		{
			leafObj = meshFilter.transform;
		}
		else if (materialName == "Wood")
		{
			woodObj = meshFilter.transform;
		}
	}
}

Part 3. Add trees

Adding trees is similar to removing trees. As said before, we are going to cheat by just instantiating the trees, add them to a waiting list, and then add them to a combined mesh over several frames. So add the following to the script "TutorialAddRemoveTrees":

//Coroutine used to determine how often we should add a new tree
//when we press left mouse button
IEnumerator AddNewTrees()
{
	while (true)
	{
		if (shouldAddTrees)
		{
			AddOneTree();
		}

		shouldAddTrees = false;

		yield return new WaitForSeconds(0.1f);
	}
}

//Add one tree randomly within the circle and just instantiate it
void AddOneTree()
{
	//Find random coordinate within the circle
	//http://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly
	float a = Random.Range(0f, 1f);
	float b = Random.Range(0f, 1f);

	if (b < a)
	{
		float a_temp = a;
		a = b;
		b = a_temp;
	}

	float R = TutorialMouseMarker.current.projector.orthographicSize;

	float xCoord = b * R * Mathf.Cos(2 * Mathf.PI * a / b);
	float zCoord = b * R * Mathf.Sin(2 * Mathf.PI * a / b);

	//Add a tree at the position of the mouse
	Vector3 mousePos = TutorialMouseMarker.current.circleObj.transform.position;
	mousePos.y = 0f;
	Vector3 treePos = new Vector3(xCoord, 0f, zCoord) + mousePos;

	//The tree we are going to add
	GameObject treeObj = TutorialCreateForest.current.treeObj;

	//Make sure the tree is active
	treeObj.SetActive(true);

	GameObject newTree = Instantiate(treeObj, treePos, Quaternion.identity) as GameObject;
	
	newTree.transform.parent = TutorialCreateForest.current.individualTreeParent;

	//Add the tree to the list of all trees so we can remove it
	TutorialCreateForest.current.allTrees.Add(newTree);

	//Now we need to add this tree to a combined mesh, but this is slow, 
	//so better spreading it out over several frames, so add it to a waiting list
	waitingListAddTree.Add(newTree);
}

//Adds one tree to a combined mesh
void AddTreeToCombinedMesh(GameObject newTree)
{
	//Find the wood and leaf meshes inside of this tree
	Transform woodObj = null;
	Transform leafObj = null;

	GetWoodandLeaf(newTree, out woodObj, out leafObj);

	//How many vertices has the leaf?
	int leafVertices = leafObj.GetComponent<MeshFilter>().mesh.vertexCount;

	//Find a list with vertices left, leafs are critical because have more vertices
	List<GameObject> combinedLeafList = TutorialCreateForest.current.combinedLeafList;
	List<GameObject> combinedWoodList = TutorialCreateForest.current.combinedWoodList;

	bool hasFoundCombinedMesh = false;

	//Search through all lists and see if we have a list that has room for more vertices
	for (int i = 0; i < combinedLeafList.Count; i++)
	{
		MeshFilter combinedMeshFilter = combinedLeafList[i].GetComponent<MeshFilter>();

		int vertices = combinedMeshFilter.mesh.vertexCount;

		//This mesh has room for more vertices
		if (vertices + leafVertices < TutorialCreateForest.current.vertexLimit)
		{
			hasFoundCombinedMesh = true;

			//Add the current wood and leaf to the combined mesh that has room for them
			AddMeshToCombinedMesh(leafObj, combinedLeafList[i]);
			AddMeshToCombinedMesh(woodObj, combinedWoodList[i]);

			//Add the list number to the tree object
			newTree.GetComponent<TreeData>().listPos = i;

			break;
		}
	}

	//We need to create a new combined mesh because all meshes are full
	if (!hasFoundCombinedMesh)
	{
		//Wood
		GameObject newMeshHolderWood = Instantiate(TutorialCreateForest.current.combinedWoodObj) as GameObject;

		newMeshHolderWood.transform.parent = TutorialCreateForest.current.combinedMeshParent;

		combinedWoodList.Add(newMeshHolderWood);

		//Leaf
		GameObject newMeshHolderLeaf = Instantiate(TutorialCreateForest.current.combinedLeafObj) as GameObject;

		newMeshHolderLeaf.transform.parent = TutorialCreateForest.current.combinedMeshParent;

		combinedLeafList.Add(newMeshHolderLeaf);


		//Add the current wood and leaf to the new combined meshes we just created
		AddMeshToCombinedMesh(leafObj, newMeshHolderLeaf);
		AddMeshToCombinedMesh(woodObj, newMeshHolderWood);

		//Add the list number to the tree object
		newTree.GetComponent<TreeData>().listPos = combinedLeafList.Count - 1;
	}

	newTree.SetActive(false);
}

//Adds one mesh to a combined mesh 
void AddMeshToCombinedMesh(Transform objToAdd, GameObject combinedMesh)
{
	//Create a new array that will hold the mesh data
	CombineInstance[] combined = new CombineInstance[2];

	combined[0].mesh = objToAdd.GetComponent<MeshFilter>().mesh;
	combined[0].transform = objToAdd.transform.localToWorldMatrix;

	combined[1].mesh = combinedMesh.GetComponent<MeshFilter>().mesh;
	combined[1].transform = combinedMesh.transform.localToWorldMatrix;

	//Create the new mesh
	Mesh newMesh = new Mesh();
	newMesh.CombineMeshes(combined);

	//Add it to the combined mesh holder
	combinedMesh.GetComponent<MeshFilter>().mesh = newMesh;
}

In a similar way as when we added the trees from the randomly generated forest, we are searching through the list of all combined meshes and see if the tree we want to add fit into that mesh (rememeber that our vertice limit is 30000). If not any combined mesh has any room for it, we have to create a new combined mesh and add the tree to it.

That's it! You have now created a fantastic Tree Brush tool like in Cities: Skylines! If you press Play you should be able to add and remove trees and you can also notice that the number of batches is constantly around 200. You will notice that the number of batches increase when we add more trees, but decreases over time as the new trees are being combined into a mesh.