WebGL Ray Tracing

The past couple of weekends I’ve been trying out some WebGL powered rendering that can be embedded into my website. Above is a little something I coded up, made by ray marching implicit surfaces using distance fields (after being inspired but some of the content over at shader toy). I recommend viewing it in a Chrome browser, but any browser that supports WebGL should do. Currently, it doesn’t work on Edge or IE browsers which tend to have a hard time with WebGL support, as evident with the shadertoy site that has the same trouble.

I’ve done a few things with ray tracing/marching techniques previously but it really is a joy to work with when you get it down, allowing you to focus on the rendering without needing explicit models, textures or lots of boiler plate code to create great looking scenes.

The above implementation is only a little over 100 lines of code in a pixel shader. Other then that, WebGL requires a tiny bit of initialisation code and there’s a pass-through vertex shader, and that’s it. So far, WebGL seems great and I’m tempted to make a basic little game with it to embed at some point.

For anyone wanting to do something similar I’d recommend the Atom text editor with plugins for GLSL syntax highlighting and a nifty little plugin called Browser-Plus that allows you to use an integrated web browser that will auto-refresh when you save code changes. Using a split screen setup it was a great way to immediately see changes as I coded them without having to mash F5 over and over.

Procedural RPG World Generation

Featured

Having now completed my MSc, below is a brief summary of my dissertation project along with galleries and a video of the prototype. There’s also a download of the full report detailing the implementation process along with background on the topic for those interested in procedural content generation or studying something related.

Report:

671 Downloads

Video:

Since the days of Rogue, and Elite, games have utilised various procedural content generation techniques to create game worlds for players to explore, freeing developers from the hand-crafted approach typically seen in the majority of games. For me, it was the second Elder Scrolls game, Daggerfall in ’96 that inspired me enough to prompt this topic choice for my MSc dissertation project. Although Daggerfall was most certainly a flawed game, the sheer size of the game world is still unsurpassed even today, being roughly 162 square kilometers (about half the size of the Great Britain) and featuring over 15,000 towns, villages and dungeons. An amusing rumor is that it’s so big that you can fit every other subsequent Elder Scrolls game world into a pixel on Daggerfall’s world map.

When you have a game world that big, procedural content generation (PCG) is the only feasible way to populate it. Daggerfall’s world was generated ‘offline’ and shipped on the game media, making the world the same every time you played it. It’s main story-line areas and characters were hand-crafted, but the rest of its towns, dungeons and wilderness areas were all generated.

Scale comparison of the Elder Scrolls games.

Scale comparison of the Elder Scrolls games.

What I wanted to do, is to tackle a project that aimed to generate an RPG world in real-time so each world would be unique, and ultimately create an explorable 3D RPG world generator. What I actually wanted to do was create a full RPG game to play within these generated worlds (i.e. my dream game), but clearly this would never have been feasible in the time-frame and so I settled for a compromise by removing any game mechanics or AI from the project, effectively stripping out the ‘game’ aspect. Even with this, the project workload was going to be ridiculous considering I wanted to use my own DirectX engine and use it to generate the world, complete with dungeons, NPC towns and a day/night cycle.

Unlike most of my previous projects, there wasn’t going to be much focus on graphics and that actually fit nicely with my retro vision for a more modern looking Daggerfall-esque game, complete with sprites…lots of sprite.

My report can be found at the top of this post if you’re curious about some of the techniques I used in the prototype. I had little knowledge of how other games have really approached this from a technical point of view, other that what I had uncovered during my research on the topic. The developed prototype is therefore very much my own approach.

Since, the detail is all in the above report, I’ll just briefly mention some of the techniques the prototype involved:

The world generation itself was created using a procedural noise technique to generate a height-map. Multiple octaves of value noise are combined (Fractional Brownian motion) to create a resulting fractal noise suitable for generating realistic terrain formations. The noise implementation I used was specifically Voronoise, a method that combines a value grid-based noise type and a ‘jittered’ grid version of Voronoi (cellular noise) into an single adjustable function. I introduced a seed value into the noise generation to allow for reproducibility of worlds, given the same seed. The height-map is output in the pixel shader to a render target upon generation, and then used during the tessellation shader stages via patch control-point displacement when rendering the world.

