How to Use Shaders for Simulations

This series of tutorials will teach you how use shaders for simulations; in particular how to use them to simulate fluids. This first post will focus on how to continuously process a texture using a shader. This technique is at the heart of most simulations and will be used in this series to implement shaders that simulate smoke and liquids.

texture6

Continue reading

To Voronoi and Beyond

Voronoi Diagrams

This tutorial is a primer on Voronoi diagrams: what they are, what you need them for and how to generate them using a Shader in Unity. You can download the complete Unity page in Part 4.

Part 1: Voronoi Diagrams

Technically speaking, Voronoi diagrams are a way to tassellate a space. It means that the end result of Voronoi is a set of “puzzle pieces” which completely fills the space. To start, we need a set of points (often called seeds) in the space. Each seed will generate a piece of this puzzle. The way Voronoi works is by assigning every point of the space to its closest seed. The final result heavily depends on the way distance is measured in the space.

Euclidean distance

Voronoi_1Most Voronoi diagrams are are based on the Euclidean distance. The cost between two points is given by the length of the shortest segment which connects them both. It can be calculated easily with the Pythagorean theorem:

    \[D=\sqrt\left({\Delta x}^2+{\Delta y}^2 \right)\]

In Cg, this function is already implemented and is called distance. The picture on the left shows a Voronoi diagram based on the Euclidean distance, drawn with 100 points. On the right, the same diagram uses a gradient to visualise the actual distance from a pixel to the closest one.

Voronoi
Voronoi distance
The distance diagram has been calculated using minDist to sample a gradient from black to white.

Manhattan distance

Voronoi_2As the name suggests, the Manhattan distance takes his name from the homonym city. The shortest path between two locations is not a straight line, since Manhattan is full of buildings. The shortest distance is the one which goes around building.

    \[D=\left | \Delta x \right |+ \left | \Delta y \right |\]

