// Requries parts of the q3 tools source to compile
// Date: Oct 5, 2001
// Written by: Brad Whitehead (email username: fonfon domain: gmail.com)

#include "./common/qbsp.h"

// settings
qboolean	bspLoaded;
qboolean	ignoreSeen;
qboolean	tracePoint;
int			portalTrace;
int			traceCluster;
vec3_t		traceCoords;

// names
char		bspName[1024];
char		linName[1024];

FILE		*traceFile;

#define		VIS_HEADER_SIZE	8

typedef struct {
	int		portalclusters;
	int		leafbytes;       //leafbytes = ((portalclusters+63)&~63)>>3;
} vis_header;

#define INTRO "VIS Find - v. 0.00 - FonFon\n"

// added because int shift = 32; i = 0xFFFFFFFF >> shift; 
// then i = 0xFFFFFFFF, when it should = 0
const unsigned long bitmasks[33] =
{
	0x00000000,
	0x00000001, 0x00000003, 0x00000007, 0x0000000F,
	0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
	0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
	0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
	0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
	0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
	0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
	0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
};

void PrintUsage()
{
	printf("Usage: visfind options bspFileName.bsp\n\n");
	printf("This program has two modes.  The default mode will search the bsp file for the\n");
	printf("points where the most VIS clusters are visible from.  The second mode \n");
	printf("will process only the specified cluster.  Both modes will output a point\n");
	printf("file that can be loaded with q3radiant (File->Pointfile).\n\n");
	printf("Options:\n");
	printf("-p #\n");
	printf("Creates a point file with clusters visible from the # cluster in the list\n");
	printf("-i\n");
	printf("Ignore already seen clusters when determining clusters with most visible.\n");
	printf("-c # \n");
	printf("Creates a pointfile with all the clusters visible from cluster number #\n");
	printf("-z x y z\n");
	printf("Creates a pointfile with all the clusters visible from point (x,y,z)\n");



	exit(1);
}

int bsp_leafnumfororigin(vec3_t origin)
{
	dnode_t		*node;
	dplane_t	*plane;
	float		d;

	// TODO: check if origin is in the map??

	node = dnodes;
	while (1)
	{
		plane = &dplanes[node->planeNum];
		d = DotProduct (origin, plane->normal) - plane->dist;
		if ( d >= 0 )
			if ( node->children[0] < 0 )
				return(-(node->children[0]+1));
			else
				node = &dnodes[node->children[0]];
		else
			if ( node->children[1] < 0 )
				return(-(node->children[1]+1));
			else
				node = &dnodes[node->children[1]];
	}
	return(0);
}

int bsp_leafnumforcluster(int cluster)
{
	dleaf_t *l;
	int i;

	for ( i = 0, l = dleafs; i < numleafs; i++, l++ )
		if ( l->cluster == cluster ) return(i);
	return(0);
}

// leaf1 = origin leaf
// leaf2 = leaf to test for
int bsp_InPVS(int cluster1, int cluster2)
{
	vis_header		*vheader;
	byte			*visdata;

	vheader = (vis_header *) visBytes;
	visdata = visBytes + VIS_HEADER_SIZE;

	return( *( visdata + ( cluster1 * vheader->leafbytes ) + (cluster2 / 8) ) & ( 1 << ( cluster2 % 8 ) ) );
}

void bsp_setbitvectorlength( byte *v, int length_bits, int length_vector )
{
	int i;

	i = length_bits/8;

	*(v+i) = (byte) bitmasks[length_bits % 8];

	memset((v+i+1), 0, length_vector-i-1);
}


void bsp_bitvectorsubtract(byte *first, byte *second, byte *out, int length)
{

	int i;

	for ( i = 0; i < length; i++ )
		*(out+i) = *(first+i) & ~(*(second+i));
}

int bsp_countclusters(byte *bitvector, int length)
{
	int i, j, c;

	c = 0;
	for ( i = 0; i < length; i++ )
		for ( j = 0; j < 8; j++ )
			if ( (*(bitvector+i) & (1 << j)) ) c++;
	return(c);
}

int bsp_countclusters_mask(byte *bitvector, byte *maskvector, int length)
{
	int i, j, c;

	c = 0;
	for ( i = 0; i < length; i++ )
		for ( j = 0; j < 8; j++ )
			if ( (*(bitvector+i) & (1 << j)) && (*(maskvector+i) & (1 << j)) ) c++;
	return(c);
}

// returns the cluster # for the best camera placement
int bsp_nextcamera(vis_header *header, byte *visdata, byte *seen, int *numSeen)
{
	int i, bestnum, currentseen;

	*numSeen = 0;
	bestnum = 0;

	for ( i = 0; i < header->portalclusters; i++ )
	{
		// if this cluster has already been seen dont process it
		if ( ignoreSeen )
			if ( !(*(seen + (i/8)) & (1 << (i % 8))) ) continue;
		currentseen = bsp_countclusters_mask((visdata + (i * header->leafbytes)), seen, header->leafbytes);
		if (currentseen > *numSeen) 
		{
			*numSeen = currentseen;
			bestnum = i;
		}
	}
	return(bestnum);
}

/*
=============
CreateTrace
=============
*/
void CreateTrace( dleaf_t *leaf, int c, vis_header *header, byte *visdata, byte *seen )
{
	vec3_t		leafOrigin;
	byte		*vis;
	int			i, j, clusterNum;
	dleaf_t		*cl;
	
	if ( !traceFile )
		return;

	printf("Creating Trace File: %s\n", linName);

	vis = visdata + ( c * header->leafbytes );

	leafOrigin[0] = (leaf->maxs[0]+leaf->mins[0])/2;
	leafOrigin[1] = (leaf->maxs[1]+leaf->mins[1])/2;
	leafOrigin[2] = (leaf->maxs[2]+leaf->mins[2])/2;

	clusterNum = 0;

	for ( i = 0; i < header->leafbytes; i++ )
	{
		for ( j = 0; j < 8; j++ )
		{
			if ( ( *(vis + i) & (1 << j) ) && (*(seen+i) & (1 << j)) )
			{
				cl = &(dleafs[bsp_leafnumforcluster( clusterNum )]);
				fprintf(traceFile, "%f %f %f\n",
						((float)(cl->maxs[0]+cl->mins[0]))/2,
						((float)(cl->maxs[1]+cl->mins[1]))/2,
						((float)(cl->maxs[2]+cl->mins[2]))/2 );
				fprintf(traceFile, "%f %f %f\n",
						leafOrigin[0],
						leafOrigin[1],
						leafOrigin[2] );
			}
			clusterNum++;
		}
	}
}


/*
=============
CreateCameras
=============
*/
void bsp_createcameras()
{
	// find the leaf with the greatest number of visible clusters
	// create camera there 
	// mark visible clusters as seen
	// repeat ( minus the marked clusters ) 
	
	int				cluster;
	dleaf_t			*leaf;
	vis_header		*vheader;
	byte			*visdata;
	byte			seen[(MAX_MAP_LEAFS/8) + 1];
	int				i, numSeen;

	if (!bspLoaded)
	{
		printf("bsp_createcameras called without bsp loaded\n");
		return;
	}

	printf("Finding... \n");
	
	numSeen = 0;
	vheader = (vis_header *) visBytes;
	visdata = visBytes + VIS_HEADER_SIZE;

	memset(seen, 0xFF, sizeof(seen));
	bsp_setbitvectorlength(seen, vheader->portalclusters, sizeof(seen));

	i = 0;
	while ( bsp_countclusters(seen, vheader->leafbytes) )
	{
		cluster = bsp_nextcamera( vheader, visdata, seen, &numSeen );
		leaf = &(dleafs[bsp_leafnumforcluster( cluster )]);
		if (leaf->cluster == -1) 
			printf("bsp_createcameras: found solid cluster\n");
		if ( i+1 == portalTrace )
			CreateTrace(leaf, cluster, vheader, visdata, seen);
		bsp_bitvectorsubtract(seen, (visdata + (cluster * vheader->leafbytes)), seen, vheader->leafbytes);
		printf("Coords(x,y,z): %7i %7i %7i numSeen: %4i clusterNum: %i\n",
							(leaf->maxs[0] + leaf->mins[0])/2,
							(leaf->maxs[1] + leaf->mins[1])/2,
							(leaf->maxs[2] + leaf->mins[2])/2,
							numSeen,
							cluster	);	
		i++;
	}
	
	printf("\nNumber of points: %i\n", i);
}


/*
=============
TraceCluster

setup for CreateTrace
=============
*/
void TraceCluster ()
{
	byte			seen[(MAX_MAP_LEAFS/8) + 1];
	vis_header		*vheader;
	byte			*visdata;
	dleaf_t			*leaf;

	if (!bspLoaded)
	{
		printf("bsp_createcameras called without bsp loaded\n");
		return;
	}

	vheader = (vis_header *) visBytes;
	visdata = visBytes + VIS_HEADER_SIZE;

	memset(seen, 0xFF, sizeof(seen));
	bsp_setbitvectorlength(seen, vheader->portalclusters, sizeof(seen));

	leaf = &(dleafs[bsp_leafnumforcluster( traceCluster )]);

	if ( leaf->cluster == -1 )
		printf("WARNING: specified a solid cluster/leaf\n");

	CreateTrace(leaf, traceCluster, vheader, visdata, seen);

}


/*
=============
SetNames

Ensure extensions, create lin name
=============
*/
void SetNames(char *name)
{
	strcpy(bspName, name);
	DefaultExtension(bspName, ".bsp");
	ExtractFileBase(bspName, linName);
	DefaultExtension(linName, ".lin");
}


/*
=============
Init

Init our statics and others
=============
*/
void Init()
{

	bspLoaded = qfalse;
	ignoreSeen = qfalse;
	portalTrace = 0;
	traceFile = NULL;
	traceCluster = 0;
	tracePoint = qfalse;
}


main ( int argc, char *argv[] )
{
	int		i;
	char	*bspname;
	double	start, end;
	dleaf_t *leaf;
	
	printf("%s", INTRO);

	Init();

	// parse command line
	if ( argc < 2 )	PrintUsage();

	for ( i = 1; i < argc-1; i++ )
	{
		switch ( *argv[i] )
		{
		case '-':
			switch (*(argv[i]+1))
			{
			case 'c':
				traceCluster = atoi(argv[i+1]);
				i++;
				break;
			case 'i':
				ignoreSeen = qtrue;
				break;
			case 'p':
				portalTrace = atoi((argv[i+1]));
				i++;
				break;
			case 'z':
				if ( i+3 >= argc )
				{
					printf("must specify three numbers (x, y, z) with the -z option\n");
					exit(1);
				}
				tracePoint = qtrue;
				traceCoords[0] = atof(argv[i+1]);
				traceCoords[1] = atof(argv[i+2]);
				traceCoords[2] = atof(argv[i+3]);
				i += 3;
				break;
			default:
				printf("Unknown option: %s\n", argv[i]);
				PrintUsage();
				break;
			}
			break;
		
		default:
			break;
		}
	}

	bspname = argv[argc-1];

	start = I_FloatTime ();
	
	printf("Loading BSP: %s\n", bspname);
	SetNames(bspname);
	LoadBSPFile(bspName);
	bspLoaded = qtrue;
	
	if ( portalTrace || traceCluster || tracePoint )
		traceFile = SafeOpenWrite(linName);
	
	if ( tracePoint )
	{
		leaf = &dleafs[bsp_leafnumfororigin(traceCoords)];
		traceCluster = leaf->cluster;
		TraceCluster();
	}
	else if ( traceCluster )
	{
		TraceCluster();
	}
	else
	{
		bsp_createcameras();
	}

	if ( portalTrace )
		fclose(traceFile);

	end = I_FloatTime ();

	printf("Elapsed Time %i sec\n", end-start);

}