Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound Members | File Members

VectorInterpolationCompressor.cpp

Go to the documentation of this file.
00001 //------------------------------------------------------------------------------
00002 // Lamp : Open source game middleware
00003 // Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
00004 //
00005 // This library is free software; you can redistribute it and/or
00006 // modify it under the terms of the GNU Lesser General Public
00007 // License as published by the Free Software Foundation; either
00008 // version 2.1 of the License, or (at your option) any later version.
00009 //
00010 // This library is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013 // Lesser General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU Lesser General Public
00016 // License along with this library; if not, write to the Free Software
00017 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00018 //------------------------------------------------------------------------------
00019 
00020 /** @file
00021  * ベクトル補間圧縮実装
00022  * @author Junpee
00023  */
00024 
00025 #include "LampBasic.h"
00026 #include "Animation/VectorInterpolator/VectorInterpolationCompressor.h"
00027 #include "Animation/VectorInterpolator/VectorArrayInterpolator.h"
00028 #include "Animation/VectorInterpolator/VectorConstantInterpolator.h"
00029 #include "Animation/VectorInterpolator/VectorLinearInterpolator.h"
00030 #include "Core/Container/Deque.h"
00031 
00032 namespace Lamp{
00033 
00034 //------------------------------------------------------------------------------
00035 // 生成、破棄
00036 //------------------------------------------------------------------------------
00037 // コンストラクタ
00038 VectorInterpolationCompressor::VectorInterpolationCompressor() :
00039     tolerance_(0.f), length_(0.f), sourceKeyCount_(0), compressedKeyCount_(0),
00040     compressedKeySize_(0){
00041 }
00042 //------------------------------------------------------------------------------
00043 // デストラクタ
00044 VectorInterpolationCompressor::~VectorInterpolationCompressor(){
00045 }
00046 //------------------------------------------------------------------------------
00047 // 圧縮
00048 //------------------------------------------------------------------------------
00049 // 圧縮
00050 VectorInterpolator* VectorInterpolationCompressor::compress(
00051     VectorArrayInterpolator* source, float tolerance){
00052     // 圧縮準備
00053     compressSetup(source, tolerance);
00054     VectorInterpolator* result = NULL;
00055 
00056     // 定数圧縮
00057     result = compressConstant(source);
00058     if(result != NULL){ return result; }
00059 
00060     // 線形圧縮
00061     result = compressLinear(source);
00062     if(result != NULL){ return result; }
00063 
00064     // スプライン系の圧縮と線形圧縮の結果を重み付けした上で比較して出力可能
00065     // その場合にsetCompressedDataを忘れないように注意
00066 
00067     // 全ての圧縮に失敗したなら元データのコピーを返す
00068     result = source->duplicate();
00069     setCompressedData(getSourceKeyCount(), sourceKeySize_);
00070     
00071     return result;
00072 }
00073 //------------------------------------------------------------------------------
00074 // 圧縮準備
00075 void VectorInterpolationCompressor::compressSetup(
00076     VectorArrayInterpolator* source, float tolerance){
00077     Assert((source != NULL) && (tolerance >= 0.f));
00078     tolerance_ = tolerance;
00079     length_ = source->getLength();
00080     sourceKeyCount_ = source->getSize();
00081     Assert(sourceKeyCount_ > 1);
00082 }
00083 //------------------------------------------------------------------------------
00084 // 定数圧縮
00085 VectorInterpolator* VectorInterpolationCompressor::compressConstant(
00086     VectorArrayInterpolator* source){
00087     // ターゲットとなる値の算出、バウンディングボックスの中心
00088     AxisAlignedBox boundingBox(source->getValue(0), source->getValue(0));
00089     for(int i = 1; i < sourceKeyCount_; i++){
00090         boundingBox.merge(source->getValue(i));
00091     }
00092     Vector3 targetValue = boundingBox.getCenter();
00093 
00094     // 誤差チェック
00095     float squaredTolerance = getTolerance() * getTolerance();
00096     for(int i = 0; i < sourceKeyCount_; i++){
00097         Vector3 distance = source->getValue(i) - targetValue;
00098         // 定数圧縮に失敗
00099         if(distance.getSquaredLength() > squaredTolerance){ return NULL; }
00100     }
00101 
00102     // 定数圧縮に成功
00103     VectorConstantInterpolator* result = new VectorConstantInterpolator();
00104     result->setLength(getLength());
00105     result->setValue(targetValue);
00106     setCompressedData(1, sizeof(Vector3) + sizeof(float));
00107     return result;
00108 }
00109 //------------------------------------------------------------------------------
00110 // 線形圧縮
00111 VectorInterpolator* VectorInterpolationCompressor::compressLinear(
00112     VectorArrayInterpolator* source){
00113     // キーのリストを作成し、誤差が小さいキーから間引いていく
00114 
00115     // キーリストの作成
00116     int sourceKeyCount = getSourceKeyCount();
00117     Deque<LinearKey> keys_(sourceKeyCount);
00118     for(int i = 0; i < sourceKeyCount; i++){
00119         LinearKey key;
00120         key.value_ = source->getValue(i);
00121         key.time_ = (float)i;
00122         keys_.pushBack(key);
00123     }
00124 
00125     // 全誤差の算出
00126     int keyCount = keys_.getCount();
00127     int maxKeyCount = keyCount - 1;
00128     // 最初と最後の値は操作しない
00129     keys_[0].squaredError_ = 0.f;
00130     keys_[maxKeyCount].squaredError_ = 0.f;
00131     Assert(keys_[0].time_ == 0.f)
00132     Assert(keys_[maxKeyCount].time_ == getLength());
00133     for(int i = 1; i < maxKeyCount; i++){
00134         LinearKey& key = keys_[i];
00135         LinearKey& preKey = keys_[i - 1];
00136         LinearKey& postKey = keys_[i + 1];
00137         // 誤差の初期化時は前のキーと後ろのキーの平均が補間値になる
00138         Vector3 value = (preKey.value_ + postKey.value_) * 0.5f;
00139         key.squaredError_ = (value - key.value_).getSquaredLength();
00140     }
00141 
00142     // 圧縮ループ、キーが2個になったら抜ける
00143     float squaredTolerance = getTolerance() * getTolerance();
00144     while(keys_.getCount() > 2){
00145         // 誤差が最小のキーを調べる
00146         int targetIndex = 1;
00147         float targetSquaredError = keys_[targetIndex].squaredError_;
00148         maxKeyCount = keys_.getCount() - 1;
00149         for(int i = 2; i < maxKeyCount; i++){
00150             if(keys_[i].squaredError_ < targetSquaredError){
00151                 targetSquaredError = keys_[i].squaredError_;
00152                 targetIndex = i;
00153             }
00154         }
00155 
00156         // 最小誤差が許容範囲外なら圧縮ループを抜ける
00157         if(targetSquaredError > squaredTolerance){ break; }
00158 
00159         // 最小誤差キーの削除と誤差のアップデート
00160         keys_.remove(targetIndex);
00161         // 前のキーが先頭キーでなければ誤差を再計算
00162         if((targetIndex - 1) > 0){
00163             recalcLinearError(source, keys_[targetIndex - 2],
00164                 keys_[targetIndex - 1], keys_[targetIndex]);
00165         }
00166         // 後ろのキーが最後尾キーでなければ誤差を再計算
00167         if(targetIndex < (keys_.getCount() - 1)){
00168             recalcLinearError(source, keys_[targetIndex - 1],
00169                 keys_[targetIndex], keys_[targetIndex + 1]);
00170         }
00171 
00172     }
00173 
00174     // サイズが小さくなっていなければ失敗、失敗条件を厳しくするのもあり
00175     keyCount = keys_.getCount();
00176     int keySize = sizeof(Vector3) + sizeof(float);
00177     if((keyCount * keySize) >= getSourceSize()){ return NULL; }
00178 
00179     // 線形圧縮に成功
00180     VectorLinearInterpolator* result = new VectorLinearInterpolator();
00181     result->setKeyCount(keyCount);
00182     for(int i = 0; i < keyCount; i++){
00183         LinearKey& key = keys_[i];
00184         result->setKey(i, key.time_, key.value_);
00185     }
00186     setCompressedData(keyCount, keySize);
00187     return result;
00188 }
00189 //------------------------------------------------------------------------------
00190 // 線形圧縮誤差の再計算
00191 void VectorInterpolationCompressor::recalcLinearError(
00192     VectorArrayInterpolator* source,
00193     LinearKey& preKey, LinearKey& key, LinearKey& postKey){
00194     int preTime = (int)preKey.time_;
00195     Vector3 preValue = preKey.value_;
00196     int postTime = (int)postKey.time_;
00197     Vector3 postValue = postKey.value_;
00198     int timeRange = postTime - preTime;
00199     Vector3 distance = postValue - preValue;
00200 
00201     // 最大の二乗誤差を算出
00202     float maxSquaredError = 0.f;
00203     for(int i = 1; i < timeRange; i++){
00204         int time = preTime + i;
00205         Vector3 sourceValue = source->getValue(time);
00206         float rate = (float)i / (float)timeRange;
00207         Vector3 targetValue = distance * rate + preValue;
00208         float squaredError = (targetValue - sourceValue).getSquaredLength();
00209         if(squaredError > maxSquaredError){ maxSquaredError = squaredError; }
00210     }
00211     key.squaredError_ = maxSquaredError;
00212 }
00213 //------------------------------------------------------------------------------
00214 // 圧縮結果
00215 //------------------------------------------------------------------------------
00216 // 結果文字列の取得
00217 String VectorInterpolationCompressor::getResultString() const{
00218     String result;
00219     result.format(
00220         "%.2f%%  Key %d/%d  Size %.2f/%.2fKb  Length %.0f",
00221         getCompressionRate() * 100.f,
00222         getCompressedKeyCount(), getSourceKeyCount(),
00223         (float)getCompressedSize() / 1024.f, (float)getSourceSize() / 1024.f,
00224         getLength());
00225     return result;
00226 }
00227 //------------------------------------------------------------------------------
00228 } // End of namespace Lamp
00229 //------------------------------------------------------------------------------

Generated on Wed Mar 16 10:29:38 2005 for Lamp by doxygen 1.3.2