More Multithreading!

     This week I decided to try my hand at optimizing and improving the multithreading that is used in the game. I wanted to make it faster because the way it was implemented would cause the initial level load to take minutes if you had many terrestrial planets or cranked the quality level up in the settings.


Background

    I first added multithreading to the game in early October of 2020, and I covered the process of doing so in the "Multithreading Hell" post. I remember it being a frustrating ordeal at the time, but with years more experience under my belt by now I figured it would be a good a time as any to go back to it.
    Multithreading is only utilized for the generation of terrestrial planets. Terrestrial planet meshes are made by evaluating noise at coordinates on a sphere. The sphere is made by taking points on a cube and normalizing them from the center. The sphere can then be neatly divided into six faces. The old approach would use one thread per face which was absolutely an improvement over the single threaded approach, being able to calculate all six faces at once and not blocking up the game thread until that was all finished. But I got to thinking, could I do more threads?
    

Implementation

    My first thought was to subdivide each square face into smaller square faces, and have each thread calculate for one of those subfaces. It seemed intuitive, but when I got to looking at the implementation it got quite tricky. The main limiter is that the vertices, UVs, and tris for the procedural mesh are all in 1D arrays. The indices of the arrays would count up as you go left to right, top to bottom along the mesh. So for a mesh of resolution 16, the first row of points would start at array index 0, the second row at 15, and so on. Because of this, I anticipated that calculating the array indices that each thread would be responsible for was going to be a massive headache and would probably end up looking super convoluted in the code. 
    Then I realized there's no reason it has to be calculated in squares. Sure it would look nice if I wanted to get a slo-mo shot where each section is generated in sync, but I had to focus on the end result I wanted; clean, readable code with reliable execution. The implementation that I would use then became relatively obvious: each thread would calculate some number of rows of the final mesh. 
    This implementation would be quite simple. The mesh calculation just goes through every (x, y) coordinate of the mesh in two nested loops. All I would need to do is give each thread a different starting and ending y coordinate: 

int ResolutionPerThread = Data.Resolution / TotalThreads;
int StartIndex = ResolutionPerThread * ThreadIndex;
int EndIndex = StartIndex + ResolutionPerThread; 
int TriIndex = StartIndex * (Data.Resolution - 1) * 6;
		
for (int y = StartIndex; y < EndIndex; y++)
{
	for (int x = 0; x < Data.Resolution; x++)
	{
...

    The only hiccup I had was with the triangles array. Because there are six array indices per triangle (to define each point of the triangle) it needs to be six times the resolution. But because you don't want to run off the mesh, you don't want to include the last line of vertices. Which is what the (Data.Resolution - 1) is doing, and that took me an embarrassingly long time to figure out.
    With the vertex calculation working there was still one bottleneck left: tangents and normals. This was the last step once the entire face had been calculated to get lighting and whatnot to behave properly on the mesh. I just hand this work off to the engine by calling UKismetProceduralMeshLibrary::CalculateTangentsForMesh. I tried doing this for each sub-face but for some reason that made it much less performant. When I calculated the whole face at once, loading into the game (so generating three planets) took about a second. But when calculating tangents/normals for each subface it took about twenty two seconds which is crazy. I absolutely messed something up along the way, and I plan to investigate more next week.

Comments

Post a Comment

Popular posts from this blog

Progress Update #19

Image
  Orbit Debug/Visualizer Optimization     This week I tasked myself with optimizing the orbit visualizer. The reasoning behind this was that I couldn't render an entire orbit of planets with large orbit radii without the framerate plummeting to the low teens and that would need to change. Finding the Root Problem     The first thing I set out to do was to find out exactly why the engine was having a hard time with rendering orbits far into the predicted future. While looking for methods of debugging optimization in Unreal, I came across a presentation by the Unreal team on  Profiling and Optimization in UE4 . This talk introduced me to the stat unitGraph console command as well as the GPU Profile accessible with the shortcut Ctrl + Shift + ,     Through these methods of debugging I realized that the debug line method of rendering would hit the CPU render thread (draw) while the spline method would hit the CPU game thread. Baseline (0 step...
Read more

Progress Update #21

Image
  Procedural Generation Runtime Compliance     Over this week I have made major progress on the packaging errors that effected the project; the majority of which had to do with the systems of generating procedural meshes and textures at runtime. The reason they weren't runtime compliant is that I was using functions and variables from the engine that were marked as WITH_EDITOR or WITH_EDITORONLY_DATA which are not allowed to be used in packaged builds of the game/ at runtime. Procedural Meshes:     With the main appeal of the game being the generation of planets I decided to start by fixing the mesh generation system. In the process of looking for a solution I came across two articles ( article 1 article 2 ) on the subject of runtime procedural meshes written by an employee of Epic Games. The first article was the one that I spent most of my time on but they are both very detailed on their respective topics.      After multiple days of trying to ...
Read more

Progress Update #29

Image
  Ahead of Schedule     This week I managed to get all the features done before the end of the sprint and even managed to make a dent in next week's work as well. Overview Overhaul     The main focus of this week's sprint was to redo the overview UI. Like I said last week, this remodeling essentially makes the highlight UI that I worked on obsolete. This is not necessarily a bad thing though as, in my opinion, it is much more easy to understand and interact with.     The essence of the new design was to have a collapsing sidebar that would have three sections: Bodies, Asteroids, and Simulation Settings. The bodies tab would have all of the information that was in the old highlight but now in an easy to read vertical list. This tab would also house the "Add Body" button that was made last week. The asteroids tab would have settings for the asteroids that are aimlessly wandering the solar system as well as specific settings for individual aster...
Read more