half distance_manhattan(float2 a, float2 b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

Compared to the Euclidean distance, It is sensibly less expensive to calculate.

manhattan
manhattan distance

Using the Manhattan distance produces very intriguing patterns which resemble circuit boards. This is not a coincidence: many boards are designed to minimise circuit length and avoid curves.

Minkowski distance

Voronoi_3Despite looking very different, both the Euclidean and the Manhattan distances are both special cases of a more general metric: the Minkowsi distance. To understand why, you have to remind some algebra. In the same way multiplication and division are the same operator (dividing by 10 is equivalent to multiply by \frac{1}{10}), even root and exponentiation are deeply connected. Remembering then \sqrt[n]{x} = x^{ 1/n   }, we can introduce the Minkowski distance:

    \[D= \left( { \left| {\Delta x} \right | ^p+\left| {\Delta y} \right |^p } \right)^{1/p}\]

When p=1 or p=2 it equivalent to the Manhattan or Euclidian distance, respectively.

half distance_minkowski(float2 a, float2 b, float p) {
	return pow(pow(abs(a.x - b.x),p) + pow(abs(a.y - b.y),_P),1/p);
}

The most fascinating aspect is that is provides a way to smoothly transitioning from the Euclidean to the Manhattan distance, and the other way round.

m2v
m2v_d
 If you are in a higher dimension, the Minkowski distance can be still used, providing that you calculate it on all the components of two points a and b:

    \[D= \left( {\sum_i^n \left|{a_i - b_i}\right |^p } \right)^{1/p}\]

The next part of this tutorial will focus on the applications of Voronoi diagrams.

Applications

Part 2: Applications

Despite looking pretty, not a single application has been indicated for Voronoi diagrams yet. In actuality, they play a very important role in Science, and many games can benefits from them.

In games

Breaking object realistically is a very challenging task, that requires to know how pressure waves propagates through a material. A simpler way to create plausible fractures in an object is to rely on a Voronoi 3D tassellation. You start choosing random points within the object you want to break, then each Voronoi cell become one of its chunks. In games, breakable objects don’t break: they are already broken, and your interaction makes the piece falling apart.

fracturedcube-e1358120248710

The famous Fracturing & Destruction plugin on the Asset Store, for instance, uses this technique to generate breakable objects. A future post will show how to replicate this effect at no cost.

In path finding

As a game developer, you might be familiar with path finding. A* is notoriously the most known, but there are many other ways one can find the optimal path between two points. So far, Voronoi diagrams have been seen as independent regions of space although there is an alternative way of interpreting them. If we put a node every time two segments connects, Voronoi produces a graph. The segments (now edges of the graph) represent the paths which are as far as possible from the seeds. In terms of gaming, seeds can be enemies you want to avoid; travelling on the edges provides the safest route possible. Brent Owens has written a very nice tutorial about this.

Voronoi_diagrams_for_AI-9-voronoi_safe_path

Conversely, Voronoi diagrams can be also used to approximate the shortest path. The dual graph of a Voronoi diagram (known as the Delaunay triangulation) allows to find paths which are as close as possible to the seeds. When coupled with the Manhattan distance, it can be used to generate the fastest route within a city, considering how fast you can go on different roads.

cityvoronoi

In nature

2000px-Circle_packing_(hexagonal).svgCircle packing is the problem of fitting as many circles as possible in a given space. The best possible solution to this problem is shown on the left; circles are arranged in a hexagonal lattice, which resemble a honeycomb. This is actually why honeycomb cells have a hexagonal structure: if all circle expands at the same time to fill all the space around them, they’ll end up pressing against each other until they create a perfect hexagonal lattice. The same pattern can be found in several other phenomena, like cooling magma and soap bubbles. The latter, provide an excellent (and transparent) example of how Voronoi diagrams look in three dimensions.

The next part of this tutorial will show how to generate Voronoi diagrams using Shaders.

Generation

Part 3: Generation

Fortunes-algorithm-slowedThere are several algorithms you can rely on to generate Voronoi diagrams.  Every point is independent from the other, so this is one of those perfect applications for a shader. Traditionally the Fortune’s algorithm (left) is commonly used, but it is very hard to implement within a shader. The tricky part, in this case, is how to provide a list of points to the Material, since the Unity APIs don’t provide any SetArray function. Luckily, there is an undocumented feature you can use to pass arrays and matrices to a shaders, and it has been discussed in this post. We will use one array for the position of the points (in a 2D space) and another one for the colours. A variable called _Length is used to indicate how many points are there since Cg doesn’t support arrays of arbitrary dimensions.

uniform int _Length = 0;
uniform half2 _Points[100];
uniform fixed3 _Colors[100];

The actual code of the Voronoi diagram is implemented in the fragment function. For each pixel, it simply loops over all the points and finds the closest one. Its index is then used to find the right colour to use:

fixed4 frag(vertOutput output) : COLOR {
	half minDist = 10000; // (Infinity)
	int minI = 0;
	for (int i = 0; i < _Length; i++) {
		half dist = distance(output.worldPos.xy, _Points[i].xy);
		if (dist < minDist) {
			minDist = dist;
			minI = i;
		}
	}
	return fixed4(_Colors[minI], 1);
}

Different types of diagrams are possible simply by replacing the function distance with the appropriate metric. If you want to draw the distance diagram instead, you can sample a ramp texture using minDist. You can also set the texture mode to “Repeat” rather than “Clamp” for some bizarre effects.

half4 color = tex2D(_RampTex, fixed2(minDist, 0.5));
color.a = 1;
return color;

Weighted Voronoi diagrams

Interesting results can be obtained by mixing different metric, or altering the “attraction” of the seeds by providing an extra coefficient to the shader. The distance is now:

half dist = distance(output.worldPos.xy, _Points[i].xy) + _Weights[i];

This takes the name of weighted Voronoi (also known as Dirichlet tessellation) and it can be used to generate beautiful effects, like Milan Domkář did with his foam:

01

Cone projection

cones.gifThere is a smarter approach to generate Voronoi diagrams (almost!) for free, and Chris Wellons is beautifully explaining it in its blog. You can generate a Voronoi tessellation by projecting cones out of the starting points. The cones will eventually intersect and seeing them it from the above will produce the same effect.

You can download the full Unity package in the last part of this tutorial.

Conclusion & Download

Conclusion

Voronoi diagrams are a way to tessellate the space which has many applications, from game development to city planning. This tutorial has shown how to generate them using a shader; you can download the complete Unity package here.

Other resources

Arrays & shaders: heatmaps in Unity

This tutorial explains how to pass arrays to shaders in Unity. This feature has been present for a long time, but is mostly undocumented. Unity 5.4.0 Beta 1 will introduce a proper API to pass arrays to shaders; this technique however will work with any previous version.

If you are using Unity 5.4+, please refer to the Arrays & Shaders in Unity 5.4+ tutorial.

Continue reading

Accessibility Design: Color Blindness

The filter

This tutorial will teach you how to create and use post-processing effects which simulate how colour blind players might experience your Unity game. One of my most anticipated games is The Witness; since it uses so many vibrant colours, it will be used as an example in this tutorial. This is how a player affected by red-green colour blindness (protanopia) might see it:

The image effect provided in this tutorial will help you understand which parts of your game are harder to see for color blind users.

Continue reading

Impossible Geometry: Non-Euclidean Cubes

This tutorial will teach you how to create non euclidean cubes in Unity, giving the illusion that each face is a door onto another dimension. This post is part of a series of tutorials on impossible geometries.

antichamber

This effect can be seen in many game, most notoriously Antichamber which uses it extensively.

You can download the Unity package here.
Continue reading

Screen shaders and image effects in Unity3D

Part 1, Part 2, Part 3, Part 4, Part 5, [download the Unity3D package]

If you are using Unity3D you may be familiar with image effects. They are scripts which, once attached to a camera, alter its rendering output. Despite being presented as standard C# scripts, the actual computation is done using shaders. So far, materials have been applied directly to geometry; they can also be used to render offscreen textures, making them ideal for postprocessing techniques. When shaders are used in this fashion, they are often referred as screen shaders.

Continue reading

Vertex and fragment shaders in Unity3D

Part 1, Part 2, Part 3, Part 4, Part 5, [download the Unity3D package]

The previous three posts of this tutorial have introduced surface shaders and how they can be used to specify physical properties (such as albedo, gloss and specular reflections) of the materials we want to model. The other type of shader available in Unity3D is called vertex and fragment shader. As the name suggests, the computation is done in two steps. Firstly, the geometry is passed through a function called (typically called vert) which can alter the position and data of each vertex. Then, the result goes through a frag function which finally outputs a colour.

Vertex and Fragment shader Continue reading

Physically Based Rendering and lighting models in Unity3D

Part 1, Part 2, Part 3, Part 4, Part 5, [download the Unity3D package]

Why is it colder at the poles and hotter on the equator? This question, which seems completely unrelated to shaders, is actually fundamental to understand how lighting models work. As explained in the previous part of this tutorial, surface shaders use a mathematical model to predict how light will reflect on triangles. Generally speaking, Unity supports two types of shading techniques, one for matte and one for specular materials. The former ones are perfect for opaque surfaces, while the latter ones simulate objects which reflections. The Maths behind these lighting models can get quite complicated, but understanding how they work is essential if you want to create your own, custom lighting effect. Up to Unity4.x, the default diffuse lighting model was based on the Lambertian reflectance. Continue reading

Surface shaders in Unity3D

Part 1, Part 2, Part 3, Part 4, Part 5

This is the second part of a series of posts on Unity3D shaders, and it will focus on surface shaders. As previously mentioned, shaders are special programs written in a language called Cg / HLSL which is executed by GPUs. They are used to draw triangles of your 3D models on the screen. Shaders are, in a nutshell, the code which represents how different materials are rendered. Surface shaders are introduced in Unity3D to simplify the way developers can define the look of their materials.

Surface shader Continue reading

A gentle introduction to shaders in Unity3D

Part 1, Part 2, Part 3, Part 4, Part 5

We can safely say that Unity3D has made game development easier for a lot of people. Something where it still has a long way to go is, with no doubt, shader coding. Often surrounded by mystery, a shader is a program specifically made to run on a GPU. It is, ultimately, what draws the triangles of your 3D models. Learning how to code shaders is essential if you want to give a special look to your game. Unity3D also uses them for postprocessing, making them essential for 2D games as well. This series of posts will gently introduce you to shader coding, and is oriented to developers with little to no knowledge about shaders.

Introduction

The diagram below loosely represents the three different entities which plays a role in the rendering workflow of Unity3D:

shader theory Continue reading