Unity Mesh Generation from a Quadtree

Questions & Answers
1

Hi,

I am trying to implement a procedurally generated (near-infinite) terrain on a Quad-Sphere in Unity.
Therefor I already managed to create Plane meshes, map them to a sphere and now I’m trying to implement some LOD via a quadtree structure. I already coded a (very basic) quadtree implementation but now I can’t wrap my head around how to (recursively) generate a mesh from the leaf nodes (children) and how to calculate triangle and vertex indices recursively.

I’m sure it’s not a big deal, but I’m quite new to this and can’t really wrap my head around this mesh generation stuff.

It would be so nice, if someone can give me kind of a clue, at least where I can find answers on how to generate meshes from quadtrees. Thank you in advance.

My quadtree Implementation looks as follows:

QuadTreeManager.cs

[ExecuteInEditMode]
public class QuadTreeManager : MonoBehaviour
{
	public QuadTree quadTree;
	public Transform observer;
	public Vector3 observerPositionLastFrame;
	// This is the edge-length for one "side" of one subdivision quad
	public int leafGridSize = 256;
	public int maxTreeDepth = 8;
	private List<Vector3> meshVertices = new List<Vector3>();
	public void Init()
	{
		InitializeQuadTree();
	}
	private void InitializeQuadTree()
	{
		quadTree = new QuadTree(Vector3.zero, leafGridSize, 0, maxTreeDepth);
	}
	private void Update()
	{
		if (null != observer && null != quadTree)
		{
			quadTree.UpdateBasedOnProximity(observer);

			if (quadTree.isDirty())
			{
				meshVertices = quadTree.GetMeshVertices();
				// Then the geometry needs an update
			}
			else
			{
				// Just for debug: Foreach points in List draw a line to see if coordinates are correct 
				foreach (var coordinate in meshVertices)
				{
					Debug.DrawLine(coordinate, coordinate + Vector3.up);
				}
			}
		}
		observerPositionLastFrame = observer.position;
	}
	private void OnDrawGizmos()
	{
		if (null == quadTree)
		{
			Init();
			return;
		}
		quadTree.OnDrawGizmo();
	}
}

QuadTree.cs

public class QuadTree
{
	public QuadTree[] children;
	public QuadTree parent = null;
	public float leafGridSize;
	public Bounds bounds;
	public int myDepth;
	public int maxDepth;
	public Vector3 coords;
	public bool verticesChanged = true;
	private Color myGizmoColor = Color.white;
	public bool isSubdivided = false;
	public QuadTree(Vector3 coords, float leafGridSize, int myDepth = 0, int maxDepth = 1)
	{
		this.leafGridSize = leafGridSize;
		this.myDepth = myDepth;
		this.coords = coords;
		this.maxDepth = maxDepth;
		bounds = new Bounds(coords, Vector3.one * leafGridSize * 2f);
	}
	public void UpdateBasedOnProximity(Transform observer)
	{
		var interactionObject = observer.GetComponent<QuadTreeInteractionObject>();
		var isClose = false;

		if (null != interactionObject)
		{
			if (bounds.Intersects(interactionObject.bounds))
				isClose = true;
		}
		else
		{
			if (bounds.Contains(observer.position))
				isClose = true;
		}
		if (isClose)
		{
			Subdivide();
		}
		else
		{
			RecycleChildren();
			return;
		}
		if (isClose && isSubdivided)
		{
			for (var i = 0; i < children.Length; i++)
				children*.UpdateBasedOnProximity(observer);*

  •  }*

  • }*

  • public List GetMeshVertices()*