fBM3

Summation of noise octaves.

terrains

A variety of generated worlds.

The prototype’s generated world size is not huge like Daggerfall, but it’s a fair size at around 16,777 square km. That’s a little under half the size of Skyrim’s world for example, but for a little prototype I’m happy with this and it still allows plenty of explorable terrain using the appropriate movement speed and not the super fast one as seen in my video!

Dungeons use a completely different generation method that I implemented off the top of my head after looking into various techniques. It’s an agent-based technique that uses diggers to burrow out corridors and rooms, with various rules thrown in to keep them in-check to ensure they generate sensible looking dungeons. They are also responsible for spawning the dungeons contents which include monsters and treasure chests and the up and down stairs. Here are some ASCII representations of the dungeon layouts generated by the method:

dungeons

The world is divided up into 32×32 terrain chunks that are each responsible for hosting their respective game objects such as flora, fauna, towns and dungeon entrances. For performance purposes frustum culling was a necessity due to the large scale of the terrain, and only chunks visible in the frustum are processed. Each chunk has a chance of creating towns and/or dungeons and checks such as suitably flat terrain are important factors in determining this. Each building performs a suitability check on the terrain mesh at a chosen spot to see if its within the gradient threshold, and if so places a random structure. If enough buildings are present in a town, NPCs will spawn within proximity of the town.

I added a few small graphical enhancements to the game such as faked atmospheric scattering, fog, layered sky domes, water and emission mapped buildings at night. They are each detailed in the report, but ultimately time was limited and any graphical enhancements were really a secondary concern. Despite this, I really wanted to add them and I think it does enough to achieve the overall atmosphere that I had envisaged, as demonstrated in the below comparison with a Daggerfall screenshot:

DaggerfallComparison

Aesthetic comparison between Daggerfall (left) and prototype (right).

The prototype initially starts into the table view where a map of the generated world is shown that can be rotated and zoomed in/out for examination. At a key press the camera moves into the first-person mode and plonks the player into the world. Worlds can be generated in first-person mode but it’s much more intuitive to do it in the table view. By tweaking the various settings in the UI i.e. noise values, town frequency and tree density; worlds can be tailored to whatever style you want, although currently you have to understand each of the noise settings and their influence on the generation process, to create something you have in mind. Failing that though, there’s trial and error. Ultimately, I’ll add predefined terrain settings that can be selected to simplify this process since it’s really not intuitive to know how ‘lacunarity’, ‘gain’ or ‘frequency’ for instance will effect the world, but academically, it’s quite useful to have them directly tweak-able. A seed value can be directly entered into the UI, with every unique value resulting in a unique world.

I hope at some point to continue with the project. There will be a hiatus for the foreseeable future while I work on other things. There is near infinite scope for the project, with so many things to add so it’s likely something I can keep coming back to.

I also produced a nifty tool for visualising noise which could have various uses for demoing. I’ll probably get this uploaded with a download of the prototype itself at some point.

As detailed in the report, the prototype uses various art assets (models/textures) sourced online via Creative Commons license. The project is for non-commercial use and many art assets are effectively placeholders used to finish the prototype during my studies.

 

 

Hybrid Rendered Dragon Scene (Ray Marching, Forward Rendering)

Featured

This is a quick run down on my Advanced Rendering coursework submission. It uses my own renderer using C++ and DirectX 11. Below I’ll basically post the report contents that I submitted with the code which details how each effect has been implemented.

Effect Descriptions

Effect 1: Chamber Room Environment

The chamber walls and ceilings were ray traced by ray marching implicit geometry using distance functions.

