### 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

Most 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:

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.

#### Manhattan distance

As 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.

1 2 3 |
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.

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

Despite 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 is equivalent to multiply by ), even root and exponentiation are deeply connected. Remembering then , we can introduce the Minkowski distance:

When or it equivalent to the Manhattan or Euclidian distance, respectively.

1 2 3 |
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.

**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.

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!

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).

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.

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

Hey!

I know right? Unfortunately, I’ve been very busy so didn’t have the chance to write that part yet!