Pixels

Drawing a single pixel is a good place to start, and there’s a thing for doing just that.  In most graphics API’s there is a drawing style called ‘point’. On the right, is a bunch of randomly placed points, each is currently being drawn as a pixel by the graphics API. This may look fairly dull, but there is a lot happening in the background.

Each pixel in this image is an X, Y, Z coordinate in the code that’s being run and drawn. Your GPU is provided the list of coordinates, and an image of blank pixels and told: “Draw ‘points’ at these coordinates in this image”.  Doing that placement requires a lot of linear algebra, but it’s easier to explain through an example.  Imagine you had a sheet of window screen material, where each hole in the material represents a pixel.  In our little example to the right, our netting has 100 holes by 100 holes. Place ping pong balls around the place you want to draw, each position of a ball is represented as one of the coordinates in the coordinate list.  Holding the netting between you and the ping pong balls, you take paint and fill each hole in the netting that you can see a ping pong ball through.  Present the netting as your image and you’re done. Now, your GPU isn’t filled with paint and window screens, it does this process using matrices and a big chunk of memory, but the end result is similar in concept.

This ‘painting pixels into a grid’ idea has it’s own name: rasterization.  It’s one of the things GPU’s are very good at, to the point they have these equations implemented as hardware instead of software.

Earlier I lied slightly, I said a point means a pixel, however it instead means a square facing the camera. The “looking at ping pong balls through a screen” exercise is used because a “point” may be composed of more than one pixel, depending on things like screen resolution.  In the upper image the points are a 1×1 unit square at 120 units away (they are scattered over a 100×100 unit area).  The second example image to the right has the same distance from the camera and scatter area, but each point is 20×20 instead. If you stare at the larger square image for a time, you may notice that the squares are not all the same size. Because the positions of the square are random, some of them may just brush the edges of a larger area of pixels while others may rest cleanly inside a smaller area of pixels. There are a few techniques to deal with these irregularities and smooth them out, such as anti-alising, but for now, we’re not doing that because it’s complicated.

Lines

Line segments are closer to being “useful”, a few choice games like assassins creed use them for visual accents. Line segments also have a drawing style, called ‘line segment’.  Who would have guessed?

Instead of a single coordinate, line segments requires two coordinates, one for the start and one for the end. The rasterization process is nearly the same, although now we take a ruler and lay an edge connecting the two points. If any part of that edge overlaps a hole, paint that hole as well. If the line segment is not perfectly vertical or horizontal, it might start looking a bit jagged. This is normal, and you can see it with the lines on the right.  Anti-alising is a way to try to hide the problem, but the techniques get theory and math heavy real fast.  In a nutshell, it uses shading to fool your eye to believing something is smoother than it is.  Instead of a jagged line of white pixels on a black background for example, it’ll fill in some of those jaggy edges with grey pixels. I’ll cover them in another article but for now we’ll stick with jagged lines.

Another issue that can come up here is overlaps, how do they get handled? Which lines overlap which other lines? In our example renderer, the order seems somewhat random, and that’s not a coincidence. The lines are generated randomly, and the order they are generated controls what’s drawn above what. Things get complicated if you try something more advanced than a random pile of line segments. One of the standard way to solve this is a technique called Z-culling.   As you draw a pixel you also store how far away the geometry that caused the pixel to be drawn is. This is stored in a section of memory on your video card called the Z-buffer.  If anything farther away from that distance tries to overwrite the pixel, it is ignored.  In the example renderer, all of the lines are 100 units away from the camera.  Because they are all the same distance away, Z-buffering isn’t taken into effect, so line order is used instead, and lines drawn after other lines overwrite the pixels already there.  Z-culling does not work with transparent things, but for solid things it helps keep the rendering cost down.  It may sound complicated to do that check, having to do the math for how far away something is when you’re trying to draw it, but the depth can often be figured out for free based on the way GPU’s do their math.  Even so, doing the distance check would still a good choice even if it wasn’t free, as lighting and other effects can be hundreds of times more expensive than a depth check, and it makes no sense to make your GPU work hard to figure out what something looks like and draw it… if in the end, it’s only going to be hidden by a wall or a door in the way.  If you find out you don’t need to do calculations again for a pixel, you save a lot of processing time; even if you lost a tiny bit of time when you did the Z-culling check.

