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   nodes_.push_back(T());
  17   back()->id = 0;
  18   back()->parent_id = -1;
  19 }
  20
  21 template <typename T>
  22 PropertyTree<T>::~PropertyTree() {
  23 }
  24
  25 template <typename T>
  26 int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
  27   DCHECK_GT(nodes_.size(), 0u);
  28   nodes_.push_back(tree_node);
  29   T& node = nodes_.back();
  30   node.parent_id = parent_id;
  31   node.id = static_cast<int>(nodes_.size()) - 1;
  32   return node.id;
  33 }
  34
  35 template class PropertyTree<TransformNode>;
  36 template class PropertyTree<ClipNode>;
  37 template class PropertyTree<OpacityNode>;
  38
  39 TransformNodeData::TransformNodeData()
  40     : target_id(-1),
  41       content_target_id(-1),
  42       needs_local_transform_update(true),
  43       is_invertible(true),
  44       ancestors_are_invertible(true),
  45       is_animated(false),
  46       to_screen_is_animated(false),
  47       flattens_inherited_transform(false),
  48       node_and_ancestors_are_flat(true),
  49       scrolls(false),
  50       needs_sublayer_scale(false),
  51       layer_scale_factor(1.0f) {
  52 }
  53
  54 TransformNodeData::~TransformNodeData() {
  55 }
  56
  57 ClipNodeData::ClipNodeData() : transform_id(-1), target_id(-1) {
  58 }
  59
  60 bool TransformTree::ComputeTransform(int source_id,
  61                                      int dest_id,
  62                                      gfx::Transform* transform) const {
  63   transform->MakeIdentity();
  64
  65   if (source_id == dest_id)
  66     return true;
  67
  68   if (source_id > dest_id && IsDescendant(source_id, dest_id))
  69     return CombineTransformsBetween(source_id, dest_id, transform);
  70
  71   if (dest_id > source_id && IsDescendant(dest_id, source_id))
  72     return CombineInversesBetween(source_id, dest_id, transform);
  73
  74   int lca = LowestCommonAncestor(source_id, dest_id);
  75
  76   bool no_singular_matrices_to_lca =
  77       CombineTransformsBetween(source_id, lca, transform);
  78
  79   bool no_singular_matrices_from_lca =
  80       CombineInversesBetween(lca, dest_id, transform);
  81
  82   return no_singular_matrices_to_lca && no_singular_matrices_from_lca;
  83 }
  84
  85 bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
  86   gfx::Transform transform;
  87   return ComputeTransform(source_id, dest_id, &transform) &&
  88          transform.Preserves2dAxisAlignment();
  89 }
  90
  91 void TransformTree::UpdateTransforms(int id) {
  92   TransformNode* node = Node(id);
  93   TransformNode* parent_node = parent(node);
  94   TransformNode* target_node = Node(node->data.target_id);
  95   if (node->data.needs_local_transform_update)
  96     UpdateLocalTransform(node);
  97   UpdateScreenSpaceTransform(node, parent_node, target_node);
  98   UpdateSublayerScale(node);
  99   UpdateTargetSpaceTransform(node, target_node);
 100   UpdateIsAnimated(node, parent_node);
 101   UpdateSnapping(node);
 102 }
 103
 104 bool TransformTree::IsDescendant(int desc_id, int source_id) const {
 105   while (desc_id != source_id) {
 106     if (desc_id < 0)
 107       return false;
 108     desc_id = Node(desc_id)->parent_id;
 109   }
 110   return true;
 111 }
 112
 113 int TransformTree::LowestCommonAncestor(int a, int b) const {
 114   std::set<int> chain_a;
 115   std::set<int> chain_b;
 116   while (a || b) {
 117     if (a) {
 118       a = Node(a)->parent_id;
 119       if (a > -1 && chain_b.find(a) != chain_b.end())
 120         return a;
 121       chain_a.insert(a);
 122     }
 123     if (b) {
 124       b = Node(b)->parent_id;
 125       if (b > -1 && chain_a.find(b) != chain_a.end())
 126         return b;
 127       chain_b.insert(b);
 128     }
 129   }
 130   NOTREACHED();
 131   return 0;
 132 }
 133
 134 bool TransformTree::CombineTransformsBetween(int source_id,
 135                                              int dest_id,
 136                                              gfx::Transform* transform) const {
 137   const TransformNode* current = Node(source_id);
 138   const TransformNode* dest = Node(dest_id);
 139   // Combine transforms to and from the screen when possible. Since flattening
 140   // is a non-linear operation, we cannot use this approach when there is
 141   // non-trivial flattening between the source and destination nodes. For
 142   // example, consider the tree R->A->B->C, where B flattens its inherited
 143   // transform, and A has a non-flat transform. Suppose C is the source and A is
 144   // the destination. The expected result is C * B. But C's to_screen
 145   // transform is C * B * flattened(A * R), and A's from_screen transform is
 146   // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
 147   // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
 148   // A's from_screen will not produce the correct result.
 149   if (!dest || (dest->data.ancestors_are_invertible &&
 150                 current->data.node_and_ancestors_are_flat)) {
 151     transform->ConcatTransform(current->data.to_screen);
 152     if (dest)
 153       transform->ConcatTransform(dest->data.from_screen);
 154     return true;
 155   }
 156
 157   bool all_are_invertible = true;
 158
 159   // Flattening is defined in a way that requires it to be applied while
 160   // traversing downward in the tree. We first identify nodes that are on the
 161   // path from the source to the destination (this is traversing upward), and
 162   // then we visit these nodes in reverse order, flattening as needed. We
 163   // early-out if we get to a node whose target node is the destination, since
 164   // we can then re-use the target space transform stored at that node.
 165   std::vector<int> source_to_destination;
 166   source_to_destination.push_back(current->id);
 167   current = parent(current);
 168   for (; current && current->id > dest_id; current = parent(current)) {
 169     if (current->data.target_id == dest_id &&
 170         current->data.content_target_id == dest_id)
 171       break;
 172     source_to_destination.push_back(current->id);
 173   }
 174
 175   gfx::Transform combined_transform;
 176   if (current->id > dest_id) {
 177     combined_transform = current->data.to_target;
 178     // The stored target space transform has sublayer scale baked in, but we
 179     // need the unscaled transform.
 180     combined_transform.Scale(1.0f / dest->data.sublayer_scale.x(),
 181                              1.0f / dest->data.sublayer_scale.y());
 182   }
 183
 184   for (int i = source_to_destination.size() - 1; i >= 0; i--) {
 185     const TransformNode* node = Node(source_to_destination[i]);
 186     if (node->data.flattens_inherited_transform)
 187       combined_transform.FlattenTo2d();
 188     combined_transform.PreconcatTransform(node->data.to_parent);
 189
 190     if (!node->data.is_invertible)
 191       all_are_invertible = false;
 192   }
 193
 194   transform->ConcatTransform(combined_transform);
 195   return all_are_invertible;
 196 }
 197
 198 bool TransformTree::CombineInversesBetween(int source_id,
 199                                            int dest_id,
 200                                            gfx::Transform* transform) const {
 201   const TransformNode* current = Node(dest_id);
 202   const TransformNode* dest = Node(source_id);
 203   // Just as in CombineTransformsBetween, we can use screen space transforms in
 204   // this computation only when there isn't any non-trivial flattening
 205   // involved.
 206   if (current->data.ancestors_are_invertible &&
 207       current->data.node_and_ancestors_are_flat) {
 208     transform->PreconcatTransform(current->data.from_screen);
 209     if (dest)
 210       transform->PreconcatTransform(dest->data.to_screen);
 211     return true;
 212   }
 213
 214   // Inverting a flattening is not equivalent to flattening an inverse. This
 215   // means we cannot, for example, use the inverse of each node's to_parent
 216   // transform, flattening where needed. Instead, we must compute the transform
 217   // from the destination to the source, with flattening, and then invert the
 218   // result.
 219   gfx::Transform dest_to_source;
 220   CombineTransformsBetween(dest_id, source_id, &dest_to_source);
 221   gfx::Transform source_to_dest;
 222   bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
 223   transform->PreconcatTransform(source_to_dest);
 224   return all_are_invertible;
 225 }
 226
 227 void TransformTree::UpdateLocalTransform(TransformNode* node) {
 228   gfx::Transform transform = node->data.post_local;
 229   transform.Translate(-node->data.scroll_offset.x(),
 230                       -node->data.scroll_offset.y());
 231   transform.PreconcatTransform(node->data.local);
 232   transform.PreconcatTransform(node->data.pre_local);
 233   node->data.set_to_parent(transform);
 234   node->data.needs_local_transform_update = false;
 235 }
 236
 237 void TransformTree::UpdateScreenSpaceTransform(TransformNode* node,
 238                                                TransformNode* parent_node,
 239                                                TransformNode* target_node) {
 240   if (!parent_node) {
 241     node->data.to_screen = node->data.to_parent;
 242     node->data.ancestors_are_invertible = true;
 243     node->data.to_screen_is_animated = false;
 244     node->data.node_and_ancestors_are_flat = node->data.to_parent.IsFlat();
 245   } else {
 246     node->data.to_screen = parent_node->data.to_screen;
 247     if (node->data.flattens_inherited_transform)
 248       node->data.to_screen.FlattenTo2d();
 249     node->data.to_screen.PreconcatTransform(node->data.to_parent);
 250     node->data.ancestors_are_invertible =
 251         parent_node->data.ancestors_are_invertible;
 252     node->data.node_and_ancestors_are_flat =
 253         parent_node->data.node_and_ancestors_are_flat &&
 254         node->data.to_parent.IsFlat();
 255   }
 256
 257   if (!node->data.to_screen.GetInverse(&node->data.from_screen))
 258     node->data.ancestors_are_invertible = false;
 259 }
 260
 261 void TransformTree::UpdateSublayerScale(TransformNode* node) {
 262   // The sublayer scale depends on the screen space transform, so update it too.
 263   node->data.sublayer_scale =
 264       node->data.needs_sublayer_scale
 265           ? MathUtil::ComputeTransform2dScaleComponents(
 266                 node->data.to_screen, node->data.layer_scale_factor)
 267           : gfx::Vector2dF(1.0f, 1.0f);
 268 }
 269
 270 void TransformTree::UpdateTargetSpaceTransform(TransformNode* node,
 271                                                TransformNode* target_node) {
 272   node->data.to_target.MakeIdentity();
 273   if (node->data.needs_sublayer_scale) {
 274     node->data.to_target.Scale(node->data.sublayer_scale.x(),
 275                                node->data.sublayer_scale.y());
 276   } else {
 277     const bool target_is_root_surface = target_node->id == 1;
 278     // In order to include the root transform for the root surface, we walk up
 279     // to the root of the transform tree in ComputeTransform.
 280     int target_id = target_is_root_surface ? 0 : target_node->id;
 281     if (target_node) {
 282       node->data.to_target.Scale(target_node->data.sublayer_scale.x(),
 283                                  target_node->data.sublayer_scale.y());
 284     }
 285
 286     gfx::Transform unscaled_target_transform;
 287     ComputeTransform(node->id, target_id, &unscaled_target_transform);
 288     node->data.to_target.PreconcatTransform(unscaled_target_transform);
 289   }
 290
 291   if (!node->data.to_target.GetInverse(&node->data.from_target))
 292     node->data.ancestors_are_invertible = false;
 293 }
 294
 295 void TransformTree::UpdateIsAnimated(TransformNode* node,
 296                                      TransformNode* parent_node) {
 297   if (parent_node) {
 298     node->data.to_screen_is_animated =
 299         node->data.is_animated || parent_node->data.to_screen_is_animated;
 300   }
 301 }
 302
 303 void TransformTree::UpdateSnapping(TransformNode* node) {
 304   if (!node->data.scrolls || node->data.to_screen_is_animated ||
 305       !node->data.to_target.IsScaleOrTranslation()) {
 306     return;
 307   }
 308
 309   // Scroll snapping must be done in target space (the pixels we care about).
 310   // This means we effectively snap the target space transform. If TT is the
 311   // target space transform and TT' is TT with its translation components
 312   // rounded, then what we're after is the scroll delta X, where TT * X = TT'.
 313   // I.e., we want a transform that will realize our scroll snap. It follows
 314   // that X = TT^-1 * TT'. We cache TT and TT^-1 to make this more efficient.
 315   gfx::Transform rounded = node->data.to_target;
 316   rounded.RoundTranslationComponents();
 317   gfx::Transform delta = node->data.from_target;
 318   delta *= rounded;
 319   gfx::Transform inverse_delta(gfx::Transform::kSkipInitialization);
 320   bool invertible_delta = delta.GetInverse(&inverse_delta);
 321
 322   // The delta should be a translation, modulo floating point error, and should
 323   // therefore be invertible.
 324   DCHECK(invertible_delta);
 325
 326   // Now that we have our scroll delta, we must apply it to each of our
 327   // combined, to/from matrices.
 328   node->data.to_parent.PreconcatTransform(delta);
 329   node->data.to_target.PreconcatTransform(delta);
 330   node->data.from_target.ConcatTransform(inverse_delta);
 331   node->data.to_screen.PreconcatTransform(delta);
 332   node->data.from_screen.ConcatTransform(inverse_delta);
 333 }
 334
 335 }  // namespace cc