vis.c

quake3工具源码。包括生成bsp文件

	if (i == f1->numpoints)
		return NULL;			// no matching edges

	//
	// check slope of connected lines
	// if the slopes are colinear, the point can be removed
	//
	back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
	VectorSubtract (p1, back, delta);
	CrossProduct (planenormal, delta, normal);
	VectorNormalize (normal, normal);
	
	back = f2->points[(j+2)%f2->numpoints];
	VectorSubtract (back, p1, delta);
	dot = DotProduct (delta, normal);
	if (dot > CONTINUOUS_EPSILON)
		return NULL;			// not a convex polygon
	keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
	
	back = f1->points[(i+2)%f1->numpoints];
	VectorSubtract (back, p2, delta);
	CrossProduct (planenormal, delta, normal);
	VectorNormalize (normal, normal);

	back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
	VectorSubtract (back, p2, delta);
	dot = DotProduct (delta, normal);
	if (dot > CONTINUOUS_EPSILON)
		return NULL;			// not a convex polygon
	keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);

	//
	// build the new polygon
	//
	newf = NewWinding (f1->numpoints + f2->numpoints);
	
	// copy first polygon
	for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
	{
		if (k==(i+1)%f1->numpoints && !keep2)
			continue;
		
		VectorCopy (f1->points[k], newf->points[newf->numpoints]);
		newf->numpoints++;
	}
	
	// copy second polygon
	for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
	{
		if (l==(j+1)%f2->numpoints && !keep1)
			continue;
		VectorCopy (f2->points[l], newf->points[newf->numpoints]);
		newf->numpoints++;
	}

	return newf;
}

/*
============
MergeLeafPortals
============
*/
void MergeLeafPortals(void)
{
	int i, j, k, nummerges, hintsmerged;
	leaf_t *leaf;
	vportal_t *p1, *p2;
	winding_t *w;

	nummerges = 0;
	hintsmerged = 0;
	for (i = 0; i < portalclusters; i++)
	{
		leaf = &leafs[i];
		if (leaf->merged >= 0) continue;
		for (j = 0; j < leaf->numportals; j++)
		{
			p1 = leaf->portals[j];
			if (p1->removed)
				continue;
			for (k = j+1; k < leaf->numportals; k++)
			{
				p2 = leaf->portals[k];
				if (p2->removed)
					continue;
				if (p1->leaf == p2->leaf)
				{
					w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal);
					if (w)
					{
						FreeWinding(p1->winding);
						p1->winding = w;
						if (p1->hint && p2->hint)
							hintsmerged++;
						p1->hint |= p2->hint;
						SetPortalSphere(p1);
						p2->removed = qtrue;
						nummerges++;
						i--;
						break;
					}
				}
			}
			if (k < leaf->numportals)
				break;
		}
	}
	_printf("%6d portals merged\n", nummerges);
	_printf("%6d hint portals merged\n", hintsmerged);
}


/*
============
WritePortals
============
*/
int CountActivePortals(void)
{
	int num, hints, j;
	vportal_t *p;

	num = 0;
	hints = 0;
	for (j = 0; j < numportals * 2; j++)
	{
		p = portals + j;
		if (p->removed)
			continue;
		if (p->hint)
			hints++;
		num++;
	}
	_printf("%6d active portals\n", num);
	_printf("%6d hint portals\n", hints);
	return num;
}

/*
============
WritePortals
============
*/
void WriteFloat (FILE *f, vec_t v);

