Bend the world with Unity's Shader Graph

Hurray! Unity 2018.2 is out and that means: vertex positions are now accessible in graph shaders!

This means that the world bend shader from this previous post can now be implemented as a node! The cool part is: I only added one .cs file containing a custom node and it works with the existing code.

Add the "World Bend" node into the graph, and define 3 properties "Horizon", "Spread" and "Attenuation" (check my previous post to see what they are for). Connect the output as input for the position of your Master Node. Do not expose the three properties, but give them these reference values respectively: "_HORIZON", "_SPREAD", "_ATTENUATE". That way they receive the global values set by the World Bender script on the camera. And that's it! There is only one extra file:

using System.Reflection;
using UnityEditor.ShaderGraph;
using UnityEngine;

[Title("Custom", "World Bend")]
public class BendNode : CodeFunctionNode
{
 public BendNode()
 {
  name = "World Bend";
 }

 protected override MethodInfo GetFunctionToConvert()
 {
  return GetType().GetMethod("Bend",
   BindingFlags.Static | BindingFlags.NonPublic);
 }

 static string Bend(
  [Slot(0, Binding.ObjectSpacePosition)] Vector3 v,
  [Slot(1, Binding.None)] Vector1 Horizon,
  [Slot(2, Binding.None)] Vector1 Spread,
  [Slot(3, Binding.None)] Vector1 Attenuate,
  [Slot(4, Binding.None)] out Vector3 Out)
 {
  Out = Vector3.zero;
  return @"
{
 Out = mul (unity_ObjectToWorld, v);
 float dist = max(0.0, abs(Horizon.x - Out.z) - Spread);
 Out.y -= dist * dist * Attenuate;
 Out = mul(unity_WorldToObject, Out);
}";
 }
}

As always, you can find a small demo on my unity toolset repo. I'm open for feedback!

Trashing the cache: C++ vs C#

In my previous post I showed how data locality can improve your program's performance. Since then I have been wondering whether these same optimizations are valid in C# too. (If you haven't read the previous post you'd better do that first, or this won't make much sense)

Integer array

Thus again, we loop over an array of integers with increasing step size, inspired by this blogpost. The goal is to illustrate the impact of cache-fetches, where we need to fetch data from memory into the cache instead of having a cache-hit. In C# we have almost identical code to the C++ version:

const int length = 64 * 1024 * 1024;
var arr = new int[length];
for (int k = 1; k <= 1024; k = k * 2)
{
  for (int i = 0; i < length; i += k)
  arr[i] = i;
}

We measure how long it takes to go through the array and perform an operation on each value, with an increasing step size of powers of two. That gave me these results:

That's quasi identical to the C++ version:

In other words, we're just as memory-fetch-time bound in C# as we are in C++. This should not come as a surprise.

GameObjects

We create a similar GameObject class as in the C++ version:

class GameObject3D
{
  public float[] transform = {
    1,0,0,0,
    0,1,0,0,
    0,0,1,0,
    0,0,0,1
  };
  public int ID;
}

Here we stumble upon a difference between C++ and C#: creating an array of these objects in C++ allocates the memory and initializes it with the default constructor on every instance. In C# we must write this ourselves:

GameObject3D* arr = new GameObject3D[length];

vs

GameObject3D[] arr = new GameObject3D[length];
for (int i = 0; i < length; i++)
  arr[i] = new GameObject3D();

The timings are very similar. Again, we are bound by cache speed:

Here's my alternative again:

class Transform
{
  public float[] values = {
    1,0,0,0,
    0,1,0,0,
    0,0,1,0,
    0,0,0,1
  };
}

class GameObject3DAlt
{
  public Transform transform;
  public int ID;
};

Which yields this graphic:

Wait what? What happens here? The chart has a different shape than the C++ version and is almost twice as high? C# clearly introduces some overhead here. The talk of Joachim Ante on the new Entity-Component system of Unity gave me the idea to try a struct version of our classes; because we are creating the game object instances one by one they're not guaranteed to be located next to each other in memory. So I tried this instead:

struct SGameObject3DAlt
{
  public Transform transform;
  public int ID;
};

Unlike arrays of classes, arrays of structs are co-allocated in memory and initialized, causing the same speeds as we had in C++ (even a little bit faster!):

Ok, that's it. We re-created all tests in C# and we achieved quasi identical results. In conclusion: C# is just as memory-fetch-bound as C++, and in C# you carefully need to think whether or not you want to use structs instead of classes. But the fact that we achieve at least the same timings also shows that C# is as fast as C++ in these rather contrived tests.

Unity crash dumps to the rescue!

My last post ended with me being disappointed about the state of our webgl build of Kweetet. I'm happy to say that I solved a lot of the remaining issues in the past holidays, against my expectations! The WebGL build might be a viable production target after all.

Nevertheless we still need a standalone build, because it's clear that WebGL is not fit for older systems. The memory usage has become less (around 1GB) but it's still a lot and we have a target audience that sometimes has only that.

Creating a standalone version went fast, i was done in a day, but that doesn't come as a surprise since standalone windows and webplayer builds are very alike.

A colleague of mine always had the weirdest crashes in the webplayer. It was always only on her pc and we could never reliably reproduce it. The log of the webplayer pointed in various directions, but we could never determine the cause of the crashes. Now with the standalone build she had the same crash and behold: there was a crash.dmp file! I've always made builds for mobile and web platforms so I had no idea that standalone build generated dump files. I opened it in Visual Studio immediately. I couldn't do much with it at first, but googling around brought me to this thread on the Unity forum where I learned that Unity has a symbol server! There you can download the pdb files for a standalone build, or even better, you can add the server to your debugger settings in Visual Studio:

Once you've done that you have an accurate callstack of the crash. The callstack was completely different than anything reported in the webplayer log files, but it explained completely every crash my colleague has had. It was an easy fix after that.

Trying to reproduce hard to find crashes in the webplayer or even the webgl builds with a standalone build can really pay off.

The quest for WebGL - part 2

Find part 1 here.

So now that we have a +/- working version running with Unity5 it was time for the next step: making a webgl build. That wasn't hard, getting the build to run on the other hand was.

1. Communicating with the api

You can't start Kweetet unless you're logged in, so one thing that we needed to get working first was the communication with the api. We used sockets in the webplayer with the UniWeb plugin, but as you might know sockets aren't supported in webgl, so we had to look for other solutions. Our website had a javascript class that already communicated with the api via CORS for other purposes than the game, so we wrote a javascript plugin that uses this class. The documentation on how to do that can be found here, but what's missing is how to use callbacks. Our function needs to call the api and trigger a succes or error callback. It ended up looking like this:

var WebGLAPI = {
  $callbackObject: {},

  InitRestClient: function(successCallback, errorCallback)
  {
    callbackObject.successCallback = successCallback;
    callbackObject.errorCallback = errorCallback;
  },
  
  DoJSCall: function(path, method, data)
  {
    DK.restClient.doCall(Pointer_stringify(path), Pointer_stringify(method), Pointer_stringify(data), function() {
      var returnStr = arguments[0];
      var buffer = _malloc(lengthBytesUTF8(returnStr) + 1);
      writeStringToMemory(returnStr, buffer);
      Runtime.dynCall('vi', callbackObject.successCallback, [buffer]);
      _free(buffer);
    },
    function() {
      var returnStr = JSON.stringify(arguments[0].data);
      var buffer = _malloc(lengthBytesUTF8(returnStr) + 1);
      writeStringToMemory(returnStr, buffer);
      Runtime.dynCall('vi', callbackObject.errorCallback, [buffer]);
      _free(buffer);
    });
  }  
};

autoAddDeps(WebGLAPI, '$callbackObject');
mergeInto(LibraryManager.library, WebGLAPI);

As you can see we need to define a callbackobject where we register our callbacks in an init function. In the C# part that looks like this:

public class JsApiComm {
  [DllImport("__Internal")]
  private static extern void DoJSCall(string path, string method, string data);

  [DllImport("__Internal")]
  public static extern void InitRestClient(Action<string> success, Action<string> failure);

  [MonoPInvokeCallback(typeof(Action<string>))]
  public static void SuccessCallback(string arg)
  {
    ...
  }

  [MonoPInvokeCallback(typeof(Action<string>))]
  public static void ErrorCallback(string arg)
  {
    ...
  }

  public JsApiComm()
  {
    InitRestClient(SuccessCallback, ErrorCallback);
  }
  
  ...
}

Just today I stumbled upon a subtle problem with the code from the manual: to create the buffer to write a javascript string into, the manual uses the length of the string to create a buffer of that many bytes + 1. But if the string contains multibyte characters as in for example "Dierië" then you need to allocate more bytes than characters, or you have a buffer overflow!

The javascript function writeStringToMemory does not look at the size of the buffer so if the string is larger than the buffer it simply writes outside of it. This of course caused many seemingly random crashes in our game, which made it difficult to find the cause at first. The solution is using the function that counts the bytes in the string, and thus enables us to create a buffer of the correct size. I mentioned this on the forum and they're updating this.

2. Memory leak

So with the api in place we can start the game, but even before the first loadscreen was done the browser ran out of memory. I had this in a latest version of Firefox 32bit and it was even worse in Chrome (Chrome has proven to be very bad at most of the things I tried). I then installed a 64bit developer edition, since that one would be able to go beyond 3GB memory and it did: the memory consumption went up to 10GB (!) and kept rising.

This turned out to be a Unity bug in WWW.LoadFromCacheOrDownload that we used all the time. It was this explanation of Jonas Echterhoff that tipped me in the right direction. A must read!

So we temporarily use the regular WWW download and now the memory leak issue is gone. It's supposed to be fixed in 5.3 so I'll try again then.

3. "Could not produce class..."

Another hard to solve problem was that our game crashed when loading a new scene with LoadLevelAsync. Apparently (thanks Marco Trivellato) this is caused by the stripping of classes you never reference in your code but do use in your scenes that you then load via assetbundles. You know you have this issue when you start seeing log entries that look like "Could not produce class with ID xxx". This gives you an ID which you can use to lookup here. For example, we had a few WindZones with ID 182 in some scenes that caused this issue.

4. Development vs Release build

With a development build it's easier to read stacktraces which you need to fix bugs, but most browsers aren't capable to handle the large output of that build (a .js file of 192MB!). Firefox 32 bit tries and succeeds most of the time, Chrome gives up before it executed anything. So I really recommend using the 64bit developer edition of Firefox, that one can handle any build, no matter what I enable or disable.

Luckily, chrome can run a release build, so we're in the clear. But it's still not as fast as Firefox.

Once these issues were solved we finally have a running build! Hurray! I commented out some parts of the game however to get this far, so I have to re-enable those en see what errors I need to fix there. But I'm cautiously confident that we'll succeed to port our game to webgl, how cool is that!

Bending the world with Unity

I am a big fan of Deathspank. I love the art style, I like the humor, the gameplay, the combat, the inventory, the start menu, all of it. You can see that in the game I currently work on (Kweetet): some of the art style has a resemblance, the dialog system is the same and: we've got a rolling world too. I really like the rolling world effect in Deathspank, it creates a cartoony feel for the world in general. So I said the concept artist that I really wanted it in the game, he liked it too, so we implemented it. In this post I'd like to explain how we did it, what problems were encountered and how we solved them or didn't solve them.

Here is a movie that illustrates the effect in the game:

The shader

The idea behind it is actually very simple, we just displace the vertices of any mesh in the vertex shader according to a parabola. The vertex shader of the main material in Kweetet looks like this:

#pragma vertex vert
#pragma fragment frag
#pragma multi_compile __ BEND_ON
#pragma multi_compile __ BEND_OFF

