//------------------------------------------------------------------------------
// Lamp : Open source game middleware
// Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library 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
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//------------------------------------------------------------------------------

/** @file
 * 回転補間圧縮実装
 * @author Junpee
 */

#include "LampBasic.h"
#include "Animation/RotationInterpolator/RotationInterpolationCompressor.h"
#include "Animation/RotationInterpolator/QuaternionArrayInterpolator.h"
#include "Animation/RotationInterpolator/EulerArrayInterpolator.h"
#include "Animation/RotationInterpolator/RotationConstantInterpolator.h"
#include "Animation/RotationInterpolator/QuaternionLinearInterpolator.h"
#include "Core/Container/Deque.h"

namespace Lamp{

//------------------------------------------------------------------------------
// 生成、破棄
//------------------------------------------------------------------------------
// コンストラクタ
RotationInterpolationCompressor::RotationInterpolationCompressor() :
	tolerance_(0.f), length_(0.f), sourceKeyCount_(0), compressedKeyCount_(0),
	compressedKeySize_(0){
}
//------------------------------------------------------------------------------
// デストラクタ
RotationInterpolationCompressor::~RotationInterpolationCompressor(){
}
//------------------------------------------------------------------------------
// 圧縮
//------------------------------------------------------------------------------
// 圧縮
RotationInterpolator* RotationInterpolationCompressor::compress(
	EulerArrayInterpolator* source, float tolerance){
	// 四元数回転配列補間に変換して圧縮する
	QuaternionArrayInterpolator* interpolator =
		source->convertQuaternionArrayInterpolator();
	RotationInterpolator* result = compress(interpolator, tolerance);
	delete interpolator;
	return result;
}
//------------------------------------------------------------------------------
// 圧縮
RotationInterpolator* RotationInterpolationCompressor::compress(
	QuaternionArrayInterpolator* source, float tolerance){
	// 圧縮準備
	compressSetup(source, tolerance);
	RotationInterpolator* result = NULL;

	// 定数圧縮
	result = compressConstant(source);
	if(result != NULL){ return result; }

	// 線形圧縮
	result = compressLinear(source);
	if(result != NULL){ return result; }

	// スプライン系の圧縮と線形圧縮の結果を重み付けした上で比較して出力可能
	// その場合にsetCompressedDataを忘れないように注意

	// 全ての圧縮に失敗したなら元データのコピーを返す
	result = source->duplicate();
	setCompressedData(getSourceKeyCount(), sourceKeySize_);
	
	return result;
}
//------------------------------------------------------------------------------
// 圧縮準備
void RotationInterpolationCompressor::compressSetup(
	QuaternionArrayInterpolator* source, float tolerance){
	Assert(source != NULL); 
	Assert((tolerance >= 0.f) && (tolerance < Math::halfPI));
	tolerance_ = tolerance;
	length_ = source->getLength();
	sourceKeyCount_ = source->getSize();
	Assert(sourceKeyCount_ > 1);
}
//------------------------------------------------------------------------------
// 定数圧縮
RotationInterpolator* RotationInterpolationCompressor::compressConstant(
	QuaternionArrayInterpolator* source){
	// ターゲットとなる値の算出、最初の値を使用する
	const Quaternion& targetValue = source->getValue(0);
	Assert(targetValue.isUnit());

	// 誤差チェック
	float toleranceCos = Math::cos(getTolerance());
	for(int i = 0; i < sourceKeyCount_; i++){
		const Quaternion& sourceValue = source->getValue(i);
		Assert(sourceValue.isUnit());
		// 定数圧縮に失敗
		if(targetValue.dotProduct(sourceValue) < toleranceCos){ return NULL; }
	}

	// 定数圧縮に成功
	RotationConstantInterpolator* result = new RotationConstantInterpolator();
	result->setLength(getLength());
	result->setQuaternion(targetValue);
	setCompressedData(1, sizeof(Quaternion) + sizeof(float));
	return result;
}
//------------------------------------------------------------------------------
// 線形圧縮
RotationInterpolator* RotationInterpolationCompressor::compressLinear(
	QuaternionArrayInterpolator* source){
	// キーのリストを作成し、誤差が小さいキーから間引いていく

	// キーリストの作成
	int sourceKeyCount = getSourceKeyCount();
	Deque<LinearKey> keys_(sourceKeyCount);
	for(int i = 0; i < sourceKeyCount; i++){
		LinearKey key;
		key.value_ = source->getValue(i);
		key.time_ = (float)i;
		keys_.pushBack(key);
	}

	// 全誤差の算出
	int keyCount = keys_.getCount();
	int maxKeyCount = keyCount - 1;
	// 最初と最後の値は操作しない
	keys_[0].errorCos_ = 1.f;
	keys_[maxKeyCount].errorCos_ = 1.f;
	Assert(keys_[0].time_ == 0.f)
	Assert(keys_[maxKeyCount].time_ == getLength());
	Assert(keys_[0].value_.dotProduct(keys_[1].value_) >= 0.f);
	for(int i = 1; i < maxKeyCount; i++){
		LinearKey& key = keys_[i];
		LinearKey& preKey = keys_[i - 1];
		LinearKey& postKey = keys_[i + 1];
		Assert(key.value_.dotProduct(postKey.value_) >= 0.f);
		// 前のキーと後ろのキーの中間の値との誤差
		Quaternion value =
			Quaternion::slerp(preKey.value_, postKey.value_, 0.5f);
		key.errorCos_ = key.value_.dotProduct(value);
	}

	// 圧縮ループ、キーが2個になったら抜ける
	float toleranceCos = Math::cos(getTolerance());
	while(keys_.getCount() > 2){
		// 誤差が最小のキーを調べる
		int targetIndex = 0;
		float targetErrorCos = -1.f;
		maxKeyCount = keys_.getCount() - 1;
		for(int i = 1; i < maxKeyCount; i++){
			// Cosがより1に近いと誤差が小さい
			// 前と後ろのキーの内積が0以上
//			if(keys_[i].errorCos_ > targetErrorCos){
			if((keys_[i].errorCos_ > targetErrorCos) &&
				(keys_[i - 1].value_.dotProduct(keys_[i + 1].value_) >= 0.f)){
				targetErrorCos = keys_[i].errorCos_;
				targetIndex = i;
			}
		}

		// ターゲットが見つからなかった
		if(targetIndex == 0){ break; }
		// 最小誤差が許容範囲外なら圧縮ループを抜ける
		if(targetErrorCos < toleranceCos){ break; }

		// 最小誤差キーの削除と誤差のアップデート
		keys_.remove(targetIndex);
		// 前のキーが先頭キーでなければ誤差を再計算
		if((targetIndex - 1) > 0){
			recalcLinearError(source, keys_[targetIndex - 2],
				keys_[targetIndex - 1], keys_[targetIndex]);
		}
		// 後ろのキーが最後尾キーでなければ誤差を再計算
		if(targetIndex < (keys_.getCount() - 1)){
			recalcLinearError(source, keys_[targetIndex - 1],
				keys_[targetIndex], keys_[targetIndex + 1]);
		}
	}

	// サイズが小さくなっていなければ失敗、失敗条件を厳しくするのもあり
	keyCount = keys_.getCount();
	int keySize = sizeof(Quaternion) + sizeof(float);
	if((keyCount * keySize) >= getSourceSize()){ return NULL; }

	// 線形圧縮に成功
	QuaternionLinearInterpolator* result = new QuaternionLinearInterpolator();
	result->setKeyCount(keyCount);
	for(int i = 0; i < keyCount; i++){
		LinearKey& key = keys_[i];
		result->setKey(i, key.time_, key.value_);
	}
	setCompressedData(keyCount, keySize);
	return result;
}
//------------------------------------------------------------------------------
// 線形圧縮誤差の再計算
void RotationInterpolationCompressor::recalcLinearError(
	QuaternionArrayInterpolator* source,
	LinearKey& preKey, LinearKey& key, LinearKey& postKey){
	int preTime = (int)preKey.time_;
	Quaternion preValue = preKey.value_;
	int postTime = (int)postKey.time_;
	Quaternion postValue = postKey.value_;
	int timeRange = postTime - preTime;

	// 最大誤差のCosを算出
	float maxErrorCos = 1.f;
	for(int i = 1; i < timeRange; i++){
		int time = preTime + i;
		Quaternion sourceValue = source->getValue(time);
		float rate = (float)i / (float)timeRange;
		Quaternion targetValue = Quaternion::slerp(preValue, postValue, rate);
		float errorCos = sourceValue.dotProduct(targetValue);
		if(errorCos < maxErrorCos){ maxErrorCos = errorCos; }
	}
	key.errorCos_ = maxErrorCos;
}
//------------------------------------------------------------------------------
// 圧縮結果
//------------------------------------------------------------------------------
// 結果文字列の取得
String RotationInterpolationCompressor::getResultString() const{
	String result;
	result.format(
		"%.2f%%  Key %d/%d  Size %.2f/%.2fKb  Length %.0f",
		getCompressionRate() * 100.f,
		getCompressedKeyCount(), getSourceKeyCount(),
		(float)getCompressedSize() / 1024.f, (float)getSourceSize() / 1024.f,
		getLength());
	return result;
}
//------------------------------------------------------------------------------
} // End of namespace Lamp
//------------------------------------------------------------------------------
