Name:			GLQuake stencil shadows
Author:			Rich Whitehouse
E-mail:			thefatal@telefragged.com
Homepage:		http://www.telefragged.com/thefatal/
-----------------------------------------------------------------------
Having never done anything with the stencil buffer before, I decided
to sit down this weekend and put stencil shadows into Quake merely for
the experience. It ended up being a lot more trouble than I'd anticipated,
but it is done, so I am now writing a tutorial on it.

Before I get started I will note that these are the "traditional" style
stencil shadows and as such they do have some issues, mainly the fact that
they do not stop and continue to the projected point, so you can see a
shadow being projected through to the other side of a wall for example.
I've noticed the same thing with stencil shadows in Quake3 so I imagine it
is using a similar method. Unfortunately as far as I know there is no easy
fix for that using this method. Although in theory you could determine
the surfaces of the BSP/other models that the shadow should project on
and rerender them instead of just rendering a screen rectangle at the end
of the routine, I'm not sure it would be worthwhile.

Having said that, there are still some things to be learned from this
tutorial, particularly if you're unfamiliar with practical applications of
the stencil buffer.

Anyway, let's start off by making sure the stencil buffer is ready to use.
Open up gl_vidnt.c and find the function "BOOL bSetupPixelFormat(HDC hDC)".
Under the initilization of our PIXELFORMATDESCRIPTOR you'll see this line:

	0,				// no stencil buffer