...

v2f vert (appdata_t v)
{
 v2f o;
 #if defined(BEND_OFF)
 o.vertex = mul(UNITY_MATRIX_MVP, v.vertex);
 #else
  #if defined(BEND_ON)
  o.vertex = mul(UNITY_MATRIX_MVP, DSEffect(v.vertex));
  #else
  o.vertex = mul(UNITY_MATRIX_MVP, v.vertex);
  #endif
 #endif
 o.texcoord = TRANSFORM_TEX(v.texcoord, _MainTex);
 ...
 return o;
}

As you see at the top, we have two multi compile directives. The first one is used to enable bending on a global level via a shader keyword. That way all materials bend if it's enabled in the current scene. Sometimes however you do want to disable the bending, even if the world bends, for example objects that are shown in the UI instead of the scene. To do that enable the BEND_OFF keyword via the material. We use these two because we can't disable the BEND_ON keyword via the material if it was enabled via a global shader keyword.

If BEND_OFF is disabled and BEND_ON is enabled, you see that the function DSEffect is called before we multiply the vertex with the modelviewprojection matrix (DSEffect as short for "DeathSpankEffect" - I called it like that when we were still experimenting and never took the time to refactor). That function looks like this:

uniform float _HORIZON = 0.0f;
uniform float _ATTENUATE = 0.0f;
uniform float _SPREAD = 0.0f;

float4 DSEffect (float4 v)
{
 float4 t = mul (_Object2World, v);
 float dist = max(0, abs(_HORIZON - t.z) - _SPREAD);
 t.y -= dist * dist * _ATTENUATE;
 t.xyz = mul(_World2Object, t).xyz * unity_Scale.w;
 return t;
}

There are three global variables, that I'll explain further. First we put the given vertex in world space. Then we calculate it's z depth (more on that line later). Then we apply the parabola formula:

y = -a * z^2

where a is the attenuation of the parabola. It's a negative attenuation so the world goes down. (If it were positive the world would bend upwards. Can be cool too). We add this result to the y value of the vertex. Then we put the vertex back in object space and return the result. In Unity 4.x you need to multiply with unity_Scale.w, in Unity 5 this is no longer needed.

For the characteristics of our game we only need bending in the z direction, and only with a parabolic function. But off course we can use other functions that alter the y value in function of both the z and the x coordinates.

The bendcontroller

In a scene that needs to bend we place a gameobject with a bend controller script attached, that looks something like this:

using UnityEngine;

public class HeroBendController : MonoBehaviour {
 
 public float attenuate = 1.0f;
 public float horizonOffset = 0.0f;
 public float spread = 1.0f;
 public Transform player;
 
 private void Update () 
 {
  Shader.EnableKeyword("BEND_ON");
  Shader.SetGlobalFloat("_HORIZON", player.position.z + horizonOffset);
  Shader.SetGlobalFloat("_SPREAD", spread);
  Shader.SetGlobalFloat("_ATTENUATE", attenuate);
 }
 
 private void OnDisable()
 {
  Shader.DisableKeyword("BEND_ON");
  Shader.SetGlobalFloat("_ATTENUATE", 0);
  Shader.SetGlobalFloat("_SPREAD", 0);
  Shader.SetGlobalFloat("_HORIZON", 0);
 }
}

We need the transform of the avatar of the player (or some other reference), the z position of the avatar needs to be the top of the parabola, so this is the offset we have to apply on the vertices of the other meshes. This is what I called the _HORIZON variable in the shader. It's the z coordinate in world space where the top of the parabola will be. It looks something like this:

In this case the avatar is walking on top of the world, but most of the time we want the horizon to be a bit higher, so that's why we have the horizonOffset value in the controller. This is the same scene, but with an offset of 3:

And that's it. There's nothing more to it than this to achieve the bending world effect. Unfortunately the effect introduces some consequences that need to be addressed, if the game is impacted by them.

Raycasting

