Commits

Jake Todd  committed 3ae0cd8

first commit

  • Participants

Comments (0)

Files changed (34)

File light/entities.c

+// entities.c
+
+#include "light.h"
+
+entity_t entities[MAX_MAP_ENTITIES];
+int num_entities;
+
+/*
+==============================================================================
+
+ENTITY FILE PARSING
+
+If a light has a targetname, generate a unique style in the 32-63 range
+==============================================================================
+*/
+
+int numlighttargets;
+char lighttargets[32][64];
+
+int
+LightStyleForTargetname(char *targetname, qboolean alloc)
+{
+	int i;
+
+	for(i = 0; i < numlighttargets; i++)
+		if(!strcmp(lighttargets[i], targetname))
+			return 32 + i;
+	if(!alloc)
+		return -1;
+	strcpy(lighttargets[i], targetname);
+	numlighttargets++;
+	return numlighttargets - 1 + 32;
+}
+
+
+/*
+==================
+MatchTargets
+==================
+*/
+void
+MatchTargets(void)
+{
+	int i, j;
+
+	for(i = 0; i < num_entities; i++) {
+		if(!entities[i].target[0])
+			continue;
+
+		for(j = 0; j < num_entities; j++)
+			if(!strcmp(entities[j].targetname, entities[i].target)) {
+				entities[i].targetent = &entities[j];
+				break;
+			}
+		if(j == num_entities) {
+			printf
+				("WARNING: entity at (%i,%i,%i) (%s) has unmatched target\n",
+				 (int)entities[i].origin[0], (int)entities[i].origin[1],
+				 (int)entities[i].origin[2], entities[i].classname);
+			continue;
+		}
+// set the style on the source ent for switchable lights
+		if(entities[j].style) {
+			char s[16];
+
+			entities[i].style = entities[j].style;
+			sprintf(s, "%i", entities[i].style);
+			SetKeyValue(&entities[i], "style", s);
+		}
+	}
+}
+
+
+/*
+==================
+LoadEntities
+==================
+*/
+void
+LoadEntities(void)
+{
+	char *data;
+	entity_t *entity;
+	char key[64];
+	epair_t *epair;
+	double vec[3];
+	
+
+	
+//
+// start parsing
+//
+	num_entities = 0;
+
+// go through all the entities
+	while(1) {
+		// parse the opening brace  
+		data = COM_Parse(data);
+		if(!data)
+			break;
+		if(com_token[0] != '{')
+			Error("LoadEntities: found %s when expecting {", com_token);
+
+		if(num_entities == MAX_MAP_ENTITIES)
+			Error("LoadEntities: MAX_MAP_ENTITIES");
+		entity = &entities[num_entities];
+		num_entities++;
+
+		// go through all the keys in this entity
+		while(1) {
+			int c;
+
+			// parse key
+			data = COM_Parse(data);
+			if(!data)
+				Error("LoadEntities: EOF without closing brace");
+			if(!strcmp(com_token, "}"))
+				break;
+			strcpy(key, com_token);
+
+			// parse value
+			data = COM_Parse(data);
+			if(!data)
+				Error("LoadEntities: EOF without closing brace");
+			c = com_token[0];
+			if(c == '}')
+				Error("LoadEntities: closing brace without data");
+
+			epair = malloc(sizeof(epair_t));
+			memset(epair, 0, sizeof(epair));
+			strcpy(epair->key, key);
+			strcpy(epair->value, com_token);
+			epair->next = entity->epairs;
+			entity->epairs = epair;
+
+			if(!strcmp(key, "classname"))
+				strcpy(entity->classname, com_token);
+			else if(!strcmp(key, "target"))
+				strcpy(entity->target, com_token);
+			else if(!strcmp(key, "targetname"))
+				strcpy(entity->targetname, com_token);
+			else if(!strcmp(key, "origin")) {
+				
+					// scan into doubles, then assign
+					// which makes it vec_t size independent
+					if(sscanf(com_token, "%lf %lf %lf",
+							  &vec[0], &vec[1], &vec[2]) != 3)
+					Error("LoadEntities: not 3 values for origin");
+				
+					
+			} else if(!strncmp(key, "light", 5) || !strcmp(key, "_light")) {
+				entity->light = atof(com_token);
+			} else if(!strcmp(key, "style")) {
+				entity->style = atof(com_token);
+				if((unsigned)entity->style > 254)
+					Error("Bad light style %i (must be 0-254)",
+						  entity->style);
+			} else if(!strcmp(key, "angle")) {
+				entity->angle = atof(com_token);
+			}
+
+		}
+
+		// all fields have been parsed
+		if(!strncmp(entity->classname, "light", 5) && !entity->light)
+			entity->light = DEFAULTLIGHTLEVEL;
+
+		if(!strcmp(entity->classname, "light")) {
+			if(entity->targetname[0] && !entity->style) {
+				char s[16];
+
+				entity->style =
+					LightStyleForTargetname(entity->targetname, true);
+				sprintf(s, "%i", entity->style);
+				SetKeyValue(entity, "style", s);
+			}
+		}
+	}
+
+	printf("%d entities read\n", num_entities);
+
+	MatchTargets();
+}
+
+char *
+ValueForKey(entity_t * ent, char *key)
+{
+	epair_t *ep;
+
+	for(ep = ent->epairs; ep; ep = ep->next)
+		if(!strcmp(ep->key, key))
+			return ep->value;
+	return "";
+}
+
+void
+SetKeyValue(entity_t * ent, char *key, char *value)
+{
+	epair_t *ep;
+
+	for(ep = ent->epairs; ep; ep = ep->next)
+		if(!strcmp(ep->key, key)) {
+			strcpy(ep->value, value);
+			return;
+		}
+	ep = malloc(sizeof(*ep));
+	ep->next = ent->epairs;
+	ent->epairs = ep;
+	strcpy(ep->key, key);
+	strcpy(ep->value, value);
+}
+
+float
+FloatForKey(entity_t * ent, char *key)
+{
+	char *k;
+
+	k = ValueForKey(ent, key);
+	return atof(k);
+}
+
+void
+GetVectorForKey(entity_t * ent, char *key, vec3_t vec)
+{
+	char *k;
+
+	k = ValueForKey(ent, key);
+	sscanf(k, "%lf %lf %lf", &vec[0], &vec[1], &vec[2]);
+}
+
+
+
+/*
+================
+WriteEntitiesToString
+================
+*/
+void
+WriteEntitiesToString(void)
+{
+	char *buf, *end;
+	epair_t *ep;
+	char line[128];
+	int i;
+
+	buf = dentdata;
+	end = buf;
+	*end = 0;
+
+	printf("%i switchable light styles\n", numlighttargets);
+
+	for(i = 0; i < num_entities; i++) {
+		ep = entities[i].epairs;
+		if(!ep)
+			continue;			// ent got removed
+
+		strcat(end, "{\n");
+		end += 2;
+
+		for(ep = entities[i].epairs; ep; ep = ep->next) {
+			sprintf(line, "\"%s\" \"%s\"\n", ep->key, ep->value);
+			strcat(end, line);
+			end += strlen(line);
+		}
+		strcat(end, "}\n");
+		end += 2;
+
+		if(end > buf + MAX_MAP_ENTSTRING)
+			Error("Entity text too long");
+	}
+	entdatasize = end - buf + 1;
+}

File light/entities.h

+#define DEFAULTLIGHTLEVEL	300
+
+typedef struct epair_s
+{
+	struct epair_s	*next;
+	char	key[MAX_KEY];
+	char	value[MAX_VALUE];
+} epair_t;
+
+typedef struct entity_s
+{
+	char	classname[64];
+	vec3_t	origin;
+	float	angle;
+	int		light;
+	int		style;
+	char	target[32];
+	char	targetname[32];
+	struct epair_s	*epairs;
+	struct entity_s	*targetent;
+} entity_t;
+
+extern	entity_t	entities[MAX_MAP_ENTITIES];
+extern	int			num_entities;
+
+char 	*ValueForKey (entity_t *ent, char *key);
+void 	SetKeyValue (entity_t *ent, char *key, char *value);
+float	FloatForKey (entity_t *ent, char *key);
+void 	GetVectorForKey (entity_t *ent, char *key, vec3_t vec);
+
+void LoadEntities (void);
+void WriteEntitiesToString (void);

