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.

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

Lesson 2: Painting with randomness

# 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 $\stackrel{―}{AB}$ at the midpoint, $M$.
Now we can pick another point on the boundary, $P$ and make two triangles: $\mathrm{△}AMP$ and $\mathrm{△}BMP$.
Point $P$ is on the boundary so we know that $\stackrel{―}{AP}=\stackrel{―}{BP}$.
We also know that $\stackrel{―}{AM}=\stackrel{―}{BM}$ and that both triangles share side $\stackrel{―}{MP}$.
Since both triangles share three side lengths, they are similar triangles. You can learn more about similar triangles here.
Since $\mathrm{△}AMP$ and $\mathrm{△}BMP$ are similar we know that $\mathrm{\angle }AMP=\mathrm{\angle }BMP$. Since both angles lie on a straight line (line $AB$), we know that $\mathrm{\angle }AMP+\mathrm{\angle }BMP={180}^{\circ }$. So both angles must be ${90}^{\circ }$.
Therefore, the boundary between $A$ and $B$ is the perpendicular bisector of the line $AB$. 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

1. What is the term for point $V$ in relation to $\mathrm{△}ABC$?
2. 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=\left(30,60\right)$
$B=\left(90,80\right)$
$C=\left(150,20\right)$
Let's first calculate the equation for the perpendicular bisector of $\stackrel{―}{AB}$. We know this line will pass through the midpoint of $\stackrel{―}{AB}$ and have the negative inverse gradient of $\stackrel{―}{AB}$.
Learn how to calculate the equation of a perpendicular line here.
What is the midpoint of $\stackrel{―}{AB}$? $\left($
,
$\right)$

What is the gradient of $\stackrel{―}{AB}$?

What is the gradient of the perpendicular bisector of $\stackrel{―}{AB}$?

What is the equation for the perpendicular bisector of $\stackrel{―}{AB}$?
$y=$
$x+$

Now we have the equation for the perpendicular bisector of $\stackrel{―}{AB}$, we can use the same approach to calculate the perpendicular bisector of $\stackrel{―}{BC}$.
What is the equation of the perpendicular bisector of $\stackrel{―}{BC}$?
$y=$
$x+$

Now we have the equations for two perpendicular bisectors we can calculate where they intersect. If we use ${m}_{1}$ and ${b}_{1}$ to represent the gradient and $y$-intersect the first perpendicular bisector and ${m}_{2}$ and ${b}_{2}$ to represent the gradient and $y$-intersect the second perpendicular bisector, we have:
$\phantom{\rule{2em}{0ex}}\begin{array}{rl}y& ={m}_{1}x+{b}_{1}\\ y& ={m}_{2}x+{b}_{2}\end{array}$
So:
$\phantom{\rule{2em}{0ex}}\begin{array}{rl}{m}_{1}x+{b}_{1}& ={m}_{2}x+{b}_{2}\\ \\ {m}_{1}x-{m}_{2}x& ={b}_{2}-{b}_{1}\\ \\ \left({m}_{1}-{m}_{2}\right)x& ={b}_{2}-{b}_{1}\\ \\ x& =\frac{{b}_{2}-{b}_{1}}{{m}_{1}-{m}_{2}}\end{array}$
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.
Where do the perpendicular bisectors intersect? $\left($
,
$\right)$

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!
• 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.
• Will we be using readymade software to construct veronoi partitions or we need to write a program for it?
• Hi guys! what is a gradient in the second question of The Algebra Of Voronoi Partition? I don't quite understand the question.
thanxs
• 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.
• 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!
• Anyone wanna say HI (or need any help)(LOL I idk what to do)!!
• Hey! what's the meaning of this AB thing? Anybody got a doubt in this?
• how do we do this and what grade is this?
• 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.
• This bonus is VERY hard I got all of them wrong sorry :[ ;[ cry..
• Are those all we need to know?
• 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)
• The m is the gradient (slope) of the perpendicular bisector, which is the opposite flipped version of AB's gradient. So if AB's gradient is 1/3, then the flipped version would be -3/1 or -3 simplified. Think of the line being flipped, so it is opposite for the bisector.
You put 1/3 in for m, when it should have been the opposite -3. You were right in putting 60 in there, as it was the x-value for the midpoint.
We also have to put in the y-value of the midpoint in, so it would look like this

y = mx +b
70 = -3(60) +b

When we solve -3(60) we get -180, and add it over to 70 to get 250
70 = -180 +b
+180 +180
250 = b

Making b = 250

so overall the answer would be
y = -3x + 250

These are the basic rules of algebra, and they don't give a lot of hints wihtout giving you the answer.
I know you wrote this 7 years ago, but i hope this is helpful to anyone trying to figure out this problem

If you also want to check your last answer, you should have gotten 80 (x), 10(y) for the vertex coordinates
(1 vote)