Moving to a new site

The time has come to move this site over to my own domain at www.alexrodgers.co.uk. This way I can vastly improve the site and not be restricted by a directly managed service. It’ll still be running WordPress software, but I’ll have much greater access to tools, scripting and hosting facilities.

Apparently, I’ll need to pay WordPress £10 a year until the end of time if I want to keep the traffic redirected to my own domain, so instead, I’ve stuck a massive header at the top (hopefully you can’t miss it) to shepherd any search engine visitors to the proper site.

All content has been transferred across and no new updates will be made here, but I’ll likely leave this legacy site online for a bit.

Again, click here to go to the new site: www.alexrodgers.co.uk

Thanks.

CUDA Ray Tracer – Dissertation Project

After on and off work for a year, and many thousand words later, my final year BSc dissertation project and report was completed. Can a ray tracer ever be truly ‘complete’? Considering endless potential optimisations and features that can be implemented, if one so desires, probably not! My report can be found here and below are a few renderings from my prototypes.

The project from a personal point of view was an important one. It was a period where I gained heightened interest in graphics programming, gaining an understanding of the principles of computer graphics, the mathematics involved and also the creative satisfaction that comes from it. When creating realistic virtual graphics from essentially nothing but code, maths and a display, on the face of it, it’s very easy to gloss over the ‘magic’ of it all, especially when you understand the complexity of how we actually perceive the Universe and the shortcuts that must be taken for computers to accurately mimic the natural phenomena of our brain’s visual perception.

A Bit of Biology and Philosophy:

The modern computer when you think of it, is really just a primitive extension of our own bodies, simple enough that we can manipulate, manage and understand it, with much greater control and predictability then our biology. They allow us to achieve things we could not otherwise do and many of the components inside a computer carry out very similar roles to organs found within us. Of course we can think of the CPU as a brain, but what else? Going into more detail, the GPU could be seen as a specialised part of the brain engineered to handle visual computation, just as our brain has it’s own visual cortex. A virtual camera in a rendering program replicates the capabilities of part of our eye, defining an aperture or lens through which to calculate rays of light, and like-wise, an ‘image plane’ positioned in front of the camera, carries out essentially the same functionality as our retina, but using pixels to make up the visual image of what we see.

When you understand the detailed steps required to render something in 3D, you realise that we are essential trying to recreate our own little simplified universe, it’s a pretty profound concept that when taken much further, manifests itself in popular science fiction such as the Matrix. After all, is mathematics not simply the ‘code’ of our Universe? It’s perhaps not as silly as it may sound, when you get down to the fundamentals of game developers creating virtual worlds, graphics programming being an essential component, and looking just how real and immersive these worlds are starting to become.

So What Is Ray Tracing?

Ray Tracing

Of all popular rendering techniques, it’s ray tracing that perhaps stands out the most in respect to my previous comments above. We all know roughly how and why we see, where light rays shine from a light source such as our Sun, they travel millions of miles to get to us and out of all the infinite number of rays, the tiniest percentage may find it’s way directly into our eye. This could be from directly looking at the Sun (not recommended!), and also from scattered or reflected light that has hit a surface, finding it’s way on a collision course with our eye.
This is fundamentally close to how ray tracing works, but with important differences. If a computer had to calculate the trajectory of all possible rays been fired out from a light source, this would be impossible with modern hardware, there are just too many potential rays, of which, only an infinitesimally small amount would ever find there way into the camera (eye) of the scene, and it’s only these rays we are interested in anyway. Instead, and referred to as ‘Backwards Ray Tracing’, light is fired from the camera (eye) into the scene and then traced backwards as it is reflected, refracted or simply absorbed by whatever material it hits. We then only have to fire a ray from the camera for each pixel in the image, which is still potentially a considerable number of rays (1920×1080 = 2073600 primary rays) and that’s without counting all the secondary rays as light scatters throughout the scene, but at least this reduced number is quite feasible.