File light/light.c

+// lighting.c
+
+#include "light.h"
+
+/*
+
+NOTES
+-----
+
+*/
+
+float scaledist = 1.0;
+float scalecos = 0.5;
+float rangescale = 0.5;
+
+byte *filebase, *file_p, *file_end;
+
+dmodel_t *bspmodel;
+int bspfileface;				// next surface to dispatch
+
+vec3_t bsp_origin;
+
+qboolean extrasamples;
+
+float minlights[MAX_MAP_FACES];
+
+
+byte *
+GetFileSpace(int size)
+{
+	byte *buf;
+
+	LOCK;
+	file_p = (byte *) (((long)file_p + 3) & ~3);
+	buf = file_p;
+	file_p += size;
+	UNLOCK;
+	if(file_p > file_end)
+		Error("GetFileSpace: overrun");
+	return buf;
+}
+
+
+void
+LightThread(void *junk)
+{
+	int i;
+
+	while(1) {
+		LOCK;
+		i = bspfileface++;
+		UNLOCK;
+		if(i >= numfaces)
+			return;
+
+		LightFace(i);
+	}
+}
+
+/*
+=============
+LightWorld
+=============
+*/
+void
+LightWorld(void)
+{
+	filebase = file_p = dlightdata;
+	file_end = filebase + MAX_MAP_LIGHTING;
+
+	RunThreadsOn(LightThread);
+
+	lightdatasize = file_p - filebase;
+
+	printf("lightdatasize: %i\n", lightdatasize);
+}
+
+
+/*
+========
+main
+
+light modelfile
+========
+*/
+int
+main(int argc, char **argv)
+{
+	int i;
+	double start, end;
+	char source[1024];
+
+	printf("----- LightFaces ----\n");
+
+	for(i = 1; i < argc; i++) {
+		if(!strcmp(argv[i], "-threads")) {
+			numthreads = atoi(argv[i + 1]);
+			i++;
+		} else if(!strcmp(argv[i], "-extra")) {
+			extrasamples = true;
+			printf("extra sampling enabled\n");
+		} else if(!strcmp(argv[i], "-dist")) {
+			scaledist = atof(argv[i + 1]);
+			i++;
+		} else if(!strcmp(argv[i], "-range")) {
+			rangescale = atof(argv[i + 1]);
+			i++;
+		} else if(argv[i][0] == '-')
+			Error("Unknown option \"%s\"", argv[i]);
+		else
+			break;
+	}
+
+	if(i != argc - 1)
+		Error("usage: light [-threads num] [-extra] bspfile");
+
+	InitThreads();
+
+	start = I_FloatTime();
+
+	strcpy(source, argv[i]);
+	StripExtension(source);
+	DefaultExtension(source, ".bsp");
+
+	LoadBSPFile(source);
+	LoadEntities();
+
+	MakeTnodes(&dmodels[0]);
+
+	LightWorld();
+
+	WriteEntitiesToString();
+	WriteBSPFile(source);
+
+	end = I_FloatTime();
+	printf("%5.1f seconds elapsed\n", end - start);
+
+	return 0;
+}

File light/light.h

+#include "cmdlib.h"
+#include "mathlib.h"
+#include "bspfile.h"
+#include "entities.h"
+#include "threads.h"
+
+#define	ON_EPSILON	0.1
+
+#define	MAXLIGHTS			1024
+
+void LoadNodes (char *file);
+qboolean TestLine (vec3_t start, vec3_t stop);
+
+void LightFace (int surfnum);
+void LightLeaf (dleaf_t *leaf);
+
+void MakeTnodes (dmodel_t *bm);
+
+extern	float		scaledist;
+extern	float		scalecos;
+extern	float		rangescale;
+
+extern	int		c_culldistplane, c_proper;
+
+byte *GetFileSpace (int size);
+extern	byte		*filebase;
+
+extern	vec3_t	bsp_origin;
+extern	vec3_t	bsp_xvector;
+extern	vec3_t	bsp_yvector;
+
+void TransformSample (vec3_t in, vec3_t out);
+void RotateSample (vec3_t in, vec3_t out);
+
+extern	qboolean	extrasamples;
+
+extern	float		minlights[MAX_MAP_FACES];

File light/ltface.c

