Nick Bray - Blog

Deferred Rendering

2010-04-19T13:22:00.000-07:00

Since my last update, I've done quite a bit of work on PyStream to finish off my dissertation.

The example rendering system is now a deferred rendering system, and includes a pass for screen-space ambient occlusion (SSAO). This is type of rendering system that is the "hot" thing for games right now; this technique is being used in Crysis 2 and Starcraft 2, among others. The statue of Beethoven that is nearest to the camera is entirely unlit, except for ambient lighting. Despite this, the shape of the statue is still apparent, due both to SSAO and to the use of HDR cube map ambient lighting.

The shaders being generated by the compiler are pretty much what I'd write by hand. The overall rendering system easily achieves 60 fps on a mid-range video card despite the fact that it is written entirely in Python.

Highly Dynamic Cows

2010-02-23T11:27:00.000-08:00

High-dynamic range rendering support has been added to the example renderer I am building using PyStream.

This means that cube maps are now supported, as is off-screen rendering. Ambient lighting is now done with low-resolution cube maps. Loops are now supported. The dips in the ground are a result of using parallax occlusion mapping.

A Data-driven Discourse

2010-02-03T19:11:00.000-08:00

I am currently TAing CS428 at UIUC. This class is the second in a sequence of software engineering classes. In this class, students form groups of 6-8 and work on projects for an entire semester. Many students choose to work on games, which is serendipitous, as I am interested in game architecture.

In an email I sent out to some of the students, I suggested they look into data-driven design. Unfortunately, there isn't a lot of concrete information on data-driven design. Most of the documentation is along the lines of “put as much of the game in data as you can, it's a good idea” and not a lot of specifics. There was much confusion. The truth of the matter is, I did not fully understand data-driven design until I used it in a real game. I think, in general, data-driven design is one of those topics that people do not fully understand until they've done it. There are lots of experienced people evangelizing a data-driven approach, and a lot of inexperienced people simply not understanding why the evangelists are so fervent. This is my attempt to bridge that gap.

What Does it Look Like?

Data-driven systems can look like pretty much anything. Data can be sucked from virtually any source, .ini files, .xml files, or a custom configuration format. This is part of the reason everyone waves hands when the talk about data-driven systems, they share little in common other than a high-level focus on data. Certain types of data may have their own formats, such maps or images. Yes, images. I see you raising your hand in the back of the room. Let me guess, your game was already loading images? The truth of the matter is that most games are partially data-driven, as they usually load images and sounds. The fundamental idea of being data-centric is extremely simple, but unanticipated benefits emerge when the scale is increased. Images and sounds are just the tip of the iceberg.

Isolating Change

One of the reasons data-driven design works is because it helps isolate changes. For example, when tuning a game, you will fiddle with a lot of parameters, and keep testing until the gameplay feels right. With data-driven design, you can centralize these parameters in a single configuration file. Tuning becomes much easier if you are not forced to comb through your entire codebase to make changes. As a related issue, data-driven systems do not need to be recompiled when the data changes. (Well... if you did everything right.) This is a huge advantage for large C programs, where linking can take five minutes or longer. In data driven systems, you can see the changes as fast as you can load the data.

Isolating change is also handy if you're working with dedicated artists or designers. If everything they edit is data, there is no need for them to recompile the game. The artist I worked on Scamper Ghost loved this freedom. Not only is this faster and simpler for them, but there is no need to keep them synced up with the current version of the source, or for them to install a compiler or IDE.

From a software engineering perspective, data-driven design cleanly orthogonalizes the system: the game definition gets separated from the implementation issues.

Online Reloading

One of the holy grails of data-driven systems is online loading of data. The idea being that as soon as data changes on disk, it should be possible to load it into the game, even while the game is running. A image doesn't look right? Edit it, hit a button, and it changes in-game. Or, if you're particularly good with OS API Kung Fu, monitor the data directory for changes, and automatically reload it.

Personally, I have never reached this data-driven nirvana. There are too many sticky issues about reloading arbitrary data. What kind of data can be reloaded, and what kind of data cannot? For example, reloading a level that is currently being played could cause problems, as the player may find themselves suck inside a solid object, or similar. If you change the number of hitpoints for a certain kind of monster, do you attempt to adjust the hitpoints of already instantiated monsters, or just the ones instantiated in the future? There are likely many heuristics to address these issues, but I have not had a chance to explore them.

