bspconv.c

quake 游戏原代码

/* bspstruc.c */
#include "ray.h"
#include "globals.h"
#include "idbsp.h"
#include "sortseg.h"
#include <mem.h>
						  
#define Get_Sec_From_SSec(x) ((Seg_List+((x)->seg_start))->ld->s[(short)(Seg_List+((x)->seg_start))->left_sidedef]->sec)

						  
/*
id              secstore_i;
id              mapvertexstore_i;
id              subsecstore_i;
id              maplinestore_i;
id              nodestore_i;
id              mapthingstore_i;
id              ldefstore_i;
id              sdefstore_i;
*/

STORAGE *subsecstore_i;
STORAGE *maplinestore_i;
STORAGE *nodestore_i;

void * MyRealloc(void * ptr, long old_size, long new_size) {
	void * temp_ptr=SafeMalloc(new_size);
	memmove(temp_ptr, ptr, old_size);
	Free_Mem(ptr);
	return temp_ptr;
}

/*
===============================================================================

							PROCESSING

===============================================================================
*/

/*
=================
=
= LineFromSeg
=
=================
*/

void LineFromSeg(mapseg_t * seg, line_t * line) {
memset(line, 0, sizeof(line));
line->p1.x=Vector_List[seg->v1].x;
line->p1.y=Vector_List[seg->v1].y;
line->p2.x=Vector_List[seg->v2].x;
line->p2.y=Vector_List[seg->v2].y;
}

/*
=================
=
= UniqueVertex
=
= Returns the vertex number, adding a new vertex if needed
=================
*/

int UniqueVertex (int x, int y)
{
	int                             i, count;
	vector2             mv;
	pvector2 mvp;

	mv.x = x;
	mv.y = y;

/* see if an identical vertex already exists */
/*
	count = [mapvertexstore_i count];
	mvp = [mapvertexstore_i elementAt:0];
*/
	count = Number_Of_Vectors;
	mvp=Vector_List;
	for (i=0 ; i<count ; i++, mvp++)
		if (mvp->x == mv.x && mvp->y == mv.y)
			return i;

/*      [mapvertexstore_i addElement: &mv]; */
	Number_Of_Vectors++;
	Vector_List = (pvector2)MyRealloc(Vector_List,
	sizeof(vector2) * (Number_Of_Vectors-1),
		  sizeof(vector2) * (Number_Of_Vectors));
	memcpy(Vector_List+Number_Of_Vectors-1, &mv,                         
					sizeof(vector2));


	return count;
}


/*
=============================================================================
*/

float   bbox[4];

/*
=================
=
= AddPointToBBox
=
=================
*/

void AddPointToBBox (float x, float y)
{
	if (x < bbox[BOXLEFT])
		bbox[BOXLEFT] = x;
	if (x > bbox[BOXRIGHT])
		bbox[BOXRIGHT] = x;

	if (y > bbox[BOXTOP])
		bbox[BOXTOP] = y;
	if (y < bbox[BOXBOTTOM])
		bbox[BOXBOTTOM] = y;
}


/*
=================
=
= ProcessLines
=
= Adds the lines in a subsector to the mapline storage
=================
*/

/* void ProcessLines (id store_i) */
void ProcessLines(STORAGE *store_i)
{
	int                     i,count;
	line_t          *wline;
	mapseg_t        line;
	short           angle;
	float           fangle;

	bbox[BOXLEFT] = INT_MAX;
	bbox[BOXRIGHT] = INT_MIN;
	bbox[BOXTOP] = INT_MIN;
	bbox[BOXBOTTOM] = INT_MAX;

/*      count = [store_i count]; */
	count = store_i->count;
	for (i=0 ; i<count ; i++)
	{
/*              wline = [store_i elementAt: i]; */
		wline = (line_t *)store_i->data + i;
		if (wline->grouped)
			printf ("ERROR: line regrouped\n");
		wline->grouped = true;

		memset (&line, 0, sizeof(line));
		AddPointToBBox (wline->p1.x, wline->p1.y);
		AddPointToBBox (wline->p2.x, wline->p2.y);
		line.v1 = UniqueVertex (wline->p1.x, wline->p1.y);
		line.v2 = UniqueVertex (wline->p2.x, wline->p2.y);
		line.linedef = wline->linedef;
		line.side = wline->side;
		line.offset = wline->offset;
		fangle = atan2 (wline->p2.y - wline->p1.y, wline->p2.x - wline->p1.x);
/************************ CHANGED BY MATT! *********************************/                
		angle = (short)(fangle/(PI*2)*ANGLE_360);
		if (angle<0) angle+=ANGLE_360; // get rid of negative angles
/************************ END CHANGED BY MATT! *****************************/
		line.angle = angle;
/*              [maplinestore_i addElement: &line]; */
		memcpy((mapseg_t *)maplinestore_i->data + maplinestore_i->count, &line,
						sizeof(line));
		maplinestore_i->count += 1;
		maplinestore_i->data = (mapseg_t *)MyRealloc(maplinestore_i->data,
			sizeof(mapseg_t) * (maplinestore_i->count),
						 sizeof(mapseg_t) * (maplinestore_i->count+1));
	}
}

