Tessellating The Go Stone

Hello, I’m Glenn Fiedler and welcome to Virtual Go, my project to simulate a Go board and stones.

In the previous article we mathematically defined the shape of a go stone.

In this article we want to draw the go stone using OpenGL so we can visualize it before we start doing physics calculations. It’s difficult to know if your physics calculations are working properly if you can’t see the result on your screen :)

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!”.

These days 3D graphics hardware works by drawing triangles, so 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.

naive-tesselation-side-view

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:

inefficient-tesselation-at-pole

Triangle Subdivision

The next method I tried was triangle subdivision. You start with an approximate shape then subdivide each triangle into four smaller triangles recursively like this:

sphere tessellation

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.

generating-shape

With this technique I was able to generate a much more efficient tessellation:

regular-tesselation

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.

end-result-go-stone-with-bevel

Vertex Welding

Finally, due to the way the the 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 tolerance.

With vertex welding the reduction in vertices is roughly 53000 -> 6500 which is a huge win.

For more information on vertex welding please refer to the discussion in Real-Time Collision Detection by Christer Ericson.


Next: How The Go Stone Moves




If you enjoyed this article please donate.

Donations offset hosting costs and encourage me to write more articles!

Leave a Reply

Glenn Fiedler's Game Development Articles and Tutorials