Andy Fenwick

Andy Fenwick is a graphics programmer, computer gamer, board gamer, science geek and reluctant DIY-er. He is often found in his natural habitat of Ashby-de-la-Zouch listening to gothic music and complaining about government incompetence to his long-suffering wife.

Mar 312013
 

Here’s a quick video of something I’ve been working on recently:

This is just an experiment in coming up with a more interesting ray-marched scene to test out graphics techniques. It may be developed into a proper demo at some point, but that probably requires more artistic input than I’m able to give, so we’ll see.

What we have here are two infinite length boxes, with X and Y coordinates rotated around the Z axis depending on Z. Another box is intersected at intervals to break it up a bit. Finally a texture is used to add some small-scale surface detail. So there’s nothing particularly interesting about the base shape.

The background environment map was made in Spacescape, an awesome little program for drawing sky boxes of stars and nebulae. and then baked into a cubemap. The basic rendering is much the same as I talked about here. There is also an implementation of the Bokeh depth of field presented here (which I’ll post a bit more about at some point), and lots of point lights rendered using an implementation of the tiled deferred shading presented here.

I’ve not really worried about optimisation but it’s currently running at around 100fps at 720p on my HD7950.

Mar 122013
 

Last time I talked about basic ambient and diffuse lighting.  This is good for perfectly matt surfaces, but every real surface has some degree of specularity, which is when light is reflected off a surface to give a shiny appearance.  You may not think of most objects as having a shiny surface, but it’s a significant part of the look of almost any surface.  If you want to see for yourself, take a look at this article which shows you how to split up the light from any object into specular and diffuse components.

Specular from perfect mirrors

Light reflects off specular surfaces in exactly the same way as a mirror (because mirrors are in fact just very flat surfaces with pure specular reflection, and no diffuse lighting).  If you have a point light source, you can work out the reflection direction by reflecting around the surface normal.

Mirror reflections

When looking in a mirror, you see the reflection of the light at the point where the reflected light direction goes directly into your eye. If you work backwards you can see that each point on the surface of the mirror will reflect light from a different point in the world. Mirrors are the simplest case because they are completely flat, meaning that light from a point in the world will only be reflected towards your eye from one point on the mirror.

Imperfect reflections

Most surfaces aren’t perfectly flat, and so don’t have perfect mirror reflections. If a surface isn’t perfectly flat it means that the normals around a given point will be pointing in lots of different directions. On average the normals will all point directly away from the surface, but if you look close enough at a rough surface (e.g. tarmac) you’ll see lots of surface facets pointing in different directions.

When we’re far enough away from the surface, all of these surface facets will look small enough that they occupy just one pixel on the screen, or one receptor in our eye. However, the distribution of the normals still affects how it appears to us.

Reflections from rough surfaces

What we see in the diagram is that one pixel on a rough surface actually reflects light from lots of different directions. The strongest reflections are from the ‘mirror’ reflection direction, with the reflection strength tailing off the further you get from this (because on average more of the surface facets will be pointing in the normal direction). What this means is that if the light source is at A then you’ll get a very bright reflection because lots of the light is reflected towards the eye. If the light is at B then there will still be some reflection but it will be weaker. This is why shiny surfaces have sharp, bright highlights and rough surface have blurry, dim highlights.

Implementation

To calculate the specular highlights from a light source at a given pixel, we first need to find out how much the angles all line up. We need three pieces of information at each pixel:

  1. View vector. This is the vector from the pixel to the eye, in world space. It is calculated in the vertex shader and interpolated for each pixel.
  2. Normal vector. This is part of the data for each vertex in the mesh, and interpolated for each pixel. Normal maps can also be used to provide more detail (I’ll talk about those another time).
  3. Light vector. This is the vector from the light to the pixel, and for distant light sources is constant for all pixels. For near light sources this is calculated in the vertex shader, the same as for the view vector.

Now we need to find the halfway vector, which is half way between the view and the light vectors.  To find this, simply work out (lightVecviewVec) and renormalise.

Then take the dot product of the halfway vector and the normal, which will give you a value for how aligned the two are. This value will be 1 if the vectors are perfectly aligned, and zero if they are at 90 degrees. It should never be negative (as this would mean you are viewing a surface from behind it) but it’s possible due to the way things are interpolated sometimes.

The next part is to come up with some simple way of simulating the rough surfaces, in particularly how all the normals reflect light from different directions.  Because the dot product is between zero and one, the simplest way is to just raise it to a power – higher powers cause the value to drop off quicker the further the halfway vector is from the normal, leading to a sharper highlight. The full specular equation is then:

spec = pow(dot(normalize(lightVecviewVec), normalVec), specularPower) * lightColour

Varying the specular power will change the sharpness of the highlight. Here are examples of just the specular lighting with powers of 2 and 20:

Specular power of 2

Specular power of 20

 Add this to the other lighting and you start to get a more believable image:

Specular, diffuse and ambient lighting

Better specular

The problem with this method of doing specular highlights is with the simplicity of just taking a dot product and raising it to a power.  This method is chosen because it looks “about right” and is very cheap to calculate. It isn’t based on anything fundamental about the way light behaves, and because of this it will never produce photorealistic images.

In a future post I’ll talk about Physically Based Rendering (PBR), which boils down to a more complicated method of doing specular highlights, but a method that is based in the real-world behaviour of lights and surfaces. It is an advanced technique and has only been widespread in games for the last few years, but it given much nicer results (and the cost of being a lot more expensive to calculate).  Anyway, I’ll come back to this in a future post.

Next time I’ll talk about normal mapping, which allows much more detail to be put into lighting models.

Mar 022013
 

Lately I’ve mainly been playing a couple of shooters at different ends of the same evolutionary path.  They are Planetside 2 and Wolfenstein: Enemy Territory (henceforth called ET).

Wolfenstein: Enemy Territory

I’ll start with ET, as it’s pretty old now and you might not have come across it.  It’s a free game that started out as an expansion to Return to Castle Wolfenstein, but was never finished and simply given away as a standalone game.  Amazingly I’ve been playing this on and off with my gaming group for eight or nine years now, and it still gets an enthusiastic response.

Wolfenstein: ET Seawall Battery

This is purely a multiplayer game and was an early example of lots of the things you see in modern shooters. It has asymmetrical gameplay, with an attacking and defending team. It’s purely objective based, with a string of objectives for the attacker to accomplish within a time limit.  It’s class based, with five distinct classes. And it has an XP and levelling system.

Our favourite map is Fuel Dump.  The Allies are attacking and first must escort a tank across a bridge, with their engineers keeping it repaired while the Axis team rain down air strikes and sniper shots. Oh, and the bridge requires building before the tank can cross, and every time it’s built the Axis team seem to blow it up again.  Then the tank is driven through a tunnel system before finally blowing a hole in the fuel dump wall.  Finally the Allies have to get into the base, destroy the gates with explosives and plant the dynamite.

