The effect of dithering in a three-dimensional game

The creator of Papers, Please Lucas Pope is working on a new three-dimensional project Return of the Obra Dinn, in which he tries to recreate the feeling of an old book using the dithering effect .

To begin with a brief explanation: Obra Dinn internally renders everything in an 8-bit palette in grayscale, and then at the post-processing stage converts the final output into 1-bit values. Conversion from 8-bit to 1-bit color is performed by comparing each pixel in the source image with the corresponding point in the dithering tile pattern. If the image pixel value is greater than the value of the dithering pattern point, then the output bit is assigned the value 1, otherwise it is 0. The output data is simplified to 1-bit values, and the viewer's eye combines the pixels, approximating more bits from them.


Converting the source image using a dithering pattern The

two components of this process are the source image and the dithering pattern. In various cases, Obra Dinn uses two different patterns: an 8x8 Bayer matrix for a smoother hue range and a 128x128 blue noise field for less ordered output.


Bayer / blue noise

The result is inside the engine without wireframe lines. Bayer on the sphere, blue noise on everything else.

The classic dithering process works great for still images and looks much worse on moving and animated images. When the original image changes frame-by-frame, the static dithering pattern and low-resolution output become a serious problem. What should be solid shapes and shades turns into a shimmering chaos of pixels.


Today, dithering is mainly used for static source images or for high resolution output. The first thing you think when looking at this floating effect of dithering is not “yes, that’s how dithering works”, but “what is this twitching effect and how can I turn it off”.


Try to focus on some object while it is moving, and you will understand what the main problem of Obra Dinn is in full screen mode. There are ways to fix this, and most often they come down to "this style does not work, replace it." I went quite a long way along this path, experimenting with different styles, but then I went back and asked myself a question - maybe you shouldn't let these bastard pixels bother me.

We stabilize dithering

To give the eyes the opportunity to recombine everything in the best way, dithering is best used with dithering pattern points that have a 1: 1 correlation with output pixels. But if there is a “only” correlation with the output, then when applying scene post-effects there will be no connection between the rendered geometry and the threshold pattern. In each frame, the moving elements of the scene will have a new threshold value. Instead, I want the dithering pattern to be “glued” to the geometry and appear stable when moving along with the rest of the scene.

This is where the overlay problem arises. There is a conflict between the “perfect” overlay of the dithering pattern (1: 1 with the screen) and the perfect overlay on the scene (x: 1 with the geometry), so you need to be prepared to compromise. Most of my work is devoted to superimposing the input dithering pattern on different spaces, which ensures the best match of the pattern with the geometry of the scene. Here everything is done at the stage before setting the thresholds.

Texel space

My first attempt was to impose a dithering pattern on the texel space. This is similar to dithering object textures during scene rendering instead of post-processing an 8-bit output image. I did not expect this to work, but I still wanted to see how the overlay would perfectly match the scene.


Dithering pattern in texel space

Well, in general, expectations have justified themselves. The overlay on all objects is performed differently, so the scales from the patterns do not match. They can be unified. But the real problem is distortion. Any resampling from one space to another will lead to distortion, and for dithering patterns it is not so easy to perform mip-texturing or filtering as for traditional textures. However, we bring it to the end:


Everything is not so bad - the pattern is well attached to the geometry. Distortion creates its own floating effect, and unifying or scaling the overlay does nothing to help. Texels change size depending on the distance to the camera, so there will always be pixels of a dithering pattern that, when resampled on the screen, will be terribly distorted.

Movement strain

If I wanted the dithering pattern to track the movement of the geometry underneath, then why not just deform the pattern based on the change in position of each rendered pixel in the scene? Indeed, why not give it a try. This is a bit like motion blur, in which each pixel tracks its movement relative to the previous frame. In this case, I update the dithering texture so that its pattern moves with the scene. If the scene pixel was not present on the previous frame, then the dithering pattern is reloaded in it. The implementation of this technique was greatly facilitated by the static nature of the game - I had to worry about the movement of the camera, and not individual objects.


It was a rather “quick and dirty” attempt, but some facts became apparent. Firstly, it works in some ways. Secondly, the dithering pattern needs to be taken into account by neighbors - it cannot just be individual pixels. If we consider each pixel separately, as is done in this method, it is obvious that we will get gaps and distortions in the pattern. In this test scene, I moved the camera to show this with the example of a chest. By looking at the distorted dither pattern itself, it’s easier to notice.


