Friends don’t let friends generate icosahedrons

by admin

A while ago, I did a retake for a course on procedural programming. One of the assignments was to generate a textured sphere. You would be marked on getting the texturing right, but I got distracted and decided to try making an icosahedron instead and looking at other games to get ideas, find out now where you can play online. However, I also made a version that used a more traditional subdivision method: generate circles on a cylinder, and have the radius of the circles depend on the cosine of the distance on the cylinder’s height. Here are my spheres:

Looks pretty round right? However, let’s take a look at their wireframes:

Click on the image for a larger version.

From the thumbnail, the second version looks unchanged. But when you click on it, you’ll notice that the lines are so dense that it looks textured!

What’s the difference?

The sphere on the left (sphere 1) uses the traditional method of sphere generation. It has 31 subdivisions on the y-axis and 31 subdivisions on the z-axis of the half-sphere. This half-sphere is then mirrored to the bottom. It has a total of 3,844 faces.

In pseudocode:

for (y = 0; y < subdivisions_y; y++)
{
	y = cos(degrees_y) * radius_sphere;
	
	radius_y = sin(degrees_y) * radius_sphere;
	
	for (z = 0; z < subdivisions_z; x++)
	{
		x = cos(degrees_z) * radius_y;
		z = sin(degrees_z) * radius_y
	}
}

The sphere on the right (sphere 2) uses an icosahedron subdivision algorithm to generate a sphere. It has a recursive depth of 5 and generates 109,200 faces.

In pseudocode:

// first, generate the 20 triangles of an icosahedron
// then subdivide them:

triangle_curr = triangle_first;
for (int i = 0; i < 20; i++)
{
	subdivide_triangle(curr, recursive_depth);
	triangle_curr = triangle_next;
}

The icosahedron is an almost perfect sphere, but it comes at a high price. It uses a lot more faces to achieve the same effect.

But okay, that’s not really fair. Let’s scale down the quality considerably:

Sphere 1 uses 5 subdivisions on the y-axis and 5 subdivisions on the z-axis, for a total of 100 faces.

Sphere 2 uses 0 recursive subdivisions, for a total of 100 faces.

They use the same amount of faces, but in my opinion, the sphere on the left looks better. It looks less lumpy and a lot more round. Let’s take a look at the amount of faces per quality level.

Icosahedron:

  • Level 0 – 100 faces
  • Level 1 – 420 faces
  • Level 2 – 1,700 faces
  • Level 3 – 6,820 faces
  • Level 4 – 27,300 faces
  • Level 5 – 109,220 faces

Subdivided sphere:

  • YZ: 5 – 100 faces
  • YZ: 10 – 400 faces
  • YZ: 15 – 900 faces
  • YZ: 20 – 1,600 faces
  • YZ: 25 – 2,500 faces
  • YZ: 30 – 3,600 faces

It’s easy to see that the subdivided sphere gives you a lot more bang for your buck. The 30-subdivisions version is comparably in quality to the 5-level recursive icosahedron, but it uses only 3.2% of the faces!

Texturing problems

The truth is: you don’t *need* the precision an icosahedron will give you. Because they both hide a much harder problem: texturing a 2D plane on a 3D sphere. Here’s what the top looks like:

On the top-left, you can see the texture being used. Coincidentally, it’s also being generated procedurally. (Hey, it was a course on procedural generation, right?) It looks terrible, but this is as good as it’s going to get. I got top marks for my texture mapping, because most people don’t even get it this right.

Why is it such a problem to map a texture to a sphere? Well, xkcd explains it better than I can:

Image taken from http://xkcd.net/977/

The way I solved it is by generating polar coordinates from normalized coordinates on the sphere to get the texture u and v. I won’t go into too much detail, because I don’t want to ruin the course material. But I do have a fix for the dateline issue, which took a very long time to figure out. When the texture goes around the sphere, you get to a face that has to wrap around from 1.0 to 0.0. If you don’t fix that, you will get an ugly band.

void ModelSphere::FixDateLine(tb::Vec2& a_Left, tb::Vec2& a_Right)
{
	float tt = 0.75f;
	float nn = 1.f - tt;

	if (tb::Math::Abs(a_Left.x - a_Right.x) > tt) 
	{ 
		if (a_Left.x < nn) { a_Left.x += 1.f; }
		if (a_Right.x < nn) { a_Right.x += 1.f; }
	}
}

It’s not a lot of code, but it isn’t explained properly anywhere else. The same code is used for both the icosahedron and the subdivided sphere, in case you were wondering.

Conclusion

Consider using cosine and sine to generate a sphere. It generates a lot less faces for the same amount of detail. For most games it will be “good enough”. Unless you’re generating planets that really, really need to be round all over its surface, you can get away with a subdivided sphere quite easily. Casino games have been getting very appear everywhere even in movies check this movies you forgot had a casino scene.