I Declare!

My personal favorite reason to go data-driven is that configuration files are declarative, not imperative. The data is not coupled with how it is used. This means the same data can be used in multiple ways. For example, in Flash data can either be loaded from external sources, or embedded in the binary. Embedding data makes it much faster to load (the fixed overhead of transferring a file across the network is comparatively huge if there is only a small amount of data), and simplifies distribution, as it reduces the number of files that need to be distributed. Unfortunately, embedded data cannot be changed without recompiling the binary. Ideally a game would not embed data during development, but embed it for release. Sadly, Flash does not provide an easy way to switch between these two configurations. File embedding is specified by an explicit directive in the source code for each embedded file, and loading an embedded file requires slightly different code than loading an external file.

In Scamper Ghost, the game loaded data off the disk by default. When creating a release build, a Python script is used to parse the config file and finds all of the images and sounds the game uses. The script then generates an additional source file that embeds all of the resources, and provides hooks for loading them. In general, the declarative nature of data allows tools to analyze and manipulate the game data in arbitrary ways.

So What About Game Logic?

Most evangelists insist that a game should contain no game-specific code, rather everything should be defined in data. At first glance this is a little scary and quite impossible, but it is mitigated by three unspoken assumptions.

First, quite a bit of “game specific” code can be generalized into a parametrization of generic code. For example, if a game has particle effects, there will likely be some code, somewhere that implements particle effects. It is patently absurd to imagine that particle effects could or should be defined from first principles using data. At that point, the configuration language would have become a programming language. It should be possible to share the same particle effect code between games, but each game may have different looking particle effects due to how they're parametrized. In addition, a game may require a novel parameter, such as controlling how much the particle effect is affected by wind, and adding support for that parameter is not considered game-specific code (by the evangelists), even though that parameter may only be used in one game.

Second, the evangelists assume there is a scripting language, and that the scripting language does not count as code. The amount of scripts needed by a game should be minimized, however, by clever and liberal parametrization. If you are not using a scripting language, your goal should be to keep the “code” decoupled from the game logic. (The reverse will likely be untrue, the game logic will likely need to understand the code unless it is isolated with an interface.) In any case, best practice that game logic be attached to the game using data. For example, a configuration file could indicate that a certain type of monster will call a given script when hit.

Third, the evangelists assume that you're using some kind of component system to define game object structure. Component systems allow you to define game object structure via the composition of know substructures. Without a component system, you would need to hardcode the structures for various game objects. Of course, best practice would dictate that these structures should be part of the “game logic” and not the main code.

Bigger Than You'd Think

Another aspect of data-driven systems that is easy to underestimate is the magnitude of data most games contain. Scamper Ghost, a small but polished game, contained over 500 images. Modern commercial games contain megabytes to gigabytes of data. Techniques that work at smaller scales, such as embedding image names in code, simply do not scale. With smaller amounts of data, many of the benefits of data-driven design can still be realized, but for “normal” amounts of data, being data-centric is a virtual necessity.

Permission to Sin

Data-driven systems are hard to bootstrap. It is often tempting to hardcode something, just to get the game up and running. My advice is this: do it. The true value of data driven systems is only realized when almost everything is data, however. You will likely come to regret hardcoding whatever it was, and go back to generalize it later. Hardcoding is simply part of how data-driven systems are bootstrapped, attempting to be strictly orthodox from the beginning will simply slow down the boostrapping process. Just be sure that you don't paint yourself into a corner.

Polymorphic Cows

2010-02-03T18:38:00.000-08:00

The PyStream compiler is getting more robust, and the cases that break it are getting hammered out.

A big milestone is that polymorphic types now work. In the screenshot, there are three different “material” types that control how light interacts with a given surface. There's a chalky DiffuseMaterial that wraps implements wrap lighting. There's a shiny PhongMaterial which implements straight-up Blinn-Phong lighting. There's also a non-photorealistic ToonMaterial that emulates the banded lighting commonly found in cartoons. The code for these materials is at the end of this post.

The screenshot isn't knock-your-socks-off amazing, the real magic is going on in the compiler. There are two significantly cools things going on:

First, Python code is being translated into GLSL. Python loves and abuses indirection. GLSL has no pointers, which makes indirection very difficult to implement. The PyStream compiler is capable of eliminating a vast majority of this indirection, and emulating the rest. In effect, it is now possible to run a significant subset of Python on the GPU. There are a number of existing approaches to metaprogram shaders in non-shader languages, but these approaches uniformly adopt the semantics of the shader language. To my knowledge, this is the first instance where non-shader code has actually been translated into shader code while preserving semantics.

Second, binding code is generated in such a way that executing shaders is entirely Pythonic. The user first composes the shader out of objects. For example, a ToonMaterial object could be stored into a shader's “material” field, colors can be stored into other fields, and so on. The user then calls a method on the shader object to execute the shader. Serialization between the CPU and the GPU is automatic, and the result is drawn into the frame buffer. Currently, shader programmers write a lot of boilerplate to transfer data, and this approach eliminates it entirely.

Code

class DiffuseMaterial(Material):
    __slots__ = 'wrap',

    def __init__(self, wrap):
        Material.__init__(self)
        self.wrap = wrap

    def diffuseTransfer(self, n, l, e):
        # Wrap lighting - approximates
        # sub-surface scattering
        ndl = n.dot(l)
        wrapped = (ndl+self.wrap)/(1.0+self.wrap)
        return max(wrapped, 0.0)

    def specularTransfer(self, n, l, e):
        return 0.0


class PhongMaterial(Material):
    __slots__ = 'shiny',

    def __init__(self, shiny):
        Material.__init__(self)
        self.shiny = shiny

    def specularTransfer(self, n, l, e):
        # Blinn-Phong transfer
        h = (l+e).normalize()
        ndh = nldot(n, h)
        # Scale by (shiny+8)/8 to approximate
        # energy conservation
        scale = (self.shiny+8.0)*0.125
        return (ndh**self.shiny)*scale

class ToonMaterial(Material):
    __slots__ = 'toonMap',

    def __init__(self, toonMap):
        Material.__init__(self)
        self.toonMap = toonMap

    def diffuseTransfer(self, n, l, e):
        amt = n.dot(l)*0.5+0.5
        uv = vec2(0.25, amt)
        return self.toonMap.texture(uv).x

    def specularTransfer(self, n, l, e):
        h = (l+e).normalize()
        amt = nldot(n, h)*0.5+0.5
        uv = vec2(0.75, amt)
        return self.toonMap.texture(uv).x

Scamper Ghost Released

2009-11-27T09:45:00.000-08:00

A friend and I have finally released our game

As they say, it's "a fast-paced avoidance retro pixel art game with ghosts, coin collecting, power-ups, and slow motion."

Unified Codebases Rock

2009-11-22T15:30:00.000-08:00

In a previous post, I eluded to the advantages of being able to run the same code on the CPU and the GPU. One obvious example is the interaction between color processing and frame buffer clearing. Shaders may process the color of a fragment before it is written to the frame buffer for a multitude of reasons, including color correction, exposure control, tone mapping, and gamma correction. This causes problems when the CPU needs to predict the final value for a color that will be output by a shader. For example, when fog is used to attenuate the colors of objects as they fade into the distance, it is necessary to match the clear color with the fog color. If the same color processing is not applied to both, the result is the following:

On the other hand, if the correct color processing is applied to the clear color, the result is much more satisfying:

The problem with the current shader paradigm is that shader code has entirely different semantics than CPU code and is kept in a separate code base. Executing shader functions on the CPU side is at best difficult, and is typically entirely unsupported. The traditional workaround to this issue is to rewrite the necessary functions in the language being used on the CPU. This results in code duplication, however, and complicates maintaining and evolving the rendering system.

PyStream avoids this problem by using the same language on the CPU and the GPU, and unifying the codebases. With a few reasonable restrictions, most functions can be executed on either the CPU or the GPU.

The fragment shader is that generated the images in this post was as follows:

def shadeFragment(self, context, pos, normal, texCoord):
    surface = self.material.surface(pos, normal.normalize())

    # Texture
    surface.diffuseColor *= self.sampler.texture(texCoord).xyz
    
    # Accumulate lighting
    self.ambient.accumulate(surface, self.worldToCamera)
    self.light.accumulate(surface, self.worldToCamera)
                
    mainColor = surface.litColor()
    mainColor = self.fog.apply(mainColor, surface.p)
    mainColor = self.processOutputColor(mainColor)
    
    mainColor = vec4(mainColor, 1.0)
    context.colors = (mainColor,)