/*
=================
=
= FinishCut
=
= Cuts a box agains lines in sub sector ****MADE BY MATT****
=================
*/

STORAGE * FinishCut(mapsubsector_t * cur_ssec, STORAGE * cutbox_i)
{
STORAGE * new_front;
STORAGE * back_temp;
STORAGE * cur_list;
short cur_seg_index;             
mapseg_t * cur_seg;
line_t spliton;
cur_list=cutbox_i;

for (cur_seg_index=0; cur_seg_index<cur_ssec->numsegs; cur_seg_index++) {
	cur_seg=(mapseg_t *)maplinestore_i->data+cur_ssec->firstseg+cur_seg_index;        
	LineFromSeg(cur_seg, &spliton); 
	
	new_front=(STORAGE *)SafeMalloc(sizeof(STORAGE));
	new_front->count = 0;
	new_front->size = sizeof(vector2);
	new_front->data = (pvector2)SafeMalloc(sizeof(vector2));

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

	SplitCutBoxes(cur_list, &spliton, new_front, back_temp);
	
	Free_Mem(back_temp->data);
	Free_Mem(back_temp);
	Free_Mem(cur_list->data);
	Free_Mem(cur_list);

	cur_list=new_front;
}
return cur_list;
}

/*
=================
=
= Makes alternate bound box, using cut box
=
=================
*/

void Make_Alt_BBox(mapsubsector_t * cur_ssec) {
	pvector2 cur_vec;
	short count, counter;

	bbox[BOXLEFT] = INT_MAX;
	bbox[BOXRIGHT] = INT_MIN;
	bbox[BOXTOP] = INT_MIN;
	bbox[BOXBOTTOM] = INT_MAX;

  count=cur_ssec->cutbox->count;
  for (counter=0; counter<count; counter++) {
	  cur_vec=(pvector2)cur_ssec->cutbox->data+counter;
	  AddPointToBBox(cur_vec->x, cur_vec->y);
	}
}

/*         
=================
=
= ProcessSubsector
=
=================
*/

/* int ProcessSubsector (id wmaplinestore_i) */
int ProcessSubsector(STORAGE *wmaplinestore_i, STORAGE *cutbox_i)
{
	int                             count;
	worldline_t             *linedef;
	line_t                  *wline;
	mapsubsector_t  sub;

	memset (&sub,0,sizeof(sub));

/*      count = [wmaplinestore_i count]; */
	count = wmaplinestore_i->count;
	if (count < 1)
		Error ("ProcessSubsector: count = %i",count);

/*      wline = [wmaplinestore_i elementAt: 0]; */
	wline = wmaplinestore_i->data;

/*      linedef = [linestore_i elementAt: wline->linedef]; */
	linedef = (worldline_t *)linestore_i->data + wline->linedef;
				sub.numsegs = count;
/*      sub.firstseg = [maplinestore_i count]; */
				sub.firstseg = maplinestore_i->count;
				ProcessLines (wmaplinestore_i);

	sub.cutbox=FinishCut(&sub, cutbox_i); 
		  Make_Alt_BBox(&sub);

	
/* add the new subsector
				[subsecstore_i addElement: &sub];
*/
				memcpy((mapsubsector_t *)subsecstore_i->data + subsecstore_i->count, &sub,
																				sizeof(mapsubsector_t));
				subsecstore_i->count += 1;
				subsecstore_i->data = (mapsubsector_t *)MyRealloc(subsecstore_i->data,
											  sizeof(mapsubsector_t) * (subsecstore_i->count),
										sizeof(mapsubsector_t) * (subsecstore_i->count + 1));

/*      return [subsecstore_i count]-1; */
				return subsecstore_i->count - 1;
}

/*
=================
=
= ProcessNode
=
=================
*/

