In this article we want to draw the go stone using OpenGL.
Unfortunately we can’t just tell the graphics card, “Hey! Please draw the intersection of two spheres with radius r and d apart with a bevel torus r1 and r2!“, because modern 3D graphics cards work by drawing triangles. We have to take our mathematical definition of the go stone and turn it into a set of triangles that the graphics card can render.
This is called tessellation and there are several different ways to do it.
Longitude And Lattitude
The first way that I tried was to consider sphere rendering like a globe with longitude/latitude. I started with a ring around the ‘equator’ of the go stone, stepping these rings up to the top of the sphere like the north pole on a globe.
Unfortunately, just like longitude/latitude on a globe, tessellating this way leads to very distorted mapping around the pole and a lot of wasted triangles:
The next method is triangle subdivision. You start with an approximate shape then subdivide each triangle into four smaller triangles recursively like this:
Since the go stone only needs the top 1⁄3 or 1⁄4 of a sphere, I didn’t want to subdivide a whole sphere only to throw most of it away. So I designed my own subdivision algorithm to generate only the top section of a sphere.
After some trial and error I found that a pentagon plus a center vertex at the pole of the sphere was a good initial generator that minimized the distortion that occurs during subdivision. The only tricky part is that when subdividing you need to keep track of whether the edge is a sphere edge or a circle edge, as the subdivided vertex must be projected differently.
With this technique I was able to generate a much more efficient tessellation:
Tessellating The Bevel
Now we need to tesselate the bevel. To do this I take the vertices which form the circle edge at the bottom of the top sphere surface and calculate the angle of each vertex about the y axis. I then use these angles to sweep around the torus ensuring that the torus vertices weld perfectly with the top and bottom sphere sections.
Due to how recursive subdivision works a lot of duplicate vertices are generated.
I’d rather not have the graphics card waste time transforming the same vertex over and over, so as I add vertices to the mesh I hash vertex positions into a 3D grid (~1mm cells) and reuse an existing vertex if the position and normals match within some small epsilon value.
With vertex welding the reduction in vertices is dramatic: 53000 to just 6500.
NEXT ARTICLE: How The Go Stone Moves
Glenn Fiedler is the founder and CEO of Network Next.
Network Next is fixing the internet for games by creating a marketplace for premium network transit.