The walls and ceiling are done inside the pixel shader on an screen sized quad. I then perform a second ray tracing pass for the interior pillar geometry. I did this in a separate pass in order to be able to blend the geometry in the correct order i.e. the pillars needed to sit on top of the forward rendered floor which meant I would need to render first the walls, then the floor  and finally the pillars. The hybrid ray tracing and forward rendering passes were combined in the scene using blending.

The structure is comprised of 4 large radius spheres for efficiency. The texture and bump-mapping effect is done via ray tracing a texture lookup and modifying the distance function to adjust the intersection point on the ray based on the texture sample.

All lighting in the program is done based on the ‘Blinn-Phong’ reflection model.

Effect 2: Animated Dragon

The dragon is a forward rendered basic mesh model with texture-mapping and shading. The dragon is animated via the vertex shader performing multiple different motions of local body parts. The tail sways up and down and the neck and head move gently but differently from each other. Breathing was also emulated on the dragon’s torso and throat.

The animation aims to give the impression of a living, breathing creature guarding its treasure horde. The animations themselves were performed by passing in a timer value to the vertex shader and using ‘smooth step’ functions of time, sine and cosine.

Normal bump-mapping is also implemented using a separate normal map texture.

Effect 3: Four Bumpy Stone Pillars

Similar to the walls and ceiling, a separate ray tracing pass was done for the stone pillars. Four capped cylinders were defined using distance functions. The parallax bump -mapping was done in the same way as before.

Effect 4: Geometry Shader-based Particle Systems

9

Both fire and smoke particle system effects were created on the GPU using the geometry shader. The systems are created from a base mesh model of a cone  (procedurally generated). Each cone vertex is input individually into the geometry shader which then creates an additional 3 vertices to form a quad, effectively transforming the cone into a quad array. The resultant quad is bill-boarded to ensure it is always facing to the camera.

The particle systems are animated using functions of time, sine and cosine inside the vertex shader.  The fire system uses additive blending. The smoke particles use an alpha fade to make them appear transparent.

The centre fire can be toggled to show the original preserved shape using the  ‘FireShape’ UI variable.

A mesh model of a wall torch was used to contain the fire and smoke particle systems for each pillar. The torch is forward rendered and features normal bump-mapping. An additional central fire inside a torus brazier was also added.

Effect 5: A Procedural Bumpy Floor

The floor is made from a single quad primitive input into the tessellation  stage of the shader pipeline (hull and domain shaders). The quad is tessellated in a triangle domain using a variety of partitioning methods changeable via the UI. The domain shader also perturbs the height of the floor using a ‘smooth step’ function based on the coordinate of the tessellated triangle patch, sine and cosine.  The normals are also recalculated by processing two adjacent positions with the same function, calculating a slope for each and normalizing them.

View dependent tessellation is implemented inside the hull shader based on the camera distance from the floor plane. The closer the camera is, the more triangles are tessellated.

Effect 6: Ellipsoid and Torus using Tessellation Shaders

Both the dragon egg and brazier are made from single points that are input into the pipeline and converted inside the domain shader using parametric representations of an ellipsoid and a torus. This is done by ‘wrapping’ the patch UV coordinate space around the respective shape.

Effect 7: Dragon Tail Spikes

18

The dragon tail spikes were created inside the geometry shader by calculating  a single new centroid vertex and utilising the existing vertices to form three new triangles faces. The effect was localised to just the tail using the world position of the vertices.

Extra Features:

Extra features include a strong wooden door made by texturing and bump mapping a quad. I also added some precious gem stones to the floor made the same way as the egg (parametric ellipsoid) but tessellated much less to make them look more geometric.

4

This coursework took my in the region of 2-3 weeks including research and learning the more advanced shader pipeline stages such as hardware tessellation and geometry shaders. Blending the scene components together was quite a headache and there are some noticeable blocky bits around the particle systems when they over lap caused by some issues I had blending everything together. Despite this it was a great learning opportunity for some of the more advanced forward rendering techniques and luckily my past experience with ray tracing helped a great deal. In the end I received a mark of 96% for it.