PS: “Culling” is a word that will come up a lot.  It means to exclude something from being drawn.  In this case it excludes pixels from being redrawn.

It turns out there is another way to draw a line, specifically one line. Previously we used two points for each line, but often, you need to draw a chain of line segments, each segment starting where the last one ended. While you could just have each line segment two sets of points, almost half your data is redundant and unnecessary as long as the GPU understands “we’re making a chain, just send a list of points for every point in the chain and I’ll draw the line segments between them”.  This format for drawing chains of line segments allows for half the memory for the same amount of geometry.  Instead of a chain of 10 line segments needing 20 points to draw, it only needs 11 points.  Storing the same things in more compressed formats will be a repeating theme here.  It may seem stupid for 10 or even 100 line segments, but GPUs may need to draw trillions for a single frame of a scene… and all those point coordinates add up.

Now, for the colors, because the lines now look like they are blending between different colors. Each coordinate in the line has a different color, and each color is blended based on how far the pixel being drawn is from each coordinate. The style of blending is called linear interpolation.  At point A it’s all the color of A. Point B is all the color of B, and a point perfectly between A and B is half A half B; at 1/4 the way from A to B, it’s 3/4 A, and 1/4 B. There are a few different styles of interpolation, each has a separate purpose but linear is the cheapest, so I’m going to be using that in examples for now.

For this style of interpolation to work, each coordinate needs to have a color related to it. All of our examples so far, have a color paired with each coordinate, but this is the first time the color has been blended between two coordinates.  Even the prior line segment example above this one, technically had two colors, but the colors assigned to each point in the line segment was the same, and blending two identical colors together makes the same color.  Coordinates in a chain of line segments we have defined so far is often called a “vertex” (another graphics term you’ve probably heard), but that’s also a bit misleading.  In graphics, a vertex can contain significantly more information than just a position.  In this case, the vertex also contains a color.  If you have ever heard the term ‘vertex shader’ with graphics, this is what it means by ‘vertex’.

A “shader” is a small program (sometimes called a kernel) that is executed on a piece of a set of data and generates a similar piece of data (most of the time). In this case a vertex is consumed and then a new vertex is produced for other shaders. All kinds of shaders are responsible for massive parts of that crazy math I hinted at earlier, and vertex shaders are responsible for things like placing models in the world (I’ll come back to this later). Using of vertex shaders is difficult, since they can be used to do a whole bunch of things, and people have long debates on if it’s good to do those things with vertex shaders or some other similar technology or shader.  However, to get data to those shaders, you normally use vertices (there are a few other ways as well, not getting into those).  You use each vertex like a little box, normally storing position, color, and whatever else you need to make the vertex shader work.

So, does a vertex shader do that fancy color blending interpolation?… nope, it’s not dealing with that.  The point of bringing up vertex shaders, is to bring up vertices store data like color, but a vertex shader is going to likely (again with the “people will argue this”) pass that onto the next shader. This gets a bit more complicated since vertex shaders are normally the first shader in a series of shaders, but we’re going to jump to the last shader, the pixel (or fragment) shader.  Guess what?  It’s a tiny program run on each pixel and generates a color to put in that pixel. I brought up that there are shaders between the vertex and pixel shaders, but they are optional and we’re not going to go into them.  Each pixel shader requires a point, that was produced by (in this case) a vertex shader…  Wait – didn’t we generate a vertex earlier? The pixel shader input format is the same as the vertex shader output’s format, so a position and a color in this case.  But, between these steps, the rasterizer came in and picked the spot where the pixel shader needs to run. The rasterizer provides how far along the geometry (in this case a line) the pixel is, and each piece of data in the vertex shader output is interpolated and blended between the the two end of the line based on that distance. In this case, our pixel shader gets the interpolated coordinate of the pixel being drawn (which is the position of the pixel), and an interpolated color from the two endpoints of the line; from there it provides that color as the color of the pixel at that point. This means our pixel shader is dumb as bricks right now, it’s taking a piece of data provided as it’s input and directly providing it as output. Current AAA game pixel shaders can have hundreds of things going on.  These shaders tend to be most complicated, as it’s what handles things like lighting and reflections.  Each of these shaders also get run at least once for each pixel of your monitor.  I mentioned Z-culling before, but that technique isn’t perfect and transparency is a thing, so many pixels get drawn multiple times. Most of the render time in a game, is running these pixel shaders.