BUILD engine is the game engine behind Duke Nukem 3D, Shadow Warrior, Blood, and many other titles of the 90s. It was one of the most popular engines to be licensed third-party until the Unreal Engine.

Post tutorial Report RSS Cheap shadows

You just started making a 3D engine or a 3D engine mod. The renderings look nice, but there is something missing from your characters: shadows. There are many methods to put shadows in your characters, but here is one which won't need much more than a few minutes to implement :-).

Posted by on - Basic Client Side Coding

Introduction

Hello and welcome to my first tutorial in IndieDB. This tutorial is about a cheap method i'm frequently using to put shadows in dynamic 3D models. The method is very simple and as any simple method it has its drawbacks. However it is so easy to implement that it can be used even as a "placeholder method" for later when you add a more advanced method.

In a nutshell, the method is to just render your model a second time at ground level, vertically flattened using a solid (usually black) color. For some this might be enough, but i'm going to discuss it further :-P.

In this tutorial i will assume you use classic OpenGL (OpenGL 1.x or 2.x, not the cropped up 3.x or 4.x) with immediate mode. I make this assumption because it's easier to follow the code examples and it translates well to other APIs. Also i like classic OpenGL more than any other API (including modern OpenGL 3.x/4.x).

Solid Flat Shadows

Actually i lied a bit at the brief text: you'll only need a few minutes to implement the very very basic form of this, which while looks like real dynamic shadows, it doesn't look very natural in all places. Do not dismiss it however, some games actually do use this method. For example a (rather small) game i finished yesterday night, Prey: Invasion for the iPhone and iPod Touch, uses this method for character shadows.

So, what does it take to render these shadows? Simple: just modify your model rendering code to override the Y value (assuming your Y coordinates go "up"). Now lets assume your model rendering code looks something like

void render_model(model_t* model)
{
    glBindTexture(GL_TEXTURE_2D, model->texture);
    glBegin(GL_TRIANGLES);
    for (i = 0; i < model->triangles; i++) {
        triangle_t* tri = model->triangle[i];
        
        /* first vertex */
        glNormal3f(tri->normal1.x, tri->normal1.y, tri->normal1.z);
        glTexCoord2f(tri->s1, tri->t1);
        glVertex3f(tri->pos1.x, tri->pos1.y, tri->pos1.z);
    
        /* second vertex */
        glNormal3f(tri->normal2.x, tri->normal2.y, tri->normal2.z);
        glTexCoord2f(tri->s2, tri->t2);
        glVertex3f(tri->pos2.x, tri->pos2.y, tri->pos2.z);
    
        /* third vertex */
        glNormal3f(tri->normal3.x, tri->normal3.y, tri->normal3.z);
        glTexCoord2f(tri->s3, tri->t3);
        glVertex3f(tri->pos3.x, tri->pos3.y, tri->pos3.z);
    }
    glEnd();
}

Obviously this isn't the most performant code, but i'm trying to show the idea here. Ideally you will use a VBO or a geometry-only display list (the latter is at the time of this writing the fastest method to render stuff, at least in nVidia hardware).

To modify the above model rendering code to render shadows, you just have to ignore the Y values. So the function to render shadows will be based on the above function with a small modification

void render_model_shadow(model_t* model, float ground_y)
{
    /* do not use textures and use a black color */
    glBindTexture(GL_TEXTURE_2D, 0);
    glColor3f(0, 0, 0);
    
    glBegin(GL_TRIANGLES);
    for (i = 0; i < model->triangles; i++) {
        triangle_t* tri = model->triangle[i];
        
        /* first vertex */
        glVertex3f(tri->pos1.x, ground_y, tri->pos1.z);
    
        /* second vertex */
        glVertex3f(tri->pos2.x, ground_y, tri->pos2.z);
    
        /* third vertex */
        glVertex3f(tri->pos3.x, ground_y, tri->pos3.z);
    }
    glEnd();
}


Notice that i removed the calls to glNormal3f and glTexCoord2f. That is because we don't need normal information or shadows. Also notice that the function has an extra argument, ground_y, which is used instead of the model's y coordinates. This flattens the model's geometry in Y axis to the coordinate provided by ground_y. Since we use a flat single color, the overlapping triangles will look like a single solid shadow.

How do we find ground_y though? More on this a bit later. First i want to note something.

Coordinate Systems