3D Pinball Game – Development Project

Featured

 

This is a 3D pinball game developed as part of my MSc Computer Science. The module was a group project and we were tasked with developing a 3D pinball without using an existing propriety game engine (such as Unity or Unreal etc.).

I developed an easy to use DX11 renderer for use by the group and we incorporated the Bullet physics and FMOD libraries to put the game together.

The time constraints on the project were intense and so this was put together in around 10 days (some crazy hours ensued). Many cans of energy drink and cups of coffee later this was the result. Its not exactly pinball FX but factoring in timeframe and tool constraints, I’m pleased with how it turned out. I wouldn’t expect a public release any time soon though!

Gallery:

Bullet physics is pretty fiddly to get up and running and took a bit of research to get to grips with. As with most open source libraries there are many conflicting sources of documentation and versions floating around which often serve only to confuse, but for a free physics library you can hardly complain.

I worked on quite a bit of the project, putting together the renderer and framework that the group used for production. I programmed the graphics, did any required artwork (base textures were sourced online) and worked a lot on the important physics such as the flippers and launch mechanism. With more time we could have improved quite a bit, as it stands the physics aren’t on a fixed time step and neither is it on an independent thread, therefore bad things happen if the frame rate gets low. For this reason it’s designed to run more or less perfectly on the system we developed it on and we were marked on, but it would need a fair bit of improvement to get it working nicely on any system and I doubt I’ll have time for that any time soon.

The project was probably my first real taste of game dev crunch or ‘death march’. Really it was worse, with 16+ hour days, often leaving the lab after sunrise. In the end, I think it was worth it though and I had actually always quite fancied trying my hand at developing a pinball game!

PS. Thanks to the guys (and gal) for such a hard-working group.

Falling Object Simulator – Simulation & Concurrency

Featured

 

As part of my MSC Computer Science degree, the Simulation & Concurrency module was probably the most intense module on the course, tasking us to produce a physics engine from scratch with robust network and multi-threading integration in order to implement a simulation of balls falling into a box, with removable trays and also a cloth simulated net.

Having done only a little previous physics programming for ‘The Column’, I set about researching the topic since implementing a solid and robust physics engine is no trivial task, even without a networking element. Although I found several good sources, for specific elements, Ian Millington’s ‘Game Physics Engine Development’ was an excellent book that covered many aspects of getting a basic physics engine up and running. I promptly devoured about a third of the book during this project though it lacks any real depth on collision detection and doesn’t real cover cloth simulation as I recall.

In the end I received 87% for the ACW which I’m pleased with. With more time I would have implemented rigid body motion but this second semester of the MSc has been pretty insane in terms of work load, mainly due to the fact that the UK carries out MSc degrees in a single year, rather then 2 like everywhere else in the world! Additionally, the University of Hull’s MSc degree is extremely practical, which although I find preferable to more theoretical based degrees (how better to learn then via implementation?) does result in a heavy work load. The good side is that if you put the work in, your get an extensive portfolio at the end of the degree.

Project Description:

The result of the project was a multi-threaded interactive falling object simulator developed from scratch using C++ and DirectX 11. The physics engine is a mass aggregate system using particles i.e. no rigid body motion. It features simple sphere and plane based collision detection and interpenetration resolution.

Each tray features different friction and elasticity attributes as per the specification.

An advanced feature is the cloth simulation for the net made using a lattice of spring constraints (Hook’s law) with four anchored corners.

Net collision detection is made using small spheres mapped to the vertices of the net, this however means I had to make the springs quite rigid to stop balls from forcing their way in-between the vertices hence the cloth is not very fluid or fluttery.

Without rigid body dynamics to get the cube rotations I used rod constraints connected to each vertex of the cube. This is a simple way to get rotations using just particles.

Rendering and physics integration are performed on separate threads, with an additional 3 threads for handling network. Rendering frame rate is hence independent from the simulation and both can be changed to run at a specific target rate.

