From 3e6a7f8ae2ba43728d16954ac7c31257b7bfb581 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Sun, 6 Dec 2015 15:55:36 +0200
Subject: [PATCH] Add a class for building icosahedron-based spheres

It doesn't do texture coordinates because there's no straightforward
mapping between a plane and an icosahedral surface.
---
 source/sphere.cpp | 179 ++++++++++++++++++++++++++++++++++++++++++++++
 source/sphere.h   |  25 +++++++
 2 files changed, 204 insertions(+)

diff --git a/source/sphere.cpp b/source/sphere.cpp
index 0bedf150..0b48ee40 100644
--- a/source/sphere.cpp
+++ b/source/sphere.cpp
@@ -1,7 +1,10 @@
 #include <cmath>
+#include <vector>
 #include "primitivebuilder.h"
 #include "sphere.h"
 
+using namespace std;
+
 namespace Msp {
 namespace GL {
 
@@ -77,5 +80,181 @@ void UvSphereBuilder::build(PrimitiveBuilder &builder) const
 	}
 }
 
+
+// https://en.wikipedia.org/wiki/Regular_icosahedron#Cartesian_coordinates
+float IcoSphereBuilder::base_vertices[12*3] =
+{
+	 0.0f,       -0.5257311f, -0.8506508f,
+	 0.0f,        0.5257311f, -0.8506508f,
+	 0.0f,       -0.5257311f,  0.8506508f,
+	 0.0f,        0.5257311f,  0.8506508f,
+	-0.8506508f,  0.0f,       -0.5257311f,
+	-0.8506508f,  0.0f,        0.5257311f,
+	 0.8506508f,  0.0f,       -0.5257311f,
+	 0.8506508f,  0.0f,        0.5257311f,
+	-0.5257311f, -0.8506508f,  0.0f,
+	 0.5257311f, -0.8506508f,  0.0f,
+	-0.5257311f,  0.8506508f,  0.0f,
+	 0.5257311f,  0.8506508f,  0.0f
+};
+
+unsigned IcoSphereBuilder::base_triangles[20*3] =
+{
+	0, 1, 6,
+	1, 0, 4,
+	2, 3, 5,
+	3, 2, 7,
+	4, 5, 10,
+	5, 4, 8,
+	6, 7, 9,
+	7, 6, 11,
+	8, 9, 2,
+	9, 8, 0,
+	10, 11, 1,
+	11, 10, 3,
+	0, 8, 4,
+	0, 6, 9,
+	1, 4, 10,
+	1, 11, 6,
+	2, 5, 8,
+	2, 9, 7,
+	3, 10, 5,
+	3, 7, 11
+};
+
+unsigned IcoSphereBuilder::base_edges[30*2] = { 0, 0 };
+unsigned IcoSphereBuilder::base_tri_edges[20*3] = { 0, 0, 0 };
+
+IcoSphereBuilder::IcoSphereBuilder(float r, unsigned s):
+	radius(r),
+	subdivision(s)
+{
+	if(base_edges[0]==base_edges[1])
+		initialize_edges();
+}
+
+void IcoSphereBuilder::initialize_edges()
+{
+	vector<int> edge_map(12*12, -1);
+	unsigned next_edge = 0;
+	for(unsigned i=0; i<20; ++i)
+		for(unsigned j=0; j<3; ++j)
+		{
+			unsigned v1 = base_triangles[i*3+j];
+			unsigned v2 = base_triangles[i*3+(j+1)%3];
+			int e = edge_map[v1*12+v2];
+			if(e<0)
+			{
+				e = next_edge++;
+				base_edges[e*2] = v1;
+				base_edges[e*2+1] = v2;
+				// The other triangle using this edge will have the vertices swapped
+				edge_map[v2*12+v1] = e|32;
+			}
+			base_tri_edges[i*3+j] = e;
+		}
+}
+
+void IcoSphereBuilder::build(PrimitiveBuilder &bld) const
+{
+	for(unsigned i=0; i<12; ++i)
+	{
+		const float *v = base_vertices+i*3;
+		bld.normal(v[0], v[1], v[2]);
+		bld.vertex(v[0]*radius, v[1]*radius, v[2]*radius);
+	}
+
+	if(subdivision>1)
+	{
+		vector<Vector3> edge_subdiv(30*(subdivision+1));
+		for(unsigned i=0; i<30; ++i)
+		{
+			Vector3 v1(base_vertices+base_edges[i*2]*3);
+			Vector3 v2(base_vertices+base_edges[i*2+1]*3);
+			for(unsigned j=1; j<subdivision; ++j)
+			{
+				float t = static_cast<float>(j)/subdivision;
+				Vector3 v = v1*(1.0f-t)+v2*t;
+				edge_subdiv[i*(subdivision-1)+j-1] = v;
+				v.normalize();
+				bld.normal(v);
+				bld.vertex(v*radius);
+			}
+		}
+
+		for(unsigned i=0; i<20; ++i)
+			for(unsigned j=1; j<subdivision; ++j)
+			{
+				unsigned e = base_tri_edges[i*3];
+				Vector3 v1 = edge_subdiv[edge_vertex(e, subdivision-j)];
+				e = base_tri_edges[i*3+1];
+				Vector3 v2 = edge_subdiv[edge_vertex(e, j)];
+				for(unsigned k=1; k<j; ++k)
+				{
+					float t = static_cast<float>(k)/j;
+					Vector3 v = normalize(v1*(1.0f-t)+v2*t);
+					bld.normal(v);
+					bld.vertex(v*radius);
+				}
+			}
+
+		for(unsigned i=0; i<20; ++i)
+		{
+			unsigned mid = 12+30*(subdivision-1)+i*(subdivision-1)*(subdivision-2)/2;
+			for(unsigned j=1; j<=subdivision; ++j)
+			{
+				bld.begin(TRIANGLE_STRIP);
+				if(j==subdivision)
+					bld.element(base_triangles[i*3]);
+				else
+					bld.element(12+edge_vertex(base_tri_edges[i*3], subdivision-j));
+
+				if(j==1)
+				{
+					bld.element(base_triangles[i*3+1]);
+					bld.element(12+edge_vertex(base_tri_edges[i*3+1], j));
+				}
+				else
+				{
+					bld.element(12+edge_vertex(base_tri_edges[i*3], subdivision-j+1));
+
+					if(j==subdivision)
+						bld.element(12+edge_vertex(base_tri_edges[i*3+2], subdivision-1));
+					else
+						bld.element(mid+(j-1)*(j-2)/2);
+
+					for(unsigned k=2; k<j; ++k)
+					{
+						bld.element(mid+(j-2)*(j-3)/2+k-2);
+						if(j==subdivision)
+							bld.element(12+edge_vertex(base_tri_edges[i*3+2], subdivision-k));
+						else
+							bld.element(mid+(j-1)*(j-2)/2+k-1);
+					}
+
+					bld.element(12+edge_vertex(base_tri_edges[i*3+1], j-1));
+					if(j==subdivision)
+						bld.element(base_triangles[i*3+2]);
+					else
+						bld.element(12+edge_vertex(base_tri_edges[i*3+1], j));
+				}
+				bld.end();
+			}
+		}
+	}
+	else
+	{
+		bld.begin(TRIANGLES);
+		for(unsigned i=0; i<20*3; ++i)
+			bld.element(base_triangles[i]);
+		bld.end();
+	}
+}
+
+unsigned IcoSphereBuilder::edge_vertex(unsigned e, unsigned i) const
+{
+	return (e&31)*(subdivision-1)+((e&32)?subdivision-i:i)-1;
+}
+
 } // namespace GL
 } // namespace Msp
diff --git a/source/sphere.h b/source/sphere.h
index b69c4083..b20ff541 100644
--- a/source/sphere.h
+++ b/source/sphere.h
@@ -20,6 +20,31 @@ public:
 	virtual void build(PrimitiveBuilder &) const;
 };
 
+
+class IcoSphereBuilder: public GeometryBuilder
+{
+private:
+	float radius;
+	unsigned subdivision;
+
+	static float base_vertices[];
+	static unsigned base_triangles[];
+	static unsigned base_edges[];
+	static unsigned base_tri_edges[];
+
+public:
+	IcoSphereBuilder(float, unsigned);
+private:
+	static void initialize_edges();
+
+public:
+	using GeometryBuilder::build;
+	virtual void build(PrimitiveBuilder &) const;
+
+private:
+	unsigned edge_vertex(unsigned, unsigned) const;
+};
+
 } // namespace GL
 } // namespace Msp
 
-- 
2.45.2