// solidbsp.c

#include "bsp5.h"

extern char *GetContentsName( int Contents );

int	leaffaces;
int	nodefaces;
int	splitnodes;

int c_solid, c_empty, c_water;

qboolean usemidsplit;

// ============================================================================

void
CalcSurfaceBounds( surface_t *const surfaces, vec3_t mins, vec3_t maxs ) {
	int
		i, j;
	surface_t
		*surf;

	for( i = 0; i < 3; i++ ) {
		mins[i] = 99999.9;
		maxs[i] = -99999.9;
	}

	for( surf = surfaces; surf; surf = surf->next ) {
		face_t
			*face;

		for( face = surf->faces; face; face = face->next ) {
			for( i = 0; i < face->numpoints; i++ ) {
				for( j = 0; j < 3; j++ ) {
					mins[j] = MIN( mins[j], face->pts[i][j] );
					maxs[j] = MAX( maxs[j], face->pts[i][j] );
				}
			}
		}
	}
}

/*
==================
FaceSide

For BSP hueristic
==================
*/
int
FaceSide( face_t *in, plane_t *split ) {
	int	frontcount, backcount;
	vec_t	dot;
	int	i;
	vec_t	*p;
	vec_t dist1, dist2;

	frontcount = backcount = 0;

	// axial planes are fast
	if( PlaneIsAxial( split )) {
		dist1 = split->dist + ON_EPSILON;
		dist2 = split->dist - ON_EPSILON;

		for( i = 0, p = in->pts[ 0 ] + split->type; i < in->numpoints; i++, p += 3 ) {
			if( *p > dist1 ) {
				if( backcount )
					return SIDE_ON;

				frontcount = 1;
			}
			else if( *p < dist2 ) {
				if( frontcount )
					return SIDE_ON;

				backcount = 1;
			}
		}
	} else {
		// sloping planes take longer
		for( i = 0, p = in->pts[ 0 ]; i < in->numpoints; i++, p += 3 ) {
			dot = DotProduct( p, split->normal );
			dot -= split->dist;
			if( dot > ON_EPSILON ) {
				if( backcount )
					return SIDE_ON;

				frontcount = 1;
			}
			else if( dot < -ON_EPSILON ) {
				if( frontcount )
					return SIDE_ON;

				backcount = 1;
			}
		}
	}

	if( !frontcount )
		return SIDE_BACK;

	if( !backcount )
		return SIDE_FRONT;

	return SIDE_ON;
}

/*
==================
ChooseMidPlaneFromList

The clipping hull BSP doesn't worry about avoiding splits
==================
*/
surface_t *
ChooseMidPlaneFromList( surface_t *surfaces, vec3_t mins, vec3_t maxs ) {
	int j, l;
	surface_t	*p, *bestsurface;
	vec_t		bestvalue, value, dist;
	plane_t		*plane;

	//
	// pick the plane that sits nearest to the bounds center
	//
	bestvalue = 6 * 8192 * 8192;
	bestsurface = NULL;

	for( p = surfaces; p; p = p->next ) {
		if( p->onnode )
			continue;

		plane = &planes[ p->planenum ];

		// check for axis aligned surfaces
		if( !PlaneIsAxial( plane ))
			continue;

		l = plane->type;

		//
		// calculate the split metric along axis l, smaller values are better
		//
		value = 0;

		dist = plane->dist * plane->normal[ l ];

#if 0
		if( maxs[ l ] - dist < ON_EPSILON || dist - mins[ l ] < ON_EPSILON )
			continue;
		if( maxs[ l ] - dist < 1024 / 2.0 - ON_EPSILON || dist - mins[ l ] < 1024 / 2.0 - ON_EPSILON )
			continue;
#endif

		for( j = 0; j < 3; j++ ) {
			if( j == l ) {
				value += ( maxs[ l ] - dist ) * ( maxs[ l ] - dist );
				value += ( dist - mins[ l ] ) * ( dist - mins[ l ] );
			}
			else
				value += 2 * ( maxs[ j ] - mins[ j ] ) * ( maxs[ j ] - mins[ j ] );
		}

		if( value > bestvalue )
			continue;

		//
		// currently the best!
		//
		bestvalue = value;
		bestsurface = p;
	}

#if 0
	if( !bestsurface ) {
		for( p = surfaces; p; p = p->next )
			if( !p->onnode )
				return p;



		// first valid surface

		Message( MSGERR, "ChooseMidPlaneFromList: No valid planes" );
	}
#endif

	return bestsurface;
}

