src/third_party/WebKit/Source/core/animation/KeyframeEffectModel.cpp

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "config.h"
  32 #include "core/animation/KeyframeEffectModel.h"
  33
  34 #include "core/animation/TimedItem.h"
  35 #include "wtf/text/StringHash.h"
  36
  37 namespace {
  38
  39 using namespace WebCore;
  40
  41 class AddCompositableValue FINAL : public AnimationEffect::CompositableValue {
  42 public:
  43     static PassRefPtr<AddCompositableValue> create(const AnimatableValue* value)
  44     {
  45         return adoptRef(new AddCompositableValue(value));
  46     }
  47     virtual bool dependsOnUnderlyingValue() const OVERRIDE
  48     {
  49         return true;
  50     }
  51     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const OVERRIDE
  52     {
  53         return AnimatableValue::add(underlyingValue, m_value.get());
  54     }
  55 private:
  56     AddCompositableValue(const AnimatableValue* value)
  57         : m_value(const_cast<AnimatableValue*>(value))
  58     {
  59     }
  60     RefPtr<AnimatableValue> m_value;
  61 };
  62
  63 class BlendedCompositableValue FINAL : public AnimationEffect::CompositableValue {
  64 public:
  65     static PassRefPtr<BlendedCompositableValue> create(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
  66     {
  67         return adoptRef(new BlendedCompositableValue(before, after, fraction));
  68     }
  69     virtual bool dependsOnUnderlyingValue() const OVERRIDE
  70     {
  71         return m_dependsOnUnderlyingValue;
  72     }
  73     virtual PassRefPtr<AnimatableValue> compositeOnto(const AnimatableValue* underlyingValue) const OVERRIDE
  74     {
  75         return AnimatableValue::interpolate(m_before->compositeOnto(underlyingValue).get(), m_after->compositeOnto(underlyingValue).get(), m_fraction);
  76     }
  77 private:
  78     BlendedCompositableValue(const AnimationEffect::CompositableValue* before, const AnimationEffect::CompositableValue* after, double fraction)
  79         : m_before(const_cast<AnimationEffect::CompositableValue*>(before))
  80         , m_after(const_cast<AnimationEffect::CompositableValue*>(after))
  81         , m_fraction(fraction)
  82         , m_dependsOnUnderlyingValue(before->dependsOnUnderlyingValue() || after->dependsOnUnderlyingValue())
  83     { }
  84     RefPtr<AnimationEffect::CompositableValue> m_before;
  85     RefPtr<AnimationEffect::CompositableValue> m_after;
  86     double m_fraction;
  87     bool m_dependsOnUnderlyingValue;
  88 };
  89
  90 const double accuracyForKeyframeEasing = 0.0000001;
  91
  92 } // namespace
  93
  94
  95 namespace WebCore {
  96
  97 Keyframe::Keyframe()
  98     : m_offset(nullValue())
  99     , m_composite(AnimationEffect::CompositeReplace)
 100 { }
 101
 102 Keyframe::Keyframe(const Keyframe& copyFrom)
 103     : m_offset(copyFrom.m_offset)
 104     , m_composite(copyFrom.m_composite)
 105     , m_easing(copyFrom.m_easing)
 106 {
 107     for (PropertyValueMap::const_iterator iter = copyFrom.m_propertyValues.begin(); iter != copyFrom.m_propertyValues.end(); ++iter)
 108         setPropertyValue(iter->key, iter->value.get());
 109 }
 110
 111 void Keyframe::setPropertyValue(CSSPropertyID property, const AnimatableValue* value)
 112 {
 113     m_propertyValues.add(property, const_cast<AnimatableValue*>(value));
 114 }
 115
 116 void Keyframe::clearPropertyValue(CSSPropertyID property)
 117 {
 118     m_propertyValues.remove(property);
 119 }
 120
 121 const AnimatableValue* Keyframe::propertyValue(CSSPropertyID property) const
 122 {
 123     ASSERT(m_propertyValues.contains(property));
 124     return m_propertyValues.get(property);
 125 }
 126
 127 PropertySet Keyframe::properties() const
 128 {
 129     // This is not used in time-critical code, so we probably don't need to
 130     // worry about caching this result.
 131     PropertySet properties;
 132     for (PropertyValueMap::const_iterator iter = m_propertyValues.begin(); iter != m_propertyValues.end(); ++iter)
 133         properties.add(*iter.keys());
 134     return properties;
 135 }
 136
 137 PassRefPtr<Keyframe> Keyframe::cloneWithOffset(double offset) const
 138 {
 139     RefPtr<Keyframe> theClone = clone();
 140     theClone->setOffset(offset);
 141     return theClone.release();
 142 }
 143
 144 KeyframeEffectModel::KeyframeEffectModel(const KeyframeVector& keyframes)
 145     : m_keyframes(keyframes)
 146 {
 147 }
 148
 149 PropertySet KeyframeEffectModel::properties() const
 150 {
 151     PropertySet result;
 152     if (!m_keyframes.size()) {
 153         return result;
 154     }
 155     result = m_keyframes[0]->properties();
 156     for (size_t i = 1; i < m_keyframes.size(); i++) {
 157         PropertySet extras = m_keyframes[i]->properties();
 158         for (PropertySet::const_iterator it = extras.begin(); it != extras.end(); ++it) {
 159             result.add(*it);
 160         }
 161     }
 162     return result;
 163 }
 164
 165 PassOwnPtr<AnimationEffect::CompositableValueList> KeyframeEffectModel::sample(int iteration, double fraction) const
 166 {
 167     ASSERT(iteration >= 0);
 168     ASSERT(!isNull(fraction));
 169     const_cast<KeyframeEffectModel*>(this)->ensureKeyframeGroups();
 170     OwnPtr<CompositableValueList> map = adoptPtr(new CompositableValueList());
 171     for (KeyframeGroupMap::const_iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter)
 172         map->append(std::make_pair(iter->key, iter->value->sample(iteration, fraction)));
 173     return map.release();
 174 }
 175
 176 KeyframeEffectModel::KeyframeVector KeyframeEffectModel::normalizedKeyframes(const KeyframeVector& keyframes)
 177 {
 178     // keyframes [beginIndex, endIndex) will remain after removing all keyframes if they are not
 179     // loosely sorted by offset, and after removing keyframes with positional offset outide [0, 1].
 180     size_t beginIndex = 0;
 181     size_t endIndex = keyframes.size();
 182
 183     // Becomes the most recent keyframe with an explicit offset.
 184     size_t lastIndex = endIndex;
 185     double lastOffset = std::numeric_limits<double>::quiet_NaN();
 186
 187     for (size_t i = 0; i < keyframes.size(); ++i) {
 188         double offset = keyframes[i]->offset();
 189         if (!isNull(offset)) {
 190             if (lastIndex < i && offset < lastOffset) {
 191                 // The keyframes are not loosely sorted by offset. Exclude all.
 192                 endIndex = beginIndex;
 193                 break;
 194             }
 195
 196             if (offset < 0) {
 197                 // Remove all keyframes up to and including this keyframe.
 198                 beginIndex = i + 1;
 199             } else if (offset > 1) {
 200                 // Remove all keyframes from this keyframe onwards. Note we must complete our checking
 201                 // that the keyframes are loosely sorted by offset, so we can't exit the loop early.
 202                 endIndex = std::min(i, endIndex);
 203             }
 204
 205             lastIndex = i;
 206             lastOffset = offset;
 207         }
 208     }
 209
 210     KeyframeVector result;
 211     if (beginIndex != endIndex) {
 212         result.reserveCapacity(endIndex - beginIndex);
 213         for (size_t i = beginIndex; i < endIndex; ++i) {
 214             result.append(keyframes[i]->clone());
 215         }
 216
 217         if (isNull(result[result.size() - 1]->offset()))
 218             result[result.size() - 1]->setOffset(1);
 219
 220         if (result.size() > 1 && isNull(result[0]->offset()))
 221             result[0]->setOffset(0);
 222
 223         lastIndex = 0;
 224         lastOffset = result[0]->offset();
 225         for (size_t i = 1; i < result.size(); ++i) {
 226             double offset = result[i]->offset();
 227             if (!isNull(offset)) {
 228                 if (lastIndex + 1 < i) {
 229                     for (size_t j = 1; j < i - lastIndex; ++j)
 230                         result[lastIndex + j]->setOffset(lastOffset + (offset - lastOffset) * j / (i - lastIndex));
 231                 }
 232                 lastIndex = i;
 233                 lastOffset = offset;
 234             }
 235         }
 236     }
 237     return result;
 238 }
 239
 240 void KeyframeEffectModel::ensureKeyframeGroups() const
 241 {
 242     if (m_keyframeGroups)
 243         return;
 244
 245     m_keyframeGroups = adoptPtr(new KeyframeGroupMap);
 246     const KeyframeVector keyframes = normalizedKeyframes(getFrames());
 247     for (KeyframeVector::const_iterator keyframeIter = keyframes.begin(); keyframeIter != keyframes.end(); ++keyframeIter) {
 248         const Keyframe* keyframe = keyframeIter->get();
 249         PropertySet keyframeProperties = keyframe->properties();
 250         for (PropertySet::const_iterator propertyIter = keyframeProperties.begin(); propertyIter != keyframeProperties.end(); ++propertyIter) {
 251             CSSPropertyID property = *propertyIter;
 252             KeyframeGroupMap::iterator groupIter = m_keyframeGroups->find(property);
 253             PropertySpecificKeyframeGroup* group;
 254             if (groupIter == m_keyframeGroups->end())
 255                 group = m_keyframeGroups->add(property, adoptPtr(new PropertySpecificKeyframeGroup)).storedValue->value.get();
 256             else
 257                 group = groupIter->value.get();
 258
 259             group->appendKeyframe(adoptPtr(
 260                 new PropertySpecificKeyframe(keyframe->offset(), keyframe->easing(), keyframe->propertyValue(property), keyframe->composite())));
 261         }
 262     }
 263
 264     // Add synthetic keyframes.
 265     for (KeyframeGroupMap::iterator iter = m_keyframeGroups->begin(); iter != m_keyframeGroups->end(); ++iter) {
 266         iter->value->addSyntheticKeyframeIfRequired();
 267         iter->value->removeRedundantKeyframes();
 268     }
 269 }
 270
 271
 272 KeyframeEffectModel::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, PassRefPtr<TimingFunction> easing, const AnimatableValue* value, CompositeOperation composite)
 273     : m_offset(offset)
 274     , m_easing(easing)
 275     , m_value(composite == AnimationEffect::CompositeReplace ?
 276         AnimatableValue::takeConstRef(value) :
 277         static_cast<PassRefPtr<CompositableValue> >(AddCompositableValue::create(value)))
 278 {
 279 }
 280
 281 KeyframeEffectModel::PropertySpecificKeyframe::PropertySpecificKeyframe(double offset, PassRefPtr<TimingFunction> easing, PassRefPtr<CompositableValue> value)
 282     : m_offset(offset)
 283     , m_easing(easing)
 284     , m_value(value)
 285 {
 286     ASSERT(!isNull(m_offset));
 287 }
 288
 289 PassOwnPtr<KeyframeEffectModel::PropertySpecificKeyframe> KeyframeEffectModel::PropertySpecificKeyframe::cloneWithOffset(double offset) const
 290 {
 291     return adoptPtr(new PropertySpecificKeyframe(offset, m_easing, PassRefPtr<CompositableValue>(m_value)));
 292 }
 293
 294
 295 void KeyframeEffectModel::PropertySpecificKeyframeGroup::appendKeyframe(PassOwnPtr<PropertySpecificKeyframe> keyframe)
 296 {
 297     ASSERT(m_keyframes.isEmpty() || m_keyframes.last()->offset() <= keyframe->offset());
 298     m_keyframes.append(keyframe);
 299 }
 300
 301 void KeyframeEffectModel::PropertySpecificKeyframeGroup::removeRedundantKeyframes()
 302 {
 303     // As an optimization, removes keyframes in the following categories, as
 304     // they will never be used by sample().
 305     // - End keyframes with the same offset as their neighbor
 306     // - Interior keyframes with the same offset as both their neighbors
 307     // Note that synthetic keyframes must be added before this method is
 308     // called.
 309     ASSERT(m_keyframes.size() >= 2);
 310     for (int i = m_keyframes.size() - 1; i >= 0; --i) {
 311         double offset = m_keyframes[i]->offset();
 312         bool hasSameOffsetAsPreviousNeighbor = !i || m_keyframes[i - 1]->offset() == offset;
 313         bool hasSameOffsetAsNextNeighbor = i == static_cast<int>(m_keyframes.size() - 1) || m_keyframes[i + 1]->offset() == offset;
 314         if (hasSameOffsetAsPreviousNeighbor && hasSameOffsetAsNextNeighbor)
 315             m_keyframes.remove(i);
 316     }
 317     ASSERT(m_keyframes.size() >= 2);
 318 }
 319
 320 void KeyframeEffectModel::PropertySpecificKeyframeGroup::addSyntheticKeyframeIfRequired()
 321 {
 322     ASSERT(!m_keyframes.isEmpty());
 323     double offset = m_keyframes.first()->offset();
 324     bool allOffsetsEqual = true;
 325     for (PropertySpecificKeyframeVector::const_iterator iter = m_keyframes.begin() + 1; iter != m_keyframes.end(); ++iter) {
 326         if ((*iter)->offset() != offset) {
 327             allOffsetsEqual = false;
 328             break;
 329         }
 330     }
 331     if (!allOffsetsEqual)
 332         return;
 333
 334     if (!offset)
 335         appendKeyframe(m_keyframes.first()->cloneWithOffset(1.0));
 336     else
 337         m_keyframes.insert(0, adoptPtr(new PropertySpecificKeyframe(0.0, 0, AnimatableValue::neutralValue(), CompositeAdd)));
 338 }
 339
 340 PassRefPtr<AnimationEffect::CompositableValue> KeyframeEffectModel::PropertySpecificKeyframeGroup::sample(int iteration, double offset) const
 341 {
 342     // FIXME: Implement accumulation.
 343     ASSERT_UNUSED(iteration, iteration >= 0);
 344     ASSERT(!isNull(offset));
 345
 346     // Bail if offset is null, as this can lead to buffer overflow below.
 347     if (isNull(offset))
 348         return const_cast<CompositableValue*>(m_keyframes.first()->value());
 349
 350     double minimumOffset = m_keyframes.first()->offset();
 351     double maximumOffset = m_keyframes.last()->offset();
 352     ASSERT(minimumOffset != maximumOffset);
 353
 354     PropertySpecificKeyframeVector::const_iterator before;
 355     PropertySpecificKeyframeVector::const_iterator after;
 356
 357     // Note that this algorithm is simpler than that in the spec because we
 358     // have removed keyframes with equal offsets in
 359     // removeRedundantKeyframes().
 360     if (offset < minimumOffset) {
 361         before = m_keyframes.begin();
 362         after = before + 1;
 363         ASSERT((*before)->offset() > offset);
 364         ASSERT((*after)->offset() > offset);
 365     } else if (offset >= maximumOffset) {
 366         after = m_keyframes.end() - 1;
 367         before = after - 1;
 368         ASSERT((*before)->offset() < offset);
 369         ASSERT((*after)->offset() <= offset);
 370     } else {
 371         // FIXME: This is inefficient for large numbers of keyframes. Consider
 372         // using binary search.
 373         after = m_keyframes.begin();
 374         while ((*after)->offset() <= offset)
 375             ++after;
 376         before = after - 1;
 377         ASSERT((*before)->offset() <= offset);
 378         ASSERT((*after)->offset() > offset);
 379     }
 380
 381     if ((*before)->offset() == offset)
 382         return const_cast<CompositableValue*>((*before)->value());
 383     if ((*after)->offset() == offset)
 384         return const_cast<CompositableValue*>((*after)->value());
 385
 386     double fraction = (offset - (*before)->offset()) / ((*after)->offset() - (*before)->offset());
 387     if (const TimingFunction* timingFunction = (*before)->easing())
 388         fraction = timingFunction->evaluate(fraction, accuracyForKeyframeEasing);
 389     return BlendedCompositableValue::create((*before)->value(), (*after)->value(), fraction);
 390 }
 391
 392 } // namespace