cc/trees/property_tree.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <set>
   6 #include <vector>
   7
   8 #include "base/logging.h"
   9 #include "cc/base/math_util.h"
  10 #include "cc/trees/property_tree.h"
  11
  12 namespace cc {
  13
  14 template <typename T>
  15 PropertyTree<T>::PropertyTree()
  16     : needs_update_(false) {
  17   nodes_.push_back(T());
  18   back()->id = 0;
  19   back()->parent_id = -1;
  20 }
  21
  22 template <typename T>
  23 PropertyTree<T>::~PropertyTree() {
  24 }
  25
  26 TransformTree::TransformTree() : source_to_parent_updates_allowed_(true) {
  27 }
  28
  29 template <typename T>
  30 int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
  31   DCHECK_GT(nodes_.size(), 0u);
  32   nodes_.push_back(tree_node);
  33   T& node = nodes_.back();
  34   node.parent_id = parent_id;
  35   node.id = static_cast<int>(nodes_.size()) - 1;
  36   return node.id;
  37 }
  38
  39 template <typename T>
  40 void PropertyTree<T>::clear() {
  41   nodes_.clear();
  42   nodes_.push_back(T());
  43   back()->id = 0;
  44   back()->parent_id = -1;
  45 }
  46
  47 template class PropertyTree<TransformNode>;
  48 template class PropertyTree<ClipNode>;
  49 template class PropertyTree<OpacityNode>;
  50
  51 TransformNodeData::TransformNodeData()
  52     : target_id(-1),
  53       content_target_id(-1),
  54       source_node_id(-1),
  55       needs_local_transform_update(true),
  56       is_invertible(true),
  57       ancestors_are_invertible(true),
  58       is_animated(false),
  59       to_screen_is_animated(false),
  60       flattens_inherited_transform(false),
  61       node_and_ancestors_are_flat(true),
  62       scrolls(false),
  63       needs_sublayer_scale(false),
  64       layer_scale_factor(1.0f),
  65       post_local_scale_factor(1.0f) {
  66 }
  67
  68 TransformNodeData::~TransformNodeData() {
  69 }
  70
  71 void TransformNodeData::update_pre_local_transform(
  72     const gfx::Point3F& transform_origin) {
  73   pre_local.MakeIdentity();
  74   pre_local.Translate3d(-transform_origin.x(), -transform_origin.y(),
  75                         -transform_origin.z());
  76 }
  77
  78 void TransformNodeData::update_post_local_transform(
  79     const gfx::PointF& position,
  80     const gfx::Point3F& transform_origin) {
  81   post_local.MakeIdentity();
  82   post_local.Scale(post_local_scale_factor, post_local_scale_factor);
  83   post_local.Translate3d(
  84       position.x() + source_offset.x() + transform_origin.x(),
  85       position.y() + source_offset.y() + transform_origin.y(),
  86       transform_origin.z());
  87 }
  88
  89 ClipNodeData::ClipNodeData() : transform_id(-1), target_id(-1) {
  90 }
  91
  92 bool TransformTree::ComputeTransform(int source_id,
  93                                      int dest_id,
  94                                      gfx::Transform* transform) const {
  95   transform->MakeIdentity();
  96
  97   if (source_id == dest_id)
  98     return true;
  99
 100   if (source_id > dest_id) {
 101     return CombineTransformsBetween(source_id, dest_id, transform);
 102   }
 103
 104   return CombineInversesBetween(source_id, dest_id, transform);
 105 }
 106
 107 bool TransformTree::ComputeTransformWithDestinationSublayerScale(
 108     int source_id,
 109     int dest_id,
 110     gfx::Transform* transform) const {
 111   bool success = ComputeTransform(source_id, dest_id, transform);
 112
 113   const TransformNode* dest_node = Node(dest_id);
 114   if (!dest_node->data.needs_sublayer_scale)
 115     return success;
 116
 117   transform->matrix().postScale(dest_node->data.sublayer_scale.x(),
 118                                 dest_node->data.sublayer_scale.y(), 1.f);
 119   return success;
 120 }
 121
 122 bool TransformTree::ComputeTransformWithSourceSublayerScale(
 123     int source_id,
 124     int dest_id,
 125     gfx::Transform* transform) const {
 126   bool success = ComputeTransform(source_id, dest_id, transform);
 127
 128   const TransformNode* source_node = Node(source_id);
 129   if (!source_node->data.needs_sublayer_scale)
 130     return success;
 131
 132   transform->Scale(1.f / source_node->data.sublayer_scale.x(),
 133                    1.f / source_node->data.sublayer_scale.y());
 134   return success;
 135 }
 136
 137 bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
 138   gfx::Transform transform;
 139   return ComputeTransform(source_id, dest_id, &transform) &&
 140          transform.Preserves2dAxisAlignment();
 141 }
 142
 143 bool TransformTree::NeedsSourceToParentUpdate(TransformNode* node) {
 144   return (source_to_parent_updates_allowed() &&
 145           node->parent_id != node->data.source_node_id);
 146 }
 147
 148 void TransformTree::UpdateTransforms(int id) {
 149   TransformNode* node = Node(id);
 150   TransformNode* parent_node = parent(node);
 151   TransformNode* target_node = Node(node->data.target_id);
 152   if (node->data.needs_local_transform_update ||
 153       NeedsSourceToParentUpdate(node))
 154     UpdateLocalTransform(node);
 155   UpdateScreenSpaceTransform(node, parent_node, target_node);
 156   UpdateSublayerScale(node);
 157   UpdateTargetSpaceTransform(node, target_node);
 158   UpdateIsAnimated(node, parent_node);
 159   UpdateSnapping(node);
 160 }
 161
 162 bool TransformTree::IsDescendant(int desc_id, int source_id) const {
 163   while (desc_id != source_id) {
 164     if (desc_id < 0)
 165       return false;
 166     desc_id = Node(desc_id)->parent_id;
 167   }
 168   return true;
 169 }
 170
 171 bool TransformTree::CombineTransformsBetween(int source_id,
 172                                              int dest_id,
 173                                              gfx::Transform* transform) const {
 174   DCHECK(source_id > dest_id);
 175   const TransformNode* current = Node(source_id);
 176   const TransformNode* dest = Node(dest_id);
 177   // Combine transforms to and from the screen when possible. Since flattening
 178   // is a non-linear operation, we cannot use this approach when there is
 179   // non-trivial flattening between the source and destination nodes. For
 180   // example, consider the tree R->A->B->C, where B flattens its inherited
 181   // transform, and A has a non-flat transform. Suppose C is the source and A is
 182   // the destination. The expected result is C * B. But C's to_screen
 183   // transform is C * B * flattened(A * R), and A's from_screen transform is
 184   // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
 185   // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
 186   // A's from_screen will not produce the correct result.
 187   if (!dest || (dest->data.ancestors_are_invertible &&
 188                 dest->data.node_and_ancestors_are_flat)) {
 189     transform->ConcatTransform(current->data.to_screen);
 190     if (dest)
 191       transform->ConcatTransform(dest->data.from_screen);
 192     return true;
 193   }
 194
 195   // Flattening is defined in a way that requires it to be applied while
 196   // traversing downward in the tree. We first identify nodes that are on the
 197   // path from the source to the destination (this is traversing upward), and
 198   // then we visit these nodes in reverse order, flattening as needed. We
 199   // early-out if we get to a node whose target node is the destination, since
 200   // we can then re-use the target space transform stored at that node.
 201   std::vector<int> source_to_destination;
 202   source_to_destination.push_back(current->id);
 203   current = parent(current);
 204   for (; current && current->id > dest_id; current = parent(current)) {
 205     if (current->data.target_id == dest_id &&
 206         current->data.content_target_id == dest_id)
 207       break;
 208     source_to_destination.push_back(current->id);
 209   }
 210
 211   gfx::Transform combined_transform;
 212   if (current->id > dest_id) {
 213     combined_transform = current->data.to_target;
 214     // The stored target space transform has sublayer scale baked in, but we
 215     // need the unscaled transform.
 216     combined_transform.Scale(1.0f / dest->data.sublayer_scale.x(),
 217                              1.0f / dest->data.sublayer_scale.y());
 218   } else if (current->id < dest_id) {
 219     // We have reached the lowest common ancestor of the source and destination
 220     // nodes. This case can occur when we are transforming between a node
 221     // corresponding to a fixed-position layer (or its descendant) and the node
 222     // corresponding to the layer's render target. For example, consider the
 223     // layer tree R->T->S->F where F is fixed-position, S owns a render surface,
 224     // and T has a significant transform. This will yield the following
 225     // transform tree:
 226     //    R
 227     //    |
 228     //    T
 229     //   /|
 230     //  S F
 231     // In this example, T will have id 2, S will have id 3, and F will have id
 232     // 4. When walking up the ancestor chain from F, the first node with a
 233     // smaller id than S will be T, the lowest common ancestor of these nodes.
 234     // We compute the transform from T to S here, and then from F to T in the
 235     // loop below.
 236     DCHECK(IsDescendant(dest_id, current->id));
 237     CombineInversesBetween(current->id, dest_id, &combined_transform);
 238     DCHECK(combined_transform.IsApproximatelyIdentityOrTranslation(
 239         SkDoubleToMScalar(1e-4)));
 240   }
 241
 242   for (int i = source_to_destination.size() - 1; i >= 0; i--) {
 243     const TransformNode* node = Node(source_to_destination[i]);
 244     if (node->data.flattens_inherited_transform)
 245       combined_transform.FlattenTo2d();
 246     combined_transform.PreconcatTransform(node->data.to_parent);
 247   }
 248
 249   transform->ConcatTransform(combined_transform);
 250   return true;
 251 }
 252
 253 bool TransformTree::CombineInversesBetween(int source_id,
 254                                            int dest_id,
 255                                            gfx::Transform* transform) const {
 256   DCHECK(source_id < dest_id);
 257   const TransformNode* current = Node(dest_id);
 258   const TransformNode* dest = Node(source_id);
 259   // Just as in CombineTransformsBetween, we can use screen space transforms in
 260   // this computation only when there isn't any non-trivial flattening
 261   // involved.
 262   if (current->data.ancestors_are_invertible &&
 263       current->data.node_and_ancestors_are_flat) {
 264     transform->PreconcatTransform(current->data.from_screen);
 265     if (dest)
 266       transform->PreconcatTransform(dest->data.to_screen);
 267     return true;
 268   }
 269
 270   // Inverting a flattening is not equivalent to flattening an inverse. This
 271   // means we cannot, for example, use the inverse of each node's to_parent
 272   // transform, flattening where needed. Instead, we must compute the transform
 273   // from the destination to the source, with flattening, and then invert the
 274   // result.
 275   gfx::Transform dest_to_source;
 276   CombineTransformsBetween(dest_id, source_id, &dest_to_source);
 277   gfx::Transform source_to_dest;
 278   bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
 279   transform->PreconcatTransform(source_to_dest);
 280   return all_are_invertible;
 281 }
 282
 283 void TransformTree::UpdateLocalTransform(TransformNode* node) {
 284   gfx::Transform transform = node->data.post_local;
 285   if (NeedsSourceToParentUpdate(node)) {
 286     gfx::Transform to_parent;
 287     ComputeTransform(node->data.source_node_id, node->parent_id, &to_parent);
 288     node->data.source_to_parent = to_parent.To2dTranslation();
 289   }
 290   transform.Translate(
 291       node->data.source_to_parent.x() - node->data.scroll_offset.x(),
 292       node->data.source_to_parent.y() - node->data.scroll_offset.y());
 293   transform.PreconcatTransform(node->data.local);
 294   transform.PreconcatTransform(node->data.pre_local);
 295   node->data.set_to_parent(transform);
 296   node->data.needs_local_transform_update = false;
 297 }
 298
 299 void TransformTree::UpdateScreenSpaceTransform(TransformNode* node,
 300                                                TransformNode* parent_node,
 301                                                TransformNode* target_node) {
 302   if (!parent_node) {
 303     node->data.to_screen = node->data.to_parent;
 304     node->data.ancestors_are_invertible = true;
 305     node->data.to_screen_is_animated = false;
 306     node->data.node_and_ancestors_are_flat = node->data.to_parent.IsFlat();
 307   } else {
 308     node->data.to_screen = parent_node->data.to_screen;
 309     if (node->data.flattens_inherited_transform)
 310       node->data.to_screen.FlattenTo2d();
 311     node->data.to_screen.PreconcatTransform(node->data.to_parent);
 312     node->data.ancestors_are_invertible =
 313         parent_node->data.ancestors_are_invertible;
 314     node->data.node_and_ancestors_are_flat =
 315         parent_node->data.node_and_ancestors_are_flat &&
 316         node->data.to_parent.IsFlat();
 317   }
 318
 319   if (!node->data.to_screen.GetInverse(&node->data.from_screen))
 320     node->data.ancestors_are_invertible = false;
 321 }
 322
 323 void TransformTree::UpdateSublayerScale(TransformNode* node) {
 324   // The sublayer scale depends on the screen space transform, so update it too.
 325   node->data.sublayer_scale =
 326       node->data.needs_sublayer_scale
 327           ? MathUtil::ComputeTransform2dScaleComponents(
 328                 node->data.to_screen, node->data.layer_scale_factor)
 329           : gfx::Vector2dF(1.0f, 1.0f);
 330 }
 331
 332 void TransformTree::UpdateTargetSpaceTransform(TransformNode* node,
 333                                                TransformNode* target_node) {
 334   if (node->data.needs_sublayer_scale) {
 335     node->data.to_target.MakeIdentity();
 336     node->data.to_target.Scale(node->data.sublayer_scale.x(),
 337                                node->data.sublayer_scale.y());
 338   } else {
 339     const bool target_is_root_surface = target_node->id == 1;
 340     // In order to include the root transform for the root surface, we walk up
 341     // to the root of the transform tree in ComputeTransform.
 342     int target_id = target_is_root_surface ? 0 : target_node->id;
 343     ComputeTransformWithDestinationSublayerScale(node->id, target_id,
 344                                                  &node->data.to_target);
 345   }
 346
 347   if (!node->data.to_target.GetInverse(&node->data.from_target))
 348     node->data.ancestors_are_invertible = false;
 349 }
 350
 351 void TransformTree::UpdateIsAnimated(TransformNode* node,
 352                                      TransformNode* parent_node) {
 353   if (parent_node) {
 354     node->data.to_screen_is_animated =
 355         node->data.is_animated || parent_node->data.to_screen_is_animated;
 356   }
 357 }
 358
 359 void TransformTree::UpdateSnapping(TransformNode* node) {
 360   if (!node->data.scrolls || node->data.to_screen_is_animated ||
 361       !node->data.to_target.IsScaleOrTranslation()) {
 362     return;
 363   }
 364
 365   // Scroll snapping must be done in target space (the pixels we care about).
 366   // This means we effectively snap the target space transform. If TT is the
 367   // target space transform and TT' is TT with its translation components
 368   // rounded, then what we're after is the scroll delta X, where TT * X = TT'.
 369   // I.e., we want a transform that will realize our scroll snap. It follows
 370   // that X = TT^-1 * TT'. We cache TT and TT^-1 to make this more efficient.
 371   gfx::Transform rounded = node->data.to_target;
 372   rounded.RoundTranslationComponents();
 373   gfx::Transform delta = node->data.from_target;
 374   delta *= rounded;
 375
 376   DCHECK(delta.IsApproximatelyIdentityOrTranslation(SkDoubleToMScalar(1e-4)))
 377       << delta.ToString();
 378
 379   gfx::Vector2dF translation = delta.To2dTranslation();
 380
 381   // Now that we have our scroll delta, we must apply it to each of our
 382   // combined, to/from matrices.
 383   node->data.to_parent.Translate(translation.x(), translation.y());
 384   node->data.to_target.Translate(translation.x(), translation.y());
 385   node->data.from_target.matrix().postTranslate(-translation.x(),
 386                                                 -translation.y(), 0);
 387   node->data.to_screen.Translate(translation.x(), translation.y());
 388   node->data.from_screen.matrix().postTranslate(-translation.x(),
 389                                                 -translation.y(), 0);
 390
 391   node->data.scroll_snap = translation;
 392 }
 393
 394 PropertyTrees::PropertyTrees() : needs_rebuild(true), sequence_number(0) {
 395 }
 396
 397 }  // namespace cc