/*
==================
ChoosePlaneFromList

The real BSP heuristic
==================
*/

#ifdef FEATURE_DETAIL
surface_t *
ChoosePlaneFromList( surface_t *surfaces, vec3_t mins, vec3_t maxs, qboolean usefloors, qboolean usedetail ) {
#else
surface_t *
ChoosePlaneFromList( surface_t *surfaces, vec3_t mins, vec3_t maxs, qboolean usefloors ) {
	#endif
	int j, k, l;
	surface_t	*p, *p2, *bestsurface;
	vec_t		bestvalue, bestdistribution, value, dist;
	plane_t		*plane;
	face_t		*f;
	#ifdef FEATURE_HINTSKIP
	int ishint;
	#endif
	vec_t			boxRatio;
	vec3_t		bboxSize;
	vec3_t		bboxRatios;

	//
	// pick the plane that splits the least
	//
	bestvalue = 99999;
	bestsurface = NULL;
	bestdistribution = 9e30;

#if 1
	// rebb : experimental, use normalized axis ratios
	if( options.normalizeSplitBounds ) {
		VectorSubtract( maxs, mins, bboxSize );

		boxRatio = 0.0;

		for( j = 0; j < 3; ++j ) {
			boxRatio = MAX( bboxSize[j], boxRatio );
		}

		for( j = 0; j < 3; ++j ) {
			if( boxRatio <= 0.0f ) {
				bboxRatios[ j ] = options.splitAxisRatio;
			} else {
				bboxRatios[ j ] = ( boxRatio / bboxSize[j] ) * options.splitAxisRatio;
			}
		}
	} else {
		for( j = 0; j < 3; ++j ) {
			bboxRatios[ j ] = options.splitAxisRatio;
		}
	}
	//
#endif

	for( p = surfaces; p; p = p->next ) {
		if( p->onnode )
			continue;

		#ifdef FEATURE_HINTSKIP
		for( f = p->faces; f; f = f->next ) {
			if( f->texturenum == TEX_HINT ) {
				break;
			}
		}

		ishint = f ? 1 : 0;
		#endif

		#ifdef FEATURE_DETAIL
		if( p->has_struct && usedetail )
			continue;
		if( !p->has_struct && !usedetail )
			continue;
		#endif
		
		plane = &planes[ p->planenum ];
		k = 0;

		if( !usefloors && plane->normal[ 2 ] == 1 )
			continue;

		for( p2 = surfaces; p2; p2 = p2->next ) {
			if(
				p2 == p
				|| p2->onnode
				|| ( PlaneIsAxial( plane ) && plane->type == planes[ p2->planenum ].type )
			)
				continue;

			for( f = p2->faces; f; f = f->next ) {
				if( FaceSide( f, plane ) == SIDE_ON ) {
					#ifdef FEATURE_HINTSKIP
					if( !ishint && f->texturenum == TEX_HINT )
						k += 9999;
					else
						++k;
					#else
					++k;
					#endif
					if( k >= bestvalue )
						break;
				}
			}

			if( k > bestvalue )
				break;
		}

		if( k > bestvalue )
			continue;

		// if equal numbers, axial planes win, then decide on spatial subdivision
		if( k < bestvalue || ( k == bestvalue && PlaneIsAxial( plane ))) {
			// check for axis aligned surfaces
			if( PlaneIsAxial( plane )) { // axial aligned
				l = plane->type;

				//
				// calculate the split metric along axis l
				//
				value = 0;

				for( j = 0; j < 3; j++ ) {
					if( j == l ) {
						dist = plane->dist * plane->normal[ l ];
						value += ( maxs[ l ] - dist ) * ( maxs[ l ] - dist );
						value += ( dist - mins[ l ] ) * ( dist - mins[ l ] );
					}
					else
						// prefer a certain bounding box ratio ?
						value += ( maxs[ j ] - mins[ j ] ) * ( maxs[ j ] - mins[ j ] ) * bboxRatios[ j ];
				}

				if( value > bestdistribution && k == bestvalue )
					continue;

				bestdistribution = value;
			}

			//
			// currently the best!
			//
			bestvalue = k;
			bestsurface = p;
		}
	}

	return bestsurface;
}

/*
==================
SelectPartition

Selects a surface from a linked list of surfaces to split the group on
returns NULL if the surface list can not be divided any more (a leaf)
==================
*/

#ifdef FEATURE_DETAIL
surface_t *
SelectPartition( surface_t *surfaces, int *detail ) {
#else
surface_t *
SelectPartition( surface_t *surfaces ) {
	#endif
	int		i, j;
	vec3_t		mins, maxs;
	surface_t	*p, *bestsurface;

	#ifdef FEATURE_DETAIL
	// zero by default
	*detail = 0;
	#endif

	//
	// count onnode surfaces
	//

	i = 0;
	bestsurface = NULL;

	for( p = surfaces; p; p = p->next ) {
		// if surface has not yet been assigned to a node
		if( !p->onnode ) {
			i++;
			bestsurface = p;
		}
	}

	// all surfaces have been assigned to nodes already
	if( i == 0 )
		return NULL;

	if( i == 1 ) {
		#ifdef FEATURE_DETAIL
		if( !bestsurface->has_struct && !usemidsplit )
			*detail = 1;
		#endif

		return bestsurface; // this is a final split
	}

	//
	// calculate a bounding box of the entire surfaceset
	//
#if 0
	for( i = 0; i < 3; i++ ) {
		mins[ i ] = 99999;
		maxs[ i ] = -99999;
	}

	for( p = surfaces; p; p = p->next )
		for( j = 0; j < 3; j++ ) {
			if( p->mins[ j ] < mins[ j ] )
				mins[ j ] = p->mins[ j ];
			if( p->maxs[ j ] > maxs[ j ] )
				maxs[ j ] = p->maxs[ j ];
		}
#else
	CalcSurfaceBounds( surfaces, mins, maxs );
#endif

	if(
		usemidsplit
		|| (
			options.maxNodeSize >= 64.0 &&
			(
				maxs[0] - mins[0] > options.maxNodeSize - ON_EPSILON ||
				maxs[1] - mins[1] > options.maxNodeSize - ON_EPSILON ||
				maxs[2] - mins[2] > options.maxNodeSize - ON_EPSILON
			)
		)
	) {
		surface_t
			*s = ChooseMidPlaneFromList( surfaces, mins, maxs );

		if( s != NULL )
			return s;
	}

	// do slow way to save poly splits for drawing hull
	#if 0
	bestsurface = ChoosePlaneFromList( surfaces, mins, maxs, false );
	if( bestsurface )
		return bestsurface;
	#endif

	#ifdef FEATURE_DETAIL
		
	bestsurface = ChoosePlaneFromList( surfaces, mins, maxs, true, false );
	if( bestsurface )
		return bestsurface;
	
	*detail = 1;
	return ChoosePlaneFromList( surfaces, mins, maxs, true, true );

	#else

	return ChoosePlaneFromList( surfaces, mins, maxs, true );

	#endif
}

// ============================================================================

/*
=================
CalcSurfaceInfo

Calculates the bounding box
=================
*/
void
CalcSurfaceInfo( surface_t *surf ) {
	int	i, j;
	face_t	*f;

	if( !surf->faces )
		Message( MSGERR, "CalcSurfaceInfo: Surface without a face" );

	//
	// calculate a bounding box
	//
	for( i = 0; i < 3; i++ ) {
		surf->mins[ i ] = 99999;
		surf->maxs[ i ] = -99999;
	}

	for( f = surf->faces; f; f = f->next ) {
		if( f->contents[ 0 ] >= 0 || f->contents[ 1 ] >= 0 )
			Message( MSGERR, "Bad contents" );

		for( i = 0; i < f->numpoints; i++ )
			for( j = 0; j < 3; j++ ) {
				if( f->pts[ i ][ j ] < surf->mins[ j ] )
					surf->mins[ j ] = f->pts[ i ][ j ];
				if( f->pts[ i ][ j ] > surf->maxs[ j ] )
					surf->maxs[ j ] = f->pts[ i ][ j ];
			}
	}
}

/*
==================
DividePlane
==================
*/
void
DividePlane( surface_t *in, plane_t *split, surface_t **front, surface_t **back ) {
	face_t		*facet, *next;
	face_t		*frontlist, *backlist;
	face_t		*frontfrag, *backfrag;
	surface_t	*news;
	plane_t		*inplane;
	vec_t		normalEpsilon = EQUAL_EPSILON;
#ifdef FEATURE_DETAIL
	int have[ 2 ][ 2 ]; // [front|back][detail|struct]
#endif

	inplane = &planes[ in->planenum ];

	// parallel case is easy
	if( VectorCompareEpsilon( inplane->normal, split->normal, normalEpsilon )) {
		// check for exactly on node
		if( inplane->dist == split->dist ) { // divide the facets to the front and back sides
			news = AllocSurface();
			*news = *in;

			facet = in->faces;
			in->faces = NULL;
			news->faces = NULL;
			in->onnode = news->onnode = true;

#ifdef FEATURE_DETAIL
			in->has_detail = in->has_struct = false;
#endif

			for(; facet; facet = next ) {
				next = facet->next;
				if( facet->planeside == 1 ) {
					facet->next = news->faces;
					news->faces = facet;

#ifdef FEATURE_DETAIL
					if( facet->detail )
						news->has_detail = true;
					else
						news->has_struct = true;
#endif
				}
				else {
					facet->next = in->faces;
					in->faces = facet;

#ifdef FEATURE_DETAIL
					if( facet->detail )
						in->has_detail = true;
					else
						in->has_struct = true;
#endif
				}
			}

			if( in->faces )
				*front = in;
			else {
#ifndef FEATURE_DETAIL
				FreeSurface( in );
#endif
				*front = NULL;
			}

			if( news->faces )
				*back = news;
			else {
#ifndef FEATURE_DETAIL
				FreeSurface( news );
#endif
				*back = NULL;
			}

			return;
		}

		if( inplane->dist > split->dist ) {
			*front = in;
			*back = NULL;
		}
		else {
			*front = NULL;
			*back = in;
		}
		return;
	}

	// do a real split.  may still end up entirely on one side
	// OPTIMIZE: use bounding box for fast test
	frontlist = NULL;
	backlist = NULL;

#ifdef FEATURE_DETAIL
	memset( have, 0, sizeof( have ));
#endif

	for( facet = in->faces; facet; facet = next ) {
		next = facet->next;

		SplitFace( facet, split, &frontfrag, &backfrag );

		if( frontfrag ) {
			frontfrag->next = frontlist;
			frontlist = frontfrag;
#ifdef FEATURE_DETAIL
			have[ 0 ][ frontfrag->detail ] = 1;
#endif
		}
		if( backfrag ) {
			backfrag->next = backlist;
			backlist = backfrag;
#ifdef FEATURE_DETAIL
			have[ 1 ][ backfrag->detail ] = 1;
#endif
		}
	}

	// if nothing actually got split, just move the in plane

	if( frontlist == NULL ) {
		*front = NULL;
		*back = in;
		in->faces = backlist;
		return;
	}

	if( backlist == NULL ) {
		*front = in;
		*back = NULL;
		in->faces = frontlist;
		return;
	}

	// stuff got split, so allocate one new plane and reuse in
	news = AllocSurface();
	*news = *in;
	news->faces = backlist;
	*back = news;

	in->faces = frontlist;
	*front = in;

#ifdef FEATURE_DETAIL
	in->has_struct = have[ 0 ][ 0 ];
	in->has_detail = have[ 0 ][ 1 ];

	news->has_struct = have[ 1 ][ 0 ];
	news->has_detail = have[ 1 ][ 1 ];
#endif

	// recalc bboxes and flags
	CalcSurfaceInfo( news );
	CalcSurfaceInfo( in );
}

/*
==================
DivideNodeBounds
==================
*/
void
DivideNodeBounds( node_t *node, plane_t *split ) {
	VectorCopy( node->mins, node->children[ 0 ]->mins );
	VectorCopy( node->mins, node->children[ 1 ]->mins );
	VectorCopy( node->maxs, node->children[ 0 ]->maxs );
	VectorCopy( node->maxs, node->children[ 1 ]->maxs );

	// OPTIMIZE: sloping cuts can give a better bbox than this...
	if( PlaneIsAxial( split )) {
		node->children[ 0 ]->mins[ split->type ] = node->children[ 1 ]->maxs[ split->type ] = split->dist;
	}
}

/*
==================
GetContentsName
==================
*/
char *
GetContentsName( int Contents ) {
	switch( Contents ) {
	case CONTENTS_EMPTY:
		return "Empty";

	case CONTENTS_SOLID:
		return "Solid";

	case CONTENTS_WATER:
		return "Water";

	case CONTENTS_SLIME:
		return "Slime";

	case CONTENTS_LAVA:
		return "Lava";

	case CONTENTS_SKY:
		return "Sky";

	default:
		return "Error";
	}
}

/*
==================
LinkConvexFaces

Determines the contents of the leaf and creates the final list of
original faces that have some fragment inside this leaf
==================
*/
void
LinkConvexFaces( surface_t *planelist, node_t *leafnode ) {
	face_t		*f, *next;
	surface_t	*surf, *pnext;
	int i, count;
	qboolean OnlyWarn;

	leafnode->faces = NULL;
	leafnode->contents = 0;
	leafnode->planenum = -1;

	count = 0;
	for( surf = planelist; surf; surf = surf->next ) {
		for( f = surf->faces; f; f = f->next ) {
			#ifdef FEATURE_HINTSKIP
			if( f->texturenum < 0 )
				continue;
			#endif

			count++;

			if( !leafnode->contents ) {
				leafnode->contents = f->contents[ 0 ];
			} else
			if( leafnode->contents != f->contents[ 0 ] ) {
				OnlyWarn = leafnode->contents == CONTENTS_EMPTY || f->contents[ 0 ] == CONTENTS_EMPTY;

				Message( OnlyWarn ? MSGWARN : MSGERR, "Mixed face contents (%s, %s) near %s",
					 GetContentsName( leafnode->contents ), GetContentsName( f->contents[ 0 ] ), GetCoord( f->pts[ 0 ] ));
			}
		}
	}

	if( !leafnode->contents )
		leafnode->contents = CONTENTS_SOLID;

	switch( leafnode->contents ) {
	case CONTENTS_EMPTY:
		c_empty++;
		break;

	case CONTENTS_SOLID:
		c_solid++;
		break;

	case CONTENTS_WATER:
	case CONTENTS_SLIME:
	case CONTENTS_LAVA:
	case CONTENTS_SKY:
		c_water++;
		break;

	default:
		Message( MSGERR, "LinkConvexFaces: Bad contents number" );
	}

	//
	// write the list of faces, and free the originals
	//
	leaffaces += count;

	if( count > 0 )
		leafnode->markfaces = AllocOther( sizeof( face_t * ) * ( count + 1 ));

	i = 0;

	for( surf = planelist; surf; surf = pnext ) {
		pnext = surf->next;
		for( f = surf->faces; f; f = next ) {
			next = f->next;

			#ifdef FEATURE_HINTSKIP
			if( f->texturenum >= 0 ) {
				leafnode->markfaces[ i ] = f->original;
				++i;
			}
			#else
			leafnode->markfaces[ i ] = f->original;
			++i;
			#endif

			FreeFace( f );
		}
		FreeSurface( surf );
	}

	if( count > 0 )
		leafnode->markfaces[ i ] = NULL; // sentinal
}

/*
==================
LinkNodeFaces

Returns a duplicated list of all faces on surface
==================
*/
face_t *
LinkNodeFaces( surface_t *surface ) {
	face_t	*f, *new, **prevptr;
	face_t	*list;

	list = NULL;

	// subdivide
	prevptr = &surface->faces;
	while( 1 ) {
		f = *prevptr;
		if( !f )
			break;
		SubdivideFace( f, prevptr );
		f = *prevptr;
		prevptr = &f->next;
	}

	// copy
	for( f = surface->faces; f; f = f->next ) {
		nodefaces++;
		new = AllocFace();
		CopyFace( new, f );
		f->original = new;
		new->next = list;
		list = new;
	}

	return list;
}

qboolean DispProgress; // Unnecessary; speed only

static qboolean     CalcNodeBounds(node_t* node)
{
    int             i;
    int             j;
    vec_t           v;
    portal_t*       p;
    portal_t*       next_portal;
    int             side = 0;
	 vec_t			buf;

    node->mins[0] = node->mins[1] = node->mins[2] = 999999;
    node->maxs[0] = node->maxs[1] = node->maxs[2] = -999999;

    for (p = node->portals; p; p = next_portal)
    {
        if (p->nodes[0] == node)
        {
            side = 0;
        }
        else if (p->nodes[1] == node)
        {
            side = 1;
        }
        else
        {
            //Error("CalcNodeBounds: mislinked portal");
			  //Error(
			  printf("CalcNodeBounds: mislinked portal");
        }
        next_portal = p->next[side];

		  for (i = 0; i < p->winding->numpoints; i++)
        {
            for (j = 0; j < 3; j++)
            {
						v = p->winding->points[i][j];
                if (v < node->mins[j])
                {
                    node->mins[j] = v;
                }
                if (v > node->maxs[j])
                {
                    node->maxs[j] = v;
                }
            }
        }
    }

	 for( i = 0; i != 3; ++i ) {
		 if( node->mins[i] > node->maxs[i] ) {
			buf = node->mins[i];
			node->mins[i] = node->maxs[i];
			node->maxs[i] = buf;
		 }
	 }

#define MAXNODESIZE 1024

    for (i = 0; i < 3; i++)
    {
        if (node->maxs[i] - node->mins[i] > MAXNODESIZE)
        {
            return true;
        }
    }
    return false;
}

/*
==================
PartitionSurfaces
==================
*/
void
PartitionSurfaces( surface_t *surfaces, node_t *node ) {
	surface_t	*split, *p, *next;
	surface_t	*frontlist, *backlist;
	surface_t	*frontfrag, *backfrag;
	plane_t		*splitplane;

#ifdef FEATURE_DETAIL
	split = SelectPartition( surfaces, &node->detail );

	if( !split ) { // this is a leaf node
		//node->detail = 0; // clear just in case
#else
	split = SelectPartition( surfaces );
	if( !split ) { // this is a leaf node
#endif
		node->planenum = PLANENUM_LEAF;
		LinkConvexFaces( surfaces, node );
		return;
	}

	splitnodes++;

	if( DispProgress )
		// Try to make progress info more linear
		ShowBar((int) ( sqrt( 4 * ( splitnodes + leaffaces + nodefaces )) * 100 / sqrt( csgmergefaces )), 100 );

	node->faces = LinkNodeFaces( split );
	node->children[ 0 ] = AllocNode();
	node->children[ 1 ] = AllocNode();
	node->planenum = split->planenum;

	splitplane = &planes[ split->planenum ];

	DivideNodeBounds( node, splitplane );

	//
	// multiple surfaces, so split all the polysurfaces into front and back lists
	//
	frontlist = NULL;
	backlist = NULL;

	for( p = surfaces; p; p = next ) {
		next = p->next;

		DividePlane( p, splitplane, &frontfrag, &backfrag );

#if 0
		if (frontfrag && backfrag) {
			// the plane was split, which may expose oportunities to merge
			// adjacent faces into a single face
			MergePlaneFaces (backfrag);
			MergePlaneFaces (frontfrag);
			//continue;
			//frontfrag = p;
			//backfrag = p;
			CalcSurfaceInfo( frontfrag );
			CalcSurfaceInfo( backfrag );
		}
#endif

		if( frontfrag ) {
			if( !frontfrag->faces )
				Message( MSGERR, "Surface with no faces" );

			frontfrag->next = frontlist;
			frontlist = frontfrag;
		}

		if( backfrag ) {
			if( !backfrag->faces )
				Message( MSGERR, "Surface with no faces" );

			backfrag->next = backlist;
			backlist = backfrag;
		}
	}

	PartitionSurfaces( frontlist, node->children[ 0 ] );
	PartitionSurfaces( backlist, node->children[ 1 ] );
}

/*
==================
SolidBSP
==================
*/
node_t *
SolidBSP( surface_t *surfhead, qboolean midsplit, qboolean ForcePrint, qboolean Progress ) {
	int	i;
	node_t	*headnode;

	Message( ForcePrint ? MSGALWAYS : MSGVERBOSE, "------ SolidBSP ------" );

	headnode = AllocNode();
	usemidsplit = midsplit;

	//
	// calculate a bounding box for the entire model
	//
	for( i = 0; i < 3; i++ ) {
		headnode->mins[ i ] = brushset->mins[ i ] - SIDESPACE;
		headnode->maxs[ i ] = brushset->maxs[ i ] + SIDESPACE;
	}

	//
	// recursively partition everything
	//
	splitnodes = 0;
	leaffaces = 0;
	nodefaces = 0;
	c_solid = c_empty = c_water = 0;

	DispProgress = Progress;

	PartitionSurfaces( surfhead, headnode );

	ShowBar( -1, -1 );

	Message( MSGVERBOSE, "%6i split nodes", splitnodes );
	Message( MSGVERBOSE, "%6i solid leafs", c_solid );
	Message( MSGVERBOSE, "%6i empty leafs", c_empty );
	Message( MSGVERBOSE, "%6i water leafs", c_water );
	Message( MSGVERBOSE, "%6i leaffaces", leaffaces );
	Message( MSGVERBOSE, "%6i nodefaces", nodefaces );

	return headnode;
}