Spherical Worlds in Unity Tests - subdivision of sphere into tetrahedra, cube and adjusted cube

GlobeVisualizer.cs

/*
#License: 
MIT. Copyrigh 2022 Victor "NegInfinity" Eremin.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

#What is it?:
It is a quick test made while investigating possibility
of making sperical worlds in unity.

#How do I use it?:
Add an empty into the scene, add GlobeVisualizer to it.
You'll see a wireframe, if you want a mesh, hit "Play"
in editor. No warranties whatsoever. 

#Related materials:
* Creating Spherical Worlds (sap 0251) (spore developers)
* https://en.wikipedia.org/wiki/Quadrilateralized_spherical_cube
* COMPARISON OF SPHERICAL CUBE MAP PROJECTIONS
USED IN PLANET-SIZED TERRAIN RENDERING
Aleksandar M. Dimitrijevi´c, Martin Lambers and Dejan D. Ranˇci´c
* https://acko.net/blog/making-worlds-1-of-spheres-and-cubes/

#Details?
I've tried tetrahedra and basic cube using normalized lerp, and slerp.
I originally hoped that I can get away with using a tetrahedra-based map, because
it can be wrapped nicely into a texture, but the distortion is significant, 
whether it is normalized lerp or slerp.

#Conclusion?
* The simplest way to store spherical data would be using spore dev
method, where they simply used cubemaps. The advantage is that it is
fast and GPU accelerated. The disadvantage is distortion, which is the worst
among all possibilities presented in "comparison" paper.
* The most decent way of storing data seems to be ASC projection 
("Adjusted Sphere Cube"), as it is equal area and does not waste too many
texels. Dealing with it requires atan, sin and cos, but with modern gpu
horsepower this should not be a problem, even if you do it per-pixel. Plus
you can always do a lookup.
* It seems that that there's no point in tryign to directly use map faces in 
some sort of "flat" overland view, like acko's author is trying to do and it 
would be better to generate "flat" overland view dynamically by sampling the map.
* Thinking about it more, for many things it would be erasonable to use lat/long coordinates,
and convert them to whatever is necessary when needed. It is also possible to use
the cubemap for landscape data and t hen use whatever for the map itself.
* It seems that if the planet is sufficiently large, the best idea would be to treat 
things like cities as "anchoret" flat or mostly flat regions. The terrain of the region could be generated
from cubic map data, but while the player is within the region, for all practical purposes, 
it would be a standard flat world.
*/
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class GlobeVisualizer: MonoBehaviour{
	public enum GridType{
		Tetrahedra, SphereCube, AscCube
	};

	public enum LerpType{
		NormLerp, Lerp, Slerp
	};

	[SerializeField] bool useDrawGizmos = true;
	[SerializeField] GridType _gridType = GridType.AscCube;
	[SerializeField] LerpType _lerpType = LerpType.NormLerp;
	[SerializeField] int _numTess = 8;

	GridType lastGridType = GridType.AscCube;
	LerpType lastLerpType = LerpType.NormLerp;
	int lastTess = 1;

	MeshRenderer meshRend = null;
	MeshFilter meshFilt = null;
	Mesh mesh = null;
	Material material = null;

	int numTess => Mathf.Max(_numTess, 1);
	static float sqrt(float arg){
		return Mathf.Sqrt(arg);
	}

	static void line(Vector3 a, Vector3 b){
		Gizmos.DrawLine(a, b);
	}

	static void gizTrig(Vector3 a, Vector3 b, Vector3 c){
		line(a, b);
		line(b, c);
		line(c, a);
	}
	
	static void sphereLine(Vector3 a, Vector3 b, float tStep = 0.1f){
		float t = tStep;
		float prevT = 1.0f;
		var prevV = a;
		while(t < 1.0f){
			var v = Vector3.Slerp(a, b, t);
			line(prevV, v);
			prevT = t;
			prevV = v;
			t += tStep;
		}
		line(prevV, b);
	}

	static Vector3 sphereTrigPoint(Vector3 a, Vector3 b, Vector3 c, float u, float v){
		if (v >= 1.0f)
			return a;
		if (v <= 0.0f)
			return Vector3.Slerp(c, b, u);
		
		var start = Vector3.Slerp(c, a, v);
		var end = Vector3.Slerp(b, a, v);
		var u1 = u / (1.0f - v);
		return Vector3.Slerp(start, end, u1);
	}

	static Vector3 quadPoint(Vector3 a, Vector3 b, Vector3 c, Vector3 d, float u, float v, LerpDelegate lerp){
		var start = lerp(a, c, v);
		var end = lerp(b, d, v);
		return lerp(start, end, u);
	}

	static Vector3 quadPoint(Quad q, float u, float v, LerpDelegate lerp){
		var start = lerp(q.a, q.c, v);
		var end = lerp(q.b, q.d, v);
		return lerp(start, end, u);
	}

	static Vector3 trigQuadPoint(Vector3 a, Vector3 b, Vector3 c, float u, float v, LerpDelegate lerp) 
		=> quadPoint(a, a, c, b, u, v, lerp);

	static void sphereTrig(Vector3 a, Vector3 b, Vector3 c){
		//line(a, b);
		//line(b, c);
		//line(c, a);

		var dt = 0.1f;
		sphereLine(a, b, dt);
		sphereLine(b, c, dt);
		sphereLine(a, c, dt);

		var ab = sphereTrigPoint(a, b, c, 0.5f, 0.5f);
		var ac = sphereTrigPoint(a, b, c, 0.0f, 0.5f);
		var bc = sphereTrigPoint(a, b, c, 0.5f, 0.0f);

		var abc = sphereTrigPoint(a, b, c, 0.25f, 0.5f);

		gizTrig(ab, bc, ac);
		line(ab, abc);
		line(ac, abc);
		line(bc, abc);
	}

	static void quad(Quad q){
		line(q.a, q.b);
		line(q.c, q.d);
		line(q.a, q.c);
		line(q.b, q.d);
	}

	static void gizQuad(Vector3 a, Vector3 b, Vector3 c, Vector3 d){
		line(a, b);
		line(c, d);
		line(a, c);
		line(b, d);
	}

	public struct Triangle{
		public Vector3 a;
		public Vector3 b;
		public Vector3 c;
		public Triangle(Vector3 a_, Vector3 b_, Vector3 c_){
			a = a_;
			b = b_;
			c = c_;
		}
	}

	public struct Quad{
		public Vector3 a;
		public Vector3 b;
		public Vector3 c;
		public Vector3 d;

		public Quad(Vector3 a_, Vector3 b_, Vector3 c_, Vector3 d_){
			a = a_;
			b = b_;
			c = c_;
			d = d_;
		}
	}

	public delegate void TrigDelegate(Vector3 a, Vector3 b, Vector3 c);
	public delegate void QuadDelegate(Vector3 a, Vector3 b, Vector3 c, Vector3 d);
	public delegate Vector3 LerpDelegate(Vector3 arg1, Vector3 arg2, float t);
	public delegate Vector3 UvDelegate(float u, float v);

	//static void uvGrid<Vert>(int numSteps, UvDelegate)

	static void uvGrid(int numSteps, UvDelegate uvPoint, QuadDelegate quad){
		float dt = 1.0f/(float)numSteps;
		Vector2 uv0 = Vector2.zero, uv1 = Vector2.zero;
		for(int iv = 0; iv < numSteps; iv++){
			uv0.y = iv * dt;
			uv1.y = uv0.y + dt;
			for(int iu = 0; iu < numSteps; iu++){
				uv0.x = iu * dt;
				uv1.x = uv0.x + dt;

				quad(
					uvPoint(uv0.x, uv0.y),
					uvPoint(uv1.x, uv0.y),
					uvPoint(uv0.x, uv1.y),
					uvPoint(uv1.x, uv1.y)
				);
			}
		}
	}

	static void quadTess(Vector3 a, Vector3 b, Vector3 c, Vector3 d, LerpDelegate lerp, QuadDelegate quad, int numSteps = 8){
		quadTess(new Quad(a, b, c, d), lerp, quad, numSteps);
	}

	static void quadTess(Quad q, LerpDelegate lerp, QuadDelegate quad, int numSteps = 8){
		//var quad = new Quad(a, b, c, d);

		if (numSteps <= 1){
			quad(q.a, q.b, q.c, q.d);
			return;
		}

		float dt = 1.0f/(float)numSteps;
		for(int iv = 0; iv < numSteps; iv++){
			float v0 = iv * dt;
			float v1 = v0 + dt;
			for(int iu = 0; iu < numSteps; iu++){
				float u0 = iu * dt;
				float u1 = u0 + dt;

				quad(
					quadPoint(q, u0, v0, lerp),
					quadPoint(q, u1, v0, lerp),
					quadPoint(q, u0, v1, lerp),
					quadPoint(q, u1, v1, lerp)
				);
			}
		}
	}

	public class MeshBuilder{
		List<Vector3> verts = new();
		List<Vector2> uvs = new();
		List<Vector3> norms = new();
		List<int> idx = new();
		public void clear(){
			verts.Clear();
			uvs.Clear();
			norms.Clear();
			idx.Clear();
		}

		public void applyTo(Mesh mesh){
			mesh.Clear();
			mesh.SetVertices(verts);
			mesh.SetUVs(0, uvs);
			mesh.SetNormals(norms);
			mesh.SetIndices(idx, 0, idx.Count, MeshTopology.Triangles, 0);
		}

		public void addTriangle(Vector3 a, Vector3 b, Vector3 c){
			var baseIdx = verts.Count;
			verts.Add(a);
			verts.Add(b);
			verts.Add(c);
			uvs.Add(new Vector2(0.0f, 0.0f));
			uvs.Add(new Vector2(1.0f, 1.0f));
			uvs.Add(new Vector2(0.0f, 1.0f));
			var n = Vector3.Cross(b - a, c - a).normalized;
			norms.Add(n);
			norms.Add(n);
			norms.Add(n);
			idx.Add(baseIdx + 0);
			idx.Add(baseIdx + 1);
			idx.Add(baseIdx + 2);
		}

		public void addQuad(Vector3 a, Vector3 b, Vector3 c, Vector3 d){
			var baseIdx = verts.Count;
			verts.Add(a);
			verts.Add(b);
			verts.Add(c);
			verts.Add(d);
			uvs.Add(new Vector2(0.0f, 0.0f));
			uvs.Add(new Vector2(1.0f, 0.0f));
			uvs.Add(new Vector2(0.0f, 1.0f));
			uvs.Add(new Vector2(1.0f, 1.0f));
			var n = Vector3.Cross(d - a, c - b).normalized;
			norms.Add(n);
			norms.Add(n);
			norms.Add(n);
			norms.Add(n);
			idx.Add(baseIdx + 0);
			idx.Add(baseIdx + 1);
			idx.Add(baseIdx + 2);
			idx.Add(baseIdx + 1);
			idx.Add(baseIdx + 3);
			idx.Add(baseIdx + 2);
		}
	}

	static void trigTess(Vector3 a, Vector3 b, Vector3 c, LerpDelegate lerp, TrigDelegate trig, int numSteps = 8){
		if (numSteps <= 1){
			trig(a, b, c);
			return;
		}

		float dt = 1.0f/(float)numSteps;

		for(int i = 0; i < numSteps; i++){
			var v0 = dt * i;
			var v1 = dt * (i + 1);

			var numU0 = i;
			var numU1 = i + 1;

			var ustep0 = (numU0 <= 0) ? 0.0f: 1.0f/(float)numU0;
			var ustep1 = 1.0f / (float)(numU1);

			for(int j = 0; j < numU0; j++){
				var u00 = j * ustep0;
				var u01 = u00 + ustep0;
				var u10 = j * ustep1;
				var u11 = u10 + ustep1;

				var a1 = trigQuadPoint(a, b, c, u00, v0, lerp);
				var b1 = trigQuadPoint(a, b, c, u01, v0, lerp);
				var c1 = trigQuadPoint(a, b, c, u10, v1, lerp);
				var d1 = trigQuadPoint(a, b, c, u11, v1, lerp);

				trig(a1, d1, c1);
				trig(b1, d1, a1);
			}

			trig(
				trigQuadPoint(a, b, c, 1.0f, v0, lerp),
				trigQuadPoint(a, b, c, 1.0f, v1, lerp),
				trigQuadPoint(a, b, c, 1.0f - ustep1, v1, lerp)
			);
		}
	}

	static Vector3 normLerp(Vector3 a, Vector3 b, float t){
		return Vector3.Lerp(a, b, t).normalized;
	}

	LerpDelegate getLerp() => _lerpType switch {
		LerpType.Lerp => Vector3.Lerp,
		LerpType.NormLerp => normLerp,
		LerpType.Slerp => Vector3.Slerp,
		_ => normLerp
	};

	static Vector3 vec3(float x, float y, float z){
		return new Vector3(x, y, z);
	}

	void tetrahedraPlanet(TrigDelegate trig){
		var a = vec3(0.0f, 1.0f, 0.0f);
		var b = vec3(sqrt(2.0f/3.0f), -1.0f/3.0f, -sqrt(2.0f/9.0f));
		var c = vec3(-sqrt(2.0f/3.0f), -1.0f/3.0f, -sqrt(2.0f/9.0f));
		var d = vec3(0.0f, -1.0f/3.0f, sqrt(8.0f/9.0f));

		var tess = numTess;
		LerpDelegate lerp = getLerp();
		trigTess(a, b, c, lerp, trig, tess);
		trigTess(a, d, b, lerp, trig, tess);
		trigTess(a, c, d, lerp, trig, tess);
		trigTess(d, c, b, lerp, trig, tess);
	}

	void cubePlanet(QuadDelegate quad){
		float dx = sqrt(1.0f/3.0f);

		System.Span<Vector3> v = stackalloc[]{
			vec3(dx, dx, dx),
			vec3(-dx, dx, dx),
			vec3(dx, -dx, dx),
			vec3(-dx, -dx, dx),
			vec3(dx, dx, -dx),
			vec3(-dx, dx, -dx),
			vec3(dx, -dx, -dx),
			vec3(-dx, -dx, -dx)
		};

		var p000 = vec3(dx, dx, dx);
		var p001 = vec3(-dx, dx, dx);
		var p010 = vec3(dx, -dx, dx);
		var p011 = vec3(-dx, -dx, dx);
		var p100 = vec3(dx, dx, -dx);
		var p101 = vec3(-dx, dx, -dx);
		var p110 = vec3(dx, -dx, -dx);
		var p111 = vec3(-dx, -dx, -dx);

		//LerpDelegate lerp = Vector3.Lerp;//Vector3.Slerp;
		LerpDelegate lerp = getLerp();//normLerp;//Vector3.Lerp;//Vector3.Slerp;
		//LerpDelegate lerp = Vector3.Slerp;
		var tess = numTess;

		quadTess(v[0], v[1], v[2], v[3], lerp, quad, tess);
		quadTess(v[5], v[4], v[7], v[6], lerp, quad, tess);

		quadTess(v[4], v[0], v[6], v[2], lerp, quad, tess);
		quadTess(v[1], v[5], v[3], v[7], lerp, quad, tess);

		quadTess(v[4], v[5], v[0], v[1], lerp, quad, tess);
		quadTess(v[2], v[3], v[6], v[7], lerp, quad, tess);
	}

	void ascGrid(Vector3 x, Vector3 y, Vector3 z, QuadDelegate quad){
		uvGrid(numTess, 
			(u, v) => {
				u = (u * 2.0f - 1.0f);
				v = -(v * 2.0f - 1.0f);
				float uAngle = u * Mathf.PI / 4.0f;				
				float vAngle = v * Mathf.PI / 4.0f;
				vAngle = Mathf.Atan(
					Mathf.Tan(v * Mathf.PI / 4.0f) * Mathf.Cos(uAngle)
				);

				var p = Vector3.zero;

				var uCos= Mathf.Cos(uAngle);
				var uSin = Mathf.Sin(uAngle);
				var vCos= Mathf.Cos(vAngle);
				var vSin = Mathf.Sin(vAngle);

				p += -x * uSin * vCos + z * uCos * vCos;
				p += y * vSin;

				return p;
			},
			quad
		);
	}

	void ascPlanet(QuadDelegate quad){
		Vector3 x = Vector3.right,
			y = Vector3.up,
			z = Vector3.forward;
		ascGrid(x, y, z, quad);
		ascGrid(-x, y, -z, quad);
		ascGrid(-z, y, x, quad);
		ascGrid(z, y, -x, quad);
		ascGrid(-x, z, y, quad);
		ascGrid(x, z, -y, quad);
	}

	void processSphere(TrigDelegate trig, QuadDelegate quad){
		switch(_gridType){
			case(GridType.Tetrahedra):
				tetrahedraPlanet(trig);
				break;
			case(GridType.SphereCube):
				cubePlanet(quad);
				break;
			default:
				ascPlanet(quad);
				break;
		}
	}

	void drawGizmos(){
		if (useDrawGizmos)
			processSphere(gizTrig, gizQuad);
	}

	void drawGizmosWrapper(Color c){
		var oldColor = Gizmos.color;
		Gizmos.color = c;
		drawGizmos();
		Gizmos.color = oldColor;
	}

	void OnDrawGizmosSelected(){
		drawGizmosWrapper(Color.white);
	}

	void OnDrawGizmos(){
		drawGizmosWrapper(Color.yellow);
	}

	MeshBuilder meshBuilder = new();

	void rebuildMesh(){
		if (!meshFilt){
			meshFilt = gameObject.AddComponent<MeshFilter>();
		}
		if (!meshRend){
			meshRend = gameObject.AddComponent<MeshRenderer>();
		}
		if (!material){
			material = new Material(Shader.Find("Standard"));
		}
		if (!mesh){
			mesh = new Mesh();
		}
		meshRend.sharedMaterial = material;
		meshFilt.sharedMesh = mesh;
		meshBuilder.clear();
		processSphere(meshBuilder.addTriangle, meshBuilder.addQuad);
		meshBuilder.applyTo(mesh);

		lastLerpType = _lerpType;
		lastTess = _numTess;
		lastGridType = _gridType;
	}

	bool checkMeshParameterChange(){
		var result = (_lerpType != lastLerpType) ||
			(_gridType != lastGridType) ||
			(_numTess != lastTess);
		lastLerpType = _lerpType;
		lastGridType = _gridType;
		lastTess = _numTess;
		return result;
	}

	void OnEnable(){
		rebuildMesh();
	}

	void OnDisable(){
		if (mesh){
			Destroy(mesh);
			mesh = null;
		}
		if (material){
			Destroy(material);
			material = null;
		}
	}

	void Update(){
		if (checkMeshParameterChange()){
			rebuildMesh();
		}
	}
}