Still, it is ray tracing’s close semblance to how light interacts with us in the real world that makes it a very elegant and simple algorithm for rendering images, allowing for what is known as ‘physically based rendering’, where light is simulated to create realistic looking scenes with mathematically accurate shadows, caustics and more advanced features such as ‘global illumination’, something that other faster and more common rendering techniques like rasterization (pipeline-based) cannot do.

Illumination and Shading:

Phong Shading

Phong shading

The ultimate main job of firing the rays into a scene in the first place is to determine what colour the pixel in our image should be. This is found by looking at what a ray hits when fired into a 3D scene. Put simply, if it hits a red sphere, the pixel is set to red. We can define the material information for every object in the scene in similar fashion to how we know in the real world that a matt yellow box reflects light. Technically, the box is yellow because it reflects yellow light, and is matt (not shiny) because it has a microscopically uneven surface (diffuse) that scatters the light more evenly away from the surface. Compare this to light hitting a smooth (specular) surface, most of the light would bounce off the surface in the same direction and appear shiny to our eyes. Clearly, for computer graphics, we are not likely to program a surface material literally in such microscopic detail as to define if it is rough or smooth, but we can cheat using a popular and effective local illumination model such as Phong, essentially using the ‘normal’ of a surface, the directions of our light source and camera and some vector math to put it all together and calculate the colour of the surface based on it’s material and angle, creating a smooth shaded object rather than a ‘flat’ colour.

Intersections, Distance Functions and Ray Marching:

Implicit Functions

So we know why we need to fire the rays, but how do know a ray has hit a surface? There’s a few different ways this can be done, all down to the complexity of the geometry you’re trying to render. Ray intersections with simple shape such as planes or spheres can be calculated precisely using linear and quadratic equations respectively. Additionally, for complex explicit 3D models made from triangle mesh, linear algebra and vector math can also be used to compute the intersections.

Another technique, has been gaining popularity in recent years, despite been around quite some time in academic circles. Rendering complex implicit geometry using ‘distance functions’ with nothing but a pixel shader on your GPU as shown on websites like Shadertoy have popularised a subset of ray tracing called ‘ray marching’, requiring no 3D mesh models, vertices or even textures to produce startlingly realistic real-time 3D renderings. It is in fact, the very freedom from mesh constraints that is apparent when you observe the complex, organic and smooth ray marched geometry possible using the technique. Ray marching allows you to do things you simply cannot do using explicit mesh, such as blending surfaces seamlessly together, akin to sticking two lumps of clay together to form a more complicated object. Endless repetition of objects throughout a scene at little extra cost using simple modulus maths is another nifty trick allowing for infinite scenes. By manipulating the surface positions along cast rays, you can effectively transform your objects, twist, contort and even animate; it’s all good stuff.

The Dissertation Project:

My development project was comprised of two parts, a prototype phase to create a ray tracer using GPGPU techniques and a hefty report detailing the theory, implementation and outcomes. For those unfamiliar, General-purpose computing on graphics processing units (GPGPU) is a area of programming aimed at using the specialised hardware found in GPU’s to perform arithmetic tasks normally carried out by the CPU, and is widely used in supercomputing. Though the CPU hardware is singularly much more powerful than the processors in a GPU; GPU’s make up for it in sheer numbers, meaning they excel and outperform CPU’s when computing simple highly parallel tasks. Ray tracing, is one such highly parallel candidate that is well suited to GPGPU techniques and for my dissertation I was tasked to use NVIDIA’s GPGPU framework called CUDA to create an offline ray tracer, done from scratch using no existing graphics API. Offline rendering means not real-time, and is clearly unsuitable for games, yet is commonly used in 3D graphics industry for big budget animations like those by Pixar and DreamWorks, with each frame individually rendered to ultra high quality, sometimes over a period in excess of 24 hours for a single frame.