void WritePortals(char *filename)
{
	int i, j, num;
	FILE *pf;
	vportal_t *p;
	winding_t *w;

	// write the file
	pf = fopen (filename, "w");
	if (!pf)
		Error ("Error opening %s", filename);

	num = 0;
	for (j = 0; j < numportals * 2; j++)
	{
		p = portals + j;
		if (p->removed)
			continue;
//		if (!p->hint)
//			continue;
		num++;
	}

	fprintf (pf, "%s\n", PORTALFILE);
	fprintf (pf, "%i\n", 0);
	fprintf (pf, "%i\n", num);// + numfaces);
	fprintf (pf, "%i\n", 0);

	for (j = 0; j < numportals * 2; j++)
	{
		p = portals + j;
		if (p->removed)
			continue;
//		if (!p->hint)
//			continue;
		w = p->winding;
		fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
		fprintf (pf, "%d ", p->hint);
		for (i=0 ; i<w->numpoints ; i++)
		{
			fprintf (pf,"(");
			WriteFloat (pf, w->points[i][0]);
			WriteFloat (pf, w->points[i][1]);
			WriteFloat (pf, w->points[i][2]);
			fprintf (pf,") ");
		}
		fprintf (pf,"\n");
	}

	/*
	for (j = 0; j < numfaces; j++)
	{
		p = faces + j;
		w = p->winding;
		fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
		fprintf (pf, "0 ");
		for (i=0 ; i<w->numpoints ; i++)
		{
			fprintf (pf,"(");
			WriteFloat (pf, w->points[i][0]);
			WriteFloat (pf, w->points[i][1]);
			WriteFloat (pf, w->points[i][2]);
			fprintf (pf,") ");
		}
		fprintf (pf,"\n");
	}*/

	fclose (pf);
}

