Introduction
In this first part of a procedural runtime planet generator/renderer, we will take a look how to generate meshes using the Unity job system. The mesh will represent a terrain with heights based on random noise. We will also decimate the mesh to make it easier to render. To keep the performance impact low and enable the generation to run at runtime, everything will be done using a chain of burst-compiled jobs. This allows the terrain to be generated while playing, so you can use it for infinite worlds or anything that needs terrain to be generated at runtime.
In the next part of this series, we will use a quadtree to dynamically split and merge the terrain based on the players position, allowing for far bigger worlds to be explored at runtime (coming soon).
The third part will explore how to warp the terrain into a spherical shape, so we can have planetery terrains with adaptive details (coming soon).
Shameless self-advertising: The mechanics mentioned in this tutorial, together with a ton of additional features, are all included in my DOTS Terrain generation tool Orbis: https://assetstore.unity.com/packages/tools/terrain/orbis-dots-terrains-197551. Feel free to check it out on the asset store.
Goal:
At the end of this tutorial, we will have set up a chain of jobs that will generate a random terrain chunk, with minimal impact on performance. The terrain mesh will be based on a grid of points, with points in "flat" regions being removed from the mesh. The result should look something like this:
The base of the terrain is formed by a square of points, forming a grid with a specified resultion. These points are processed using a job chain consisting of 4 jobs:
- Height Sampling Job: The first job samples and stores a height for each point in the terrain grid. This tutorial uses simplex noise to sample the heights, but you could also use a heightmap or some other function to provide the heights.
- Normals Pass: The second job utilizes the heights stored by the first job, and calculates the normal for each point in the terrain grid, based on the heights of the point itself and the heights of the 4 points surround it. If the heights are on a common plane (or close enough to it), we mark that points as candidate that will be skipped later. This allows us to reduce the detail in flat regions, while still keeping a high resulution where it matters. All non-skipped points together with their normals are stored to a new list.
- Triangulation: In the third job, we now try to triangulate the grid. Since we removed an arbitrary amount of points in the second job, the grid now has "holes" in it, which makes triangulating it a lot harder. To allow this to be performed fast, we split the grid into multiple patches, and use the Bowyer-Watson algorithm to compute a Delaunay Triangulation of the patch. The triangles of each patch are added to a global triangle list.
- Meshing Job: At last, the actual unity 'mesh' can be created. To do so, we utility the new MeshData API, which allows us to create meshes from the job system. We allocate the mesh's indices and vertex arrays from inside a job, and populate it using the positions, normals and triangles we computed in the previous jobs.
Setup:
In this tutorial we'll start from a blank unity project, but you can also try this in an existing project. Any unity version that supports the job system should be fine. I'm using 2020.3 and can verify that things are working there. If you are getting unity errors from the packages or unable to install them, maybe try switching to a more recent version.
Required packages:
Some of the features used in this project are using features from preview packages. To enable installation of preview packages, enable project settings -> package manager -> "Enable Preview Packages". In the package manager, add the following packages:
- Collections (com.unity.collections: "1.2.3-pre.1")
- Jobs (com.unity.jobs: "0.5.0-preview.14")
- Burst (com.unity.burst: "1.7.0")
If you can not add the packages using the package search for the unity registry, try using the 'Add package from git url) found at the '+' button on the top left.
The versions listed are are not specifically required, you should also be able to use other versions.
Project Setup:
In later parts of this tutorial we'll be doing some (very basic) pointer magic and unsafe memory allocations. To allow this. it is required to enable unsafe code. This can be done in Project Settings -> Player -> Other Settings -> 'Allow unsafe code'. I also recommend setting the scripting backend to IL2CPP, although this is not required.
Getting Started
Create a new scene, and add a new, empty gameobject to it. Create and attach a new script to it. This script will be used to generate our terrains. To allow us to test our generation code directly in the editor without having to enter playmode, we'll perform all our main work from a separate function in this script. This function will be called everytime we change a property of this script. We'll call this component 'MeshGenerator'.
We'll start with an empty function, which we call from the 'onvalidate' event:
// class MeshGenerator.cs
// used as a dummy to trigger the generation from the editor
public bool reload;
private void OnValidate() {
GenerateMesh();
if (reload) {
reload = false;
}
}
private void GenerateMesh() {
Debug.Log("This will generate our terrain");
// TODO
}Height Sampling
Now, it is time to get started with the first part of our job chain: The height sampler. Here, we operate on a grid of points. At each point we execute a height sampling function. The easiest way to get heights for our terrain will be by sampling simplex noise at each point.
In the picture here, i'll try to show what we're trying to accomplish in this job:
The grid size, which represents the amount of detail we have, should also be configurable from the editor. To do so, create a new struct to store our grid settings:
[Serializable]
public struct GridSettings {
public ushort Count;
}The [Serializable] attribute allows our custom struct to be editable in the unity inspector, when assigned to a GameObject.
Add the new GridSettings struct as a field to our MeshGenerator component, and we should be able to set the count parameter in the inspector.
Next, we create the HeightSampler job itself. This is done by implementing the IJob interface in our job struct. We need a NativeArray to store the heights of each points as output, and the GridSettings defined before as input.
If the Job System, together with the WriteOnly & ReadOnly annotations and NativeContainers are new to you, i recommend youcheck out the Unity C# Job System first before continuing with this tutorial.
public struct HeightSampler : IJob {
[WriteOnly] public NativeArray<half> heights;
public GridSettings gridSettings;
public void Execute() {
var index = 0;
for (int x = 0; x < gridSettings.Count; x++) {
for (int y = 0; y < gridSettings.Count; y++) {
var point = new float2(x, y);
// divide point by 8 to reduce the noise scale
// we'll replace this later with a proper variable
var height = noise.snoise(point / 8);
heights[index] = (half) height;
index++;
}
}
}
}In this job, we basically just iterate over each point in the grid, construct a coordinate for it (the int2 point), and sample a height at that point.
Note that we are not using Vector2's or the unity standard math library. Instead we're using the vectors from the new Unity.Mathematics library, which is optimized for burst-compiled jobs. This provides us with the int2, int3, float2 and float3 structs. It also contains the noise functions we're using here to sample the heights for the points.
The job now needs to be scheduled from the MeshGenerator. Inside our GenerateMesh() method, create a new NativeArray for the samples heights. This array is then scheduled to our job instance. I've also added a timer so we can measure the job's performance. The code should look something like this:
var timer = new Stopwatch();
timer.Start();
var pointCountInitial = settings.Count * settings.Count;
var heights = new NativeArray<half>(pointCountInitial, Allocator.TempJob);
// wrap anything that could fail in a try block
// this way we can ensure to dispose the previously allocated memory again
try {
var job = new HeightSampler {
gridSettings = settings,
heights = heights
};
job.Run();
}
finally {
heights.Dispose();
}
timer.Stop();
Debug.Log("job took " + timer.ElapsedMilliseconds + " ms or " + timer.ElapsedTicks + " ticks");We can now test our new job in the editor. Clicking 'reload' or changing any of the parameters should cause the job to run. Of course, the only indication that something happened is that we get a message in the log.
Point Visualization
Let's fix that by drawing the points we just generated. To do so, i'll be using the OnDrawGizmosSelected() event function to draw the gizmos. The points are cached in a field of the class, so we can reference it anytime. Your MeshGenerator class should now have 2 more methods, one to store the generated points in a List, and one that draw's the points as gizmos:
private List<float3> cachedPoints = new List<float3>();
private void OnValidate() {
GenerateMesh();
if (reload) {
reload = false;
}
}
private void GenerateMesh() {
var timer = new Stopwatch();
timer.Start();
var pointCountInitial = settings.Count * settings.Count;
var heights = new NativeArray<half>(pointCountInitial, Allocator.TempJob);
// wrap anything that could fail in a try block
// this way we can ensure to dispose the previously allocated memory again
try {
var job = new HeightSampler {
gridSettings = settings,
heights = heights
};
job.Run();
timer.Stop();
Debug.Log("job took " + timer.ElapsedMilliseconds + " ms or " + timer.ElapsedTicks + " ticks");
StoreGeneratedPoints(in heights, in settings);
}
finally {
heights.Dispose();
}
}
private void StoreGeneratedPoints(in NativeArray<half> heights, in GridSettings gridSettings) {
var index = 0;
cachedPoints.Clear();
for (int x = 0; x < gridSettings.Count; x++) {
for (int y = 0; y < gridSettings.Count; y++) {
var heightAt = heights[index];
var point = new float3(x, heightAt, y);
index++;
cachedPoints.Add(point);
}
}
}
private void OnDrawGizmosSelected() {
Gizmos.color = Color.yellow;
foreach (var point in cachedPoints) {
Gizmos.DrawSphere(point, 0.1f);
}
}Using a count of 32 for the GridSettings, we should now get a nice grid of points with some random height values:
However, you'll notice that as you increase the grid size, the job takes longer and longer. At small grid sizes like 32 with a simple height function, this is no issue. But as we add more complex height sampling functions, such as multi-layered noise or heights map into the map, we'll run into trouble. Also, increasing the grid count massivly increases the generation time:
Count 32: job took 1 ms or 18859 ticks for 1024 points
Count 128: job took 31 ms or 314715 ticks for 16384 points
Count 512: job took 491 ms or 4918620 ticks for 262144 pointsWhile this slow generation would be okay in the editor to be run once, it's definitly something that could be improved. Currently, we are only using the main thread, and process every point in sequence.
Optimization
Since we have no dependencies between points, we can process each point on its own. To do so and spread the work on all available cores, an IJobParallelFor can be used instead of the IJob we're using currently. A "parallel for" job basically replaces the for-loops we had before and executes the loop body in parallel for us. We'll also add the [BurstCompile] attribute to the job, which should gives us another massive speedup by allowing the job to be burst compiled.
Because ParallelFor jobs represent only a single loop, we'll have to pack both the x and y coordinates into a single loop, and then reconstruct the point coordinates from the loop's index. To do so, we need a simple helper class with provides some utility methods:
public static class LinearArrayHelper {
public static int GetLinearIndex(int x, int y, int count) {
return y + x * count;
}
public static int GetLinearIndex(int2 pos, int count) {
return pos.y + pos.x * count;
}
public static int GetLinearIndexSafe(int x, int y, int count) {
x = math.clamp(x, 0, count - 1);
y = math.clamp(y, 0, count - 1);
return y + x * count;
}
public static int2 ReverseLinearIndex(int index, int count) {
var y = index % count;
var x = index / count;
return new int2(x, y);
}
}We can use the new method ReverseLinearIndex(args) to convert from our single-dimensional ParallelFor loop to the point coordinates we used before.
Switching our HeightSampler to an IJobParallelFor instead of an IJob and using the new utility methods above leads to the following code:
[BurstCompile]
public struct HeightSampler : IJobParallelFor {
[WriteOnly] public NativeArray<half> heights;
public GridSettings gridSettings;
public void Execute(int index) {
var coordinates = LinearArrayHelper.ReverseLinearIndex(index, gridSettings.Count);
var x = coordinates.x;
var y = coordinates.y;
var localPosition = new float2(x, y);
var heightSample = noise.snoise(localPosition / 8);
heights[index] = (half) heightSample;
}
}Now, in our MeshGenerator we also need to correctly utilize this new job type. Replace the old .Run() call with a Schedule(int length, int batchSize) call:
var job = new HeightSampler {
gridSettings = settings,
heights = heights
};
var jobHandle = job.Schedule(pointCountInitial, settings.Count);
jobHandle.Complete();We're using settings.count as batch size here. This means that it'll process this amount of points inside a single job.
Testing the new changes in the editor, we should see a massive performance improvement (make sure you have Jobs->"Use Job Threads" and Jobs->Burst->"Enable Compilation" both enabled for best results)
Count 32: job took 0 ms or 567 ticks for 1024 points
Count 128: job took 0 ms or 1376 ticks for 16384 points
Count 512: job took 1 ms or 14893 ticks for 262144 pointsWow, that's a major speedup. Using a grid size of 512, we have a speedup of 330x (4918620 vs 14893 cpu ticks). Entering the debug view, we can also see that we're now properly utilizing all CPU cores.
We still get a major lag when generating high amounts of points. This is caused by the Gizmos.DrawSphere() calls, as it is not intended to be used to draw hundreds of thousands of spheres. We'll address this issue later by using an actual mesh which we generate from jobs.
Normals Pass
Next, we'll create a second job which depends on our first job. Here, we calculate the normals for the points, and based on the normals select which points we will not require anymore as they don't provide enough additional detail to the mesh.
To do so, another IJobParalleFor which operates on every point is required again. We need the previously generated height array as input, and then calculate the normal for every point. To calculate accurate normals, we get the calculated height for the point itself, and also for the 4 points surrounding the point. Using the cross product, we compute a normal based on the top-left triangle, and the bottom-right triangle. The point normal is the result of combining those both normals. We could also sample the normal based on the points on one triangle, but that would be less accurate. Also, those 2 normals will be used to check if the point can be removed or not. If they are not similar, it means the 5 points are not on a common plane or close enough to it. Here is a sketch showing what we're trying to do:
To avoid deleting every triangle in a consecutive area, i'll introduce a Core Grid parameter to our grid settings. This will be used to avoid points that are inside the core grid being deleted. We also need a new parameter to decide at what threshold to delete points, a height scale to apply to the points, and for convenience also a parameter to affect the scale of the grid (the spacing between points). Implementing all this, our GridSettings now look like this:
[Serializable]
public struct GridSettings {
public ushort Count;
public float Distance;
public float NormalReduceThreshold;
public float HeightScale;
public ushort CoreGridSpacing;
}We also need a struct to contain data for vertices that we're generating in this job (containing a point's position and normal):
[System.Runtime.InteropServices.StructLayout(System.Runtime.InteropServices.LayoutKind.Sequential)]
public struct VertexData {
public float3 Position;
public float3 Normal;
public override string ToString() {
return $"{nameof(Normal)}: {Normal}";
}
}The System.Runtime.InteropServices.StructLayout(System.Runtime.InteropServices.LayoutKind.Sequential) will be required later on so we can directly use this struct as input for the MeshData API. It describes how the struct will be laid out in memory.
In our job, we need to get the index of each adjacent point, and calculate two sets of normals. Also, each point is checked if it is a core grid point or is on the edge of the mesh. If either is true, we avoid deleting the point, no matter the normal data.
The two normals are calculated based on the cross-product of the adjacent points, and if the angle between the two normals is greated than our defined threshold, we dont add the point to our vertices list.
Because we're using a parallel job, we don't know the order in which the vertices are added to the list, as they are added in parallel. So, we need another hashmap to store our index references based on the grid position. The job system allows us to write to NativeContainers in parallel by using their parallelWriter variants. However, the default NativeList<T>.parallelWriter AddNoResize() method does not return the index at which we just added the element. We can also not retreive it using the length method, as other threads might have added to the list before we can call '.length'. So, we need a new unsafe method that adds to the list and also return the index at which we've just added. To do so, we'll create a new UnsafeListHelper utility class:
public static class UnsafeListHelper {
public static unsafe int AddWithIndex<T>(ref NativeList<T>.ParallelWriter list, in T element) where T : unmanaged {
var listData = list.ListData;
var idx = Interlocked.Increment(ref listData->m_length) - 1;
UnsafeUtility.WriteArrayElement(listData->Ptr, idx, element);
return idx;
}
public static unsafe void Add<T>(ref NativeList<T>.ParallelWriter list, in T element) where T : unmanaged {
var listData = list.ListData;
var idx = Interlocked.Increment(ref listData->m_length) - 1;
UnsafeUtility.WriteArrayElement(listData->Ptr, idx, element);
}
}The AddWithIndex method works by getting a reference to the internal UnsafeList and using it's pointer. Then, we atomically increment the list length, and write the element to the new index. Then, we also return that index.
Putting it all together, we get the Normals pass jobs:
[BurstCompile]
public struct NormalPassJob : IJobParallelFor {
[ReadOnly] public NativeArray<half> heights;
public GridSettings settings;
[WriteOnly] public NativeList<VertexData>.ParallelWriter vertices;
[WriteOnly] public NativeHashMap<int2, int>.ParallelWriter pointToVertexReferences;
public void Execute(int index) {
var revIndex = LinearArrayHelper.ReverseLinearIndex(index, settings.Count);
var x = revIndex.x;
var y = revIndex.y;
var isEdge = x == 0 || x == settings.Count - 1 || y == 0 || y == settings.Count - 1;
var ownHeight = heights[index];
var centerPos = new float3(0, ownHeight * settings.HeightScale, 0);
var sampleAIndex = LinearArrayHelper.GetLinearIndexSafe(x - 1, y, settings.Count);
var sampleA = heights[sampleAIndex] * settings.HeightScale;
var posA = new float3(-settings.Distance, sampleA, 0);
var sampleBIndex = LinearArrayHelper.GetLinearIndexSafe(x + 1, y, settings.Count);
var sampleB = heights[sampleBIndex] * settings.HeightScale;
var posB = new float3(settings.Distance, sampleB, 0);
var sampleCIndex = LinearArrayHelper.GetLinearIndexSafe(x, y - 1, settings.Count);
var sampleC = heights[sampleCIndex] * settings.HeightScale;
var posC = new float3(0, sampleC, -settings.Distance);
var sampleDIndex = LinearArrayHelper.GetLinearIndexSafe(x, y + 1, settings.Count);
var sampleD = heights[sampleDIndex] * settings.HeightScale;
var posD = new float3(0, sampleD, settings.Distance);
var normalA = math.cross(posC - centerPos, posA - centerPos);
var normalB = math.cross(posD - centerPos, posB - centerPos);
var normal = math.normalize(normalA + normalB);
var angle = Vector3.Angle(normalA, normalB);
var isCoreGridPoint = x % settings.CoreGridSpacing == 0 && y % settings.CoreGridSpacing == 0;
var skipPoint = !isEdge && !isCoreGridPoint && angle < settings.NormalReduceThreshold;
if (skipPoint) return;
var localPosition = new float3(x * settings.Distance, ownHeight * settings.HeightScale, y * settings.Distance);
var data = new VertexData {
Normal = normal,
Position = localPosition,
};
var idx = UnsafeListHelper.AddWithIndex(ref vertices, in data);
pointToVertexReferences.TryAdd(revIndex, idx);
}
}In our MeshGenerator we can now add the new job. The jobhandle of the height sampling job can be used as input, so the jobHandle.Complete() we had here before can be removed now. We first need to allocate some memory for the new output data of the job:
var vertices = new NativeList<NormalPassJob.VertexData>(pointCountInitial, Allocator.TempJob);
var pointToVertexRefs = new NativeHashMap<int2, int>(pointCountInitial, Allocator.TempJob);Remember to dispose the allocated containers at the end of the method, or you'll get memory leaks. Next, we create and schedule the new job:
var normalsHandle = new NormalPassJob {
settings = settings,
heights = heights,
vertices = vertices.AsParallelWriter(),
pointToVertexReferences = pointToVertexRefs.AsParallelWriter()
}.Schedule(pointCountInitial, settings.Count, jobHandle);
normalsHandle.Complete();To draw the new points and normals, the cachedPoints variable can be changed to store the VertexData structs instead:
private List<NormalPassJob.VertexData> cachedPoints = new List<NormalPassJob.VertexData>();Also update the methods to store and draw the points to the new data type, and draw the normal as line:
private void StoreGeneratedPoints(in NativeList<NormalPassJob.VertexData> vertices) {
cachedPoints.Clear();
foreach (var vertex in vertices) {
cachedPoints.Add(vertex);
}
}
private void OnDrawGizmosSelected() {
Gizmos.color = Color.green;
foreach (var cachedPoint in cachedPoints) {
Gizmos.DrawRay(cachedPoint.Position, cachedPoint.Normal);
}
}After assigning the new GridSettings in the editor, it should look like this (Count 32, Normal Reduce Threshold 0, Height Scale 1, Core Grid Spacing 4):
If we change the Normal Reduce Threshold to something higher, we can remove some of the points. For example, we can remove all points where the angle between both normals is less than 10:
That's already looking good. The normals are pointing in the right direction, the height of the points is correct and we have our Core Grid where points are blocked from removal. However, because we removed some of the points, triangulating the grid is less straightforward.
Triangulation
To achieve a proper, evenly spread out triangulation, we'll try to compute a Delaunay Triangulation. The algorithm to get there is the Bowyer-Watson algorithm. Make sure to check out how to algorithm works before continuing, as it would exceed the scope of the tutorial to explain how the algorithm works and how to implement it. There also is a more in-depth unity tutorial that goes into detail on how to implement it together with some additional optimizations. Feel free to check it out and implement it on theor's site here. In this tutorial we'll use a more crude version than the mentioned tutorial. Feel free to try and replace/optimize this version based on theor's.
Since the triangulation algorithm itself is locked to one core and does not allow any parallelization, we need to find a way to utilize all our cores, or the performance will be rather bad. Since we already have a defined grid where we know that a vertex exists at the edge, we'll split the triangulation into smaller jobs based on our Core Grid defined previously. Each 'cell' of the Core Grid will be triangulated individually. This makes the job a bit lighter on the algorithm, since the amount of vertices and triangles that have to be check is way smaller. Also, we can split it up into multiple threads, and process multiple cells in parallel.
Here is my basic, burst & job-compatible version of the Bowyer-Watson algorithm:
using System.Runtime.CompilerServices;
using Unity.Burst;
using Unity.Collections;
using Unity.Mathematics;
using Unity.Profiling;
[BurstCompile]
public static class SimpleBowyerWatson {
public static NativeList<Triangle> Delaunay(ref NativeList<int2> points, in int size,
ref ProfilerMarker invalidSearchMarker, ref ProfilerMarker edgeComputeMarker, ref ProfilerMarker holeTriangulationMarker) {
var triangles = new NativeList<Triangle>(points.Length * 2, Allocator.Temp);
var firstPoint = points[0];
var superTriangleA = new int2(size / 2, -3 * size) + firstPoint;
var superTriangleB = new int2(-3 * size,3 * size) + firstPoint;
var superTriangleC = new int2(3 * size, 3 * size) + firstPoint;
var superTriIndexStart = points.Length;
points.Add(superTriangleA);
points.Add(superTriangleB);
points.Add(superTriangleC);
var superTri = insertTriangle(ref triangles, new int3(superTriIndexStart, superTriIndexStart + 1, superTriIndexStart + 2), in points);
triangles.Add(superTri);
for (var pointIndex = 0; pointIndex < points.Length; pointIndex++) {
var point = points[pointIndex];
var badTris = new NativeList<int>(2, Allocator.Temp);
invalidSearchMarker.Begin();
// find bad triangles
for (var triIndex = triangles.Length - 1; triIndex >= 0; triIndex--) {
var triangle = triangles[triIndex];
var distSq = math.distancesq(triangle.Center, point);
var isInside = distSq < triangle.RadiusSq;
if (isInside) badTris.Add(triIndex);
}
invalidSearchMarker.End();
// int2 values are vertex positions (represents edges)
var polygon = new NativeHashSet<int2>(6, Allocator.Temp);
edgeComputeMarker.Begin();
// compute valid polygon
for (var badTriIterator = 0; badTriIterator < badTris.Length; badTriIterator++) {
var badTriIndex = badTris[badTriIterator];
var badTri = triangles[badTriIndex];
if (!isEdgeShared(badTri.EdgeA, badTriIndex, in badTris, in triangles)) polygon.Add(badTri.EdgeA);
if (!isEdgeShared(badTri.EdgeB, badTriIndex, in badTris, in triangles)) polygon.Add(badTri.EdgeB);
if (!isEdgeShared(badTri.EdgeC, badTriIndex, in badTris, in triangles)) polygon.Add(badTri.EdgeC);
}
edgeComputeMarker.End();
badTris.Sort();
// remove tris that overlap with the new point
for (int i = badTris.Length - 1; i >= 0; i--) {
var badTriIndex = badTris[i];
triangles.RemoveAtSwapBack(badTriIndex);
}
holeTriangulationMarker.Begin();
// triangulate new hole
using var polyIterator = polygon.ToNativeArray(Allocator.Temp).GetEnumerator();
while (polyIterator.MoveNext()) {
var edge = polyIterator.Current;
var newTriIndices = new int3(edge.x, edge.y, pointIndex);
var tri = insertTriangle(ref triangles, newTriIndices, in points);
if (!float.IsNaN(tri.RadiusSq)) triangles.Add(tri);
}
holeTriangulationMarker.End();
}
// clean up
// remove triangles from super triangle
var toRemove = new NativeList<int>(3, Allocator.Temp);
for (var i = 0; i < triangles.Length; i++) {
var triangle = triangles[i];
if (math.any(triangle.Indices == superTriIndexStart) || math.any(triangle.Indices == superTriIndexStart + 1) || math.any(triangle.Indices == superTriIndexStart + 2)) {
toRemove.Add(i);
}
}
toRemove.Sort();
for (int i = toRemove.Length - 1; i >= 0; i--) {
var removeIndex = toRemove[i];
triangles.RemoveAtSwapBack(removeIndex);
}
// remove vertices of super tri
// remove 3 times the same index, since the next item in the list is being moved "back"
points.RemoveRangeSwapBack(superTriIndexStart, 3);
return triangles;
}
private static bool isEdgeShared(in int2 edge, in int selfIndex, in NativeList<int> badTris, in NativeList<Triangle> triangles) {
for (var i = 0; i < badTris.Length; i++) {
var curBadTriIndex = badTris[i];
if (curBadTriIndex == selfIndex) continue;
var badTri = triangles[curBadTriIndex];
if (triangleContainsEdge(badTri, edge)) return true;
}
return false;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool triangleContainsEdge(in Triangle triangle, in int2 edge) {
return isCommonEdge(edge, triangle.EdgeA) || isCommonEdge(edge, triangle.EdgeB) || isCommonEdge(edge, triangle.EdgeC);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool isCommonEdge(in int2 edgeA, in int2 edgeB) {
return math.all(edgeA == edgeB) || edgeA.x == edgeB.y && edgeA.y == edgeB.x;
}
private static Triangle insertTriangle(ref NativeList<Triangle> list, in int3 indices, in NativeList<int2> points) {
var posA = points[indices.x];
var posB = points[indices.y];
var posC = points[indices.z];
var v1 = new float3(posA.x, 0, posA.y);
var v2 = new float3(posB.x, 0, posB.y);
var v3 = new float3(posC.x, 0, posC.y);
Geometry.CircumCircle(v1, v2, v3, out var center, out var radius);
var tri = new Triangle {Indices = indices, RadiusSq = radius * radius, Center = center.xz};
return tri;
}
public struct Triangle {
public int3 Indices;
internal float RadiusSq; //squared
internal float2 Center;
internal int2 EdgeA => new int2(Indices.xy);
internal int2 EdgeB => new int2(Indices.yz);
internal int2 EdgeC => new int2(Indices.zx);
}
}I moved some of the more complicated math functions out of the job itself. The CircumCircle method with some additional helper methods is added to a new static Geometry class:
public static class Geometry {
public static void InCenter(float2 p1, float2 p2, float2 p3, out float2 inCenter, out float inRadius) {
var a = math.distance(p1, p2);
var b = math.distance(p2, p3);
var c = math.distance(p3, p1);
var perimeter = (a + b + c);
var x = (a * p1.x + b * p2.x + c * p3.x) / perimeter;
var y = (a * p1.y + b * p2.y + c * p3.y) / perimeter;
inCenter = new float2(x, y);
var s = perimeter / 2;
var triangleArea = math.sqrt(s * (s - a) * (s - b) * (s - c));
inRadius = triangleArea / s;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void CircumCircle(float3 a, float3 b, float3 c, out float3 circleCenter, out float circleRadius) {
PerpendicularBisector(a, b - a, out var perpAbPos, out var perpAbDir);
PerpendicularBisector(a, c - a, out var perpAcPos, out var perpAcdir);
var tAb = Intersection(perpAbPos, perpAbPos + perpAbDir, perpAcPos, perpAcPos + perpAcdir);
circleCenter = perpAbPos + perpAbDir * tAb;
circleRadius = math.length(circleCenter - a);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void PerpendicularBisector(float3 pos, float3 dir, out float3 bisectorPos,
out float3 bisectorDir) {
var m = dir * .5f;
var cross = math.normalize(math.cross(math.normalize(dir), new float3(0, 1, 0)));
bisectorPos = pos + m;
bisectorDir = cross;
}
// http://paulbourke.net/geometry/pointlineplane/
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static float Intersection(float3 p1, float3 p2, float3 p3, float3 p4) {
var tAb = ((p4.x - p3.x) * (p1.z - p3.z) - (p4.z - p3.z) * (p1.x - p3.x)) /
((p4.z - p3.z) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.z - p1.z));
return tAb;
}
}In the triangulation job, we process one cell of the Core Grid at a time. In the job we collect all the non-skipped points inside the cell, and then get the triangulation using the Bowyer-Watson algorithm from above. Since the triangles use the indices relative to the patch, we also need to convert our indices from the patch triangulation to the 'global' index, so they reference vertices from the original vertex list again. To make this possible, we use the public NativeHashMap<int2, int> vertexReferences from the last job.
Since this job is still very computationally expensive, i've added a couple profiler marker to better understand where the time is spend in the profiler. This is the Patch Triangulation Job we get as a result:
[BurstCompile]
public struct PatchTriangulationJob : IJobParallelFor {
public GridSettings settings;
[ReadOnly] public NativeHashMap<int2, int> vertexReferences;
[WriteOnly] public NativeList<int3>.ParallelWriter triangles;
public ProfilerMarker InvalidSearchMarker;
public ProfilerMarker EdgeComputeMarker;
public ProfilerMarker VertexGatherMarker;
public ProfilerMarker TriangulationMarker;
public ProfilerMarker HoleTriangulationMarker;
public void Execute(int patchIndex) {
VertexGatherMarker.Begin();
var patchCountPerLine = (settings.Count - 1) / settings.CoreGridSpacing;
var patchPosition = LinearArrayHelper.ReverseLinearIndex(patchIndex, patchCountPerLine);
var patchLineVertCount = (settings.Count - 1) / patchCountPerLine;
var startVertex = patchPosition * patchLineVertCount;
var patchVertices = new NativeList<int2>(patchLineVertCount * patchLineVertCount / 2, Allocator.Temp);
var size = math.length(new int2(patchLineVertCount + 1));
// get all non-skipped vertices
for (int x = startVertex.x; x < startVertex.x + patchLineVertCount + 1; x++) {
for (int y = startVertex.y; y < startVertex.y + patchLineVertCount + 1; y++) {
var candidatePos = new int2(x, y);
var isValid = vertexReferences.ContainsKey(candidatePos);
if (isValid) patchVertices.Add(candidatePos);
}
}
VertexGatherMarker.End();
TriangulationMarker.Begin();
var triangulation = SimpleBowyerWatson.Delaunay(ref patchVertices, (int) size, ref InvalidSearchMarker, ref EdgeComputeMarker, ref HoleTriangulationMarker);
// add triangles to global triangle list, while getting the correct global indices.
for (var i = 0; i < triangulation.Length; i++) {
var triangle = triangulation[i];
var indices = triangle.Indices;
var posA = patchVertices[indices.x];
var posB = patchVertices[indices.y];
var posC = patchVertices[indices.z];
var indexA = vertexReferences[posA];
var indexB = vertexReferences[posB];
var indexC = vertexReferences[posC];
var globalIndices = new int3(indexA, indexB, indexC);
triangles.AddNoResize(globalIndices);
}
TriangulationMarker.End();
}
}Next we plug that new job into our MeshGenerator, using the job handle from the previous normals pass:
var triangleCountHalf = (settings.Count - 1) * (settings.Count - 1);
var triangles = new NativeList<int3>(triangleCountHalf * 2, Allocator.TempJob);
var patchCountPerLine = (settings.Count - 1) / settings.CoreGridSpacing;
var patchCount = patchCountPerLine * patchCountPerLine;
var triangulationHandle = new PatchTriangulationJob {
settings = settings,
vertexReferences = pointToVertexRefs,
triangles = triangles.AsParallelWriter(),
EdgeComputeMarker = new ProfilerMarker("EdgeComputeMarker"),
InvalidSearchMarker = new ProfilerMarker("InvalidSearchMarker"),
VertexGatherMarker = new ProfilerMarker("VertexGatherMarker"),
TriangulationMarker = new ProfilerMarker("TriangulationMarker"),
HoleTriangulationMarker = new ProfilerMarker("HoleTriangulationMarker")
}.Schedule(patchCount, 1, normalsHandle);
triangulationHandle.Complete();We also want to draw the triangles for easier debugging, so we cache them in the MeshGenerator component. In the OnDrawGizmosSelected() method, we draw the triangles. Also, dont't forget to dispose the 'triangles' NativeList we just created at the end of the GenerateMesh() method.
// to store the triangles (inside the GenerateMesh() method):
cachedTriangles.Clear();
foreach (var triangle in triangles) {
cachedTriangles.Add((vertices[triangle.x].Position, vertices[triangle.y].Position, vertices[triangle.z].Position));
}// draw the triangles:
private void OnDrawGizmosSelected() {
Gizmos.color = Color.green;
foreach (var cachedPoint in cachedPoints) {
Gizmos.DrawRay(cachedPoint.Position, cachedPoint.Normal);
}
Gizmos.color = Color.cyan;
foreach (var elem in cachedTriangles) {
var posA = elem.a + (float3) transform.position;
var posB = elem.b + (float3) transform.position;
var posC = elem.c + (float3) transform.position;
Gizmos.DrawLine(posA, posB);
Gizmos.DrawLine(posB, posC);
Gizmos.DrawLine(posC, posA);
}
}In this sample code, we do not take into account the gameobject's position when debug drawing the triangles. So make sure the object is at 0/0/0 or the triangles will not line up correctly. Or add the code to draw them add the correct positions (left as homework to the reader)
This is what the result looks like:
We can see that the mesh is now triangulated, and some areas of it have a lower vertex density that others. We also have the correct normals on each point. Looking at it from above gives us a clear view of how the grid is triangulated:
Generating the Mesh
Now all that is left to do is convert the triangle and vertex data into a unity mesh, and the first part of this tutorial series is done. To efficiently set the mesh data, the new MeshData API will be used.
On the main Thread, inside the GenerateMesh() method, we allocate a new writable mesh data instance:
var meshData = Mesh.AllocateWritableMeshData(1);
var mainMesh = meshData[0];We only have 1 mesh, so pass that '1' as parameter, and then get a reference to the first meshData we just created. Next, we create a new IJob, where we configure and populate the meshData element. For this, we need both the previously create list of triangles and vertices. Also, we need the meshData instance as job field.
The use the meshData, we first need to tell it the amount of indices and vertices we have, and in what format they're in. Since we stored our triangles as int3, each index is a 32-bit int. In the new job, we use this information to configure the index buffer parameters:
meshData.SetIndexBufferParams(triangles.Length * 3, IndexFormat.UInt32);Next, we need to set the vertex buffer parameters. We only have positions and normals available now, but here it would also be possible to set UVs, vertex colors, tangents and more. Vertex attributes are defined using VertexAttributeDescriptors. Normally they would be supplied as a list in the method parameters, but since we are in the burst-compiled job, a nativearray is required:
var attributes = new NativeArray<VertexAttributeDescriptor>(2, Allocator.Temp);
attributes[0] = new VertexAttributeDescriptor(VertexAttribute.Position);
attributes[1] = new VertexAttributeDescriptor(VertexAttribute.Normal);
meshData.SetVertexBufferParams(vertices.Length, attributes);Finally, we copy the vertices and indices into the meshData. This is the resulting complete job:
[BurstCompile]
public struct MeshPreparationJob : IJob {
[WriteOnly] public Mesh.MeshData meshData;
[ReadOnly] public NativeArray<NormalPassJob.VertexData> vertices;
[ReadOnly] public NativeArray<int3> triangles;
public void Execute() {
meshData.SetIndexBufferParams(triangles.Length * 3, IndexFormat.UInt32);
var attributes = new NativeArray<VertexAttributeDescriptor>(2, Allocator.Temp);
attributes[0] = new VertexAttributeDescriptor(VertexAttribute.Position);
attributes[1] = new VertexAttributeDescriptor(VertexAttribute.Normal);
meshData.SetVertexBufferParams(vertices.Length, attributes);
var meshVerts = meshData.GetVertexData<NormalPassJob.VertexData>();
meshVerts.CopyFrom(vertices);
var meshTris = meshData.GetIndexData<int>();
for (var i = 0; i < triangles.Length; i++) {
var triangle = triangles[i];
var startIndex = i * 3;
meshTris[startIndex] = triangle.x;
meshTris[startIndex + 1] = triangle.y;
meshTris[startIndex + 2] = triangle.z;
}
}
}Back in the main thread, in our GenerateMesh() method, we add this now job to the job chain, with the job handle of the triangulation job as dependency.
To apply the mesh data to an actual unity mesh, unity does some additional checks on the mesh. We do not need this, as we know we have the correct amount of indices, vertex, etc. To get a MeshUpdateFlags instance which skips all validations, we use the following method:
private static MeshUpdateFlags NoCalculations() {
return MeshUpdateFlags.DontRecalculateBounds | MeshUpdateFlags.DontValidateIndices | MeshUpdateFlags.DontNotifyMeshUsers | MeshUpdateFlags.DontResetBoneBounds;
}Since we disable the automatic bounds calculation for the mesh, we'll have to do that manually. This is rather easy, as we know the height and size of the terrain already:
var meshSize = settings.Count * settings.Distance;
mesh.bounds = new Bounds(new Vector3(meshSize / 2, settings.HeightScale / 2, meshSize / 2), new Vector3(meshSize, settings.HeightScale, meshSize));At last, we need to create a normal unity Mesh component, and apply our meshData to it. This mesh is then set to the MeshFilter of our object. Make sure to add both a MeshFilter and MeshRenderer component to the GameObject in the editor.
Putting it all together, we need to add this code to our GenerateMesh() method:
var meshData = Mesh.AllocateWritableMeshData(1);
var mainMesh = meshData[0];
var meshingHandle = new MeshPreparationJob {
meshData = mainMesh,
triangles = triangles.AsDeferredJobArray(),
vertices = vertices.AsDeferredJobArray()
}.Schedule(triangulationHandle);
meshingHandle.Complete();
var indicesCount = triangles.Length * 3;
mainMesh.subMeshCount = 1;
mainMesh.SetSubMesh(0, new SubMeshDescriptor(0, indicesCount), NoCalculations());
var mesh = new Mesh {name = this.transform.name};
var meshSize = settings.Count * settings.Distance;
mesh.bounds = new Bounds(new Vector3(meshSize / 2, settings.HeightScale / 2, meshSize / 2), new Vector3(meshSize, settings.HeightScale, meshSize));
Mesh.ApplyAndDisposeWritableMeshData(meshData, mesh, NoCalculations());
gameObject.GetComponent<MeshFilter>().mesh = mesh;Checking back into the inspector, we can now see that we have generated a mesh:
Outro
Now, we have a working, procedural "terrain" generation. It works using burst-compiled jobs and finishes in a couple milliseconds, allowing us to execute it at runtime, during a single frame or delayed in the background over a couple of frames. Where you go with this is up to you. You could add multiple terrain parts together, and update their resolution as the camera moves around.
The terrain shape itself is looking pretty boring at the moment. We could solve this by using one or a mix of multiple Heightmaps to sample heights from, or use more advanced methods of procedural generation. We could use (ridged) multifractal noise, or use different layers of noise as masks for each other to generate a more interesting procedural terrain.
Here is an example of what we could do using multi-layered noise with different noise mask inputs:
I'll leave it to you to figure out how you want to sample your terrains, there's plenty of tutorials available in this area online.
In the next episode of this tutorial series, a quadtree will be used to adaptivly create and remove terrain chunks, making the terrain detail adaptivly change around the player.
Let me know in the comments what you think of this approach, and if you have ideas for improvements.
Code: https://github.com/Rearth/MeshGenerationSamples