Not shown in the video, but being a significant part of the project is the peer-to-peer network aspect. The program can be run on 2 peers, each peer will communicate and synchronise the simulation using linear interpolation of the scenes physics data. Each peer can be interacted with i.e. camera can be moved independently (think multiplayer) and commands such as open/close tray and spawn ball is communicated across the network to each peer. Network coding was done using Winsock. UDP broadcasting was used purely for peer detection and TCP for data transmission. Packet loss and latency resilience was also implemented.

Sandy Snow Globe – Deferred Shading

Featured

 

For the Real-Time Graphics module as part of my MSc in Computer Science we were tasked with developing a real-time graphics application representing a snow globe but with a few added twists. Instead of a wintery landscape, the theme would be desert with specific requirements including a day/night cycle, seasonal effects, shadow mapping and particle systems. Additional marks would be awarded for various advanced features, the highest being deferred shading. Having always wanted to try my hand at implementing it I went about researching the topic.

I implemented the project using my own engine I have been developing during my MSc written in C++ and utilising DirectX 11. The snow globe features deferred shading, particle systems, blending, PCF filtered shadow mapping, normal bump mapping, height mapping and environment mapping. The Snow Globe has a simple day/night cycle via two orbiting directional lights (Sun and Moon) and alternating summer/winter seasons. Summer nights = fireflies, winter nights = snow. Each firefly has a point light and using ‘deferred shading’, significant numbers of lights can be processed while maintaining good performance.

‘Deferred shading’, particular for non 3D programming experts, can be a rather tricky concept to grasp fully and so please find below my own attempt at describing what deferred shading is and why its a really cool technique.

Deferred Shading: Overview

‘Deferred Shading’ is a multi-pass rendering technique that has the distinct advantage of deferring the scene lighting to a second pass meaning put simply the calculation becomes one of a 2D domain rather then 3D. Usually with standard forward rendering, lighting is calculated in the pixel shader for every interpolated fragment after processing in the vertex shader. This means that every geometric object in your scene will be required to perform the lighting calculations which in ‘Big O’ notation looks like O(lights * meshes). The wonderful thing about deferred shading is that by using just one extra pass we can reduce that to O(lights + meshes) or to look at it another way in terms of fragments, we can reduce it from O(lights * geometryFragments) down to O(lights * screenFragments).

Deferred Shading - Sandy Snow Globe

Deferred Shading – Sandy Snow Globe

 

This has massive implications for performance. With forward rendering, more than half dozen or so light sources is enough to seriously impact performance, though modern games generally get away with this number by limiting how many are visible at a time. Deferred shading however as demonstrated in the above video can handle many times that amount of lights simultaneously with little performance impact. For the coursework I demonstrated a scene with 100 point lights which although pushed the GPU a little, still ran comfortably at over 30 FPS.

There are multiple deferred rendering techniques with ‘deferred shading’ being a 2 pass solution unlike ‘deferred lighting’ which introduces a third pass. Basically, for systems with lower GPU memory such as old-gen console hardware, ‘deferred lighting’ is preferable since it allows the size of the ‘G-buffer’ to be smaller because of the extra pass. Deferred shading is a simpler and more elegant solution but does require a larger ‘G-buffer’ and hence is better suited for ‘beefier’ GPU hardware.

DesertGlobe2

How it Works?

Deferred shading works as described using two separate rendering passes. The first pass is called the ‘geometry pass’ and works similar to a normal pixel shader carried out in forward rendering, except instead of outputting to the back buffer, we output to a selection of render targets, collectively referred to as the ‘G-buffer’. Each render target stores specific scene information so that once fed into the second ‘lighting pass’ the correct lighting calculations can be performed. Exactly what information you store in the ‘G-Buffer’ is fairly flexible although at a minimum you will require 3 buffers for colour data, normal data and preferably depth information. I say preferably because you could instead choose to store the 3D world position but this results in storing superfluous information since by using just the depth information we can reconstruct the 3D world position for each screen pixel later at a much cheaper memory cost (1 vs 3 floats per pixel).

