nel/src/3d/animation_optimizer.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/animation_optimizer.h"
  20 #include "nel/misc/mem_stream.h"
  21 #include "nel/misc/vectord.h"
  22 #include "nel/3d/track.h"
  23 #include "nel/3d/track_keyframer.h"
  24 #include "nel/3d/animation.h"
  25 #include "nel/3d/track_sampled_quat.h"
  26 #include "nel/3d/track_sampled_vector.h"
  27
  28
  29 using   namespace NLMISC;
  30 using   namespace std;
  31
  32 #ifdef DEBUG_NEW
  33 #define new DEBUG_NEW
  34 #endif
  35
  36 namespace NL3D
  37 {
  38
  39
  40 // ***************************************************************************
  41 CAnimationOptimizer::CAnimationOptimizer()
  42 {
  43         _SampleFrameRate= 30;
  44         _QuaternionThresholdLowPrec= 1.0 - 0.0001;
  45         _QuaternionThresholdHighPrec= 1.0 - 0.000001;
  46         _VectorThresholdLowPrec= 0.001;
  47         _VectorThresholdHighPrec= 0.0001;
  48 }
  49
  50
  51 // ***************************************************************************
  52 void            CAnimationOptimizer::setQuaternionThreshold(double lowPrecThre, double highPrecThre)
  53 {
  54         nlassert(lowPrecThre>=0);
  55         nlassert(highPrecThre>=0);
  56         _QuaternionThresholdLowPrec= 1.0 - lowPrecThre;
  57         _QuaternionThresholdHighPrec= 1.0 - highPrecThre;
  58 }
  59
  60
  61 // ***************************************************************************
  62 void            CAnimationOptimizer::setVectorThreshold(double lowPrecThre, double highPrecThre)
  63 {
  64         nlassert(lowPrecThre>=0);
  65         nlassert(highPrecThre>=0);
  66         _VectorThresholdLowPrec= lowPrecThre;
  67         _VectorThresholdHighPrec= highPrecThre;
  68 }
  69
  70
  71 // ***************************************************************************
  72 void            CAnimationOptimizer::setSampleFrameRate(float frameRate)
  73 {
  74         nlassert(frameRate>0);
  75         _SampleFrameRate= frameRate;
  76 }
  77
  78
  79 // ***************************************************************************
  80 void            CAnimationOptimizer::optimize(const CAnimation &animIn, CAnimation &animOut)
  81 {
  82         // reset animOut
  83         contReset(animOut);
  84
  85         // Parse all tracks of the animation.
  86         set<string>             setString;
  87         animIn.getTrackNames (setString);
  88         set<string>::iterator   it;
  89
  90         for(it=setString.begin();it!=setString.end();it++)
  91         {
  92                 const string    &trackName= *it;
  93                 uint    trackId= animIn.getIdTrackByName(trackName);
  94                 nlassert(trackId!=CAnimation::NotFound);
  95                 const ITrack    *track= animIn.getTrack(trackId);
  96
  97                 // If the track is optimisable.
  98                 ITrack  *newTrack;
  99                 if(isTrackOptimisable(track))
 100                 {
 101                         // choose the threshold according to precision wanted
 102                         if( isLowPrecisionTrack(trackName) )
 103                         {
 104                                 _QuaternionThreshold= _QuaternionThresholdLowPrec;
 105                                 _VectorThreshold= _VectorThresholdLowPrec;
 106                         }
 107                         else
 108                         {
 109                                 _QuaternionThreshold= _QuaternionThresholdHighPrec;
 110                                 _VectorThreshold= _VectorThresholdHighPrec;
 111                         }
 112
 113                         // optimize it.
 114                         newTrack= optimizeTrack(track);
 115                 }
 116                 else
 117                 {
 118                         // just clone it.
 119                         newTrack= cloneTrack(track);
 120                 }
 121
 122                 // Add it to the animation
 123                 animOut.addTrack(trackName, newTrack);
 124         }
 125
 126         // Parse all SSS shapes of the animation (important for preload of those shapes)
 127         const vector<string>    &shapes= animIn.getSSSShapes();
 128         for(uint i=0;i<shapes.size();i++)
 129                 animOut.addSSSShape(shapes[i]);
 130
 131         // Set min animation length
 132         animOut.setMinEndTime (animIn.getEndTime ());
 133         nlassert (animOut.getEndTime() == animIn.getEndTime());
 134 }
 135
 136 // ***************************************************************************
 137 ITrack          *CAnimationOptimizer::cloneTrack(const ITrack   *trackIn)
 138 {
 139         CMemStream      memStream;
 140
 141         // write to the stream.
 142         ITrack  *trackInSerial= const_cast<ITrack*>(trackIn);
 143         memStream.serialPolyPtr(trackInSerial);
 144
 145         // read from the stream.
 146         memStream.invert();
 147         ITrack  *ret= NULL;
 148         memStream.serialPolyPtr(ret);
 149
 150         return ret;
 151 }
 152
 153
 154 // ***************************************************************************
 155 bool            CAnimationOptimizer::isTrackOptimisable(const ITrack    *trackIn)
 156 {
 157         nlassert(trackIn);
 158
 159         // If the track is a Linear, Bezier or a TCB track, suppose we can optimize it. Constant may not be interressant....
 160         if(     dynamic_cast<const CTrackKeyFramerTCBQuat*>(trackIn) ||
 161                 dynamic_cast<const CTrackKeyFramerBezierQuat*>(trackIn) ||
 162                 dynamic_cast<const CTrackKeyFramerLinearQuat*>(trackIn) )
 163                 return true;
 164
 165         // If the track is a Linear, Bezier or a TCB track, suppose we can optimize it. Constant may not be interressant....
 166         if(     dynamic_cast<const CTrackKeyFramerTCBVector*>(trackIn) ||
 167                 dynamic_cast<const CTrackKeyFramerBezierVector*>(trackIn) ||
 168                 dynamic_cast<const CTrackKeyFramerLinearVector*>(trackIn) )
 169                 return true;
 170
 171         return false;
 172 }
 173
 174
 175 // ***************************************************************************
 176 ITrack          *CAnimationOptimizer::optimizeTrack(const ITrack        *trackIn)
 177 {
 178         // Get track param.
 179         float beginTime= trackIn->getBeginTime();
 180         float endTime= trackIn->getEndTime();
 181         nlassert(endTime>=beginTime);
 182
 183         // Get num Sample
 184         uint    numSamples= (uint)ceil( (endTime-beginTime)*_SampleFrameRate);
 185         numSamples= max(1U, numSamples);
 186         nlassert(numSamples<65535);
 187
 188
 189         // Optimize Quaternion track??
 190         //================
 191         // eval the track only to get its value type!!
 192         CAnimatedValueBlock             avBlock;
 193         const IAnimatedValue    &valueType= ((ITrack*)trackIn)->eval(0, avBlock);
 194         if( dynamic_cast<const CAnimatedValueQuat *>(&valueType) )
 195         {
 196                 // sample the animation. Store result in _TimeList/_QuatKeyList
 197                 sampleQuatTrack(trackIn, beginTime, endTime, numSamples);
 198
 199                 // check if the sampled track can be reduced to a TrackDefaultQuat. Test _QuatKeyList.
 200                 if( testConstantQuatTrack() )
 201                 {
 202                         // create a default Track Quat.
 203                         CTrackDefaultQuat       *trackDefault= new CTrackDefaultQuat;
 204                         // setup the uniform value.
 205                         trackDefault->setDefaultValue(_QuatKeyList[0]);
 206
 207                         // return the result.
 208                         return trackDefault;
 209                 }
 210                 // else optimize the sampled animation, and build.
 211                 else
 212                 {
 213                         // optimize.
 214                         optimizeQuatTrack();
 215
 216                         // Create a sampled quaternion track
 217                         CTrackSampledQuat       *trackSQ= new CTrackSampledQuat;
 218
 219                         // Copy loop from track.
 220                         trackSQ->setLoopMode(trackIn->getLoopMode());
 221
 222                         // Build it.
 223                         trackSQ->build(_TimeList, _QuatKeyList, beginTime, endTime);
 224
 225                         // return result.
 226                         return trackSQ;
 227                 }
 228         }
 229         // Optimize Position track??
 230         //================
 231         else if( dynamic_cast<const CAnimatedValueVector *>(&valueType) )
 232         {
 233                 // sample the animation. Store result in _TimeList/_VectorKeyList
 234                 sampleVectorTrack(trackIn, beginTime, endTime, numSamples);
 235
 236                 // check if the sampled track can be reduced to a TrackDefaultVector. Test _VectorKeyList.
 237                 if( testConstantVectorTrack() )
 238                 {
 239                         // create a default Track Vector.
 240                         CTrackDefaultVector     *trackDefault= new CTrackDefaultVector;
 241                         // setup the uniform value.
 242                         trackDefault->setDefaultValue(_VectorKeyList[0]);
 243
 244                         // return the result.
 245                         return trackDefault;
 246                 }
 247                 // else optimize the sampled animation, and build.
 248                 else
 249                 {
 250                         // optimize.
 251                         optimizeVectorTrack();
 252
 253                         // Create a sampled Vector track
 254                         CTrackSampledVector     *trackSV= new CTrackSampledVector;
 255
 256                         // Copy loop from track.
 257                         trackSV->setLoopMode(trackIn->getLoopMode());
 258
 259                         // Build it.
 260                         trackSV->build(_TimeList, _VectorKeyList, beginTime, endTime);
 261
 262                         // return result.
 263                         return trackSV;
 264                 }
 265         }
 266         else
 267         {
 268                 // Must be a quaternion track or vector track for now.
 269                 nlstop;
 270                 // Avoid warning.
 271                 return cloneTrack(trackIn);
 272         }
 273 }
 274
 275
 276 // ***************************************************************************
 277 // ***************************************************************************
 278 // Quaternion optimisation
 279 // ***************************************************************************
 280 // ***************************************************************************
 281
 282
 283 // ***************************************************************************
 284 void            CAnimationOptimizer::sampleQuatTrack(const ITrack *trackIn, float beginTime, float endTime, uint numSamples)
 285 {
 286         // resize tmp samples
 287         _TimeList.resize(numSamples);
 288         _QuatKeyList.resize(numSamples);
 289
 290         // Sample the animation.
 291         float   t= beginTime;
 292         float   dt= 0;
 293         if(numSamples>1)
 294                 dt= (endTime-beginTime)/(numSamples-1);
 295         for(uint i=0;i<numSamples; i++, t+=dt)
 296         {
 297                 CQuat   quat;
 298
 299                 // make exact endTime match (avoid precision problem)
 300                 if(i==numSamples-1)
 301                         t= endTime;
 302
 303                 // evaluate the track
 304                 const_cast<ITrack*>(trackIn)->interpolate(t, quat);
 305
 306                 // normalize this quaternion
 307                 quat.normalize();
 308
 309                 // force on same hemisphere according to precedent frame.
 310                 if(i>0)
 311                 {
 312                         quat.makeClosest(_QuatKeyList[i-1]);
 313                 }
 314
 315                 // store time and key.
 316                 _TimeList[i]= i;
 317                 _QuatKeyList[i]= quat;
 318         }
 319
 320 }
 321
 322 // ***************************************************************************
 323 bool            CAnimationOptimizer::testConstantQuatTrack()
 324 {
 325         uint    numSamples= (uint)_QuatKeyList.size();
 326         nlassert(numSamples>0);
 327
 328         // Get the first sample as the reference quaternion, and test others from this one.
 329         CQuat   quatRef= _QuatKeyList[0];
 330         for(uint i=0;i<numSamples;i++)
 331         {
 332                 // All values must be nearly equal to the reference quaternion.
 333                 if(!nearlySameQuaternion(quatRef, _QuatKeyList[i]))
 334                         return false;
 335         }
 336
 337         // ok.
 338         return true;
 339 }
 340
 341
 342 // ***************************************************************************
 343 void            CAnimationOptimizer::optimizeQuatTrack()
 344 {
 345         uint    numSamples= (uint)_QuatKeyList.size();
 346         nlassert(numSamples>0);
 347
 348         // <=2 key? => no opt possible..
 349         if(numSamples<=2)
 350                 return;
 351
 352         // prepare dest opt
 353         std::vector<uint16>             optTimeList;
 354         std::vector<CQuat>              optKeyList;
 355         optTimeList.reserve(numSamples);
 356         optKeyList.reserve(numSamples);
 357
 358         // Add the first key.
 359         optTimeList.push_back(_TimeList[0]);
 360         optKeyList.push_back(_QuatKeyList[0]);
 361         double  timeRef= _TimeList[0];
 362         CQuatD  quatRef= _QuatKeyList[0];
 363
 364         // For all keys, but the first and the last, test if can remove them.
 365         for(uint i=1; i<numSamples-1; i++)
 366         {
 367                 CQuatD  quatCur= _QuatKeyList[i];
 368                 CQuatD  quatNext= _QuatKeyList[i+1];
 369                 double  timeCur= _TimeList[i];
 370                 double  timeNext= _TimeList[i+1];
 371
 372                 // must add the key?
 373                 bool    mustAdd= false;
 374
 375                 // If the Delta time are too big, abort (CTrackSampledQuat limitation)
 376                 if(timeNext-timeRef>255)
 377                 {
 378                         mustAdd= true;
 379                 }
 380                 // If the next quaternion or the current quaternion are not on same hemisphere than ref, abort.
 381                 else if( CQuatD::dotProduct(quatCur, quatRef)<0 || CQuatD::dotProduct(quatNext, quatRef)<0 )
 382                 {
 383                         mustAdd= true;
 384                 }
 385                 // else, test interpolation
 386                 else
 387                 {
 388                         // If the 3 quats are nearly equals, it is ok (avoid interpolation)
 389                         if( nearlySameQuaternion(quatRef, quatCur) && nearlySameQuaternion(quatRef, quatNext) )
 390                                 mustAdd= false;
 391                         else
 392                         {
 393                                 // interpolate.
 394                                 CQuatD  quatInterpolated;
 395                                 double  t= (timeCur-timeRef)/(timeNext/timeRef);
 396                                 quatInterpolated= CQuatD::slerp(quatRef, quatNext, (float)t);
 397
 398                                 // test if cur and interpolate are equal.
 399                                 if( !nearlySameQuaternion(quatCur, quatInterpolated) )
 400                                         mustAdd= true;
 401                         }
 402                 }
 403
 404                 // If must add the key to the optimized track.
 405                 if(mustAdd)
 406                 {
 407                         optTimeList.push_back(_TimeList[i]);
 408                         optKeyList.push_back(_QuatKeyList[i]);
 409                         timeRef= _TimeList[i];
 410                         quatRef= _QuatKeyList[i];
 411                 }
 412         }
 413
 414         // Add the last key.
 415         optTimeList.push_back(_TimeList[numSamples-1]);
 416         optKeyList.push_back(_QuatKeyList[numSamples-1]);
 417
 418         // copy the optimized track to the main one.
 419         _TimeList= optTimeList;
 420         _QuatKeyList= optKeyList;
 421 }
 422
 423
 424 // ***************************************************************************
 425 bool            CAnimationOptimizer::nearlySameQuaternion(const CQuatD &quat0, const CQuatD &quat1)
 426 {
 427         // true if exactly same, or exactly inverse
 428         if(quat0==quat1 || quat0==-quat1)
 429                 return true;
 430
 431         // Else compute the rotation to go from qRef to q. Use double for better presion.
 432         CQuatD  quatDif;
 433         quatDif= quat1 * quat0.conjugate();
 434         // inverse the quaternion if necessary. ie make closest to the identity quaternion.
 435         if(quatDif.w<0)
 436                 quatDif= -quatDif;
 437
 438         // compare "angle threshold"
 439         return (quatDif.w >= _QuaternionThreshold);
 440 }
 441
 442
 443 // ***************************************************************************
 444 // ***************************************************************************
 445 // Vector optimisation
 446 // ***************************************************************************
 447 // ***************************************************************************
 448
 449
 450 // ***************************************************************************
 451 void            CAnimationOptimizer::sampleVectorTrack(const ITrack *trackIn, float beginTime, float endTime, uint numSamples)
 452 {
 453         // resize tmp samples
 454         _TimeList.resize(numSamples);
 455         _VectorKeyList.resize(numSamples);
 456
 457         // Sample the animation.
 458         float   t= beginTime;
 459         float   dt= 0;
 460         if(numSamples>1)
 461                 dt= (endTime-beginTime)/(numSamples-1);
 462         for(uint i=0;i<numSamples; i++, t+=dt)
 463         {
 464                 CVector vector;
 465
 466                 // make exact endTime match (avoid precision problem)
 467                 if(i==numSamples-1)
 468                         t= endTime;
 469
 470                 // evaluate the track
 471                 const_cast<ITrack*>(trackIn)->interpolate(t, vector);
 472
 473                 // store time and key.
 474                 _TimeList[i]= i;
 475                 _VectorKeyList[i]= vector;
 476         }
 477
 478 }
 479
 480 // ***************************************************************************
 481 bool            CAnimationOptimizer::testConstantVectorTrack()
 482 {
 483         uint    numSamples= (uint)_VectorKeyList.size();
 484         nlassert(numSamples>0);
 485
 486         // Get the first sample as the reference Vectorer, and test others from this one.
 487         CVector vectorRef= _VectorKeyList[0];
 488         for(uint i=0;i<numSamples;i++)
 489         {
 490                 // All values must be nearly equal to the reference vector.
 491                 if(!nearlySameVector(vectorRef, _VectorKeyList[i]))
 492                         return false;
 493         }
 494
 495         // ok.
 496         return true;
 497 }
 498
 499
 500 // ***************************************************************************
 501 void            CAnimationOptimizer::optimizeVectorTrack()
 502 {
 503         uint    numSamples= (uint)_VectorKeyList.size();
 504         nlassert(numSamples>0);
 505
 506         // <=2 key? => no opt possible..
 507         if(numSamples<=2)
 508                 return;
 509
 510         // prepare dest opt
 511         std::vector<uint16>             optTimeList;
 512         std::vector<CVector>    optKeyList;
 513         optTimeList.reserve(numSamples);
 514         optKeyList.reserve(numSamples);
 515
 516         // Add the first key.
 517         optTimeList.push_back(_TimeList[0]);
 518         optKeyList.push_back(_VectorKeyList[0]);
 519         double          timeRef= _TimeList[0];
 520         CVectorD        vectorRef= _VectorKeyList[0];
 521
 522         // For all keys, but the first and the last, test if can remove them.
 523         for(uint i=1; i<numSamples-1; i++)
 524         {
 525                 CVectorD        vectorCur= _VectorKeyList[i];
 526                 CVectorD        vectorNext= _VectorKeyList[i+1];
 527                 double  timeCur= _TimeList[i];
 528                 double  timeNext= _TimeList[i+1];
 529
 530                 // must add the key?
 531                 bool    mustAdd= false;
 532
 533                 // If the Delta time are too big, abort (CTrackSampledVector limitation)
 534                 if(timeNext-timeRef>255)
 535                 {
 536                         mustAdd= true;
 537                 }
 538                 // else, test interpolation
 539                 else
 540                 {
 541                         // If the 3 Vectors are nearly equals, it is ok (avoid interpolation)
 542                         if( nearlySameVector(vectorRef, vectorCur) && nearlySameVector(vectorRef, vectorNext) )
 543                                 mustAdd= false;
 544                         else
 545                         {
 546                                 // interpolate.
 547                                 CVectorD        vectorInterpolated;
 548                                 double  t= (timeCur-timeRef)/(timeNext/timeRef);
 549                                 vectorInterpolated= vectorRef*(1-t) + vectorNext*t;
 550
 551                                 // test if cur and interpolate are equal.
 552                                 if( !nearlySameVector(vectorCur, vectorInterpolated) )
 553                                         mustAdd= true;
 554                         }
 555                 }
 556
 557                 // If must add the key to the optimized track.
 558                 if(mustAdd)
 559                 {
 560                         optTimeList.push_back(_TimeList[i]);
 561                         optKeyList.push_back(_VectorKeyList[i]);
 562                         timeRef= _TimeList[i];
 563                         vectorRef= _VectorKeyList[i];
 564                 }
 565         }
 566
 567         // Add the last key.
 568         optTimeList.push_back(_TimeList[numSamples-1]);
 569         optKeyList.push_back(_VectorKeyList[numSamples-1]);
 570
 571         // copy the optimized track to the main one.
 572         _TimeList= optTimeList;
 573         _VectorKeyList= optKeyList;
 574 }
 575
 576
 577 // ***************************************************************************
 578 bool            CAnimationOptimizer::nearlySameVector(const CVectorD &v0, const CVectorD &v1)
 579 {
 580         // true if exactly same
 581         if(v0==v1)
 582                 return true;
 583
 584         // Else compute the dif, use double for better precision
 585         CVectorD        vDif;
 586         vDif= v1-v0;
 587
 588         // compare norm
 589         return (vDif.norm() <= _VectorThreshold);
 590 }
 591
 592
 593 // ***************************************************************************
 594 // ***************************************************************************
 595 // LowPrecisionTrack
 596 // ***************************************************************************
 597 // ***************************************************************************
 598
 599
 600 // ***************************************************************************
 601 void            CAnimationOptimizer::addLowPrecisionTrack(const std::string &name)
 602 {
 603         _LowPrecTrackKeyName.push_back(name);
 604 }
 605
 606 // ***************************************************************************
 607 void            CAnimationOptimizer::clearLowPrecisionTracks()
 608 {
 609         _LowPrecTrackKeyName.clear();
 610 }
 611
 612 // ***************************************************************************
 613 bool            CAnimationOptimizer::isLowPrecisionTrack(const std::string &trackName)
 614 {
 615         for(uint i=0; i<_LowPrecTrackKeyName.size(); i++)
 616         {
 617                 // if find a substr of the key, it is a low prec track
 618                 if( trackName.find(_LowPrecTrackKeyName[i]) != string::npos )
 619                         return true;
 620         }
 621
 622         // no key found
 623         return false;
 624 }
 625
 626
 627 } // NL3D