int ProcessNode (bspnode_t *node, short *totalbox)
{
	short           subbox[2][4];
	int                     i, r;
	mapnode_t       mnode;

	memset (&mnode,0,sizeof(mnode));

	if (node->lines_i)      /* NF_SUBSECTOR flags a subsector */
	{
		r = ProcessSubsector (node->lines_i, node->cutbox_i);
		for (i=0 ; i<4 ; i++)
			totalbox[i] = bbox[i];
		return r | NF_SUBSECTOR;
	}

	mnode.x =node->divline.pt.x;
	mnode.y =node->divline.pt.y;
	mnode.dx =node->divline.dx;
	mnode.dy =node->divline.dy;

	r = ProcessNode(node->side[0], subbox[0]);
	mnode.children[0] =r;
	for (i=0 ; i<4 ; i++)
		mnode.bbox[0][i] =subbox[0][i];

	r = ProcessNode (node->side[1],subbox[1]);
	mnode.children[1] =r;
	for (i=0 ; i<4 ; i++)
		mnode.bbox[1][i] =subbox[1][i];

	totalbox[BOXLEFT] = MIN(subbox[0][BOXLEFT], subbox[1][BOXLEFT]);
	totalbox[BOXTOP] = MAX(subbox[0][BOXTOP], subbox[1][BOXTOP]);
	totalbox[BOXRIGHT] = MAX(subbox[0][BOXRIGHT], subbox[1][BOXRIGHT]);
	totalbox[BOXBOTTOM] = MIN(subbox[0][BOXBOTTOM], subbox[1][BOXBOTTOM]);

/*      [nodestore_i addElement: &mnode]; */
	memcpy((mapnode_t *)nodestore_i->data + nodestore_i->count, &mnode, sizeof(mapnode_t));
	nodestore_i->count += 1;
	nodestore_i->data = (mapnode_t *)MyRealloc(nodestore_i->data,
			  sizeof(mapnode_t) * (nodestore_i->count),
											sizeof(mapnode_t) * (nodestore_i->count + 1));

/*      return [nodestore_i count] - 1; */
	return nodestore_i->count - 1;
}


/*
=================
=
= ProcessNodes
=
= Recursively builds the nodes, subsectors, and line lists,
= then writes the lumps
=================
*/

void ProcessNodes (void)
{
	short   worldbounds[4];
/*
	subsecstore_i = [[Storage alloc]
		initCount:              0
		elementSize:    sizeof(mapsubsector_t)
		description:    NULL];
	maplinestore_i = [[Storage alloc]
		initCount:              0
		elementSize:    sizeof(mapseg_t)
		description:    NULL];
	nodestore_i = [[Storage alloc]
		initCount:              0
		elementSize:    sizeof(mapnode_t)
		description:    NULL];
*/
	subsecstore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	subsecstore_i->data = (mapsubsector_t *)SafeMalloc(sizeof(mapsubsector_t));
	subsecstore_i->count = 0;
	subsecstore_i->size = sizeof(mapsubsector_t);

	maplinestore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	maplinestore_i->data = (mapseg_t *)SafeMalloc(sizeof(mapseg_t));
	maplinestore_i->count = 0;
	maplinestore_i->size = sizeof(mapseg_t);

	nodestore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	nodestore_i->data = (mapnode_t *)SafeMalloc(sizeof(mapnode_t));
	nodestore_i->count = 0;
	nodestore_i->size = sizeof(mapnode_t);

	ProcessNode (startnode, worldbounds);

}

/*
=============================================================================
*/

/*
==================
=
= ConvertNodes
=
= Converts data to My format ****MADE BY MATT****
==================
*/