In the end I produced four different ray tracing prototypes for comparison, incorporating previously mentioned techniques. Prototype 1, running purely on a CPU single thread using simple implicit intersections of spheres and planes. Prototype 2, the same but implemented using a single CUDA kernel and running purely on the GPU across millions of threads. Prototype 3, a CPU ray marcher using distance functions to render more complex implicit geometry. Prototype 4, the same as 3, but implemented using CUDA. My aim for the project was to assess GPGPU performance and the rendering qualities of the ray marching technique, the findings of which can be found in the report.

I knew when I picked this project that I was not taking an easy topic by any stretch, and a great thing I can take away from this is the extensive research experience and planning needed to simultaneously implement many different difficult concepts I had no prior knowledge about, yet still managed to produce a cohesive project, and fully working prototypes, achieving an 88% mark for my efforts, which I am very pleased with. As expected, with heinsight there are things that I would do differently if repeated, but nothing too major, and really, it’s all part of the learning process.

Ray tracing, ray marching, GPGPU, CUDA, distance functions and implicit geometry were all concepts I had to pickup and learn. I bought some books, but in the end, research on the internet in the form of tutorials, blogs, academic papers and lectures proved more beneficial. Sometimes, it takes a certain kind of way to present the information for your brain to ‘click’ with certain principles, and all of us are different. The Internet is a treasure trove in this regard, if you spend the time, you can usually eventually find some explanation that will suit your grey matter, failing that, re-reading it a million times can sometimes help!

Future Plans:

On the back of this, I will be continuing this subject into my masters degree and will likely be pursuing this further during my masters dissertation. I am already busy at work on a real-time implicit render with UI functionality running in DirectX 11 (A couple of early screenshots above). Additionally, I’d love to get a chance to contribute to a research paper on the subject, but we’ll see.

I plan to make some easy to follow tutorials on implementing ray tracing and ray marching at some point for this website, when I get the chance. Hopefully, they could  help out other students or anyone else wanting to learn the aforementioned topics. I know first hand and from friends, that at times it can be frustrating since although there is theory out there, there is comparatively very little information on actual implementation details for the subject, when compared to say pipeline-based rendering.

Dungeon Master – An Iconic RPG

Box Art

Box Art

Aged probably no more than 6, I looked on in excitement and fear at the Amiga monitor. My parents were playing Dungeon Master again, it’s labyrinthine dungeons, fiendish puzzles, stunning graphics (for the time) and always death, waiting around the next corner.

Dungeon Master was a pivotal game of my childhood, it taught me how real and immersive games could actually get, despite computer limitations. Using a 2D perspective trick, it could render a seemingly 3D environment as if seen from the eyes of the player. This of course was an illusion, but it did it so effectively, that it stood out back then with hugely impressive visuals. It wasn’t just nice to look at though; featuring groundbreaking level design and puzzle concepts, being brutally difficult but still rewarding; there was something about it that left a lasting impression on you. It was a little like the Dark Souls of it’s day.

Although there had been other well known ‘dungeon crawler’ games (as they came to be known) like Bard’s Tale and Wizardry, it was DM that really culminated the best attributes of the genre, distilling it into what is in my opinion the best of the lot, even to this day. It’s no coincidence that Almost Human’s ‘Legend of Grimrock’ in 2012, cited Dungeon Master as large inspiration and something that is clearly evident having finished Grimrock and noticing many ‘tips of the hat’ to DM’s puzzles, mechanics and creatures. All those puzzles of putting an item on a pressure plate to close a pit, or placing a torch in a wall sconce to open a secret door hearken back to this era.

DM was in fact the largest selling title of all time for the Atari ST, whose version differed only mildly from that of the Amiga, with the latter featuring improved 3D sound effects where most noticeably, you can hear creatures moving around with unnerving effect.

