nevrax.org : docs

00001 
+00007 /* Copyright, 2000-2002 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "std3d.h"
+00027 
+00028 #include "3d/animation_optimizer.h"
+00029 #include "nel/misc/mem_stream.h"
+00030 #include "nel/misc/vectord.h"
+00031 #include "3d/track.h"
+00032 #include "3d/track_keyframer.h"
+00033 #include "3d/animation.h"
+00034 #include "3d/track_sampled_quat.h"
+00035 #include "3d/track_sampled_vector.h"
+00036 
+00037 
+00038 using   namespace NLMISC;
+00039 using   namespace std;
+00040 
+00041 
+00042 namespace NL3D 
+00043 {
+00044 
+00045 
+00046 // ***************************************************************************
+00047 CAnimationOptimizer::CAnimationOptimizer()
+00048 {
+00049         _SampleFrameRate= 30;
+00050         _QuaternionThresholdLowPrec= 1.0 - 0.0001;
+00051         _QuaternionThresholdHighPrec= 1.0 - 0.000001;
+00052         _VectorThresholdLowPrec= 0.001;
+00053         _VectorThresholdHighPrec= 0.0001;
+00054 }
+00055 
+00056 
+00057 // ***************************************************************************
+00058 void            CAnimationOptimizer::setQuaternionThreshold(double lowPrecThre, double highPrecThre)
+00059 {
+00060         nlassert(lowPrecThre>=0);
+00061         nlassert(highPrecThre>=0);
+00062         _QuaternionThresholdLowPrec= 1.0 - lowPrecThre;
+00063         _QuaternionThresholdHighPrec= 1.0 - highPrecThre;
+00064 }
+00065 
+00066 
+00067 // ***************************************************************************
+00068 void            CAnimationOptimizer::setVectorThreshold(double lowPrecThre, double highPrecThre)
+00069 {
+00070         nlassert(lowPrecThre>=0);
+00071         nlassert(highPrecThre>=0);
+00072         _VectorThresholdLowPrec= lowPrecThre;
+00073         _VectorThresholdHighPrec= highPrecThre;
+00074 }
+00075 
+00076 
+00077 // ***************************************************************************
+00078 void            CAnimationOptimizer::setSampleFrameRate(float frameRate)
+00079 {
+00080         nlassert(frameRate>0);
+00081         _SampleFrameRate= frameRate;
+00082 }
+00083 
+00084 
+00085 // ***************************************************************************
+00086 void            CAnimationOptimizer::optimize(const CAnimation &animIn, CAnimation &animOut)
+00087 {
+00088         // reset animOut
+00089         contReset(animOut);
+00090 
+00091         // Parse all tracks of the animation.
+00092         set<string>             setString;
+00093         animIn.getTrackNames (setString);
+00094         set<string>::iterator   it;
+00095 
+00096         for(it=setString.begin();it!=setString.end();it++)
+00097         {
+00098                 const string    &trackName= *it;
+00099                 uint    trackId= animIn.getIdTrackByName(trackName);
+00100                 nlassert(trackId!=CAnimation::NotFound);
+00101                 const ITrack    *track= animIn.getTrack(trackId);
+00102 
+00103                 // If the track is optimisable.
+00104                 ITrack  *newTrack;
+00105                 if(isTrackOptimisable(track))
+00106                 {
+00107                         // choose the threshold according to precision wanted
+00108                         if( isLowPrecisionTrack(trackName) )
+00109                         {
+00110                                 _QuaternionThreshold= _QuaternionThresholdLowPrec;
+00111                                 _VectorThreshold= _VectorThresholdLowPrec;
+00112                         }
+00113                         else
+00114                         {
+00115                                 _QuaternionThreshold= _QuaternionThresholdHighPrec;
+00116                                 _VectorThreshold= _VectorThresholdHighPrec;
+00117                         }
+00118 
+00119                         // optimize it.
+00120                         newTrack= optimizeTrack(track);
+00121                 }
+00122                 else
+00123                 {
+00124                         // just clone it.
+00125                         newTrack= cloneTrack(track);
+00126                 }
+00127 
+00128                 // Add it to the animation
+00129                 animOut.addTrack(trackName, newTrack);
+00130         }
+00131 
+00132         // Set min animation length
+00133         animOut.setMinEndTime (animIn.getEndTime ());
+00134         nlassert (animOut.getEndTime() == animIn.getEndTime());
+00135 }
+00136 
+00137 // ***************************************************************************
+00138 ITrack          *CAnimationOptimizer::cloneTrack(const ITrack   *trackIn)
+00139 {
+00140         CMemStream      memStream;
+00141 
+00142         // write to the stream.
+00143         ITrack  *trackInSerial= const_cast<ITrack*>(trackIn);
+00144         memStream.serialPolyPtr(trackInSerial);
+00145 
+00146         // read from the stream.
+00147         memStream.invert();
+00148         ITrack  *ret= NULL;
+00149         memStream.serialPolyPtr(ret);
+00150 
+00151         return ret;
+00152 }
+00153 
+00154 
+00155 // ***************************************************************************
+00156 bool            CAnimationOptimizer::isTrackOptimisable(const ITrack    *trackIn)
+00157 {
+00158         nlassert(trackIn);
+00159 
+00160         // If the track is a Linear, Bezier or a TCB track, suppose we can optimize it. Constant may not be interressant....
+00161         if(     dynamic_cast<const CTrackKeyFramerTCBQuat*>(trackIn) || 
+00162                 dynamic_cast<const CTrackKeyFramerBezierQuat*>(trackIn) ||
+00163                 dynamic_cast<const CTrackKeyFramerLinearQuat*>(trackIn) )
+00164                 return true;
+00165 
+00166         // If the track is a Linear, Bezier or a TCB track, suppose we can optimize it. Constant may not be interressant....
+00167         if(     dynamic_cast<const CTrackKeyFramerTCBVector*>(trackIn) || 
+00168                 dynamic_cast<const CTrackKeyFramerBezierVector*>(trackIn) ||
+00169                 dynamic_cast<const CTrackKeyFramerLinearVector*>(trackIn) )
+00170                 return true;
+00171 
+00172         return false;
+00173 }
+00174 
+00175 
+00176 // ***************************************************************************
+00177 ITrack          *CAnimationOptimizer::optimizeTrack(const ITrack        *trackIn)
+00178 {
+00179         // Get track param.
+00180         float beginTime= trackIn->getBeginTime();
+00181         float endTime= trackIn->getEndTime();
+00182         nlassert(endTime>=beginTime);
+00183 
+00184         // Get num Sample 
+00185         uint    numSamples= (uint)ceil( (endTime-beginTime)*_SampleFrameRate);
+00186         numSamples= max(1U, numSamples);
+00187         nlassert(numSamples<65535);
+00188 
+00189 
+00190         // Optimize Quaternion track??
+00191         //================
+00192         if( dynamic_cast<const CAnimatedValueQuat *>(&trackIn->getValue()) )
+00193         {
+00194                 // sample the animation. Store result in _TimeList/_QuatKeyList
+00195                 sampleQuatTrack(trackIn, beginTime, endTime, numSamples);
+00196 
+00197                 // check if the sampled track can be reduced to a TrackDefaultQuat. Test _QuatKeyList.
+00198                 if( testConstantQuatTrack() )
+00199                 {
+00200                         // create a default Track Quat.
+00201                         CTrackDefaultQuat       *trackDefault= new CTrackDefaultQuat;
+00202                         // setup the uniform value.
+00203                         trackDefault->setValue(_QuatKeyList[0]);
+00204 
+00205                         // return the result.
+00206                         return trackDefault;
+00207                 }
+00208                 // else optimize the sampled animation, and build.
+00209                 else
+00210                 {
+00211                         // optimize.
+00212                         optimizeQuatTrack();
+00213 
+00214                         // Create a sampled quaternion track
+00215                         CTrackSampledQuat       *trackSQ= new CTrackSampledQuat;
+00216 
+00217                         // Copy loop from track.
+00218                         trackSQ->setLoopMode(trackIn->getLoopMode());
+00219 
+00220                         // Build it.
+00221                         trackSQ->build(_TimeList, _QuatKeyList, beginTime, endTime);
+00222 
+00223                         // return result.
+00224                         return trackSQ;
+00225                 }
+00226         }
+00227         // Optimize Position track??
+00228         //================
+00229         else if( dynamic_cast<const CAnimatedValueVector *>(&trackIn->getValue()) )
+00230         {
+00231                 // sample the animation. Store result in _TimeList/_VectorKeyList
+00232                 sampleVectorTrack(trackIn, beginTime, endTime, numSamples);
+00233 
+00234                 // check if the sampled track can be reduced to a TrackDefaultVector. Test _VectorKeyList.
+00235                 if( testConstantVectorTrack() )
+00236                 {
+00237                         // create a default Track Vector.
+00238                         CTrackDefaultVector     *trackDefault= new CTrackDefaultVector;
+00239                         // setup the uniform value.
+00240                         trackDefault->setValue(_VectorKeyList[0]);
+00241 
+00242                         // return the result.
+00243                         return trackDefault;
+00244                 }
+00245                 // else optimize the sampled animation, and build.
+00246                 else
+00247                 {
+00248                         // optimize.
+00249                         optimizeVectorTrack();
+00250 
+00251                         // Create a sampled Vector track
+00252                         CTrackSampledVector     *trackSV= new CTrackSampledVector;
+00253 
+00254                         // Copy loop from track.
+00255                         trackSV->setLoopMode(trackIn->getLoopMode());
+00256 
+00257                         // Build it.
+00258                         trackSV->build(_TimeList, _VectorKeyList, beginTime, endTime);
+00259 
+00260                         // return result.
+00261                         return trackSV;
+00262                 }
+00263         }
+00264         else
+00265         {
+00266                 // Must be a quaternion track or vector track for now.
+00267                 nlstop;
+00268                 // Avoid warning.
+00269                 return cloneTrack(trackIn);
+00270         }
+00271 }
+00272 
+00273 
+00274 // ***************************************************************************
+00275 // ***************************************************************************
+00276 // Quaternion optimisation
+00277 // ***************************************************************************
+00278 // ***************************************************************************
+00279 
+00280 
+00281 // ***************************************************************************
+00282 void            CAnimationOptimizer::sampleQuatTrack(const ITrack *trackIn, float beginTime, float endTime, uint numSamples)
+00283 {
+00284         // resize tmp samples
+00285         _TimeList.resize(numSamples);
+00286         _QuatKeyList.resize(numSamples);
+00287 
+00288         // Sample the animation.
+00289         float   t= beginTime;
+00290         float   dt= 0;
+00291         if(numSamples>1)
+00292                 dt= (endTime-beginTime)/(numSamples-1);
+00293         for(uint i=0;i<numSamples; i++, t+=dt)
+00294         {
+00295                 CQuat   quat;
+00296 
+00297                 // make exact endTime match (avoid precision problem)
+00298                 if(i==numSamples-1)
+00299                         t= endTime;
+00300 
+00301                 // evaluate the track
+00302                 const_cast<ITrack*>(trackIn)->interpolate(t, quat);
+00303 
+00304                 // normalize this quaternion
+00305                 quat.normalize();
+00306 
+00307                 // force on same hemisphere according to precedent frame.
+00308                 if(i>0)
+00309                 {
+00310                         quat.makeClosest(_QuatKeyList[i-1]);
+00311                 }
+00312 
+00313                 // store time and key.
+00314                 _TimeList[i]= i;
+00315                 _QuatKeyList[i]= quat;
+00316         }
+00317 
+00318 }
+00319 
+00320 // ***************************************************************************
+00321 bool            CAnimationOptimizer::testConstantQuatTrack()
+00322 {
+00323         uint    numSamples= _QuatKeyList.size();
+00324         nlassert(numSamples>0);
+00325 
+00326         // Get the first sample as the reference quaternion, and test others from this one.
+00327         CQuat   quatRef= _QuatKeyList[0];
+00328         for(uint i=0;i<numSamples;i++)
+00329         {
+00330                 // All values must be nearly equal to the reference quaternion.
+00331                 if(!nearlySameQuaternion(quatRef, _QuatKeyList[i]))
+00332                         return false;
+00333         }
+00334 
+00335         // ok.
+00336         return true;
+00337 }
+00338 
+00339 
+00340 // ***************************************************************************
+00341 void            CAnimationOptimizer::optimizeQuatTrack()
+00342 {
+00343         uint    numSamples= _QuatKeyList.size();
+00344         nlassert(numSamples>0);
+00345 
+00346         // <=2 key? => no opt possible..
+00347         if(numSamples<=2)
+00348                 return;
+00349 
+00350         // prepare dest opt
+00351         std::vector<uint16>             optTimeList;
+00352         std::vector<CQuat>              optKeyList;
+00353         optTimeList.reserve(numSamples);
+00354         optKeyList.reserve(numSamples);
+00355 
+00356         // Add the first key.
+00357         optTimeList.push_back(_TimeList[0]);
+00358         optKeyList.push_back(_QuatKeyList[0]);
+00359         double  timeRef= _TimeList[0];
+00360         CQuatD  quatRef= _QuatKeyList[0];
+00361 
+00362         // For all keys, but the first and the last, test if can remove them.
+00363         for(uint i=1; i<numSamples-1; i++)
+00364         {
+00365                 CQuatD  quatCur= _QuatKeyList[i];
+00366                 CQuatD  quatNext= _QuatKeyList[i+1];
+00367                 double  timeCur= _TimeList[i];
+00368                 double  timeNext= _TimeList[i+1];
+00369 
+00370                 // must add the key?
+00371                 bool    mustAdd= false;
+00372 
+00373                 // If the Delta time are too big, abort (CTrackSampledQuat limitation)
+00374                 if(timeNext-timeRef>255)
+00375                 {
+00376                         mustAdd= true;
+00377                 }
+00378                 // If the next quaternion or the current quaternion are not on same hemisphere than ref, abort.
+00379                 else if( CQuatD::dotProduct(quatCur, quatRef)<0 || CQuatD::dotProduct(quatNext, quatRef)<0 )
+00380                 {
+00381                         mustAdd= true;
+00382                 }
+00383                 // else, test interpolation
+00384                 else
+00385                 {
+00386                         // If the 3 quats are nearly equals, it is ok (avoid interpolation)
+00387                         if( nearlySameQuaternion(quatRef, quatCur) && nearlySameQuaternion(quatRef, quatNext) )
+00388                                 mustAdd= false;
+00389                         else
+00390                         {
+00391                                 // interpolate.
+00392                                 CQuatD  quatInterpolated;
+00393                                 double  t= (timeCur-timeRef)/(timeNext/timeRef);
+00394                                 quatInterpolated= CQuatD::slerp(quatRef, quatNext, (float)t);
+00395 
+00396                                 // test if cur and interpolate are equal.
+00397                                 if( !nearlySameQuaternion(quatCur, quatInterpolated) )
+00398                                         mustAdd= true;
+00399                         }
+00400                 }
+00401 
+00402                 // If must add the key to the optimized track.
+00403                 if(mustAdd)
+00404                 {
+00405                         optTimeList.push_back(_TimeList[i]);
+00406                         optKeyList.push_back(_QuatKeyList[i]);
+00407                         timeRef= _TimeList[i];
+00408                         quatRef= _QuatKeyList[i];
+00409                 }
+00410         }
+00411 
+00412         // Add the last key.
+00413         optTimeList.push_back(_TimeList[numSamples-1]);
+00414         optKeyList.push_back(_QuatKeyList[numSamples-1]);
+00415 
+00416         // copy the optimized track to the main one.
+00417         _TimeList= optTimeList;
+00418         _QuatKeyList= optKeyList;
+00419 }
+00420 
+00421 
+00422 // ***************************************************************************
+00423 bool            CAnimationOptimizer::nearlySameQuaternion(const CQuatD &quat0, const CQuatD &quat1)
+00424 {
+00425         // true if exactly same, or exactly inverse
+00426         if(quat0==quat1 || quat0==-quat1)
+00427                 return true;
+00428 
+00429         // Else compute the rotation to go from qRef to q. Use double for better presion.
+00430         CQuatD  quatDif;
+00431         quatDif= quat1 * quat0.conjugate();
+00432         // inverse the quaternion if necessary. ie make closest to the identity quaternion.
+00433         if(quatDif.w<0)
+00434                 quatDif= -quatDif;
+00435 
+00436         // compare "angle threshold"
+00437         return (quatDif.w >= _QuaternionThreshold);
+00438 }
+00439 
+00440 
+00441 // ***************************************************************************
+00442 // ***************************************************************************
+00443 // Vector optimisation
+00444 // ***************************************************************************
+00445 // ***************************************************************************
+00446 
+00447 
+00448 // ***************************************************************************
+00449 void            CAnimationOptimizer::sampleVectorTrack(const ITrack *trackIn, float beginTime, float endTime, uint numSamples)
+00450 {
+00451         // resize tmp samples
+00452         _TimeList.resize(numSamples);
+00453         _VectorKeyList.resize(numSamples);
+00454 
+00455         // Sample the animation.
+00456         float   t= beginTime;
+00457         float   dt= 0;
+00458         if(numSamples>1)
+00459                 dt= (endTime-beginTime)/(numSamples-1);
+00460         for(uint i=0;i<numSamples; i++, t+=dt)
+00461         {
+00462                 CVector vector;
+00463 
+00464                 // make exact endTime match (avoid precision problem)
+00465                 if(i==numSamples-1)
+00466                         t= endTime;
+00467 
+00468                 // evaluate the track
+00469                 const_cast<ITrack*>(trackIn)->interpolate(t, vector);
+00470 
+00471                 // store time and key.
+00472                 _TimeList[i]= i;
+00473                 _VectorKeyList[i]= vector;
+00474         }
+00475 
+00476 }
+00477 
+00478 // ***************************************************************************
+00479 bool            CAnimationOptimizer::testConstantVectorTrack()
+00480 {
+00481         uint    numSamples= _VectorKeyList.size();
+00482         nlassert(numSamples>0);
+00483 
+00484         // Get the first sample as the reference Vectorer, and test others from this one.
+00485         CVector vectorRef= _VectorKeyList[0];
+00486         for(uint i=0;i<numSamples;i++)
+00487         {
+00488                 // All values must be nearly equal to the reference vector.
+00489                 if(!nearlySameVector(vectorRef, _VectorKeyList[i]))
+00490                         return false;
+00491         }
+00492 
+00493         // ok.
+00494         return true;
+00495 }
+00496 
+00497 
+00498 // ***************************************************************************
+00499 void            CAnimationOptimizer::optimizeVectorTrack()
+00500 {
+00501         uint    numSamples= _VectorKeyList.size();
+00502         nlassert(numSamples>0);
+00503 
+00504         // <=2 key? => no opt possible..
+00505         if(numSamples<=2)
+00506                 return;
+00507 
+00508         // prepare dest opt
+00509         std::vector<uint16>             optTimeList;
+00510         std::vector<CVector>    optKeyList;
+00511         optTimeList.reserve(numSamples);
+00512         optKeyList.reserve(numSamples);
+00513 
+00514         // Add the first key.
+00515         optTimeList.push_back(_TimeList[0]);
+00516         optKeyList.push_back(_VectorKeyList[0]);
+00517         double          timeRef= _TimeList[0];
+00518         CVectorD        vectorRef= _VectorKeyList[0];
+00519 
+00520         // For all keys, but the first and the last, test if can remove them.
+00521         for(uint i=1; i<numSamples-1; i++)
+00522         {
+00523                 CVectorD        vectorCur= _VectorKeyList[i];
+00524                 CVectorD        vectorNext= _VectorKeyList[i+1];
+00525                 double  timeCur= _TimeList[i];
+00526                 double  timeNext= _TimeList[i+1];
+00527 
+00528                 // must add the key?
+00529                 bool    mustAdd= false;
+00530 
+00531                 // If the Delta time are too big, abort (CTrackSampledVector limitation)
+00532                 if(timeNext-timeRef>255)
+00533                 {
+00534                         mustAdd= true;
+00535                 }
+00536                 // else, test interpolation
+00537                 else
+00538                 {
+00539                         // If the 3 Vectors are nearly equals, it is ok (avoid interpolation)
+00540                         if( nearlySameVector(vectorRef, vectorCur) && nearlySameVector(vectorRef, vectorNext) )
+00541                                 mustAdd= false;
+00542                         else
+00543                         {
+00544                                 // interpolate.
+00545                                 CVectorD        vectorInterpolated;
+00546                                 double  t= (timeCur-timeRef)/(timeNext/timeRef);
+00547                                 vectorInterpolated= vectorRef*(1-t) + vectorNext*t;
+00548 
+00549                                 // test if cur and interpolate are equal.
+00550                                 if( !nearlySameVector(vectorCur, vectorInterpolated) )
+00551                                         mustAdd= true;
+00552                         }
+00553                 }
+00554 
+00555                 // If must add the key to the optimized track.
+00556                 if(mustAdd)
+00557                 {
+00558                         optTimeList.push_back(_TimeList[i]);
+00559                         optKeyList.push_back(_VectorKeyList[i]);
+00560                         timeRef= _TimeList[i];
+00561                         vectorRef= _VectorKeyList[i];
+00562                 }
+00563         }
+00564 
+00565         // Add the last key.
+00566         optTimeList.push_back(_TimeList[numSamples-1]);
+00567         optKeyList.push_back(_VectorKeyList[numSamples-1]);
+00568 
+00569         // copy the optimized track to the main one.
+00570         _TimeList= optTimeList;
+00571         _VectorKeyList= optKeyList;
+00572 }
+00573 
+00574 
+00575 // ***************************************************************************
+00576 bool            CAnimationOptimizer::nearlySameVector(const CVectorD &v0, const CVectorD &v1)
+00577 {
+00578         // true if exactly same
+00579         if(v0==v1)
+00580                 return true;
+00581 
+00582         // Else compute the dif, use double for better precision
+00583         CVectorD        vDif;
+00584         vDif= v1-v0;
+00585 
+00586         // compare norm
+00587         return (vDif.norm() <= _VectorThreshold);
+00588 }
+00589 
+00590 
+00591 // ***************************************************************************
+00592 // ***************************************************************************
+00593 // LowPrecisionTrack
+00594 // ***************************************************************************
+00595 // ***************************************************************************
+00596 
+00597 
+00598 // ***************************************************************************
+00599 void            CAnimationOptimizer::addLowPrecisionTrack(const std::string &name)
+00600 {
+00601         _LowPrecTrackKeyName.push_back(name);
+00602 }
+00603 
+00604 // ***************************************************************************
+00605 void            CAnimationOptimizer::clearLowPrecisionTracks()
+00606 {
+00607         _LowPrecTrackKeyName.clear();
+00608 }
+00609 
+00610 // ***************************************************************************
+00611 bool            CAnimationOptimizer::isLowPrecisionTrack(const std::string &trackName)
+00612 {
+00613         for(uint i=0; i<_LowPrecTrackKeyName.size(); i++)
+00614         {
+00615                 // if find a substr of the key, it is a low prec track
+00616                 if( trackName.find(_LowPrecTrackKeyName[i]) != string::npos )
+00617                         return true;
+00618         }
+00619 
+00620         // no key found
+00621         return false;
+00622 }
+00623 
+00624 
+00625 } // NL3D
+
animation_optimizer.cpp
