Main content

## Pixar in a Box

### Course: Pixar in a Box > Unit 8

Lesson 2: Painting with randomness- Start here!
- Looking at different resolutions
- Resolution challenge
- One dimensional noise
- One dimensional noise
- Perlin noise (1D)
- Multi-resolution noise
- Perlin noise (2D)
- Two dimensional noise
- Painting your dino skin
- Make your own dino skin 2
- Bonus Challenge

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Bonus Challenge

This article gives a step-by-step guide to how the boundary lines in a Voronoi diagram can be calculated.

# The geometry of Voronoi partitions

A Voronoi partition is made by taking a set of sites spread on the screen and drawing boundaries between the sites, in such a way that each boundary is exactly halfway between the sites on either side of it.

## Dividing two sites

Let's start with two sites, A and B. Every point on the line that divides them, is an equal distance from A and from B. What other properties does this line have?

The first thing we can do is to draw a line segment from A to B. Since all the points on the boundary are an equal distance from A and from B, the boundary will cross start overline, A, B, end overline at the midpoint, M.

You can learn more about midpoints here.

Now we can pick another point on the boundary, P and make two triangles: triangle, A, M, P and triangle, B, M, P.

Point P is on the boundary so we know that start overline, A, P, end overline, equals, start overline, B, P, end overline.

We also know that start overline, A, M, end overline, equals, start overline, B, M, end overline and that both triangles share side start overline, M, P, end overline.

We also know that start overline, A, M, end overline, equals, start overline, B, M, end overline and that both triangles share side start overline, M, P, end overline.

Since both triangles share three side lengths, they are

**similar triangles**. You can learn more about similar triangles here.Since triangle, A, M, P and triangle, B, M, P are similar we know that angle, A, M, P, equals, angle, B, M, P. Since both angles lie on a straight line (line A, B), we know that angle, A, M, P, plus, angle, B, M, P, equals, 180, degrees. So both angles must be 90, degrees.

Therefore, the boundary between A and B is the

**perpendicular bisector**of the line A, B. You can learn more about perpendicular bisectors here.## Dividing three sites

So we know the boundary between two sites is a perpendicular bisector of the line joining those sites. How can we use this information to find the Voronoi partition of three sites? First let's start by drawing lines between the sites.

Next we find the midpoints of the edges and draw the perpendicular bisector for each edge.

Notice that the three perpendicular bisectors meet at a point, V. Since each perpendicular bisector is an equal distance from two sites and V lies on all three of them, V must be an equal distance from all three site. V is therefore a vertex in our Voronoi partition. We can draw our final boundaries by starting from this vertex and continuing through each of the midpoints.

### Questions

- What is the term for point V in relation to triangle, A, B, C?
- Under what circumstances will the perpendicular bisectors not intersect each other?

# The algebra of Voronoi partitions

Now we've seen some of the geometry of a simple Voronoi partition, let's use algebra to calculate the coordinates for a vertex in a Voronoi partition.

Say we have three sites, A, B, and C with coordinates:

A, equals, left parenthesis, 30, comma, 60, right parenthesis

B, equals, left parenthesis, 90, comma, 80, right parenthesis

C, equals, left parenthesis, 150, comma, 20, right parenthesis

B, equals, left parenthesis, 90, comma, 80, right parenthesis

C, equals, left parenthesis, 150, comma, 20, right parenthesis

Let's first calculate the equation for the perpendicular bisector of start overline, A, B, end overline. We know this line will pass through the midpoint of start overline, A, B, end overline and have the negative inverse gradient of start overline, A, B, end overline.

Learn how to calculate the equation of a perpendicular line here.

Now we have the equation for the perpendicular bisector of start overline, A, B, end overline, we can use the same approach to calculate the perpendicular bisector of start overline, B, C, end overline.

Now we have the equations for two perpendicular bisectors we can calculate where they intersect. If we use m, start subscript, 1, end subscript and b, start subscript, 1, end subscript to represent the gradient and y-intersect the first perpendicular bisector and m, start subscript, 2, end subscript and b, start subscript, 2, end subscript to represent the gradient and y-intersect the second perpendicular bisector, we have:

So:

$\qquad \begin{aligned} m_1 x + b_1 &= m_2 x + b_2 \\ \\ m_1 x - m_2 x &= b_2 - b_1 \\ \\ (m_1 - m_2)x &= b_2 - b_1 \\ \\ x &=\dfrac{b_2 - b_1}{m_1 - m_2} \end{aligned}$

$\qquad \begin{aligned} m_1 x + b_1 &= m_2 x + b_2 \\ \\ m_1 x - m_2 x &= b_2 - b_1 \\ \\ (m_1 - m_2)x &= b_2 - b_1 \\ \\ x &=\dfrac{b_2 - b_1}{m_1 - m_2} \end{aligned}$

Plug the values for the gradients and y-intersects into the equation to find the x coordinate of the intersection point. Then plug the value for x into one of the equations for a perpendicular bisector to find the y coordinate.

Now imagine calculating this for hundreds of sites. This is why we use computers!

## Want to join the conversation?

