Other articles mention "Carmacks reverse" as the solution, but warn that it is patented. How did they work around this patent issue in the open source release of Doom 3?

Carmack's reverse is the solution

You could check out the Doom 3 source code - I hear they modified it to remove the patented algorithm before releasing the source code.

I've personally used it in a game before. I read the actual patent and compared their claims against my implementation of the "Carmack's reverse" algorithm, and in my professional opinion, my method did not overlap with their claims. My lead agreed with me, so we shipped it So, IMHO, it's possible to implement the algorithm without using the patented method, but maybe I'm wrong, and maybe we opened our employer up to a lawsuit... Yay for patents.

However, stencil shadows are rarely used these days. Almost everyone uses shadow mapping methods instead - unless you specifically need pixel-perfect hard-edged shadows.

most annoying thing in stencil shadows (for z fail) is that you need properly drawn shadow volumes (clockwise or counterclockwise - depending on implementation) they need to face all inside or all outside (as far as i remember)

anyway heres old code (was working last time i used it ;])

VBO_BE -> array of face info (provides length of each face, and index in VBO_V]

VBO_V array of vertices

//---------------------------------------------------------------------------

#ifndef STENCIL_SHADOW_TACHOGL_DRAWINGH
#define STENCIL_SHADOW_TACHOGL_DRAWINGH
//---------------------------------------------------------------------------
#include "DxcMath.h"
#include "DxcMatrix.h"
#include "OPENGL_ATTACH.h"
#include "SysUtils.hpp"
#include "Dialogs.hpp"
#include "Math.hpp"
#include "Math.h"
#include "gl/glew.h"
#include "gl/gl.h"
#include "TachoGLModelSRC.h"

struct ShadowFaceNFO
{
int index;
int len;
};

