Thoughts on tesselating a sphere

January 23, 2016 — When programming a space game, you’re going to need some planets. And that means you need some spheres. And that means you’re going to need to tessellate some spheres, meaning, produce an approximation of a sphere that is made out of flat triangles.

There are a lot of different ways of doing it, and I have tried a few, going through a progression which I suspect many others have gone through as well. In the beginning my space game used my own, very simple, and very slow software renderer. I was not concerned even with texture mapping, and required my models to have an extremely low polygon count, and so the merest symbolic suggestion of a sphere was sufficient. Without putting much thought into it, I just created a sphere in OpenSCAD, exported it as an STL file, and called it done.

OpenSCAD sphere

This was fine, until I wanted to try wrapping a texture around the sphere. At the poles, the triangles get smaller and smaller. If you try to use an equi-rectangular mapping, that is, take an image that is twice as wide as it is high, and wrap it into a cylinder, then pinch the top and bottom of the cylinder to fit it onto the sphere, you get quite a lot of distortion at the poles. You can mitigate this somewhat be pre-stretching the image at the poles, but you lose some detail.

To avoid this, you can cube map a texture onto the sphere. You can do this with any geometry, and the tessellation of the sphere doesn’t really matter for purposes of cube-mapping a sphere, except that the interpolation tends to work a bit better if the triangles on the sphere are more uniformly sized. You can get a “smoother” sphere by having more uniformly sized triangles.

This leads to the next method of tessellating a sphere, the subdivided icosohedron. This has very nice, almost uniformly sized triangles, and works very well indeed.

Subdivided icosahedron

The problem comes when you try to do normal mapping to get nice lighting of detailed features like mountains and craters on the surface of your planets. To do normal mapping, you need to have per-vertex normal, tangent, and bi-tangent vectors which get interpolated across the faces of the triangles in the shader program. This would all work fine on the icosahedron if you could get a continuous field of tangent and bitangent vectors on the surface of a sphere. But you cannot get such a field, there will be discontinuities in any such filed (see the Hairy Ball Theorem). Discontinuities aren’t a problem in and of themselves, but manifest as problems when a triangle spans a discontinuity, which throws the interpolation off. The trick is to get the discontinuities to reside between the triangles. Doing this on a subdivided icosahedron would be quite tricky though.

This leads us to the next iteration of sphere tessellation, the spherified cube. The idea is you create a cube at the origin, and each of the six faces is divided into a grid, and each square of the grid is cut diagonally into two triangles. Then normalize every vertex. Voila! A sphere! Additionally if you make sure the edges of each of the six faces of the cube do not share vertices, then you can compute the per-vertex normal, tangent, and bitangent vectors independently for each face. This means that the discontinuities reside between the six faces, and each face independently can be free of discontinuities, and since no triangles span the boundary between faces, that means no triangles span discontinuities in the tangent and bitangent vector fields, and the interpolation across triangle faces works everywhere without problems.

Spherified cube

But, with a naive construction of the cube faces — dividing them into a uniform grid — another minor problem becomes apparent. The triangles near the center of the cube faces are much larger than the triangles near the corners of the cube faces. There is a simple solution to this. Instead of dividing the faces into a regular grid, divide them into a grid based on equal angles between vertices. For example, if each face is to be divided into a 10×10 grid, the naive way would be to divide the length of one edge of each face by ten, and make 100 equal sized squares. Once normalized into a sphere, you get the problematic distortion. Instead, we notice that from one edge of a face to another we sweep an arc of 90 degrees. So we can start with an angle of -45 degrees, and sweep across placing 10 vertices 9 degrees apart from one another. This will lead to more uniformly sized rectangles, and thus, more uniformly sized triangles.

Better spherified cube (more uniformly sized triangles)

There is one more step we can take. If we look at the corners of each face of the cube, we can see that the rectangles are in some cases cut into two thin slivers of triangles. If instead the rectangle had been cut by the other diagonal, the resulting triangles would have been fatter, and closer to an equilateral triangle than to the thin slivers they are now. So when splitting our rectangles into triangles we can choose to split them by the shortest diagonal. This yields even more uniformly sized triangles.

Even better spherified cube (even more uniformly sized triangles)

And that is the tessellation I am using lately. Perhaps something even better might come along.

~ by scaryreasoner on January 23, 2016.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: