The Autocorrelation Function

The purpose of this tutorial is to show a simple technique to estimate periodicity in time series, called autocorrelation.

This tutorial is part of a longer series that focuses on how to analyse time series.

Continue reading

Time Series Decomposition

This tutorial will teach you how you can extract valuable information from time series, such as your sold copies on Steam or your Google Analytics. The previous part of this series introduced a technique called moving average, which has been used to attenuate the effects of noise in a signal. When signals represent an event that evolves over time, we are in front of a time series. Classical decomposition is a technique that attempts to find the main trends within time series.

Continue reading

How to Simulate Smoke with Shaders

This post will show how to simulate the diffusion of smoke using shaders. This part of the tutorial focuses on the Maths and the code necessary to recreate the smoke effect. To learn how to set up your project, check out the first part: How to Use Shaders For Simulations.

texture6

Continue reading

To Voronoi and Beyond

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 |\]

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.

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.

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.

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.

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:

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.

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:

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

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