3D Things

Douglas O'Brien
Unregistered
 
Post: #1
How do you make fast shaddows on 3D engines?

I know there is something called stencil buffers. Aren't those the shapes that are created when light shines off of something? For example a ball would make a cone. And then when you draw the world you check a pixel to see if its in any of those shapes to detrimine how it's lit? I doubt this would be how it works cause it seems to slow.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
Huh boy. What a topic to try & summarize.

Basically, shadows are hard. Nobody can do proper shadows in real time yet. There are a number of cheats, though. These names aren't official, I made up most of them on the spot. It's also not a comprehensive catalog, there are undoubtedly many more techniques I've missed.

Light Mapping
If your world isn't changing, neither do the shadows, or the patterns of light. That means that you can pre-calculate shadow and light colors and shapes for everything that doesn't move. Obviously, any moving objects screw this up, but it's quite a good approximation. This is what Quake 3 and most current 3D engines do.

Projective Texturing
If your shadow doesn't change shape, you can project the shape out to the closest surface in an appropriate direction, and draw a shadow texture flush with that surface. Quake 3 uses this technique to cast fuzzy dot shadows for people on the ground below them. Not super-realistic, but quite inexpensive.

Projective Geometry
Rather than projecting a fuzzy blob onto your world, you can project the shape of the object casting the shadow. If you project it out from the light's position, you'll get a fairly realistic shadow. Unfortunately, you still can't really make your object shadow itself, and the method is quite expensive. Quake 3 can also use this method if you set it up from the console.

As a half-way house between projective texturing and geometry, you can render your geometry in 2D into a texture, and then use that texture as a projective texture. Brian Barnes is trying this method out for Dim3. He'll be able to tell you all the ins and outs of it.

Stencil Shadows
This is what Doom 3 will use for shadowing. Basically, you draw your scene once for each light that affects the scene. For each object you draw, you test it against the "shadow volume" for that light, generated by the geometry in the scene. If it's inside the volume, you don't draw it this time around; if it's outside, you draw it lit by that light & blended with whatever you've already drawn. This method is called stencil shadows because it uses the stencil buffer to create the shadow volume that's tested against.

You'll find good articles on all these methods elsewhere on the 'net, but hopefully this gives you somewhere to start looking.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #3
I would advice strongly AGAINST using the stencil buffer for any shadowing effects you plan to create. It is not hardware acellerated on early cards and in os 9 at all. Instead use the alpha buffer - it has support back to the Rage Pro.

I'm using the alpha buffer, and standard projection method to create shadows back to the Rage Pro.

Shameless plug: On the Rage128 and later I throw in a soon-to-be-patent-pending* method to create anti-aliased geometry and shadows with only about 20% overhead.

* email for more info if you're really interested.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
Unregistered
Unregistered
 
Post: #4
Here is the basic algorithm that I use to make shadows:

1. Create your 4X4 "shadow matrix"

for (short i=0; i<4; i++){
for (short j=0; j<4; j++){
shadowMatrix[i][j] = 0.;
}

shadowMatrix[i][i] = 1.;
}

shadowMatrix[3][3] = 0.;


2. Do this every time through your loop:

glPushMatrix();
glPushAttrib(GL_LIGHTING_BIT);
glDisable(GL_LIGHTING);
glColor4f(0.f, 0.f, 0.f, 0.75f);
get xq, yq, zq, the position of the light source
glTranslatef(xq, yq, zq);
glMultMatrixf(shadowMatrix[0]);
glTranslatef(-xq, -yq, -zq);
glTranslatef(x, y, z); // or wherever you want to draw your object
Draw your object here
glPopAttrib();
glPopMatrix();

This creates a squashed black version of your object in the plane y=0
Quote this message in a reply
Unregistered
Unregistered
 
Post: #5
oops

I forgot this step:

shadowMatrix[1][3] = -1. / (y-position of light);

sorry
Quote this message in a reply
Unregistered
Unregistered
 
