hi I'm Kerry Ann and welcome to crash
course computer science over the past
five episodes we've worked up from
text-based teletype interfaces to
pixelated bitmap graphics then last
episode we covered graphical user
interfaces and all their eerie gooey
richness all of these examples have been
2d but of course we're living in a 3d
world and I'm a three-dimensional girl
so today we're going to talk about some
fundamental methods in 3d computer
graphics and how you render them onto a
2d screen
[Music]
as we discussed in episode 24 we can
write functions that draw a line between
any two points like a and B by
manipulating the x and y coordinates of
points a and B we can manipulate the
line in 3d graphics points of not just
two coordinates but three x y&z or Z but
I'm going to say it of course we don't
have XYZ coordinates on a 2d computer
screen so graphics algorithms are
responsible for flattening 3d
coordinates onto a 2d plane this process
is known as 3d projection once all of
the points have been converted from 3d
to 2d we can use the regular 2d line
drawing function to connect the dots
literally this is called wireframe
rendering imagine building a cube out of
chopsticks and shining a flashlight on
it the shadow it casts onto your wall
it's projection is flat if you rotate
the cube around you can see it's a 3d
object even though it's a flat
projection this transformation from 3d
to 2d is exactly what your computer is
doing just with a lot more math and less
chopsticks there are several types of 3d
projection what you're seeing right now
is an orthographic projection where for
example the parallel slides in the cube
appear as parallel in the projection in
the real 3d world though parallel lines
converge as they get further from the
viewer like a road going to the horizon
this type of 3d projection is called
perspective projection it's the same
process just with different math
sometimes you want perspective and
sometimes you don't the choice is up to
the developer simple shapes like cubes
are easily defined by straight lines but
for more complex shapes triangles are
better what are called polygons in 3d
graphics look at this beautiful teapot
made out of polygons a collection of
polygons like this is a mesh the denser
the mesh the smoother the curves and the
finer the details but that also
increases the polygon count which means
more work for the computer game
designers have to carefully balance
model fidelity versus polygon count
because if the count goes too high the
framerate of an animation drops below
what users perceive as smooth for this
reason there are algorithms for
simplifying meshes the reason triangles
are used or not squares or polygons or
some other more complex shape is
simplicity three points in space and
ambiguously define a plane if you give
me three points in a 3d space I
draw a plane through it there is only
one single answer this isn't guaranteed
to be true for shapes with four or more
points also two points aren't enough to
define a plane only a line so three is
the perfect a minimal number triangles
for the win wireframe rendering is cool
and all sorts of retro but of course 3d
graphics could also be filled the
classic algorithm for doing this is
called scanline rendering first
developed in 1967 at the university of
utah for a simple example let's consider
just one polygon our job here is to
figure out how this polygon translates
to filled pixels on a computer screen
so let's first overlay a grid of pixels
to fill the scanline algorithm starts by
reading the three points that make up
the polygons and finding the lowest and
highest y-values it will only consider
rows between these two points then the
algorithm works down one row at a time
in each row it calculates where a line
running through the center of a row
intersects with the side of the polygon
because polygons are triangles if you
intersect one line you have to intersect
with another it's guaranteed the job of
the scanline algorithm is to fill in the
pixels between the two intersections
let's see how this works on the first
row we look at we intersect here and
here the algorithm then colors in all
the pixels between those two
intersections and this just continues
row by row which is why it's called
scanline rendering when we hit the
bottom of the polygon we've done the
rate at which a computer fills in
polygons it's called the fill rate
admittedly this is a pretty ugly filled
polygon it has one unknown as jaggies
those rough edges this effect is less
pronounced when using smaller pixels but
nonetheless you see these in games all
the time especially on lower powered
platforms one method to soften this
effect is anti-aliasing instead of
filling pixels in a polygon with the
same color we can adjust the color based
on how much the polygon cuts through
each pixel if a pixel is entirely inside
of a polygon it gets fully colored but
if the polygon only grazes a pixel it'll
get a lighter shade this feathering of
the edges is much more pleasant for the
eyes anti-aliasing is used all over the
place including in 2d graphics like
fonts and icons if you leanin real close
to your monitor closer closer you'll see
all the fonts in your browser at
anti-aliased so smooth in a 3d scene
there are polygons that are part
objects-- in the back
me in the front and just about
everywhere only some are visible because
some objects are hidden behind other
objects in the scene what's called
occlusion the most straightforward way
to handle this is to use a saw algorithm
and arrange all the polygons in the
scene from farthest to nearest then
render them in that order
this is called the painters algorithm
because painters also have to start with
the background and then increasingly
work up to foreground elements consider
this example scene with three
overlapping polygons to make things
easier to follow we're going to color
the polygons differently also for
simplicity we'll assume these polygons
are all parallel to the screen but in a
real program like a game the polygons
can be tilted in 3d space our three
polygons a B and C are at distance
twenty twelve and fourteen the first
thing that painters algorithm does is
saw all the polygons from farthest to
nearest now they're in order we can use
scanline rendering to fill each polygon
one at a time
we start with polygon a the farthest one
away then we repeat the process for the
next farthest polygon in this case C and
then we'll repeat this again for
polygons B now we're all done and you
can see the ordering is correct the
polygons that are closer are in front an
alternative method for handling
occlusion is called z-buffering achieves
the same output as before but with a
different algorithm let's go back to our
previous example before it was sorted
that's because this algorithm doesn't
need to saw any polygons which makes it
faster is sure dead buffering keeps
track of the closest distance to a
polygon for every pixel in the scene it
does this by maintaining a Zed buffer
which is just a matrix of values that
sits in memory at first every pixel is
initialized to infinity then Zed
buffering starts with the first polygon
in its list in this case it's a it
follows the same logic as the scanline
algorithm but instead of coloring in
pixels it checks the distance of the
polygons versus what's recorded in its
Zed buffer it records the lower of the
two values for our polygons a with a
distance of 20 it wins against infinity
every time when it's done with polygons
a it moves on to the next polygon in its
list and the same thing happens now
because we didn't sort the polygons it's
not always the case that later polygons
overwrite high values in the case of
polygons see only some of the valleys in
the Z buffer get new minimum distances
this completed Z buffer is used in
conjunction with a fancier version of
scanline renderer
they're not only tests for line
intersection but also does a lookup to
see if that pixel will even be visible
in the final scene if it's not the
algorithm skips it and moves on an
interesting problem arises when two
polygons have the same distance
like if polygon a and B are both a
distance of 20 which one do you draw on
top polygons are constantly being
shuffled around in memory and changing
their access order plus rounding errors
are inherent in floating point
computations so which one gets drawn on
top is often unpredictable the result is
a flickering effect called z-fighting
which if you've played 3d games you've
no doubt encountered speaking of
glitches another common optimization in
3d graphics is called back face culling
if you think about it a triangle has two
sides a front and a back
with something like the head of an
avatar or the ground in the game you
should only ever seen one side the side
facing outwards so for safe processing
time the back side of polygons are often
ignored in the rendering pipeline which
cuts the number of polygon faces to
consider in half this is great except
when there's a bug that lets you get
inside of those objects and look
outwards then the avatar head or ground
becomes invisible moving on we need to
talk about lighting also known as
shading because if it's a 3d scene the
lighting should vary over the surface of
objects let's go back to our teapot mesh
with scanline rendering coloring in all
the polygons our teapot looks like this
not very 3d so let's have some lighting
to enhance the realism as an example
we'll pick three polygons from different
parts of our teapot unlike our previous
examples we're now going to consider how
these polygons are oriented in 3d space
they're no longer parallel to the screen
but rather tilted in different 3d
directions the direction they face is
called the surface normal and we can
visualize that direction with a little
3d arrow that's perpendicular to the
polygon surface now let's add a light
source each polygon is going to be
illuminated a different amount some will
appear brighter because their angle
causes more light to be reflected
towards the viewer for example the
bottom most polygon is tilted downwards
away from the light source which means
it's going to be dark in a similar way
the rightmost polygon is slightly facing
away from the light so it will be
partially illuminated and finally
there's the upper left polygon its angle
means it will reflect light from the
light source towards our view so it will
appear bright if we do this for every
colleague on our teapot looks like this
which is much more realistic this
approach is called flat shading and it's
the most basic lighting algorithm
unfortunately it also makes all those
polygon boundaries really noticeable and
the mesh doesn't look smooth
for this reason more advanced lighting
algorithms were developed such as bureau
shading and Phong shading instead of
coloring in polygons just using one
color they vary the color across the
surface in clever ways which results in
much nicer output we also need to talk
about textures which in graphics refers
to the look of a surface rather than its
feel like we've lighting there are many
algorithms with all sorts of fancy
effects the simplest is texture mapping
to visualize this process let's go back
to our single polygons when we're
filling this in using scanline rendering
we can look up what color to use at
every pixel according to a texture image
saved in memory to do this we need a
mapping between the polygons coordinates
and the textures coordinates let's jump
to the first pixel the scanline
rendering needs to fill in the texturing
algorithm will consult the texture in
memory take the average color from the
corresponding region and fill the
polygons accordingly this process
repeats for all pixels in the polygons
and that's how we get textures if you
combine all the techniques we've talked
about this episode you get a wonderfully
funky little teapot and this teapot can
sit in an even bigger scene comprised of
millions of polygons rendering a scene
like this takes a fair amount of
computation but importantly it's the
same type of calculations being
performed over and over and over again
for many millions of polygons scan line
filling anti-aliasing lighting and
texturing however there are a couple of
ways to make this much faster first off
we can speed things up by having special
Hardware with extra bells and whistles
just for these specific types of
computations making them lightning fast
and secondly we can divide up a 3d scene
into many smaller parts and then render
all the pieces in parallel rather than
sequentially CPUs aren't designed for
this so they aren't particularly fast so
computer engineers created special
processors just for graphics a GPU or
graphics processing unit these can be
found on graphics cards inside of your
computer along with Ram reserved for
graphics this is where all the meshes
and textures live allowing them to be
accessed super fast by many different
cause of the GPU all at once a modern
graphics card like a GeForce GTX 1080 Ti
contains 3584 processing cores offering
massive paralyzation it can process
hundreds of millions of polygons every
second ok that concludes our Whistlestop
tour of 3d graphics next week we switch
topics entirely I'll ping you then crash
course computer science is produced in
association with PBS Digital Studios at
their channel you can check out a
playlist of shows like gross science
ACS reactions and the art assignment
this episode was filmed at the chavez
stacey emigholz studio in indianapolis
indiana and it was made with the help of
all these nice people and our wonderful
graphics too you thought cafe thanks for
watching
and try turning your off them and back
on again
[Music]
you