Shawn Hargreaves Blog

Bloom on Windows Phone

2012-01-20T01:04:11Z

Ok, silliness aside, is it possible to implement an efficient bloom effect on Windows Phone without custom shaders?

Bloom consists of three operations:

Identify which parts of the image should be bloomed
Blur those parts
Combine blurred bloomy bits with the original image

There are many choices for how each operation should be implemented, the combination of which determines the visual result. In the XNA bloom sample:

Bright areas are identified by subtracting a threshold value, then scaling back up to preserve full color range: (value - threshold) / (1 - threshold)
Blur is applied using a two pass separable Gaussian filter
To avoid excessively bright areas, the final combine operation is: (base * (1 – bloom)) + bloom (done in a pixel shader that also provides brightness and saturation adjustment for both images)

There is no good way to adjust saturation without shaders, but everything else in this design can be done with simple alpha blending operations:

using System;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace BloomPostprocess
{
    public class BloomComponent : DrawableGameComponent
    {
        // Adjust these values to change visual appearance.
        const float BloomThreshold = 0.25f;
        const float BloomIntensity = 1.5f;
        const int BlurPasses = 4;


        // result = source - destination
        static BlendState extractBrightColors = new BlendState
        {
            ColorSourceBlend = Blend.One,
            AlphaSourceBlend = Blend.One,

            ColorDestinationBlend = Blend.One,
            AlphaDestinationBlend = Blend.One,

            ColorBlendFunction = BlendFunction.Subtract,
            AlphaBlendFunction = BlendFunction.Subtract,
        };


        // result = source + destination
        static BlendState additiveBlur = new BlendState
        {
            ColorSourceBlend = Blend.One,
            AlphaSourceBlend = Blend.One,

            ColorDestinationBlend = Blend.One,
            AlphaDestinationBlend = Blend.One,
        };


        // result = source + (destination * (1 - source))
        static BlendState combineFinalResult = new BlendState
        {
            ColorSourceBlend = Blend.One,
            AlphaSourceBlend = Blend.One,

            ColorDestinationBlend = Blend.InverseSourceColor,
            AlphaDestinationBlend = Blend.InverseSourceColor,
        };


        SpriteBatch spriteBatch;

        RenderTarget2D scene;
        RenderTarget2D halfSize;
        RenderTarget2D quarterSize;
        RenderTarget2D quarterSize2;


        public BloomComponent(Game game)
            : base(game)
        { }


        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);

            PresentationParameters pp = GraphicsDevice.PresentationParameters;

            int w = pp.BackBufferWidth;
            int h = pp.BackBufferHeight;

            scene = new RenderTarget2D(GraphicsDevice, w, h, false, pp.BackBufferFormat, pp.DepthStencilFormat, pp.MultiSampleCount, RenderTargetUsage.DiscardContents);
            halfSize = new RenderTarget2D(GraphicsDevice, w / 2, h / 2, false, pp.BackBufferFormat, DepthFormat.None);
            quarterSize = new RenderTarget2D(GraphicsDevice, w / 4, h / 4, false, pp.BackBufferFormat, DepthFormat.None);
            quarterSize2 = new RenderTarget2D(GraphicsDevice, w / 4, h / 4, false, pp.BackBufferFormat, DepthFormat.None);
        }


        public void BeginDraw()
        {
            if (Visible)
            {
                GraphicsDevice.SetRenderTarget(scene);
            }
        }


        public override void Draw(GameTime gameTime)
        {
            // Shrink to half size.
            GraphicsDevice.SetRenderTarget(halfSize);
            DrawSprite(scene, BlendState.Opaque);

            // Shrink again to quarter size, at the same time applying the threshold subtraction.
            GraphicsDevice.SetRenderTarget(quarterSize);
            GraphicsDevice.Clear(new Color(BloomThreshold, BloomThreshold, BloomThreshold));
            DrawSprite(halfSize, extractBrightColors);

            // Kawase blur filter (see http://developer.amd.com/media/gpu_assets/Oat-ScenePostprocessing.pdf)
            for (int i = 0; i < BlurPasses; i++)
            {
                GraphicsDevice.SetRenderTarget(quarterSize2);
                GraphicsDevice.Clear(Color.Black);

                int w = quarterSize.Width;
                int h = quarterSize.Height;

                float brightness = 0.25f;

                // On the first pass, scale brightness to restore full range after the threshold subtraction.
                if (i == 0)
                    brightness /= (1 - BloomThreshold);

                // On the final pass, apply tweakable intensity adjustment.
                if (i == BlurPasses - 1)
                    brightness *= BloomIntensity;

                Color tint = new Color(brightness, brightness, brightness);

                spriteBatch.Begin(0, additiveBlur);

                spriteBatch.Draw(quarterSize, new Vector2(0.5f, 0.5f), new Rectangle(i + 1, i + 1, w, h), tint);
                spriteBatch.Draw(quarterSize, new Vector2(0.5f, 0.5f), new Rectangle(-i, i + 1, w, h), tint);
                spriteBatch.Draw(quarterSize, new Vector2(0.5f, 0.5f), new Rectangle(i + 1, -i, w, h), tint);
                spriteBatch.Draw(quarterSize, new Vector2(0.5f, 0.5f), new Rectangle(-i, -i, w, h), tint);
                
                spriteBatch.End();

                Swap(ref quarterSize, ref quarterSize2);
            }

            // Combine the original scene and bloom images.
            GraphicsDevice.SetRenderTarget(null);
            DrawSprite(scene, BlendState.Opaque);
            DrawSprite(quarterSize, combineFinalResult);
        }


        void DrawSprite(Texture2D source, BlendState blendState)
        {
            spriteBatch.Begin(0, blendState);
            spriteBatch.Draw(source, GraphicsDevice.Viewport.Bounds, Color.White);
            spriteBatch.End();
        }


        static void Swap<T>(ref T a, ref T b)
        {
            T tmp = a;
            a = b;
            b = tmp;
        }
    }
}

Notes:

High quality blur filters can be expensive, so most bloom implementations do a cheap bilinear downsample to lower resolution before the ‘real’ blur. The original XNA sample operates at half resolution, but in a nod to the limited bandwidth of mobile GPUs, I made this version shrink to quarter size.
It is possible to implement Gaussian blur (or indeed any multi-tap filter) as a series of additive and subtractive blends with suitable offsets, but that gets expensive for large filter kernels. Instead I chose a Kawase blur (originally developed by Masaki Kawase for the Xbox1 game Wreckless), which cunningly exploits GPU bilinear filtering to get a not-quite-as-good-but-still-ok result more cheaply.
The threshold subtraction is perhaps the least intuitive operation. We want (source - threshold), but the alpha blending hardware only gives us (source - destination). So, we simply clear the destination rendertarget to our desired threshold value before drawing the source image!
There are two scaling operations in this bloom design: one to preserve full color range after the threshold subtraction, and a second after the blur to adjust intensity of the bloom. For efficiency, I apply these adjustments during the first and last blur passes, getting them for free as a side effect of drawing work that was already taking place.

So how does it look?

With BloomThreshold = 0.25f, BloomIntensity = 1.5f, BlurPasses = 4:

With BloomThreshold = 0.5f, BloomIntensity = 3, BlurPasses = 6:

With BloomThreshold = 0, BloomIntensity = 1.5f, BlurPasses = 3:

Voting results are in!

2012-01-19T20:04:00Z

Thanks for the comments about what I should write about next. Hopefully I managed to count these more accurately than the Iowa Republican party :-)

C++ 16

How GPU’s work 11

3D math 10

Game design 10

SIMD optimization 3

Of course my blog is not a democracy, so I’m not promising to actually cover these topics in that order! But it is useful to know that for instance I have more readers interested in C++ than in SIMD optimization.

There were also several write-in nominations:

Specifics of how XNA is implemented. It does seem like there should be a couple of interesting articles to be had here. I will have to think about exactly what they might be.
Managed <-> native interop (esp. WinRT). Hmm. My immediate reaction is I don’t know enough about this topic, but I will mull it over and see if anything worthwhile comes to mind.
A couple of requests to talk about future XNA plans. Sorry, no can do. Not my team any more!
Single-vote requests to write about input, component based entities, and XACT garbage. Unlikely (due to lack of knowledge / opinions / info to share) but I will bear them in mind.

Thank you all!

Is SpriteBatch Turing complete?

2011-12-29T22:58:56Z

Time for some end-of-year silliness...

Inspired by this recent Twitter exchange:

Scionwest - @shawnhargreaves @nickgravelyn How about post processing for WP7? I've seen people do Bloom effects and thought P.P. was not part of WP7?

nickgravelyn - @Scionwest Shaders aren't available, but I've seen some clever post-processing done without custom shaders. You theoretically could do CPU based "shaders", but you can also use blend states in fun ways to achieve effects

(which is actually an interesting topic that I may someday return to)

I found myself thinking "well, of course you could implement bloom, because the no-programmable-shaders Reach graphics subset on Windows Phone is Turing complete, so can do anything you can imagine given sufficient ingenuity. It might not be easy, efficient, or sensible, but anything is possible..."

And then I found myself thinking, is that really true?

We can add and subtract via blend states, and perform comparisons with AlphaTestEffect, which seems like it should be enough to enable arbitrary algorithms (at least if we ignore mundane practicalities such as time and space constraints :-) But can I prove that XNA on Windows Phone is enough to enable Turing complete GPU computation?

Conway's Game of Life is already proven to be a form of universal Turing machine, so I set out to see if I could implement that on the GPU without custom shaders.

Starting with the default Game template, I declared two rendertargets to hold the state of my simulation:

    const int width = 256;
    const int height = 128;

    RenderTarget2D currentState;
    RenderTarget2D nextState;

Plus two helper objects:

    AlphaTestEffect alphaTestEffect;

    Texture2D singleWhitePixel;

These are initialized in LoadContent:

    currentState = new RenderTarget2D(GraphicsDevice, width, height, false, SurfaceFormat.Color, DepthFormat.Depth24Stencil8);
    nextState    = new RenderTarget2D(GraphicsDevice, width, height, false, SurfaceFormat.Color, DepthFormat.Depth24Stencil8);

    alphaTestEffect = new AlphaTestEffect(GraphicsDevice);

    singleWhitePixel = new Texture2D(GraphicsDevice, 1, 1);

    singleWhitePixel.SetData(new Color[] { Color.White });

In order for it to do anything interesting, the Game of Life must be initialized to more than just zeros. This code (at the end of LoadContent) creates a single glider that will move diagonally across the screen:

    Color[] initialData = new Color[width * height];

    initialData[3 + 1 * width] = Color.White;
    initialData[3 + 2 * width] = Color.White;
    initialData[3 + 3 * width] = Color.White;
    initialData[2 + 3 * width] = Color.White;
    initialData[1 + 2 * width] = Color.White;

    currentState.SetData(initialData);

For a more interesting initial state, add this (before the currentState.SetData call) to randomize the cells:

    Random random = new Random();

    for (int i = 0; i < 10000; i++)
    {
        initialData[random.Next(width * height)] = Color.White;
    }

My Draw code is simple. It uses SamplerState.PointClamp to scale up the current simulation state to fill the entire screen, without any filtering:

    SimulateLife();

    GraphicsDevice.Clear(Color.CornflowerBlue);

    spriteBatch.Begin(SpriteSortMode.Deferred, null, SamplerState.PointClamp, null, null);
    spriteBatch.Draw(currentState, GraphicsDevice.Viewport.Bounds, Color.White);
    spriteBatch.End();

Ok, that's the boilerplate taken care of. How are we actually going to implement this SimulateLife method? Wikipedia defines the rules as:

Any live cell with fewer than two live neighbours dies, as if caused by under-population
Any live cell with two or three live neighbours lives on to the next generation
Any live cell with more than three live neighbours dies, as if by overcrowding
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction

But I found it useful to rearrange this to a different (equivalent) form:

Rule 1: If there are two live neighbours, preserve the current state of the cell
Rule 2: If there are three live neighbours, set the cell to alive
Rule 3: Otherwise set the cell to dead

Ok, let's do it! SimulateLife starts by drawing onto the nextState rendertarget, and setting up the AlphaTestEffect to only accept pixels with alpha greater than 128, i.e.. cells that are currently alive:

    GraphicsDevice.SetRenderTarget(nextState);

    GraphicsDevice.Clear(Color.Transparent);

    Viewport viewport = GraphicsDevice.Viewport;

    Matrix projection = Matrix.CreateOrthographicOffCenter(0, viewport.Width, viewport.Height, 0, 0, 1);
    Matrix halfPixelOffset = Matrix.CreateTranslation(-0.5f, -0.5f, 0);

    alphaTestEffect.Projection = halfPixelOffset * projection;

    alphaTestEffect.AlphaFunction = CompareFunction.Greater;
    alphaTestEffect.ReferenceAlpha = 128;

We are going to count how many alive neighbours each cell has, accumulating this value in the stencil buffer (which was previously cleared to zero). We do this by drawing the current simulation state texture 8 times, shifted one pixel to the top left, top, top right, left, etc. We use a blend state that prevents drawing anything to the color buffer, because we are only interested in generating stencil values. This code combines AlphaTestEffect (which rejects dead neighbour pixels) and the stencil buffer (which counts how many neighbour pixels pass the alpha test):

    spriteBatch.Begin(SpriteSortMode.Deferred, blendNone, null, stencilAdd, null, alphaTestEffect);

    spriteBatch.Draw(currentState, new Vector2(-1, -1), Color.White);
    spriteBatch.Draw(currentState, new Vector2( 0, -1), Color.White);
    spriteBatch.Draw(currentState, new Vector2( 1, -1), Color.White);
    spriteBatch.Draw(currentState, new Vector2(-1,  0), Color.White);
    spriteBatch.Draw(currentState, new Vector2( 1,  0), Color.White);
    spriteBatch.Draw(currentState, new Vector2(-1,  1), Color.White);
    spriteBatch.Draw(currentState, new Vector2( 0,  1), Color.White);
    spriteBatch.Draw(currentState, new Vector2( 1,  1), Color.White);

    spriteBatch.End();

This uses two custom state objects:

    static readonly BlendState blendNone = new BlendState
    {
        ColorSourceBlend = Blend.Zero,
        ColorDestinationBlend = Blend.One,

        AlphaSourceBlend = Blend.Zero,
        AlphaDestinationBlend = Blend.One,

        ColorWriteChannels = ColorWriteChannels.None,
    };

    static readonly DepthStencilState stencilAdd = new DepthStencilState
    {
        DepthBufferEnable = false,
        StencilEnable = true,
        StencilFunction = CompareFunction.Always,
        StencilPass = StencilOperation.Increment,
    };

We now have our rendertarget cleared to zero (which means all dead, so we have already implemented rule #3), while stencil contains a count of live neighbour cells. It is but the work of a moment to draw a copy of the current simulation state, using stencil to only accept cells that have 2 live neighbours, thus implementing rule #1:

    spriteBatch.Begin(SpriteSortMode.Deferred, BlendState.Opaque, null, stencilDrawIf2, null);
    spriteBatch.Draw(currentState, Vector2.Zero, Color.White);
    spriteBatch.End();

The last draw call implements rule #2 by rendering solid white (which means alive) over only those cells which have 3 live neighbours:

    spriteBatch.Begin(SpriteSortMode.Deferred, BlendState.Opaque, null, stencilDrawIf3, null);
    spriteBatch.Draw(singleWhitePixel, viewport.Bounds, Color.White);
    spriteBatch.End();

This requires two new state objects:

    static readonly DepthStencilState stencilDrawIf2 = new DepthStencilState
    {
        DepthBufferEnable = false,
        StencilEnable = true,
        StencilFunction = CompareFunction.Equal,
        ReferenceStencil = 2,
    };

    static readonly DepthStencilState stencilDrawIf3 = new DepthStencilState
    {
        DepthBufferEnable = false,
        StencilEnable = true,
        StencilFunction = CompareFunction.Equal,
        ReferenceStencil = 3,
    };

Finally, the end of SimulateLife unsets our output rendertarget, then swap the two rendertargets, replacing the current state with the new one we just computed:

    GraphicsDevice.SetRenderTarget(null);

    Swap(ref currentState, ref nextState);

Swap is a handy little helper, implemented like so:

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

So, does it work?

Tada! SpriteBatch is Turing complete :-)

Exercise for the reader: is it possible to do the same thing without using stencil?

What should I write about next?

2011-12-29T19:34:46Z

I have a couple more articles planned about aliasing and motion blur, but am curious to hear where you would like me to take this blog next.

Some topics I am considering:

C++. Dirty secret: although I've mostly blogged about C# programming, much of XNA itself is written in C++, so I've actually been straddling both worlds for years. And interesting things are happening in C++ land right now, with the arrival of C++11 and maturity of the standard library affecting best practices and recommended style. But are my readers interested in such things? You tell me!

More about how GPU's work. Tiling, swizzling, caching, parallelism, predication, etc.

3D Math. Vectors, matrices, what really is an orientation, how to think in multiple coordinate spaces, and why rotation angles are Teh Evil.

Game design. What makes it fun? What makes a good AI? How does one persuade customers to try/buy your work? I've been reluctant to cover these topics because it's not really my area of expertise, but I do have some opinions about it so who knows, maybe a few worthwhile articles to be had here.

SIMD optimization, SSE, DirectXMath.

Other?

From games to telephones

2011-12-14T00:22:45Z

After six years working on XNA, I decided it was time to take on a new challenge. I am moving to the Windows Phone team, where I will be working on things I'm not sure how much I can say about here (leaking future business plans on MSDN might not be the best way to endear myself to my new boss :-)

Writing this post is a bittersweet moment for me. I'm excited by what the future holds for Windows Phone, and looking forward to my chance to be part of that, but also sad to leave a team and product that have given me so much satisfaction. There'll be no going back once I hit that Publish button a few minutes from now...

I feel an urge to wax nostalgic about some of my favorite times with XNA:

Staying up all night to watch Michael purchase the first ever Creators Club subscription.
The first Dream Build Play competition, when we got to see the first actual games made with our technology (Dishwasher FTW!)
On stage with Mitch at Gamefest, where I wrote a network game 'from scratch' (if you ignore some minor snippet cheating :-) in less than an hour. I'm still blown away by the fact that our APIs were simple enough to make this possible. Also amazed that the demo actually worked, considering what an unstable early build we were using! Unfortunately there is no video of this, and the slides don't do it justice since the whole point was the live coding demo.
On stage once more at MIX, demonstrating XNA graphics on the new Windows Phone with a frighteningly last minute demo cobbled together just a few days earlier using a hot-off-the-presses build of XNA on an even more experimental frankenbuild of the phone OS. Then rushing back to my hotel room to blog about the new features coming in XNA 4.0 (which, modesty aside, I still think is some of the best design work I have done to date).
Trying to decide, of all the lines of code I have written in my life, which one has been executed the most times? I think it must be the default SpriteBatch pixel shader.
Last but not least, spending time with y'all on forums and this blog, where I got to know so many great people and see the amazing things you create.

I'm not yet sure what this means for my blog. I want to keep writing, but will probably cover more general graphics and game development topics, and will obviously no longer have inside scoop on XNA implementation details. I'm also not sure how much time I will have for writing, especially in the early months as I settle into the new job, but I will do my best.

Ok, I'm off now to meet some new people and learn my way around a whole new product.

Temporal sampling frequency (aka 'framerate')

2011-11-19T00:21:47Z

Game player: "d00d, teh framerate totally sux0rz!"

Game developer: "we are experiencing aliasing due to low sampling frequency along the temporal axis..."

One of the many decisions that goes into making a game is whether it is better to run at a high framerate, which means drawing many frames per second and thus having little time to spend on each, or should we choose a lower framerate, get more time per frame, and thus be able to draw larger numbers of higher quality objects? The perfect balance is a matter of heated debate, varying with the game, genre, and personal preference, but there are some widely accepted truths:

Dropping below 30 fps is rarely a good idea
30 fps is generally considered ok, but 60 is better
Higher than 60 fps offers rapidly diminishing returns

Yet movies are animated at a mere 24 fps! Why has Hollywood chosen a framerate so much lower than most game developers?

Perhaps this is just a historical legacy, preserved for backward compatibility with decisions made in the 1920s? But when IMAX was designed in the late 1960s, they specified new cameras, film, projectors, and screens, while keeping the 24 fps sampling frequency. And in the early 21st century, Blu-ray and HD DVD fought an entire format war during the transition to high definition digital video, but oh look, still 24 fps. It sure looks like the movie world just doesn't see any reason to go higher, similar to how few game developers care to go above 60 fps.

Ok, next theory: perhaps the difference is because games are interactive, while movies are just prerecorded entertainment? The lower the framerate, the more latency there will be between providing an input and seeing the resulting change on screen. The pause button on my DVR remote has ~.5 sec latency, which is irrelevant when watching my favorite romantic comedy but would be a showstopper when trying to nail a Halo headshot.

And a final theory: perhaps the difference is due to aliasing? Realtime graphics are usually point sampled along the time axis, as we render individual frames based on the state of the game at a single moment in time, with no consideration of what came before or what will happen next. Movies, on the other hand, are beautifully antialiased, as the physical nature of a camera accumulates all light that reaches the sensor while the shutter is open. We've all seen the resulting blurry photos when we try to snap something that is moving too quickly, or fail to hold the camera properly still. Motion blur is usually considered a flaw when it shows up uninvited in our vacation snapshots, but when capturing video it provides wonderfully high quality temporal antialiasing.

So which theory is correct? Do games care more than movies about framerate because of latency, or because of aliasing?

We can find out with a straightforward experiment. Write a game that runs at 60 fps. Make another version of the same game that runs at 30 fps. Make a third version at 30 fps with super high quality temporal antialiasing (aka motion blur). Get some people to play all three versions. Get more people to watch the first people playing. Compare their reactions.

If aliasing is a significant factor, the watchers will be able to distinguish 60 fps from 30 fps, but unable to distinguish 60 fps from motion blurred 30 fps
If latency is a significant factor, people playing the game will be able to distinguish 60 fps from motion blurred 30 fps, even though the watchers cannot
If everybody can tell the versions apart, both theories must be wrong
If nobody can tell any difference, we might as well just leave the whole game at 30 fps and be done with it :-)

If you try this experiment, you will find the results depend on which game you choose to test with. Many observers do indeed think motion blurred 30 fps looks the same as 60 fps, so temporal aliasing is surely important. Players also find the two equivalent with some games, while reporting a big difference with other games. So the significance of latency depends on the game in question.

Sensitivity to latency is directly proportional to how hands-on the input mechanism is. When you move a mouse, even the slightest lag in cursor motion will feel very bad (which is why the mouse has a dedicated hardware cursor, allowing it to update at a higher framerate than the rest of whatever app is using it). Likewise for looking around in an FPS, or pinch zooming on a touch screen. You are directly manipulating something, so expect it to respond straight away and for the motion to feel pinned to your finger. Less direct control schemes, such as pressing a fire button, moving around in an FPS, driving a vehicle, or clicking on a unit in an RTS, can tolerate higher latencies. The more indirect things become, the less latency matters, which is why third person games can often tolerate lower framerates than would be acceptable in an FPS.

What can we learn from all this rambling?

If we have a game at 60 fps, and are trying to find room to add more sophisticated graphics, an interesting option might be to drop down to 30 fps while adding motion blur. As long as we can implement a good blur for less than the cost of drawing one 60 fps frame, we may be able to achieve equivalent visual quality while freeing up a bunch of GPU cycles.
If we have a game at 30 fps or lower, we should avoid the sort of input behaviors that will make this latency objectionable to the player. Conversely, if we have a game that uses only the sort of input not sensitive to latency, there is less point bothering to make it run at 60 fps!

Yeah. yeah, so I should talk about how to actually implement motion blur. Next time...

Stand still and they won't see you

2011-11-08T01:54:06Z

So far I have written about aliasing in the context of rendering single images, but neglected to consider what happens when we string a series of images together, attempting to create the illusion of smooth motion. Animation introduces the temporal (time) axis, which we sample by rendering frames usually 30 or 60 times per second. And remember, whenever we sample from a theoretically continuous signal, aliasing can ensue.

Yet the biggest impact of animation is often not new aliasing at all, but how it makes any existing aliasing far more objectionable. If you have aliased triangle edges, textures, geometry, or shaders, some portion of your output pixels will be determined by aliasing noise as opposed to an accurate representation of the desired image. A small amount of random noise may be unnoticeable in a still image, but when the camera moves even a fraction, the nature of aliasing means these random elements will be different for every frame. Because the human eye is drawn to motion, even a few percent aliasing noise over an otherwise stable image becomes painfully obvious as the scene shimmers, strobes, flickers, and crawls.

When testing graphics code, always view with a camera that moves the same way as your final game. That is the only way to judge whether you have aliasing under control.

Aliasing can sometimes be 'fixed' simply by getting rid of motion! In MotoGP we mapped special cameras for use during replays, trying to emulate how a race would be filmed for TV. Some of these cameras were low to the ground, looking down a straight section of track with an extremely narrow field of view (aka telephoto lens). These unusual angles let to nasty aliasing that was not visible during normal gameplay. We fixed it by locking the problematic cameras in place, setting a flag that forbade them from rotating or changing zoom level. The aliasing was technically still as bad, but because it no longer moved, the game looked much better.

A similar technique is used in some shadow mapping implementations, which calculate light projections in such a way as to snap shadow map texels to a fixed worldspace grid. The shadow map no longer moves through texel space, so aliasing is less noticeable.

Shader aliasing

2011-11-01T01:07:24Z

Looking through my backlog of half written articles, I realized I have a couple more topics in my series about antialiasing, which I had entirely forgotten about! Oops...

Actually, though, today is a good day to finish this article. Forget your ghosts, ghouls, and goblins, for I have something Really Truly Very Scarily Horrible indeed. Yes, boys and girls, today marks the return of the ALIASING MONSTER!

A shader is really just a program that computes what color pixels should end up on the screen. Depending on the details of what this program does, it could cause aliasing, or it could use any imaginable technique (including any of the things I previously discussed) to avoid aliasing.

For instance, consider a pixel shader that implements a vector rasterization algorithm. Invoked by C# code that draws a simple square:

    spriteBatch.Begin(0, null, null, null, null, effect); 
    spriteBatch.Draw(flatWhiteDummyTexture, new Rectangle(0, 0, 128, 128), Color.White); 
    spriteBatch.End();

If we apply this pixel shader:

    float2 circleCenter = { 0.5, 0.5 }; 
    float circleRadius = 0.4; 
    float spriteSize = 128;

    float4 PixelShaderFunction(float4 color : COLOR0, float2 uv : TEXCOORD0) : COLOR0 
    { 
        float distanceFromCenter = length(circleCenter - uv); 
        float distanceFromCircle = abs(circleRadius - distanceFromCenter) * spriteSize; 
    
        float alpha = (distanceFromCircle < 0.5) ? 1 : 0;

        return color * alpha; 
    }

    technique Technique1 
    { 
        pass Pass1 
        { 
            PixelShader = compile ps_2_0 PixelShaderFunction(); 
        } 
    }

We get a circle:

But it is an aliased circle. We can fix this by changing the alpha computation in our pixel shader to:

    float alpha = saturate(1 - distanceFromCircle);

Which gives a nicer, antialiased result:

Zoomed in so you can see the difference more clearly:

Ok, so this is a contrived case. And the way I implemented this antialiasing is specific to this particular circle algorithm. It isn't especially useful to say "depending on what they do, some shaders may cause aliasing, but there may be specialized ways you can change them to antialias their computations" :-) Is there some more general principle that be extracted here?

Vertex Shader Aliasing

Perhaps surprisingly, vertex shaders are not usually a source of aliasing problems, at least so long as your triangles remain large enough to avoid geometry aliasing.

The vertex shader is responsible for computing two things:

Position of each vertex on the screen, which causes geometry aliasing if the resulting triangles are too small
Values such as colors and texture coordinates, which are interpolated and then passed to the pixel shader

Regardless of whether these interpolated values are looked up from vertex buffers or computed by whatever crazy piece of math you can imagine, it is basically impossible for them to cause aliasing. Remember that aliasing occurs when we resample a signal containing frequencies above the Nyquist threshold. We can think of color or texture coordinate channels as a waveform:

Frequency is determined by the distance between vertices (aka triangle size)
Changing the value of the color or texture coordinate alters the amplitude of the waveform, but not usually its frequency
Changing values can reduce frequency if several adjacent vertices share identical values, but can never increase it above the limit determined by triangle size

This means that, having taken care to avoid small triangles that would cause geometry aliasing, you need not worry about aliasing elsewhere in your vertex processing.

Note that, although choice of color or texture coordinates cannot introduce aliasing that was not previously present, it can affect how noticeable previously existing aliasing is in practice. If you had a model with nasty geometry aliasing, but colored the whole thing subtle shades of grey, the aliasing might not be too offensive. Change the colors to a rainbow of primary shades, and even though we altered the amplitude but not frequency of our color signal, the geometry aliasing will now be clear for all to see. It was there all along, but our choice of colors can make the problem more or less obvious. Regardless, such problems are best tackled by fixing the geometry aliasing at source (which means using larger triangles) rather than trying to paper over them by changing vertex color or texture coordinate mappings.

Pixel Shader Aliasing

The pixel shader is where things get interesting. This is a function that takes interpolated values from the vertex shader, applies an arbitrary computation, and produces an output color for a single screen pixel. The previous section explained how, as long as your triangles are not too small, the pixel shader input values will not be aliased, but it is both possible and common for pixel shader computations to introduce entirely new aliasing of their own.

Whenever a pixel shader applies a computation to an input value it is useful to ask yourself, does this alter the frequency of the signal, or change its amplitude, or both? If the former, aliasing may ensue, but if the latter, we are safe.

Consider these common shader operations:

    color = textureColor * lightColor;

    alpha *= 2;

    result = lerp(baseTexture, environmentMap, fresnelAmount);

    intensity = dot(normal, lightDirection);

These are all linear computations, which means they change amplitude but not frequency, and so will not cause aliasing.

These, on the other hand, are not linear. They have the potential to increase the frequency of the output signal above that of the input, so aliasing must be a concern any time you encounter a shader that does such things:

    color = (alpha < 0.5) ? red : green;

    color = lookupTable[alpha];

    result = pow(nDotL, 16);

The act of indexing into a lookup table is especially important to graphics programmers, because this is exactly what we do each time we sample a texture map! Fortunately, GPUs provide sophisticated mechanisms to avoid aliasing when performing such lookups. If your pixel shader contains other nonlinear math that is causing aliasing artifacts, a good solution is often to replace these computations with a texture lookup, thus bringing the power of bilinear filtering and mipmaps to bear on the problem.

Specular Light Aliasing

One of the most everyday and yet pernicious examples of shader aliasing is the humble specular light. This is so common and inoffensive that we built it into the standard BasicEffect lighting model, and yet specular lighting involves a power computation which is inherently nonlinear, and thus a source of aliasing. The higher you crank the specular power setting, the shiner the object looks, and also the worse the aliasing becomes.

Surprisingly for something that is so widely used, there is no universally accepted solution for specular aliasing problems. Many people just turn down their specular intensity or specular power for whichever models show the worst artifacts, put up with minor remaining flaws, and call it good.

A full discussion of how to antialias specular lighting is beyond the scope of this article. The Self Shadow blog has a great summary of the topic.

RIP John McCarthy

2011-10-25T19:05:03Z

What a sad month for those of us who program computers.

Take a moment to reflect on this paper, published in April 1960:

No provision need be made for the user to program the return of registers to the free-storage list.

This return takes place automatically, approximately as follows (it is necessary to give a simplified description of this process in this report): There is a fixed set of base registers in the program which contains the locations of list structures that are accessible to the program. Of course, because list structures branch, an arbitrary number of registers may be involved. Each register that is accessible to the program is accessible because it can be reached from one or more of the base registers by a chain of car and cdr operations. When the contents of a base register are changed, it may happen that the register to which the base register formerly pointed cannot be reached by a car - cdr chain from any base register. Such a register may be considered abandoned by the program because its contents can no longer be found by any possible program; hence its contents are no longer of interest, and so we would like to have it back on the free-storage list. This comes about in the following way.

Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts.

First, the program finds all registers accessible from the base registers and makes their signs negative. This is accomplished by starting from each of the base registers and changing the sign of every register that can be reached from it by a car - cdr chain. If the program encounters a register in this process which already has a negative sign, it assumes that this register has already been reached.

After all of the accessible registers have had their signs changed, the program goes through the area of memory reserved for the storage of list structures and puts all the registers whose signs were not changed in the previous step back on the free-storage list, and makes the signs of the accessible registers positive again.

This process, because it is entirely automatic, is more convenient for the programmer than a system in which he has to keep track of and erase unwanted lists. Its efficiency depends upon not coming close to exhausting the available memory with accessible lists. This is because the reclamation process requires several seconds to execute, and therefore must result in the addition of at least several thousand registers to the free-storage list if the program is not to spend most of its time in reclamation.

This was on a computer with single digit kilobytes of memory, in a world where high level languages were still an unproven, experimental idea. Yet to this day, much of what we consider 'new' in mainstream programming languages (C# 3.0, anyone?) boils down to pieces of Lisp wrapped up with a more friendly syntax!

A great man, truly ahead of his time, whose work benefited us all.

Silverlight 3D and the composition thread

2011-10-18T18:51:43Z

A simple test

Load the Silverlight 5 port of the XNA bloom sample (which you can find in c:/Program Files (x86)/Microsoft SDKs/Silverlight/v5.0/Toolkit/Sep11/Source/Sample source code.zip/Xna after installing the Silverlight toolkit). Run it, and observe the shiny tank.

Now open up MainPage.xaml.cs, find the OnDraw method, and add this line:

    int test = SettingsCombo.SelectedIndex;

Run the sample again:

CrossAppDomainMarshaledException was unhandled
System.UnauthorizedAccessException: Invalid cross-thread access.
at MS.Internal.XcpImports.CheckThread()
at System.Windows.DependencyObject.GetValueInternal(DependencyProperty dp)
at System.Windows.FrameworkElement.GetValueInternal(DependencyProperty dp)
at System.Windows.Controls.Primitives.Selector.get_SelectedIndex()
at Bloom.MainPage.OnDraw(Object sender, DrawEventArgs e)

What's going on?

The traditional XNA Game class is not multithreaded. Sure, you can create threads of your own if you want, but parallel programming is strictly opt-in, so if you don't do anything special to make it happen, you won't have to worry about the insanity that is threaded programming.

Silverlight used to work the same way. It has a single UI thread which is responsible for all user code, event handlers, and XAML rendering. But Silverlight 5 adds a new composition thread, which takes care of GPU accelerated rendering (although software rendering still runs on the UI thread). The advantage of this architecture is that, even if you block the UI thread running some lengthy operation, the composition thread can independently continue to play back XAML animations, thus providing a smoother UI with less glitching. Of course, the downside is that threaded programming is REALLY HARD, but since all your code still runs on the UI thread, you don't generally have to worry about this. Those clever coding gnomes on the Silverlight team have taken care of the necessary synchronization so the composition thread can do its thing without customer code needing to know or care that things are now running in parallel behind the scenes.

Enter the 3D DrawingSurface...

Unlike the rest of Silverlight, which uses a retained mode XAML rendering architecture, DrawingSurface provides an immediate mode 3D API. Because this rendering is GPU accelerated, the DrawingSurface.Draw event must occur, not on the UI thread along with the rest of your code, but directly on the composition thread.

Here be dragons! Even though you never created any threads of your own, the simple act of hooking the Draw event means your 3D rendering code can run in parallel with regular UI code. Thus you find yourself inadvertently deep in the land of locks, interlocks, deadlocks, race conditions, and suchlike fun stuff :-)

What does this mean for me?

If you are making a game that uses only 3D rendering without any XAML UI, you can put all your code (both Update and Draw) inside the DrawingSurface.Draw event. Regardless of whether you choose variable or fixed timestep logic, this means the UI thread will be entirely unused, so there is no parallelism to worry about and everything will Just Work™ the way you expect.

If you combine 3D rendering with XAML UI, you must figure out how to synchronize access to any data that is shared between the two. In the bloom sample (which uses XAML UI to alter bloom settings) you will notice the rendering code does not read its settings directly from the Silverlight controls. Instead, MainPage.xaml hooks the change events from these controls (which run on the UI thread) and copies their settings into fields which can be safely accessed by the composition thread. If the shared data structure was more complex, we would need a lock to coordinate this access.

Game timing in Silverlight 5

2011-10-17T23:18:30Z

One thing missing from the new 3D functionality in Silverlight 5 is an equivalent of the XNA Game class. I previously wrote about how to provide XNA style Update and Draw methods in a WinForms environment. What is the Silverlight equivalent of that?

After installing the Silverlight Toolkit, create a new project using the Silverlight 3D Application template. Open up MainPage.xaml, and note how this declares a DrawingSurface object and hooks its Draw event. Now open MainPage.xaml.cs, and observe the implementation of the myDrawingSurface_Draw event handler method. After calling scene.Draw(), this calls e.InvalidateSurface(), which tells Silverlight this object needs to be redrawn. Normally Silverlight would draw the object once at startup, then only redraw it when something changed about the scene (perhaps because the object was resized, or some other shape moved over the top of it). But when the draw handler invalidates the surface, that causes it to be drawn again, which invalidates it again, which causes it to be drawn again, which { rinse, lather, repeat }. This effectively creates an infinite loop, with the surface constantly being redrawn, just like we want for a game loop.

Note also the UserControl_Loaded method in MainPage.xaml.cs, which is hooked up to the UserControl.Loaded event via MainPage.xaml. This is the Silverlight equivalent of the XNA Initialize and LoadContent methods.

Well and good, but how do we build an actual game on top of this system? Check out the Silverlight port of the XNA Platformer starter kit (in c:/Program Files (x86)/Microsoft SDKs/Silverlight/v5.0/Toolkit/Sep11/Source/Sample source code.zip/Xna). Again look at the myDrawingSurface_Draw method in MainPage.xaml.cs. This is very simple:

    private void myDrawingSurface_Draw(object sender, DrawEventArgs e)
    {
        platformerGame.Update(e);
        platformerGame.Draw(e);

        e.InvalidateSurface();
    }

What we have here is a variable timestep game loop. Thanks to the InvalidateSurface call, it will loop forever, calling Update and then Draw as fast as possible.

If you prefer to use a fixed timestep system, you can make one like so:

    readonly TimeSpan TargetElapsedTime = TimeSpan.FromTicks(TimeSpan.TicksPerSecond / 60);
    readonly TimeSpan MaxElapsedTime = TimeSpan.FromTicks(TimeSpan.TicksPerSecond / 10);

    TimeSpan accumulatedTime;


    private void myDrawingSurface_Draw(object sender, DrawEventArgs e)
    {
        TimeSpan elapsedTime = e.DeltaTime;

        if (elapsedTime > MaxElapsedTime)
        {
            elapsedTime = MaxElapsedTime;
        }

        accumulatedTime += elapsedTime;

        while (accumulatedTime >= TargetElapsedTime)
        {
            Update();
            accumulatedTime -= TargetElapsedTime;
        }

        Draw();
        e.InvalidateSurface();
    }

Silverlight 5 version of Ito's XNA AppWeek game

2011-10-07T22:59:37Z

Could this be the first ever 3D Silverlight game?

My colleague Ito ported the rail shooter that he originally wrote for AppWeek 2010 to use the new 3D features in Silverlight 5. First get the SL5 RC plugin (if you don't have it already). Then play the game here.

Once the intro animation finishes playing, mouse over enemy ships to target them, and left click to fire.

Silverlight 5 brings XNA 3D to the web

2011-10-06T00:13:00Z

I have been remiss in not mentioning this on my blog before, but if you are an XNA developer who hasn't been paying attention to Silverlight 5, now might be a good time to start!

A quick history:

At the MIX11 conference in April, we announced that Silverlight 5 was adding a new 3D API. This is based on XNA, so included familiar types such as GraphicsDevice, VertexBuffer, and Texture2D, but it was not a full port of XNA. In particular it did not include many of the higher level helper features, so there was no BasicEffect, no SpriteBatch, no math library, and no Content Pipeline. It did support custom shaders, but using a low level DX9 style constant register API as opposed to the friendlier Effect system used by XNA. This beta release made it possible to use high performance 3D in a Silverlight web app, but it wasn't exactly easy to do so!
In September, the Silverlight 5 RC added new features including the same five built-in effects as XNA 4.0, plus an XNA compatible math library. David Catuhe writes about these changes.
Now, the Silverlight Toolkit provides vastly improved XNA compatibility, including ContentManager, Model, SpriteBatch, Mouse, Keyboard, custom effects, and new Visual Studio templates for getting started with Silverlight 3D. Again David has a great intro.

This is still not all of XNA (for instance there is no Game class) but with this new toolkit, enough pieces are the same that porting existing Xbox or Windows Phone games to the web can be quite easy. It took us just a few hours to port several existing XNA samples, which are included in the toolkit (Toolkit/Sep11/Source/Sample source code.zip):

If you want to use the Content Pipeline in a Silverlight 5 app, you will also need to install XNA Game Studio 4.0 on your development PC. But don't worry, this doesn't mean you will have to redistribute XNA to your web clients, or have it installed on every computer that runs the app. Remember this diagram from an old article about the Content Pipeline:

The way this works with Silverlight 5 is that the blue boxes, which run at build time on your development PC, use the original XNA Game Studio 4.0 Content Pipeline assemblies. Only the red boxes, which execute at runtime on the client machine, use the new code from the Silverlight Toolkit. This is similar to when you build an XNA game for Xbox or Windows Phone, but the remote device is now a web browser. If you are extending the Content Pipeline to add new types, you will need to provide both an XNA version of these types for use at build time, and also a Silverlight version for runtime. Check out the Silverlight port of the Skinning sample for an example of how to set this up.

I don't normally name names, as I'm lucky to work with so many talented people and this blog is my chance to take credit for all their hard work :-) But in this case I want to give a shout out to Aaron Oneal and David Catuhe, who went above and beyond to pull all the pieces together and make this happen. Nice job guys!

Content pipeline builds no longer need a D3D device starting in the XNA Game Studio 4.0 Refresh Beta 2

2011-07-07T21:02:21Z

(shamelessly stealing the title of a post by my colleague Aaron)

In fact, why don't I let him provide the content as well as title:

http://blogs.msdn.com/b/astebner/archive/2011/07/07/10184338.aspx

XNB file format documentation

2011-07-07T17:51:43Z

Recent silence notwithstanding, I'm still here, and will have more to say about aliasing as soon as I find myself less busy!

In the meantime, check out this latest App Hub release: http://create.msdn.com/en-US/sample/xnb_format

This article documents the format of the compiled data files (.xnb) produced by the XNA Game Studio 4.0 Content Pipeline build process. This information may be useful if you wish to write your own code to load .xnb files into a programming environment other than XNA / .NET, or if you wish to create .xnb files independently of the usual Content Pipeline build process.

It also includes an example .xnb parser, written in native C++, which demonstrates how to parse a compiled XNB file by printing its contents to the screen. This can be used as a reference to help you understand how to write your own XNB loader, and also as a debugging tool for investigating exactly what data is contained within an XNB file.

Reza's blog

2011-06-06T19:05:56Z

My colleague Reza recently started a blog at http://blogs.msdn.com/b/rezanour. He already has some good posts about vector math, and is a smart guy so I'm betting will be writing many interesting things in the future :-)

Geometry aliasing

2011-05-18T22:01:32Z

Back when multisampling first showed up, GPU hardware was slow, so triangle counts were low. Complex curved shapes were approximated by a small number of faceted triangles, each of which was big enough to cover many screen pixels.

This created an odd situation where early articles about multisampling focused on how it could smooth jaggies along the straight edges of these enormous triangles. We’d become so used to the faceted appearance of computer graphics that we could geek out over how beautifully antialiased our triangle edges were, without ever stopping to notice “whoah, that dude’s entire head is made of just 5 triangles!”

But hardware improved. Triangle counts went up. A high end modern game typically uses somewhere between 4000 and 6000 triangles for a main character.

Consider a typical gameplay situation:

The character is drawn in such a way that it occupies 1/8 the height of the screen
The game is rendering at 720p, so the resulting image is 90 pixels high
That means it covers ~2000 screen pixels
Assume half of our 6000 triangles are backfacing
We are left with 3000 triangles, covering 2000 output pixels

With this much detail in our models, faceted geometry is a thing of the past. Instead we have a new problem: we just got Nyquisted!

Remember: to avoid aliasing we must take at least twice as many output samples as our highest frequency input signal. But here we have FEWER output pixels than input triangles. It is intuitively obvious that this must cause aliasing. With fewer pixels than triangles, some triangles will inevitably not appear in the output image at all. As the object moves, which triangles are lucky enough to get themselves a pixel will randomly vary, so the image shimmers with aliasing as individual triangles pop in and out of view.

In fact there is a narrow sweet spot for how many triangles a model should contain. For best quality, you want each triangle to cover exactly two screen pixels. If triangles are smaller than this, you cross the Nyquist threshold and get aliasing. If larger, your silhouette will appear polygonal and faceted.

It is not entirely intuitive that the sweet spot is two pixels per triangle as opposed to just one, yet this is true. Consider a circle being approximated as a series of straight line segments. As you increase the number of segments, the circle becomes more perfectly round. By the time each line segment reaches two pixels in length, the circle is perfect. Adding more line segments beyond this point will not give any improvement to the curvature of the shape.

It is obviously impractical to keep all our triangles exactly the same size on screen, given that models must be drawn at different sizes as they or the player move around the world. So how can we draw high detail geometry without aliasing?

Multisampling (or supersampling if you can afford it) helps by giving more headroom before we hit the Nyquist threshold, but this alone is not enough to avoid all geometry aliasing.

Normalmaps can be a powerful technique. We have great features for avoiding aliasing when resampling textures, so any time we can take fine detail out of our geometry and replace it with a normalmap, that will help control aliasing. We often think of normalmaps as purely a performance optimization (replacing expensive geometry with a cheap texture map) but they can also boost visual quality (replacing a data representation that cannot be easily filtered with one that supports anisotropic filtering and mipmaps).

Finally, it is important to consider level-of-detail model variants. When the object is far away, replacing that 6000 triangle model with a simpler 1000 or 500 triangle alternative will not only boost perf, but also reduce geometry aliasing artifacts.

Moral: when it comes to triangle counts, more is not always better! Beware of trying to draw more triangles than you have screen pixels to represent. That way lieth the land of aliasing.

Antialiasing alpha cutouts

2011-05-06T21:29:11Z

Alpha cutouts (where you use the alpha channel of a texture to determine the shape of a sprite or billboard) are the cause of many an aliasing problem. There are basically two ways to do alpha cutouts, both tragically flawed.

Alpha blended cutouts

As long as you start with high quality source textures, and draw them using bilinear filtering and mipmaps, alpha blended cutout textures can be pleasingly free of aliasing artifacts.

But alpha blending does not play nice with the depth buffer, and it can be a PITA to manually depth sort every piece of alpha cutout geometry!

Alpha tested cutouts

In an attempt to make the hardware depth buffer work with alpha cutouts, many developers switch from full alpha blending to alpha testing (using the XNA AlphaTestEffect, or the clip() HLSL pixel shader intrinsic). This does indeed avoid the complexity of manually sorting alpha blended objects, but at the cost of aliasing.

The problem is that alpha testing only provides a boolean on/off decision, with no ability to draw fractional alpha values.

In mathematical terms, when we quantize a smoothly varying signal such as the alpha channel of a texture into a binary on/off decision, we are increasing the amount of high frequency data in our signal, which moves the Nyquist threshold in the wrong direction and hence increases aliasing.

Or I can avoid the math and try a common sense explanation:

We would normally antialias our source textures by including fractional values around shape borders, but alpha testing does not support fractional alpha values, so this is no longer possible.

We would normally avoid aliasing when resampling textures via bilinear filtering and mipmapping. But even if the original texture uses only on/off boolean alpha, when we filter between multiple texels, or scale it down to create 1/2, 1/4, and 1/8 size mip levels, these will inevitably end up with fractional alpha values. To use alpha testing, we must round all such values to either fully transparent or fully opaque, which entirely defeats the point of filtering and mipmapping.

We would normally avoid aliasing along the edges of triangle geometry by multisampling, but remember this only runs the pixel shader one per final output pixel. Since each group of multisamples gets a single alpha value from this single shader invocation, each multisample inevitably also has the same alpha test result, so multisampling is useless when it comes to smoothing our alpha cutout silhouette.

Yowser! Our entire arsenal of antialiasing techniques just vanished in a puff of smoke...

The only common antialiasing technique that works with alpha tested cutouts is supersampling. Which is great if you can afford it, but most games cannot.

Example time. Consider this image, taken from the XNA billboard sample, which uses full alpha blending with a two pass depth sorting technique:

If I change the code to use alpha testing instead of blending, standard depth buffer sorting works with no more need for that expensive two pass technique, but at the cost of nasty aliasing on the thinner parts of the grass fronds:

How to fix this?

You don't. There are really just three choices for alpha cutouts:

Go for quality over simplicity. Use full alpha blending, and manually sort by depth.
Put up with sorting artifacts. Use full alpha blending, but don't bother to depth sort.
Put up with aliasing problems. Use alpha testing, and let the depth buffer handle sorting.

In MotoGP we used a mixture of #2 and #3, and let the artists choose which was the lesser evil for each alpha cutout texture.

Antialiasing source textures

2011-05-03T19:12:34Z

This is almost too obvious to be worth pointing out, but no amount of clever tricks like bilinear filtering and mipmapping will help if your input data is itself already aliased!

Yet the example texture used in my previous post had nasty pixelization along the diagonal black lines:

I can improve this just by editing the source image in a paint program:

Compare these two versions at original size:

When a sprite is drawn without any resampling (at an integer pixel location, with no scaling or rotation) the resulting image is an exact copy of the source data, so it is obviously important that this source data contain as little aliasing as possible. Perhaps less obvious is that manually antialiasing my source data also helps when the texture is resampled. In mathematical terms, by smoothing the diagonal lines I have reduced the amount of high frequency information in my source signal, thus gaining more headroom to resample this signal before I will run into the Nyquist threshold and encounter aliasing.

Simple moral of this story: high quality antialiased textures are better than crappy ones with aliasing problems :-)

Alternative moral for those who find themselves suspicious of oversimplification: if you find yourself with the occasional texture that just won't stop aliasing no matter what you do, consider applying a blur to the relevant source images. Blurring removes high frequency data, which shifts the Nyquist threshold, which may be enough to fix the aliasing. This can obviously be taken too far (it's no good if we fix aliasing by making everything blurry!) but the occasional subtle blur, judiciously applied, can be a valuable weapon in the antialiasing arsenal.

Texture aliasing

2011-04-29T23:18:07Z

Aliasing can occur any time you resample a texture, for instance to scale it, rotate it, or map it onto a 3D model. Thanks to our friend the Nyquist threshold, the resulting problems get worse the lower a frequency you sample at, ie. the smaller you shrink it.

Check out this awesome 32x32 test image:

Zoomed 4x so you can see in detail:

This test code draws six copies, first with no transform, then rotated, followed by straight and rotated versions at half and quarter size:

    spriteBatch.Begin(0, null, SamplerState.PointClamp, null, null);

    spriteBatch.Draw(testTexture, new Vector2(20, 24), null, Color.White, 0, new Vector2(16, 16), 1, 0, 0);
    spriteBatch.Draw(testTexture, new Vector2(60, 24), null, Color.White, 1, new Vector2(16, 16), 1, 0, 0);

    spriteBatch.Draw(testTexture, new Vector2(95, 24), null, Color.White, 0, new Vector2(16, 16), 0.5f, 0, 0);
    spriteBatch.Draw(testTexture, new Vector2(120, 24), null, Color.White, 1, new Vector2(16, 16), 0.5f, 0, 0);

    spriteBatch.Draw(testTexture, new Vector2(140, 24), null, Color.White, 0, new Vector2(16, 16), 0.25f, 0, 0);
    spriteBatch.Draw(testTexture, new Vector2(155, 24), null, Color.White, 1, new Vector2(16, 16), 0.25f, 0, 0);

    spriteBatch.End();

Note the use of SamplerState.PointClamp, which turns off the antialiasing SpriteBatch would normally apply by default.

Resulting image:

Zoomed 4x:

This has almost too many aliasing problems to mention! Some that I find particularly bothersome are:

The black diagonal lines have pieces missing in the full size rotated image
The half size non rotated image has lots of problems:

The green vertical line, and also the red and blue horizontal lines, are entirely missing
It ended up with just two rather than three sets of black diagonal lines
The black border remains on the bottom and right, but is missing on the top and left

The two quarter size images are entirely different:

Non rotated version has only a blue line, no red or green at all
Rotated version has scattered red and green pixels, but no blue
Imagine how horrible it would look if we animated this sprite spinning, as it would flicker back and forth between different colors!

Remember how multisampling smooths triangle edges but does not affect their interior? We can confirm this by turning on 4x multisampling, and noting how the only difference is smoother borders on the rotated images:

With 4x supersampling, on the other hand, texture aliasing is indeed reduced:

But this is still far from perfect. The full size rotated and half size non rotated images look pretty nice, but the half size rotated and both quarter size versions have flaws. We'd still get nasty color pulsation if we animated a rotation of that quarter size version. This is because 4x supersampling only gives a 2x improvement in sampling frequency along each of the horizontal and vertical axes. That can reduce aliasing, but is not enough to keep us above the Nyquist threshold if we transform the texture by a factor of more than 2x.

Whatever is a poor graphics programmer to do?

To start with, we shouldn't have made life difficult for ourselves by specifying point sampling! If we turn off supersampling and multisampling, then change our SpriteBatch.Begin call to use the default SamplerState.LinearClamp, bilinear filtering produces a much nicer image than the point sampled version we started out with:

Unlike multisampling and supersampling, texture filtering does not smooth the border of the rotated images, but it does a nice job to reduce aliasing inside our full size rotated and half size non rotated images. Bilinear filtering lets us down in the same places as supersampling. Because the GPU only takes four filter taps per texture fetch (two horizontal and two vertical), we get 2x more headroom before we will run into aliasing problems, but a 2x improvement cannot entirely eliminate the Nyquist threshold, so our quarter size images remain nasty.

The solution is to combine bilinear filtering with precalculated mipmaps (plus anisotropic filtering if you can afford it). No matter how small the texture is scaled, the GPU can now simply select the appropriate mip level to sample from, always remaining just below the Nyquist threshold regardless of what transforms are applied.

With mipmaps enabled, even our smallest images now keep the same color intensity and hue, with no stray pixels or random changes of shape, so we can animate our sprite rotating or scaling with no aliasing problems at all:

Multisampling

2011-04-27T22:51:00Z

Multisampling is a compromise for people who really want to use supersampling, but can't afford it.

The idea is simple: instead of increasing the resolution for all rendering, what if we do triangle rasterization and depth/stencil tests at the higher resolution, but leave pixel shading and texture lookups at the original, lower resolution?

Where standard rendering goes like:

For each final output pixel covered by a triangle:
- Run the pixel shader
- Perform the depth test
- Write the pixel color

And supersampling is:

For each high resolution supersampled pixel covered by a triangle:
- Run the pixel shader
- Perform the depth test
- Write the pixel color
After all geometry is drawn, downsample the high resolution image to the final size

The process for multisampling is:

For each final output pixel covered by a triangle:
- Run the pixel shader
- For each high resolution multisampled pixel covered by the intersection of the triangle and the current output pixel:
  - Perform the depth test
  - Write the pixel color
After all geometry is drawn, downsample the high resolution image to the final size

Unlike supersampling, which can be implemented by drawing to a standard rendertarget and using a pixel shader to apply the final downsize filter, multisampling requires dedicated hardware support. In XNA, it is enabled by adding this to your Game constructor:

    graphics.PreferMultiSampling = true;

Because triangle rasterization and depth testing are performed at the higher resolution, multisampling is every bit as good as supersampling at combating triangle edge and geometry aliasing. But because the pixel shader only runs once per final output pixel, it does not help at all with texture map or shader aliasing.

This is an important and easily missed point: multisampling only knows about the edges of polygonal geometry.

Multisampling can smooth the edges of triangles, and also the edges formed where one zbuffered triangle intersects another, but it knows nothing about what happens within the interior of each triangle. Texturing, shading, and lighting produce exactly the same results as if multisampling was not used at all (think about it: the pixel shader runs just once, then we write out 2 or 4 copies of the same color, after which the downsample filter averages these identical colors, producing the exact same value we started with). If your triangles have interior borders caused by texture lookups or shader code (for instance the border of an alpha cutout sprite), multisampling will be irrelevant. This often surprises people when they see aliasing on cutout sprites and turn on multisampling in an attempt to fix it, but nothing changes. Yet this is the nature of the beast. If you want to antialias alpha cutout borders within a triangle, you need supersampling, or one of the texture/shader based techniques I will talk about later.

So why is multisampling popular? (and it is very popular, to the extent where many people confuse the generic term "antialiasing" with the specific technique "multisampling")

Simple: it's cheap. On some hardware (notably Xbox 360) it can be very cheap indeed.

Remember that the GPU is an asynchronous parallel processing pipeline. Multisampling increases the cost of some stages along this pipeline (notably rasterization, depth/stencil testing, and framebuffer writes), but it does not affect the areas that are most often performance bottlenecks (vertex fetch, vertex shading, texture fetch, and pixel shading). Adding work to things that were not the perf bottleneck can sometimes even be entirely free, so multisampling often turns out to improve visual quality for low cost.

Even if you are bottlenecked by framebuffer bandwidth, hardware designers are clever and can pull all sorts of neat silicon tricks to make multisampling efficient, taking advantage of the coherency where the same color value is usually written many times in a row. Why waste memory bandwidth saying "write X, ok, write X again, and again, and one more 'gain", when you could send just a single copy of X over the bus, followed by a couple of bit flags indicating which multisamples this pixel shader result should cover?

Oh yeah, before I go I should show you how it looks. Here's our favorite tank model, first with no antialiasing, then using 4x multisampling:

And the same images zoomed in:

Supersampling

2011-04-27T00:14:25Z

Supersampling is the simple, brute force approach to antialiasing computer graphics.

In order to avoid aliasing, the Nyquist theorem says we must take at least twice as many samples as the highest frequency detail in our input signal. So how about we just render our scene at a really, really high output resolution?

Of course, we may not want our final image to be at such a silly high resolution. It is no good if we end up with more pixels than our screen is capable of displaying! So once we have our beautiful, high resolution, alias-free image, we shrink it down to the final output size, using a high quality filter to maximize image quality.

Here is an example model, first rendered at 64x64 with no antialiasing, and then rendered at 256x256 (16x supersampling) before shrinking down to 64x64 using the "Best Quality" image resize filter in Paint.NET (if you were doing this on the fly in a game, you could use a pixel shader to apply a similar high quality scaling filter):

And the same images zoomed to show more detail:

Because it increases the resolution for all rendering operations, supersampling addresses many different kinds of aliasing in one fell swoop:

Triangle edge aliasing
Geometry aliasing
Texture map aliasing
Shader aliasing

In fact the only common aliasing problem that supersampling does not help with is temporal (time based) aliasing.

The problem is cost. Even if you only double the horizontal and vertical resolution (giving 4x supersampling), you now have four times as many pixels to render. Four times as many texture fetches and pixel shader computations, not to mention four times the amount of framebuffer and depth buffer memory, leaves your GPU performing at roughly quarter speed. And that's just for 4x supersampling, which is nowhere near enough to get rid of all geometry, texture, and shader aliasing.

Remember that pesky Nyquist theorem? To avoid aliasing, it is important to consider the ratio between the maximum and minimum scale at which a signal can be sampled:

Consider a texture map, such as the side of a building
How close is the player likely to get to the building?
To keep the graphics looking crisp, we want our texture to be high enough resolution to remain detailed when sampled at this maximum scale
Now the player starts to back away from the building
The texture shrinks in size, ie. is sampled at a lower frequency
After a while, it will be sampled at too low a rate, below the Nyquist threshold, so aliasing will occur
Supersampling to the rescue!
We turn on 2x supersampling, so the aliasing goes away
But the player continues to back away from the building
When the texture reaches half the scale at which we previously saw aliasing, the problem returns

It is common for objects to change size by a factor of 100 or more as you move around the world. But it would be wildly impractical to increase our rendering resolution by 100x in both width and height, as this would increase the GPU pixel workload by a factor of 10,000!

For this reason, supersampling is not widely used, and hence this series of articles is not over. But it is an important starting point for understanding other more advanced antialiasing techniques.

One place you probably have used supersampling is if you ever connected an Xbox 360 to a standard definition TV. Most Xbox games will continue to render at an HD resolution such as 1280x720, relying on the hardware scaler to shrink the resulting images to the output video resolution. That's supersampling, right there! Thanks to the high quality scaling hardware, those extra high resolution pixels are not wasted, but instead used to create a nicely antialiased 640x480 image.

