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 //------------------------------------------------------------------------------