- Hi there! I really love all the Pixar lessons and am so happy you guys added the "Patterns" program on! This course was personally my favorite, and I would love to do more of this kind of stuff. I was wondering though, does this certain category have a certain name? I also wrote in earlier this year about character modeling and I was wondering if there is a field that ties both of these categories together? Also it would be awesome if you could attach a list of field names that relate to these subjects. Thank you so much! I appreciate all the time and effort you put into these lessons!(64 votes)
- The practice of creating images using mathematical formulae and algorithms is called "computational imaging." It is a pretty narrow application of more general math, geometry, and graphics programming skills.

Synthetic imagery and patterns are very commonly used in character modeling—adding displacement detail and, of course, texture to a model. If you experiment with the program ZBrush, you can see how patterns like Perlin noise can be added directly to a character mesh. I think you can do it in Blender's sculpt mode, too, but don't quote me on that.

If you're looking for educational programs to pursue, look for schools that offer things like visual effects, animation, video game design, computer graphics, interactive media, virtual reality, and similar things. You could also come at it through the research side by studying mathematics, computer science, or image processing.

If you'd like to learn a lot more about modeling, I recommend the book [Digital] Modeling by William Vaughan from New Riders. ISBN-13: 978-0321700896

In fact, the entire [Digital] series is pretty good. [Digital] Texturing and Painting by Owen Demers (ISBN-13: 978-0735709188) has some nice stuff in it about pattern creation and applying them to a character.(23 votes)

- Will we be using readymade software to construct veronoi partitions or we need to write a program for it?(12 votes)
- Hi guys! what is a gradient in the second question of The Algebra Of Voronoi Partition? I don't quite understand the question.

thanxs(5 votes)- Gradient is another word for slope. "Negative inverse gradient" is the same as saying "negative reciprocal." That is, if the slope of the line AB is 3/4, its perpendicular bisector has a slope of -4/3: Negative and inverted.(5 votes)

- How does this help you with patterns in real life?(6 votes)
- Well, if you want to be an animator or the like when you grow up, it would help you to get a basic knowledge of the tools animators use in their work. That's the cool thing about these courses--they give you a sense of what different jobs/projects would be like, and let you try things out yourself. I hope that answers your question!(3 votes)

- Anyone wanna say HI (or need any help)(LOL I idk what to do)!!(4 votes)
- how do we do this and what grade is this?(2 votes)
- This is about 8th to 9th grade math. As for finding out how to do it, if you click on
*[Hint]*, you'll get a link on how to calculate the given question.(2 votes)

- This bonus is VERY hard I got all of them wrong sorry :[ ;[ cry..(2 votes)
- Are those all we need to know?(2 votes)
- I'm on the "What is the equation for the perpendicular bisector of AB?" and frankly I'm not sure why my answer is not correct. They want m to be the gradient of AB, not the perpendicular bisector, right? So then m = 1/3. I did 60 = (1/3)(30) + b and got b = 50. But the answer is wrong. :( Could someone clarify this, please?(1 vote)
- var saveData = {

edgeWidth: 98,

jitter: 50,

extrude: 10,

skinColor: -11582429,

scaleColor1: -4938931,

scaleColor2: -11503476,

skinAmplitudes: [0,0,0],

scaleAmplitudes: [0,0,0],

sites: [[145.939,498.243],[306.915,495.932],[-63.136,495.183],[79.896,479.111],[401.756,467.633],[23.797,459.774],[219.542,458.266],[452.679,457.042],[355.548,448.305],[145.873,443.297],[-75.677,430.6],[262.304,426.482],[59.483,424.111],[-9.662,417.404],[106.166,402.259],[417.288,394.01],[477.18,390.161],[318.157,385.962],[29.253,378.857],[198.932,370.622],[147.264,365.816],[367.106,365.018],[-28.001,362.074],[459.348,342.386],[-84.528,339.497],[151,336],[184,335],[267.634,330.264],[128.529,313.306],[228,311],[70.904,310.494],[364.505,309.573],[186.812,301.577],[16.096,299.534],[303.241,291.077],[-64.176,289.317],[127,289],[267,283],[432.781,263.325],[483.547,260.64],[239.683,255.877],[118.104,250.14],[65.896,249.123],[167.91,245.259],[258,239],[329.228,236.652],[379.975,235.89],[124,224],[-13.928,217.474],[490.167,205.445],[265.464,201.037],[199,196],[33.048,195.763],[138,194],[116,193],[164.5,187.596],[239,184],[344.247,174.798],[114.551,171.571],[442.833,170.625],[-64.726,167.623],[220.404,166.731],[53.168,148.434],[115,143],[401.209,140.471],[225,133],[309.888,131.798],[171.19,131.788],[90,130],[-7.047,129.462],[494.535,116.778],[263.524,112.745],[-57.682,107.96],[124.334,107.313],[208.6,98.137],[445.441,95.467],[67.069,90.292],[376.515,90.239],[187,75],[113,72],[292.501,71.871],[16.563,71.817],[158.462,69.219],[237.991,48.27],[85.204,41.388],[-36.941,40.876],[440.924,34.536],[494.54,24.955],[327.362,18.121],[150.563,-0.134],[274.609,-3.58],[203.11,-4.027],[372.695,-6.224],[4.424,-10.262],[467.277,-18.473],[329.895,-34.524],[96.012,-43.1],[-38.056,-47.609],[190.599,-61.365],[419.141,-63.567],[263.144,-70.134],[49.338,-77.015],]

};

Paste the code above into:

https://www.khanacademy.org/pixar/a/5620766808

✖(1 vote)