The longer maps can be a bit of a gruelling slog, repeatedly running out into the defenders’ guns as you inch closer to achieving the objective, but when you finally get that dynamite to blow seconds before the 30 minute timer runs down, it’s really rewarding. The classes are varied – the engineer is the most generally useful as most objectives require building stuff or blowing stuff up, but you’ll likely die a lot. Soldiers have heavy weapons (switch to the Panzerfaust if you’re getting frustrated at not getting any kills…). Covert Ops can steal uniforms and snipe. Medics pick everyone up again when they go down. Finally, Field Ops get love and hate in equal measure as a well timed airstrike takes out three enemies in one go, or you wipe your entire team with a misplaced flare canister throw.

Wolfenstein: ET Gold Rush

It’s not the most accessible game ever, likely because it wasn’t ‘finished’. There are very few hints as to what you’re supposed to be doing as a new player and the maps can be a bit confusing, but after a game or two on each with someone showing you the ropes you’ll know exactly what’s going on. Also you need a decent sized group of players to make it work – three per side is the absolute minimum in my opinion, but you’ll have a great game with five or more per team.

I’m not exactly sure why we’re all still playing it years later (and in preference to many more recent games, including the disappointing sequal, ET: Quake Wars). At a guess, I’d say that it’s because it’s free (everyone has a copy), it runs fine on literally any machine, there are no server and connection issues (we have our own private server), and we’re all ‘bought in’ so there’s no learning period any more.  Oh, and it’s just a damned good game.

 

Planetside 2

At the other end of the spectrum is Planetside 2, which I’ve played a fair bit in the last few weeks. Planetside 2 is an MMOFPS, with each server seeing hundreds of players across three teams, all fighting over the same objectives at once on a massive map.

The first thing that strikes you on joining the game is that it actually works. Countless other infantry rush around you, tanks trundle past and aircraft buzz overhead, and there’s hardly any lag. The second thing that strikes you is a hail of bullets, and you’re back at the respawn.

Planetside 2

PS2 also isn’t a particularly newbie-friendly game. The UI is confusing, and the mechanics of capturing objectives isn’t obvious. Identifying friend from foe is tricky, the constant explosions and gunfire is disorientating, and standing still in the open will get a sniper’s bullet in your head.  And it’s the closest a game has made to feel to taking part in a real war.

Or at least, one of those fictional wars where random people are pulled off the streets, given a gun and thrown into a combat zone with no training.

Nowhere is this more apparent than with the aircraft. My favourite activity in Planetside is flying the fighter jets. Very rarely do I get shot down. This isn’t because I’m some kind of flying ace, but because most flights end up with me crashing into mountains, buildings, trees, or the ground. Occasionally I crash into enemy aircraft, but that’s good because they tend to blow up and I get XP. Sometimes I manage to shoot at ground targets, although I imagine the conversation in the last transport I attacked would have gone something like this:

“Hey, there’s a plane firing rockets at us!”

“Really? But we’ve taken no damage.”

“Yeah, I’m using ‘at’ in the vaguest sense.  Oh, he’s coming in closer… er… looks like he’s trying to park upside down…”

Planetside 2, not crashed this plane yet

This is a free to play, micro-transaction supported game. This instantly sets off alarm bells among gamers about pay-to-win, but I’m impressed with how much this isn’t the case. All you can buy with real money is additional weapons and cosmetic player customisations. The basic free weapons are all good, and the paid for ones are just different rather than better.  All of the other unlocks and upgrades are bought with XP earned in game, so it’s perfectly viable to play on a level playing field without spending any money.

When this game is good, it’s really good. Your enjoyment is quite dependent on getting into a good squad (or bringing your own group of friends).  If you’re lucky you’ll end up in a well organised team, with a leader with voice comms who knows what they’re doing and sets appropriate objectives.  When that happens it’s as good an MMO experience as I’ve ever had (well, outside of a successful Eve Online fleet battle, but I don’t have time for those any more).

If you’re on Woodman server and come across a TR player called Schizofen, go easy on him…

Feb 232013
 

A while back I had a quick search for soft shadowing techniques for ray-marching rendering, but somehow I didn’t manage to find anything very useful.  So I just had a play around and came up with something.  Here’s the video from last time again:

Then I did another search and found almost exactly the same technique described here by Iñigo Quilez, apart from his method was a bit simpler and more elegant so I’ve just gone with that.  I’ll give a bit of background and explain the method anyway.

Why shadows are soft

If we  want to model lighting in the real world we have to understand how it works and why, and then come up with an approximation in code.  In the case of shadows, they are caused when the path from a point in the world to a light source is blocked by something else so the light can’t reach it.  Which is obvious, but what the shadow looks like depends on the shape of the light source.

The simplest case is when the light is really tiny, so that it’s effectively just a point in space.  In this case, each position in the world can either ‘see’ the light source, or it can’t.  Each position is either fully lit or fully in shadow, so you get very sharp shadows.  Real lights aren’t points though, and have a size.  Therefore positions in the world can see either none of the light, all of it or just some of it.  This gives ‘soft’ shadows, with a smooth transition from fully lit to fully shadowed.  The larger the light, the softer the shadow.

This is a pretty bad diagram but hopefully it shows what I’m talking about.  The region in full shadow is called the umbra, and the region in partial shadow is called the penumbra.

Shadows from point lights and area lights

One final thing to note from the diagram is that the size of the penumbra is wider the further away you are from the occluding object.  This means you get sharper shadows close to the shadowing object, and blurrier shadows further away.

Larger penumbra further away

Quick intro to ray marching

I’d better give a brief description of how ray-marching renderers work, or the rest of this won’t make a lot of sense.

When using a ray marching renderer, you define your scene by using an equation.  What this equation does is it takes a 3D point and tells you how far that point is from a surface in the scene.  To render the scene you start at the eye position and for every pixel on the screen, get a direction vector that goes from the start position through that pixel.  Then you iteratively step through the scene along this vector.

Marching along a ray until it hits the floor

At each step, you plug the current position into the equation and it tells you how far you are from a surface.  You then know that you can safely move that distance along the vector and not hit anything.  As you approach a surface the distance of each step will get smaller and smaller, and at some threshold you stop and say that you’ve hit it.  There is a more detailed explanation in this great presentation.

Simulating soft shadows

We now know where soft shadows come from and how the ray-marching renderer works, so we can combine them.

The simplest shadowing method is hard shadows.  For this we simply need to fire a ray from the position of the pixel we’re rendering, to the sun.  If it hits anything, it’s in shadow.  If it doesn’t (i.e. the distance function gets sufficiently large) then there is nothing in the way and it’s lit.

But, at each step we know how far the ray is from something in the scene.  The closer the ray comes to an object, the more shadowed it’s going to be.  Also, the further away from the rendered pixel the object is, the more shadowed it’s going to be (as objects further away case larger penumbra).  Therefore, the amount of light at each step is proportional to:

distanceFromObject / distanceFromPixel

Furthermore, the penumbra size is proportional to the light source size, so we can extend it to:

distanceFromObject / (distanceFromPixel * sunSize)

Take the minimum of this at every step and clamp the amount of light to 1 (fully lit), and you’ll get nice soft shadows.

This shadow method doesn’t give fully correct shadows though.  The reason is that it only gives the outer half of the penumbra, meaning that there is actually more shadow than there should be (i.e. light energy is lost).  Hopefully this illustrates the reason:

Inner half of penumbra is fully shadowed

