3D Graphics: Crash Course Computer Science #27

0:03 Hi, I’m Carrie Anne, and welcome to CrashCourse Computer Science!

0:05 Over the past five episodes, we’ve worked up from text-based

0:09 teletype interfaces to pixelated bitmapped graphics.

0:11 Then, last episode, we covered Graphical User

0:14 Interfaces and all their “Ooey Gooey” richness.

0:17 All of these examples have been 2D.

0:18 But of course “we are living in a 3D world,

0:21 and I’m a 3 dimensional girl!” So today,

0:23 we're going to talk about some fundamental methods in 3D

0:26 computer graphics and how you render them onto a 2D screen.

0:29 INTRO As we discussed in episode 24 we can write functions

0:41 that draw a line between any two points like A and B.

0:44 By manipulating the X and Y coordinates of points A and B,

0:48 we can manipulate the line.

0:49 In 3D graphics, points have not just two coordinates, but three— X, Y and Z.

0:54 Or “zee” but I’m going to say “zed”.

0:56 Of course, we don’t have X/Y/Z coordinates on a 2D computer screen,

1:00 so graphics algorithms are responsible for “flattening”

1:02 3D coordinates onto a 2D plane.

1:05 This process is known as 3D Projection.

1:07 Once all of the points have been converted from 3D to 2D,

1:10 we can use the regular 2D line drawing function to connect the dots… literally.

1:15 This is called Wireframe Rendering.

1:17 Imagine building a cube out of chopsticks, and shining a flashlight on it.

1:20 The shadow it casts onto your wall– its projection– is flat.

1:24 If you rotate the cube around,

1:25 you can see it’s a 3D object, even though it’s a flat projection.

1:29 This transformation from 3D to 2D is exactly what your computer is doing,

1:33 just with a lot more math… and less chopsticks.

1:36 There are several types of 3D Projection.

1:38 What you’re seeing right now is an Orthographic Projection, where, for example,

1:42 the parallel sides in the cube appear as parallel in the projection.

1:47 In the real 3D world through,

1:48 parallel lines converge as they get further from the viewer,

1:50 like a road going to the horizon.

1:53 This type of 3D projection is called Perspective Projection.

1:56 It’s the same process, just with different math.

1:58 Sometimes you want perspective and sometimes you

2:01 don’t— the choice is up to the developer.

2:03 Simple shapes, like cubes, are easily defined by straight lines.

2:06 But for more complex shapes,

2:08 triangles are better— what are called polygons in 3D graphics.

2:11 Look at this beautiful teapot made out of polygons.

2:14 A collection of polygons like this is a mesh.

2:17 The denser the mesh, the smoother the curves and the finer the details.

2:20 But, that also increases the polygon count,

2:22 which means more work for the computer.

2:24 Game designers have to carefully balance model fidelity vs.

2:28 polygon count, because if the count goes too high,

2:31 the framerate of an animation drops below what users perceive as smooth.

2:34 For this reason, there are algorithms for simplifying meshes.

2:37 The reason triangles are used, and not squares, or polygons,

2:40 or some other more complex shape is simplicity:

2:43 three points in space unambiguously define a plane.

2:46 If you give me three points in a 3D space,

2:49 I can draw a plane through it- there is only one..

2:52 single..

2:52 answer.

2:52 This isn’t guaranteed to be true for shapes with four or more points.

2:56 Also, two points aren’t enough to define a plane,

2:58 only a line, so three is the perfect and minimal number.

3:01 Triangles for the win!

3:03 Wireframe rendering is cool and all– sorta retro–

3:06 but of course 3D graphics can also be filled.

3:09 The classic algorithm for doing this is called Scanline Rendering,

3:12 first developed in 1967 at the University of Utah.

3:15 For a simple example, let’s consider just one polygon.

3:19 Our job here is to figure out how

3:21 this polygon translates to filled pixels on a computer screen,

3:23 so let’s first overlay a grid of pixels to fill.

3:26 The scanline algorithm starts by reading

3:28 the three points that make up the polygon,

3:30 and finding the lowest and highest Y values.

3:32 It will only consider rows between these two points.

3:36 Then, the algorithm works down one row at a time.

3:38 In each row, it calculates where a line– running through

3:41 the center of a row– intersects with the side of the polygon.

3:44 Because polygons are triangles, if you intersect one line,

3:47 you have to intersect with another.

3:49 It’s guaranteed!

3:49 The job of the scanline algorithm is

3:51 to fill in the pixels between the two intersections.

3:54 Let’s see how this works.

3:56 On the first row we look at we intersect here and here.

3:59 The algorithm then colors in all pixels between those two intersections.

4:03 And this just continues, row by row, which is why it’s called Scan...

4:07 Line...

4:07 Rendering.