Hopefully you know about local and global (or object and world) coordinate systems, otherwise you would have a hard time understanding how to create (or modify) a 3D game engine. So it is important to keep in mind that as the functions are written above, they assume the rendering happens in local (object) space and before you pass the ground_y argument to the render_model_shadow function, you need to bring it in the model's local space because most likely it will be in world (global) space. Fortunately this is just a matter of subtracting the Y coordinate of the object's origin from the ground's Y level (assuming that the object "stands on" its own origin, otherwise you'll also need to include the distance between the origin and the low-most vertex of the model - in a humanoid character that would be the distance between the origin and the feet of the character).

Semi-transparent Shadows

If you try the above method, you'll realize that the shadows are very dark. Unless you are making a game full with dark areas, you might want to make the shadows a bit see-through. The obvious method is to enable alpha blending in OpenGL and use that. However, as many people who tried the shadows in the original GLQuake figured out, this looks a bit weird since the overlapping parts of the model darkened some areas more than others.

To do this right we need to use the stencil buffer. The method is very simple: after we have all of our scene and models rendered, we render the shadows with only the stencil buffer enabled to "burn" the shadow geometry in the stencil buffer in a way that only allows writes in the "burned" areas. Then we enable blending and draw a fullscreen semi-transparent quad. This makes the shadowed areas darker without making them actually black and solves the overlapping issue. In fact not only makes the shadows appear as perfectly solid but also overlapping shadows from different models are unified to a single surface.

Ok, so how to do that? The code is more complex than the above, so i'm only going to show snippets from my own Alithia Engine which does that. You can find the full code of the engine in its git repository (from this site you can read the code without actually downloading it, just click on the tree link). Keep in mind that the Alithia Engine code uses display lists and, thus, is a bit more "obfuscated" to look at. There are comments to find the right part of the code though and with this tutorial in mind i think you can understand it.

So, as i explained, first we have to enable only stencil writing. This can be done with the code below

glDisable(GL_LIGHTING);
glDisable(GL_TEXTURE_2D);
glEnable(GL_POLYGON_OFFSET_FILL);
glPolygonOffset(-1.0, -1.0);
glColorMask(0, 0, 0, 0);
glDepthMask(0);
glEnable(GL_STENCIL_TEST);
glStencilFunc(GL_ALWAYS, 1, 1);
glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);

The above code disables lighting and texturing, sets the color and depth mask to zero so no color or depth information will be written to frame buffer and depth buffer, enables the stencil buffer and configures its state to always write the value "1" in the stencil buffer when triangles are drawn (note that at the beginning of the frame, the stencil buffer is cleared to zero so at this point it is always zero - if you use the stencil buffer for other purposes, such as mirrors, you will need to also clear it here using glClear and GL_DEPTH_BUFFER_BIT).

Pay a bit of attention to glPolygonOffset. This configures OpenGL to "offset" a bit the depth values read from the depth buffer when doing depth testing to avoid "z-fighting". This is an artifact that happens when two depth values are about the same, which is a common case when we're rendering triangles which share the same space.

Next we draw the shadow geometry. This depends on the engine, etc but it will be something like

for (i = 0; i < models; i++) {
    float ground_y = find_ground_y_for_model(model[i]);
    draw_model_shadow(model[i], ground_y);
}

The "draw_model_shadow" function above will be slightly modified than the one i showed at the previous part of the article: it doesn't need to alter texturing or set color since both are disabled anyway.

Now that we have the shadow geometry burned in the stencil buffer, we need to draw the fullscreen quad. Here is how i do this in the Alithia Engine

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

glColorMask(1, 1, 1, 1);

glStencilFunc(GL_EQUAL, 1, 1);
glStencilOp(GL_ZERO, GL_ZERO, GL_ZERO);

glColor4f(0, 0, 0, 0.5f);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

glBegin(GL_QUADS);
glVertex2d(-1, -1);
glVertex2d(1, -1);
glVertex2d(1, 1);
glVertex2d(-1, 1);
glEnd();

First the projection and modelview matrices are reset to identity matrices. This makes drawing a fullscreen quad very easy. Then we enable color writes and configure the stencil to allow writes only where the stencil value for a pixel is set to "1" (the value we wrote at the buffer when we burned the shadows in). We also enable alpha blending and use a black color with 0.5 alpha (exactly half-transparent black) and finally we draw a quad to cover the whole screen.

Once everything is said and done, we have to bring back the OpenGL to a useful state.

glDisable(GL_BLEND);
glDepthMask(1);
glDisable(GL_STENCIL_TEST);
glDisable(GL_POLYGON_OFFSET_FILL);

At this point in Alithia Engine i draw the HUD and GUI (if it is enabled).

The Ground

Ok, so how do we find the ground_y value used all above? The answer is probably not what you expect: i don't know. This really depends on your engine more than anything else. Conceptually what you have to do is find the ground's Y value at exactly the point where the origin of the model to render is. In Alithia Engine, the world is made of a 2D grid, so all i have to do is to divide the X and Z coordinates of the model's position by the grid cell's size to find the cell that the origin is. Then use the height of that cell's floor and i find the ground_y value.