The effect is done in the vertex shader, not on the actual vertices. This means that the meshes in the game do not bend, and thus the physics world doesn't bend. This is a good thing, because if the physics world would bend, everything would start to fall off. The same goes for pathfinding meshes; they are still valid. The raycasts that may be used in pathfinding are valid too, so everything remains ok.

But when we perform a raycast from the camera into the scene, to select objects in the world or to select the next position that the avatar needs to walk to, things are more difficult. The user will click on the visual position of an object but if the object is bended the actual location in the physics world is different.

The following image illustrates this: the user wants to click above the cube in the scene on the floor (the red ray) but will actually click on the cube. If the user would have clicked on the bottom of the cube (to select it for example) he would have clicked on the floor instead.

My first idea was to determine the position that the ray hits in the visual world by calculating the intersection of the ray with the parabola. I projected that position back to its original height and then I did a raycast to that position instead. This worked quite perfectly for situations similar to the one in the above image, however when the ray is above the horizon we don't have an intersection point, so this solution doesn't cover all cases.

The best solution of course is not to use these raycasts at all of course. This is what Deathspank does; navigation is not done by clicking on the next spot where Deathspank needs to go but with the keys or the gamepad. Interaction with objects is done when you're close to them with keys or the gamepad. In the pc version of DeathSpank you can use the mouse to navigate, so I don't know what solution they've come up with.

Animal Crossing uses a rolling world as well. I've never played it but since it's a 3DS game I don't think there's ever any raycasts needed from the camera, so they won't have this issue either.

With Kweetet we are targeting children in primary school with possibly limited gaming skills playing on a pc in the browser, so they need to be able to do everything with a single mouse click. So I had no choice but to find a solution, or we would have to abandon the idea entirely.

In the game, objects can be interacted with once they are within a certain distance to the avatar. That distance is mostly between 3 and 5 units. This means that if we create an area of +/- 5 units around the avatar where the world doesn't bend, all relevant raycasts will be correct. This is what the _SPREAD variable does in the vertex shader. it flattens the top of the parabola, creating an area around the avatar where physics and visuals match.

This turned out to be the perfect solution, raycasts work where they should and the flat area around the player is small enough to still enjoy the effect of the world bending.

Frustum culling

