Journey to Procedural Planets in Unreal Engine 5

At the end of the last post, we left off with a single triangle. Everyone loves a good David vs. Goliath story, but our little triangle alone does not make for good terrain. Therefore, we must go deeper...to the grid!

It's all about the grid, man.

At this point in the journey, I was getting a little nervous as the process ahead was clear, but still intimidating. We've got a triangle and now we need a full quad. That's very simple - you add 1 more entry into your vertice array, 1 entry into the UV array and 3 more entries into your triangle indice array. That looks like this.

At this point, it's pretty clear that we can't simply keep manually adding entries here if we want to progress in a reasonable manner (preferably in our lifetime). So we need a formula or algorithm to help us sort all of this data out for us. Luckily, generating a grid of points is not terribly difficult to do.

Let's start off very simple in blueprints, shall we. I'm assuming some prerequisite knowledge of blueprints, loops, etc, so if you're not there yet, feel free to bookmark this and come back when you're ready.

We're generating a rectangle here, so we need to generate N amount of points in two directions, so how do we do that? Well, if we simply loop over a single direction, we will only get a single row or column of points in that direction, meaning we need to loop over both.

Let's take a look at what these nasty nested BP loops will look like when generating a simple grid, and then break it down.

Even though this is a simple setup, it can be confusing to understand what's going on. I'll do my best to explain it simply.

We need to place items into rows and columns, and to do that, we're going to user outer/inner loops:
An outer loop for the rows (each time this loop runs, it creates a new row).
An inner loop for the columns (this runs for each item in a row).

The outer loop starts a new row: Each time the outer loop executes, it moves to the next row. This is like saying, "Okay, row 1 is done; let's move down to row 2."
The inner loop fills each row: Inside each row, the inner loop places objects (tiles) one by one across the row, like placing one tile after another from left to right.

How It All Comes Together:

Imagine you want a 3x5 grid (3 rows, 5 columns).
The outer loop runs 3 times, once for each row.
For each row, the inner loop runs 5 times, placing 5 items across the row.
By the end, you have 3 rows, each with 5 items, forming a 3x5 grid.

Row 1: [x] [x] [x] [x] [x]
Row 2: [x] [x] [x] [x] [x]
Row 3: [x] [x] [x] [x] [x]

Still with me? If not, that's okay; recreate the blueprint above and play with the variables to help visualize what's going on.

The next part to break down is the spacing of the items, which works based off the inner/outer loop index and a spacing variable.

When creating a grid, each item needs a specific location to avoid overlapping with the previous one. This is where index multiplied by spacing comes in. It’s a straightforward formula that lets us place each item at a consistent distance from the others.

It's easy to imagine the index as the item’s “position number” within a row or column. In the first row, the first item has an index of 0, the second item has an index of 1, and so on. The index tells us where each item is within the grid. The idea here is that we want our items a set distance apart, hence the spacing variable, which we can combine with the loop index to do just that.

Imagine spacing is 100 units, and you have 3 items in a row:

Item 1 (index 0): 0 * 100 = 0
Item 2 (index 1): 1 * 100 = 100
Item 3 (index 2): 2 * 100 = 200

The items are placed at [0, 100, 200] along the row. This keeps everything evenly spaced, making the grid look clean and organized, assuming a single spacing variable is used. This works in both axes, which is how we generate the whole grid.

Here is what that looks like in practice:

Phew, that was a lot of word salad right there. I would apologize, but it's only going to get more complicated from here on out. Now, some of you may realize that this setup has an issue. I'll give you a minute if you didn't realize what it was...

If you said "with every increase of rows/columns/spacing, the overall size of the grid changes with the resolution of the grid ", you are correct in your assessment. This is a problem, and one that is easily fixed.

Theoretically, the setup will change from rows/columns/spacing to height/width/subdivisions, because we are moving to a subdivision based grid.

As you can see, little had to be changed to achieve the desired result. So what exactly changed and why does this work?

This is a simple algebra problem, basically - we are working with height and width, which makes this topic about area, and what can be confined within that area. Our goal here is to determine the spacing automatically. To do that, you simply divide height/width by our subdivision variable. Those results get set to GridX and GridY, which are placed where our spacing variable was before. That's it.

To summarize: Instead of letting the area grow with each new point, we're fitting all the points evenly within the existing area.