Rays that intersect with an object never make it to the light source, they just converge on the object itself.  Therefore it is impossible for a single ray to measure the inner half of the penumbra.  The central red line is from a pixel that will be drawn as fully shadowed, instead of half shadowed as it should be.  However, it still looks nice and it’s a really simple shadowing method, so we can live with it being a little wrong.

Finally, here is the full shadow code if you’re interested:

float shadow = 1.0f;
float shadowRayLength = epsilon;

while (shadowRad < 150.0)
{
	float3 testPos = worldPos + SunDir*shadowRayLength;
	float distFromObject = DistanceFunc(testPos);
	shadowRayLength += distFromObject;

	shadow = min(shadow, distFromObject/(shadowRayLength*SunSize));

	if (distFromObject < 0.0001)
	{
		shadow = 0.0;
		break;
	}
}
Feb 172013
 

In my last post I mentioned that even the simplest scene can look photo-realistic if lit well, before going on to talk about really simple lighting methods that really don’t.  Obviously you have to start with the basics, but I was playing around with the code to see what could be done and I got it looking fairly nice.

Confession time – I was talking about polygonal rendering in my last post but the screenshots were actually from a ray-marching renderer (I’ll talk about it more on here one day), which is much easier to do realistic lighting with. But for the simple lighting examples the results are exactly the same.

The video show a method of doing soft shadows, where the softness correctly increases the further the pixel is from the occluder.  The sun size can be adjusted to change the degree of blurring.  After that there is some basic ambient occlusion (nothing fancy, just brute force to get it looking nice).  Finally there is some postprocessing – tone mapping, bloom, antialiasing and lens flare.

The video looks pretty terrible.  I suspect that the almost flat colours don’t compress well, hence all the banding.  When it’s running there aren’t any banding issues, as you can hopefully see in the screenshot.

In my next I’ll explain how the shadows works.

Jan 302013
 

Lighting is what makes a 3D scene look real.  You used to hear talk of the number of polyons or the resolution of the textures in a game, but these days GPUs are powerful enough that we’re rarely limited by these things in any meaningful sense.  The focus now is on the lighting.  The most detailed 3D model will look terrible if it’s unlit, and the simplest scene can look photorealistic if rendered with good lighting.

I’ll first cover the most basic lighting solutions that have been used in games for years, and later talk about more advanced and realistic methods.  This will cover simple ambient and diffuse lighting.  But first of all I’ll explain a bit of the theory about lighting in general and how real objects are lit.

A bit of light physics

Eyes and cameras capture images by sensing photons of light.  Photons originate from light sources, for example the sun or a light bulb.  They then travel in a straight line until they are bounced, scattered, or absorbed and re-emitted by objects in the world.  Finally some of these photons end up inside the eye or the camera, where they are sensed.

Not all photons are the same – they come in different wavelengths which correspond to different colours.  Our eyes have three types of colour-sensitive cells which are sensitive to photons of different wavelengths.  We can see many colours because our brains combine the responses from each of the cell types, for example if both the ‘green’ and ‘red’ cells are stimulated equally we’ll see yellow.

Responses of the three types of cones in the eye to different wavelengths of light

Televisions and monitors emit light at just three wavelengths, corresponding to the red, green and blue wavelengths that our eyes are sensitive to.  By emitting different ratios of each colour, almost any colour can be reproduced in the eye.  This is a simplification of the real world because sunlight is made up of photons with wavelengths all across the visible spectrum, and our cones are sensitive across a range of wavelengths.

Objects look coloured because they absorb different amounts of different frequencies of light.  For example, if a material absorbs most of the green and red light that hits it, but reflects or re-emits most of the blue light, it will look blue.  Black materials absorbs most of the light across all frequencies.  White materials absorb very little.

The rendering equation

Feel free to skip this section if you don’t get it.  The rendering equation is a big complicated equation that states exactly how much light will reach your eye from any point in the scene.  Accurately solving the rendering equation will give a photorealistic image.  Unfortunately it’s too complicated to solve it exactly, so lighting in computer graphics is about finding better and better approximations to it.  The full equation looks something like this:

Don’t worry about understanding it.  What it says is that the light leaving a point towards your eye is made up of the light directly emitted by that point, added to all of the other light that hits that point and is subsequently deflected towards your eye.

If you zoom in closer and closer to any material (right down to the microscopic level), at some point it will be effectively ‘flat’.  Hence we only need to consider light over a hemisphere, because light coming from underneath a surface would never reach it.  Here is a slightly easier to understand picture of what the rendering equation represents:

The reason that the rendering equation is so hard to solve is because you have to consider all of the incoming light onto each point.  However, all of that light is being reflected from an infinite number of other points.  And all the light reflected from those points is coming from an infinite number of other points again.  So it’s basically impossible to solve the rendering equation except in very special cases.

Ambient light

Hopefully you’re still with me!  Let’s leave the complicated equations behind and look at how this relates to simple lighting in games.

As the rendering equation suggests, there is loads of light bouncing all over the place in the world that doesn’t appear to come from any specific direction.  We call this the ambient lighting.  At its simplest, lighting can be represented as a single colour.  Here is my simple test scene (a box and a sphere on a flat floor plane) lit with white ambient light:

White ambient light only

To work out what the final colour of a surface on the screen is, we take the lighting colour for each channel (red, green, blue) and multiply it with the surface colour for that channel.  So under white light, represented in (Red, Green, Blue) as (1, 1, 1), the final colour is just the original surface colour.  So this is what my test world would look like if an equal amount of light hit every point.  As you can see, it’s not very realistic.  Constant ambient light on its own is a very bad approximation to world lighting, but we have to start somewhere.

As a quick aside, I mentioned earlier that we only use three wavelengths of light when simulating lighting, as a simplification of the real world where all wavelengths are present.  In some cases this can cause problems.  The colour of the floor plane in my world is (0, 0.5, 0), meaning the material is purely green and has no interaction with red or blue light.  Now we can try lighting the scene with pure magenta light, which is (1, 0, 1), thus it contains no green light.  This is what we get:

Lit with pure magenta ambient light

As you can see, the ground plane has gone completely black.  This is because when multiplying the light by the surface colour, all components come out to zero.  Usually this isn’t a problem as scenes are rarely lit with such lights, but it’s something to be aware of.

Directional light and normals

The first thing we can do to improve the lighting in our scene is to add a directional light.  If we are outside on a sunny day then the scene is directly lit by one very bright light – the sun.  In this case the ambient light is made up of sunlight that has bounced off other objects, or the sky.  We know how to apply basic ambient, so we can now look at adding the directional light.

It’s time to introduce another concept in rendering, which is the normal vector.  The normal vector is a direction that is perpendicular to a surface, i.e. it points directly away from it.  For example, the normal vector for the floor plane is directly upwards.  For the sphere, the normal is different at every position on the surface and points directly away from the centre.

So where do we get this normal vector from?  Last time, I introduced the concept of vertex attributes for polygon rendering, where each vertex contains information on the position, colour and texture coordinates.  Well, the normal is just another vertex attribute, and is usually calculated by whichever tool you used to make your model.  Normals consist of three numbers, (x, y, z), representing a direction in space (think of it as moving from the origin to that coordinate in space).  The length of a normal should always be 1, and we call such vectors unit vectors).  Hence the normal vector for the floor plane is (0, 1, 0), which is length 1 and pointing directly up.  Normals can then be interpolated across polygons in the same way as texture coordinates or colours, and this is needed to get smooth lighting across surface made up of multiple polygons.