Frustum culling is done before any vertex shaders are executed (obviously, or it wouldn't be culling). Because of that, objects that are bended into the view of the camera but are actually outside of it get culled. The result is that these objects pop in and out when they shouldn't.

In the above image the red line and circle is the non bended world, the black line and circle is the bended world. The blue lines depict the camera frustum. As you can see, the circle will be culled, while it should be visible.

These objects are typical small and highly located in the world. Ideally, we want to disable frustum culling for these objects, but that is not possible in Unity.

[Start edit]

The first comment on this post pointed me in another direction to solve this issue, so I changed this part. In Unity 4 it wasn't possible to change the camera used for culling without affecting the camera used for rendering. It turns it that in Unity 5 this has been made possible!

This totally removes the need to, as I used to do, enlarge bounding boxes of meshes or combine them into larger objects. Instead, you can add a script to the camera that looks somewhat like this:

using UnityEngine;
public class BenderCamera : MonoBehaviour
{
 [Range(0, 0.5f)]
 public float extraCullHeight;
 public Camera _camera;

 private void Start() {
  if(_camera == null)
   _camera = GetComponent<Camera>();
 }

 private void OnPreCull() {
  float ar = _camera.aspect;
  float fov = _camera.fieldOfView;
  float viewPortHeight = Mathf.Tan(Mathf.Deg2Rad * fov * 0.5f);
  float viewPortwidth = viewPortHeight * ar;

  float newfov = fov * (1 + extraCullHeight);
  float newheight = Mathf.Tan(Mathf.Deg2Rad * newfov * 0.5f);
  float newar = viewPortwidth / (newheight);

  _camera.projectionMatrix = Matrix4x4.Perspective(newfov, newar, _camera.nearClipPlane, _camera.farClipPlane);
 }

 private void OnPreRender() {
  _camera.ResetProjectionMatrix();
 }
}

This adds a bit on the top and bottom of the culling camera, as you can see in this screenshot (the grey lines are the view frustum of the render camera, the colored lines are the view frustum of the cull camera):

This solution solves the culling issue completely, without any manual intervention other than tweaking the extra cull height value.

[End edit]

Particles

Another thing to consider are particles. With particles you can choose between meshes or billboards. With meshes nothing changes so you can use the same vertex shader, but billboards are passed in camera space instead of object space to the vertex shader. Thus we need a camera to world space matrix to achieve the bending effect on billboard particles. I have this in a script on my camera:

private void OnPreCull()
{
 Shader.SetGlobalMatrix ("_Camera2World", camera.cameraToWorldMatrix );
 Shader.SetGlobalMatrix ("_World2Camera", camera.worldToCameraMatrix );
}

And with these matrices we have this function for the vertex shaders:

float4x4 _Camera2World;
float4x4 _World2Camera;

float4 ParticleDSEffect (float4 v)
{
 float4 t = mul (_Camera2World, v);
 float dist = max(0, abs(_HORIZON - t.z) - _SPREAD);
 t.y -= dist * dist * _ATTENUATE;
 t.xyz = mul(_World2Camera, t).xyz;
 return t;
}

Which is basically the same one, but without the unity_Scale and using the other matrices. We override the built-in particle materials in Unity to use this bending function when appropriate. In other words, this situation is easily fixed, but it requires some careful handling of the shaders.

Conclusion

This is in short how we've implemented this technique in our game and how we solved certain problems. I'm by no means sure that these are good solutions, so I'm happy to receive feedback on all of this. I'm planning to set up a Unity project on github where I can place all the scripts I describe on this blog, with demo scenes of every technique. And if this post helps the reader to apply this technique in another game then I'm pleased to be able to contribute.

[Edit]The unity project with a demo is now available here (it's a bitbucket repo instead of github). Look for the world bender scene in the project.[/Edit]

[Edit]Since 2018.2 is out, I also have a node that can be used in a shader graph, read all about it here.

C# - Initialization of enums

I notice that I want to write too much based on what I have read in Effective C#, so I'll post bits and pieces instead of one big article, here comes a small one:

Initialization and enums

If an object is instantiated all member variables are initialized, with a given initializer or 0/null if none was specified. References are always null, bools are always false, number values are 0, and... enums are set to 0.

Wow! I never realized that, I kinda assumed that an enum value was set to the first value defined in the enum, but this is clearly not the case - and shouldn't be. It does imply that you always need to have a 0-value in your enums, or you risk having an enum variable with an undefined value. Also, when using the [Flags] modifier, None = 0.

Effective C#

Now that I own the c++ coding standards book, I also want to buy the Effective C++ book by Scott Meyers. I also already read it at Larian front to back and I know its worth.

But since I'm currently developing more in C# I thought I'd look for similar quality books about that language. I just ordered Effective C# by Bill Wagner and I hope it's as good as the C++ books.

While looking for it, I also found this code project article that has the same title. It offers some tips but unfortunately without explaining why the tips apply. But at least I learned some small ideas that I can use in the future:

I can write strings with an @ in front and then I don't have to worry about double backslashes to have a single backslash in my path.

I really should start using stringbuilders, I know I have to use them but the only time I want to concatenate strings is when I want to have some debugging output. I'm too lazy to create stringbuilders at that time and since they're only executed in debug mode I don't want to bother with them. But when I do concatenate strings in release, I should use stringbuilders, let's do that from now on.

Let's look into ngen

Wow, 'checked', handy keyword!

And concerning the 'for' versus 'foreach' discussion: I want to delve more deeply into that because let's face it, foreach is soooo easy to use that I do not want to ditch it just because it would be a little less efficient. I want to know for sure that's the case and when that's the case. I hope my new book (arriving in 2-3 days) will provide me with an answer.