/*
============
LoadPortals
============
*/
void LoadPortals (char *name)
{
	int			i, j, hint;
	vportal_t	*p;
	leaf_t		*l;
	char		magic[80];
	FILE		*f;
	int			numpoints;
	winding_t	*w;
	int			leafnums[2];
	plane_t		plane;
	
	if (!strcmp(name,"-"))
		f = stdin;
	else
	{
		f = fopen(name, "r");
		if (!f)
			Error ("LoadPortals: couldn't read %s\n",name);
	}

	if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4)
		Error ("LoadPortals: failed to read header");
	if (strcmp(magic,PORTALFILE))
		Error ("LoadPortals: not a portal file");

	_printf ("%6i portalclusters\n", portalclusters);
	_printf ("%6i numportals\n", numportals);
	_printf ("%6i numfaces\n", numfaces);

	// these counts should take advantage of 64 bit systems automatically
	leafbytes = ((portalclusters+63)&~63)>>3;
	leaflongs = leafbytes/sizeof(long);
	
	portalbytes = ((numportals*2+63)&~63)>>3;
	portallongs = portalbytes/sizeof(long);

	// each file portal is split into two memory portals
	portals = malloc(2*numportals*sizeof(vportal_t));
	memset (portals, 0, 2*numportals*sizeof(vportal_t));
	
	leafs = malloc(portalclusters*sizeof(leaf_t));
	memset (leafs, 0, portalclusters*sizeof(leaf_t));

	for (i = 0; i < portalclusters; i++)
		leafs[i].merged = -1;

	numVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes;

	((int *)visBytes)[0] = portalclusters;
	((int *)visBytes)[1] = leafbytes;
		
	for (i=0, p=portals ; i<numportals ; i++)
	{
		if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)
			Error ("LoadPortals: reading portal %i", i);
		if (numpoints > MAX_POINTS_ON_WINDING)
			Error ("LoadPortals: portal %i has too many points", i);
		if ( (unsigned)leafnums[0] > portalclusters
		|| (unsigned)leafnums[1] > portalclusters)
			Error ("LoadPortals: reading portal %i", i);
		if (fscanf (f, "%i ", &hint) != 1)
			Error ("LoadPortals: reading hint state");
		
		w = p->winding = NewWinding (numpoints);
		w->numpoints = numpoints;
		
		for (j=0 ; j<numpoints ; j++)
		{
			double	v[3];
			int		k;

			// scanf into double, then assign to vec_t
			// so we don't care what size vec_t is
			if (fscanf (f, "(%lf %lf %lf ) "
			, &v[0], &v[1], &v[2]) != 3)
				Error ("LoadPortals: reading portal %i", i);
			for (k=0 ; k<3 ; k++)
				w->points[j][k] = v[k];
		}
		fscanf (f, "\n");
		
		// calc plane
		PlaneFromWinding (w, &plane);

		// create forward portal
		l = &leafs[leafnums[0]];
		if (l->numportals == MAX_PORTALS_ON_LEAF)
			Error ("Leaf with too many portals");
		l->portals[l->numportals] = p;
		l->numportals++;
		
		p->num = i+1;
		p->hint = hint;
		p->winding = w;
		VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
		p->plane.dist = -plane.dist;
		p->leaf = leafnums[1];
		SetPortalSphere (p);
		p++;
		
		// create backwards portal
		l = &leafs[leafnums[1]];
		if (l->numportals == MAX_PORTALS_ON_LEAF)
			Error ("Leaf with too many portals");
		l->portals[l->numportals] = p;
		l->numportals++;
		
		p->num = i+1;
		p->hint = hint;
		p->winding = NewWinding(w->numpoints);
		p->winding->numpoints = w->numpoints;
		for (j=0 ; j<w->numpoints ; j++)
		{
			VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]);
		}

		p->plane = plane;
		p->leaf = leafnums[0];
		SetPortalSphere (p);
		p++;

	}

	faces = malloc(2*numfaces*sizeof(vportal_t));
	memset (faces, 0, 2*numfaces*sizeof(vportal_t));

	faceleafs = malloc(portalclusters*sizeof(leaf_t));
	memset(faceleafs, 0, portalclusters*sizeof(leaf_t));

	for (i = 0, p = faces; i < numfaces; i++)
	{
		if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2)
			Error ("LoadPortals: reading portal %i", i);

		w = p->winding = NewWinding (numpoints);
		w->numpoints = numpoints;
		
		for (j=0 ; j<numpoints ; j++)
		{
			double	v[3];
			int		k;

			// scanf into double, then assign to vec_t
			// so we don't care what size vec_t is
			if (fscanf (f, "(%lf %lf %lf ) "
			, &v[0], &v[1], &v[2]) != 3)
				Error ("LoadPortals: reading portal %i", i);
			for (k=0 ; k<3 ; k++)
				w->points[j][k] = v[k];
		}
		fscanf (f, "\n");
		
		// calc plane
		PlaneFromWinding (w, &plane);

		l = &faceleafs[leafnums[0]];
		l->merged = -1;
		if (l->numportals == MAX_PORTALS_ON_LEAF)
			Error ("Leaf with too many faces");
		l->portals[l->numportals] = p;
		l->numportals++;
		
		p->num = i+1;
		p->winding = w;
		// normal pointing out of the leaf
		VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
		p->plane.dist = -plane.dist;
		p->leaf = -1;
		SetPortalSphere (p);
		p++;
	}
	
	fclose (f);
}


/*
================
CalcPHS

Calculate the PHS (Potentially Hearable Set)
by ORing together all the PVS visible from a leaf
================
*/
void CalcPHS (void)
{
	int		i, j, k, l, index;
	int		bitbyte;
	long	*dest, *src;
	byte	*scan;
	int		count;
	byte	uncompressed[MAX_MAP_LEAFS/8];

	_printf ("Building PHS...\n");

	count = 0;
	for (i=0 ; i<portalclusters ; i++)
	{
		scan = visBytes + i*leafbytes;
		memcpy (uncompressed, scan, leafbytes);
		for (j=0 ; j<leafbytes ; j++)
		{
			bitbyte = scan[j];
			if (!bitbyte)
				continue;
			for (k=0 ; k<8 ; k++)
			{
				if (! (bitbyte & (1<<k)) )
					continue;
				// OR this pvs row into the phs
				index = ((j<<3)+k);
				if (index >= portalclusters)
					Error ("Bad bit in PVS");	// pad bits should be 0
				src = (long *)(visBytes + index*leafbytes);
				dest = (long *)uncompressed;
				for (l=0 ; l<leaflongs ; l++)
					((long *)uncompressed)[l] |= src[l];
			}
		}
		for (j=0 ; j<portalclusters ; j++)
			if (uncompressed[j>>3] & (1<<(j&7)) )
				count++;

		// FIXME: copy it off
	}

	_printf ("Average clusters hearable: %i\n", count/portalclusters);
}

