in maths, shader, tutorial

To Voronoi and Beyond

Share Button

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.
📧 Stay updated

A new tutorial is released every week.

💖 Support this blog

This websites exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

Paypal
Ko-fi
Twitter_logo

Write a Comment

Comment

  1. Hi alan, i am getting into VR and something that i think would really improve immersion is dynamic voronoi object shattering. So if you could please do that tutorial on the fracturing and destruction remake it would be highly appreciated!

    P.S. I am 13 and have already tried making a voronoi system but it was limited to 2D, so yet again that tutorial would be greatly appreciated!

    • Hey! 😀

      Thank you for your message! Voronoi facture is super cool! The only issues is that is incredibly tedious to code. The reason is that you need to do mesh intersections, and splitting them to different geometries. If I am going to do it, it will be over many posts!

      Hopefully I’ll manage to find the time to do it! XD

      • Ok thanks, today I got a triangle exploding system going that gets each triangle and adds a point in the middle to create a prism, it’ll do for now so take as long as you’d like!

  2. Interesting … I just replied to someone on another page about him complaining about Alan charging via Patreon.
    Now I read above “A future post will show how to replicate [Fracturing & Destruction] effect at no cost.”
    Makes me think …
    I still think that definitely for developing things (e.g. games) it is worth paying if it safes me time. For me personally, I am as well willing to pay for leisure things (e.g. movies, books).

  3. Just tried to take a look into the unity example, but it diesnt seem to work anymore. Looking inside the frame debuger shows, that the arrays are not filled with the technique which worked in older versions. I am using Unity 5.60f3 atm.

  4. This would be a great tutorial to finish, breaking things is a very useful and not well covered topic on other blogs.