It is worth mentioning this calculation is ideal for generating the grid UVs - you simply output the results from the spacing formula to Make Vector 2D instead and add that to your UV array. If you want, you can add a variable called UV Scale and multiply the spacing result by it before adding it to the array.

If you've made it this far without wanting to give up, congratulations - you're in for a bumpy ride.

Connecting the dots

The basic grid setup is complete, but we have not yet solved generating the proper order of the triangle indices.

Before we go further, I'd like to explain that I've been working on this article for awhile, and the hold up has primarily been trying to effectively demonstrate the problems/solutions in an easy to understand manner, while also providing the code/blueprint for those wanting to follow along. However, blueprint loops are notoriously bad performance wise, which is due to a large number of factors: blueprint VM overhead, for-loop performance disparity due to a questionable macro design, PIE vs Standalone, etc etc. There's a lot of information out there about this topic, so please do some research on the matter if you are interested. I would include more, but this article is already much longer than I'd like.

In my experience, if there are going to be loop heavy calculations, especially nested loops like we are doing, then that is 100% going to be turned into a C++ node that I will expose to blueprints via a function library or subsystem, depending on the use case. As such, from here on out, these articles will heavily feature C++ based development, and blueprints where they make sense.

With that out of the way, let's continue. I'd like to convert the grid loop section to a single C++ node that will give us our vertex/UV0/triangle indice data. Let's start with the vertices and uvs - it's the same as it was in blueprints, only far more readable.

        // Spacing between vertices
	const float GridX = XSpacing/Resolution; 
	const float GridY = YSpacing/Resolution;

	for(int32 y = 0; y<Resolution+1; y++)
	{
		for(int32 x = 0; x<Resolution+1; x++)
		{
		   Vertices.Emplace(FVector(x*GridX, y*GridY, 0)); // Add vertices
		   UVs.Emplace(FVector2D((GridX * x) * UVScale, (GridY * y) * UVScale)); // Add UVs
		}
	}

I know it's possible to convert this to a flattened loop to avoid a nested loop, but I'm not looking to delve into that for this article. Plus, it likely would not help as flattened or nested, this setup results in O(n^2). Might as well be able to easily read the code.

It's important to keep in mind that if our outer loop is Y and the inner loop is X, our vertices will be created from the bottom left corner and progress vertically until it hits the edge, then it will go to the next row and repeat. If you want them to be placed left to right starting from the bottom left corner, simply place X in the outer loop and Y in the inner. However, this will necessitate a change in the upcoming triangle loop. More on that when we get there.

Now, we're onto the triangle indices. If you remember in the first blog post, I mentioned we have to build our indices in a CCW manner. To do this for all our triangles, we're going to again use nested loops with a bit of indexing math. I'm going to post the whole snippet and then break down each line.

        // Create triangles
	for(int32 Row = 0; Row<Resolution; Row++){
		for(int32 Column = 0; Column<Resolution; Column++)
		{
		   int32 i = (Row*Resolution) + Row + Column; // Calculates the index of the bottom-left vertex of each "cell". Converting the 2D array to 1D.

		   // First triangle (bottom-left corner of the square)
		   Triangles.Emplace(i);
		   Triangles.Emplace(i+Resolution+1);
		   Triangles.Emplace(i+1);
 
		   // Second triangle (top-right corner of the square)
		   Triangles.Emplace(i+1);
		   Triangles.Emplace(i+Resolution+1);
		   Triangles.Emplace(i+Resolution + 2);
		}
	}

For the first two lines, we are creating our row/column loop. We aren't doing what we did in the vertex loops, which is Resolution+1 for the condition, and that's due to how our grid is formed.

In the vertices loop, we need an extra vertex at the end of each row and column. This is because each "cell" in the grid requires vertices at its four corners. So, if our grid resolution is 10, for example, we'll need 11 vertices across and 11 down to cover the full grid with vertices around each cell.

For triangles, we're forming cells between the vertices. Each cell is defined by four corner vertices, which allows us to form two triangles per cell. Here, we only need rows and columns of cells.

Line 5 is where we encounter our first bit of complexity - the index formula. If there are any CS majors reading this, you'll recognize it as a modified 2D-1D index conversion, with a slight modification due to that extra vertex. We're doing this because our grid of vertices can be thought of as a 2D array.

