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.

Want to join the conversation?

  • leafers sapling style avatar for user Peter Collingridge
    (36 votes)
    Default Khan Academy avatar avatar for user
  • purple pi purple style avatar for user St s
    What does irregular shape mean?
    (9 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Drew
    does pixar use texture mapping?
    (8 votes)
    Default Khan Academy avatar avatar for user
    • sneak peak blue style avatar for user Miles Waugh
      Texture mapping can also be really useful for pieces of paper and signs. But procedural textures, like the Voronoi Partition, Perlin Noise, or Musgrave, are fully mathematical, and therefore have essentially infinite resolution. If you texture mapped the dinosaur's leg, for example, closeups would show pixels, and you would need a monstrously large texture to avoid pixels. You can't use a smaller texture and just tile it, because not only does the voronoi density have to change smoothly along its body, but there would be visible tiling and repeats in the texture. With a procedural texture, the dinosaur can have smoothly transitioning texture densities, no repeats, and nice-looking closeup shots – and remember, these procedural texture are also commonly mixed together in different ways! It is also essential in objects like CGI planets, as you don't want to just copy planets in the solar system imaged by satellites (that would be obvious), and you want really high detail. Satellite data of other planets is very patchy, varies in resolution, and has many seams where the color abruptly changes – these can of course be fixed, but, again, the audience may recognize that planet. It is just a lot more practical to use math to describe textures for that planet. But keep in mind – in some areas, these can be mixed!! In the case of paper, it may be useful to apply a musgrave or perlin noise texture as either displacement or a normal map to the paper, to increase realism. Both textures can be fractalized, meaning you can zoom into an extreme closeup shot of the dirt or something, and see the beautiful procedural detail. Lastly, like the dinosaurs here, many times you want to create something new, that cannot be photographed in real life.
      (5 votes)
  • duskpin ultimate style avatar for user Haley Millard
    It will not let me watch the video again, a glitch?
    (8 votes)
    Default Khan Academy avatar avatar for user
  • mr pants green style avatar for user new.sheng
    Why these sites are grown in the same rate? Does the size of one of the sites depend on the distance between it to others?
    (6 votes)
    Default Khan Academy avatar avatar for user
  • starky tree style avatar for user Maddie
    Poor cake, never got to show off it's beauty. :(
    (7 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user lisa  dudek
    How do we represent the correct answer mathematically? RE:boarder vw distance = the same distance from site A & site C
    (1 vote)
    Default Khan Academy avatar avatar for user
    • leaf blue style avatar for user KCF
      This is discussed in the second section of the Patterns course in the "Bonus Challenge". Basically, we're using a bit of algebra in the slope-intercept form to find to perpendicular bisectors of a triangle that matches up with all three points surrounding the vertex. Where they intersect is the vertex of the Voronoi partition.

      I encourage you to check out the proof and algebra in the next section.
      (5 votes)
  • aqualine ultimate style avatar for user Fading Pixel
    at when she was talking about cells then she said sites i think instead of saying sites you should say the nucleus because when you think of a cell you think of the nucleus of the cell
    (3 votes)
    Default Khan Academy avatar avatar for user
  • male robot johnny style avatar for user sumanththodem
    i don't understand how all the sites have same distance
    (2 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user NR1213
      The center points or starting point of each cell is random, so they aren't equally split up.

      The walls are formed at the midpoint between 2 center points. So each wall is equal distance from the center of each cell.

      With 3 cells, the the walls between each center point are equal distance from the center point....then the spot where 3 walls meet is a vertex point and that is equal distance from all three center points.

      It's a triangle thing. The if each wall is a midpoint between 2 centers, the midpoint between all three centers will naturally have to touch all three walls....the only way for that to work is for a vertex to form that is equally distance from each center.
      (1 vote)
  • blobby green style avatar for user Arshiya Kapil
    Why do the subtitles call them "blonde" and "brunette" women?
    (2 votes)
    Default Khan Academy avatar avatar for user

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)