As a bonus, when it comes to the ‘lighting pass’, you can further enhance performance by computing lighting on only the pixels that are effected by a particular light, by representing the light as a basic primitive based on its type. A full-screen quad for a directional light, a sphere for a point light and a cone for a spotlight.

DesertGlobe3

What’s the Catch?

Blending:

This brings us to the added complexity of deferred rendering. Because we effectively flatten the scene into 2D inside our buffers, we lose the depth information from the scene, meaning when it comes to blending operations such as those used in transparency, it’s hard to know in which order the scene should be arranged. There are however a few solutions to this including manually depth sorting your geometry and rendering in a ‘painters algorithm’ fashion, or even simpler, rendering your transparent objects in a separate forward rendering pass and blending, which is how I achieved the transparent snow globe.

Materials:

Because every object is encoded inside our ‘G-buffers’, any info about the scene that isn’t in there, the lighting pass will simply not know about. This presents a problem for geometric material properties because normally these would be passed into the shaders on a ‘per object’ basis via constant-buffers (DirectX), but because our ‘lighting-pass’ will only run ‘per light’ and not ‘per object’ we have no way of assigning the required material to the objects. One simple solution to this is to use a material ID value and throw this into one of the existing buffers like the colour buffer and then define a material array inside the lighting shader utilising the ID as an index.

Overall I’d implement deferred shading for any project in the future where time is not a concern as it does slightly complicate things but the benefits more than make up for this. If your game or 3D program doesn’t need more than a few lights then its not something that is strictly necessary however many modern games are already using deferred rendering techniques to enhance scene lighting. I’d also say if you can successfully implement deferred shading and understand the technique then you have gotten to grips with one of the more advanced multi-pass rendering techniques and this brings with it an enhanced understanding of the graphics pipeline.

 

Cross-Platform Game Engine

Featured

In the first semester of my MSc Computer Science degree as part of the Games Development Architectures module we were tasked to design and implement a cross-platform game engine. A game would also be made using the engine.