4:08 When we hit the bottom of the polygon, we’re done.

4:10 The rate at which a computer fills in polygons is called the fillrate.

4:13 Admittedly, this is a pretty ugly filled polygon.

4:15 It has what are known as “Jaggies”— those rough edges.

4:19 This effect is less pronounced when using smaller pixels.

4:22 But nonetheless, you see these in games all the time,

4:25 especially on lower powered platforms.

4:26 One method to soften this effect is Antialiasing.

4:28 Instead of filling pixels in a polygon with the same color,

4:31 we can adjust the color based on how much the polygon cuts through each pixel.

4:36 If a pixel is entirely inside of a polygon, it gets fully colored.

4:39 But if the polygon only grazes a pixel, it’ll get a lighter shade.

4:43 This feathering of the edges is much more pleasant to the eyes.

4:46 Antialiasing is used all over the place,

4:49 including in 2D graphics, like fonts and icons.

4:51 If you lean in real close to your monitor..

4:54 Closer… closer….

4:55 Closer!

4:55 You’ll see all the fonts in your browser are Antialiased.

4:58 So smooth!

4:59 In a 3D scene, there are polygons that are part objects in the back,

5:02 near the front, and just about everywhere.

5:05 Only some are visible, because some objects are hidden behind other

5:08 objects in the scene— what’s called occlusion.

5:10 The most straightforward way to handle this is to use a sort algorithm,

5:14 and arrange all the polygons in the scene from farthest to nearest,

5:17 then render them in that order.

5:19 This is called the Painter's Algorithm,

5:20 because painters also have to start with the background,

5:23 and then increasingly work up to foreground elements.

5:25 Consider this example scene with three overlapping polygons.

5:29 To make things easier to follow, we’re going to color the polygons differently.

5:32 Also for simplicity, we’ll assume these polygons are all parallel to the screen,

5:36 but in a real program, like a game, the polygons can be tilted in 3D space.

5:41 Our three polygons, A B and C… are at distance 20, 12 and 14.

5:46 The first thing the Painter’s Algorithm does is sort all the polygons,

5:49 from farthest to nearest.

5:50 Now that they’re in order,

5:52 we can use scanline rendering to fill each polygon, one at a time.

5:55 We start with Polygon A, the farthest one away.

5:57 Then we repeat the process for the next farthest polygon, in this case, C.

6:01 And then we repeat this again, for Polygon B.

6:03 Now we’re all done, and you can see the ordering is correct.

6:07 The polygons that are closer, are in front!

6:09 An alternative method for handling occlusion is called Z-Buffering.

6:12 It achieves the same output as before, but with a different algorithm.

6:15 Let’s go back to our previous example, before it was sorted.

6:19 That’s because this algorithm doesn’t need to sort any polygons,

6:22 which makes it faster.

6:23 In short, Z-buffering keeps track of the closest distance

6:25 to a polygon for every pixel in the scene.

6:28 It does this by maintaining a Z-Buffer,

6:30 which is just a matrix of values that sits in memory.

6:33 At first, every pixel is initialized to infinity.

6:36 Then Z-buffering starts with the first polygon in its list.

6:39 In this case, that’s A.

6:41 It follows the same logic as the scanline algorithm,

6:43 but instead of coloring in pixels,

6:45 it checks the distance of the polygon versus what’s recorded in its Z-Buffer.

6:49 It records the lower of the two values.

6:51 For our Polygon A, with a distance of 20, it wins against infinity every time.

6:56 When it’s done with Polygon A, it moves on to the next polygon in its list,

6:59 and the same thing happens.

7:01 Now, because we didn’t sort the polygons,

7:02 it’s not always the case that later polygons overwrite high values.

7:05 In the case of Polygon C,

7:07 only some of the values in the Z-buffer get new minimum distances.

7:11 This completed Z-buffer is used in conjunction with a fancier

7:15 version of scanline rendering that not only tests for line intersection,

7:18 but also does a lookup to see if

7:19 that pixel will even be visible in the final scene.

7:22 If it’s not, the algorithm skips it and moves on.

7:26 An interesting problem arises when two polygons have the same distance,

7:29 like if Polygon A and B are both at a distance of 20.

7:32 Which one do you draw on top?

7:34 Polygons are constantly being shuffled around

7:36 in memory and changing their access order.

7:39 Plus, rounding errors are inherent in floating point computations.

7:42 So, which one gets drawn on top is often unpredictable.

7:45 The result is a flickering effect called Z-Fighting,

7:47 which if you’ve played 3D games, you’ve no doubt encountered.

7:51 Speaking of glitches,

7:52 another common optimization in 3D graphics is called Back-Face Culling.

7:55 If you think about it, a triangle has two sides, a front and a back.

7:59 With something like the head of an avatar, or the ground in a game,