  • {*

  •  List<Vector3> vertices = new List<Vector3>();*

  •  vertices.AddRange(GetMyVertices());*

  •  if (null != children)*

  •  for (var i = 0; i < children.Length; i++)*

  •  {*

  •  	{*

_ var childVertices = children*.GetMeshVertices();_
_ vertices.AddRange(childVertices);_
_ }_
_ }_
_ verticesChanged = false;_
_ return vertices;_
_ }*_

* List GetMyVertices()*
* {*
* var vertices = new List*
* {*
* // Top Left*
* new Vector3(coords.x - leafGridSize, 0, coords.z - leafGridSize),*
* // Top Right*
* new Vector3(coords.x + leafGridSize, 0, coords.z - leafGridSize),*
* // Bottom Left*
* new Vector3(coords.x - leafGridSize, 0, coords.z + leafGridSize),*
* // Bottom Right*
* new Vector3(coords.x + leafGridSize, 0, coords.z + leafGridSize)*
* };*
* return vertices;*
* }*

* public bool isDirty()*
* {*
* var childGeometryChanged = verticesChanged;*
* if (children != null)*
* {*
* for (var i = 0; i < children.Length; i++)*
_ childGeometryChanged |= children*.isDirty();
 }
 return childGeometryChanged;
 }*_

* private void RecycleChildren()*
* {*
* if (children != null)*
* {*
* for (var i = 0; i < children.Length; i++)*
* {*
_ children*.RecycleChildren();
verticesChanged = true;
}
}
children = null;
isSubdivided = false;
}*_

* public void Subdivide ()*
* {*
* if (!isSubdivided)*
* {*
* if (myDepth <= maxDepth)*
* {*
* children = new QuadTree[4];*

* // NW:*
* children[0] = new QuadTree(new Vector3(coords.x - leafGridSize / 2f, 0, coords.z + leafGridSize / 2f), leafGridSize / 2f, myDepth + 1,*
* maxDepth);*

* // NE:*
* children[1] = new QuadTree(new Vector3(coords.x + leafGridSize / 2f, 0, coords.z + leafGridSize / 2f), leafGridSize / 2f, myDepth + 1,*
* maxDepth);*

* // SW:*
* children[2] = new QuadTree(new Vector3(coords.x + leafGridSize / 2f, 0, coords.z - leafGridSize / 2f), leafGridSize / 2f, myDepth + 1,*
* maxDepth);*

* // SE:*
* children[3] = new QuadTree(new Vector3(coords.x - leafGridSize / 2f, 0, coords.z - leafGridSize / 2f), leafGridSize / 2f, myDepth + 1,*
* maxDepth);*

* for (var i = 0; i < 4; i++)*
_ children*.parent = this;*_

* verticesChanged = true;*
* isSubdivided = true;*
* }*
* }*
* }*
* public void OnDrawGizmo()*
* {*
* if (null != children)*
* {*
* foreach( QuadTree child in children )*
* child?.OnDrawGizmo();*
* }*
* var b = bounds.size;*
* b.y = .5f;*
* Gizmos.color = myGizmoColor;*
* Gizmos.DrawWireCube(coords, b);*
* }*
}

2

You make a recursive method that receives a vertex and triangle list. If the node is a leaf, it adds its geometry to the lists and returns. If it’s an inner node, it may or may not add geometry to the lists depending on your requirements but more importantly, it invokes the same method with the same parameters on its children so that they can add their geometry. It’s not fundamentally different from your OnDrawGizmo method.

A node can simply write its own vertices unchanged, without caring about the rest of the tree. However, when a node writes indices (triangles), it must respect the offset of its vertices in the list. This isn’t hard to do, you just store the number of vertices before you add your own and add that offset to each index.

So basically, the method would look somewhat like this:

void GenerateGeometry(List<Vector3> vertices, List<int> triangles) {
	var indexOffset = vertices.Count;

	if (children == null) {
		// Add leaf geometry to the lists
		// To write a position, simply do vertices.Add(position)
		// To write an index, do triangles.Add(indexOffset + index)
	} else {
		// Add inner node geometry to the lists
		// (optional, inner nodes may not have geometry)
		// To write a position, simply do vertices.Add(position)
		// To write an index, do triangles.Add(indexOffset + index)

		// Invoke recursively
		foreach (var child in children) {
			child.GenerateGeometry(vertices, triangles);
		}
	}
}