Understanding Geographical Coordinates

This series introduces the concept of trilateration. This technique can be applied to a wide range of problems, from indoor localisation to earthquake detection. This first post provides a general introduction to the concept of geographical coordinates, and how they can be effectively manipulated. The second post in the series, Positioning and Trilateration, will cover the actual techniques used to identify the position of an object given independent distance readings. Most trilateration tutorials require the measures from the sensors to be precise and consistent. The approach here presented, instead, is highly robust and can tolerate inaccurate readings.

Continue reading

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

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

The Transformation Matrix for 2D Games

This tutorial will introduce the Transformation Matrix, one of the standard technique to translate, rotate and scale 2D graphics. The first part of this series, A Gentle Primer on 2D Rotations, explaines some of the Maths that is be used here.

Continue reading

The Secrets of Colour Interpolation

This post discusses about the tricky problem of colour interpolation, and explores possible solutions. Many software and engines offer read-to-use functions to interpolate colours. In Unity, for instance, Color.Lerp is available and does its job pretty nicely. Use the interactive swatch below to see how Color.Lerp works.

There’s nothing wrong in using these functions, as long as you know what the deal with colour interpolation is.

Understanding interpolation

Interpolation is a technique that allows you to “fill a gap” between two numbers. Most APIs expose linear interpolation based on three parameters: the starting point a, the ending point b and a value t between 0 and 1 which moves along the segment that connected them:

    \[c = a + \left(b-a\right)*t\]

When t=0, a is returned. When t=1, a+\left(b-a\right)=b is returned instead. The beauty of this formula is that is easy to understand, efficient to implement, and it works in any dimension. Lerping in two dimension only requires to independently lerp the X and Y components. Lerping always returns points on the line that connects a and b, regardless of the number of dimensions. A standard RGB lerp can be done as such:

public static Color LerpRGB (Color a, Color b, float t)
{
	return new Color
	(
		a.r + (b.r - a.r) * t,
		a.g + (b.g - a.g) * t,
		a.b + (b.b - a.b) * t,
		a.a + (b.a - a.a) * t
	);
}
x

If it’s true that linear interpolation works as expected in three dimensions, the same cannot say for colours. There’s a fundamental difference between the XYZ and RGB spaces: the way the human eye perceive colours. While it make sense to connect two points in a 3D space with a line, the same doesn’t always apply for points in the RGB space. Interpolating the R, G and B components independently offers no guarantee on the hue of the intermediate colours. As Stuart Denman highlights in his Improve Color Blending, the RGB space of cyan and red meet halway in grey. A new hue appears because the RGB space does not capture how Humans perceive colours very well.

Hue Interpolation

A first attempt to compensate for this is to switch to different colour space, such as HSV (also known as HSB). It has been designed to be “artist-friendly”, grouping colours by hue and ignoring how they are created on screen.

x

The result, as it can be seen above, is rather disappointing. The reason is that interpolating the H component cycles through different hues. In this case we don’t have to go through green, but looping over the H space in the opposite direction.

HSVV255To implement an HSV lerping function we need to understand how these components are handled. For this example, we’ll assume all the HSV components range from 0 to 1. The following code is inspired from Improved Color Blending and relies on the ColorHSV Unity extension by C.J. Kimberlin:

public static Color LerpHSV (ColorHSV a, ColorHSV b, float t)
{
	// Hue interpolation
	float h;
	float d = b.h - a.h;
	if (a.h > b.h)
	{
		// Swap (a.h, b.h)
		var h3 = b.h2;
		b.h = a.h;
		a.h = h3;

		d = -d;
		t = 1 - t;
	}

	if (d > 0.5) // 180deg
	{
		a.h = a.h + 1; // 360deg
		h = ( a.h + t * (b.h - a.h) ) % 1; // 360deg
	}
	if (d <= 0.5) // 180deg
	{
		h = a.h + t * d
	}

	// Interpolates the rest
	return new ColorHSV
	(
		h,			// H
		a.s + t * (b.s-a.s),	// S
		a.v + t * (b.v-a.v),	// V
		a.a + t * (b.a-a.a)	// A
	);
}
x

For comparison, the linear lerping through HSV space is also shown together with the corrected lerping (HSV*).

Luminosity Interpolation

Despite all the effort, the transition still doesn’t look good. The reason is that even if we have correctly learped through the Hue component, different colours have different luminosities. As explained by Gregor Aisch in How To Avoid Equidistant HSV Colors, equidistant colours in the HSV space are not perceived as really equidistant. Even HSV colours with the same brightness (V) can differ in their perceived brightness and luminosity. Many aspects are responsible for this. The R, G and B components of a colour contributes in different ways the perceived luminosity, due to the way their respective photoreceptors work. Several attempts have been made to capture the non-linear relationships between R, G and B in a colour model. One of the most successful is the LCH (also known as HCL for Hue, Chroma and Lightness). Equidistant colours in the LCH space are also perceived as equidistant. The swatches below clearly shows how the LCH space provides a more uniform distribution of the colours.

x

The conversion from RGB to LCH is very expensive. This is because colours have to be converted into to intermediate spaces, the XYZ and LAB. A very good library which supports all of these conversions is chroma.js.

Using colours with equidistant perceived luminosity is essential for all these applications in which colours have a precise meaning, such as diagrams and heatmaps. Providing uniform luminosity is also important for colour blind people, as discussed in Accessibility Design: Color Blindness. A starting point to design a safe colour palette is ColorBrewer.

Conclusion

Interpolating colours by lerping their RGB components is the most common and lazy easy approach to tackle a very complex problem. If the interpolated colours need to be visible at the same time (for instance in a chart or a diagram) chances are you might need a more advance technique. Conversion from RGB to HSV are supported by most frameoworks, but if you want to go the extra mile you should adopt the LCH colour space.

x

This post was strongly inspired by the many works of Gregor Aisch.

https://vis4.net/blog/posts/avoid-equidistant-hsv-colors/

Related posts

External resources

Interactive Graphs in the Browser

Having worked both as a teacher and an artist, I know how important data visualisation is. This tutorial will teach you to create interactive network graphs with Python and JavaScript. You can have a go by dragging the nodes of the graph below…

You can find a high resolution version of the melancoil tree (2000x2000px, first 1000 numbers) here: PNG, SVG, HTML. Continue reading