The Maths Behind Computer Games: Rendering

I wanted to do something a little different with this post - and it'll probably get fairly technical, but it'll hopefully be interesting nonetheless. I've been fascinated with the maths and engineering behind games for almost as long as I can remember, and thought it might be interesting to condense some of that into a post (with pretty pictures) - if it's interesting I might do some more of these in the future. For now I'm going to explain the process of projection, with maybe a dash of texturing and lighting - there are actually some short-cuts and tricks used to speed the process up, but I'm mostly ignoring them for simplicity.

How it Works
One of the fundamental and vital things about drawing a 3D scene, is that almost everything can be approximated as a load of small, flat pieces (polygons) each joined at the edges, with a visible material applied to them. Computers generally use triangles, but you can also use quads or any n-gons if you feel so inclined. Each of the points which define the triangles can be expressed as a vector - 3 numbers, representing its X, Y and Z coordinates in space.

Mostly triangles in there...

Using some pretty self-explanatory maths, you can take a set of several different models, each positioned at different points in the world, and express them as a set of points (vertices) in the scene. So you now have a set of points in space. So what? They are pretty much useless, without some kind of viewing-point. The position and location of a camera in the world can also be expressed as a set of coordinates and a rotation - by using these bits of information, every point in the world can be shifted into a nice, simple set of values which are now oriented with respect to the camera - that is, the axes are aligned to the view-point and not the world or the objects. If you're confused, don't worry too much - essentially, what you now have is the points, but shifted so that the numbers now represent X, Y and Depth rather than the position in the world.

Unfortunately, our view on the world isn't quite as simple as this - if you imagine a simple cube, as described above, as seen face-on, each corner would be directly in front or behind of the rear face. In reality as we experience it, things which are further away appear smaller, so we shift points towards the centre of the screen depending on how deep they are. This now gives a pretty nice view of where each point on the model corresponds to on the screen - you can say that each point has been projected onto the 2D screen.

The above diagrams represent perspective and orthographic space (perspective is on the left) - the space which is actually seen by the camera (the far end is the furthest object you can see - computer games limit how far you can look into the distance, sometimes with sneaky tricks)

The initial projection I described is what's known as orthographic projection, which is useful if you need to work to a specific scale - for example, when designing a product with CAD. The depth-adjusted version is perspective projection, and is used when something needs to be displayed as it would be seen.

Once you have your points as they would be positioned on the screen, you can then draw in the triangles themselves. The easiest way would be to stretch a texture onto each triangle - though even this can have some quirks, which fall way beyond the scope of this blog post. A much more interesting and mathematical thing you can do is break each triangle into pixels and work out the colour of each - this is known as shading and can be done incredibly fast on modern graphics hardware.

All credit to Wikipedia for the image.

The Phong model of lighting (named after the first person to describe it, Bui Tuong Phong) can be used to shade a variety of material types very effectively - it's typically used for plastics or non-transparent liquids - Gels in Portal 2 for example. The principle is that the overall light reflected from a surface can be thought of as the sum of several different components, each of which is seen above.

The ambient (emissive) light is a term considered to always exist, but is often excluded because it is not strictly necessary. The diffuse (scattered) light is reflected in all roughly all directions by the material and does not depend on the viewing direction, only on the lighting direction. The specular (highlight) light is the intense highlight reflection you may see off shiny surfaces. Together, they can be summed up to give a pretty good representation of a material as a whole.

Restrain yourself, Jamie!

The Ka, Kd, Ks and alpha are material constants - representing the material's ambient, diffuse, specular and "shininess" constants. Things with a hat on (^)  are normalised vectors representing light and viewing directions, and the surface's normal. Ip is the output - the colour of a single pixel. This process is repeated for every single pixel of a scene (well, technically fragment - transparency can cause two or more fragments to be drawn for a single pixel).

Not personally a fan of the cave missions, but they definitely looked good. 

Of course, there are a huge number of other things you can (and indeed need to) do to make a realistic-looking scene which still performs well. For example, textures can be sampled to give much finer detail on items, and other shaders can be custom-written to handle reflective, refractive or translucent materials, metals, goo, or even supposedly simple things such as bumpy surfaces, as seen above. The cave's surfaces are actually flat - the surface shader is given a bump-map - a texture representing the height of a material rather than its colour. This can be used with a light vector (such as the torch) to give gorgeous, realistic-looking lighting effects, at much faster speeds.

Confused? Now remember that the computer handles about 100,000 vertices, depending on the game, and 1,000,000 pixels, 50 times a second, just in graphics calculations for a modern game.

Things I Haven't Mentioned
What about the other side of objects?
Sneaky trick with how you choose the triangles - you number the vertices in an anti-clockwise order around each polygon. When you're about to draw it, check if the order is still anticlockwise. If it is, you know it's facing you  and should be drawn. If not, you're either looking at it sideways-on or from behind - which probably means you shouldn't be drawing it.


What about things behind you?
In the part where you move things with respect to the camera, things behind you end up getting a different sign on the depth to everything in front of you. You can just throw out any vertices with depth values below zero.


Anything else?
There's probably a solution or an explanation, but I'm really not going to pre-empt anything and everything you could ask. Ask in the comments, or wait for future installments, if this was actually interesting.


Yours geekily,
Charlie

What's eating your time?

Despite having disassembled my main desktop, I've found that I still have ample distraction even on a Linux laptop - so I decided to present, in list form, the top 5 web-apps I use to distract myself:

5. Webmasters Tools/Analytics/AWS Control Panel
All are just small apps you can use to check the status of a site or sites and how they are performing - useful tools for analysing your sites. Not so useful to check every half-hour though, since the data is updated daily.