The chosen platforms were a Windows PC and Windows Phone 8 device. I decided that considering Microsoft had developed a Universal Application framework for targeting both of these, I would utilise it. This was good from the point of view that it simplified the cross-platform compatibility, but introduced a few limitations (namely having to work with the Windows RT platform and resultant consequences for dealing with inputs via ‘ref classes’ etc.. Coming from experience with Win32 desktop programs, Windows RT feels very different to program for and much less flexible, but then again Win32 really does need some modernisation.

4

Project Details:

  • Engine coded in C++ (Visual Studio).
  • DirectX11 rendering engine component coded from scratch.
  • HLSL shaders.
  • The Universal App framework used to contain the code solution and deploy to both platforms.

We were given a design specification for a simple game called ‘Tunnel Terror’. It involved the player having to control a vehicle/object through a tunnel, avoiding various obstacles. The speed would gradually increase the longer the player survived and any collisions with obstacles would result in death. Score was determined by length of survival. I decided to add various extras including power ups such as coins and a randomised speed-up/slow-down. The game would need to play on both a PC and Windows Phone 8 device, allowing for the differing input controls to play. I decided the PC would utilise keyboard whereas the phone would rely on the accelerometer (tilt) sensor to manoeuvre the player through the tunnel. The PC also required a 2 player mode. Main menu, high score table and game over screens would be needed as well as Multiple camera modes such as first-person, third-person and death fly-by cameras.

3

Although marks were given for the game implementation and extra features, much of the module was graded based on the engine design, implementation and accompanying report. My report justified the design based on four principles of games architecture, namely ‘Simplicity’, ‘Reusability’, ‘Abstractness’ and ‘Modularity’. Below is an example of the UML design used for my engines platform independent rendering component, with examples given to how behaviour could be derived for both DirectX and OpenGL.

Renderer

In the report we also had to research how we would have implemented the game on next-generation architecture such as the PlayStation 4 and how the engine would deal with the addition of different kinds of input devices.

There were some marks awarded for graphics quality and since the target platforms were both Microsoft, DirectX11 was used for the graphics. I implemented normal bump mapping to give it a nice look when flying down the tunnel. I also randomly changed the textures of each tunnel section and reset them to the end of the sequence once passing behind the frustum to give the impression of an endless tunnel with non-repeating sections.2

Annoyingly because the game is a Windows Store application there is no runnable executable so without actually publishing it to the Store and getting past all the certification requirements I cannot put it up anywhere to play! What is worse though is that currently I know of no screen capture software that can even record footage of the game running (at a decent FPS), both Fraps and Bandicam do not capture it since it’s not a desktop application. Bandicam does have desktop capture support but this also didn’t seem able to see the game and is not suitable for high frame-rate applications. So, as it stands I can’t make a video of the game running without hardware recording. Hopefully, this is something that won’t always be the case.

I was very pleased with the final engine and received a 92% grade for the module. I have since improved upon it and reused design elements for subsequent modules such as Real-time Graphics. I think a lot of what I coded for this project will be extremely useful going forward.

 

 

 

Bit’s Blitz – Puzzle Game

Bit's Blitz - Puzzle Game

Bit’s Blitz – Puzzle Game

In the third year of my Computer Science BSc (2013) as part of the Commercial Games Development module, we were placed into groups and tasked to produce a computer themed game designed for children. Each of the group members had to produce a game design document, one of which would be chosen for the group to develop. My group consisted of me, Aaron Ridge, Michael Killingbeck, Andrew Woodrow, Joshua Twigg and Alex Lynch.

The group decided to go with my game design which was inspired by the classic puzzle game Chip’s Challenge, with the idea being to reimagine it and modernise the graphics.

Game synopsis:
 “‘Bit’s Blitz’ is a fun 2D puzzle game following the escapades of its protagonist ‘Bit’. The game takes place across a series of levels increasing gradually in difficulty, gradually introducing new game-play elements. The player controls ‘Bit’ around a grid, constrained by a series of maze-like blocks and hazards. ‘Bit’ must successfully collect all the computer components that are scattered around the level and then repair his computer to proceed to the next level.”

Details:
Developed using C# and the XNA framework for the PC platform (Windows XP+).

 

The nice thing about this game design was that we could focus on the puzzle aspect of the game, time and imagination permitting, due to the simple overhead on technical implementation. The tile-based game engine was written from scratch using XNA, utilising XML data structures to store level data and a custom made loader. A cool and free little program called Tiled was used to ‘paint’ the level layout and export it into our XML format. I’d strongly recommend this to any considering 2D tile-based games for constructing levels, having said that, it’s a nice programming exercise to develop your own editor if you get the chance.

All gameplay aspects including animations and particle systems were programmed for the game, using no other libraries except XNA. I designed the game framework based on the State Design Pattern which worked out really well and continue to use it for game development.

With the use of XML and Tiled it allowed us to churn out level designs at an alarming rate and the final product has over 20 levels! Not bad considering the 2 week development time. When giving the presentation of the game, we literally only had time to demonstrate about 5 of the best levels, odd considering level variety tends to be in short supply for prototypes.

Sound effects were added (free assets) however I’ve removed these from the video and added music since honestly, they weren’t brilliant! The above gameplay video demonstrates various levels (played by me). I could barely remember most of the levels so it’s pretty much a blind play-through with some genuine mistakes.

For the project we all chipped in and the group worked well together. The game was never released or published anywhere, though if anyone is interested I could stick the executable on here for download.

Meshless Real-time Ray Tracing Demo Video

Featured

alt test

Meshless Real-time Ray Tracer

I was recently asked to put together a video showcasing my ray tracing project for the University of Hull to show some of the new Computer Science students starting this September. As detailed in my last post, ray tracing was the subject of my third year dissertation project and I have since been extending the project into real-time using DirectX 11, endeavouring hopefully to continue it as part of my MSc by creating a rendering program that can be used to design and produce complex implicit ray marched geometry through a simple UI interface.

The video unfortunately had to be recorded at 640×480 resolution to maintain good FPS due to my aging laptop GPU (around 4 years old now!). As a result, I recommend not viewing it in full-screen to avoid scaling ‘fuzziness’.

 

 

Scene Loading:

Recently I have been working on a scene loading system for it in preparation for implementing a UI with the ability to save and load created scenes. I developed a scene scripting format that allows simple definition of the various distance functions that make up a scene, along with material types and lighting properties. The scene loader parses a scene file and then procedurally generates the HLSL distance field code that will be executed in the pixel shader to render the scene. I’ve used a similar looking format to POVRay’s scene files.

Below is an example of one of my scene files showing a simple scene with a single sphere and plane with a single light :

#Scene Test
 
light
{
     position <-1.5, 3, -4.5>
}
 
sphere
{
     radius 1
     position <-2,1,0>
}
material
{
     diffuse <1,0,0,0.25>
     specular <1,1,1,25> 
}
 
plane
{
     normal <0,1,0>
}
material
{
     diffuse <0.5,1,0.5,0.5>
     specular <1,1,1,99> 
}

More complex operations such as blending can be represented in the scene file as follows:

blend
{
    threshold 1
    sphere
    {
        radius 1
        position <-2,1,0> 
    }    
    torus
    {
        radius <1, 0.44>
        position <2,1,0> 
    }
}
 

Due to the recursive nature in which I have implemented the parsing, it also allows me to nest blending operations like the following series of blended spheres, resulting in a single complex surface:
 

blend
{
     threshold 1
     blend
     {
          threshold 1
          blend
          {
               threshold 1
               sphere
               {
                    radius 1
                    position <-2,1,0>
               }
               sphere
               {
                    radius 1
                    position <2,1,0>
               }
          }
          sphere
          {
               radius 1
               position <0,2,0>
          }
     }
     sphere
     {
          radius 1
          position <0,1,-2>
     }
}
material
{
     diffuse <1,0,1,0.25>
     specular <1,1,1,25> 
}

For more complex scene featuring blending, twisting and domain repetition, an example scene file looks like this:

#Scene Test
 
light
{
     position <-1.5, 3, -4.5>
}
 
repeatBegin
{
     frequency <8.1,0,8.1>
}
 
twistY
{
     magnitude 0.04
     box
     {
          dimensions <1,4,1>
          position <0,3,0>
     }
}
material
{
     diffuse <1,0.5,0,0.1>
     specular <1,1,1,5> 
}
 
sphere
{
     radius 2
     position <0,9,0>
}
material
{
     diffuse <0,0.5,1,0.5>
     specular <1,1,1,30> 
}
 
repeatEnd
 
plane
{
     normal <0,1,0>
}
material
{
     diffuse <0.2,0.2,0.2,0.5>
     specular <1,1,1,99> 
}

Currently my scene files support spheres, cubes, tori and also a ‘Blob’ shape which takes any number of component spheres as parameters and blends them together. It also supports custom blending of the above shapes, domain twisting and repetition operations. Materials can be specified with both diffuse and specular components, with the 4th diffuse tuple representing reflectivity, and the 4th specular tuple representing shininess.

 

As the project develops, I’ll need to implement a way of creating custom distance functions that aren’t just template primitive shapes, but defined more generally to allow users to create surfaces using anchor points This will likely be a main focus for my masters dissertation if I take this topic.

 

CUDA Ray Tracer – Dissertation Project

Featured

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’? This post a brief description and summary of my project.

A download to my full dissertation report can be found below and as well as a few renderings from my prototypes:

Report:

540 Downloads

Prototype Renderings:

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.

 

CUDA Ray Tracer - Dissertation Project

CUDA Ray Tracer – Dissertation Project

 

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.