void ConvertNodes() {
short counter;
pseg cur_seg;
pssector cur_ssec;
bsp_node * cur_node;
prectl cur_rect;
mapseg_t * cur_doom_seg;
mapsubsector_t * cur_doom_ssec;
mapnode_t * cur_doom_node;
psorted_vector_type sorted_list;

// Seg conversion
Number_Of_Segs=maplinestore_i->count;
Seg_List=(pseg)SafeMalloc(Number_Of_Segs * sizeof(seg));
for (counter=0; counter<Number_Of_Segs; counter++) {
	cur_seg=Seg_List+counter;
	cur_doom_seg=(mapseg_t *)maplinestore_i->data+counter;
	cur_seg->v[0]=cur_doom_seg->v1;
	cur_seg->v[1]=cur_doom_seg->v2;
	cur_seg->angle=cur_doom_seg->angle;
	cur_seg->ld=Ld_List+cur_doom_seg->linedef;
	cur_seg->left_sidedef=(cur_doom_seg->side > 0 ? TRUE : FALSE);
	cur_seg->linedef_offset=cur_doom_seg->offset;
}
Free_Mem(maplinestore_i->data);
Free_Mem(maplinestore_i);

// SubSector conversion
Number_Of_SSectors=subsecstore_i->count;
SS_List=(pssector)SafeMalloc(Number_Of_SSectors * sizeof(ssector));
for (counter=0; counter<Number_Of_SSectors; counter++) {
	cur_ssec=SS_List+counter;
	cur_doom_ssec=(mapsubsector_t *)subsecstore_i->data+counter;
	cur_ssec->seg_start=cur_doom_ssec->firstseg;
	cur_ssec->seg_end=cur_doom_ssec->firstseg+cur_doom_ssec->numsegs-1;
	cur_ssec->flags=Get_Sec_From_SSec(cur_ssec)->flags;
	if (cur_ssec->flags & VOXEL_SSECTOR) {
		sorted_list=(psorted_vector_type)SafeMalloc(sizeof(sorted_vector_type));
		sorted_list->vector_count=cur_doom_ssec->cutbox->count;
		sorted_list->vectors=cur_doom_ssec->cutbox->data;
		cur_ssec->extra_data=(pdata)sorted_list;
	} else { 
		Free_Mem(cur_doom_ssec->cutbox->data);
		Free_Mem(cur_doom_ssec->cutbox);
		cur_ssec->extra_data=NULL;
	}
	cur_ssec->objects=NULL;
	cur_ssec->num_objects=0;                  
}
Free_Mem(subsecstore_i->data);
Free_Mem(subsecstore_i);

// Node conversion
Number_Of_Nodes=nodestore_i->count;
bsp_start_node=nodestore_i->count-1;
bsp_tree=(bsp_node *)SafeMalloc(Number_Of_Nodes * sizeof(bsp_node));
for (counter=0; counter<Number_Of_Nodes; counter++) {
	cur_node=bsp_tree+counter;
	cur_doom_node=(mapnode_t *)nodestore_i->data+counter;
	cur_node->x1=cur_doom_node->x;
	cur_node->y1=cur_doom_node->y;
	cur_node->x2=cur_doom_node->x+cur_doom_node->dx;
	cur_node->y2=cur_doom_node->y+cur_doom_node->dy;
	cur_rect=&(cur_node->left_bound);
	cur_rect->top=cur_doom_node->bbox[1][BOXTOP];
	cur_rect->left=cur_doom_node->bbox[1][BOXLEFT];
	cur_rect->bottom=cur_doom_node->bbox[1][BOXBOTTOM];
	cur_rect->right=cur_doom_node->bbox[1][BOXRIGHT];
	cur_rect=&(cur_node->right_bound);
	cur_rect->top=cur_doom_node->bbox[0][BOXTOP];
	cur_rect->left=cur_doom_node->bbox[0][BOXLEFT];
	cur_rect->bottom=cur_doom_node->bbox[0][BOXBOTTOM];
	cur_rect->right=cur_doom_node->bbox[0][BOXRIGHT];
	cur_node->left_child=cur_doom_node->children[1];
	cur_node->right_child=cur_doom_node->children[0];
} /* endfor */
Free_Mem(nodestore_i->data);
Free_Mem(nodestore_i);

}

/*
==================
=
= Make_Line_List
=
= Makes linedefs usable by bsp generator ****MADE BY MATT*****
==================
*/

void Make_Line_List() {
	short counter;
	plinedef cur_ld;
	worldline_t * cur_doom_ld;

	linestore_i=(STORAGE *)SafeMalloc(sizeof(STORAGE));
	linestore_i->count=Number_Of_Linedefs;
	linestore_i->size=Number_Of_Linedefs * sizeof(worldline_t);
	linestore_i->data=(worldline_t *)SafeMalloc(linestore_i->size);

	for (counter=0; counter<Number_Of_Linedefs; counter++) {
		cur_ld=Ld_List+counter;
		cur_doom_ld=(worldline_t *)linestore_i->data+counter;
		cur_doom_ld->p1.x=Vector_List[cur_ld->v[0]].x;
		cur_doom_ld->p1.y=Vector_List[cur_ld->v[0]].y;
		cur_doom_ld->p2.x=Vector_List[cur_ld->v[1]].x;
		cur_doom_ld->p2.y=Vector_List[cur_ld->v[1]].y;
		cur_doom_ld->tag=cur_ld->tag;
		cur_doom_ld->special=cur_ld->tag_type;
		cur_doom_ld->flags=cur_ld->attributes;
	}
}
 
/*                                      
==================
=
= ConvBSP
=
==================
*/

void ConvBSP (void)
{
	ProcessNodes ();
	ConvertNodes();
}