4. Whatever tab is to the left of this one
This rule sadly also applies - instead of concentrating on the contents of one tab, if one starts to lose its appeal, the one to its left starts to look all the more tempting. If I happen to be on the left-most tab then.... yeah, right - like I'd ever make it over there. The tabs on the left haven't seen the light of day since the machine was last booted

3. Grooveshark
Finding new music is easy. Concentrating with said music playing is often harder.

2. YouTube:

With awesomeness like that throwing itself at you, what's not to like?

1. Facebook
This one doesn't need any explanation.

(Twitter, Reader, and a few other sites also feature but less prominently)

There's an entry on the XKCD blog that looks at the procrastination response, which is surprisingly interesting. Essentially, in the absence of a clear way forward in solving a problem, the brain will throw out the potential longer-term satisfaction of solving the problem, for the shorter-term reward gained by, for example, opening up a new tab and browsing Facebook. The new action, as long as it has some novelty value, will almost always be more appealing, because it provides an instant and always-available reward. Hence, over time, more challenging things are pushed aside by the short-term rewards of a quickly-changing social site such as Facebook, which never loses its novelty value because of its continually-current nature. Similarly, sites like Twitter and YouTube can also become ingrained responses when faced with the slightest of problems in your intended work.

As for solving the above? If I find a solution in time for my Chemistry exam, it'll both save me from an embarrassing and complete failure, and will be shared on here next time.

Number of times I alt-tabbed to another window whilst writing this: 6
Charlie

Pre-exam Jelly

If you hadn't noticed, exams are now altogether too close for comfort. For that reason, I should probably be asleep rather than blogging. This week is Maths, but Chemistry is still only a week and a half away. A week is long enough to learn most of the unit - at least, that's what I'm depending upon...

In lieu of a proper post, I leave you with these tidbits:

My desktop is now literally a desktop computer - it's lying in several pieces on my desk (intentionally so, it didn't explode or anything). If you want to contact me, I can no longer read MSN or Steam messages. Send messages via FB, email or text instead, please.

Without a desktop, I've been on my laptop for far too long, and am far too used to Linux as a result. Expect to see some cool stuff over the summer as a result (if by "cool" you read "slightly more geeky than a conference of WoW enthusiasts"). I now know my "top" from my "tee", and "-X" from "-x" - the latter was the source of much confusion...

Chell in the Rain (now my background image)

A light distraction:

Contenders for the comparison included "geekier than a Maths set with their own Facebook group" and "geekier than someone fluent in both JavaScript and Klingon"
Charlie

Procrastination and Examination

I'm about to sit 9 exams, spread from the 18th of this month to the 23rd of June. Despite that, I still haven't written a blog post, or completed any of the practice papers due in under 8 hours. I've managed to get a load of little tasks done, but nothing significant or important. Ze Frank had an excellent video on procrastination, but I'm sure I've already linked far too many people to it. 


"Psychologists often cite such behavior as a mechanism for coping with the anxiety associated with starting or completing any task or decision" [wikipedia]


Interestingly, the above quote fails to mention the anxiety brought on by not completing the tasks required of you, hence discrediting the whole statement and making procrastination entirely acceptable and healthy from a psychological perspective. As if that stopped any of us anyway...

Just one of many ways in which you, too, can successfully procrastinate...

Side note - I'm interested to hear from anyone who's been affected by the PlayStation Network being down over the last couple of weeks. What does it actually stop people from doing? I know if it stopped me playing Portal 2 co-op I'd be pretty annoyed...

Now to bury myself in exam papers. Fun times.
Charlie

The last 604,800 seconds

Give or take a few percent:

• In the last 200, I've probably pissed off 40% of the contents of the house by dropping heavy things great distances at 4AM. I hope they don't repay the favour.
• In the last 2,000, Osama Bin Laden is announced dead. Convenient that the announcement came around re-election time...
• In the last 20,000, I've written a good few hundred lines of code. Not much, but enough to not feel like an utter procrastinator either.
• In the last 200,000, I've watched Thor, but that's already been covered by Benji about ten times better than I ever could over here. I also finished a damn good book (more to follow).

And looking forward:

• In the next 200, I'll probably spend 100 of them staring at the screen proof-reading and feeling desperately inadequate, and guilty for not revising.
• In the next 2,000, I might even get some sleep.
• In the next 200,000 I need to do about 9 maths papers, give or take.
• In the next 2,000,000 we will begin sitting our exams, quite potentially altering our university options and deciding entire career paths.
• For the purposes of not going down a much darker, existential path, I'll gloss over the fact that 3 lines more is a lifespan, maybe 4 at maximum is everything we know of and can care about, and about 1.5 beyond that is the start of recorded history.

On a lighter note, I appear to have officially taken up reading again (having read 5 books in about 2-3 weeks). Yesterday, I read "Will Grayson, Will Grayson", a stunning collaboration between John Green (of whom I'm a massive fan) and David Levithan. 

It's all sparkly and pretty in real life. 

The book is an engaging read from start to finish, featuring a clever plot, genuine characters and relationships who change believably as the plot progresses. I personally loved its pace and twists, and pretty much everything about it. It isn't perfect by any stretch (what book is?), but it's definitely well worth picking up a copy and spending a few hours on, as is any John Green book (he's also a YouTuber, which is how I discovered his books - see here for more information).

Want to pick up a copy? If you know me, I'll lend you my copy, or pick one up from Amazon:

Forfeit vlog (would have been today except for an annoyance with the microphone) and 3D printer progress to follow in due time...

That is the reason why logarithmic scales could be considered depressing...

Charlie