/******************************************************************************
	libx42make - skinned vertex animation library (exporter utilities)
	Copyright (C) 2007 HermitWorks Entertainment Corporation

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

#include "local.h"

namespace x42
{
namespace make
{

static void BoundPoints( const std::vector< vec3 > &verts,
	sphere &bddsphere, aabb &bddbox )
{
	if( !verts.size() )
	{
		bddsphere = spherec( vec3c( 0 ), 0 );
		bddbox = aabbc( vec3c( 0 ), vec3c( 0 ) );
		return;
	}

	size_t numUnique = verts.size();
	vec3 mean = vec3c( 0 );

	std::vector< bool > nonUnique( verts.size() );

	bddbox = aabb::empty();

	for( uint i = 0; i < verts.size(); i++ )
	{
		if( nonUnique[i] )
			continue;

		for( uint j = i + 1; j < verts.size(); j++ )
		{
			if( nonUnique[j] )
				continue;

			if( equal( verts[i], verts[j], 1e-5F ) )
			{
				nonUnique[j] = true;
				numUnique--;
			}
		}

		mean += verts[i];
		bddbox |= verts[i];
	}

	float invNumVerts = 1.0F / numUnique;
	mean *= invNumVerts;

	//set up for the covariance matrix
	//note, the matrix is symmetric so
	//c21 also represents c12, etc
	float c11 = 0;
	float c21 = 0, c22 = 0;
	float c31 = 0, c32 = 0, c33 = 0;

	for( uint i = 0; i < verts.size(); i++ )
	{
		//again, we're dealing with a sum so we want
		//the same vertices with which we computed mean
		if( nonUnique[i] )
			continue;

		//build the covariance matrix up
		const vec3 d = verts[i] - mean;

		c11 += d.x * d.x;
		c21 += d.x * d.y; c22 += d.y * d.y;
		c31 += d.x * d.z; c32 += d.y * d.z; c33 += d.z * d.z;
	}

	c11 *= invNumVerts;
	c21 *= invNumVerts; c22 *= invNumVerts;
	c31 *= invNumVerts; c32 *= invNumVerts; c33 *= invNumVerts;

	//solve for the initial sphere center (should be close)
	vec3 r, s, t;
	float l[3];

	x42::math::solve::eigenvectors_in_order_3x3s( c11, c21, c22, c31, c32, c33, (float*)&r, (float*)&s, (float*)&t, l );

	//normalize the principle axis (r)
	float len = length( r );
	assert( len > 0, "could not find principle axis" );
	r *= 1.0F / len;

	vec3 aaMin = verts[0];
	vec3 aaMax = verts[0];

	float mind = dot( r, aaMin );
	float maxd = mind;

	//get the sphere center
	for( uint i = 1; i < verts.size(); i++ )
	{  
		const vec3 &v = verts[i];
		float d = dot( r, v );

		if( d < mind )
		{
			mind = d;
			aaMin = v;
		}
		else if( d > maxd )
		{
			maxd = d;
			aaMax = v;
		}
	}

	//get the sphere center
	vec3 c = (aaMin + aaMax) * 0.5F;
	//get the radius, reuse min and max since they're dead now
	aaMin = c - aaMax;
	
	float radius = length( aaMin );

	//adjust the sphere to include outlying points
	for( uint i = 0; i < verts.size(); i++ )
	{ 
		const vec3 &v = verts[i];
		r = v - c;
		float d = length( r );

		if( d <= radius )
			//point already in sphere, good to go
			continue;

		//need to adjust the bounding
		//sphere to contain the old one
		//as well as the point v

		r *= 1.0F / d;

		//get a point g on the old sphere opposite the center from v
		vec3 g = c - r * radius;

		//find the new center (half way between v and g)
		c = (v + g) * 0.5F;
		//and the new radius
		r = v - c;
		radius = length( r );
	}

	bddsphere = spherec( c, radius );
}

static sphere BoundSpheres( const std::vector< sphere > &spheres )
{
	if( !spheres.size() )
		return spherec( vec3c( 0 ), 0 );

	vec3 c = vec3c( 0 );
	float w = 0;

	for( uint i = 0; i < spheres.size(); i++ )
	{
		float wt = spheres[i].radius;

		c += spheres[i].center * wt;
		w += wt;
	}

	if( fabsf( w ) > 1e-5F )
		c /= w;

	float r = 0;

	for( uint i = 0; i < spheres.size(); i++ )
		r = max( r, dist( c, spheres[i].center ) + spheres[i].radius );

	return spherec( c, r );
}

static aabb BoundBoxes( const std::vector< aabb > &boxes )
{
	if( !boxes.size() )
		return aabb::empty();

	aabb box = aabb::empty();
	for( uint i = 0; i < boxes.size(); i++ )
		box |= boxes[i];

	return box;
}

void ModelData::GenCullingInfoForFrame( std::vector< aabb > &boxes, std::vector< sphere > &spheres,
	const std::vector< bool > &updateExtent, uint iFrame )
{
	std::vector< affine > infMats( influences.size() );

	for( uint i = 0; i < influences.size(); i++ )
	{
		const Influence &inf = influences[i];

		if( inf.bone )
			infMats[i] = inf.bone->worldMats[iFrame].value * inf.objToBone;
		else
			infMats[i] = inf.objToBone;
	}

	std::vector< vec3 > animPts;

	for( uint i = 0; i < lods.size(); i++ )
	{
		const Lod &lod = *lods[i];

		for( uint i = 0; i < lod.groups.size(); i++ )
		{
			const Group &g = *lod.groups[i];
			animPts.resize( g.verts.size() );

			for( uint i = 0; i < g.verts.size(); i++ )
			{
				const Vertex &in = g.verts[i];
				vec3 &out = animPts[i];

				if( g.infMap.size() && g.maxInfsPerVert )
				{
					out = vec3c( 0 );
					for( uint i = 0; i < g.maxInfsPerVert; i++ )
					{
						if( in.wt[i] == 0 )
							continue;

						uint infIdx = g.infMap[in.idx[i]];
						vec3 partPt = infMats[infIdx].mul_point( in.pos );

						const Influence &inf = influences[infIdx];
						if( inf.bone && updateExtent[inf.bone->index] )
						{
							float d = dist( inf.bone->worldMats[iFrame].value.col( 3 ), partPt );
							bones[inf.bone->index]->extent = max( inf.bone->extent, d );
						}

						out += partPt * in.wt[i];
					}
				}
				else
				{
					//unweighted, untransformed vertices
					out = in.pos;
				}
			}

			sphere sph;
			aabb box;

			BoundPoints( animPts, sph, box );
			spheres.push_back( sph );
			boxes.push_back( box );
		}
	}
}

void ModelData::GenCullingInfo( bool scanAllFrames, float pad )
{
	if( !numFrames )
		return;

	std::vector< bool > updateExtent( bones.size(), false );
	for( uint i = 0; i < bones.size(); i++ )
	{
		if( bones[i]->worldMats.size() != numFrames )
			fail( ErrCode::InvalidOp, "ModelData::GenCullingInfo requires a full world matrix representation." );

		if( bones[i]->extent == Bone::AutoGenExtent )
		{
			updateExtent[i] = true;
			bones[i]->extent = 0;
		}
	}

	std::vector< aabb > boxes;
	std::vector< sphere > spheres;

	uint maxFrame = scanAllFrames ? numFrames : 1;

#if defined( DEBUG )
	maxFrame = 1;
#endif

	for( uint i = 0; i < maxFrame; i++ )
	{
		GenCullingInfoForFrame( boxes, spheres, updateExtent, i );
	}

	boundingBox = BoundBoxes( boxes );
	boundingSphere = BoundSpheres( spheres );

	boundingBox.mins -= vec3c( pad );
	boundingBox.maxs += vec3c( pad );
	boundingSphere.radius += pad;
}

};
};