As you may have guessed, we will want to change this to non-0. For me, the
stencil buffer behaves the same no matter what I set this value to (as long
as it's non-0), but it may behave differently on other cards/drivers. In
any case, set it to 16, that should be fine for doing what we're doing.

Next we want to add some stuff to the triangle and alias header structs.
Open up gl_model.h and find this chunk of code:

typedef struct mtriangle_s 
{
	int					facesfront;
	int					vertindex[3];
} mtriangle_t;

Right below the vertindex[3]; line, you'll want to add this:

	int					neighbors[3];

This is so that we can store our other triangle "neighbors". A neighbor
is a triangle which shares the same edge (pair of vertices) as this
triangle. We'll want to precalculate this and store it on the triangle,
since attempting to make the necessary calculations in realtime would
likely bring the game to a crawl.

Next, right below the mtriangle_t structure is the aliashdr_t structure.
Find this line:

	int					posedata;	// numposes*poseverts trivert_t

Right below it, we want to add:

	int					baseposedata; //original verts for triangles to reference
	int					triangles; //we need tri data for shadow volumes

baseposedata is going to be our offset for the raw vert data. We are
saving this because posedata is actually an offset for custom vertex
data that GLQuake works out so that it can draw the current frame with
proper texture coordinates and whatnot using tri strips/fans. If we
really wanted to, we could actually do away with that system entirely,
and work out tex coordinates for each of our triangles, elimating the
existing alias model draw routine. However, since I don't intend to go
into that much detail, for now we are just going to save the unmodified
vertex data for reference by our triangles. The "triangles" value is,
as you may have guessed, an offset for our actual tri data.

Now that we've added these values, we want to actually make use of them.
Open up gl_mesh.c and find the GL_MakeAliasModelDisplayLists function.
First things first, right above that function, add this line:

void GL_TriPrecalc(aliashdr_t *paliashdr, mtriangle_t *tris, trivertx_t *verts);

We'll get to this function in a bit, but first we want to make some
changes to the GL_MakeAliasModelDisplayLists function itself. At the
top let's declare this local variable:

	mtriangle_t *tris;

And a bit below that, right after the "paliashdr = hdr;" line, we want
to add this chunk of code:

	//First save the original vertex data for reference by our tris
	verts = Hunk_Alloc (paliashdr->numposes * paliashdr->numverts 
		* sizeof(trivertx_t) );
	paliashdr->baseposedata = (byte *)verts - (byte *)paliashdr;
	for (i=0 ; i<paliashdr->numposes ; i++)
	{
		for (j=0 ; j<paliashdr->numverts ; j++)
		{
			*verts++ = poseverts[i][j];	
		}
	}

	//Now save the triangles as we will need them for shadow volumes
	tris = Hunk_Alloc (paliashdr->numtris * sizeof(mtriangle_t) );
	paliashdr->triangles = (byte *)tris - (byte *)paliashdr;
	Q_memcpy(tris, triangles, paliashdr->numtris * sizeof(mtriangle_t));

	//Calculate some stuff for the tris ahead of time
	GL_TriPrecalc(paliashdr, tris, verts);

First, this is allocating room for our raw vertex data, then it is going
through and moving the vertex data for each frame in the model into this
space. We save the offset to this memory in the "baseposedata" value we
added to the aliashdr struct earlier.

Next we do virtually the same thing for triangles, allocating space for
all of the triangles, setting our offset to them, and copying the current
triangle data into the memory our offset will lead us to.

Then finally we call GL_TriPrecalc, a function we will be getting into
shortly, which will find the neighbors for all of our triangles (this is
why we added the neighbors value to our triangle structure earlier).

We're done in gl_mesh.c now, so open up gl_rmain.c. Go down to the
R_DrawAliasModel function, and at the top, right above this chunk of code:

	if (R_CullBox (mins, maxs))
		return;

Add this:

	//Since we are using stencil shadows and they tend to stretch
	//outside of the viewable area of the entity itself, we want
	//to draw them regardless of whether we pass the cull check.
	if (r_shadows.value >= 2)
	{ //Add this guy to our list.
		if (g_numStencilEnts < MAX_STENCIL_ENTS)
		{
			g_stencilEnts[g_numStencilEnts] = currententity;
			g_numStencilEnts++;
		}
	}

As the comment explains we want to shadow entities even if the entity
itself is culled out. The rest of this code is just adding this ent
into our array of ent pointers which we use to determine which ents to
shadow later on.

Now go down a little more in the function. Near the bottom you will
see the existing shadows check which reads:

	if (r_shadows.value)

You will want to change that to:

	if (r_shadows.value && r_shadows.value < 2)

So that it does not draw at the same time as our stencil shadows.

Next scroll down to the R_RenderScene function. In this function, right
below this line:

	GL_DisableMultitexture();

Add this line:

	GL_StencilShadowing();

This is the function we will be using to go through our list of
"stencilEnts" and actually do the shadowing for all of them. Now we're
finished modifying all the existing functions and code, so it's time
to start adding our own. I'll go through them individually and try to
explain what each of them do as we add them.

First scroll back up to the R_SetupAliasFrame function. Directly above
that function, add this function (note that the function does not have
to be placed there, but we're putting it there for lack of a better
place):

/*
=================
GL_StencilShadowing

Go through each frame and draw stencil shadows for appropriate ents
-rww
=================
*/
void GL_StencilShadowing(void)
{
	if (r_shadows.value < 2 || g_numStencilEnts <= 0)
	{
		return;
	}

	//Set us up for drawing our passes onto the stencil buffer
	glPushAttrib( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_ENABLE_BIT | GL_POLYGON_BIT | GL_STENCIL_BUFFER_BIT );
	glDisable (GL_TEXTURE_2D);
	glDepthMask( GL_FALSE );

	if (r_shadows.value == 2)
	{ //> 2 is a debug feature to draw the shadows outside of the stencil buffer
		glEnable( GL_STENCIL_TEST );
		glColorMask( GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE );
	}
	else
	{
		glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
		glPolygonMode (GL_FRONT_AND_BACK, GL_LINE);
	}

	glStencilFunc( GL_ALWAYS, 1, 0xFFFFFFFF );

	while (g_numStencilEnts > 0)
	{ //go through the list and do all the shadows
		g_numStencilEnts--;
		GL_StencilShadowModel(g_stencilEnts[g_numStencilEnts]);
	}

	glColorMask( GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE );

	//draw a full screen rectangle now - wherever we draw
	//is where our "shadows" will actually be seen.
	glColor4f( 0.0f, 0.0f, 0.0f, 0.6f );
	glStencilFunc( GL_NOTEQUAL, 0, 0xFFFFFFFF );

	glStencilOp( GL_KEEP, GL_KEEP, GL_KEEP );

	glEnable (GL_BLEND);
	glPushMatrix(); //save the current view matrix

	glLoadIdentity ();

	glRotatef (-90,  1, 0, 0);
	glRotatef (90,  0, 0, 1);
	glBegin (GL_QUADS);
		glVertex3f (10, 100, 100);
		glVertex3f (10, -100, 100);
		glVertex3f (10, -100, -100);
		glVertex3f (10, 100, -100);
	glEnd ();

	glPopMatrix(); //so we aren't stuck with the identity matrix
	glPopAttrib(); //pop back our previous enable/etc. state so we don't have to bother switching it all back
}

This is the function we are calling every frame from R_RenderScene.
You can get an idea of what we're doing from the comments, but overall,
the purpose of this function is to set up the stencil buffer for
drawing, go through our stencil ent list and do the shadow passes for
each alias model in the list, and then we render a rectangle over the
entire screen with the color we want our shadows to be. Basically,
our shadow volume passes determine the area of the stencil buffer the
final rectangle can cover when we draw it, to give the appearance of
shadows.

Next, above the function we just added, add this function:

/*
=================
GL_StencilShadowModel

Do the shadowing for an ent
-rww
=================
*/
void GL_StencilShadowModel(entity_t *e)
{

	int				pose, numposes;
	float			interval;
	float			len;
	aliashdr_t		*paliashdr;
	vec3_t			lightPos;
	vec3_t			fwd, right, up, ang, ang2;

	if (!e->model)
	{
		return;
	}

	paliashdr = (aliashdr_t *)Mod_Extradata (e->model);

	if ((e->frame >= paliashdr->numframes) || (e->frame < 0))
	{
		Con_DPrintf ("R_AliasSetupFrame: no such frame %d\n", e->frame);
		e->frame = 0;
	}

	pose = paliashdr->frames[e->frame].firstpose;
	numposes = paliashdr->frames[e->frame].numposes;

	if (numposes > 1)
	{
		interval = paliashdr->frames[e->frame].interval;
		pose += (int)(cl.time / interval) % numposes;
	}

	//Just some random light position.
	//This is relative to the entity position and angles.
	lightPos[0] = 0.0f;
	lightPos[1] = 0.0f;
	lightPos[2] = 512.0f;

	glPushMatrix ();
	R_RotateForEntity (e);
	glTranslatef (paliashdr->scale_origin[0], paliashdr->scale_origin[1], paliashdr->scale_origin[2]);
	glScalef (paliashdr->scale[0], paliashdr->scale[1], paliashdr->scale[2]);
	GL_DrawAliasStencilShadow(paliashdr, pose, lightPos);
	glPopMatrix ();
}

This function is similar R_SetupAliasFrame in how it does the work
of getting the pose for us first. Following that we set up our
rotation matrix and whatnot just as we do when we normally draw an
alias frame, and following that we call GL_DrawAliasStencilShadow,
which is where we actually do our shadow passes. Note that the light
position we're using here is just a fixed position above the entity,
and not relative to the current rotation. If you wanted you could
transform this point based on the relative entity position and angles
so that it is a fixed world coordinate, but for this tutorial we'll
just use the fixed point.

Next above this function, we'll add our GL_DrawAliasStencilShadow
function:

/*
=============
GL_DrawAliasStencilShadow

Do both of the stencil buffer passes
-rww
=============
*/
void GL_DrawAliasStencilShadow (aliashdr_t *paliashdr, int posenum, vec3_t lightPosition)
{
	glCullFace(GL_BACK);
	glStencilOp( GL_KEEP, GL_KEEP, GL_INCR );
	GL_ShadowPass( paliashdr, posenum, lightPosition );

	glCullFace(GL_FRONT);
	glStencilOp( GL_KEEP, GL_KEEP, GL_DECR );
	GL_ShadowPass( paliashdr, posenum, lightPosition );
}

These are our two stencil shadow passes. Basically, the first pass is
incrementing the stencil buffer by drawing the full shadow volume.
The next pass then reverses the face culling and decrements the shadow
buffer to eliminate the area we do not want the shadow to show in.
Without this second pass, we would see basically what we render for
the shadow volume, as opposed to cutting out the area between surfaces
the shadow is "hitting".

Now above this function, let's add the function we use to actually
draw the volume:

/*
=============
GL_ShadowPass

Determine and draw our shadow volume
-rww
=============
*/
void GL_ShadowPass(aliashdr_t *paliashdr, int posenum, vec3_t lightPosition)
{
	static byte *v1;
	static byte *v2;
	static vec3_t v3;
	static vec3_t v4;
	static int i;
	static int j;
	static int neighborIndex;
	static trivertx_t *verts;
	static mtriangle_t *tris;

	verts = (trivertx_t *)((byte *)paliashdr + paliashdr->baseposedata);
	tris = (mtriangle_t *)((byte *)paliashdr + paliashdr->triangles);
	verts += posenum * paliashdr->numverts;

	//go through all the triangles
	for ( i = 0; i < paliashdr->numtris; i++ )
	{
		mtriangle_t *tri = &tris[i];

		//Only bother if this tri is facing the light pos
		if (GL_TriFacingLight(tri, verts, lightPosition))
		{
			for ( j = 0; j < 3; j++ )
			{
				neighborIndex = tri->neighbors[j];

				//If the tri has no neighbor or the neighbor is not facing the light,
				//then it is an edge
				if (neighborIndex == -1 || !GL_TriFacingLight(&tris[neighborIndex], verts, lightPosition))
				{
					v1 = &verts[tri->vertindex[j]].v[0];
					v2 = &verts[tri->vertindex[( j+1 )%3]].v[0];

					//get positions of v3 and v4 based on the light position
					v3[0] = ( v1[0]-lightPosition[0] )*PROJECTION_DISTANCE;
					v3[1] = ( v1[1]-lightPosition[1] )*PROJECTION_DISTANCE;
					v3[2] = ( v1[2]-lightPosition[2] )*PROJECTION_DISTANCE;

					v4[0] = ( v2[0]-lightPosition[0] )*PROJECTION_DISTANCE;
					v4[1] = ( v2[1]-lightPosition[1] )*PROJECTION_DISTANCE;
					v4[2] = ( v2[2]-lightPosition[2] )*PROJECTION_DISTANCE;

					//Now draw the quad from the two verts to the projected light
					//verts
					glBegin( GL_QUAD_STRIP );
						glVertex3f( v1[0], v1[1], v1[2] );
						glVertex3f( v1[0]+v3[0], v1[1]+v3[1], v1[2]+v3[2] );
						glVertex3f( v2[0], v2[1], v2[2] );
						glVertex3f( v2[0]+v4[0], v2[1]+v4[1], v2[2]+v4[2] );
					glEnd();
				}
			}
		}
	}
}

Basically we are going through all the tris, then seeing which face the
light, and out of those which ones either have no neighbors or have a
neighbor that is not facing the light (to form a "silhouette" basically).
Once we have such a triangle, we take the two verts and project them
based on the position of the light, drawing that part of the shadow
volume. We do this for each tri until we have finished the full volume.

You may have noticed how we used a function called "GL_TriFacingLight"
above. We'll be adding that above this function now:

/*
=============
GL_TriFacingLight

Determine of a given triangle is facing the light position. A lot
of this could probably be precalculated, but I am lazy. To store
the planeEq we would have to store one for every frame since the
tri remains the same but the verts change based on the frame.
The calculation is relatively inexpensive so it is at least
somewhat reasonable to perform it in realtime.
-rww
=============
*/
int GL_TriFacingLight(mtriangle_t *tri, trivertx_t *verts, vec3_t lightPosition)
{
	byte *v1;
	byte *v2;
	byte *v3;
	float side;
	float planeEq[4];

	v1 = &verts[tri->vertindex[0]].v[0];
	v2 = &verts[tri->vertindex[1]].v[0];
	v3 = &verts[tri->vertindex[2]].v[0];

	planeEq[0] = v1[1]*(v2[2]-v3[2]) + v2[1]*(v3[2]-v1[2]) + v3[1]*(v1[2]-v2[2]);
	planeEq[1] = v1[2]*(v2[0]-v3[0]) + v2[2]*(v3[0]-v1[0]) + v3[2]*(v1[0]-v2[0]);
	planeEq[2] = v1[0]*(v2[1]-v3[1]) + v2[0]*(v3[1]-v1[1]) + v3[0]*(v1[1]-v2[1]);
	planeEq[3] = -( v1[0]*( v2[1]*v3[2] - v3[1]*v2[2] ) +
				v2[0]*(v3[1]*v1[2] - v1[1]*v3[2]) +
				v3[0]*(v1[1]*v2[2] - v2[1]*v1[2]) );

	side = planeEq[0]*lightPosition[0]+
		planeEq[1]*lightPosition[1]+
		planeEq[2]*lightPosition[2]+
		planeEq[3];

	if ( side > 0 )
	{
		return 1;
	}

	return 0;
}

As the function comment indicates, the planeEq could be precalculated,
but is not for the given reason. I know the math is somewhat frightening
here, but it's just a standard formula that I ripped from elsewhere, and
you aren't expected to sit down and analyze exactly what the formula does.
Just know that it's basically figuring out the plane equation from the
given vertex positions on the triangle, and checking that equation with
the light position to determine if this tri is actually facing the light
or not.

Above this function, we'll add our other function that we referenced
in gl_mesh.c as well as the neighbor finding function:

/*
=============
GL_GetTriNeighbors

Get the neighbors for a given triangle (meaning, said neighbor
shares an edge with this triangle).
-rww
=============
*/
void GL_GetTriNeighbors(aliashdr_t *paliashdr, mtriangle_t *tris, mtriangle_t *tri, int *neighbors)
{
	static mtriangle_t *n;
	int i = 0;
	int numN = 0;
	static int j, k;
	static int vertA1, vertA2, vertB1, vertB2;

	neighbors[0] = neighbors[1] = neighbors[2] = -1;

	while (i < paliashdr->numtris)
	{
		n = &tris[i];

		if (n != tri)
		{
			j = 0;
			while (j < 3)
			{
				vertA1 = tri->vertindex[j];
				vertA2 = tri->vertindex[(j+1)%3];

				k = 0;
				while (k < 3)
				{
					vertB1 = n->vertindex[k];
					vertB2 = n->vertindex[(k+1)%3];

					if ((vertA1 == vertB1 && vertA2 == vertB2) || (vertA1 == vertB2 && vertA2 == vertB1))
					{
						if (neighbors[j] == -1)
						{
							neighbors[j] = i;
						}
						else
						{ //this edge is shared by more than 2 tris apparently.
						  //this seems to actually happen at times, which is why
						  //we are bothering to check for it.
							neighbors[j] = -2;
						}
					}

					k++;
				}

				j++;
			}
		}

		i++;
	}

	j = 0;
	while (j < 3)
	{ //mark any -2 as -1 now since we're done
		if (neighbors[j] == -2)
		{
			neighbors[j] = -1;
		}
		j++;
	}
}

/*
=============
GL_TriPrecalc

Do whatever precalc'ing we can (in this case just get neighbors).
We could also pre-determine planeEq's for each tri*each frame in
here if we desired.
-rww
=============
*/
void GL_TriPrecalc(aliashdr_t *paliashdr, mtriangle_t *tris, trivertx_t *verts)
{
	int i = 0;
	mtriangle_t *tri;

	while (i < paliashdr->numtris)
	{
		tri = &tris[i];
		GL_GetTriNeighbors(paliashdr, tris, tri, tri->neighbors);
		i++;
	}
}

GL_TriPrecalc just goes through all the tris and calls the function to
find their neighbors. GL_GetTriNeighbors take a specific tri, then it
iterates through the list of tris and finds any triangle that is sharing
the specified edge with the given triangle. I did find that on some
Quake models, an edge can be shared by more than 2 triangles. I guess
this is valid but it's not something that works with our method of
drawing the shadow volume, so when we find an edge shared by more than
2 triangles, we just discard the neighbor this edge is shared with
entirely. This does not happen often so it's not a big performance hit
or anything.

Next go down to the R_Clear function and add this to the bottom:

	glClear(GL_STENCIL_BUFFER_BIT);

Or you can add a |GL_STENCIL_BUFFER_BIT to the existing glClears, either
way works.

Anyway, finally, add our globals and defines above the GL_GetTriNeighbors
function:

#define PROJECTION_DISTANCE			10
#define MAX_STENCIL_ENTS			1024

static entity_t *g_stencilEnts[MAX_STENCIL_ENTS];
static int g_numStencilEnts = 0;

Now compile and you should be done. Start the game, bring down the
console, type r_shadows 2, and you can see the result of your work.
As an additional note, I used the stencil shadow tutorial over at
nehe.gamedev.net as reference for a few things in here, so you may
wish to take a look at it for whatever reason. The site itself has
quite a few more good tutorials as well (though not quake-related).

-Rich