What this formula allows us to do is to traverse our cells via the row/column values from the loops (think plotting X & Y values on a grid like you did in early school years), and then provide indices that the mesh data will use alongside the vertices to actually build the mesh surface. I can already hear you asking "How does this formula help, though?"

The term (Row * Resolution) + Row calculates the starting index for each row, essentially "jumping" down to the start of the current row.

Adding Column to this result advances the index horizontally within that row, meaning you’re accessing elements in a left-to-right fashion within each row.

If we simply utilized the standard 2D-1D conversion ((Row * Resolution) + Column), we would have issues when building out our triangles:

You don't have to fully understand this now, and we'll build a simple visualizer for it later, so if you don't quite get it now, that's alright.

Okay, so what do the lines that have Emplace do? Well, they are taking the current cell we are in, and setting indices in a CCW manner for the vertices to use for mesh generation. Our quads are comprised of two triangles: bottom left and top right. Let's start with the bottom left triangle.

Line 8 - (i) - this will get the bottom left indice. Any addition to it is simply moving up or to the right/left depending on which triangle you're building.
Line 9 - (i + Resolution + 1) - this will get the bottom right indice. Note it is shared with the top right triangle.
Line 10 - (i + 1) - this will get the top left indice. This is also shared with the top right triangle.

Now for the top right triangle.

Line 13 - Same as Line 10.
Line 14 - Same as Line 9.
Line 15 - (i + Resolution + 2) - this will get you the top right indice.

That's it for building the triangle indices! Congrats, you've made it. All you have to do is hook up your vertices/triangles/UV0 arrays into Create Mesh Section and you'll have a fully procedural grid mesh. There are however a few little extra (but optional) things to consider.

If you remember what I mentioned previously about your vertice loops dictating how our triangles need to be constructed, it's this part specifically that requires an alteration due to needing the indices to be CCW. If you're using X as the outer and Y as the inner for the vertice loops (our original versions used Y and X), you will need to swap the last two entries for each side of the quad. For example, swap lines 9 & 10 and then swap lines 14 & 15.

Additionally, depending on how your triangle loops are setup in regards to row/column being the outer/inner, you can also change the first part of the indexing formula from (row * resolution) to (column * resolution) to ensure that your triangle faces are generated from left to right. This doesn't matter much, but if you're wanting consistency in relation to vertice/triangle generation, this part is for you. An example of left to right vertices and triangle faces can be seen here:

Now I know this is a lot to take in, which is why I built a simple function to help visualize what's happening. The function takes in values for the rows and columns, as well as a bool to choose a triangle, and then outputs the vertices from those indices.

        int32 i = (Row * GridResolution) + Row + Column;

	// If we're looking for the first triangle in the cell (bottom-left)
	if(bTriangleOne)
	{
	  // Bottom-left vertex
	  OutTriangleVertices.Emplace(Vertices[i]);
	  // Top-left vertex
	  OutTriangleVertices.Emplace(Vertices[i + GridResolution + 1]);
	  // Bottom-right vertex
	  OutTriangleVertices.Emplace(Vertices[i + 1]);
	}
	else  
        // If we're looking for the second triangle in the cell (top-right)
	{
	  // Bottom-right vertex
	  OutTriangleVertices.Emplace(Vertices[i + 1]);
	  // Top-left vertex
	  OutTriangleVertices.Emplace(Vertices[i + GridResolution + 1]);
	  // Top-right vertex
	  OutTriangleVertices.Emplace(Vertices[i + GridResolution + 2]);
	}

Since I expose these as nodes to blueprint, here's what that setup looks like when passing our vertex array in.

Here's what this looks like in practice:

You can see that for each cell, the vertex index parameter will move the sphere in a CCW manner for each half of the quad.

And here is an example of the triangle faces being generated from left to right when using the left-right code setup:

Wrapping Up

This write up was very dense, and admittedly could have used some more illustrations for the triangle indice setup - but I am a code based technical artist who cannot use other illustrative programs if my life depended on it. With that said, hopefully the simple visualizer will assist in understanding the cell selection and how the indexing formula relates to triangles/vertices/mesh generation.

The next write up will be about the importance of developing such tools when working with complex structures and features, as they can be paramount to your understanding of the task at hand, as well as helping to identify problems as they arise. After that, we'll get into switching from Procedural Mesh Component to Realtime Mesh Component and the more fun part of generating a procedural mesh: using noise to generate terrain.

Search This Blog

Unreal Engine Tech Art & Programming