/* Copyright 2005 Nicholas Bishop
 * 
 * This file is part of SharpConstruct.
 *
 * SharpConstruct 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.
 *
 * SharpConstruct 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 SharpConstruct; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#include "Brush.h"
#include "Mesh.h"
#include "MeshHistory.h"
#include "Utilities.h"
#include <algorithm>
#include <limits>

#include <iostream>

using namespace SharpConstruct;
using SharpConstruct::Optimized::Point3D;

void Mesh::Move( float x, float y, float z )
{	
	for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
	{
		_vertex_locations[ i ].X() += x;
		_vertex_locations[ i ].Y() += y;
		_vertex_locations[ i ].Z() += z;
	}
	
	_change_operation( false, true );

	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

void Mesh::Resize( float x, float y, float z )
{
	for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
	{
		if( x > 0 )
			_vertex_locations[ i ].X() *= x;
		else if( x < 0 )
			_vertex_locations[ i ].X() /= -x;
		if( y > 0 )
			_vertex_locations[ i ].Y() *= y;
		else if( y < 0 )
			_vertex_locations[ i ].Y() /= -y;
		if( z > 0 )
			_vertex_locations[ i ].Z() *= z;
		else if( z < 0 )
			_vertex_locations[ i ].Z() /= -z;
	}
	
	RecalculateAllNormals();
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

/** Smooths the entire mesh.
 *
 * Smooths every point in the mesh. Accepts a strength value between zero and
 * one.
**/
void Mesh::Smooth( float strength )
{
	Point3D average;
	
	for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
	{
		average = VertexNeighborLocAverage( i );
	
		_vertex_locations[ i ] += ( average - _vertex_locations[ i ] ) * strength;
	}
	
	RecalculateAllNormals();
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

/**
 *
**/
void Mesh::Deflate( float v )
{
	Point3D nloc;
	for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
	{
		_vertex_locations[ i ] += _vertex_normals[ i ] * v;
	}
	RecalculateAllNormals();
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

/** Normalizes the distances of vertices from the model's center
 *
 */
void Mesh::Spherize( float strength )
{
	CalculateBoundingSphere();

	const float sub( 1 - strength );
	for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
	{
		Point3D& v( _vertex_locations[ i ] );
		//const float distance( _center.Distance( _vertex_locations[ i ] ) );
		Point3D copy( v );
		Normalize( copy );
		v = v * sub + copy * strength;
	}

	RecalculateAllNormals();
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

/** Floods the entire mesh with the current color.
 *
 * All vertex colors are shifted towards the current color. Accepts an intensity
 * value between 0 and 1.
**/
void Mesh::Flood( const Color& color, const float intensity )
{
	if( intensity == 1 )
	{
		for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
			_vertex_colors[ i ] = color;
	}
	else
	{
		for( unsigned i = 0; i < _visible_elements.Vertices; ++i )
		{
			_vertex_colors[ i ].Red = _vertex_colors[ i ].Red +
				( color.Red - _vertex_colors[ i ].Red )
				* intensity;
			_vertex_colors[ i ].Green = _vertex_colors[ i ].Green +
				( color.Green - _vertex_colors[ i ].Green )
				* intensity;
			_vertex_colors[ i ].Blue = _vertex_colors[ i ].Blue +
				( color.Blue - _vertex_colors[ i ].Blue )
				* intensity;
		}
	}
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( false, true, false );
}

struct subtri
{
	unsigned O[ 3 ];
	unsigned P[ 3 ];
};
struct subquad
{
	unsigned O[ 4 ];
	unsigned P[ 4 ];
};

void Mesh::Subdivide( bool smooth )
{
	std::vector< subtri > st( _triangles.size() );
	unsigned lndx = _vertex_locations.size();

	for( unsigned i = 0; i < _triangles.size(); ++i )
	{
		// Copy _triangles data to st
		for( unsigned j = 0; j <= 2; j++ )
			st[ i ].O[ j ] = _triangles[ i ].V[ j ];

		// For each edge
		for( unsigned j = 0; j <= 2; j++ )
		{
			int j2 = j + 1;
			if( j2 > 2 )
				j2 = 0;
			
			// Find all polygon users
			std::map< unsigned, unsigned > tusrs = _triangle_users( st[ i ].O[ j ], st[ i ].O[ j2 ] );
			
			std::map< unsigned, unsigned >::iterator it;
			int subndx = -1;
			
			for( std::map< unsigned, unsigned >::iterator it = tusrs.begin();
			     it != tusrs.end(); it++ )
			{
				if( ( *it ).first < i )
				{
					it = tusrs.begin();
					subndx = st[ ( *it ).first ].P[ ( *it ).second - 1 ];
					break;
				}
			}
			
			// If not found, calculate a new midpoint
			if( subndx == -1 )
			{
				_vertex_locations.resize( _vertex_locations.size() + 1 );
				_vertex_locations[ lndx ].Midpoint( _vertex_locations[ st[ i ].O[ j ] ],
													_vertex_locations[ st[ i ].O[ j2 ] ] );
				_vertex_colors.resize( _vertex_colors.size() + 1 );
				_vertex_colors[ lndx ] = MixColors( _vertex_colors[ st[ i ].O[ j ] ],
				                                    _vertex_colors[ st[ i ].O[ j2 ] ] );
				st[ i ].P[ j ] = lndx++;
			}
			else
			{
				st[ i ].P[ j ] = subndx;
			}
		}
	}
	
	std::vector< subquad > sq( _quads.size() );
	lndx = _vertex_locations.size();
	
	for( unsigned i = 0; i < _quads.size(); ++i )
	{
		// Copy quad data to sq
		for( unsigned j = 0; j <= 3; j++ )
			sq[ i ].O[ j ] = _quads[ i ].V[ j ];
		
		// For each edge
		for( unsigned j = 0; j <= 3; j++ )
		{
			int j2 = j + 1;
			if( j2 > 3 )
				j2 = 0;
			
			// Find all polygon users
			std::map< unsigned, unsigned > tusrs = _triangle_users( sq[ i ].O[ j ], sq[ i ].O[ j2 ] );
			
			std::map< unsigned, unsigned >::iterator it;
			int subndx = -1;
			
			if( tusrs.size() )
			{
				it = tusrs.begin();
				subndx = st[ ( *it ).first ].P[ ( *it ).second - 1 ];
			}
			
			// No connected triangles
			if( subndx == -1 )
			{
				std::map< unsigned, unsigned > qusrs = _quad_users( sq[ i ].O[ j ], sq[ i ].O[ j2 ] );
				for( it = qusrs.begin(); it != qusrs.end(); it++ )
				{
					if( ( *it ).first < i )
					{
						subndx = sq[ ( *it ).first ].P[ (int)(( *it ).second) - 1 ];
						break;
					}
				}
			}
			
			// If not found, calculate a new midpoint
			if( subndx == -1 )
			{
				_vertex_locations.resize( _vertex_locations.size() + 1 );
				_vertex_locations[ lndx ].Midpoint( _vertex_locations[ sq[ i ].O[ j ] ],
								    _vertex_locations[ sq[ i ].O[ j2 ] ] );
				_vertex_colors.resize( _vertex_colors.size() + 1 );
				_vertex_colors[ lndx ] = MixColors( _vertex_colors[ sq[ i ].O[ j ] ],
				                                    _vertex_colors[ sq[ i ].O[ j2 ] ] );
				sq[ i ].P[ j ] = lndx++;
			}
			else
			{
				sq[ i ].P[ j ] = subndx;
			}
		}
	}

	_triangles.clear();
	_quads.clear();
	/* This loop makes the following subdivisional pattern:
	 *
	 *    /\               /\
	 *   /  \    ====\    /__\
	 *  /    \   ====/   /\  /\
	 * /______\         /__\/__\
	 *
	 * Currently disabled in favor of a quad-producing algorithm.
	 */
	/*for( unsigned i = 0; i < st.size(); ++i )
	{
		_triangles.push_back( Triangle( st[ i ].O[ 0 ], st[ i ].P[ 0 ], st[ i ].P[ 2 ] ) );
		_triangles.push_back( Triangle( st[ i ].P[ 0 ], st[ i ].O[ 1 ], st[ i ].P[ 1 ] ) );
		_triangles.push_back( Triangle( st[ i ].P[ 1 ], st[ i ].O[ 2 ], st[ i ].P[ 2 ] ) );
		_triangles.push_back( Triangle( st[ i ].P[ 0 ], st[ i ].P[ 1 ], st[ i ].P[ 2 ] ) );
	}*/

	// This loop produces three quads instead of four triangles.
	for( unsigned i = 0; i < st.size(); ++i )
	{
		// Find center
		Point3D cen( 0, 0, 0 );
		for( unsigned j = 0; j <= 2; j++ )
			cen += _vertex_locations[ st[ i ].O[ j ] ];
		cen /= 3;
		
		unsigned cndx = _vertex_locations.size();
		_vertex_locations.push_back( cen );
		_vertex_colors.push_back( MixColors( _vertex_colors[ st[ i ].O[ 0 ] ],
		                                     _vertex_colors[ st[ i ].O[ 1 ] ],
		                                     _vertex_colors[ st[ i ].O[ 2 ] ] ) );

		_quads.push_back( Quad( cndx, st[ i ].P[ 2 ], st[ i ].O[ 0 ], st[ i ].P[ 0 ] ) );
		_quads.push_back( Quad( cndx, st[ i ].P[ 0 ], st[ i ].O[ 1 ], st[ i ].P[ 1 ] ) );
		_quads.push_back( Quad( cndx, st[ i ].P[ 1 ], st[ i ].O[ 2 ], st[ i ].P[ 2 ] ) );
	}

	for( unsigned i = 0; i < sq.size(); ++i )
	{
		// Find center
		Point3D cen( 0, 0, 0 );
		for( unsigned j = 0; j <= 3; j++ )
			cen += _vertex_locations[ sq[ i ].O[ j ] ];
		cen /= 4;
		
		unsigned cndx = _vertex_locations.size();
		_vertex_locations.push_back( cen );
		_vertex_colors.push_back( MixColors( _vertex_colors[ sq[ i ].O[ 0 ] ],
		                                     _vertex_colors[ sq[ i ].O[ 1 ] ],
		                                     _vertex_colors[ sq[ i ].O[ 2 ] ],
		                                     _vertex_colors[ sq[ i ].O[ 3 ] ] ) );
		
		_quads.push_back( Quad( sq[ i ].O[ 0 ], sq[ i ].P[ 0 ], cndx, sq[ i ].P[ 3 ] ) );
		_quads.push_back( Quad( sq[ i ].P[ 0 ], sq[ i ].O[ 1 ], sq[ i ].P[ 1 ], cndx ) );
		_quads.push_back( Quad( sq[ i ].P[ 1 ], sq[ i ].O[ 2 ], sq[ i ].P[ 2 ], cndx ) );
		_quads.push_back( Quad( sq[ i ].P[ 2 ], sq[ i ].O[ 3 ], sq[ i ].P[ 3 ], cndx ) );
	}

	// Return mesh data to a consistent state
	
	_recalculate_vertex_users();
	_vertex_normals.resize( _vertex_locations.size() );
	_triangle_normals.resize( _triangles.size() );
	_quad_normals.resize( _quads.size() );
	//_recalculate_all_normals();
	if( smooth )
	{
		Optimized::Point3DVector nv( _vertex_locations );
		for( unsigned i = 0; i < _vertex_locations.size(); ++i )
		{
			unsigned count = 0, j;

			nv[ i ] = Point3D( 0, 0, 0 );
			//nv[ i ] = _vertex_locations[ i ];
			for( j = 0; j < _vertex_users[ i ].Triangles.size(); j++ )
				nv[ i ] += _polygon_center( _triangles[ _vertex_users[ i ].Triangles[ j ] ] );
			count += j;

			for( j = 0; j < _vertex_users[ i ].Quads.size(); j++ )
				nv[ i ] += _polygon_center( _quads[ _vertex_users[ i ].Quads[ j ] ] );
			count += j;

			nv[ i ] /= count;
		}
		_vertex_locations = nv;
	}

	_reset_visibles();

	_visible_elements.RestoreOrder.Enabled = false;
	
	_change_operation( true, true );

	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
}

/*void Mesh::Optimize( float amt )
{
	const int orig = _polygon_normals.size();
	std::vector< std::map< unsigned, float > > dists(
		_vertex_polygon_indices.size() );
	
	// Dists has one map for every vertex; the map contains every other vertex
	// the vertex is connected to (key) and the distance between them as the
	// value
	for( unsigned i = 0; i < _vertex_locations.size(); ++i )
	{
		std::set< unsigned > cs = _connected_vertices( i );
		for( std::set< unsigned >::iterator it = cs.begin(); it != cs.end();
			 ++it )
		{
			if( *it < i )
				continue;
			dists[ i ][ *it ] = _vertex_locations[ i ].Distance(
				_vertex_locations[ *it ] );
		}
	}
	while( (int)_indices.size() / 3 > orig - amt )
	{
		unsigned P[ 0 ] = 0, P[ 1 ] = *_connected_vertices( 0 ).begin();
		float shortest = _vertex_locations[ P[ 0 ] ].Distance( _vertex_locations[ P[ 1 ] ] );
		
		for( unsigned i = 1; i < dists.size(); ++i )
		{
			for( std::map< unsigned, float >::iterator it = dists[ i ].begin();
			     it != dists[ i ].end(); ++it )
			{
				if( ( *it ).second < shortest ||
					shortest < std::numeric_limits< float >::epsilon() )
				{
					shortest = ( *it ).second;
					P[ 0 ] = i;
					P[ 1 ] = ( *it ).first;
				}
			}
		}
	
		std::map< unsigned, unsigned > cn = _polygons_with_vertices( P[ 0 ], P[ 1 ] );
		
		// Polygons that use P[ 1 ] should use P[ 0 ] instead
		for( unsigned i = 0; i < _vertex_polygon_indices[ P[ 1 ] ].size(); ++i )
		{
			for( unsigned j = 0; j <= 2; j++ )
			{
				const unsigned p = _vertex_polygon_indices[ P[ 1 ] ][ i ];
				if( _indices[ p * 3 + j ] == P[ 1 ] )
					_indices[ p * 3 + j ] = P[ 0 ];
			}
		}
		
		// Remove polygons that use both P[ 0 ] and P[ 1 ]
		for( std::map< unsigned, unsigned >::reverse_iterator i = cn.rbegin();
			 i != cn.rend(); ++i )
		{
			for( unsigned j = 0; j <= 2; j++ )
			{
				const int ndx = _indices[ ( *i ).first * 3 + j ];
				for( unsigned k = 0; k < _vertex_polygon_indices[ ndx ].size(); k++ )
				{
				*//*	if( _vertex_polygon_indices[ ndx ][ k ] == ( *i ).first )
						_vertex_polygon_indices[ ndx ].erase(
							_vertex_polygon_indices[ ndx ].begin() + k );*//*
				}
			}
			//std::cout << "rm: " << ( *i ).first << std::endl;
			_indices.erase( _indices.begin() + ( *i ).first * 3,
							_indices.begin() + ( *i ).first * 3 + 3 );
		}
		
		// P[ 0 ] = the midpoint of P[ 0 ] and P[ 1 ]
		_vertex_locations[ P[ 0 ] ].Midpoint( _vertex_locations[ P[ 0 ] ], _vertex_locations[ P[ 1 ] ] );
		
		_vertex_polygon_indices[ P[ 1 ] ].clear();
		_recalculate_vertex_polygon_indices();
		
		dists[ P[ 0 ] ].clear();
		dists[ P[ 1 ] ].clear();
		
		//std::cout << P[ 0 ] << " " << P[ 1 ] << std::endl;
	}
	
	_polygon_normals.resize( _indices.size() / 3 );
	_recalculate_vertex_polygon_indices();
	RecalculateAllNormals();
	
	_change_operation();
}*/

int Mesh::RemoveDuplicates()
{
	return 0;
	/*unsigned int i, j, k, l, total = 0;
	
	for( i = 0; i < _vertices.size() - 1; ++i )
		for( j = i + 1; j < _vertices.size(); j++ )
			if( _vertices[ i ].Location == _vertices[ j ].Location )
			{
				// We've found a duplicate, destroy it
				_vertices.erase( _vertices.begin() + j );
				
				for( k = 0; k < _vertex_polygon_indices[ j ].size(); k++ )
				{
					// Copy all of the jth's polygons to i's vector
					_vertex_polygon_indices[ i ].push_back( _vertex_polygon_indices[ j ][ k ] );
					for( l = 0; l < 3; l++ )
						if( _indices[ _vertex_polygon_indices[ j ][ k * 3 + l ] ] == j )
							// Set any index equaling j to i
							_indices[ _vertex_polygon_indices[ j ][ k * 3 + l ] ] == i;
				}
				
				// Destroy the extra vertex_polygon_index
				_vertex_polygon_indices.erase( _vertex_polygon_indices.begin() + j );
				
				for( k = 0; k < _indices.size(); k++ )
					if( _indices[ k ] > j )
						_indices[ k ]--;
				total++;
				j--;
			}
	
	_recalculate_all_normals();
			
	return total;*/
}

void Mesh::Mirror( bool x, bool y, bool z )
{
	if( !x && !y && !z )
		return;
	
	for( unsigned i = 0; i < _vertex_locations.size(); ++i )
	{
		if( x )
			_vertex_locations[ i ].X() = -_vertex_locations[ i ].X();
		if( y )
			_vertex_locations[ i ].Y() = -_vertex_locations[ i ].Y();
		if( z )
			_vertex_locations[ i ].Z() = -_vertex_locations[ i ].Z();
	}
	
	if( !( ( x && y && !z ) || ( x && z && !y ) || ( y && z && !x ) ) )
		FlipNormals();
	
	
	RecalculateAllNormals();
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

void Mesh::FlipNormals()
{
	for( unsigned i = 0; i < _triangles.size(); ++i )
		_triangles[ i ].ReverseVertices();
	for( unsigned i = 0; i < _quads.size(); ++i )
		_quads[ i ].ReverseVertices();
	
	RecalculateAllNormals();
	_change_operation( true, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
}

void Mesh::Unify()
{
	CalculateBoundingSphere();

	for( unsigned i = 0; i < _vertex_locations.size(); ++i )
	{
		_vertex_locations[ i ] -= _center;
		_vertex_locations[ i ] /= _diameter / 2;
	}
	_change_operation( false, true );
	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, false, false );
}

void Mesh::ToTriangles()
{
	const std::string total( ToString( static_cast< float >
					   ( _quads.size() ) ) );
	for( unsigned i = 0; i < _quads.size(); ++i )
	{
		_triangles.push_back( Triangle( _quads[ i ].V[ 0 ],
		                                _quads[ i ].V[ 1 ],
		                                _quads[ i ].V[ 2 ] ) );
		_triangles.push_back( Triangle( _quads[ i ].V[ 0 ],
		                                _quads[ i ].V[ 2 ],
		                                _quads[ i ].V[ 3 ] ) );

		/*Messenger << OutputValue( ( i + 1 ) * 1.0f / _quads.size() )
		  << ( i + 1 ) << " / " << total << OutputFlush();*/
	}
	_quads.clear();
	_quad_normals.clear();

	_reset_visibles();
	
	_triangle_normals.resize( _triangles.size() );
	_recalculate_vertex_users();
	RecalculateAllNormals();

	_visible_elements.RestoreOrder.Enabled = false;
	
	_change_operation( true, true );

	MeshHistory::Instance().SignalEntireSectionChanged().emit( true, true, true );
}