Using the free Amiga emulator WinUAE the past week, I have finally finished Dungeon Master after all these years. I loved every second of it, scarily so, because I was telling myself continually throughout, “why am I playing a 27 year old game in this day and age?”. Irrespective of the answer, I had more fun playing it then most state of the art games I have played recently! Why? Well, many reasons, the challenge and immersion are two, but ultimately, I guess I’m a pretty hardcore gamer and there’s just something about playing old school classic RPG’s, a charm or ambiance if you like, akin to rolling that dice in a pen and paper D&D game. I’m sure many can empathize with that.

A pack of skeletons.

A pack of skeletons.

Dungeon Master does have a story and plot, though sparse and not a driving force for the progression of the game. It revolves around having to descend into the depth of the mysterious dungeon and find an artifact known as the ‘Firestaff’, as tasked by your master ‘Lord Order’. Ultimately, if your party survive the horrors long enough, you come across writings detailing the evils that will occur should you complete this quest and instead come to realise that you must descend to the deepest depths of the dungeon, combine the staff with the ‘power gem’ and defeat ‘Lord Chaos’ (think Sauron), restoring ‘Balance’ to the world.

You start the journey in the ‘Hall of Champions’, a place at the start of the dungeon where you can look upon windows on the walls and see magically suspended heroes, whom you can either ‘resurrect’ or ‘reincarnate’ to join your party, up to a total of four party members. Resurrection ensures the character maintains it’s identity, combat skills and experiences whereas reincarnation allows you to rename the character, forfeiting their skill set, but gifting them enhanced physical attributes so to enhance learning and allow you to shape the character as you see fit. Ultimately, the tried and tested composition of two fighters at the front, a priest and a wizard at the back worked wonders for my play-through, though having four ‘jack-of-all-trades’ is viable too. As 2012’s Grimrock, the party moves through the dungeon in 1st-person view in a 2 by 2 formation, meaning that only the two members of your party at the front can reach enemies with melee weapons, with the back two having to rely on ranged, throwing weapons and spell casting. Consequently, only the front two will take damage from the front, and if a ‘baddie’ creeps up behind you, your squishy casters won’t be very happy. Part of the the games meta strategy, involves you being able to change your players around in the formation at any time e.g if your front fighters get wounded, you can swap them out with the back.

Character Inventory.

Character Inventory.

The predominate theme of the game is undoubtedly ‘survival’. Staying alive is really, really not an easy thing unless you have learned the tricks and techniques generally gained after many horrible deaths, whether that be to the jaws of giant worms, starvation or plummeting down a pit arriving several levels lower than you could possibly hope to deal with. The only items you have at your disposal are those you find along the way, and that way is strewn with illusory walls, guarded chests, locked doors and secret passages that without consulting a guide or a printed map, you have little chance of ever finding yourself (hand holding pfff who needs it?). Even basic concepts we all take for granted in games today such as being able to SEE, is a premeditated game mechanic in dungeon master, where the dungeons are pitch black without a light source and torches are scarce, making the use of a wizard or others with the skills to cast ‘light’ spells essential.

One of the  most memorable mechanics which is still pretty innovative today is the magic system. To the right side of the screen are a bunch of runic symbols. The boxed game’s manual documented an alphabet of these symbols describing there purpose. As you cast a spell you first choose a rune representing the ‘power’ of the spell, would you cast a short duration spell or a potent offensive spell for instance? Then sequentially you chose the spells ‘elemental influence’, ‘form’ and ‘alignment’. It all sounds rather complicated but when you know off by heart that a weak fireball is LO FUL IR and a potent healing potion is PAL VI, it starts to become second nature, especially when you realise you can drop the power level if your priest is low on mana and make a weaker healing potion like LO VI for instance. In combat, you would be expected to click these runes in the correct order at the heat of the moment, you soon realised that if you didn’t ‘get gud’ and memorise them, then you simply got ‘dead’. In a funny kind of way, it really did feel like you were learning magic and having to go through the motions to learn and cast the spells your party depended on and I love that.

These runes are used to cast all the games many Wizard and Priest spells.

These runes are used to cast all the games Wizard and Priest spells.