In an engine where the world is made of polygons, you can fire a ray from the model's origin downwards, check all world polygons against it and use the intersection point that is closest to the model's origin. Then use the intersection point's Y coordinate as the ground_y value. Obviously, it is very slow to check all polygons, so using some method to organize the world in areas hierarchically should be used. Common methods are BSPs and octrees, both of which will speed up the process. Also since the models do not move in each frame (at least not all the time), you can save the "current" ground_y for each model in the model's structure and update it only when the model is moved around.

Using only the object's origin might not be always a good idea: if the origin is over some small but deep crack, the shadow will be rendered at the crack's bottom. It might be a better idea to check at the origin and around it and then use the one closest to the character or some average. If this is a bit slow, you might also split this process over several frames, but i'm getting out of hand here :-P.

More Than That

Despite this lengthy text, the algorithm is very simple to implement and it'll probably take you less time than reading this. However once you do, you might find yourself wanting a better method. This method looks ok for mostly flat areas and areas where hard shadows are acceptable, but it doesn't really follow any lighting or isn't the best. So here are some quick notes on making it better…

Take light sources into account

The current method simply ignores all light sources and assumes that the light is always over the model. In Alithia Engine this is actually true: when i'm rendering a model, i check the lightmap values around the model and add a light over the model with the lightmap colors. But in some cases, you might want to be a little more dynamic with your shadows (imagine a corridor with torches: the torch light sources will buzz around the torch, making the lights flicker and you want your shadows to be a little randomish). There is a small, but effective, modification to make the shadows a little more dynamic: in addition to ignoring the model's Y value, also add an offset to the X and Z values. The offset will be the direction normal from the closest light to the model, scaled to some value depending on the distance of the model from the light. Make sure you limit the length of this factor so that it generally the shadow is still under the model and doesn't stray much, but it is shifted enough to show that it isn't bolted there.

Real Planar Shadows

The method i describe in this tutorial is actually a simplification of planar shadows. Planar shadows, simply use a plane and a lightsource and project the geometry of the model from the lightsource to the plane. This looks more realistic than the modification above in regards to lighting, but requires that most of the game is in flat areas. Many games still use them though, but "shadows on air" isn't a rare sight in these. The method i described above still can have shadows on air, but since the shadow is right below the model, it is less likely to look strange.

Render the geometry in a texture instead of the stencil buffer

This requires more work and render-to-screen code, but will increase the realism of the rendering since it will produce more "blurry" (soft) shadows. Instead of rendering the model with Y flattened from the camera (player's) perspective, render it from another camera positioned at the top of the model looking straight down, in a white texture with grey flat polygons. Then render this texture in a quad using multiplicative blending below the model as if you would render the model shadow geometry above (flat in ground, with its Y values set to it).

A modification of it, which requires a bit of geometric processing, is to find the polygons which are under the model and instead of a single quad, render these polygons again (in multiplicative blending too) but with that texture and texture coordinates set to make the texture appear as a quad (these coordinates are very simple to calculate: just use the object origin's X and Z values with an offset to make it appear in center). Make sure the texture coordinates are clamped and that there is always at least a pixel of whiteness around the texture. This method allows shadows to be used even in (mostly) non-flat areas.

This last method is what the Source engine (used in Half-Life 2 and many other games) uses for most shadows. Actually it also uses a slight modification of that to allow for directional rendering, but this can be done in a similar way by offsetting the camera's position a bit when rendering the dark polygon version.

Aaaand... i'm Done

Ok, that was my first tutorial on IndieDB. Depending on the mood and responses, i might write another one at the future or not touch the site anymore :-). Also i'm not sure if the subject really required so much explanation, but i wanted to "test drive" the site and the tutorial posting feature :-P. Unfortunately the visual editor proved rather unusable, so i had to reformat everything by hand in HTML... :-/. Also since i couldn't select "Custom Built" as a link for the tutorial, i linked it to some engines which people might use with this. However, as you can imagine, like some other tutorials on this site (f.e. the seamless texturing tutorial) isn't only appropriate for these engines. Note that the Quake engine actually uses some form of this method, but has artifacts. The engine's simplicity might be a good testbed for implementing this algorithm though :-).

Have fun.

Post comment Comments
Guest
Guest

This has absolutely nothing to do with the jMonkeyEngine...

Reply Good karma Bad karma+1 vote
Post a comment

Your comment will be anonymous unless you join the community. Or sign in with your social account: