buildbsp.c

quake 游戏原代码

	DivlineFromWorldline (&divline, spliton);

/*      c = [lines_i count];
*/
	c = lines_i->count;

	for (i=0 ; i<c ; i++)
	{
/*              line_p = [lines_i elementAt:i];
*/
		line_p = (line_t *)lines_i->data + i;
		if (line_p == spliton)
			side = 0;
		else
			side = LineOnSide (line_p, &divline);
		switch (side)
		{
		case 0:
/*                      [frontlist_i addElement: line_p];
*/
			memcpy((line_t *)frontlist_i->data + frontlist_i->count, line_p, sizeof(line_t));
			frontlist_i->count += 1;
			frontlist_i->data = (line_t *)MyRealloc(frontlist_i->data,
			sizeof(line_t) * (frontlist_i->count), sizeof(line_t) * (frontlist_i->count + 1));
			break;
		case 1:
/*                      [backlist_i addElement: line_p];
*/
			memcpy((line_t *)backlist_i->data + backlist_i->count, line_p, sizeof(line_t));
			backlist_i->count += 1;
			backlist_i->data = (line_t *)MyRealloc(backlist_i->data,
				sizeof(line_t) * (backlist_i->count), sizeof(line_t) * (backlist_i->count + 1));
			break;
		case -2:
			newline_p = CutLine (line_p, &divline);
/*                      [frontlist_i addElement: line_p];
			[backlist_i addElement: newline_p];
*/
			memcpy((line_t *)frontlist_i->data + frontlist_i->count, line_p, sizeof(line_t));
			frontlist_i->count += 1;
			frontlist_i->data = (line_t *)MyRealloc(frontlist_i->data,
			sizeof(line_t) * (frontlist_i->count), sizeof(line_t) * (frontlist_i->count + 1));

			memcpy((line_t *)backlist_i->data + backlist_i->count, newline_p, sizeof(line_t));
			backlist_i->count += 1;
			backlist_i->data = (line_t *)MyRealloc(backlist_i->data,
			sizeof(line_t) * (backlist_i->count), sizeof(line_t) * (backlist_i->count + 1));

			break;
		default:
			Error ("ExecuteSplit: bad side");
		}
	}
}

/*
================
=
= SplitCutBoxes
=
= Cuts a box in half along a line ****MADE BY MATT****
================
*/

void SplitCutBoxes(STORAGE * cutbox_i, line_t * spliton, 
	STORAGE * frontlist_i, STORAGE * backlist_i) {

divline_t divline;
short point_count, cur_point, cur_side; 
pvector2 cur_vec, next_vec; 
vector2 new_vec;
line_t cur_line;
line_t * newline_p;

DivlineFromWorldline(&divline, spliton);
point_count=cutbox_i->count;
cur_vec=(pvector2)cutbox_i->data+point_count-1;

for (cur_point=0; cur_point<point_count; cur_point++) {
	next_vec=(pvector2)cutbox_i->data+cur_point;   
	
	LineFromPoints(&cur_line, cur_vec, next_vec);
	cur_side=LineOnSide(&cur_line, &divline); 
	
	switch (cur_side) {
	case 0:

		if (PointOnSide(&(cur_line.p2), &divline)==-1) {
			memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
			backlist_i->count++;
			backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
			sizeof(vector2) *(backlist_i->count),sizeof(vector2) *(backlist_i->count+1));
		}

		memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));          
		frontlist_i->count++;                                                        
		frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
		sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
		break;

	case 1:

		if (PointOnSide(&(cur_line.p2), &divline)==-1) {
			memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));
			frontlist_i->count++;
			frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
			sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
		}

		memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
		backlist_i->count++;
		backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
		sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
		break;
	
	case -2:   
		newline_p=CutLine(&cur_line, &divline);
		
		if ((newline_p->p2.x==next_vec->x) && (newline_p->p2.y==next_vec->y)) {     
	new_vec.x=newline_p->p1.x;
	new_vec.y=newline_p->p1.y;
		} else {                                                             
	new_vec.x=newline_p->p2.x;
	new_vec.y=newline_p->p2.y;
		}

		memcpy((pvector2)frontlist_i->data+frontlist_i->count, &new_vec, sizeof(vector2));
		frontlist_i->count++;
		frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
		sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));

		memcpy((pvector2)backlist_i->data+backlist_i->count, &new_vec, sizeof(vector2));
		backlist_i->count++;
		backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
		sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
	 
		if ((newline_p->p2.x==next_vec->x) && (newline_p->p2.y==next_vec->y)) {
	 memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
	 backlist_i->count++;
	 backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
	 sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
		} else {
	 memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));
	 frontlist_i->count++;
	 frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
	 sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
		}
		break;

	default:
	  Error("Bad Cut Box!");
	  break;
	}
	cur_vec=next_vec;
}
}

/*                              
================
=
= BSPList
=
= Takes a storage of lines and recursively partitions the list
= Returns a bspnode_t
================
*/

/* float        gray = NX_WHITE; */
float gray = 0;                                                            

/* bspnode_t *BSPList (id lines_i)
*/
bspnode_t *BSPList(STORAGE *lines_i, STORAGE * cutbox_i)
{
/*      id                              frontlist_i, backlist_i;
*/
	STORAGE *frontlist_i, *backlist_i;
	STORAGE *cutbacklist_i, *cutfrontlist_i;
	int                             i,c, step;
	line_t                  *line_p, *bestline_p;
	int                             v, bestv;
	bspnode_t               *node_p;
/*
	if (draw)
		PSsetgray (gray);
	gray = 1.0 - gray;
*/

	node_p = (bspnode_t *)Alloc_Mem (sizeof(*node_p));
	memset (node_p, 0, sizeof(*node_p));

/*
 find the best line to partition on
*/

/*      c = [lines_i count];
*/

	c = lines_i->count;
	bestv = INT_MAX;
	bestline_p = NULL;
	step = (c/40)+1;                /* set this to 1 for an exhaustive search */
research:
	for (i=0 ; i<c ; i+=step)
	{
/*              line_p = [lines_i elementAt:i];
*/
		line_p = (line_t *)lines_i->data + i;
		v = EvaluateSplit (lines_i, line_p, bestv);
		if (v<bestv)
		{
			bestv = v;
			bestline_p = line_p;
		}
	}

/*
 if none of the lines should be split, the remaining lines
 are convex, and form a terminal node
*/
/*
printf ("bestv:%i\n",bestv);
*/
	if (bestv == INT_MAX)
	{
		if (step > 1)
		{       /* possible to get here with non convex area if BSPSLIDE specials
				 caused rejections */
			step = 1;
			goto research;
		}
		node_p->lines_i = lines_i;
		node_p->cutbox_i= cutbox_i;
		return node_p;
	}

/*
 divide the line list into two nodes along the best split line
*/
	DivlineFromWorldline (&node_p->divline, bestline_p);
/*
	frontlist_i =
	[[Storage alloc]
		initCount:              0
		elementSize:    sizeof(line_t)
		description:    NULL];
	backlist_i =
	[[Storage alloc]
		initCount:              0
		elementSize:    sizeof(line_t)
		description:    NULL];
*/
	frontlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	frontlist_i->count = 0;
	frontlist_i->size = sizeof(line_t);
	frontlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));

	backlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	backlist_i->count = 0;
	backlist_i->size = sizeof(line_t);
	backlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));

	ExecuteSplit (lines_i, bestline_p, frontlist_i, backlist_i);

	cutfrontlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	cutfrontlist_i->count = 0;
	cutfrontlist_i->size = sizeof(vector2);
	cutfrontlist_i->data = (pvector2)SafeMalloc(sizeof(vector2));

	cutbacklist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	cutbacklist_i->count = 0;
	cutbacklist_i->size = sizeof(vector2);
	cutbacklist_i->data = (pvector2)SafeMalloc(sizeof(vector2));

	SplitCutBoxes(cutbox_i, bestline_p, cutfrontlist_i, cutbacklist_i);

/*
 recursively divide the lists
*/
	node_p->side[0] = BSPList (frontlist_i, cutfrontlist_i);
	node_p->side[1] = BSPList (backlist_i, cutbacklist_i);

	return node_p;
}



/*
=====================
=
= MakeSegs
=
=====================
*/

STORAGE *initialcutbox_i;

void MakeInitialCutBox() {
pvector2 v1,v2,v3,v4;                                                      
long min_x, min_y, max_x, max_y;
pvector2 cur_vec;
short counter;

// Get min and max points of world be looping through vectors

min_x=max_x=Vector_List[0].x;
min_y=max_y=Vector_List[0].y;

for (counter=1; counter < Number_Of_Vectors; counter++) {
	cur_vec=Vector_List+counter;
	if (cur_vec->x < min_x)
		min_x=cur_vec->x;
	if (cur_vec->y < min_y)
		min_y=cur_vec->y;
	if (cur_vec->x > max_x)
		max_x=cur_vec->x;
	if (cur_vec->y > max_y)
		max_y=cur_vec->y;
}

initialcutbox_i=(STORAGE *)SafeMalloc(sizeof(STORAGE));
initialcutbox_i->count=4;
initialcutbox_i->size=4*sizeof(vector2);
initialcutbox_i->data=(pvector2)SafeMalloc(4 * sizeof(vector2));

v1=(pvector2)initialcutbox_i->data+0;
v2=(pvector2)initialcutbox_i->data+1;
v3=(pvector2)initialcutbox_i->data+2;
v4=(pvector2)initialcutbox_i->data+3;

v1->x=min_x;
v1->y=min_y;
v2->x=min_x;
v2->y=max_y;
v3->x=max_x;
v3->y=max_y;
v4->x=max_x;
v4->y=min_y;

}

/* id segstore_i;
*/
STORAGE *segstore_i;

void MakeSegs (void)
{
				int                             i, count;
				worldline_t             *wl;
/* line_t   li;
*/
				line_t                  *li;

/*
				segstore_i =
				[[Storage alloc]
								initCount:              0
								elementSize:    sizeof(line_t)
								description:    NULL];
*/
				segstore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
				segstore_i->data = (line_t *)SafeMalloc(sizeof(line_t));
				segstore_i->count = 0;
				segstore_i->size = sizeof(line_t);

/*
				count = [linestore_i count];
				wl = [linestore_i elementAt:0];
*/
				count = linestore_i->count;
				wl = linestore_i->data;

				li = segstore_i->data;

				for (i= 0 ; i<count ; i++, wl++)
				{
								li->p1 = wl->p1;
								li->p2 = wl->p2;
		li->linedef = i;
		li->side = 0;
		li->offset = 0;
		li->grouped = false;

/*              [segstore_i addElement: &li];
*/
		segstore_i->count += 1;
		segstore_i->data = (line_t *)MyRealloc(segstore_i->data,
		sizeof(line_t) * (segstore_i->count), sizeof(line_t) * (segstore_i->count + 1));
		li = (line_t *)segstore_i->data + segstore_i->count;

		if (wl->flags & ML_TWOSIDED)
		{
			li->p1 = wl->p2;
			li->p2 = wl->p1;
			li->linedef = i;
			li->side = 1;
			li->offset = 0;
			li->grouped = false;
/*                      [segstore_i addElement: &li];
*/
			segstore_i->count += 1;
			segstore_i->data = (line_t *)MyRealloc(segstore_i->data,
			sizeof(line_t) * (segstore_i->count), sizeof(line_t) * (segstore_i->count + 1));
			li = (line_t *)segstore_i->data + segstore_i->count;
		}
	}
}


/*
=====================
=
= BuildBSP
=
=====================
*/

bspnode_t       *startnode;

void BuildBSP (void)
{
	MakeSegs ();
		  MakeInitialCutBox();
	cuts = 0;
	startnode = BSPList (segstore_i, initialcutbox_i);
}