Post: #6
that was the "y component of the position of the light", NOT y minus the position of the light
Quote this message in a reply
Unregistered
Unregistered
 
Post: #7
oops

I forgot this step:

shadowMatrix[1][3] = -1. / (y-position of light);

sorry
Quote this message in a reply
Jeff Binder
Unregistered
 
Post: #8
Here's a general purpose shadow matrix (run the function after your viewing transformations but before you modeling transformations):

Code:
typedef struct {
    double x, y, z, w;
} vector4_t;

typedef struct {
    double a, b, c, d;
} plane_t;

//light is the location (in 4D homogeneous coordinates, like
//the ones sent to glLight*()) of the light.
//plane is the standard equation of the plane onto which
//the shadow is cast.
shadow_matrix(vector4_t light, plane_t plane) {
    float matrix[4][4];
    float dot;

    if (plane.d < 0) {
        plane.a *= -1;
        plane.b *= -1;
        plane.c *= -1;
        plane.d *= -1;
    }

    dot = plane.a * light.x + plane.b * light.y + plane.c * light.z + plane.d * light.w;

    matrix[0][0] = dot - light.x * plane.a;
    matrix[1][0] = 0.0 - light.x * plane.b;
    matrix[2][0] = 0.0 - light.x * plane.c;
    matrix[3][0] = 0.0 - light.x * plane.d;

    matrix[0][1] = 0.0 - light.y * plane.a;
    matrix[1][1] = dot - light.y * plane.b;
    matrix[2][1] = 0.0 - light.y * plane.c;
    matrix[3][1] = 0.0 - light.y * plane.d;

    matrix[0][2] = 0.0 - light.z * plane.a;
    matrix[1][2] = 0.0 - light.z * plane.b;
    matrix[2][2] = dot - light.z * plane.c;
    matrix[3][2] = 0.0 - light.z * plane.d;

    matrix[0][3] = 0.0 - light.w * plane.a;
    matrix[1][3] = 0.0 - light.w * plane.b;
    matrix[2][3] = 0.0 - light.w * plane.c;
    matrix[3][3] = dot - light.w * plane.d;    

    glMultMatrixf((GLfloat *)matrix);
}

To get the standard equation of a plane, use the plane's normal for a, b, and c, and calculate d like this:

plane.d = -(plane.a * pt.x + plane.b * pt.y + plane.c * pt.z);

where pt is any point on the plane. If you want to cast shadows on convex surfaces this way, you'll need to do some clipping trickery with the stencil buffer as well. If you want I can put together some code for it.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #9
To make better looking shadows, do this:

first, draw the shadow into the alpha channel:

// don't want to set depth values when drawing the shadow
glDisable(GL_DEPTH_TEST);

// and we only want to draw into the alpha channel
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_TRUE);

clear the alpha for the receiving shadow by either drawing as (0,0,0,0), drawing it with (GL_ZERO,GL_ZERO), it or using glClear (not sure which is fastest)

glDisable(GL_CULL_FACE);

if you're using transparent stuff:
glEnable(GL_BLEND);
glBlendFunc(GL_ONE, GL_ONE);
otherwise:
glDisable(GL_BLEND);

draw the shadow as described above

now re-draw the surface receiving the shadow:

// re-enable the depth test
glEnable(GL_DEPTH_TEST);

// and only draw where the z-values equal
glDepthFunc(GL_EQUAL);

// draw into all 4 channels again
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);

// and blend so that where the alpha value is zero, it keeps the old pixels, but where it's one, it gets the new shadowed pixels
glEnable(GL_BLEND);
glBlendFunc(GL_DST_ALPHA, GL_ONE_MINUS_DST_ALPHA);

draw the shadow receiving surface with the light casting the shadow disabled

// restore blending function:
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

// restore depth compare function:
glDepthFunc(GL_LESS);