We also need another vector, the light direction.  This is another unit vector that points towards the light source.  In the case of distant light sources such as the sun, the light vector is effectively constant across the whole scene.  This keeps things simple.

Diffuse lighting

There are two ways that light can interact with an object and reach your eye.  We call these diffuse and specular lighting.  Diffuse lighting is when a photon is absorbed by a material, and then re-emitted in a random direction.  Specular lighting is when photons are reflected off the surface of a material like a mirror.  A completely matt material would only have diffuse lighting, while shiny material look shiny because they have specular lighting.

Diffuse and specular lighting

For now we will only use diffuse lighting because it is simpler.  Because diffuse lighting is re-emitted is all directions it doesn’t matter where you look at a surface from, it will always look the same.  With specular lighting, materials look different when viewed from different angles.

The amount of light received by a surface is affected by where the light is relative to a surface – things that face the sun are lighter than things that face away from it.  This is because when an object is at an angle, the same amount of light is spread over a greater surface area (the same reason as why the earth is cold at the poles).  We now have the surface normal and the light angle, so we can use these to work out the light intensity.  Intuitively, a surface will be brighter the closer together the normal and the light vectors are.

The exact relation is that the intensity of the light is proportional to the cosine of the angle between them.  There is a really easy and quick way to work this out, which is to use the dot product.  Conveniently enough the dot product is a simple mathematical function of two vectors that happens to give you the cosine of the angle between them, which is what we want.  So, give two vectors A and B, the dot product is just this:

(A.x * B.x) + (A.y * B.y) + (A.z * B.z)

To get the diffuse lighting at a pixel, take the dot product of the normal vector and the light vector.  This will give a negative value if the surface is pointing away from the light, but because you don’t get negative light we clamp it to zero.  Then you just add on your ambient light and multiply with the surface colour, and you can now make out the shapes of the sphere and the box:

Constant ambient and single directional light

Better ambient light

At this point I’ll bring in a really simple improvement to the ambient light.  The ambient represents the light that has bounced around the scene, but it’s not all the same colour.  In my test scene, the sky is blue, and therefore the light coming from the sky is also blue.  Similarly, the light bouncing off the green floor is going to be green.  When you can make generalisations like this (and you often can, especially with outdoor scenes), we may as well make use of this information to improve the accuracy of the ambient light.

In this case we can simply have two ambient light colours – a light blue for the sky and a green for the ground.  Then we can use the surface normal to blend between these colours.  A normal pointing up will receive mostly blue light from the sky, and a normal pointing down will receive mostly green light from the floor.  We can then apply a blend based on the Y component of the normal.  This is the scene using just the coloured ambient:

Hemispherical ambient light

And then add the diffuse lighting back on:

Hemispherical ambient and diffuse

Now just combine the lighting with some texture mapping and you’re up to the technology levels of the first generation of 3D polygonal games!

That’s more than enough for this post, so next time I’ll talk about specular lighting.

Jan 252013
 

I recently found out that the awesome Spectrum game The Lords Of Midnight had been updated for iOS, so I promptly coughed up the £2.99 asking price and downloaded it.

I remember playing the original on my Spectrum when I was probably nine or ten years old.  I paid zero attention to the actual quest, I had no idea on how to even attempt to win the game, but I’d just spend hours exploring the landscape, admiring the views, recruiting a few allies and battling dragons and random passing armies.

Lords Of Midnight Spectrum

Spectrum version

Released back in 1984, this game was completely different to anything else around at the time.  The concept of an epic 3D war game just didn’t exist back then.  These were the days of the text adventure, of brief text descriptions of environments and guessing commands to type into a  terminal window.  Actually seeing graphics of armies marching across the plains in front of you as you moved through the landscape was revolutionary.  Also new was the variety of gameplay with two completely different ways to win the game, leading to two very different game styles.  The first was as an war game, gathering armies together for an assault on the enemy stronghold.  The second was to guide Frodo Morkin to the Tower of Doom, on his own, to destroy the Ice Crown.  It was all very atmospheric.

However, due the the very complex (at the time) nature of the game, it was quite demanding of the player – to have any chance of winning you really had to manually map the game world and keep track of where your characters were in relation to one another.  That was far too much like hard work to me, which is probably why I never bothered with it.

iPad version

So how good is the new version, and how does it stand up today?  In short, I was surprised at how well it’s stood the test of time.  The quality of the port is top-notch.  The style of the graphics has been preserved really nicely, just recreated in high resolution, so it’s unmistakably the same game.  Nicely, the landscape smoothly scrolls when moving or looking rather than just drawing discrete frames at each location.

The touch controls work well enough.  Some of it feels a little clunky, such as the Think screen and having to go to a whole options page to search and attack, but that’s just to keep it as faithful as possible to the original and you soon get used to it.  The vital addition to the game though it that it now has a built in map.  This shows the area of the world that you’ve seen so far with the locations of all of your characters.  It’s so much easier to get a handle on what’s going on than I remember, and it makes the game much more enjoyable to play.

In actual gameplay terms it holds up well enough as a fairly simple strategy game, and I think it would pass as a newly released mobile game today.  My current game sees Morkin dodging whole armies as he sneaks ever closer to the Ice Crown, while further south Luxor is heading up a desperate defence as more and more armies from both sides pile into a massive meat-grinder battle that’s been going on for days.

The meat grinder

If you’ve got fond memories of the game first time around you’ll love this version.  Even if not I’d still recommend checking it out to see what the granddaddy of all modern wargames was all about.  The game is still fun and challenging, but it was never really about the deep strategy so much as the atmosphere of experiencing the world of Midnight, and it’s still got that in spades.

Jan 172013
 

We saw in part 3 how to move the camera around a wireframe world.  Now it’s time to move onto proper solid 3D rendering.  For this we need to introduce a few new concepts: basic shading, vertex attributes, textures and the depth buffer.

Solid rendering

Moving from wireframe to solid rendering can be as simple as filling in between the lines.  There are a load of algorithms for efficient scanline rasterisation of triangles, but these days you don’t have to worry about it because your graphics hardware deals with it – simply give it three points and tell it to draw a triangle.  This is a screenshot of a solid-rendered triangle, which is pretty much the most basic thing you can draw in D3D or OpenGL:

That’s not very exciting, but that’s about all you can draw with only positional data.  In case you wonder why I choose a triangle, it’s because a triangle is the simplest type of polygon and all rendering eventually breaks down to drawing triangles (for example a square will be cut in half diagonally to give two triangles).

Vertex attributes and interpolation

I’ll just clarify a bit of terminology.  A vertex is a single point in space, usually used to define the corners of a shape, so a triangle has three vertices.  An edge is a line between two vertices, so in wireframe drawing we just draw the edges.  A polygon is the whole filled in shape, such as the triangle above.

Vertices don’t just have to contain positional information, they can have other attributes.  One example of a simple attribute is a colour.  If all the vertices are the same colour then the whole polygon could just be drawn the same colour, but if the vertices are different colours then the values can be interpolated between the vertices.  Interpolation simply means to blend smoothly from one value to a different value – for example, exactly half way between the two vertices the colour will be an even mix of each.  Because triangles have three vertices, a slightly more complex interpolation is actually used that blends smoothly between three values.  Here is an example of the same triangle with coloured vertices:

Texture mapping

The other common vertex attributes are texture coordinates.  A texture is just a picture, usually stored as an image file (although they can be generated algorithmically at runtime).  Textures can be applied to polygons by ‘stretching the picture’ across the polygon.  You can think of a 2D picture as having coordinates like on a graph – an X coordinate running horizontally, and a Y coordinate running vertically.  These coordinates range from 0 to 1 across the image, and the X and Y coordinates are usually called U and V in the case of textures.

Textures are applied to polygons by specifying a U and V coordinate at each vertex.  These coordinates (together referred to as UVs) are interpolated across the polygon when it is drawn, and instead of directly drawing a colour for each pixel, the coordinates are used to specify a point in the texture to read from.  The colour of the texture at the point is drawn instead.  This has the effect of stretching some part of the texture across the polygon that is being drawn.

As an example, here is a texture and a screenshot of part of it mapped onto our triangle:

   

This is just a really quick introduction to the basics of polygon rendering.  There are a lot more clever and interesting things that can be done which I will talk about in later sections.

A question of depth

The problem with rendering solid geometry is that often two pieces of geometry will overlap on the screen, and one will be in front of the other.  The two options for dealing with this are either to make sure that you draw everything in back-to-front order, or to keep track of the depth of each pixel that you’ve rendered so that you don’t draw more distant objects in front of closer ones.

Rendering back to front will give the correct screen output but is more expensive – a lot of rendering work will be done to draw objects that will later be drawn over (called overdraw), and additional work is required to sort the geometry in the first place.  For this reason it is more efficient in almost all cases to use a depth buffer.

Screen buffers

First lets talk about how a computer stores data during rendering.  It has a number of buffers (areas of memory) which store information for each pixel on the screen.  It renders into these buffers before copying the contents to the display.  The size of the buffers depends on the rendering resolution and the quality.  The resolution is how many pixels you want to draw, and as an example if you want to ouput a 720p picture you need to render 1280×720 pixels.

The colour buffer stores the colour of each pixel.  For a colour image you need at least one byte of storage (which can represent 256 intensity levels) for each of the three colour channels, red, green and blue.  This gives a total of 256x256x256 = 16.7 million colours, and so each pixel required three bytes of storage (but due to the way memory is organised there is a fourth spare byte for each pixel, which can be used for other things).  These days a lot of rendering techniques require higher precision but I’ll be writing more about this later on.

The second type of buffer is the depth buffer.  This is the same resolution as the colour buffer but instead stores the distance of the pixel along the camera’s Z axis.  This is often stored as a 24-bit floating point number, meaning it can represent basically any number (to varying degrees of accuracy).  Here is an example courtesy of Wikipedia of the colour and depth buffers for a scene, where you can see that pixels in the distance have a lighter colour in the depth buffer, meaning that they are a larger value:

Depth buffer rendering

Using a depth buffer to render is conceptually very simple.  At the beginning of the frame, every pixel in the buffer is reset to the most distant value.  For every pixel of every polygon that is about to be rendered to the screen, the depth of that pixel is compared with the depth value stored for that pixel in the depth buffer.  If it’s closer, the pixel is drawn and the depth value updated.  Otherwise, the pixel is skipped.  If a pixel is skipped then no calculations have to be done for that pixel, for example doing lighting calculations or reading textures from memory.  Therefore it’s more efficient to render object from front to back so that objects behind closer ones don’t have to be drawn.

That’s all that needs to be said about depth buffers for now.  Next time I’ll be talking about lighting.

Jan 092013
 

I’ve been playing a couple of space games lately, which is good because I like space games.

FTL

You’ve probably heard of FTL, if you’ve not already played it.  It’s a small game from a two-man team, and was funded by a successful Kickstarter campaign.  The game is basically about flying your ship through randomly generated sectors of space, facing random enemies and encounters and picking up random loot.  What makes it great compared to some of the overblown epics you might have played is that you have one life, there is only one autosave and a whole playthrough only takes an hour or two.

I’m not going to describe the game in detail because that’s been done to death elsewhere.  What’s interesting is that it plays very much like a board game.  Pick a location to move to, draw an event card, pick an action and roll a dice to see what the outcome is.  The combat is realtime and has enough nuances to make it interesting (especially when it comes to the harder enemies and the final boss), but you could definitely see something like this working as a solo tabletop game.

The problem I tend to have with random single player games is I don’t like losing by pure luck.  This is a problem I often find with computer adaptations of games like Catan and Carcasonne, where there is some element of skill but a lot comes down to pure luck of the draw.  When playing against real people this isn’t a problem because, I think, there is still a winner in the room.  But when losing to a computer there is no winner, only a loser, and nobody likes to be a loser…

Having said that, I don’t have that problem in FTL.  Games don’t come a lot more random that FTL, but if you’re getting unfairly screwed you find generally find out in the first few minutes of the game so you can just restart.  Another reason is that you shouldn’t really expect to win.  The game is hard, really hard (and that’s just on the easy setting).  If you just go in with a goal of unlocking a new ship, getting one of the achievements or playing with a different play style (e.g. focus on boarding actions, drones, ion cannons etc) then dying isn’t really a failure, it’s the expected outcome.  I think I’ve just been spoilt for too long with spoon-fed “experience” games, but FTL is a perfect antidote.

So I very much recommend you take a punt if you’ve not played it.  It usually seems to be up for sale for under a fiver, so for that you really can’t go wrong.

 

Endless Space

I picked up Endless Space in the Steam sale and I’ve been playing around with it a bit.  My first comment is this – it is most definitely not wife-friendly.  The most common question in the house recently has been “What are you playing, that boring game again?”

It is not a boring game (well, if you’re into this kind of thing).  True, there will be a lot of staring at spreadsheets and production queues, but it induces in me exactly the same “one more turn” compulsion that keeps me up late into the night as the various Civilization games over the years.  There is good reason for that – it is basically just Civ In Space.

Instead of cities you have planetary systems, instead of city buildings you have system improvements.  The resources types are exactly the same: food to increase system population, production in each system to build improvements and units, “dust” (gold) to rush constructions, science generated by each system, strategic and luxury resources to unlock new constructions and keep your population happy.  It’ll all seem very familiar.  But that’s not necessarily a bad thing, and it’s all really slickly presented with a nice intuitive interface.

Combat is rather abstract.  Each fight is played out at three range bands – long where missiles dominate, medium where lasers work best, and close which favours projectile weapons.  Your only control is picking an “order” card for each phase, using a board/card game concept again.  Some are offensive, some defensive, and each card cancels out a different class of card.  So if you expect the opponent to play a defensive card in a phase you can for example use the “Sabotage” order which will cancel it out.  It’s a bit random and takes some getting used to but it adds some more interactivity over Civ’s battle system.

My main problem with the game, and it’s exactly the same problem as Civ has, is that it all gets a bit bogged down about half way through.  When you’ve got 20+ systems to manage, with half a dozen finishing constructions each turn, it takes an age to micromanage what they should all be doing next.  Turns start taking 5-10 minutes each and the game can start to drag a bit.

The tech tree is also huge, and you’ll need a couple of games under your belt to become familiar with all the upgrades.  A couple of times I’ve come across some amazing technology (e.g. the planetary exploitation upgrades) that would have provided some massive boost to my empire if only I’d noticed it 20 turns earlier.

Overall though, it’s a decent game.  If you like Civ games you’ll love it.  If you don’t then you probably won’t.

Jan 092013
 

There have been a lot of game developers coming out recently to complain about Windows 8, most notably Gabe Newell.  In the comments sections of news stories you get a lot of people dismissing their concerns and accusing them of overreacting.  I believe that some of these are justified so I’m going to explain why, but also how the problem could be averted.  There is an excellent article here which brings up many points that I agree with, but it’s quite long so I’ll summarise.

1. Closed development environment for Metro apps

This really just sounds like an inconvenience until I get to the real issues, but you can only develop Metro apps if you are a licenced developer (which requires paying an annual fee), in a closed development environment.  No longer can Average Joe whip out a text editor and download a compiler and start writing programs for free.

Closed development environments are a pain – if the Apple experience is anything to go by you’ll waste many hours trying to sort out development profiles and permissions on all of your devices, and delays when a new person joins the team or a new external person wants to test the app.  You’ll long for the days of being able to build an executable and just run it anywhere.

2. Windows Store for Metro apps

This is the main issue with the closed development model – only approved apps can be put on the store.  Although Microsoft has recently relaxed its stance on 18-rated games, anything you publish will still need to be approved by an arbitrary approval committee within Microsoft.

Now, people whose job it is to approve software apps generally aren’t the same people who know what bizarre and innovative app will kick off a revolution in the computer industry.  I guarantee that if every piece of software already written had been subject to approval by some committee before it could be released, the world of computing today would look very different.  How many innovations wouldn’t have seen the light of day because the approver didn’t understand what it was or what the possibilities could be?

This is a real problem if app stores are the only way to get software in future.

3. The Windows Desktop mode will eventually go away

So this is the crux of the issue.  Most accusations of overreacting and scaremongering go something along the lines of: “but you can still run apps on the Desktop mode and you can ignore Metro”.  That is a flawed argument.

While you can currently still run all programs in the Desktop mode, these programs don’t, and will likely never have, access to all the shiny new features and APIs of Windows 8.  Again, at the moment, this isn’t a problem as there isn’t that much new stuff yet.  However, think back to DOS…

20+ years ago everything was a DOS application, and then Windows came along.  But all your old DOS programs still worked as you could run them in DOS mode.  But, none of the new shiny features and APIs of Windows were accessible.  Sounds familiar?  How many new DOS products are written today?

Here is a concrete example – DirectX 11.1 is only supported on Windows 8.  There is no deep architectural reason why it can’t be supported on Windows 7, it just isn’t.  Come Windows 9 or Windows 10, who knows what new APIs will be Metro-only?

What this means

Taking these points together, it is really not inconceivable that in ten years time the only way to get a modern app on Windows is through the Windows Store, and publishing one would require being a registered developed and having your software approved before release.  This is what everyone is getting so worked up about.

How it can be avoided

This can all be easily avoided however – Microsoft just needs to allow open development of Metro apps.  I would say that the main competitive advantage that Windows has enjoyed up to this point is that anyone can write software for it, and so the software library is huge.  Moving to the same model as Apple puts them in direct competition, on equal terms, with MacOS and the iOS mobile devices, and it’s an optimistic person who thinks that’s a favourable matchup.

I think Microsoft have a few years yet to change their mind.  People will still buy new versions of Windows, apps will get developed for the Windows Store, and a lot of people will be happy with that.  But a lot of people will be sad to see a platform that previously offered so many opportunities go to waste.

The rise of Linux?

There is one more possible outcome, and that is the rise of Linux as a viable mainstream OS.  Moves are already afoot with Valve’s upcoming Steam Box.  As I understand it, this may work by having Linux on a bootable pen drive with Steam pre-installed.  There is no reason that this won’t be the way OSes go in future – Windows doesn’t do what you want?  Just swap out the system drive for an OS that has the features you want, just by popping in a different pen drive.  Bootcamp on the Mac is basically doing this already, and I swap between MacOS and Windows on a fairly regular basis on the laptop, depending on what I want to do.

So maybe the future isn’t that bleak after all.  Just don’t expect it to be a Windows-only future.

Jan 082013
 

[Warning: this is a slightly more technical article containing talk of matrices, transforms and spaces.  If it doesn’t make sense just carry on to the next article, you don’t need to understand the details!]

We saw in the previous article how to draw a point in 3D when the camera is at the origin and looking down the Z axis.  Most of the time though this won’t be the case as you’ll want to move the camera around.  It’s really hard to directly work out the projection of a point onto an arbitrarily positioned camera, but we can solve this by using transforms to get us back to the easy case.

Transform matrices

A transform in computer graphics is represented by a 4×4 matrix.  If you’re not familiar with matrix maths don’t worry – the important things to know are that you can multiply a 4×4 matrix with a position to get a different position, and you can multiply two 4×4 matrices together to get a new 4×4 matrix.  A transform matrix can perform translations, rotations, scales, projections, shears, or any combination of those.

Here is a simple example of why this is useful.  This is the scene we want to draw:

The camera is at position Z = 2, X = 1, and is rotated 40 degrees (approximately, again exact numbers don’t matter for the example) around the Y axis compared to where it was in the last example.  What we can do here is find a transform that will move the camera from its original position (at the origin, facing down the Z axis), to where it is now.

First we look at the rotation, so we need a matrix describing a 40° rotation around the Y axis.  After that we need to apply a translation of (2, 0, 1) in (x, y, z) to move the camera from the origin to its final location.  Then we can multiply the matrices together to get the camera transform.

If you’re interested, this is what a Y rotation matrix and and a translation matrix looks like:

This camera transform describes how the camera has been moved and rotated away from the origin, but on its own this doesn’t help us.  But think about if you were to move a camera ten metres to the right – this is exactly the same as if the camera had stayed where it was and the whole world was moved ten metres to the left.  The same goes for rotations, scales and any other transform.

We can take the inverse of the camera matrix – this gives us a transform that will do the opposite of the original matrix.  More precisely, if you transform a point by a matrix and then transform the result by the inverse transform the point will end up back where it started.  So while the camera transform can be used to move the camera from the origin to its current position, applying the inverse (called the view transform) to every position in the world will move those points to be relative to the camera.  The ‘view’ of the world through the camera will look the same, but the camera will still be at the origin, looking down the Z axis:

This diagram may look familiar, and in fact is the exact same setup that was used for rendering in the previous article.  So we can now use the same rendering projection method!

World, camera, object and screen spaces

Using transforms like this enables the concept of spaces.  Each ‘space’ is a frame of reference with a different thing at the origin.  We met world space last time, which is where the origin is some arbitrary position in the world, the Y axis is up and everything is positioned in the world relative to this.

