Depth of Field

So, I've now got depth of field working!

It was pretty straightforward. I just used a list comprehension to generate a list of points to jitter the rays with, and then it took a lot of fiddling to get the focusing working correctly.

I've also done various refactorings to my code.

All in all, it added roughly an extra 15-20 lines of code to the tracer. And that's without writing Perl-style gibberish.

Predictably enough, though, the tracer is now running much slower - about a minute for this image on my 2008 MBP. So, the next job will be learning how to optimise code in Haskell, and throwing some threading (back) in there.

Pet Project Resurrected

So, about 14 months or so ago, I spent a few weeks learning Haskell over Christmas. Then, I had to start work in earnest on my MSc final-year project, so the Haskell hacking went on the back burner.

Now that I'm in my last few weeks of the MSc, I've picked up Haskell again. Last time around I'd knocked myself up a basic little raytracer. I'm now starting up that project again. I want to work on some off-line rendering techniques for a change of pace from the day job.

So far, I've got the basics: reflection, refraction, shadows, materials and shaders (100% Haskell including shaders):

So what's next? I reckon:

* Distributed ray tracing
* Anti-aliasing
* More light types and lighting model types

That should be a good set of features to work on whilst I get my Haskell back up to speed. Once I'm back up to speed, I can start to look at meatier tasks like an asset pipeline or spatial partitioning.

I did have it running in parallel last time round, but that's all changed in Haskell in the last year or so, so I'll have to revisit that.

Sparse Voxel Octrees meet Marching Cubes

Some speculation here. I've not tried this idea out yet.

I've been doing a little reading up on Sparse Voxel Octrees lately, and an idea in Samuli Laine's papers particularly interested me. In these papers, "contours" are used to add shape to the basic octree voxels to enhance detail without extra subdivision.

I quite like this idea. I've been thinking of ways to try to extend the contour idea.

How about using a marching-cubes type algorithm to provide some more detailed geometry at the node or leaf level, based on the existence of non-existence of neighbouring octree cells?

You could quickly construct a bit mask based on the existence of neighbouring cells, use that to look up in a table providing several specific pieces of geometry for each case. This could add some extra detail and shape to each octree voxel.

Polymorphism

Polymorphism is one of the object oriented paradigms that leads to pain when optimising.

Why?

Virtual.

Polymorphism in itself isn't a bad thing. It's a useful design mechanism and has its place. The virtual function call adds a level of abstraction that makes it difficult to port to SPU or GPU architectures and adds a barrier to many optimisation techniques.

A common example is using polymorphism and virtual functions to process a list of heterogenous types with a common base class.

This is bad because:
(a) You're adding the cost of virtual function calls to every object
(b) You're dispatching to different pieces of code, in a potentially incoherent order, causing I$ thrash.
(c) You often end up with oversized objects that carry dead code and data around, again hurting cache efficiency
(d) It's harder to port the code to the SPU (or GPU)

I've been exploring an alternative way of structuring this approach. I've retained a polymorphic external interface for registering objects of different types in a list. However, rather than have a single add() function that takes the base type, I've explicitly made several overloaded functions that take the derived types. Each of these functions adds that object to a list of objects of the same specific derived type. So, instead of having one big heterogenous list, internally I have several type-specific homogenous lists.

This way, I eliminate all virtual calls in my processing-side code. I can now process all of the objects of type X, Y and Z. I can explicitly call X::process() in a list, Y::process(), Z::process() and so on. This makes the code much easier to optimise and much easier to port to the SPU because you no longer need to know about the vtable. I now have much better I$ coherency.

Who said we must have one list, after all? Why does the contained object have to pay the cost of the abstraction mechanism? Doesn't it make more sense for the containing object to pay the cost? And a cheaper cost at that! Provided the set of types you are dealing with remains reasonable, maintaining multiple separate lists can be an easy way to enhance efficiency and make your code easier to port to SPU.

My MSc Research Project