Other mechanics such as food and drink meters for each character really puts that hanging dread over your party for the entirety of the game, since you never know when your next meal is coming up and when you’ll see a fountain again to refill your water skins. Realising your lost deep somewhere with no water left and down to your last couple of hunks of meat is pretty terrifying. Luckily though, some of the critters are edible if you can kill them, ‘Screamer Slice’, ‘Worm Round’ or ‘Dragon Steak’ anyone? Yum!

A water fountain, always a welcome sight!

A water fountain, always a welcome sight!

Having finally finished the game after all these years, I felt an immense sense of accomplishment because it’s a game that I grew up thinking was simply too tough for me to contend with, and to be fair, me being less than 10, it probably was! The end showdown with Lord Chaos is no simple matter. Once you have collected all the ‘Ra keys’, broken into the vault of the Firestaff, defeated it’s Stone Golem guardians and retrieved it, you then have to descend to the last level, defeat a wingless dragon and free the power gem with a spell you better have learned along the way or your buggered! (*cough* Google). You then must combine the staff with the gem, creating an ultimate weapon and then go back up a level and find Lord Chaos. Using the staff’s power you must surround him with ‘Fluxcages’ and finally ‘Fuse’ him to restore ‘Lord Balance’ and beat the game. If that sounds straightforward, it really isn’t, especially considering even if you do figure this all out on your own from a subtle hint in an very well hidden scroll, you have to do all this while being attacked by demons, black flame elementals and Chaos himself flinging fireballs at your face!

Defeating Lord Chaos and restoring Balance.

Defeating Lord Chaos and restoring Balance.

I’m currently now playing through it’s sequel ‘Chaos Strikes Back’ (Yes…it really IS called that) and it is unbelievably hard, as in Dark Souls has nothing, not a bean compared to this in terms of difficulty. CSM will eat you alive and then spit out your regurgitated remains for a second helping. Firstly, the sequel starts at the same difficultly level that DM ends at. You can import your characters which you may think will help and sure enough it does a little, but little prepares you for the first 10 seconds of the game which pretty much goes like this:

“Ok, let’s go, hmm it’s pitch black…where am I? My party is naked with no weapons…I can hear things moving around me…let me cast a light spell. That’s better! SHIT there’s four armoured worms in here with me and no exits…no wait, SIX worms…EIGHT….I’m surrounded…can’t move….DEAD.”

That’s your first taste of Chaos Strikes Back, shoved into an infested pit of worms with no weapons and no obvious way out, but like Dark Souls, I still love it.

As reported in 2012 in a Rock, Paper, Shotgun article here, one chap amazingly spent 6 months, eight hours a day of his own time, programming 120,000 lines of code to port the Atari ST version, creating a C++ executable version that runs today on any modern PC. It can be found here free: Chaos Strikes Back for Windows (and Linux, MacOS X, Pocket PC)

For those used to emulators, by getting hold of the Amiga .adf ROM file (basically an image of the game disk), you can run it in WinUAE (my personal preference for the better sounds) but ultimately, only ex-Amiga junkies would likely do this over the ported PC version :D.

Dungeon Master is a truly iconic game that has undoubtedly influenced many great games, not just across the dungeon-crawler and RPG genres like the classic ‘Eye of the Beholder’ series or recently the ‘Legend of Grimrock’, but also modern popular AAA titles such as the Elder Scrolls. It’s a testament to it’s influence that the game still has it’s own updated Encyclopedia site: http://dmweb.free.fr/  and even an online message forum with an active and thriving community: http://www.dungeon-master.com/forum/.

I would encourage anyone who is curious about classic RPG’s games, interested in why modern games are like they are and all that jazz to check out old titles like Dungeon Master, because although the graphics leave much to be desired by today’s standards, the game play is still truly as good as it ever was. It’s clear there is still much to wonder and marvel at, in both game design and execution in this old gem.

My party in the hall of fame after beating the game!

My party in the hall of fame after beating the game!