+
+#include "light.h"
+
+/*
+============
+CastRay
+
+Returns the distance between the points, or -1 if blocked
+=============
+*/
+vec_t
+CastRay(vec3_t p1, vec3_t p2)
+{
+	int i;
+	vec_t t;
+	qboolean trace;
+
+	trace = TestLine(p1, p2);
+
+	if(!trace)
+		return -1;				// ray was blocked
+
+	t = 0;
+	for(i = 0; i < 3; i++)
+		t += (p2[i] - p1[i]) * (p2[i] - p1[i]);
+
+	if(t == 0)
+		t = 1;					// don't blow up...
+	return sqrt(t);
+}
+
+/*
+===============================================================================
+
+SAMPLE POINT DETERMINATION
+
+void SetupBlock (dface_t *f) Returns with surfpt[] set
+
+This is a little tricky because the lightmap covers more area than the face.
+If done in the straightforward fashion, some of the
+sample points will be inside walls or on the other side of walls, causing
+false shadows and light bleeds.
+
+To solve this, I only consider a sample point valid if a line can be drawn
+between it and the exact midpoint of the face.  If invalid, it is adjusted
+towards the center until it is valid.
+
+(this doesn't completely work)
+
+===============================================================================
+*/
+
+#define	SINGLEMAP	(18*18*4)
+
+typedef struct {
+	vec_t lightmaps[MAXLIGHTMAPS][SINGLEMAP];
+	int numlightstyles;
+	vec_t *light;
+	vec_t facedist;
+	vec3_t facenormal;
+
+	int numsurfpt;
+	vec3_t surfpt[SINGLEMAP];
+
+	vec3_t texorg;
+	vec3_t worldtotex[2];		// s = (world - texorg) . worldtotex[0]
+	vec3_t textoworld[2];		// world = texorg + s * textoworld[0]
+
+	vec_t exactmins[2], exactmaxs[2];
+
+	int texmins[2], texsize[2];
+	int lightstyles[256];
+	int surfnum;
+	dface_t *face;
+} lightinfo_t;
+
+
+/*
+================
+CalcFaceVectors
+
+Fills in texorg, worldtotex. and textoworld
+================
+*/
+void
+CalcFaceVectors(lightinfo_t * l)
+{
+	texinfo_t *tex;
+	int i, j;
+	vec3_t texnormal;
+	float distscale;
+	vec_t dist, len;
+
+	tex = &texinfo[l->face->texinfo];
+
+// convert from float to vec_t
+	for(i = 0; i < 2; i++)
+		for(j = 0; j < 3; j++)
+			l->worldtotex[i][j] = tex->vecs[i][j];
+
+// calculate a normal to the texture axis.  points can be moved along this
+// without changing their S/T
+	texnormal[0] = tex->vecs[1][1] * tex->vecs[0][2]
+		- tex->vecs[1][2] * tex->vecs[0][1];
+	texnormal[1] = tex->vecs[1][2] * tex->vecs[0][0]
+		- tex->vecs[1][0] * tex->vecs[0][2];
+	texnormal[2] = tex->vecs[1][0] * tex->vecs[0][1]
+		- tex->vecs[1][1] * tex->vecs[0][0];
+	VectorNormalize(texnormal);
+
+// flip it towards plane normal
+	distscale = DotProduct(texnormal, l->facenormal);
+	if(!distscale)
+		Error("Texture axis perpendicular to face");
+	if(distscale < 0) {
+		distscale = -distscale;
+		VectorSubtract(vec3_origin, texnormal, texnormal);
+	}
+// distscale is the ratio of the distance along the texture normal to
+// the distance along the plane normal
+	distscale = 1 / distscale;
+
+	for(i = 0; i < 2; i++) {
+		len = VectorLength(l->worldtotex[i]);
+		dist = DotProduct(l->worldtotex[i], l->facenormal);
+		dist *= distscale;
+		VectorMA(l->worldtotex[i], -dist, texnormal, l->textoworld[i]);
+		VectorScale(l->textoworld[i], (1 / len) * (1 / len),
+					l->textoworld[i]);
+	}
+
+
+// calculate texorg on the texture plane
+	for(i = 0; i < 3; i++)
+		l->texorg[i] =
+			-tex->vecs[0][3] * l->textoworld[0][i] -
+			tex->vecs[1][3] * l->textoworld[1][i];
+
+// project back to the face plane
+	dist = DotProduct(l->texorg, l->facenormal) - l->facedist - 1;
+	dist *= distscale;
+	VectorMA(l->texorg, -dist, texnormal, l->texorg);
+
+}
+
+/*
+================
+CalcFaceExtents
+
+Fills in s->texmins[] and s->texsize[]
+also sets exactmins[] and exactmaxs[]
+================
+*/
+void
+CalcFaceExtents(lightinfo_t * l)
+{
+	dface_t *s;
+	vec_t mins[2], maxs[2], val;
+	int i, j, e;
+	dvertex_t *v;
+	texinfo_t *tex;
+
+	s = l->face;
+
+	mins[0] = mins[1] = 999999;
+	maxs[0] = maxs[1] = -99999;
+
+	tex = &texinfo[s->texinfo];
+
+	for(i = 0; i < s->numedges; i++) {
+		e = dsurfedges[s->firstedge + i];
+		if(e >= 0)
+			v = dvertexes + dedges[e].v[0];
+		else
+			v = dvertexes + dedges[-e].v[1];
+
+		for(j = 0; j < 2; j++) {
+			val = v->point[0] * tex->vecs[j][0] +
+				v->point[1] * tex->vecs[j][1] +
+				v->point[2] * tex->vecs[j][2] + tex->vecs[j][3];
+			if(val < mins[j])
+				mins[j] = val;
+			if(val > maxs[j])
+				maxs[j] = val;
+		}
+	}
+
+	for(i = 0; i < 2; i++) {
+		l->exactmins[i] = mins[i];
+		l->exactmaxs[i] = maxs[i];
+
+		mins[i] = floor(mins[i] / 16);
+		maxs[i] = ceil(maxs[i] / 16);
+
+		l->texmins[i] = mins[i];
+		l->texsize[i] = maxs[i] - mins[i];
+		if(l->texsize[i] > 17)
+			Error("Bad surface extents");
+	}
+}
+
+/*
+=================
+CalcPoints
+
+For each texture aligned grid point, back project onto the plane
+to get the world xyz value of the sample point
+=================
+*/
+int c_bad;
+void
+CalcPoints(lightinfo_t * l)
+{
+	int i;
+	int s, t, j;
+	int w, h, step;
+	vec_t starts, startt, us, ut;
+	vec_t *surf;
+	vec_t mids, midt;
+	vec3_t facemid, move;
+
+//
+// fill in surforg
+// the points are biased towards the center of the surface
+// to help avoid edge cases just inside walls
+//
+	surf = l->surfpt[0];
+	mids = (l->exactmaxs[0] + l->exactmins[0]) / 2;
+	midt = (l->exactmaxs[1] + l->exactmins[1]) / 2;
+
+	for(j = 0; j < 3; j++)
+		facemid[j] =
+			l->texorg[j] + l->textoworld[0][j] * mids +
+			l->textoworld[1][j] * midt;
+
+	if(extrasamples) {			// extra filtering
+		h = (l->texsize[1] + 1) * 2;
+		w = (l->texsize[0] + 1) * 2;
+		starts = (l->texmins[0] - 0.5) * 16;
+		startt = (l->texmins[1] - 0.5) * 16;
+		step = 8;
+	} else {
+		h = l->texsize[1] + 1;
+		w = l->texsize[0] + 1;
+		starts = l->texmins[0] * 16;
+		startt = l->texmins[1] * 16;
+		step = 16;
+	}
+
+	l->numsurfpt = w * h;
+	for(t = 0; t < h; t++) {
+		for(s = 0; s < w; s++, surf += 3) {
+			us = starts + s * step;
+			ut = startt + t * step;
+
+			// if a line can be traced from surf to facemid, the point is good
+			for(i = 0; i < 6; i++) {
+				// calculate texture point
+				for(j = 0; j < 3; j++)
+					surf[j] = l->texorg[j] + l->textoworld[0][j] * us
+						+ l->textoworld[1][j] * ut;
+
+				if(CastRay(facemid, surf) != -1)
+					break;		// got it
+				if(i & 1) {
+					if(us > mids) {
+						us -= 8;
+						if(us < mids)
+							us = mids;
+					} else {
+						us += 8;
+						if(us > mids)
+							us = mids;
+					}
+				} else {
+					if(ut > midt) {
+						ut -= 8;
+						if(ut < midt)
+							ut = midt;
+					} else {
+						ut += 8;
+						if(ut > midt)
+							ut = midt;
+					}
+				}
+
+				// move surf 8 pixels towards the center
+				VectorSubtract(facemid, surf, move);
+				VectorNormalize(move);
+				VectorMA(surf, 8, move, surf);
+			}
+			if(i == 2)
+				c_bad++;
+		}
+	}
+
+}
+
+
+/*
+===============================================================================
+
+FACE LIGHTING
+
+===============================================================================
+*/
+
+int c_culldistplane, c_proper;
+
+/*
+================
+SingleLightFace
+================
+*/
+void
+SingleLightFace(entity_t * light, lightinfo_t * l)
+{
+	vec_t dist;
+	vec3_t incoming;
+	vec_t angle;
+	vec_t add;
+	vec_t *surf;
+	qboolean hit;
+	int mapnum;
+	int size;
+	int c, i;
+	vec3_t rel;
+	vec3_t spotvec;
+	vec_t falloff;
+	vec_t *lightsamp;
+
+	VectorSubtract(light->origin, bsp_origin, rel);
+	dist = scaledist * (DotProduct(rel, l->facenormal) - l->facedist);
+
+// don't bother with lights behind the surface
+	if(dist <= 0)
+		return;
+
+// don't bother with light too far away
+	if(dist > light->light) {
+		c_culldistplane++;
+		return;
+	}
+
+	if(light->targetent) {
+		VectorSubtract(light->targetent->origin, light->origin, spotvec);
+		VectorNormalize(spotvec);
+		if(!light->angle)
+			falloff = -cos(20 * Q_PI / 180);
+		else
+			falloff = -cos(light->angle / 2 * Q_PI / 180);
+	} else
+		falloff = 0;			// shut up compiler warnings
+
+	mapnum = 0;
+	for(mapnum = 0; mapnum < l->numlightstyles; mapnum++)
+		if(l->lightstyles[mapnum] == light->style)
+			break;
+	lightsamp = l->lightmaps[mapnum];
+	if(mapnum == l->numlightstyles) {	// init a new light map
+		if(mapnum == MAXLIGHTMAPS) {
+			printf("WARNING: Too many light styles on a face\n");
+			return;
+		}
+		size = (l->texsize[1] + 1) * (l->texsize[0] + 1);
+		for(i = 0; i < size; i++)
+			lightsamp[i] = 0;
+	}
+//
+// check it for real
+//
+	hit = false;
+	c_proper++;
+
+	surf = l->surfpt[0];
+	for(c = 0; c < l->numsurfpt; c++, surf += 3) {
+		dist = CastRay(light->origin, surf) * scaledist;
+		if(dist < 0)
+			continue;			// light doesn't reach
+
+		VectorSubtract(light->origin, surf, incoming);
+		VectorNormalize(incoming);
+		angle = DotProduct(incoming, l->facenormal);
+		if(light->targetent) {	// spotlight cutoff
+			if(DotProduct(spotvec, incoming) > falloff)
+				continue;
+		}
+
+		angle = (1.0 - scalecos) + scalecos * angle;
+		add = light->light - dist;
+		add *= angle;
+		if(add < 0)
+			continue;
+		lightsamp[c] += add;
+		if(lightsamp[c] > 1)	// ignore real tiny lights
+			hit = true;
+	}
+
+	if(mapnum == l->numlightstyles && hit) {
+		l->lightstyles[mapnum] = light->style;
+		l->numlightstyles++;	// the style has some real data now
+	}
+}
+
+/*
+============
+FixMinlight
+============
+*/
+void
+FixMinlight(lightinfo_t * l)
+{
+	int i, j;
+	float minlight;
+
+	minlight = minlights[l->surfnum];
+
+// if minlight is set, there must be a style 0 light map
+	if(!minlight)
+		return;
+
+	for(i = 0; i < l->numlightstyles; i++) {
+		if(l->lightstyles[i] == 0)
+			break;
+	}
+	if(i == l->numlightstyles) {
+		if(l->numlightstyles == MAXLIGHTMAPS)
+			return;				// oh well..
+		for(j = 0; j < l->numsurfpt; j++)
+			l->lightmaps[i][j] = minlight;
+		l->lightstyles[i] = 0;
+		l->numlightstyles++;
+	} else {
+		for(j = 0; j < l->numsurfpt; j++)
+			if(l->lightmaps[i][j] < minlight)
+				l->lightmaps[i][j] = minlight;
+	}
+}
+
+
+/*
+============
+LightFace
+============
+*/
+void
+LightFace(int surfnum)
+{
+	dface_t *f;
+	lightinfo_t l;
+	int s, t;
+	int i, j, c;
+	vec_t total;
+	int size;
+	int lightmapwidth, lightmapsize;
+	byte *out;
+	vec_t *light;
+	int w, h;
+
+	f = dfaces + surfnum;
+
+//
+// some surfaces don't need lightmaps
+//
+	f->lightofs = -1;
+	for(j = 0; j < MAXLIGHTMAPS; j++)
+		f->styles[j] = 255;
+
+	if(texinfo[f->texinfo].flags & TEX_SPECIAL) {	// non-lit texture
+		return;
+	}
+
+	memset(&l, 0, sizeof(l));
+	l.surfnum = surfnum;
+	l.face = f;
+
+//
+// rotate plane
+//
+	VectorCopy(dplanes[f->planenum].normal, l.facenormal);
+	l.facedist = dplanes[f->planenum].dist;
+	if(f->side) {
+		VectorSubtract(vec3_origin, l.facenormal, l.facenormal);
+		l.facedist = -l.facedist;
+	}
+
+
+
+	CalcFaceVectors(&l);
+	CalcFaceExtents(&l);
+	CalcPoints(&l);
+
+	lightmapwidth = l.texsize[0] + 1;
+
+	size = lightmapwidth * (l.texsize[1] + 1);
+	if(size > SINGLEMAP)
+		Error("Bad lightmap size");
+
+	for(i = 0; i < MAXLIGHTMAPS; i++)
+		l.lightstyles[i] = 255;
+
+//
+// cast all lights
+//  
+	l.numlightstyles = 0;
+	for(i = 0; i < num_entities; i++)
+		
 {
+		if(entities[i].light)
+			SingleLightFace(&entities[i], &l);
+		
+
+	FixMinlight(&l);
+
+	if(!l.numlightstyles) {		// no light hitting it
+		return;
+	}
+//
+// save out the values
+//
+	for(i = 0; i < MAXLIGHTMAPS; i++)
+		f->styles[i] = l.lightstyles[i];
+
+	lightmapsize = size * l.numlightstyles;
+
+	out = GetFileSpace(lightmapsize);
+	f->lightofs = out - filebase;
+
+// extra filtering
+	h = (l.texsize[1] + 1) * 2;
+	w = (l.texsize[0] + 1) * 2;
+
+	for(i = 0; i < l.numlightstyles; i++) {
+		if(l.lightstyles[i] == 0xff)
+			Error("Wrote empty lightmap");
+		light = l.lightmaps[i];
+		c = 0;
+		for(t = 0; t <= l.texsize[1]; t++)
+			for(s = 0; s <= l.texsize[0]; s++, c++) {
+				if(extrasamples) {	// filtered sample
+					total =
+						light[t * 2 * w + s * 2] + light[t * 2 * w + s * 2 +
+														 1]
+						+ light[(t * 2 + 1) * w + s * 2] +
+						light[(t * 2 + 1) * w + s * 2 + 1];
+					total *= 0.25;
+				} else
+					total = light[c];
+				total *= rangescale;	// scale before clamping
+				if(total > 255)
+					total = 255;
+				if(total < 0)
+					Error("light < 0");
+				*out++ = total;
+			}
+	}
+
+
+}

File light/threads.c

+
+#include "cmdlib.h"
+#include "threads.h"
+
+#ifdef __alpha
+int numthreads = 4;
+pthread_mutex_t *my_mutex;
+#else
+int numthreads = 1;
+#endif
+
+void
+InitThreads(void)
+{
+#ifdef __alpha
+	pthread_mutexattr_t mattrib;
+
+	my_mutex = malloc(sizeof(*my_mutex));
+	if(pthread_mutexattr_create(&mattrib) == -1)
+		Error("pthread_mutex_attr_create failed");
+	if(pthread_mutexattr_setkind_np(&mattrib, MUTEX_FAST_NP) == -1)
+		Error("pthread_mutexattr_setkind_np failed");
+	if(pthread_mutex_init(my_mutex, mattrib) == -1)
+		Error("pthread_mutex_init failed");
+#endif
+}
+
+/*
+===============
+RunThreadsOn
+===============
+*/
+void
+RunThreadsOn(threadfunc_t func)
+{
+#ifdef __alpha
+	pthread_t work_threads[256];
+	pthread_addr_t status;
+	pthread_attr_t attrib;
+	int i;
+
+	if(numthreads == 1) {
+		func(NULL);
+		return;
+	}
+
+	if(pthread_attr_create(&attrib) == -1)
+		Error("pthread_attr_create failed");
+	if(pthread_attr_setstacksize(&attrib, 0x100000) == -1)
+		Error("pthread_attr_setstacksize failed");
+
+	for(i = 0; i < numthreads; i++) {
+		if(pthread_create
+		   (&work_threads[i], attrib, (pthread_startroutine_t) func,
+			(pthread_addr_t) i) == -1)
+			Error("pthread_create failed");
+	}
+
+	for(i = 0; i < numthreads; i++) {
+		if(pthread_join(work_threads[i], &status) == -1)
+			Error("pthread_join failed");
+	}
+#else
+	func(NULL);
+#endif
+}

File light/threads.h

+#ifdef __alpha
+#include <pthread.h>
+extern	pthread_mutex_t	*my_mutex;
+#define	LOCK	pthread_mutex_lock (my_mutex)
+#define	UNLOCK	pthread_mutex_unlock (my_mutex)
+#else
+#define	LOCK
+#define	UNLOCK
+#endif
+
+extern	int		numthreads;
+
+typedef void (threadfunc_t) (void *);
+
+void InitThreads (void);
+void RunThreadsOn ( threadfunc_t func );

File light/trace.c

+// trace.c
+
+#include "light.h"
+
+typedef struct tnode_s {
+	int type;
+	vec3_t normal;
+	float dist;
+	int children[2];
+	int pad;
+} tnode_t;
+
+tnode_t *tnodes, *tnode_p;
+
+/*
+==============
+MakeTnode
+
+Converts the disk node structure into the efficient tracing structure
+==============
+*/
+void
+MakeTnode(int nodenum)
+{
+	tnode_t *t;
+	dplane_t *plane;
+	int i;
+	dnode_t *node;
+
+	t = tnode_p++;
+
+	node = dnodes + nodenum;
+	plane = dplanes + node->planenum;
+
+	t->type = plane->type;
+	VectorCopy(plane->normal, t->normal);
+	t->dist = plane->dist;
+
+	for(i = 0; i < 2; i++) {
+		if(node->children[i] < 0)
+			t->children[i] = dleafs[-node->children[i] - 1].contents;
+		else {
+			t->children[i] = tnode_p - tnodes;
+			MakeTnode(node->children[i]);
+		}
+	}
+
+}
+
+
+/*
+=============
+MakeTnodes
+
+Loads the node structure out of a .bsp file to be used for light occlusion
+=============
+*/
+void
+MakeTnodes(dmodel_t * bm)
+{
+	tnode_p = tnodes = malloc(numnodes * sizeof(tnode_t));
+
+	MakeTnode(0);
+}
+
+
+
+/*
+==============================================================================
+
+LINE TRACING
+
+The major lighting operation is a point to point visibility test, performed
+by recursive subdivision of the line by the BSP tree.
+
+==============================================================================
+*/
+
+typedef struct {
+	vec3_t backpt;
+	int side;
+	int node;
+} tracestack_t;
+
+
+/*
+==============
+TestLine
+==============
+*/
+qboolean
+TestLine(vec3_t start, vec3_t stop)
+{
+	int node;
+	float front, back;
+	tracestack_t *tstack_p;
+	int side;
+	float frontx, fronty, frontz, backx, backy, backz;
+	tracestack_t tracestack[64];
+	tnode_t *tnode;
+
+	frontx = start[0];
+	fronty = start[1];
+	frontz = start[2];
+	backx = stop[0];
+	backy = stop[1];
+	backz = stop[2];
+
+	tstack_p = tracestack;
+	node = 0;
+
+	while(1) {
+		while(node < 0 && node != CONTENTS_SOLID) {
+			// pop up the stack for a back side
+			tstack_p--;
+			if(tstack_p < tracestack)
+				return true;
+			node = tstack_p->node;
+
+			// set the hit point for this plane
+
+			frontx = backx;
+			fronty = backy;
+			frontz = backz;
+
+			// go down the back side
+
+			backx = tstack_p->backpt[0];
+			backy = tstack_p->backpt[1];
+			backz = tstack_p->backpt[2];
+
+			node = tnodes[tstack_p->node].children[!tstack_p->side];
+		}
+
+		if(node == CONTENTS_SOLID)
+			return false;		// DONE!
+
+		tnode = &tnodes[node];
+
+		switch (tnode->type) {
+		case PLANE_X:
+			front = frontx - tnode->dist;
+			back = backx - tnode->dist;
+			break;
+		case PLANE_Y:
+			front = fronty - tnode->dist;
+			back = backy - tnode->dist;
+			break;
+		case PLANE_Z:
+			front = frontz - tnode->dist;
+			back = backz - tnode->dist;
+			break;
+		default:
+			front =
+				(frontx * tnode->normal[0] + fronty * tnode->normal[1] +
+				 frontz * tnode->normal[2]) - tnode->dist;
+			back =
+				(backx * tnode->normal[0] + backy * tnode->normal[1] +
+				 backz * tnode->normal[2]) - tnode->dist;
+			break;
+		}
+
+		if(front > -ON_EPSILON && back > -ON_EPSILON)
+//      if (front > 0 && back > 0)
+		{
+			node = tnode->children[0];
+			continue;
+		}
+
+		if(front < ON_EPSILON && back < ON_EPSILON)
+//      if (front <= 0 && back <= 0)
+		{
+			node = tnode->children[1];
+			continue;
+		}
+
+		side = front < 0;
+
+		front = front / (front - back);
+
+		tstack_p->node = node;
+		tstack_p->side = side;
+		tstack_p->backpt[0] = backx;
+		tstack_p->backpt[1] = backy;
+		tstack_p->backpt[2] = backz;
+
+		tstack_p++;
+
+		backx = frontx + front * (backx - frontx);
+		backy = fronty + front * (backy - fronty);
+		backz = frontz + front * (backz - frontz);
+
+		node = tnode->children[side];
+	}
+}

File qbsp/brush.c

+// brush.c
+
+#include "bsp5.h"
+
+int numbrushplanes;
+plane_t planes[MAX_MAP_PLANES];
+
+int numbrushfaces;
+mface_t faces[128];				// beveled clipping hull can generate many extra
+
+
+/*
+=================
+CheckFace
+
+Note: this will not catch 0 area polygons
+=================
+*/
+void
+CheckFace(face_t * f)
+{
+	int i, j;
+	vec_t *p1, *p2;
+	vec_t d, edgedist;
+	vec3_t dir, edgenormal, facenormal;
+
+	if(f->numpoints < 3)
+		Error("CheckFace: %i points", f->numpoints);
+
+	VectorCopy(planes[f->planenum].normal, facenormal);
+	if(f->planeside) {
+		VectorSubtract(vec3_origin, facenormal, facenormal);
+	}
+
+	for(i = 0; i < f->numpoints; i++) {
+		p1 = f->pts[i];
+
+		for(j = 0; j < 3; j++)
+			if(p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
+				Error("CheckFace: BUGUS_RANGE: %f", p1[j]);
+
+		j = i + 1 == f->numpoints ? 0 : i + 1;
+
+		// check the point is on the face plane
+		d = DotProduct(p1,
+					   planes[f->planenum].normal) - planes[f->planenum].dist;
+		if(d < -ON_EPSILON || d > ON_EPSILON)
+			Error("CheckFace: point off plane");
+
+		// check the edge isn't degenerate
+		p2 = f->pts[j];
+		VectorSubtract(p2, p1, dir);
+
+		if(VectorLength(dir) < ON_EPSILON)
+			Error("CheckFace: degenerate edge");
+
+		CrossProduct(facenormal, dir, edgenormal);
+		VectorNormalize(edgenormal);
+		edgedist = DotProduct(p1, edgenormal);
+		edgedist += ON_EPSILON;
+
+		// all other points must be on front side
+		for(j = 0; j < f->numpoints; j++) {
+			if(j == i)
+				continue;
+			d = DotProduct(f->pts[j], edgenormal);
+			if(d > edgedist)
+				Error("CheckFace: non-convex");
+		}
+	}
+}
+
+
+//===========================================================================
+
+/*
+=================
+ClearBounds
+=================
+*/
+void
+ClearBounds(brushset_t * bs)
+{
+	int i, j;
+
+	for(j = 0; j < NUM_HULLS; j++)
+		for(i = 0; i < 3; i++) {
+			bs->mins[i] = 99999;
+			bs->maxs[i] = -99999;
+		}
+}
+
+/*
+=================
+AddToBounds
+=================
+*/
+void
+AddToBounds(brushset_t * bs, vec3_t v)
+{
+	int i;
+
+	for(i = 0; i < 3; i++) {
+		if(v[i] < bs->mins[i])
+			bs->mins[i] = v[i];
+		if(v[i] > bs->maxs[i])
+			bs->maxs[i] = v[i];
+	}
+}
+
+//===========================================================================
+
+int
+PlaneTypeForNormal(vec3_t normal)
+{
+	float ax, ay, az;
+
+// NOTE: should these have an epsilon around 1.0?       
+	if(normal[0] == 1.0)
+		return PLANE_X;
+	if(normal[1] == 1.0)
+		return PLANE_Y;
+	if(normal[2] == 1.0)
+		return PLANE_Z;
+	if(normal[0] == -1.0 || normal[1] == -1.0 || normal[2] == -1.0)
+		Error("PlaneTypeForNormal: not a canonical vector");
+
+	ax = fabs(normal[0]);
+	ay = fabs(normal[1]);
+	az = fabs(normal[2]);
+
+	if(ax >= ay && ax >= az)
+		return PLANE_ANYX;
+	if(ay >= ax && ay >= az)
+		return PLANE_ANYY;
+	return PLANE_ANYZ;
+}
+
+#define	DISTEPSILON		0.01
+#define	ANGLEEPSILON	0.00001
+
+void
+NormalizePlane(plane_t * dp)
+{
+	vec_t ax, ay, az;
+
+	if(dp->normal[0] == -1.0) {
+		dp->normal[0] = 1.0;
+		dp->dist = -dp->dist;
+	}
+	if(dp->normal[1] == -1.0) {
+		dp->normal[1] = 1.0;
+		dp->dist = -dp->dist;
+	}
+	if(dp->normal[2] == -1.0) {
+		dp->normal[2] = 1.0;
+		dp->dist = -dp->dist;
+	}
+
+	if(dp->normal[0] == 1.0) {
+		dp->type = PLANE_X;
+		return;
+	}
+	if(dp->normal[1] == 1.0) {
+		dp->type = PLANE_Y;
+		return;
+	}
+	if(dp->normal[2] == 1.0) {
+		dp->type = PLANE_Z;
+		return;
+	}
+
+	ax = fabs(dp->normal[0]);
+	ay = fabs(dp->normal[1]);
+	az = fabs(dp->normal[2]);
+
+	if(ax >= ay && ax >= az)
+		dp->type = PLANE_ANYX;
+	else if(ay >= ax && ay >= az)
+		dp->type = PLANE_ANYY;
+	else
+		dp->type = PLANE_ANYZ;
+	if(dp->normal[dp->type - PLANE_ANYX] < 0) {
+		VectorSubtract(vec3_origin, dp->normal, dp->normal);
+		dp->dist = -dp->dist;
+	}
+
+}
+
+/*
+===============
+FindPlane
+
+Returns a global plane number and the side that will be the front
+===============
+*/
+int
+FindPlane(plane_t * dplane, int *side)
+{
+	int i;
+	plane_t *dp, pl;
+	vec_t dot;
+
+	dot = VectorLength(dplane->normal);
+	if(dot < 1.0 - ANGLEEPSILON || dot > 1.0 + ANGLEEPSILON)
+		Error("FindPlane: normalization error");
+
+	pl = *dplane;
+	NormalizePlane(&pl);
+	if(DotProduct(pl.normal, dplane->normal) > 0)
+		*side = 0;
+	else
+		*side = 1;
+
+	dp = planes;
+	for(i = 0; i < numbrushplanes; i++, dp++) {
+		dot = DotProduct(dp->normal, pl.normal);
+		if(dot > 1.0 - ANGLEEPSILON && fabs(dp->dist - pl.dist) < DISTEPSILON) {	// regular match
+			return i;
+		}
+	}
+
+	if(numbrushplanes == MAX_MAP_PLANES)
+		Error("numbrushplanes == MAX_MAP_PLANES");
+
+	planes[numbrushplanes] = pl;
+
+	numbrushplanes++;
+
+	return numbrushplanes - 1;
+}
+
+
+/*
+===============
+FindPlane_old
+
+Returns a global plane number and the side that will be the front
+===============
+*/
+int
+FindPlane_old(plane_t * dplane, int *side)
+{
+	int i;
+	plane_t *dp;
+	vec_t dot, ax, ay, az;
+
+	dot = VectorLength(dplane->normal);
+	if(dot < 1.0 - ANGLEEPSILON || dot > 1.0 + ANGLEEPSILON)
+		Error("FindPlane: normalization error");
+
+	dp = planes;
+
+	for(i = 0; i < numbrushplanes; i++, dp++) {
+		dot = DotProduct(dplane->normal, dp->normal);
+		if(dot > 1.0 - ANGLEEPSILON && fabs(dplane->dist - dp->dist) < DISTEPSILON) {	// regular match
+			*side = 0;
+			return i;
+		}
+		if(dot < -1.0 + ANGLEEPSILON && fabs(dplane->dist + dp->dist) < DISTEPSILON) {	// inverse of vector
+			*side = 1;
+			return i;
+		}
+	}
+
+// allocate a new plane, flipping normal to a consistant direction
+// if needed
+	*dp = *dplane;
+
+	if(numbrushplanes == MAX_MAP_PLANES)
+		Error("numbrushplanes == MAX_MAP_PLANES");
+	numbrushplanes++;
+
+	*side = 0;
+
+// NOTE: should these have an epsilon around 1.0?       
+	if(dplane->normal[0] == 1.0)
+		dp->type = PLANE_X;
+	else if(dplane->normal[1] == 1.0)
+		dp->type = PLANE_Y;
+	else if(dplane->normal[2] == 1.0)
+		dp->type = PLANE_Z;
+	else if(dplane->normal[0] == -1.0) {
+		dp->type = PLANE_X;
+		dp->normal[0] = 1.0;
+		dp->dist = -dp->dist;
+		*side = 1;
+	} else if(dplane->normal[1] == -1.0) {
+		dp->type = PLANE_Y;
+		dp->normal[1] = 1.0;
+		dp->dist = -dp->dist;
+		*side = 1;
+	} else if(dplane->normal[2] == -1.0) {
+		dp->type = PLANE_Z;
+		dp->normal[2] = 1.0;
+		dp->dist = -dp->dist;
+		*side = 1;
+	} else {
+		ax = fabs(dplane->normal[0]);
+		ay = fabs(dplane->normal[1]);
+		az = fabs(dplane->normal[2]);
+
+		if(ax >= ay && ax >= az)
+			dp->type = PLANE_ANYX;
+		else if(ay >= ax && ay >= az)
+			dp->type = PLANE_ANYY;
+		else
+			dp->type = PLANE_ANYZ;
+		if(dplane->normal[dp->type - PLANE_ANYX] < 0) {
+			VectorSubtract(vec3_origin, dp->normal, dp->normal);
+			dp->dist = -dp->dist;
+			*side = 1;
+		}
+	}
+
+	return i;
+}
+
+
+
+/*
+=============================================================================
+
+			TURN BRUSHES INTO GROUPS OF FACES
+
+=============================================================================
+*/
+
+vec3_t brush_mins, brush_maxs;
+face_t *brush_faces;
+
+/*
+=================
+CreateBrushFaces
+=================
+*/
+#define	ZERO_EPSILON	0.001
+void
+CreateBrushFaces(void)
+{
+	int i, j, k;
+	vec_t r;
+	face_t *f;
+	winding_t *w;
+	plane_t plane;
+	mface_t *mf;
+
+	brush_mins[0] = brush_mins[1] = brush_mins[2] = 99999;
+	brush_maxs[0] = brush_maxs[1] = brush_maxs[2] = -99999;
+
+	brush_faces = NULL;
+
+	for(i = 0; i < numbrushfaces; i++) {
+		mf = &faces[i];
+
+		w = BaseWindingForPlane(&mf->plane);
+
+		for(j = 0; j < numbrushfaces && w; j++) {
+			if(j == i)
+				continue;
+			// flip the plane, because we want to keep the back side
+			VectorSubtract(vec3_origin, faces[j].plane.normal, plane.normal);
+			plane.dist = -faces[j].plane.dist;
+
+			w = ClipWinding(w, &plane, false);
+		}
+
+		if(!w)
+			continue;			// overcontrained plane
+
+		// this face is a keeper
+		f = AllocFace();
+		f->numpoints = w->numpoints;
+		if(f->numpoints > MAXEDGES)
+			Error("f->numpoints > MAXEDGES");
+
+		for(j = 0; j < w->numpoints; j++) {
+			for(k = 0; k < 3; k++) {
+				r = Q_rint(w->points[j][k]);
+				if(fabs(w->points[j][k] - r) < ZERO_EPSILON)
+					f->pts[j][k] = r;
+				else
+					f->pts[j][k] = w->points[j][k];
+
+				if(f->pts[j][k] < brush_mins[k])
+					brush_mins[k] = f->pts[j][k];
+				if(f->pts[j][k] > brush_maxs[k])
+					brush_maxs[k] = f->pts[j][k];
+			}
+
+		}
+		FreeWinding(w);
+		f->texturenum = mf->texinfo;
+		f->planenum = FindPlane(&mf->plane, &f->planeside);
+		f->next = brush_faces;
+		brush_faces = f;
+		CheckFace(f);
+	}
+}
+
+
+
+/*
+==============================================================================
+
+BEVELED CLIPPING HULL GENERATION
+
+This is done by brute force, and could easily get a lot faster if anyone cares.
+==============================================================================
+*/
+
+vec3_t hull_size[3][2] = {
+	{{0, 0, 0}
+	 , {0, 0, 0}
+	 }
+	,
+	{{-16, -16, -32}
+	 , {16, 16, 24}
+	 }
+	,
+	{{-32, -32, -64}
+	 , {32, 32, 24}
+	 }
+
+};
+
+#define	MAX_HULL_POINTS	32
+#define	MAX_HULL_EDGES	64
+
+int num_hull_points;
+vec3_t hull_points[MAX_HULL_POINTS];
+vec3_t hull_corners[MAX_HULL_POINTS * 8];
+int num_hull_edges;
+int hull_edges[MAX_HULL_EDGES][2];
+
+/*
+============
+AddBrushPlane
+=============
+*/
+void
+AddBrushPlane(plane_t * plane)
+{
+	int i;
+	plane_t *pl;
+	float l;
+
+	if(numbrushfaces == MAX_FACES)
+		Error("AddBrushPlane: numbrushfaces == MAX_FACES");
+	l = VectorLength(plane->normal);
+	if(l < 0.999 || l > 1.001)
+		Error("AddBrushPlane: bad normal");
+
+	for(i = 0; i < numbrushfaces; i++) {
+		pl = &faces[i].plane;
+		if(VectorCompare(pl->normal, plane->normal)
+		   && fabs(pl->dist - plane->dist) < ON_EPSILON)
+			return;
+	}
+	faces[i].plane = *plane;
+	faces[i].texinfo = faces[0].texinfo;
+	numbrushfaces++;
+}
+
+
+/*
+============
+TestAddPlane
+
+Adds the given plane to the brush description if all of the original brush
+vertexes can be put on the front side
+=============
+*/
+void
+TestAddPlane(plane_t * plane)
+{
+	int i, c;
+	vec_t d;
+	vec_t *corner;
+	plane_t flip;
+	vec3_t inv;
+	int counts[3];
+	plane_t *pl;
+
+// see if the plane has allready been added
+	for(i = 0; i < numbrushfaces; i++) {
+		pl = &faces[i].plane;
+		if(VectorCompare(plane->normal, pl->normal)
+		   && fabs(plane->dist - pl->dist) < ON_EPSILON)
+			return;
+		VectorSubtract(vec3_origin, plane->normal, inv);
+		if(VectorCompare(inv, pl->normal)
+		   && fabs(plane->dist + pl->dist) < ON_EPSILON)
+			return;
+	}
+
+// check all the corner points
+	counts[0] = counts[1] = counts[2] = 0;
+	c = num_hull_points * 8;
+
+	corner = hull_corners[0];
+	for(i = 0; i < c; i++, corner += 3) {
+		d = DotProduct(corner, plane->normal) - plane->dist;
+		if(d < -ON_EPSILON) {
+			if(counts[0])
+				return;
+			counts[1]++;
+		} else if(d > ON_EPSILON) {
+			if(counts[1])
+				return;
+			counts[0]++;
+		} else
+			counts[2]++;
+	}
+
+// the plane is a seperator
+
+	if(counts[0]) {
+		VectorSubtract(vec3_origin, plane->normal, flip.normal);
+		flip.dist = -plane->dist;
+		plane = &flip;
+	}
+
+	AddBrushPlane(plane);
+}
+
+/*
+============
+AddHullPoint
+
+Doesn't add if duplicated
+=============
+*/
+int
+AddHullPoint(vec3_t p, int hullnum)
+{
+	int i;
+	vec_t *c;
+	int x, y, z;
+
+	for(i = 0; i < num_hull_points; i++)
+		if(VectorCompare(p, hull_points[i]))
+			return i;
+
+	VectorCopy(p, hull_points[num_hull_points]);
+
+	c = hull_corners[i * 8];
+
+	for(x = 0; x < 2; x++)
+		for(y = 0; y < 2; y++)
+			for(z = 0; z < 2; z++) {
+				c[0] = p[0] + hull_size[hullnum][x][0];
+				c[1] = p[1] + hull_size[hullnum][y][1];
+				c[2] = p[2] + hull_size[hullnum][z][2];
+				c += 3;
+			}
+
+	if(num_hull_points == MAX_HULL_POINTS)
+		Error("MAX_HULL_POINTS");
+
+	num_hull_points++;
+
+	return i;
+}
+
+
+/*
+============
+AddHullEdge
+
+Creates all of the hull planes around the given edge, if not done allready
+=============
+*/
+void
+AddHullEdge(vec3_t p1, vec3_t p2, int hullnum)
+{
+	int pt1, pt2;
+	int i;
+	int a, b, c, d, e;
+	vec3_t edgevec, planeorg, planevec;
+	plane_t plane;
+	vec_t l;
+
+	pt1 = AddHullPoint(p1, hullnum);
+	pt2 = AddHullPoint(p2, hullnum);
+
+	for(i = 0; i < num_hull_edges; i++)
+		if((hull_edges[i][0] == pt1 && hull_edges[i][1] == pt2)
+		   || (hull_edges[i][0] == pt2 && hull_edges[i][1] == pt1))
+			return;				// allread added
+
+	if(num_hull_edges == MAX_HULL_EDGES)
+		Error("MAX_HULL_EDGES");
+
+	hull_edges[i][0] = pt1;
+	hull_edges[i][1] = pt2;
+	num_hull_edges++;
+
+	VectorSubtract(p1, p2, edgevec);
+	VectorNormalize(edgevec);
+
+	for(a = 0; a < 3; a++) {
+		b = (a + 1) % 3;
+		c = (a + 2) % 3;
+		for(d = 0; d <= 1; d++)
+			for(e = 0; e <= 1; e++) {
+				VectorCopy(p1, planeorg);
+				planeorg[b] += hull_size[hullnum][d][b];
+				planeorg[c] += hull_size[hullnum][e][c];
+
+				VectorCopy(vec3_origin, planevec);
+				planevec[a] = 1;
+
+				CrossProduct(planevec, edgevec, plane.normal);
+				l = VectorLength(plane.normal);
+				if(l < 1 - ANGLEEPSILON || l > 1 + ANGLEEPSILON)
+					continue;
+				plane.dist = DotProduct(planeorg, plane.normal);
+				TestAddPlane(&plane);
+			}
+	}
+
+
+}
+
+/*
+============
+ExpandBrush
+=============
+*/
+void
+ExpandBrush(int hullnum)
+{
+	int i, x, s;
+	vec3_t corner;
+	face_t *f;
+	plane_t plane, *p;
+
+	num_hull_points = 0;
+	num_hull_edges = 0;
+
+// create all the hull points
+	for(f = brush_faces; f; f = f->next)
+		for(i = 0; i < f->numpoints; i++)
+			AddHullPoint(f->pts[i], hullnum);
+
+// expand all of the planes
+	for(i = 0; i < numbrushfaces; i++) {
+		p = &faces[i].plane;
+		VectorCopy(vec3_origin, corner);
+		for(x = 0; x < 3; x++) {
+			if(p->normal[x] > 0)
+				corner[x] = hull_size[hullnum][1][x];
+			else if(p->normal[x] < 0)
+				corner[x] = hull_size[hullnum][0][x];
+		}
+		p->dist += DotProduct(corner, p->normal);
+	}
+
+// add any axis planes not contained in the brush to bevel off corners
+	for(x = 0; x < 3; x++)
+		for(s = -1; s <= 1; s += 2) {
+			// add the plane
+			VectorCopy(vec3_origin, plane.normal);
+			plane.normal[x] = s;
+			if(s == -1)
+				plane.dist = -brush_mins[x] + -hull_size[hullnum][0][x];
+			else
+				plane.dist = brush_maxs[x] + hull_size[hullnum][1][x];
+			AddBrushPlane(&plane);
+		}
+
+// add all of the edge bevels
+	for(f = brush_faces; f; f = f->next)
+		for(i = 0; i < f->numpoints; i++)
+			AddHullEdge(f->pts[i], f->pts[(i + 1) % f->numpoints], hullnum);
+}
+
+//============================================================================
+
+
+/*
+===============
+LoadBrush
+
+Converts a mapbrush to a bsp brush
+===============
+*/
+brush_t *
+LoadBrush(mbrush_t * mb, int hullnum)
+{
+	brush_t *b;
+	int contents;
+	char *name;
+	mface_t *f;
+
+//
+// check texture name for attributes
+//  
+	name = miptex[texinfo[mb->faces->texinfo].miptex];
+
+	if(!Q_strcasecmp(name, "clip") && hullnum == 0)
+		return NULL;			// "clip" brushes don't show up in the draw hull
+
+	if(name[0] == '*' && worldmodel)	// entities never use water merging
+	{
+		if(!Q_strncasecmp(name + 1, "lava", 4))
+			contents = CONTENTS_LAVA;
+		else if(!Q_strncasecmp(name + 1, "slime", 5))
+			contents = CONTENTS_SLIME;
+		else
+			contents = CONTENTS_WATER;
+	} else if(!Q_strncasecmp(name, "sky", 3) && worldmodel && hullnum == 0)
+		contents = CONTENTS_SKY;
+	else
+		contents = CONTENTS_SOLID;
+
+	if(hullnum && contents != CONTENTS_SOLID && contents != CONTENTS_SKY)
+		return NULL;			// water brushes don't show up in clipping hulls
+
+// no seperate textures on clip hull
+
+//
+// create the faces
+//
+	brush_faces = NULL;
+
+	numbrushfaces = 0;
+	for(f = mb->faces; f; f = f->next) {
+		faces[numbrushfaces] = *f;
+		if(hullnum)
+			faces[numbrushfaces].texinfo = 0;
+		numbrushfaces++;
+	}
+
+	CreateBrushFaces();
+
+	if(!brush_faces) {
+		printf("WARNING: couldn't create brush faces\n");
+		return NULL;
+	}
+
+	if(hullnum) {
+		ExpandBrush(hullnum);
+		CreateBrushFaces();
+	}
+//
+// create the brush
+//
+	b = AllocBrush();
+
+	b->contents = contents;
+	b->faces = brush_faces;
+	VectorCopy(brush_mins, b->mins);
+	VectorCopy(brush_maxs, b->maxs);
+
+	return b;
+}
+
+//=============================================================================
+
+
+/*
+============
+Brush_DrawAll
+
+============
+*/
+void
+Brush_DrawAll(brushset_t * bs)
+{
+	brush_t *b;
+	face_t *f;
+
+	for(b = bs->brushes; b; b = b->next)
+		for(f = b->faces; f; f = f->next)
+			Draw_DrawFace(f);
+}
+
+
+/*
+============
+Brush_LoadEntity
+============
+*/
+brushset_t *
+Brush_LoadEntity(entity_t * ent, int hullnum)
+{
+	brush_t *b, *next, *water, *other;
+	mbrush_t *mbr;
+	int numbrushes;
+	brushset_t *bset;
+
+	bset = malloc(sizeof(brushset_t));
+	memset(bset, 0, sizeof(brushset_t));
+	ClearBounds(bset);
+
+	numbrushes = 0;
+	other = water = NULL;
+
+	qprintf("--- Brush_LoadEntity ---\n");
+
+	for(mbr = ent->brushes; mbr; mbr = mbr->next) {
+		b = LoadBrush(mbr, hullnum);
+		if(!b)
+			continue;
+
+		numbrushes++;
+
+		if(b->contents != CONTENTS_SOLID) {
+			b->next = water;
+			water = b;
+		} else {
+			b->next = other;
+			other = b;
+		}
+
+		AddToBounds(bset, b->mins);
+		AddToBounds(bset, b->maxs);
+	}
+
+// add all of the water textures at the start
+	for(b = water; b; b = next) {
+		next = b->next;
+		b->next = other;
+		other = b;
+	}
+
+	bset->brushes = other;
+
+	brushset = bset;
+	Brush_DrawAll(bset);
+
+	qprintf("%i brushes read\n", numbrushes);
+
+	return bset;
+}
+#include "../common/cmdlib.h"
+#include "../common/mathlib.h"
+#include "../common/bspfile.h"
+
+typedef struct {
+	vec3_t	normal;
+	vec_t	dist;
+	int		type;
+} plane_t;
+
+
+#include "map.h"
+
+#define	MAX_THREADS	4
+
+#define	ON_EPSILON	0.05
+#define	BOGUS_RANGE	18000
+
+// the exact bounding box of the brushes is expanded some for the headnode
+// volume.  is this still needed?
+#define	SIDESPACE	24
+
+typedef struct {
+	int		numpoints;
+	vec3_t	points[8];			// variable sized
+} winding_t;
+
+#define MAX_POINTS_ON_WINDING	64
+
+winding_t *BaseWindingForPlane (plane_t *p);
+void CheckWinding (winding_t *w);
+winding_t	*NewWinding (int points);
+void		FreeWinding (winding_t *w);
+winding_t	*CopyWinding (winding_t *w);
+winding_t	*ClipWinding (winding_t *in, plane_t *split, qboolean keepon);
+void	DivideWinding (winding_t *in, plane_t *split, winding_t **front, winding_t **back);
+
+#define	MAXEDGES			32
+#define	MAXPOINTS			28		// don't let a base face get past this
+									// because it can be split more later
+
+typedef struct visfacet_s {
+	struct visfacet_s	*next;
+	
+	int				planenum;
+	int				planeside;	// which side is the front of the face
+	int				texturenum;
+	int				contents[2];	// 0 = front side
+
+	struct visfacet_s	*original;		// face on node
+	int				outputnumber;		// only valid for original faces after
+										// write surfaces
+	int				numpoints;
+	vec3_t			pts[MAXEDGES];		// FIXME: change to use winding_t
+	int				edges[MAXEDGES];
+} face_t;
+
+typedef struct surface_s {
+	struct surface_s	*next;
+	struct surface_s	*original;	// before BSP cuts it up
+	int			planenum;
+	int			outputplanenum;		// only valid after WriteSurfacePlanes
+	vec3_t		mins, maxs;
+	qboolean		onnode;				// true if surface has already been used
+									// as a splitting node
+	face_t		*faces;	// links to all the faces on either side of the surf
+} surface_t;
+
+
+// there is a node_t structure for every node and leaf in the bsp tree
+#define	PLANENUM_LEAF		-1
+
+typedef struct node_s {
+	vec3_t			mins,maxs;		// bounding volume, not just points inside