We’ve just met camera space – this is the frame of reference where the origin is defined as the position of the camera, the Z axis is straight forwards from the camera and the X and Y axes are left/right and up/down from the camera’s point of view.  The view transform will convert a point from world space to camera space.

You may also come across object space.  Imagine you’re building a model of a tree in a modelling package – you’ll work in object space, probably with the origin on ground level and at the bottom.  When you’ve build your model you’ll want to position it in the world, and for this we use the basis matrix, which is a transform (exactly the same as how the camera was positioned above) that will convert the points you’ve modelled in object space into world space, thus defining where the tree is in the world.  To render the tree, the points will then be further converted to camera space.  This means that the same object can be rendered multiple times in different places just by using a different basis matrix.

Finally, as we saw in the previous article, we can convert to screen space by applying the projection matrix.

Using this in a renderer

All of these transforms are represented exactly the same, as 4×4 matrices.  Because matrices can be multiplied together to make new matrices, all of these transforms can be combined into one.  Indeed, a rendering pipeline will often just use one transform to take each point in a model and project it directly to the final position on the screen.  In general, each point in eac object is rendered using this sequence of transforms:

Basis Matrix * Camera Matrix * Projection Matrix * Position = Final screen position

You now pretty much know enough to render a basic wireframe world.  Next time I’ll talk about rendering solid 3D – colours, textures and the depth buffer.

Jan 022013
 

The usual image of board games is of a sedentary pursuit, with players taking their time to decide their next move or roll some dice.  These games can be incredibly tactical and intense, but one thing that’s usually not associated with board games is adrenaline.

I’ve played two great games recently that are completely different from this, and I’m going to tell you what makes them awesome.  The games are Space Alert and Galaxy Trucker.  They are both designed by the same person, one Vlaada Chvátil, and they both include the element of real-time gameplay.

Space Alert

Space Alert is a co-operative game for four or five players.  You play the crew of a spaceship sent into hostile territory who must survive for ten minutes.  What makes this game different though is that those ten minutes are played out in real time, to an accompanying soundtrack CD.  Every minute or two the ship’s computer will call out a new threat that has to be dealt with, and as a team you have to work together to defeat each threat before it tears your ship apart.

During those ten minutes you put down cards to plan out what your little crewman is going to do.  With each action you can move to a different room, or you can press the A, B or C button in each room which either fires the guns, powers up the shields, moves power to where it’s needed, or a few other special actions.  All players plan out their moves, but the move cards are placed face down so nobody can see what anyone else is doing – you have to talk to each other to make sure all threats are being dealt with.

Finally, after the ten minutes are up, there is the “action replay” phase.  Each player turns over their action cards and replays on the board what actually happened.  If all went well and the team played as a cohesive whole then a whole pile of alien spaceships will appear and be blown away by coordinated volleys of laser fire, and you can congratulate yourselves on a job well done.  More often than not though one player will be pressing the fire button on the main laser but nothing will happen because someone else drained the batteries to power up the shields and nobody remembered to throw more fuel into the reactor and the missiles were fired too early and the target was out of range and…  and it’s just funny to watch what you thought was a bulletproof plan fall to pieces as your ship does likewise!

Playing this game is completely unlike playing any other game.  You will experience ten minutes of pumping adrenaline, shouting and panic as five people all try to coordinate their actions against the clock.  Make a mistake, lose track of what room you thought you were in, press the fire button at the wrong time and the whole carefully laid plan can fall down around you.  Everyone is relying on you, and you are relying on everyone else.  But each game only takes around 20 minutes, so if you fail horribly (and you will), just get back up and try again.

Galaxy Trucker

I love Galaxy Trucker.  It’s very high on my list of “Games to try with people who don’t play board games”.  The premise is simple: build a spaceship out of junk and fly it to the other side of the galaxy, and hope it makes it in one piece.

This is another game of two halves, one frantic half against the clock and a more sedate resolution phase.  The best bit is building your spaceship.  Each player has a board with squares on in the rough shape of a spaceship.  In the middle of the table is a pile of face-down square tiles.  Each of these tiles is a ship component (such as an engine, laser or crew compartment), and each has different shaped connectors on each edge.  You build a ship by taking a tile, looking at it, and then either connecting it to an existing compatible connector on your ship, or placing it back on the pile face-up.  But, there is no turn-taking.  Everyone plays are once, grabbing pieces, looking at them, and deciding whether to attach them or put them back on the table.

What you’ll get is a mad dash as everyone grabs components looking for the best bits for their ship.  But as you’re taking new tiles you have to keep an eye on what’s being thrown back, in case it’s that battery with the awkard connectors you’ve been looking for.  As the tiles start to run out the panic can set in as you realise you still need to find shields or engines and you just can’t get them.

It’s all so tactile, and the few rules about how components fit together are pretty simple and all make sense.  It’ll take five minutes to explain the basics to new players before they’re building their first ships, and this is what makes it so approachable for novices.

After the building phase there is a simple adventure phase, where random event cards are used to throw asteroids, pirates and planets full of loot at the players.  Bits fall off the ships when they’re hit, and there is great comedy potential as you watch a lucky asteroid hit cleave your friend’s precarious construction in half before it limps to the destination with nothing but a crew compartment attached to an engine.  But nobody minds because the whole thing is over in 20 minutes again so you just move up to a bigger and better ship and try again.

So, Space Alert and Galaxy Trucker are two of the most fun games I’ve played recently, and I don’t think that it’s a coincidence that both involve real-time gameplay.  I appreciate a complex strategy game as much as the next geek, but playing these games scratches a different itch and comes much closer to what we think of as playing in the traditional sense.

Dec 222012
 

These days I’m mainly working with tablet devices including the various flavours of iPad.  A year ago there was just the iPad 1 and the iPad 2, but now the 3 and 4 also exist, as well as the mini.  Here is a summary:

  • iPad 1 – Very limited performance and memory.  The GPU appears to be around 5-6 times slower than the iPad 2, with the same resolution.  Getting a decent frame rate with any kind of non-trivial graphics is challenging, and you can most likely forget about 60Hz.
  • iPad 2 – This is a very balanced system.  Much quicker than the iPad 1, it’s pretty easy to achieve silky-smooth 60Hz with a decent amount of overdraw and alpha blending.
  • iPad Mini – Almost exactly the same performance as the iPad 2 and the same resolution, just a bit smaller.  This device adds no more complications which is nice.
  • iPad 3 – This is a pr0blematic device.  Double the GPU power of the iPad 2, but four times the pixels on to the retina display.  Due to everything being alpha blending in our app, the profiler shows the GPU cost to be double that of the iPad 2.  This is our limiting device.
  • iPad 4 – Double the CPU and GPU again.  This brings the GPU performance back up to the level of the iPad 2.

The iPad 3 is a bit of a blip.  The tiled rendering architecture means that an app predominantly rendered with layers of alpha-blended geomety can expect a 2X performance penalty on the 3.  The 3 is actually the limiting system, more so that the 2.