This should work all the way back to the RagePro*. using the stencil buffer looks similar but won't work on anything before the Rage128, and if you're running 9 doesn't even work on some cards that support it I think. It's important that when drawing the shadow receiving polygon the first time (with full lighting), blending be enabled. If blending is not enabled, OpenGL does not guarantee that the depth values generated will equal. The following code makes blending act as though it were disabled, and most of the time should not reduce the polygon and pixel throughput at all:

glEnable(GL_BLEND);
glBlendFunc(GL_ONE, GL_ZERO);

* I've yet to test if glDepthFunc(GL_EQUAL) works to spec.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #10
I was just looking at that shadow projection matrix generation code... that would make a GREAT AltiVec sample. Absolutely pointless though - you only generate a couple dosen shadow projection matrices per frame max.

edit: If you're wondering, this code could be used to demonstrate:
1. load/store
2. vector multiplication
3. sum-across
4. using vec_sld to extract one value from a vector float
5. splatting
6. silly subtract-multiply operations.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
Member
Posts: 70
Joined: 2002.07
Post: #11
Quote:Originally posted by OneSadCookie
As a half-way house between projective texturing and geometry, you can render your geometry in 2D into a texture, and then use that texture as a projective texture. Brian Barnes is trying this method out for Dim3. He'll be able to tell you all the ins and outs of it.

Quick addition to the above. Actually, dim3's shadows are more of a half-way house between projective, geometry, and stencils, at a pretty low cost.

Basically, the objects that cast shadows are run against each light in the scene. Right now, to speed things up, they stop at only the closest light, but that will be a setting for those with better hardware.

A second pass against drawing the maps happens for each light, and it's volume is created and cast against the world, redrawing those parts in darkness; the stencil buffer is used to splice between the volume and the texture that is created against the object.

The biggest problem is that too many shadows force a flush of the main opengl context when I've used up all the shadow buffers (settable.)

Another benifit, other than it's fast and looks as good as doom's shadows (based on doom screenshots), is that I can use ATI's whatever-it's-called (forgot the name - thing that adds additional vertexes) to smooth out the shadow.

A con is that it only casts shadows against objects in the map, not the map geomertry.

There's actually a "shadow" volume that you can attach to each model; this allows you to "fake" the size of a shadow. For instance, you can make something's shadows a lot bigger than it will be in real life to add some additional effect.

I'm going to have to put out a version soon, even a broken one, so you guys can see what I'm talking about.
Quote this message in a reply
Member
Posts: 49
Joined: 2002.05
Post: #12
My experience with stencil shadows is that they can be generated and rendered at a fairly decent speed. I'm testing on a Rage128 in OS 10.1.5. OS 9 may be really slow, I'm not sure because I haven't tried it there yet. I've been coding them into my engine and I found that you will need some sort of edge detection algorithm to get them to run fast enough (at least on my machine). My edge detection isn't working quite right yet so the shadows look like crap. I can get them to look decent when I take a brute force approach but it runs too slow. Another problem I've noticed is that stitching is occuring when I try to light my terrain with shadow volumes. When you get a polygon that is almost lying on a shadow volume plane you get an ugly stitching effect. I've tried using polygon offset but haven't got it quite right yet either.

Before I tried out stencil shadows I had projective shadows. Every frame you render the model from the position of the light and project it onto the scene. This was actually a lot faster in OS 9 than in OS X. It was way too slow updating the texture every frame however because glCopyTexSubImage2D() is very slow. I think Jaguar has a new render to texture feature in agl that is supposed to be a lot faster however. Another problem with this method is that if you don't render high res shadows and they get stretched across a lot of geometry the edges get horribly aliased and look really bad. Another problem is that the shadow keeps on projecting after it hits a polygon, so your shadow will pass through walls and stuff. The solution requires several more passes and depth testing and the accumulation buffer, etc.

Both of these methods may seem relatively attractive at first but there are lots of little problems with both of them... my 2 cents
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Seriously strange things Talyn 5 3,063 Feb 8, 2009 11:28 AM
Last Post: arekkusu
  OpenGL text and other things. Talyn 7 4,635 Jul 22, 2008 02:09 AM
Last Post: OneSadCookie