These gaps occur due to different pixel depths and selected thresholds. I was thinking of a complex system for fixing the problem based on tracking areas, averaging their depths and shifting all points of the dithering pattern in each area by the same value. Gaps along the boundaries of the areas can be hidden by a sharp change in lighting or a skeleton line. This could not be realized due to the fact that the game used colored areas to generate model wireframes. When I started implementing all this, I first missed the depth in the equation, which gave me a much simpler alternative:

Screen overlay with offset

When compiling equations for deformable dithering, a very simple transformation fell out of them:

DitherOffset = ScreenSize * CameraRotation / CameraFov

In essence, this expresses what I wanted: shifting the dithering pattern superimposed on the screen exactly one screen when the camera rotates one view area. This saves a 1: 1 overlay with the screen, but it also takes into account the simplified transformation of the visible geometry of the scene. In fact, this corresponds only to the movement in the center of the screen, but, to my happiness, it looks pretty good.


Note: It appears that the dithering pixels of the chair mostly move with geometry. The same applies to the field. The planes more perpendicular to the field of view are not displayed very well - the floor still looks chaotic.

Although the approach is not ideal, a simple shift of the dithering superimposed on the screen preserves the overall pattern and movement of the scene, so that it is more convenient for the eye to track together. I was very pleased with this. Pursuing code cleanup and commits, releasing one or two posts in devlog, I still could not get rid of the thought of perfectly sticky dithering:

World Space - Cubic Overlay

Previous experiments have shown that any correlation between a dithering pattern and scene geometry should ignore the depth information received from the scene. In practice, this means that dithering can be attached to the geometry during camera rotation, but not its movement. This is not so bad for Obra Dinn, given the slow pace of the game and the observant role of the player. Usually in the game he walks the ship, stops and looks at objects. When walking on the screen, there are so many changes that floating dithering is not very obvious.

With this in mind, my next attempt was to impose a dithering pattern on the geometry indirectly, by first rendering the pattern on the sides of the cube centered around the camera. The cube moves with the camera, but remains oriented relative to the world. It turns out a mixture: a little screen, a little scene.


The dithering pattern is superimposed on a cube centered on the camera.


The view from the camera, looking at the corner. Overlay scale for clarity increased.

Overlaying a cube works well when you look at the sides, but not so well when the camera is angled. The dithering pattern is still perfectly fixed in 3D when the camera is rotated. Even with rough checks, the result looks promising.


The case finally moved. Due to the fact that this is post-processing, this approach is more general than overlapping texels in space, which is good. The problem now boils down to a specific cubic overlay. With perfect blending, one texel per cube always corresponds to one pixel on the screen, regardless of camera rotation. For a cube, this is impossible ...

World Space - Spherical Overlay

... but thanks to the sphere, I got close enough.


Imposing a dithering pattern on the inside of a sphere The

search for this particular spherical overlay required a certain amount of time. There are no methods for perfect tiling a sphere with a square texture. It would be possible to redefine the dithering matrices through a grid of hexagons or something similar, which well tilts the sphere. It might have worked, but I have not tried. Instead, I “cracked” the tiling of the sphere, having carefully tuned it so that the “ring” overlay of the original dithering pattern would produce good results.


Better than with a cube, but still a lot of distortion. The size of the spherically superimposed point is very similar to the size of the screen pixel - it differs just enough to create moire. I felt that I was close to a solution, and it’s very easy to correct such distortions using supersampling: apply the dithering threshold at a higher resolution, and then lower it.


Spherically superimposed dithering pattern at 2x magnification and resolution reduced to 1x


This is so far the best result I have received. There are several tradeoffs:

1. Dithering pattern points become larger and less efficient at the edges of the screen.
2. The pattern is not aligned in the directions “top-bottom-left-right” for most camera turns
3. The output is no longer 1-bit due to final resolution reduction

But the benefits are very great:

1. Dithering is perfectly attached to all camera turns. In the game, this feels a little strange.
2. The discomfort from floating dithering completely disappeared, even in full screen mode.
3. Pixelated gameplay style maintained

Deficiency 3 can be completely eliminated by again limiting the output to 1-bit values ​​with a simple threshold of 50%. The result is still better than without supersampling (below are three examples for comparison).

To summarize

It seems a little strange to spend 100 hours on something that you won’t even notice the absence of. No one will definitely think "damn it, but this dithering is hellishly stable, it's some kind of magic." But I did not want people to have problems that should have arisen, so they were worth eliminating.

Offset overlay in screen space works best at 1x and spherical overlay at 2x. The whole scene is now rendered in 800x450 resolution (raised resolution from 640x360), which increases legibility, without sacrificing low-res style. In the finished game there will be two display modes:

DIGITAL - dithering in the screen space with an offset, 1-bit output.

ANALOGUE - full-screen dithering superimposed on the sphere, smooth output.