Creating Procedural Planets In Unity — Part 2
Welcome to Part 2 of an ongoing tutorial series about the Poly Universe Project, where I’m sharing what I’ve learned about making procedural planets in Unity. If didn’t just finish reading Part 1, here’s a quick recap: We’ve talked about different methods for subdividing simple objects, and we have the code necessary to generate a round sphere of polygons.
Now let’s start on the code for extruding and insetting groups of faces, which will let us add landmasses to our planets! Like before, you can find an example Unity project that includes all of this code right here, on GitHub.
Step 1 — Stitching Polygons
Extruding a set of polygons means separating them from their neighbors, and pulling them upwards. Since each poly in our planet currently shares vertices with its neighbors, the first thing we’ll need to do is identify the edges that need to be separated, and then create new vertices for the polygons that we want to extrude. This will let us move them without dragging their neighbors along with them.
But before we can do that we need to let each polygon on our planet know who its neighbors are. First let’s add a List of neighbors to the Polygon class, and a simple function to ask if two Polygons are neighbors. We’ll also add a way to replace neighbors, for when we want to split the world surface apart, and we’ll give each poly a color, so that we can tell the ocean apart from the land…
public class Polygon
{
public List<int> m_Vertices;
public List<Polygon> m_Neighbors;
public Color32 m_Color;
public bool m_SmoothNormals; public Polygon(int a, int b, int c)
{
m_Vertices = new List<int>() { a, b, c };
m_Neighbors = new List<Polygon>(); // This will determine whether a polygon's normals smoothly
// blend into its neighbors, or if it should have sharp edges.
m_SmoothNormals = true; // Hot Pink is an excellent default color because you'll
// notice instantly if you forget to set it to something else.
m_Color = new Color32(255, 0, 255, 255);
} public bool IsNeighborOf(Polygon other_poly)
{
int shared_vertices = 0;
foreach (int vertex in m_Vertices)
{
if (other_poly.m_Vertices.Contains(vertex))
shared_vertices++;
} // A polygon and its neighbor will share exactly
// two vertices. Ergo, if this poly shares two
// vertices with the other, then they are neighbors. return shared_vertices == 2;
} // Mr. Roger's voice: Please won't you replace my neighbor. public void ReplaceNeighbor(Polygon oldNeighbor,
Polygon newNeighbor)
{
for(int i = 0; i < m_Neighbors.Count; i++)
{
if(oldNeighbor == m_Neighbors[i])
{
m_Neighbors[i] = newNeighbor;
return;
}
}
}
}
Notice that we can’t fill out the m_Neighbors list in the same way that we fill out the m_Vertices list in the constructor. This has to be done later, once all the polygons have been created. So let’s add a new function to the Planet class to calculate the neighbors for each Polygon:
public class Planet
{
...
public void CalculateNeighbors()
{
foreach (Polygon poly in m_Polygons)
{
foreach (Polygon other_poly in m_Polygons)
{
if (poly == other_poly)
continue;
if (poly.IsNeighborOf (other_poly))
poly.m_Neighbors.Add(other_poly);
}
}
}
}Time for a quick digression about run-time performance! Calculating each Polygon’s neighbors, like we just did above, is pretty slow. There are much faster ways to do this than by looping over each polygon in the planet twice, but faster methods are also going to be much harder to read and understand. So here, and in general in these tutorials, if there’s a trade-off between clarity and efficiency, I’ve opted for clarity. If you’re interested in optimization, let me know in the comments; I can do another tutorial in the future to show how these techniques can be sped up.
Back to business! Now that each Polygon knows who its neighbors are, what we really want to be able to do is to grab a set of Polygons and separate them from any neighbors who are outside of that set. This will let us grab a section of the planet and drag it upwards to make land, without dragging the edge of the ocean up with it. To do this we need to identify the Edges that lay between the Polygons that we’ll be separating. Let’s create an Edge class:
public class Edge
{
// The Poly that's inside the Edge. This is the one
// we'll be extruding or insetting.
public Polygon m_InnerPoly; // The Poly that's outside the Edge. We'll be leaving
// this one alone.
public Polygon m_OuterPoly; //The vertices along this edge, according to the Outer poly.
public List<int> m_OuterVerts; //The vertices along this edge, according to the Inner poly.
public List<int> m_InnerVerts; public Edge(Polygon inner_poly, Polygon outer_poly)
{
m_InnerPoly = inner_poly;
m_OuterPoly = outer_poly;
m_OuterVerts = new List<int>(2);
m_InnerVerts = new List<int>(2); //Find which vertices these polys share.
foreach (int vertex in inner_poly.m_Vertices)
{
if (outer_poly.m_Vertices.Contains(vertex))
m_InnerVerts.Add(vertex);
} // For consistency, we want the 'winding order' of the
// edge to be the same as that of the inner polygon.
// So the vertices in the edge are stored in the same order
// that you would encounter them if you were walking clockwise
// around the polygon. That means the pair of edge vertices
// will be:
// [1st inner poly vertex, 2nd inner poly vertex] or
// [2nd inner poly vertex, 3rd inner poly vertex] or
// [3rd inner poly vertex, 1st inner poly vertex]
//
// The formula above will give us [1st inner poly vertex,
// 3rd inner poly vertex] though, so we check for that
// situation and reverse the vertices. if(m_InnerVerts[0] == inner_poly.m_Vertices[0] &&
m_InnerVerts[1] == inner_poly.m_Vertices[2])
{
int temp = m_InnerVerts[0];
m_InnerVerts[0] = m_InnerVerts[1];
m_InnerVerts[1] = temp;
} // No manipulations have happened yet, so the outer and
// inner Polygons still share the same vertices.
// We can instantiate m_OuterVerts as a copy of m_InnerVerts.
m_OuterVerts = new List<int>(m_InnerVerts);
}
}
And while we’re at it, let’s create a helper class called EdgeSet. This will a set of unique Edges, so we’ll use HashSet<Edge>, with a few extra convenience functions just for us:
public class EdgeSet : HashSet<Edge>
{
// Split - Given a list of original vertex indices and a list of
// replacements, update m_InnerVerts to use the new replacement
// vertices. public void Split(List<int> oldVertices, List<int> newVertices)
{
foreach(Edge edge in this)
{
for(int i = 0; i < 2; i++)
{
edge.m_InnerVerts[i] = newVertices[ oldVertices.IndexOf(
edge.m_OuterVerts[i])];
}
}
} // GetUniqueVertices - Get a list of all the vertices referenced
// in this edge loop, with no duplicates. public List<int> GetUniqueVertices()
{
List<int> vertices = new List<int>();
foreach (Edge edge in this)
{
foreach (int vert in edge.m_OuterVerts)
{
if (!vertices.Contains(vert))
vertices.Add(vert);
}
}
return vertices;
}
}
Now let’s do the same thing for Polygons by making a helper class called PolySet — to handle operations that we’ll need to do on a groups of polys. We’ll add a function to generate an EdgeSet out of the Edges that surround a PolySet, and a function to give us a list of the vertices used by Polygons in the Set (with no duplicates):
public class PolySet : HashSet<Polygon>
{
//Given a set of Polys, calculate the set of Edges
//that surround them. public EdgeSet CreateEdgeSet()
{
EdgeSet edgeSet = new EdgeSet();
foreach (Polygon poly in this)
{
foreach (Polygon neighbor in poly.m_Neighbors)
{
if (this.Contains(neighbor))
continue;
// If our neighbor isn't in our PolySet, then
// the edge between us and our neighbor is one
// of the edges of this PolySet. Edge edge = new Edge(poly, neighbor);
edgeSet.Add(edge);
}
}
return edgeSet;
} // GetUniqueVertices calculates a list of the vertex indices
// used by these Polygons with no duplicates. public List<int> GetUniqueVertices()
{
List<int> verts = new List<int>();
foreach (Polygon poly in this)
{
foreach (int vert in poly.m_Vertices)
{
if (!verts.Contains(vert))
verts.Add(vert);
}
}
return verts;
}
}
…And we’ll need to add one more function to the Planet class: A method that takes a list of vertices, and creates new vertices with the same positions. This is the first step in splitting a set of Polygons away from their neighbors. The Polys inside the set will be given the new cloned vertices, while their neighbors outside the set will keep the old ones.
public class Planet
{
.... public List<int> CloneVertices(List<int> old_verts)
{
List<int> new_verts = new List<int>(); foreach(int old_vert in old_verts)
{
Vector3 cloned_vert = m_Vertices [old_vert];
new_verts.Add(m_Vertices.Count);
m_Vertices.Add(cloned_vert);
}
return new_verts;
}
}
With that done, we now have enough to write the function that will take a group of polygons and separate them from their neighbors, then ‘stitch’ a row row of newly created polygons to fill in the seam.
public class Planet
{
.... public PolySet StitchPolys(PolySet polys)
{
PolySet stichedPolys = new PolySet(); var edgeSet = polys.CreateEdgeSet(); var originalVerts = edgeSet.GetUniqueVertices(); var newVerts = CloneVertices(originalVerts); edgeSet.Split(originalVerts, newVerts); foreach (Edge edge in edgeSet)
{
// Create new polys along the stitched edge. These
// will connect the original poly to its former
// neighbor. var stitch_poly1 = new Polygon(edge.m_OuterVerts[0],
edge.m_OuterVerts[1],
edge.m_InnerVerts[0]); var stitch_poly2 = new Polygon(edge.m_OuterVerts[1],
edge.m_InnerVerts[1],
edge.m_InnerVerts[0]); // Add the new stitched faces as neighbors to
// the original Polys. edge.m_InnerPoly.ReplaceNeighbor(edge.m_OuterPoly,
stitch_poly2); edge.m_OuterPoly.ReplaceNeighbor(edge.m_InnerPoly,
stitch_poly1); m_Polygons.Add(stitch_poly1);
m_Polygons.Add(stitch_poly2); stichedPolys.Add(stitch_poly1);
stichedPolys.Add(stitch_poly2);
} //Swap to the new vertices on the inner polys.
foreach (Polygon poly in polys)
{
for (int i = 0; i < 3; i++)
{
int vert_id = poly.m_Vertices[i];
if (!originalVerts.Contains(vert_id))
continue;
int vert_index = originalVerts.IndexOf(vert_id);
poly.m_Vertices[i] = newVerts[vert_index];
}
}
return stichedPolys;
}
}
Step 2 — Extruding
If we call the StitchEdges() function on our planet now, we wouldn’t see any visible changes. One set of polygons has been disconnected from another, in theory, but in practice they’re still located at the same place we left them. So let’s create a function to take a PolySet and push it outwards from the planet’s core:
public class Planet
{
.... public PolySet Extrude(PolySet polys, float height)
{
PolySet stitchedPolys = StitchPolys(polys);
List<int> verts = polys.GetUniqueVertices(); // Take each vertex in this list of polys, and push it
// away from the center of the Planet by the height
// parameter. foreach (int vert in verts)
{
Vector3 v = m_Vertices[vert];
v = v.normalized * (v.magnitude + height);
m_Vertices[vert] = v;
}
return stitchedPolys;
}
}
Step 3 — Insetting
To create multiple layers of hills, it’s handy to be able to pull groups of Polys inward towards each other, then extrude them again. So let’s also add a simple Inset() function to pull the vertices of a group of Polys together:
public class Planet
{
.... public PolySet Inset(PolySet polys, float interpolation)
{
PolySet stitchedPolys = StitchPolys(polys);
List<int> verts = polys.GetUniqueVertices(); //Calculate the average center of all the vertices
//in these Polygons. Vector3 center = Vector3.zero;
foreach (int vert in verts)
center += m_Vertices[vert];
center /= verts.Count; // Pull each vertex towards the center, then correct
// it's height so that it's as far from the center of
// the planet as it was before. foreach (int vert in verts)
{
Vector3 v = m_Vertices[vert];
float height = v.magnitude;
v = Vector3.Lerp(v, center, interpolation);
v = v.normalized * height;
m_Vertices[vert] = v;
}
return stitchedPolys;
}
}
My apologies for making this a very code-intensive tutorial, but we’re almost done. We just need a function to grab a set of polygons from inside a random sphere, and we’ll have everything we need to extrude landforms on our tiny planet:
public class Planet
{
....
public PolySet GetPolysInSphere(Vector3 center,
float radius,
IEnumerable<Polygon> source)
{
PolySet newSet = new PolySet();
foreach(Polygon p in source)
{
foreach(int vertexIndex in p.m_Vertices)
{
float distanceToSphere = Vector3.Distance(center,
m_Vertices[vertexIndex]);
if (distanceToSphere <= radius)
{
newSet.Add(p);
break;
}
}
}
return newSet;
}
}And that’s it! By calling GetPolysInSphere() with randomly generated spheres, then calling Extrude() on the results, we get a tiny planet complete with oceans, plains, and hills:
In the next few tutorials I’ll talk more about artistic questions, like how to choose different sets of polygons to achieve different effects, how to create translucent oceans, and how to add an efficient form of ambient occlusion to your planets. Speaking of which, you can find Tutorial 3 here!
If you didn’t grab it already, a working Unity demo of this tutorial is available here. And you can see a demo of this kind of planet generation tech being used in an actual game right over here.
Thanks for reading, and good luck creating worlds!