struct TStencilShadowEffect
{
//t3dpoint<double> VERT_ARR[12*4]; //for drawing // note that face vert count cant exceed 12

Matrix44<double> AMODEL;
Matrix44<double> AVIEW;
Matrix44<double> APROJ;
int 			 AVIEWP[4];



t3dpoint<double> * START_CAP_VBO;

t3dpoint<double> * CAP_CENTER;

t3dpoint<double> * END_CAP_VBO;

t3dpoint<double> * SIDE_CAP_VBO;



void CalcStartCaps(TachoGLModel<double> * model)
{
START_CAP_VBO = new t3dpoint<double> [ model->header.LENGTH ];
int i,j;
for (i=0; i < model->header.LENGTH; i++) START_CAP_VBO[i] = model->VBO_V[i];

}


void CalcEndCaps(TachoGLModel<double> * model, t3dpoint<double> lpos)
{
t3dpoint<double> LDIR;
END_CAP_VBO = new t3dpoint<double> [ model->header.LENGTH ];
int i,j;
for (i=0; i < model->header.LENGTH; i++)
{

LDIR = Normalize( model->VBO_V[i] - lpos );
END_CAP_VBO[i]  = model->VBO_V[i] + LDIR * infinity; 

}

}

void CalcCenterCap(TachoGLModel<double> * model)
{
CAP_CENTER = new t3dpoint<double> [ model->VBO_BE.Length ];

int i,j;         t3dpoint<double> center;
for (i=0; i < model->VBO_BE.Length; i++)
{
center = t3dpoint<double>(0.0,0.0,0.0);
for (j=0; j < model->VBO_BE[i].length; j++)
{
center = center + START_CAP_VBO[	model->VBO_BE[i].INDEX_START	+	j	];
center = center + END_CAP_VBO[		model->VBO_BE[i].INDEX_START	+	j	];
}


CAP_CENTER[i] = center / double( model->VBO_BE[i].length * 2.0 );
}
}


void CalcSideCaps(TachoGLModel<double> * model)
{
int cnt = 0;

int i,j,x,index;

for (i=0; i < model->VBO_BE.Length; i++)
for (j=0; j < model->VBO_BE[i].length; j++)
cnt = cnt + 4;

int mmax = cnt;
SIDE_CAP_VBO = new t3dpoint<double> [cnt];

t3dpoint<double> tmp;
t3dpoint<double> tmp2;
//now calculate side caps

cnt = -1;
for (i=0; i < model->VBO_BE.Length; i++)
{
if (i == model->VBO_BE.Length-10)
{
 int super = 3;
}
index = model->VBO_BE[i].INDEX_START;

for (x=0; x < model->VBO_BE[i].length; x++)
{
cnt = cnt + 1;
if (cnt > mmax-1) cnt = mmax - 1;
SIDE_CAP_VBO[cnt] = END_CAP_VBO[index + x]; //50 km away


cnt = cnt + 1;
if (cnt > mmax-1) cnt = mmax - 1;
SIDE_CAP_VBO[cnt] = START_CAP_VBO[index + x];

if (x != model->VBO_BE[i].length - 1)
{
tmp  = START_CAP_VBO[	index + x + 1];
tmp2 = END_CAP_VBO[		index + x + 1];
} else
{
tmp  = START_CAP_VBO[index];
tmp2 = END_CAP_VBO[index];
}

cnt = cnt + 1;
if (cnt > mmax-1) cnt = mmax - 1;
SIDE_CAP_VBO[cnt] = tmp;


cnt = cnt + 1;
if (cnt > mmax-1) cnt = mmax - 1;
SIDE_CAP_VBO[cnt] = tmp2;

}



}




}



void FaceAllCapsOutside(TachoGLModel<double> * model)
{
t3dpoint<double> TMP_BUFF[55]; //each poly can have maximum of 22 verts (its likely it will never exceed that much)



int i,x, index, j,cnt;
t3dpoint<double> V1, V2, V3, NORMAL;
double D;


//first we check start caps,


for (i=0; i < model->VBO_BE.Length; i++)
{
index = model->VBO_BE[i].INDEX_START;
V1 = START_CAP_VBO[index];
V2 = START_CAP_VBO[index+1];
V3 = START_CAP_VBO[index+2];

NORMAL = Normal(V1, V2, V3, true);

D = getplaneD(NORMAL, V1);

//====================================CHECK IF WE NEED TO SWAP FACE==============================
if ( classifyapointagainstaplane(CAP_CENTER[i], NORMAL, D) == isBack )
{
cnt = -1;
for (j=model->VBO_BE[i].length-1; j > -1; j--)
{
cnt = cnt + 1;
TMP_BUFF[cnt]  = START_CAP_VBO[ index + j ];
}
for (j=0; j < model->VBO_BE[i].length; j++)
START_CAP_VBO[ index + j ] 	= TMP_BUFF[j]; //actual swap


}
//====================================CHECK IF WE NEED TO SWAP FACE==============================


}

//end caps


for (i=0; i < model->VBO_BE.Length; i++)
{
index = model->VBO_BE[i].INDEX_START;
V1 = END_CAP_VBO[index];
V2 = END_CAP_VBO[index+1];
V3 = END_CAP_VBO[index+2];

NORMAL = Normal(V1, V2, V3, true);

D = getplaneD(NORMAL, V1);

//====================================CHECK IF WE NEED TO SWAP FACE==============================
if ( classifyapointagainstaplane(CAP_CENTER[i], NORMAL, D) == isBack )
{
cnt = -1;
for (j=model->VBO_BE[i].length-1; j > -1; j--)
{
cnt = cnt + 1;
TMP_BUFF[cnt]  = END_CAP_VBO[ index + j ];
}

for (j=0; j < model->VBO_BE[i].length; j++)
END_CAP_VBO[ index + j ] 	= TMP_BUFF[j]; //actual swap


}
//====================================CHECK IF WE NEED TO SWAP FACE==============================


}



//now check for sides


    int acnt;
cnt = 0;
for (i=0; i < model->VBO_BE.Length; i++)
{

for (x=0; x < model->VBO_BE[i].length; x++)
{

V1 = SIDE_CAP_VBO[cnt];

V2 = SIDE_CAP_VBO[cnt+1];

V3 = SIDE_CAP_VBO[cnt+2];


NORMAL = Normal(V1, V2, V3, true);

D = getplaneD(NORMAL, V1);

                                             //check side face
if ( classifyapointagainstaplane(CAP_CENTER[i], NORMAL, D) == isBack )
{
acnt = -1;
for (j=3; j > -1; j--)
{
acnt = acnt + 1;
TMP_BUFF[acnt]  = SIDE_CAP_VBO[ cnt + j ];
}

for (j=0; j < 4; j++)SIDE_CAP_VBO[ j + cnt ] 	= TMP_BUFF[j]; //actual swap



}

cnt = cnt + 4;               //move along to new face
}

}


}



void DrawStartCaps(TachoGLModel<double> * model)
{


glVertexPointer(3, 		GL_DOUBLE, 	sizeof(t3dpoint<double>), 	&START_CAP_VBO[0]	);
int i;


for (i=0; i < model->VBO_BE.Length; i++)
glDrawArrays(GL_TRIANGLE_FAN, model->VBO_BE[i].INDEX_START , model->VBO_BE[i].length);




}

void DrawEndCaps(TachoGLModel<double> * model)
{

glVertexPointer(3, 		GL_DOUBLE, 	sizeof(t3dpoint<double>), 	&END_CAP_VBO[0]	);
int i; 

for (i=0; i < model->VBO_BE.Length; i++)
glDrawArrays(GL_TRIANGLE_FAN, model->VBO_BE[i].INDEX_START , model->VBO_BE[i].length);

}





void DrawSideCaps(TachoGLModel<double> * model)
{
glVertexPointer(3, 		GL_DOUBLE, 	sizeof(t3dpoint<double>), 	&SIDE_CAP_VBO[0]	);
int i;  int x;           int cnt = 0;

for (i=0; i < model->VBO_BE.Length; i++)
for (x=0; x < model->VBO_BE[i].length; x++)
{
glDrawArrays(GL_TRIANGLE_FAN,  cnt , 4);
cnt = cnt + 4;
}




}

































void RenderShadows(TachoGLModel<double> * model)
{
bool specialDepth = glIsEnabled(GL_DEPTH_TEST);
if (!specialDepth) glEnable(GL_DEPTH_TEST);

glDisableClientState(GL_NORMAL_ARRAY_EXT);
glDisableClientState(GL_TEXTURE_COORD_ARRAY);
glEnable( GL_VERTEX_PROGRAM_ARB );
PICK_SHADER.Bind();
SetShaderMatrix(AMODEL, AVIEW, APROJ);
SendParamToShader(0.0,0.0,0.0, 1.0,  5);



glColorMask(GL_FALSE,GL_FALSE,GL_FALSE,GL_FALSE);
model->DrawSimpleModel(NULL);


glDepthMask(GL_FALSE);

 glFrontFace(GL_CW);
glEnable(GL_CULL_FACE);


glEnable(GL_STENCIL_TEST);
glClear(GL_STENCIL_BUFFER_BIT);
 glDepthFunc(GL_LESS); // We change the z-testing function to LESS, to avoid little bugs in shadow

 glStencilFunc(GL_ALWAYS, 0, 0); // We always draw whatever we have in the stencil buffer




	glCullFace(GL_FRONT);
	glStencilOp(GL_KEEP, GL_INCR, GL_KEEP);


	DrawStartCaps(model); DrawEndCaps(model); DrawSideCaps(model);


	glCullFace(GL_BACK);
	glStencilOp(GL_KEEP, GL_DECR, GL_KEEP);

	DrawStartCaps(model); DrawEndCaps(model); DrawSideCaps(model);


	 glDepthFunc(GL_LEQUAL);


		 glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); // We enable color buffer
		 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP); // Drawing will not affect the stencil buffer
		 glStencilFunc(GL_EQUAL,  0x0, 0xff); // And the most important thing, the stencil function. Drawing if equal to 0



SendParamToShader(1.0,1.0,1.0, 1.0,  5);

	model->DrawSimpleModel(NULL);
 	 glDepthMask(GL_TRUE);
		 glDisable(GL_CULL_FACE);
	glDisable(GL_STENCIL_TEST);


glDisable( GL_VERTEX_PROGRAM_ARB );
glEnableClientState(GL_NORMAL_ARRAY_EXT);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);
}
          

};




#endif