technical

warning: Creating default object from empty value in /home/mimec/www/modules/taxonomy/taxonomy.module on line 1418.

Adding glow lighting to a voxel world

This is a continuation of the previous article in which I described the ambient occlusion shading algorithm implemented in Mister Tins. This time, instead of adding shadows, I will add some lighting to the scene. But before I start, I'd like to make a few clarifications:

  • The term "glow lighting" in this article refers to a subtle tint which is added to the ambient light of blocks near a colored light source. It should not be confused with the halo or bloom effect, in which bright objects have a fringe of light around them.
  • Mister Tins uses ambient light only, without explicit point or directional light sources. It means that glow lighting only adds subtle effects to the scene and doesn't affect which objects are bright or dark. However, similar effect can be used to create scenes in which the intensity of the glow light is comparable to or higher than the ambient light.
  • Just like in case of the ambient occlusion algorithm, my goal was not to recreate any physical phenomena; those can be simulated using complex global illumination algorithms, such as radiosity. The goal was to create something that achieves best looking results and that can be easily understood and manipulated.

Let's start with an illustration:

GlowLighting

The bottom part of the image was rendered with glow lighting; the top part without. The effect is subtle, but you should see a yellow glow around the trigger on the left (occupied by a box), green glow around the two triggers on the right and blue glow near the exit on the edge. The glow effect only affects the nearest floors and walls.

Because the world in Mister Tins consists of blocks (voxels), the algorithm which calculates the intensity of glow light is quite similar to the one that Minecraft uses for lighting. A quick reminder: each block in Minecraft has a light level ranging from 0 to 15. Each light source (e.g. lava or torch) has a certain light level, and the light propagates to neighboring transparent blocks, decreasing by one level per each block. The important thing is that light from multiple sources is not additive, i.e. when a block is located near two or more light sources, it gets its light level from the nearest and/or brightest one. Simply put, adding one torch next to another other doesn't make the nearby blocks twice as bright. Also, the perceived brightness decreases exponentially, so light level 14 is 0.8 times as bright as 15, and 13 is 0.8 x 0.8 = 0.64 times as bright, etc. Finally, even though the light level is calculated per-block, it is then averaged for each vertex, so the lighting is smooth.

The same rules apply to Mister Tins, except that the range of the light is much shorter and it attenuates faster. A light source block (e.g. a trigger) gets a light level of 4. Then, each block gets the light level of its brightest neighbor minus one. Conceptually it's easy but an efficient non-recursive algorithm may be difficult to come up with. This stackexchange answer describes roughly what I used in Mister Tins.

But wait a minute… light sources in Mister Tins have different colors. Consider a scenario in which they are close to one another:

GlowLightingBlend

Note that the effect in this screenshot is slightly exaggerated. You can see that the colors nicely blend together, but how can this be achieved if each block only gets its light level from the single brightest neighbor? Again, Minecraft comes as a useful inspiration. Each block really has two light levels; one coming from the sky, the other from other sources. This makes it easy to implement the day/night cycle and make the moonlight blueish, while the light coming from torches etc. is more yellow.

In case of Mister Tins, I decided to calculate the light level separately for each possible color of the light source, because there are only a few of them (if the colors were completely arbitrary, a possible workaround would be to calculate the light level for the red, green and blue components separately). Then, for each block, the algorithm calculate the maximum light level, taking into account all colors, in order to determine the effective light intensity. It also calculates a weighted average of the colors (remembering about the exponential relation between the light level and actual brightness) in order to determine the effective color. Finally, the maximum light intensity is multiplied by the average color. Here's the corresponding code snippet:

int blendLights( int* lights )
{
    static const Color colors[ 6 ] = {
        Color( 0.76f, 0.71f, 0.20f ), Color( 0.34f, 0.72f, 0.20f ), Color( 0.58f, 0.15f, 0.63f ),
        Color( 0.96f, 0.21f, 0.10f ), Color( 0.04f, 0.79f, 0.98f ), Color( 0.65f, 0.67f, 0 )
    };

    Color color;
    float sum = 0, max = 0;

    for ( int i = 0; i < 6; i++ ) {
        int light = lights[ i ];
        if ( light > 0 ) {
            float weight = std::pow( 0.5f, 4 - light );
            color += weight * colors[ i ];
            sum += weight;
            if ( weight > max )
                max = weight;
        }
    }

    if ( sum > 0 ) {
        Color blended = 0.2f * max * color / sum;
        return blended.RGBA().v;
    }

    return 0;
}

The lights input parameter is the array of light levels for each type of light source. The return value is the final color. The colors[] table defines the color of each type of light source, 0.5 is the attenuation factor and 0.2 is the intensity of the glow effect.

In order to achieve nice smooth lighting, the algorithm calculates the maximum light intensity of each vertex of a floor or wall face from the four adjacent blocks. Then the effective color is calculated for each vertex using the function presented above. That color is then simply added to each pixel in the pixel shader.

Tags: technical

Ambient occlusion: per-vertex vs. per-pixel

In Mister Tins there are no explicit light sources, so the only kind of light is ambient light. Without occlusion, this simply means the same amount of light everywhere, which is flat and unrealistic. Occlusion means that some of the ambient light is blocked by the nearby objects, so small enclosed areas and corners are slightly darker. The maths involved in this can be quite complex, but we have to keep in mind is that the goal is to make the scene look good, not to accurately model complex physical phenomena.