/*
===========
VisMain
===========
*/
int VisMain (int argc, char **argv)
{
	char		portalfile[1024];
	char		name[1024];
	int		i;
	double		start, end;
		
	_printf ("---- vis ----\n");

	verbose = qfalse;
	for (i=1 ; i<argc ; i++) {
		if (!strcmp(argv[i],"-threads")) {
			numthreads = atoi (argv[i+1]);
			i++;
		} else if (!strcmp(argv[i],"-threads")) {
			numthreads = atoi (argv[i+1]);
			i++;
		} else if (!strcmp(argv[i], "-fast")) {
			_printf ("fastvis = true\n");
			fastvis = qtrue;
		} else if (!strcmp(argv[i], "-merge")) {
			_printf ("merge = true\n");
			mergevis = qtrue;
		} else if (!strcmp(argv[i], "-nopassage")) {
			_printf ("nopassage = true\n");
			nopassagevis = qtrue;
		} else if (!strcmp(argv[i], "-level")) {
			testlevel = atoi(argv[i+1]);
			_printf ("testlevel = %i\n", testlevel);
			i++;
		} else if (!strcmp(argv[i], "-v")) {
			_printf ("verbose = true\n");
			verbose = qtrue;
		} else if (!strcmp (argv[i],"-nosort")) {
			_printf ("nosort = true\n");
			nosort = qtrue;
		} else if (!strcmp (argv[i],"-saveprt")) {
			_printf ("saveprt = true\n");
			saveprt = qtrue;
		} else if (!strcmp (argv[i],"-tmpin")) {
			strcpy (inbase, "/tmp");
		} else if (!strcmp (argv[i],"-tmpout")) {
			strcpy (outbase, "/tmp");
		} else if (argv[i][0] == '-') {
			Error ("Unknown option \"%s\"", argv[i]);
		} else {
			break;
		}
	}

	if (i != argc - 1)
		Error ("usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile");

#ifdef MREDEBUG
	start = clock();
#else
	start = I_FloatTime ();
#endif
	
	ThreadSetDefault ();

	SetQdirFromPath (argv[i]);	

#ifdef _WIN32
  InitPakFile(gamedir, NULL);
#endif

	// load the bsp
	sprintf (name, "%s%s", inbase, ExpandArg(argv[i]));
	StripExtension (name);
	strcat (name, ".bsp");
	_printf ("reading %s\n", name);
	LoadBSPFile (name);

	// load the portal file
	sprintf (portalfile, "%s%s", inbase, ExpandArg(argv[i]));
	StripExtension (portalfile);
	strcat (portalfile, ".prt");
	_printf ("reading %s\n", portalfile);
	LoadPortals (portalfile);

	if (mergevis)
	{
		MergeLeaves();
		MergeLeafPortals();
	}

	CountActivePortals();
//	WritePortals("maps/hints.prs");

	_printf ("visdatasize:%i\n", numVisBytes);

	CalcVis ();

//	CalcPHS ();

	// delete the prt file
	if ( !saveprt ) {
		remove( portalfile );
	}

	// write the bsp file
	_printf ("writing %s\n", name);
	WriteBSPFile (name);

#ifdef MREDEBUG
	end = clock();
	_printf ("%5.2f seconds elapsed\n", (end-start) / CLK_TCK);
#else
	end = I_FloatTime ();
	_printf ("%5.2f seconds elapsed\n", end-start);
#endif
	return 0;
}