if ( f->w ) {

FreeWinding( f->w );

}

free( f );

face_t *split;

face_t *check;

face_t *bestSplit;

int splits, facing, front, back;

int side;

plane_t *plane;

int value, bestValue;

int i;

vec3_t normal;

float dist;

int planenum;

float sizeBias;

//int frontC,backC,splitsC,facingC;

/* ydnar: set some defaults */

*splitPlaneNum = -1; /* leaf */

*compileFlags = 0;

/* ydnar 2002-06-24: changed this to split on z-axis as well */

/* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */

/* if it is crossing a block boundary, force a split */

for ( i = 0; i < 3; i++ )

{

if ( blockSize[ i ] <= 0 ) {

continue;

}

dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );

if ( node->maxs[ i ] > dist ) {

VectorClear( normal );

normal[ i ] = 1;

planenum = FindFloatPlane( normal, dist, 0, NULL );

*splitPlaneNum = planenum;

return;

}

}

/* pick one of the face planes */

bestValue = -99999;

bestSplit = list;

// div0: this check causes detail/structural mixes

//for( split = list; split; split = split->next )

// split->checked = qfalse;

for ( split = list; split; split = split->next )

{

//if ( split->checked )

// continue;

plane = &mapplanes[ split->planenum ];

splits = 0;

facing = 0;

front = 0;

back = 0;

for ( check = list ; check ; check = check->next ) {

if ( check->planenum == split->planenum ) {

facing++;

//check->checked = qtrue; // won't need to test this plane again

continue;

}

side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );

if ( side == SIDE_CROSS ) {

splits++;

}

else if ( side == SIDE_FRONT ) {

front++;

}

else if ( side == SIDE_BACK ) {

back++;

}

}

if ( bspAlternateSplitWeights ) {

// from 27

//Bigger is better

sizeBias = WindingArea( split->w );

//Base score = 20000 perfectly balanced

value = 20000 - ( abs( front - back ) );

value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again

value -= facing ; // if we're going to have alot of other surfs use this plane, we want to get it in quickly.

value -= splits * 5; //more splits = bad

value += sizeBias * 10; //We want a huge score bias based on plane size

}

else

{

value = 5 * facing - 5 * splits; // - abs(front-back);

if ( plane->type < 3 ) {

value += 5; // axial is better

}

}

value += split->priority; // prioritize hints higher

if ( value > bestValue ) {

bestValue = value;

bestSplit = split;

//frontC=front;

//backC=back;

//splitsC=splits;

//facingC=facing;

}

}

/* nothing, we have a leaf */

if ( bestValue == -99999 ) {

return;

}

//Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );

/* set best split data */

*splitPlaneNum = bestSplit->planenum;

*compileFlags = bestSplit->compileFlags;

#if 0

if ( bestSplit->compileFlags & C_DETAIL ) {

for ( split = list; split; split = split->next )

if ( !( split->compileFlags & C_DETAIL ) ) {

Sys_FPrintf( SYS_ERR, "DON'T DO SUCH SPLITS (1)\n" );

}

}

if ( ( node->compileFlags & C_DETAIL ) && !( bestSplit->compileFlags & C_DETAIL ) ) {

Sys_FPrintf( SYS_ERR, "DON'T DO SUCH SPLITS (2)\n" );

}

#endif

if ( *splitPlaneNum > -1 ) {

mapplanes[ *splitPlaneNum ].counter++;

}

int c;

c = 0;

for ( ; list != NULL; list = list->next )

c++;

return c;

face_t *split;

face_t *next;

int side;

plane_t *plane;

face_t *newFace;

face_t *childLists[2];

winding_t *frontWinding, *backWinding;

int i;

int splitPlaneNum, compileFlags;

#if 0

qboolean isstruct = qfalse;

#endif

/* count faces left */

i = CountFaceList( list );

/* select the best split plane */

SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );

/* if we don't have any more faces, this is a node */

if ( splitPlaneNum == -1 ) {

node->planenum = PLANENUM_LEAF;

node->has_structural_children = qfalse;

c_faceLeafs++;

return;

}

/* partition the list */

node->planenum = splitPlaneNum;

node->compileFlags = compileFlags;

node->has_structural_children = (!( compileFlags & C_DETAIL ) && !node->opaque) ? qtrue : qfalse;

plane = &mapplanes[ splitPlaneNum ];

childLists[0] = NULL;

childLists[1] = NULL;

for ( split = list; split; split = next )

{

/* set next */

next = split->next;

/* don't split by identical plane */

if ( split->planenum == node->planenum ) {

FreeBspFace( split );

continue;

}

#if 0

if ( !( split->compileFlags & C_DETAIL ) ) {

isstruct = 1;

}

#endif

/* determine which side the face falls on */

side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );

/* switch on side */

if ( side == SIDE_CROSS ) {

ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,

&frontWinding, &backWinding ); /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */

if ( frontWinding ) {

newFace = AllocBspFace();

newFace->w = frontWinding;

newFace->next = childLists[0];

newFace->planenum = split->planenum;

newFace->priority = split->priority;

newFace->compileFlags = split->compileFlags;

childLists[0] = newFace;

}

if ( backWinding ) {

newFace = AllocBspFace();

newFace->w = backWinding;

newFace->next = childLists[1];

newFace->planenum = split->planenum;

newFace->priority = split->priority;

newFace->compileFlags = split->compileFlags;

childLists[1] = newFace;

}

FreeBspFace( split );

}

else if ( side == SIDE_FRONT ) {

split->next = childLists[0];

childLists[0] = split;

}

else if ( side == SIDE_BACK ) {

split->next = childLists[1];

childLists[1] = split;

}

}

// recursively process children

for ( i = 0 ; i < 2 ; i++ ) {

node->children[i] = AllocNode();

node->children[i]->parent = node;

VectorCopy( node->mins, node->children[i]->mins );

VectorCopy( node->maxs, node->children[i]->maxs );

}

for ( i = 0 ; i < 3 ; i++ ) {

if ( plane->normal[i] == 1 ) {

node->children[0]->mins[i] = plane->dist;

node->children[1]->maxs[i] = plane->dist;

break;

}

if ( plane->normal[i] == -1 ) {

node->children[0]->maxs[i] = -plane->dist;

node->children[1]->mins[i] = -plane->dist;

break;

}

}

#if 0

if ( ( node->compileFlags & C_DETAIL ) && isstruct ) {

Sys_FPrintf( SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children );

}

#endif

for ( i = 0 ; i < 2 ; i++ ) {

BuildFaceTree_r( node->children[i], childLists[i] );

if (!node->has_structural_children && node->children[i]->has_structural_children)

{

node->has_structural_children = qtrue;

}

}

#if 0

if ( ( node->compileFlags & C_DETAIL ) && !( node->children[0]->compileFlags & C_DETAIL ) && node->children[0]->planenum != PLANENUM_LEAF ) {

Sys_FPrintf( SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children );

}

if ( ( node->compileFlags & C_DETAIL ) && isstruct ) {

Sys_FPrintf( SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children );

}

#endif