When I first implemented ambient occlusion in Mister Tins, I used the algorithm described in the 0 FPS blog post. The idea is to take each block face and assign a shade value from 0 (darkest shadow) to 3 (no shadow) to each of the four vertices. The shade value depends on the number of non-transparent blocks directly adjacent to the given vertex. The shade values are then interpolated across the entire face. The post also mentions that the interpolation depends on how the face is divided into triangles, which can lead to subtle artifacts.

I solved the interpolation problem by using a lookup texture which contains tiles with all possible combinations of shade values, with accurate bilinear interpolation. Out of 44 possible combinations of shade values, only 112 can occur in practice, and if we use rotation and/or mirroring, there are in fact only 26 unique combinations. As you can see below, the resulting texture is very small and can be used with a fast point sampler.

BlockShadesVertex

When generating scene geometry, the adjacency information for each face is encoded as an 8-bit integer, where each bit corresponds to one of the 8 neighbor blocks. That integer value is then used to look up the corresponding shading texture coordinates from a pre-calculated 256-element table. For example, in the picture below, the adjacency of the face in the middle can be represented as 20 + 21 + 22 + 24 = 23. According to the lookup table, this corresponds to the fourth tile in the second row in the image above.

AdjacencyEncoding

While using a lookup texture for something as simple as linear interpolation may seem like a bit of overkill, this allows changing the shading algorithm without adding any complexity to the vertex and pixel shaders. What looks best depends on the kind of scenes that are rendered. In a world consisting of lots of small voxels, it may be worth considering not only the adjacent blocks, but also some further surrounding. On the other hand, the world in Mister Tins consists of a small number of relatively large blocks, so the per-vertex ambient occlusion algorithm described above is not detailed enough. Thanks to the lookup texture, the resolution of the algorithm can be easily increased from per-vertex to per-pixel.

I came up with a different idea for calculating ambient occlusion: for each point on the face, calculate the distance to the nearest non-transparent block adjacent to the face. In the image below, the nearest block for point A is the one in the top-right corner, and for point B, it's the block below.

PointDistance

The closer the point is to another block, the darker it gets, and it doesn't have to be a linear relationship - in fact, a quadratic one gives better results. Again, the lookup texture can be pre-calculated; in this case, it contains only 14 unique combinations:

BlockShadesPixel

The following image compares both shading algorithms in practice:

AmbientOcclusion

The first part was rendered using the original per-vertex interpolation algorithm. You can see that the holes are filled with solid, dark shadow, and the corners between floors and walls are only slightly darkened.

The second part was rendered using the new per-pixel distance based algorithm. The shadows in the corners are much darker, but still the center of the hole is brighter than in the first method.

The third part of the image was rendered using a combination of both algorithms. It uses a single lookup texture with the per-vertex and per-pixel shadows blended together, resulting in 33 unique combinations. This is the algorithm that is used in Mister Tins since version 0.8.5.

Tags: technical

Top-Down perspective view

This is the first technical article in the series dedicated to Mister Tins.

One of the most distinctive features of Mister Tins is the top-down perspective view. Although the top-down view (also called overhead view) has been very common in video games since the 1980s, most games of that time used some sort of orthographic or oblique projection to simulate a three-dimensional effect using two-dimensional tiles and sprites. Examples include The Legend of Zelda series, the original SimCity, Bomberman series (also known as Dyna Blaster), racing games such as Badlands and its predecessors, and early real-time strategy games such as Dune II and Warcraft.

One of the first games which featured a top-down view with real perspective projection was Grand Theft Auto, released in 1997, and it's sequel, GTA2. The camera was placed directly above the player (or player's car), but you could see various sides of the buildings at different angles in a real three-dimensional view. Starting with the 2000s, the first person and third person perspective views became dominant in most types of games. Even the modern remakes of classic games, such as Sokoban, typically use some kind of angle view, so a purely top-down perspective view remains fairly uncommon.

There is a tendency to think that a top-down view is only good for representing flat, two-dimensional world, just like the side view is good for traditional, two-dimensional platformers. One of the few examples that break this stereotypes is Fez, in which a three-dimensional world is displayed in an orthographic side view like traditional platformers, opening a whole range of new possibilities. That inspired me to think about a three-dimensional world displayed in a top-down view, in which you can only see what's around you. Everything above is not visible and most of the things below are obscured by higher floors. This way you can explore new parts of the world by climbing up and down. This simple but innovative idea received a lot of positive feedback.

The top-down perspective view in Mister Tins is created by placing the camera directly above the player, looking down along the z axis, and positioning the near clipping plane slightly above the player's head:

Top Down View

Everything above the blue clipping plane is not visible. Obviously you should not be able to see the interior of the walls that are intersected by the clipping plane. To prevent this, additional faces (which I call "caps") are drawn at these intersections. They are marked with thick red lines on the picture above. They could be simply filled with black color, but some shading is added for a better effect, so that they become brighter near the edge and darker inside.

The problem with this approach is that if you jump up the stairs to reach the higher floor, a big part of the screen would suddenly turn black as the clipping plane hits the ceiling, and then would suddenly turn into floor's texture once the clipping plane is above the floor. To make this look better, smooth transitions are necessary when the clipping plane moves up and down. The cap is almost completely transparent when the clipping plane is located just above a non-solid block (i.e. just above the ceiling) and it blends into the floor's texture when the clipping plane is placed just below the floor.

The additional advantage of this solution is that you can see that you can reach the second stair even though its top face is located above the clipping plane, because it's blended with the dark interior. It also means that if the ceiling is only one block high, it's never filled with black color, it just fades smoothly from fully transparent to fully opaque floor texture. This gives a very nice effect when going up and down between various floors.

Tags: technical
Syndicate content