How to parse a quadtree efficiently? IEnumerator function? (Procedural Planet)

Hi, I hope you can help me with my hobby implementation of creating a procedural planet.
I am using a cubesphere stored in 6 quadtrees [=my QuadtreeTerrain class].

UPDATE: I have changed the description as I followed dns hint to first implement a working approach and then check how to optimize and timeslice it.

So the creation of the cubesphere works, including splitting and merging of the planes in the quadtree. Question is how to to parse the quadtrees regularly and efficiantly. Right now I parse all six quadtree’s in the Update() function of a class attached to the gameobject (the planet’s gameobject).

The implementation is recursive, the function calls itself to traverse down the tree to check the child nodes. While this approach works suprisingly well moving the camera closely over terrain, going down in the quadtrees even till level ~18 of splittings for planet detail on a simple quadsphere, FPS gets significantly down when adding Simplex Noise for Vertice positioning to create the landscape. Following is the code where I check the tree in the update function.
My question is, what would be a typical way in Unity to optimize this (I guess since quadtrees are typical and often used, there is a “good and common” approach for heavy operations with quadtrees.
Somehow use IEnumerator functions? Or use a separate thread for vertice calulcations so that rendering is only done when the vertices are pre-calulcated (right now the vertices are calculated always and directly when a split or merge is performed?

	// Update is called once per frame
	void Update () {
		if (this.SpaceObjectProceduralPlanet.GetGameObject().layer == LayerMask.NameToLayer("LocalSpace"))
			if (SpaceObjectProceduralPlanet.worldSpaceRadius * 100 > this.cameraDistanceToObjectCenter) {
				// Get current position of gameobject
				this.SpaceObjectOriginalPosition = this.SpaceObjectProceduralPlanet.GetGameObject ().transform.position;
				// Move gameobject to zero (we do the updates here)
				this.SpaceObjectProceduralPlanet.GetGameObject ().transform.position = new Vector3 (0, 0, 0);
				// Parse Quadtrees
				ParseQuadtreeTerrain (QuadtreeTerrain1);
				ParseQuadtreeTerrain (QuadtreeTerrain2);
				ParseQuadtreeTerrain (QuadtreeTerrain3);
				ParseQuadtreeTerrain (QuadtreeTerrain4);
				ParseQuadtreeTerrain (QuadtreeTerrain5);
				ParseQuadtreeTerrain (QuadtreeTerrain6);
				// Move gameobject back to the original position
				this.SpaceObjectProceduralPlanet.GetGameObject ().transform.position = this.SpaceObjectOriginalPosition;
			}
	}

protected void ParseQuadtreeTerrain(QuadtreeTerrain quadtreeTerrain) {
		// Temporary offsetposition (we need this to check the (theoretical) camera position against the position of the Quadtree, which is based on (0,0,0) location).
		Vector3 temporaryCameraOffsetPosition = cameraLocalSpace.transform.position - this.SpaceObjectOriginalPosition;

		float outerVector1DistanceCamera = Vector3.Distance (temporaryCameraOffsetPosition, quadtreeTerrain.worldSpaceOuterVector1);
		float outerVector2DistanceCamera = Vector3.Distance (temporaryCameraOffsetPosition, quadtreeTerrain.worldSpaceOuterVector2);
		float outerVector3DistanceCamera = Vector3.Distance (temporaryCameraOffsetPosition, quadtreeTerrain.worldSpaceOuterVector3);
		float outerVector4DistanceCamera = Vector3.Distance (temporaryCameraOffsetPosition, quadtreeTerrain.worldSpaceOuterVector4);
		float closestVectorDistanceCamera = outerVector1DistanceCamera;
		if (outerVector1DistanceCamera < closestVectorDistanceCamera) closestVectorDistanceCamera = outerVector1DistanceCamera;
		if (outerVector2DistanceCamera < closestVectorDistanceCamera) closestVectorDistanceCamera = outerVector2DistanceCamera;
		if (outerVector3DistanceCamera < closestVectorDistanceCamera) closestVectorDistanceCamera = outerVector3DistanceCamera;
		if (outerVector4DistanceCamera < closestVectorDistanceCamera) closestVectorDistanceCamera = outerVector4DistanceCamera;

		if (quadtreeTerrain.nodeLevel < this.maximumNodeLevel) {
			// Check if camera is closer to closest edge of quadtree then its diameter. If yes, and quadtree is a leave, split. If not, traverse down.
			if (closestVectorDistanceCamera/2 < quadtreeTerrain.worldSpaceDiameter) {
				if (quadtreeTerrain.isLeaf == true) {
					quadtreeTerrain.Split();
					// Recurse down the tree
					if (quadtreeTerrain.childNode1 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode1);
					if (quadtreeTerrain.childNode2 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode2);
					if (quadtreeTerrain.childNode3 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode3);
					if (quadtreeTerrain.childNode4 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode4);
				} else if (quadtreeTerrain.isLeaf == false) {
					// Recurse down the tree
					if (quadtreeTerrain.childNode1 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode1);
					if (quadtreeTerrain.childNode2 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode2);
					if (quadtreeTerrain.childNode3 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode3);
					if (quadtreeTerrain.childNode4 != null) ParseQuadtreeTerrain (quadtreeTerrain.childNode4);
				}
			} else if (closestVectorDistanceCamera/2 > quadtreeTerrain.worldSpaceDiameter && quadtreeTerrain.isLeaf == false) {
				if (quadtreeTerrain.isLeaf == false) {
					quadtreeTerrain.Merge ();
				} else if (quadtreeTerrain.isLeaf == true) {
					quadtreeTerrain.parentNode.Merge();
				}
			}
		}

Hi, I think you are in the right path, breaking the problems into smaller one and solving them one at a time :slight_smile:

Now, optimizations will depend on your target platform. I guess it’s for desktop computer. You sure have multiple core and it would be nice to use them (The optimal approach may be to use the GPU but it’s another domain :).

IEnumerator, coroutines and time slicing may work, multithread solution might not be so much more complicated to implement. I’d use the ThreadPool class + some double buffering techniques: On the main thread, I would just compute the needed level of detail and allocate structs. Then, some threads would check if there is work to be done: fill those structs with the right level of detail computations, using any algorithm you want, recursive would be ok. When the thread job is done, the main thread would just have to assign those computations results to a mesh and pass it to Unity.

The thing to do here is to use 2 set of buffers. While the main thread would use a set of buffers/structures, the threads would use the other one (and just swap them when a set of jobs is done). Furthermore, each thread would have it’s own structs/memory to write to. With this concept, your threads will not “race” to write to the same memory and the synchronization between the main/Unity thread and the others should not be very complicated.

With the kind of structure you use, you may assign each quad tree to a thread, or some sub-tree to each thread (only if each thread would then write to a different part of the memory, but I think that’s how quad tree works)

Well, I’m not sure I understand exactly how your code works, I hope it helps.

Also, you may want to start a thread in the forums as “Answers” is used for questions more specific to Unity itself.