Procedural Meshes - Circles

If you're specifically interested in how to create procedural geometry in Unity and not in the mathematical details of creating circle geometry, go here:

http://www.youtube.com/watch?v=3jHe1FzrKD8.   Otherwise, please read on!

In the link above, we created a simple 4 vertex 2d rectangle (“quad”).  Quads are quite useful but sometimes you’re interested in more complex shapes.  How about a circle?  

Ok, that doesn’t sound that much more complex but it does allow us to get our hands dirty with some maths because let’s face it, there was no sexy math involved in creating a quad.  And, as we’ll soon see, a simple circle is more involved that it sounds.

You may remember this equation from school (if not, you can learn about it up with some cool videos from Khan Academy http://www.youtube.com/watch?v=6r1GQCxyMKI ):

x2 + y2 = r2

and it sure does look simple.  It says that the sum of the squares of x and y always have to equal some number, the radius squared.

In the case, it must sum up to be 1.  For example, here we’ve chosen our radius to be equal to 1 and 1² is still equal to 1.  To test this, let’s pick an x value that is less than our radius.  If we pick x to be 0.5 then x² will be equal to 0.25.  That leaves us with this equation: 0.25 + y² = 1.  So now we solve for y ("sqrt" means square root): y = sqrt(1 - 0.25).  We could compute that but we don’t really have to because we know that you have to add 0.75 to 0.25 to get 1.

Armed with that knowledge alone and some patience, you could probably get something working. and this seems sufficient to complete the task, but is it the best way?  Let’s explore this a bit further.

We know that creating procedural geometry involves creating a set of points and then connecting those points in sets of three to form triangles.  One way to this using the equation above might be to iterate across each x value and then generate the matching y value.  It might look something like this:

 for (float x = -1.0; x < 1.0; x+=0.1) {  
  float y = Mathf.sqrt(radius * radius - x * x);  
  myVertices.push(new Vector3(x, y, 0);  
 }  

This would get you points laid out across this curve:

But this is only half of what you want due to the fact that the definition of a full circle is not defined by a single mathematical function.  You’d have to run through the loop again and generate the bottom half.

 // Bottom half generated by using negative value  
 float y = -Mathf.sqrt(radius * radius - x * x);  

So it seems this method requires doing the full circles in 2 passes (2 for-loops).  But that’s not the biggest problem here.  Since we’re iterating by a constant value on the x direction (0.1 in the example), we’ll end up with y values that are closer together near x = 0 and y values that get increasingly further apart as we move toward +-1.  You'll get a distribution looking something like this:

If you were to triangulate that you'd notice that it looks blocky toward the left and right and smooth toward the top. Are we happy with that?

We want something evenly distributed.  More like this:

So let’s rethink this... This time, using sacred tools from the game developer’s toolbelt: vectors.  If you’re not already familiar with this extremely important concept, check out Khan Academy: (https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/vectors/v/linear-algebra--introduction-to-vectors).

Vectors will allow us to generate the vertex data in one convenient loop in an order that makes it easy to triangulate and even more importantly, our points will be evenly spaced out.  The idea is to start with a single vector and rotate it by a constant angle to get the next point.  We do this for the whole circle.  This image sequence will give you the basic idea:

This will give us a set of points around the circle.  But, in order to create triangles for this, we need just one more point.  Take a second and make a guess where it should go. If you guessed that it is needed in the middle of the circle you got it.  With one point in the center and a bunch of other points on the outside, we can then start carving this up like slices of a pie.

Let’s get to the code:

 // The more verts, the more 'round' the circle appears  
 // It's hard coded here but it would better if you could pass it in as an argument to this function  
 int numVerts = 41;  
 Mesh plane = new Mesh();  
 Vector3[] verts = new Vector3[numVerts];  
 Vector2[] uvs = new Vector2[numVerts];  
 int[] tris = new int[(numVerts * 3)];  
  In the beginning we set up for everything we’ll need later. We get an array of Vector3 (3 floats) to use for every point as well as arrays for uv coordinates and triangles.   
  // The first vert is in the center of the triangle  
 verts[0] = Vector3.zero;  
 uvs[0] = new Vector2(0.5f, 0.5f);  
 float angle = 360.0f / (float)(numVerts - 1);  

Here we create our center vertex as the first one in the array and we also figure out how big each slice of pie should be.  The number of pieces of pie (triangle) is equal to the number of vertices - 1.

 for (int i = 1; i < numVerts; ++i) {  
 verts[i] = Quaternion.AngleAxis(angle * (float)(i - 1), Vector3.back) * Vector3.up;  
  float normedHorizontal = (verts[i].x + 1.0f) * 0.5f;  
  float normedVertical = (verts[i].x + 1.0f) * 0.5f;  
  uvs[i] = new Vector2(normedHorizontal, normedVertical);  
 }  

Here we iterate through each slice of pie in similar fashion to that image sequence shown above.  In this code I’m starting with a vector pointing up and rotating it clockwise.  This is a little different from the images above but it doesn’t matter so long as you start somewhere and rotate all the way around.  You could choose other methods of rotation here but the Unity built in Quaternion is what I went with.  If the rotation is a little mysterious to you let me know and I’ll write something up on it.

 for (int i = 0; i + 2 < numVerts; ++i) {  
 int index = i * 3;  
  tris[index + 0] = 0;  
  tris[index + 1] = i + 1;  
  tris[index + 2] = i + 2;  
 }  

Here we create all of our triangles.  Each triangle with start with the vertex in the center and connect to 2 on the outside of the circle.

 // The last triangle has to wrap around to the first vert so we do this last and outside the lop  
 var lastTriangleIndex = tris.Length - 3;  
 tris[lastTriangleIndex + 0] = 0;  
 tris[lastTriangleIndex + 1] = numVerts - 1;  
 tris[lastTriangleIndex + 2] = 1;  

This is kind of a special case where we reuse a vertex so we save it for last and manually compute the final triangle.

 // The last triangle has to wrap around to the first vert so we do this last and outside the lop  
 var lastTriangleIndex = tris.Length - 3;  
 tris[lastTriangleIndex + 0] = 0;  
 tris[lastTriangleIndex + 1] = numVerts - 1;  
 tris[lastTriangleIndex + 2] = 1;  

Make sure you give the mesh everything you just computed and that’s it!  Now you’re thinking with portal....errr, ummm, vectors!

You can download the source package for everything here.