The games industry has had a long-standing difficulty in successfully delivering projects to market on-time and on-cost.

The industry has tried many different methods to improve this problem; yet still projects slip, are cancelled, or require significant amounts of crunch to complete them. We have tried, with varying success, to import methodologies from other industries. Yet when placed in the context of the games industry, something is still somehow lacking.

My hypothesis is that the industry does not have a project management methodology suited to its nature. This industry is a creative entertainment industry and has different needs to other sectors of the software industry. I believe that creativity is a significant factor in the development of videogames, and that it is a factor that to-date has not been explicitly treated by any project management methodology. This is a significant shortcoming for an industry that is built on creativity. I believe that much of the reason for many development problems is that we are trying to manage a creative process with tools inappropriate to that task. Creative processes are different, and need to be managed differently.

My research project will investigate the effect of creativity on various development tasks, both routine and highly creative, in a real world project. This will be the first study that provides an investigation and understanding of what role creativity plays in videogames programming. These results will be critically analysed to consider the question of how best can we manage creativity in videogames programming?

If all goes well, this should be the first step in establishing a new direction of research and practice in the management of videogames projects.

Reuse

Re-use is now an established trend. And that's a good thing.

But we go about it in a very back-to-front way.

Primarily, code re-use tends to be a very code-oriented practice. We look at a piece of code, its functionality, performance and other characteristics and decide it makes a good candidate for re-use. And so, it gets re-used. And we find that in the re-use, it didn't quite do what we wanted. We then have to spend a lot of effort re-engineering it towards our needs. We bang a lot of square pegs into round holes.

What went wrong? We put the cart before the horse. We attempted to re-use code, a derived artefact of the software engineering process without considering the original, motivating cause of that engineering effort - the requirements.

Written, implemented code is a concrete solution to some specified problem. The requirements for the code are a pure expression of the problem we need to solve. In attempting to directly re-use code without comparison or consideration of the requirements that led to that code, we're hoping that one solution solves two problems. We're hoping that a given solution can solve problems that were not known, or at least addressed during implementation.

More explicit consideration of the requirements in the re-use process has potential benefits for all parties. For the client code, wishing to re-use some candidate piece of code, we can ensure that it is a good fit for our requirements. If there is a mismatch between requirements, this clearly identifies where work is needed. These conflicting requirements can now inform the design process, to ensure that the any modifications to the re-used code are implemented appropriately, and not simply bolted on, polluting the code. We can more accurately estimate the work required, rather than attempting to untangle the specifics of implementation, piece, by piece, by piece.

Critical Chain Project Management

The Critical Chain project management methodology has some interesting ideas that are very relevant to games projects.

1. Time is not used to figure out the critical chain of a project. Instead, dependencies are used.
2. Buffers and padding are not placed at the end of each activity. Instead, they are placed, in aggregate, at the end of the project.

(1) is particularly salient for two reasons. Firstly, as is well known, software remains resolutely incredibly difficult to estimate accurately; what is the point, therefore, in using inherently inaccurate estimates to attempt to calculate your critical chain? Dependencies are a critical factor your ability to deploy resources. You cannot add resources to expediate a particular activity if dependent work is held up. Conversely, identifying those points in a project that have the maximal tasks dependent upon them highlights them as points in the project that need maximal resources to ensure their successful completion and enable dependent tasks to begin.

(2) is simply Parkinson's law. Adding padding to each task makes its timely completion far less critical, and therefore things begin to slip. Critical Chain instead calls for all activities to be begun and completed as quickly as possible (as doing so eliminates them as a dependency allowing further work to begin) and the padding is instead added at the end of the project. This change therefore means that the scheduling of a particular task is purely dependent on its input dependencies, not a function of the dependencies and the padding.

And furthermore, what sense does it make to add 20%, say, to an inherently inaccurate estimate anyway? Why not 10%? Why not 50%? Such a practice is meaningless.

Critical Chain is not a massively revolutionary technique, but its different perspective on some fundamentals of project management is quite insightful.