If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Voronoi Partition

Overview of Voronoi partitions. You can explore the interactive program used in this video here.

Video transcript

- [Woman] Now that you're comfortable reading shading packets, let's get to work. - To begin, let's step back and simplify the problem. A dino leg is essentially a cylinder, with claws at the bottom. - Let's ignore the claws for the moment. - And if we unwrap the cylinder, we get a flat rectangle, or a 2D plane. - We can do all the work like this in a flat plane, and then wrap it up whenever we wanna test it out. Let's first think about the geometry of our dino scales. Each scale is an irregular shape, and all of these different scales need to fit together like a puzzle. - At Pixar we use a really cool trick to generate these kinds of patterns. It's known as a Voronoi diagram. It's based on a pattern we see all over the place in the natural world. From the spots on a giraffe, to the spots that form when mud dries. - And I love that we can explain the math behind Voronoi patterns with bubbles. - [Brunette Woman] If we fill a container with bubbles, like this, they squish together and we get the same pattern based on where the bubbles touch. - [Dark-Haired Woman] Let's think about the geometry of what's going on here. We start by places a few points somewhere on the plane, doesn't matter where. - [Brunette Woman] Imagine they are tiny bubbles, let's call these sites. - [Dark-Haired Woman] And then we blow them up into larger bubbles. - [Brunette Woman] Eventually the neighboring bubbles collide at a single point. As they expand, this grows into a line where they squish together. - [Dark-Haired Woman] These bubble boundaries is where we draw our lines. - [Brunette Woman] And watch what happens when we do this with many sites scattered about. We get this irregular puzzle pattern. - [Dark-Haired Woman] And that's it. A Voronoi pattern. - [Brunette Woman] Or Voronoi partition, if you really wanna show off. - [Dark-Haired Woman] We'll call each of these bubble regions a cell. So we have sites and cells. - [Brunette Woman] And there are some really interesting properties here. The border of each cell is always the same distance to the two nearest sites. - [Dark-Haired Woman] And wherever three lines meet, we get a point, or a vertex right here. And this is equally distant to the three nearest sides, all thanks to the awesome power of bubble-- ah, math. (both women laugh) - Let's stop here and make sure that you understand how to draw these Voronoi patterns. - The following exercise will get you thinking about how these work. It's also a great time to grab a pencil and paper. Remember, doodling is your friend. - Do you have a good story about Voronoi patterns? - I do. When we were working on The Incredibles, we had this cake that was absolutely beautiful, and it was made for Bob Parr was gonna take a big bite out of it, and it was full of these beautiful bubbles, and the crest was shiny, and it was moist and it was really really gorgeous. And then the story changed a little bit, and the shot ended up being filmed all at night. - [Brunette Woman] So you can never see all those beautiful Voronoi bubbles. - [Dark-Haired Woman] Sounds delicious. (both women laugh)