def processOutputColor(self, color):
    return rgb2srgb(tonemap(color))

The clear color is generated by calling the shader's processOutputColor method:

clearColor = shader.processOutputColor(shader.fog.color)

PyStream Texture Support

2009-11-22T15:27:00.000-08:00

PyStream now supports textures. There are a lot of simple issues like texture mapping that have been lost in the shuffle until now, and I am going back to fix.

def shadeVertex(self, context, pos, normal, texCoord):
    trans     = self.worldToCamera*self.objectToWorld
    newpos    = trans*pos
    newnormal = trans*vec4(normal, 0.0)

    context.position = self.projection*newpos

    return newpos.xyz, newnormal.xyz, texCoord

def shadeFragment(self, context, pos, normal, texCoord):
    surface = self.material.surface(pos, normal.normalize())

    # Texture
    surface.diffuseColor *= self.sampler.texture(texCoord).xyz
    
    # Accumulate lighting
    self.ambient.accumulate(surface, self.worldToCamera)
    self.light.accumulate(surface, self.worldToCamera)
                
    mainColor = surface.litColor()

    mainColor = rgb2srgb(tonemap(mainColor))
    
    mainColor = vec4(mainColor, 1.0)
    context.colors = (mainColor,)

Dissertation Status

2009-11-16T19:39:00.001-08:00

Here's a simple example showing the current capabilities of the PyStream compiler. These shinny cows were drawn using a shader that was written in Python and then compiled into GLSL. The actual shading algorithm is pretty simple: phong shading, a point light, and gamma correction. The kicker is that Python's semantics are wildly different from GLSL's. Compiling Python code into GLSL is therefore a pretty neat trick.

An advantage of writing shaders in Python is that the same functions can be called on both the CPU and the GPU. For example, in the following code the function rgb2srgb is used to gamma correct colors on the GPU. The same function is also used to gamma correct the clear color on the CPU, so it matches the colors output by the shader. In general, arbitrary color processing could be applied in the shader: tone mapping, etc. Unless the same processing is applied to the clear color (which is not processed by the shader), the rendered objects may "pop out" from the background. For example, if fog is used and the clear color is not processed the same way as pixels, distant objects will fade to a color that does not match the background.

This is the original Python code:

def shadeVertex(self, context, pos, normal):
  trans     = self.worldToCamera*self.objectToWorld
  newpos    = trans*pos
  newnormal = trans*vec4(normal, 0.0)

  context.position = self.projection*newpos

  return newpos.xyz, newnormal.xyz

def shadeFragment(self, context, pos, normal):
  n = normal.normalize()
  e = -pos.normalize()

  # Light into camera space
  trans = self.worldToCamera
  lightPos = trans*self.lightPos

  lightDir   = lightPos.xyz-pos
  lightDist2 = lightDir.dot(lightDir)
  lightDist  = lightDist2**0.5
  l = lightDir/lightDist

  lightAtten = 1.0/(0.01+lightDist2*(1.0/(100.0**2)))
  transfer = self.material.transfer(n, l, e)
  modulated = transfer*lightAtten

  mainColor = self.material.color*(self.ambient+modulated)

  mainColor = rgb2srgb(mainColor)
  mainColor = vec4(mainColor, 1.0)
  context.colors = (mainColor,)

Loopy Dependancy Issues

2009-06-19T19:39:00.000-07:00

The Bug

Working on redundant load elimination for my dissertation, I wrote a loop:

for statement in statements:
        if someCond:
                ...
                lcl = value1
        else:
                ...
                lcl = value2
        process(lcl)

That is, that is the code I thought I wrote. As it turns out, I actually forgot the final assignment and in fact wrote the following:

for statement in statements:
        if someCond:
                ...
                lcl = value1
        else:
                ...
                # lcl not assigned to
        process(lcl)

Now this is a fairly straight forward bug to find and fix, right? As it turns out, this simple typo created a fairly subtle and hard-to-trace bug.

In the best case, someCond would evaluate to false on the first iteration of the loop, and process(lcl) would throw an exception because lcl was undefined. In practice, however, someCond almost always evaluated to true. As such, no exception was noted when the code was run. Instead, when someCond would evaluate to false, lcl was pulled from the previous iteration of the loop. This resulted in a subtle corruption of the output. Worst of all, the nature of the corruption would depend on the order that the statements were processed. All in all, the result was a subtle, non-deterministic bug. The root of this bug was that lcl was not supposed to be a loop-carried dependency, but a single typo silently turned it into one.