[Aside on the tiled deferred shading if you’re not familiar – The screen is internally divided into a grid, with each grid block made up of some number of actual pixels.  For each block, during rendering a list is kept of all geometry that intersects it.  At the end of the frame, visibility calculations are done on each pixel, and then only the geometry that contributes to the pixel colour is shaded.  Deferring all pixel shading until the end of the frame means that when drawing solid geometry, each pixel only has to be shaded once at the end of the frame, instead of being shaded and then overwritten as more geometry is drawn.  However, with alpha blending, all layers contribute to the final pixel colour so all geometry has to be shaded.  This negates all performance gains from the tiled deferred shading, hence why alpha blending is bad on iPads and iPhones.  Unfortunately, to make nice looking UIs you can’t really get away from it.]

Dec 182012
 

When we want to draw something in 3D on a screen, what we’re really doing is trying to draw a flat picture of it as it would look on a film, or projected onto the retina in your eye.  So we have an “eye” position, which is the point from which the scene is viewed, and we have the projection plane, which is the “film” of the camera.

When you take an image with a camera the image is projected reversed onto the film, because the projection plane is behind the lens (you can see this by looking at the path the light takes through the lens, in red).  When rendering, it’s conceptually simpler to think of the projection plane as being in front of the eye.  It’s also easier to see what we mean by a projection – we can think of the projection plane as being a window in front of the eye, through which we see the world.  Each pixel wants to be drawn the colour of the light that passes through the corresponding part of the “window”, to reach the eye.

A basic property of a camera is the Field Of View (FOV).  Cameras don’t capture the scene in a full 360 degrees, and the FOV is the angle which it can see, which is the angle between the red lines in the diagram.  Continuing the window analogy, there are two ways to change the field of view: you can make the window bigger or smaller, or you can stand closer or further away from the window.  Both of these will alter how much of the world you can see on the other side.

The most basic concept in 3D is perspective.  It’s so simple that it’s been explained by Father Ted.  Perspective just means that the further away things are, the smaller they look.  Further to that, the size reduction is proportional to the distance.  What this means is that something twice as far away will look half as big (specifically, half as big when you measure a length, the area will be a quarter of the size).  So if you want to work out how big something will be on the screen, you divide the size by the distance from the eye position.

To start rendering in 3D we just need to know a few numbers that define the “camera view” that will be used to draw the scene.  These are the size of the projection plane, and the distance it is from the eye (the projection plane is always some small distance in front of the eye to avoid nastiness later on with divide-by-zero and things).

In the diagram, take one grid square to be 1 unit in size.  It makes no difference what the units are, as long as you’re consistent.  For simplicity let’s work in metres.  So in this diagram we can see the two pieces of information we need.  The distance from the camera to the projection plane (called the camera near distance) is 1 metre, and the size of the projection plane is around 1.5 metres (specific numbers don’t matter at this point).  You can see the field of view that this arrangement gives in red.  In this diagram we want to draw the blue triangle, so we need to know where the three corner vertices will projected to on the projection plane.

Positions in 3D space are given using three coordinates, x, y, and z.  These specify the distance along the x axis, y axis and z axis respectively, where the three axes are perpendicular to each other.  There are various different coordinate spaces used in rendering, where coordinate space means the orientation of these three axes.  For example, world space is where things are in you ‘world’, i.e. the scene that you are rendering, so there is the origin (0, 0, 0) at some fixed point in the world and everything is positioned relative to that.  In this case x and z specify the horizontal position and y specifies the height.

The coordinate space we’re interested in at the moment though is camera space.  In camera space, X is the distance left or right in your window, y is the distance up or down, and z is the distance forwards and backwards, i.e. into or out of the window.  The origin is at the eye position and the camera traditionally looks along the negative z axis, so in the diagram the z axis will point to the right.  The diagram is 2D so only shows one of the other axes, so we’ll ignore the third one for now.

We can now do a bit of simple maths to work out where to draw one of the vertices, the one marked with a dot.  The approximate position of the vertex is (1.0, -5.2), by counting the squares in each axis (yes, this is the other way around from your traditional axes on a graph, but that just reinforces the point about different coordinate spaces).  So to project this on the screen we simply divide by Z to find the point that the green line intersects the line where Z=-1.  This give X = 1.0/-5.2 = -0.192.

Now we need to convert this to screen space, which is as shown is this diagram:

This is where we use the size of the projection plane, and the distance it is from the eye, to find a scaling factor.  We said that the projection plane was 1.5m is total, so is 0.75 metres from the centre to each side, and is at -1.0 metres from the eye along the z axis.  So the scaling factor is -1.0/0.75 = -1.333.

Now we can combine these to find where on the screen the vertex should be drawn:

X = -0.192*-1.333 = 0.256

There is one final transform that needs to be done, to work out the actual pixel coordinates on the screen.  To do this we simply map the -1.0 to 1.0 range of the screen space into the viewport, which is defined in pixels.  So if you’re drawing to a widescreen TV the viewport would be 1280×768 pixels in size, so the actual x pixel coordinate of the example would be:

((1.0 + 0.256) * 0.5) * 1280 = 804

Then simply do the same again with the Y axis and you  drawn a 3D point!  Do this with the other two points as well, and then draw straight lines between them all, and you’ve got a 3D triangle!

This works as long as the camera is at the origin, looking straight down the z axis.  Next time I’ll talk a bit about transforms and how this is generalised to any view.

Dec 052012
 

Or more precisely – “Anatomy of a modern realtime photorealistic 3D DX11 renderer, in layman’s terms”.

Modern 3D graphics and rendering techniques tend to be viewed as really complicated, specialist and difficult by those not involved in it.  There is an aura of “magic” around how computers can produce the images shown on the screen, and practically zero understanding of how this works.  I’m not even referring to just the general public (although it is certainly “magic” in this case) – even among programmers in other areas, and even a lot of games artists, there is a perception that the renderer is too complicated to understand.

So, in this series I aim to change that.  I will try to explain a bit about all of the processes going on behind the scenes, and show in rough terms how they work, in non-technical language.  If you’re reading this series and it’s too hard to understand, let me know and I’ll see if I can improve it!

The first part of the series will give a general overview of basic 3D graphics, of how to get anything drawing so it looks 3D on the screen.  This requires some knowledge of perspective and camera transforms but I’ll keep it simple!  That will take you up to the state of the art of realtime computer graphics circa 1984, which a few of you may remember:

The next jump up was full polygon-based rendering, enabled by these new-fangled graphics card things.  This approach is still what almost all game engines are based on, so the second part will give an overview of basic polygon rendering.  This is the state of the art in 1996:

After that we have all the really interesting stuff!  There are loads of cool and interesting techniques involved in taking us from Quake in 1996 to Battlefield 3, which is a pretty good representation of the state of the art in 2011:

These cool techniques include things like high dynamic range, Bokeh depth of field, physically-based lighting models, antialiasing, tone mapping, bloom, and a whole host of other things, all designed to simulate a real camera in the real world, thus giving us a believable image.  This will be the bulk of the series as it’s where all the interesting things are happening these days.

So that’s my intent.  This may be a fairly long-term project but I want to show that modern computer graphics doesn’t have to be hard or obscure, and really anyone can understand it!  Until next time…

Nov 272012
 

Hello!  So, I thought it was about time that I started a blog.  The general focus will computer graphics, computer games, board games, science and anything else that’s interesting me at the time.  Enjoy!