The effect of dithering in a three-dimensional game

The creator of Papers, Please, Lukas 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 with the help of the dithering effect.

First, a brief explanation: Obra Dinn performs internal rendering in an 8-bit palette in grayscale, and then at the post-processing stage converts the final output data to 1-bit values. Conversion from 8-bit to 1-bit color is performed by comparing each pixel of the original image with the corresponding point in the dithering tile pattern. If the pixel value of the image 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 of them.


Transforming the original image according to the dithering pattern

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

Bayer / Blue Noise

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

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


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


Try to focus on any object while it is moving, and you will understand what the main problem Obra Dinn is in full screen. There are ways to fix this, and most often they come down to "this style does not work, replace it." I’ve come pretty far on this path, experimenting with different styles, but then I went back and asked myself the question — maybe you shouldn’t let these gadish pixels get in my way.

Stabilize dithering

To give your eyes the best opportunity to recombine everything, dithering is best used with points of dithering patterns that have a 1: 1 correlation with output pixels. But if there is a “only” correlation with the output data, then when applying post-effects to the scene, 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 seem stable when moving along with the rest of the scene.

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

Texel space

My first attempt was to impose a dithering pattern on a texel space. This is analogous to dithering the textures of objects during scene rendering, instead of performing post-processing of an 8-bit output image. I didn’t expect it to work, but I still wanted to see what the overlay would look like perfectly.


Texel space dithering pattern

Well, in general, the expectations were justified. The overlay on all objects is done differently, so the scales of 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 distortions, and for dithering patterns it is not as easy to perform mip-texturing or filtering as for traditional textures. However, we will bring this to the end:


Everything is not so bad - the pattern is not bad tied to the geometry. Distortion creates its own floating effect, and unifying or scaling the overlay will not help. Texels change their size depending on the distance to the camera, so there will always be pixels of the dithering pattern, which when resampling on the screen will be horribly distorted.

Movement deformation

If I wanted the dithering pattern to track the movement of geometry under it, then why not just deform the pattern based on the change in position of each rendered pixel in the scene? Indeed, why not 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 along with the scene. If the pixel of the scene was not present in 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 camera movement, and not individual objects.


It was a pretty “quick and dirty” attempt, but some facts became obvious. Firstly, it works in some way. Secondly, the dithering pattern needs to be taken into account by its neighbors — it cannot simply be individual pixels. If we consider each pixel separately, as is done in this method, then it is obvious that we will get gaps and distortions in the pattern. In this test scene, I moved the camera to show it with the chest as an example. Looking at the distorted dithering pattern itself, it is easier to notice.


These gaps arise due to the different depth of the pixels and the selected thresholds. I was thinking about a complex system for correcting a problem based on tracking areas, averaging their depth and shifting all points of the dithering pattern in each area to the same value. Gaps along the boundaries of areas can be hidden by a sharp change of lighting or wire-frame line. This would not have been possible due to the fact that the game used colored areas to generate model frameworks. When I started to implement all of this, I first missed the depth in the equation, which gave me a much simpler alternative:

Offset overlay

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

DitherOffset = ScreenSize * CameraRotation / CameraFov 

In essence, this expresses what I wanted: the shift of the dithering pattern superimposed on the screen by exactly one screen when the camera is rotated by one viewing area. This keeps the 1: 1 overlay with the screen, but it also takes into account the simplified transformation of the apparent geometry of the scene. In fact, this only corresponds to the movement in the center of the screen, but, to my happiness, it looks quite good.


Note: it seems that the dithering pixels of the chair basically move with geometry. The same applies to the realm. Planes that are more perpendicular to the field of view are not displayed very well - the floor still looks chaotic.

Although the approach is not perfect, a simple shift of the dithering superimposed on the screen retains 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 it. Being engaged in erasure of the code and commits, having released one or two posts in the devlog, I still could not get rid of the thought of a perfectly stuck dithering:

World Space - Cubic Overlay

Previous experiments have shown that any correlation between the dithering pattern and the scene geometry should ignore the depth information received from the scene. In practice, this means that the dithering can be attached to the geometry during the rotation of the camera, 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 around the ship, stops and looks at the objects. When walking on the screen, there are so many changes that the floating dithering is not particularly obvious.

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


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


View from camera looking to the corner. The scale of the overlay for clarity increased.

Laying a cube works well when you look at the sides, but not so well when the camera is pointing at an angle. The dithering pattern is still perfectly captured in 3D space when you rotate the camera. Even with rough checks, the result looks promising.


The case finally moved. Due to the fact that it is a post-processing, this approach is more general than the imposition in the space of texels, which is good. The problem now comes down to a concrete cubic overlay. When ideally overlapping, one texel on a cube always corresponds to one pixel on the screen, regardless of the rotation of the camera. For a cube this is impossible ...

Space of the world - 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 took time. There is no way to perfectly pitch a sphere with a square texture. It would be possible to redefine the dithering matrixes through a grid of hexagons or something similar, which well tones the sphere. Perhaps it would have, but I did not try. Instead, I “hacked” the tiling of the sphere, achieving a careful adjustment so that the “ring” imposition of the original dithering pattern gave good results.


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


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


This is still the best of my results. There are several tradeoffs:

1. The points of the dithering pattern become larger and less effective around the edges of the screen.
2. The pattern is not aligned in the top-bottom-left-right directions for most camera turns.
3. The output is no longer 1-bit due to the final decrease in resolution.

But the benefits are very great:

1. Dithering perfectly attaches to all camera turns. In the game, it feels a bit strange.
2. The discomfort of floating dithering completely disappeared, even in full screen mode.
3. Pixel style of game is saved

You can completely get rid of deficiency 3 by again limiting the output to 1-bit values ​​using a simple threshold of 50%. The result is still better than without supersampling (three examples for comparison are presented below).

Summarize

It seems a bit strange to spend 100 hours on something that they will not even notice. No one really thinks "damn, yes this dithering is hellishly stable, it's some kind of magic." But I didn’t want people to have problems that should have arisen, so they should have been fixed.

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

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

ANALOG - fullscreen superimposed dithering on the sphere, a smoothed output.