8:02 you should only ever see one side— the side facing outwards.

8:06 So to save processing time,

8:07 the back-side of polygons are often ignored in the rendering pipeline,

8:10 which cuts the number of polygon faces to consider in half.

8:14 This is great, except when there’s a bug that lets

8:16 you get inside of those objects, and look outwards.

8:18 Then the avatar head or ground becomes invisible.

8:21 Moving on.

8:21 We need to talk about lighting— also known

8:24 as shading— because if it’s a 3D scene,

8:26 the lighting should vary over the surface of objects.

8:29 Let’s go back to our teapot mesh.

8:31 With scanline rendering coloring in all the polygons,

8:33 our teapot looks like this.

8:35 Not very 3D.

8:36 So, let’s add some lighting to enhance the realism!

8:39 As an example, we’ll pick 3 polygons from different parts of our teapot.

8:43 Unlike our previous examples,

8:44 we’re now going to consider how these polygons are oriented

8:47 in 3D space— they’re no longer parallel to the screen,

8:50 but rather tilted in different 3D directions.

8:53 The direction they face is called the Surface Normal,

8:55 and we can visualize that direction with a little

8:58 3D arrow that’s perpendicular to the polygon’s surface.

9:01 Now let’s add a light source.

9:03 Each polygon is going to be illuminated a different amount.

9:06 Some will appear brighter,

9:07 because their angle causes more light to be reflected towards the viewer.

9:10 For example, the bottom-most polygon is tilted downwards,

9:12 away from the light source, which means it’s going to be dark.

9:16 In a similar way, the rightmost polygon is slightly facing away from the light,

9:19 so it will be partially illuminated.

9:21 And finally, there’s the upper-left polygon.

9:23 Its angle means that it will reflect

9:25 light from the light source towards our view.

9:27 So, it’ll appear bright.

9:28 If we do this for every polygon,

9:30 our teapot looks like this which is much more realistic!

9:33 This approach is called Flat Shading,

9:35 and it’s the most basic lighting algorithm.

9:37 Unfortunately, it also makes all those polygon boundaries

9:40 really noticeable and the mesh doesn’t look smooth.

9:43 For this reason, more advanced lighting algorithms were developed,

9:46 such as Gouraud Shading and Phong Shading.

9:48 Instead of coloring in polygons using just one colour,

9:51 they vary the colour across the surface in clever ways,

9:54 which results in much nicer output.

9:56 We also need to talk about textures,

9:58 which in graphics refers to the look of a surface, rather than its feel.

10:02 Like with lighting, there are many algorithms with all sorts of fancy effects.

10:06 The simplest is texture mapping.

10:08 To visualize this process, let’s go back to our single polygon.

10:12 When we’re filling this in, using scanline rendering,

10:14 we can look up what color to use at every

10:16 pixel according to a texture image saved in memory.

10:19 To do this, we need a mapping

10:21 between the polygon’s coordinates and the texture’s coordinates.

10:24 Let’s jump to the first pixel that scanline rendering needs to fill in.

10:27 The texturing algorithm will consult the texture in memory,

10:30 take the average color from the corresponding region,

10:32 and fill the polygon accordingly.

10:34 This process repeats for all pixels in the polygon,

10:37 and that’s how we get textures.

10:39 If you combine all the techniques we’ve talked about this episode,

10:41 you get a wonderfully funky little teapot.

10:43 And this teapot can sit in an even bigger scene,

10:47 comprised of millions of polygons.

10:48 Rendering a scene like this takes a fair amount of computation.

10:51 But importantly, it’s the same type of calculations being performed over

10:54 and over and over again for many millions of polygons– scanline filling,

10:59 antialiasing, lighting, and texturing.

11:01 However there are a couple of ways to make this much faster!

11:05 First off, we can speed things up by having special hardware

11:07 with extra bells and whistles just for these specific types of computations,

11:11 making them lightning fast.

11:13 And secondly, we can divide up a 3D scene into many smaller parts,

11:17 and then render all the pieces in parallel, rather than sequentially.

11:20 CPU’s aren’t designed for this, so they aren’t particularly fast.

11:23 So, computer engineers created special processors just for graphics– a GPU,

11:28 or Graphics Processing Unit.

11:29 These can be found on graphics cards inside of your computer,

11:33 along with RAM reserved for graphics.

11:35 This is where all the meshes and textures live,

11:37 allowing them to be accessed super fast by many

11:40 different cores of the GPU all at once.

11:42 A modern graphics card, like a GeForce GTX 1080 TI,

11:48 contains 3584 processing cores, offering massive parallelization.

11:51 It can process hundreds of millions of polygons every second!

11:56 Ok, that concludes our whistle stop tour of 3D graphics.

11:59 Next week, we switch topics entirely.

12:01 I’ll ping you then.