nel/src/3d/track_sampled_common.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/misc/quat.h"
  20 #include "nel/misc/common.h"
  21 #include "nel/misc/algo.h"
  22 #include "nel/3d/track_sampled_common.h"
  23 #include "nel/misc/vectord.h"
  24
  25 using namespace NLMISC;
  26 using namespace std;
  27
  28 #ifdef DEBUG_NEW
  29 #define new DEBUG_NEW
  30 #endif
  31
  32 namespace NL3D
  33 {
  34
  35
  36 // ***************************************************************************
  37 // ***************************************************************************
  38 // CTrackSampledCommon
  39 // ***************************************************************************
  40 // ***************************************************************************
  41
  42
  43 // ***************************************************************************
  44 CTrackSampledCommon::CTrackSampledCommon()
  45 {
  46         _LoopMode= true;
  47 }
  48
  49 // ***************************************************************************
  50 CTrackSampledCommon::~CTrackSampledCommon()
  51 {
  52 }
  53
  54 // ***************************************************************************
  55 bool                                    CTrackSampledCommon::getLoopMode() const
  56 {
  57         return _LoopMode;
  58 }
  59
  60 // ***************************************************************************
  61 TAnimationTime                  CTrackSampledCommon::getBeginTime () const
  62 {
  63         return _BeginTime;
  64 }
  65
  66 // ***************************************************************************
  67 TAnimationTime                  CTrackSampledCommon::getEndTime () const
  68 {
  69         return _EndTime;
  70 }
  71
  72
  73 // ***************************************************************************
  74 void                                    CTrackSampledCommon::CTimeBlock::serial(NLMISC::IStream &f)
  75 {
  76         (void)f.serialVersion(0);
  77
  78         f.serial(TimeOffset);
  79         f.serial(KeyOffset);
  80         f.serial(Times);
  81 }
  82
  83 // ***************************************************************************
  84 void                                    CTrackSampledCommon::serialCommon(NLMISC::IStream &f)
  85 {
  86         (void)f.serialVersion(0);
  87
  88         f.serial(_LoopMode);
  89         f.serial(_BeginTime);
  90         f.serial(_EndTime) ;
  91         f.serial(_TotalRange);
  92         f.serial(_OOTotalRange);
  93         f.serial(_DeltaTime);
  94         f.serial(_OODeltaTime);
  95         f.serial(_TimeBlocks);
  96
  97 }
  98
  99 // ***************************************************************************
 100 void    CTrackSampledCommon::buildCommon(const std::vector<uint16> &timeList, float beginTime, float endTime)
 101 {
 102         nlassert( endTime>beginTime || (beginTime==endTime && timeList.size()<=1) );
 103         uint i;
 104
 105         // reset.
 106         uint    numKeys= (uint)timeList.size();
 107         _TimeBlocks.clear();
 108
 109         // Special case of 0 or 1 key.
 110         //===================
 111         if(numKeys<=1)
 112         {
 113                 _BeginTime= beginTime;
 114                 _EndTime= endTime;
 115                 _TotalRange= 0;
 116                 _OOTotalRange= 0;
 117                 _DeltaTime= 0;
 118                 _OODeltaTime= 0;
 119                 if(numKeys==1)
 120                 {
 121                         _TimeBlocks.resize(1);
 122                         _TimeBlocks[0].TimeOffset= 0;
 123                         _TimeBlocks[0].Times.resize(1);
 124                         _TimeBlocks[0].Times[0]= 0;
 125                 }
 126
 127                 return;
 128         }
 129
 130         // Compute All Time blocks.
 131         //===================
 132         sint32          lastBlockFrame= -1000000;
 133         nlassert(timeList[0] == 0);
 134         // Header info for creating timeBlocks
 135         vector<uint>    timeBlockKeyId;
 136         vector<uint>    timeBlockNumKeys;
 137
 138         // compute how many time block we need.
 139         for(i=0; i<numKeys; i++)
 140         {
 141                 // verify growing order, and time difference.
 142                 if(i>0)
 143                 {
 144                         nlassert(timeList[i]>timeList[i-1]);
 145                         nlassert(timeList[i]-timeList[i-1] <= 255 );
 146                 }
 147                 // If the current frame is to far from the last TimeBlock frame (or if 1st timeBlock), must create a new timeBlock
 148                 if(timeList[i]-lastBlockFrame>255)
 149                 {
 150                         // create a new timeblock
 151                         timeBlockKeyId.push_back(i);
 152                         // Add this key to this new time Block (numKey == 1).
 153                         timeBlockNumKeys.push_back(1);
 154                         lastBlockFrame= timeList[i];
 155                 }
 156                 else
 157                 {
 158                         // Add this key to the timeBlock.
 159                         timeBlockNumKeys[timeBlockNumKeys.size()-1]++;
 160                 }
 161         }
 162
 163         // Build the timeBlocks.
 164         _TimeBlocks.resize((uint32)timeBlockKeyId.size());
 165         for(i=0; i<timeBlockKeyId.size(); i++)
 166         {
 167                 CTimeBlock      &timeBlock= _TimeBlocks[i];
 168                 uint            firstKeyId= timeBlockKeyId[i];
 169                 uint            numKeys= timeBlockNumKeys[i];
 170                 // compute the offset time and key
 171                 timeBlock.KeyOffset= firstKeyId;
 172                 timeBlock.TimeOffset= timeList[firstKeyId];
 173                 // create array of key
 174                 timeBlock.Times.resize(numKeys);
 175                 for(uint j=0;j<timeBlock.Times.size(); j++)
 176                 {
 177                         // get the key time and make it local to the timeBlock.
 178                         timeBlock.Times[j]= timeList[firstKeyId+j] - timeBlock.TimeOffset;
 179                 }
 180         }
 181
 182         // Compute other params
 183         //===================
 184         _BeginTime= beginTime;
 185         _EndTime= endTime;
 186         // compute deltatime for a frame to another
 187         uint    totalFrameCount= timeList[numKeys-1] - timeList[0];
 188         nlassert(totalFrameCount>0);
 189         _DeltaTime= (_EndTime-_BeginTime) / totalFrameCount;
 190         _OODeltaTime= (float)(1.0 / _DeltaTime);
 191         // Compute range of anim
 192         _TotalRange= _EndTime-_BeginTime;
 193         _OOTotalRange= float(1.0/_TotalRange);
 194
 195 }
 196
 197 // ***************************************************************************
 198 void    CTrackSampledCommon::setLoopMode(bool mode)
 199 {
 200         _LoopMode= mode;
 201 }
 202
 203
 204 // ***************************************************************************
 205 CTrackSampledCommon::TEvalType  CTrackSampledCommon::evalTime (const TAnimationTime& date, uint numKeys, uint &keyId0, uint &keyId1, float &interpValue)
 206 {
 207         /* IF YOU CHANGE THIS CODE, CHANGE too CTrackSampledQuatSmallHeader
 208          */
 209
 210         // Empty? quit
 211         if(numKeys==0)
 212                 return EvalDiscard;
 213
 214         // One Key? easy, and quit.
 215         if(numKeys==1)
 216         {
 217                 keyId0= 0;
 218                 return EvalKey0;
 219         }
 220
 221         // manage Loop
 222         //=====================
 223         float   localTime;
 224         if(_LoopMode)
 225         {
 226                 nlassert(_TotalRange>0);
 227                 // get relative to BeginTime.
 228                 localTime= date-_BeginTime;
 229
 230                 // force us to be in interval [0, _TotalRange[.
 231                 if( localTime<0 || localTime>=_TotalRange )
 232                 {
 233                         double  d= localTime*_OOTotalRange;
 234
 235                         // floor(d) is the truncated number of loops.
 236                         d= localTime- floor(d)*_TotalRange;
 237                         localTime= (float)d;
 238
 239                         // For precision problems, ensure correct range.
 240                         if(localTime<0 || localTime >= _TotalRange)
 241                                 localTime= 0;
 242                 }
 243
 244         }
 245         else
 246         {
 247                 // get relative to BeginTime.
 248                 localTime= date-_BeginTime;
 249         }
 250
 251
 252         // Find the first key before localTime
 253         //=====================
 254         // get the frame in the track.
 255         sint    frame= (sint)floor(localTime*_OODeltaTime);
 256         // clamp to uint16
 257         clamp(frame, 0, 65535);
 258
 259         // Search the TimeBlock.
 260         CTimeBlock      keyTB;
 261         keyTB.TimeOffset= frame;
 262         uint            tbId;
 263         tbId= searchLowerBound(_TimeBlocks.getPtr(), _TimeBlocks.size(), keyTB);
 264
 265         // get this timeBlock.
 266         CTimeBlock      &timeBlock= _TimeBlocks[tbId];
 267         // get frame relative to this timeBlock.
 268         sint    frameRel= frame-timeBlock.TimeOffset;
 269         // clamp to uint8
 270         clamp(frameRel, 0, 255);
 271         // get the key in this timeBlock.
 272         uint    keyIdRel;
 273         keyIdRel= searchLowerBound(timeBlock.Times.getPtr(), timeBlock.Times.size(), (uint8)frameRel);
 274
 275         // Get the Frame and Value of Key0.
 276         uint            frameKey0= timeBlock.TimeOffset + timeBlock.Times[keyIdRel];
 277         // this is the key to evaluate
 278         keyId0= timeBlock.KeyOffset + keyIdRel;
 279
 280
 281         // Interpolate with next key
 282         //=====================
 283
 284         // If not the last Key
 285         if(keyId0<numKeys-1)
 286         {
 287                 // Get the next key.
 288                 keyId1= keyId0+1;
 289                 uint            frameKey1;
 290                 // If last key of the timeBlock, get the first time of the next timeBlock.
 291                 if( keyIdRel+1 >= timeBlock.Times.size() )
 292                 {
 293                         nlassert(tbId+1<_TimeBlocks.size());
 294                         frameKey1= _TimeBlocks[tbId+1].TimeOffset;
 295                 }
 296                 else
 297                 {
 298                         frameKey1= timeBlock.TimeOffset + timeBlock.Times[keyIdRel+1];
 299                 }
 300
 301                 // unpack time.
 302                 float   time0= frameKey0*_DeltaTime;
 303                 float   time1= frameKey1*_DeltaTime;
 304
 305                 // interpolate.
 306                 float   t= (localTime-time0);
 307                 // If difference is one frame, optimize.
 308                 if(frameKey1-frameKey0==1)
 309                         t*= _OODeltaTime;
 310                 else
 311                         t/= (time1-time0);
 312                 clamp(t, 0.f, 1.f);
 313
 314                 // store this interp value.
 315                 interpValue= t;
 316
 317                 return EvalInterpolate;
 318         }
 319         // else (last key of anim), just eval this key.
 320         return EvalKey0;
 321 }
 322
 323
 324 // ***************************************************************************
 325 void    CTrackSampledCommon::applySampleDivisorCommon(uint sampleDivisor, std::vector<uint32> &keepKeys)
 326 {
 327         nlassert(sampleDivisor>=2);
 328         uint    i,j;
 329
 330         /*
 331                 NB: to be faster, if we have multiple timeblock (rare, cause implies the anim>8.5 sec), the
 332                 number of time block is kept after this process, either if it could be lowered.
 333                 NB: for same reason, the first and last key of each timeBlock is kept to be simpler, and to avoid bug
 334                 in searchLowerBound() (we must keep first key of each timeBlock)
 335         */
 336
 337         // clear
 338         keepKeys.clear();
 339
 340         // **** build the key indices to keep
 341         static std::vector<uint32>              blockKeepStart;
 342         static std::vector<uint32>              blockKeepEnd;
 343         blockKeepStart.resize(_TimeBlocks.size());
 344         blockKeepEnd.resize(_TimeBlocks.size());
 345         // must Keep the first and last key.
 346         uint    lastKeyTime= 0;
 347         for(i=0;i<_TimeBlocks.size();i++)
 348         {
 349                 CTimeBlock      &timeBlock= _TimeBlocks[i];
 350
 351                 // keep track of the start new key for this block
 352                 blockKeepStart[i]= (uint32)keepKeys.size();
 353
 354                 for(j=0;j<timeBlock.Times.size();j++)
 355                 {
 356                         // get the time of this key
 357                         uint    keyTime= timeBlock.Times[j] + timeBlock.TimeOffset;
 358                         // if the diff time with last inserted key is >= than the sampleDivisor, add it!
 359                         if( (keyTime - lastKeyTime >= sampleDivisor) ||
 360                                 // add it also if it is the first or last key of the block
 361                                 (j==0 || j==timeBlock.Times.size()-1) )
 362                         {
 363                                 lastKeyTime= keyTime;
 364                                 keepKeys.push_back(j+timeBlock.KeyOffset);
 365                         }
 366                 }
 367
 368                 // keep track of the end (not included) new key for this block
 369                 blockKeepEnd[i]= (uint32)keepKeys.size();
 370         }
 371
 372         // **** rebuild the TimeBlocks
 373         for(i=0;i<_TimeBlocks.size();i++)
 374         {
 375                 CTimeBlock      &timeBlock= _TimeBlocks[i];
 376                 uint    keepStart= blockKeepStart[i];
 377                 uint    keepEnd= blockKeepEnd[i];
 378
 379                 NLMISC::CObjectVector<uint8, false>             newKeys;
 380                 newKeys.resize(keepEnd-keepStart);
 381                 for(uint j=0;j<newKeys.size();j++)
 382                 {
 383                         newKeys[j]= timeBlock.Times[keepKeys[keepStart+j]-timeBlock.KeyOffset];
 384                 }
 385                 // copy
 386                 timeBlock.Times= newKeys;
 387                 // change the key offset!
 388                 timeBlock.KeyOffset= keepStart;
 389         }
 390
 391 }
 392
 393
 394 } // NL3D