The Introspection

On one hand, if Python supported variable scoping, this bug would have been easier to identify. On the other hand, forcing explicit declaration of variables would degrade the “rapid development” nature of Python. In any case, scoped variables are only treating the symptoms of a bigger problem. The big picture problem is that loop-carried dependencies are really, really ugly. Figuring out what variables are loop-carried dependencies, and figuring out how they behave always requires significantly more thought than straight-line code. It is easy to forget this because it is a familiar ugliness.

There might be some virtue in trying to mainstream the stream programming model of “stateless” loops. Python has taken a step in the right direction with list/dictionary/set comprehensions, although they are somewhat limited. An interesting compromise might make loops naturally stateless, but allow loop-carried dependencies can be explicitly declared.

Without explicit language support, two workarounds suggest themselves. First, document all loop carried dependencies. Understanding them out requires more effort than straight-line code, which indicates they would benefit from comments, even if they seem simple at first glance. Second, any given function should only have a small number of local variables (7? 10?). This is a variation of the rule of thumb that functions should never have more than X lines, where X varies with the zealotry of the speaker and the language that they use. Lines of code is a language-dependent metric, whereas number of local variables seems to be a fairly general measure of “namespace clutter.” The more names in a local namespace, the greater chance that a programmer will forget something and make a mistake.

The Solution

Defensive programming can help reduce the peril of loop-carried dependencies. After I found the bug, I refactored the code that generated lcl into its own function.

def getValue(...):
        if someCond:
                ...
                lcl = value1
        else:
                ...
                lcl = value2
        return lcl

for statement in statements:
        lcl = getValue(...)
        process(lcl)

Not only does this make each function smaller and easier to understand, but it limits the scope of lcl. In light of this experience, I would propose that variable assignments inside loops should either be painfully clear, or refactored until they are.

Loving your self.

2009-06-19T19:24:00.000-07:00

A while ago I was giving a presentation that included a quick introduction to Python. An audience member asked a question that caught me off guard: isn't explicitly prefixing “self.” to each member access annoying? Looking back, when I started programing Python, yes it was annoying. Nowadays, however, I don't mind it at all, and in fact prefer it compared to languages with implicit member accesses. At the time I couldn't rationalize why that was, however, which indicated that I needed to give the issue further consideration. In a language designed for rapid development, why should anyone put up with typing five extra characters over and over? This question lingered in my mind for a while, but things finally clicked in place when I ran into a bug while programming Actionscript.

The Bug

public function resize(widt:Number, height:Number):void
{
     this.width  = width;
     this.height = height;
}

In this case, I misspelled the name of a function parameter. The parameter should have masked the instance variable, but due to the typo in the declaration, it did not. This resulted in a silent bug, as references to the parameter instead resolved to the instance variable. In effect, the first assignment became a null operation. It's obvious that masking instance variables is a dangerous thing to do in language with implicit references to members.

A reasonable rule of thumb might be to never mask instance variables, but this results in some strange names for locals: _width, w, width2, etc. Creating strange names, particularly if they're similar to existing names, creates a typo hazard like in the previous example. Did you mean to refer to width or _width? Can you notice the difference at a glance?

The Introspection

In this case, it seems that explicit is better than implicit. Prefixing each member access with “self.” helps separate members from other types of references. Every root identifier in a Python function is either a local, or failing that, a global. There's minimal magic behind the scenes in how names are resolved, making the code easier to understand. Easier to understand means less bugs.

The problem with the C++/Java/Actionscript/etc. Way of doing things is that too many things are crammed into the same namespace. A given identifier could reference a local, global, instance variable, or method. Programmers have struggled with this problem for a long time, and have come up with solutions such as prefixing names with characters indicating where they come from (m_, g_, etc.) These types of solutions tend to make code real ugly, real fast. The solutions are addressing a real problem – but they create a new problem while they are at it.

Python simply moves members out of the locals/globals namespace. Bugs arising from masking globals with locals, or masking one member with another are bad enough, let alone the dimensions of pain opened up by merging the namespaces. It is ironic that a dynamically typed language, in some ways, is more explicit than a statically typed language.