Another place some games use supersampling is when taking screenshots for marketing materials. Internal builds of MotoGP included a special mode that would render the same scene many times using different projection matrices, combining literally hundreds of 640x480 tiles to build up a massive 16384*16384 screenshot image, which we would then downsample to a more sane resolution in Photoshop. Cheating? Kinda. But it was the normal in-game rendering engine and shaders, using the regular in-game models and textures, running on the actual Xbox hardware. Yet the resulting images were so nicely antialiased, they looked great when printed on a giant poster.

How to resample a signal without aliasing

2011-04-21T01:19:00Z

My previous post described how resampling a signal can cause aliasing problems. The worst problems occur when dramatically reducing the number of samples used to represent a signal, or when the source includes lots of high frequency detail. Specifically, there is a magic value called the Nyquist frequency, which is half the rate at which are you taking output samples. If the source signal contains information with a higher frequency than this threshold, you will have aliasing problems.

To put this another way: in order to avoid aliasing, you must take at least twice as many output samples as the finest detail in your input signal.

That leaves us with basically just two ways to avoid aliasing:

Take more output samples
Or have less fine detail in the input signal
1. Smooth (aka. blur) the input data to remove fine detail
2. Or smooth (aka. filter) on the fly as we read our sample values

Option 2.1 can often be applied to the input data as a preprocess, which makes it very efficient. But this is no good if we need to sample the data at different frequencies depending on the situation! (for instance textures often need to be scaled by different amounts depending on distance from the camera). If we pre-smooth our input data according to the lowest frequency we will ever sample it at, the result will be excessively blurry when sampled at higher frequencies. Or if we pre-smooth to match a higher frequency, we will still have aliasing when sampling at the lower rate.

Option 2.2 can dynamically adjust to different sampling frequencies, but tends to be expensive to implement, as it must average many different samples from slightly different locations in the input.

A third option is to declare this whole digital sampling business a mug's game and refuse to play at all. In some situations it is possible to work entirely with mathematical equations, transforming one signal into another by applying mathematical transformations to the equations which describe them. This approach inherently avoids digital approximation, so will not produce any aliasing, but the math tends to get very complex. It is not widely used in realtime computer graphics, but many offline renderers (eg. RenderMan) work this way.

Ok, that's enough theory. Next, let's get practical...

Why sampling a signal causes aliasing

2011-04-21T00:56:48Z

The math behind digital sampling and filtering is fascinating, complex, and full of arcane terms like Nyquist frequency. But I'm barely a good enough mathematician to understand it, let alone try to explain it here! This post is my attempt to describe aliasing as it applies to computer graphics via overgeneralized hand waving.

Most of the important operations involved in rendering graphics can be boiled down to digitally sampling a signal. If this phrase is new to you, don't panic! A signal just means a value that changes as you move around some coordinate space (which can be 1D, 2D, or occasionally 3D or more). Common types of signal used in graphics are:

A texture image, the color of which changes as you move to different 2D locations within that image
A shader lighting function, the brightness of which changes as you alter the angle of the light
The edge of a triangle, the position of which changes as you move along the edge
The position of a moving object, which changes as you move through time

Signals can sometimes be described by a mathematical equation, but they are more commonly represented as a series of digital samples, ie. an array which stores the value of the signal for many different coordinate locations.

<digression>

People often claim that the real world uses continuously varying analog signals, but when you get down to the quantum level it is actually all digital samples! Subatomic particles are entirely discrete. Photons are either there or not there, so the brightness of a light can never involve a fractional number of photons. Things only appear continuous because these particles are so small. Reality is pixelated, just at a ridiculously high resolution :-)

</digression>

Sampling occurs whenever we wish to transform one signal into another, for instance:

To rasterize a triangle, we turn the mathematical description of its edge into an array of framebuffer pixels
To map a texture onto this triangle, we turn the array of samples which makes up our texture map into a different array of framebuffer pixel colors
To light that triangle, we turn a mathematical lighting equation into a different brightness value for each pixel that the triangle covers

Although the implementation tends to be heavily optimized, all forms of sampling work basically the same way:

The output signal is defined as an array of digital sample values
For each element in the output array, find the corresponding location in the coordinate space of the input signal
If the input signal is a mathematical equation, evaluate it at that location
Or if the input is a series of digital samples, look up the stored value at that location

Easy, right? But this basic operation is where pretty much every kind of aliasing comes from.

Example time. Consider this 1D signal, stored as an array of 512 digital values:

Let's convert this signal to an array of just 64 values, by taking evenly spaced samples every 8 entries through the original. Note that there is no requirement for our samples to be evenly spaced. That makes it easy to visualize, but if we were for instance mapping a texture onto the side of an object rendered with a 3D perspective view, the relationship between input and output samples could be a more complex curve function.

This resampling produces a new signal with the same basic shape as the original, but less detail:

It looks ugly and blocky, but that is actually a made-up problem caused by the fact that after shrinking my 512 sample signal to just 64 samples, I scaled back up to 512 before displaying the above image. If I displayed the downsampled signal at its native 64 pixel width, there would be no such blockiness.

If I did for some reason need to shrink the signal to 64 samples and then scale back up to 512, I could do that scaling by interpolating between values rather than just repeating them. This is called linear filtering (the previous example used point sampling) and it produces an image that looks pleasingly similar to our original, albeit with less fine detail:

Here's where it gets interesting. Look what happens if we reduce the output signal to just 16 samples:

Then 8:

And finally 6:

Whoah! How come 8 samples has a dip followed by peak toward the right of the signal, but the 7 sample version is almost flat, while the 6 sample version has a peak followed by dip, almost the exact opposite of the 8 sample version?

The problem is that when we are taking so few samples, there just aren't enough values to accurately represent the shape of the original signal. It ends up being basically random where in the signal these samples happen to be taken, so our output signal can change dramatically when we make even small adjustments to how we are sampling it. When reducing a signal to dramatically fewer samples than were present in the original, the result tends to be meaningless noise.

Aliasing can be a problem even when you are not dramatically reducing the number of samples. Consider our original 512 sample signal, which includes a lot of small, high frequency jitter. Then consider the 64 sample version, which has the same basic shape but without that fine detail. This looks fine as a still image, but what if were to animate it, perhaps sliding the curve gradually sideways? Now each frame of the animation will be sampling from slightly different locations in the original signal. One frame our sample location may randomly happen to be at the top of one of those little jitters, then the next frame it could be at the bottom. The result is that our output signal randomly jitters up and down, in addition to sliding sideways!

This is a common characteristic of aliasing problems. In extreme cases they can make even static images look bad, but more often, subtle aliasing may look fine when stationary yet will flicker or shimmer whenever the object or camera moves.

Fun way to see an extreme example of this in action:

Download this image and load it into Paint.NET
Select Image / Resize
Choose Nearest Neighbor resampling mode
Scale to 80%
See that crazy ripple pattern?
Undo
Now resize to 75%
Another, totally different ripple pattern!
Imagine how horrible this would look if we were rendering an animation of this texture shrinking in size as it receded into the distance...

Up next: ways to avoid aliasing when resampling a signal.

Antialiasing

2011-04-20T20:04:09Z

I've been meaning to write about antialiasing for a while, but now I sit down to do that I realize I have too much to say for a single article. So this post is the introduction to a series.

Antialiasing is one of the most important yet least widely understood areas of computer graphics. If I had a penny for every time I heard the developer of a 2D game say "I turned on antialiasing but my sprites still look jaggy", well, I'd be up to six or even seven pennies by now!

The thing is, "antialiasing" is really too vague a term to mean anything at all! The important word is "aliasing", which is surprisingly hard to pin down. Dictionary.com gives two definitions:

Jagged distortions in curves and diagonal lines in computer graphics caused by limited or diminished screen resolution.
Distortion in a reproduced sound wave caused by a low sampling rate during the recording of the sound signal as digital information.

These are both examples of aliasing, but really just special cases of a more generic underlying meaning:

Artifacts created when a source value (which can be either analog or digital) is replaced by a digital approximation.

We perform such approximations in many places when rendering computer graphics:

We approximate the shape of arbitrary objects as a list of triangles
We approximate the shape of a triangle as a grid of dots (screen pixels)
We approximate arbitrary images as grids of dots (textures)
We frequently approximate one grid of dots as another different grid of dots (scaling images, rotating, or mapping them onto 3D geometry)
Our shader programs use many digital approximations, as varied as the things for which we use shaders (ie. basically infinite)
We approximate moving objects as a series of static images (animation)

Any or all of these approximations can cause ugly aliasing artifacts. Antialiasing really just means "a technique used to avoid or cover up an aliasing problem". Since there are many different kinds of aliasing, and many techniques to overcome each of them, it should be no surprise that there are many, many different forms of antialiasing. And of course, they only work if you choose an antialiasing technique that matches the specific kind of aliasing you were suffering from in the first place!

Ok, that was kinda dry. Next up, more theory. Then after that, some practical examples.

C++	16
How GPU’s work	11
3D math	10
Game design	10
SIMD optimization	3