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 TransformTree::~TransformTree() {
  30 }
  31
  32 template <typename T>
  33 int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
  34   DCHECK_GT(nodes_.size(), 0u);
  35   nodes_.push_back(tree_node);
  36   T& node = nodes_.back();
  37   node.parent_id = parent_id;
  38   node.id = static_cast<int>(nodes_.size()) - 1;
  39   return node.id;
  40 }
  41
  42 template <typename T>
  43 void PropertyTree<T>::clear() {
  44   nodes_.clear();
  45   nodes_.push_back(T());
  46   back()->id = 0;
  47   back()->parent_id = -1;
  48 }
  49
  50 template class PropertyTree<TransformNode>;
  51 template class PropertyTree<ClipNode>;
  52 template class PropertyTree<OpacityNode>;
  53
  54 TransformNodeData::TransformNodeData()
  55     : target_id(-1),
  56       content_target_id(-1),
  57       source_node_id(-1),
  58       needs_local_transform_update(true),
  59       is_invertible(true),
  60       ancestors_are_invertible(true),
  61       is_animated(false),
  62       to_screen_is_animated(false),
  63       flattens_inherited_transform(false),
  64       node_and_ancestors_are_flat(true),
  65       node_and_ancestors_have_only_integer_translation(true),
  66       scrolls(false),
  67       needs_sublayer_scale(false),
  68       affected_by_inner_viewport_bounds_delta_x(false),
  69       affected_by_inner_viewport_bounds_delta_y(false),
  70       affected_by_outer_viewport_bounds_delta_x(false),
  71       affected_by_outer_viewport_bounds_delta_y(false),
  72       layer_scale_factor(1.0f),
  73       post_local_scale_factor(1.0f) {
  74 }
  75
  76 TransformNodeData::~TransformNodeData() {
  77 }
  78
  79 void TransformNodeData::update_pre_local_transform(
  80     const gfx::Point3F& transform_origin) {
  81   pre_local.MakeIdentity();
  82   pre_local.Translate3d(-transform_origin.x(), -transform_origin.y(),
  83                         -transform_origin.z());
  84 }
  85
  86 void TransformNodeData::update_post_local_transform(
  87     const gfx::PointF& position,
  88     const gfx::Point3F& transform_origin) {
  89   post_local.MakeIdentity();
  90   post_local.Scale(post_local_scale_factor, post_local_scale_factor);
  91   post_local.Translate3d(
  92       position.x() + source_offset.x() + transform_origin.x(),
  93       position.y() + source_offset.y() + transform_origin.y(),
  94       transform_origin.z());
  95 }
  96
  97 ClipNodeData::ClipNodeData()
  98     : transform_id(-1),
  99       target_id(-1),
 100       inherit_parent_target_space_clip(false),
 101       requires_tight_clip_rect(true) {}
 102
 103 OpacityNodeData::OpacityNodeData() : opacity(1.f), screen_space_opacity(1.f) {
 104 }
 105
 106 void TransformTree::clear() {
 107   PropertyTree<TransformNode>::clear();
 108
 109   nodes_affected_by_inner_viewport_bounds_delta_.clear();
 110   nodes_affected_by_outer_viewport_bounds_delta_.clear();
 111 }
 112
 113 bool TransformTree::ComputeTransform(int source_id,
 114                                      int dest_id,
 115                                      gfx::Transform* transform) const {
 116   transform->MakeIdentity();
 117
 118   if (source_id == dest_id)
 119     return true;
 120
 121   if (source_id > dest_id) {
 122     return CombineTransformsBetween(source_id, dest_id, transform);
 123   }
 124
 125   return CombineInversesBetween(source_id, dest_id, transform);
 126 }
 127
 128 bool TransformTree::ComputeTransformWithDestinationSublayerScale(
 129     int source_id,
 130     int dest_id,
 131     gfx::Transform* transform) const {
 132   bool success = ComputeTransform(source_id, dest_id, transform);
 133
 134   const TransformNode* dest_node = Node(dest_id);
 135   if (!dest_node->data.needs_sublayer_scale)
 136     return success;
 137
 138   transform->matrix().postScale(dest_node->data.sublayer_scale.x(),
 139                                 dest_node->data.sublayer_scale.y(), 1.f);
 140   return success;
 141 }
 142
 143 bool TransformTree::ComputeTransformWithSourceSublayerScale(
 144     int source_id,
 145     int dest_id,
 146     gfx::Transform* transform) const {
 147   bool success = ComputeTransform(source_id, dest_id, transform);
 148
 149   const TransformNode* source_node = Node(source_id);
 150   if (!source_node->data.needs_sublayer_scale)
 151     return success;
 152
 153   if (source_node->data.sublayer_scale.x() == 0 ||
 154       source_node->data.sublayer_scale.y() == 0)
 155     return false;
 156
 157   transform->Scale(1.f / source_node->data.sublayer_scale.x(),
 158                    1.f / source_node->data.sublayer_scale.y());
 159   return success;
 160 }
 161
 162 bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
 163   gfx::Transform transform;
 164   return ComputeTransform(source_id, dest_id, &transform) &&
 165          transform.Preserves2dAxisAlignment();
 166 }
 167
 168 bool TransformTree::NeedsSourceToParentUpdate(TransformNode* node) {
 169   return (source_to_parent_updates_allowed() &&
 170           node->parent_id != node->data.source_node_id);
 171 }
 172
 173 void TransformTree::UpdateTransforms(int id) {
 174   TransformNode* node = Node(id);
 175   TransformNode* parent_node = parent(node);
 176   TransformNode* target_node = Node(node->data.target_id);
 177   if (node->data.needs_local_transform_update ||
 178       NeedsSourceToParentUpdate(node))
 179     UpdateLocalTransform(node);
 180   UpdateScreenSpaceTransform(node, parent_node, target_node);
 181   UpdateSublayerScale(node);
 182   UpdateTargetSpaceTransform(node, target_node);
 183   UpdateIsAnimated(node, parent_node);
 184   UpdateSnapping(node);
 185   UpdateNodeAndAncestorsHaveIntegerTranslations(node, parent_node);
 186 }
 187
 188 bool TransformTree::IsDescendant(int desc_id, int source_id) const {
 189   while (desc_id != source_id) {
 190     if (desc_id < 0)
 191       return false;
 192     desc_id = Node(desc_id)->parent_id;
 193   }
 194   return true;
 195 }
 196
 197 bool TransformTree::CombineTransformsBetween(int source_id,
 198                                              int dest_id,
 199                                              gfx::Transform* transform) const {
 200   DCHECK(source_id > dest_id);
 201   const TransformNode* current = Node(source_id);
 202   const TransformNode* dest = Node(dest_id);
 203   // Combine transforms to and from the screen when possible. Since flattening
 204   // is a non-linear operation, we cannot use this approach when there is
 205   // non-trivial flattening between the source and destination nodes. For
 206   // example, consider the tree R->A->B->C, where B flattens its inherited
 207   // transform, and A has a non-flat transform. Suppose C is the source and A is
 208   // the destination. The expected result is C * B. But C's to_screen
 209   // transform is C * B * flattened(A * R), and A's from_screen transform is
 210   // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
 211   // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
 212   // A's from_screen will not produce the correct result.
 213   if (!dest || (dest->data.ancestors_are_invertible &&
 214                 dest->data.node_and_ancestors_are_flat)) {
 215     transform->ConcatTransform(current->data.to_screen);
 216     if (dest)
 217       transform->ConcatTransform(dest->data.from_screen);
 218     return true;
 219   }
 220
 221   // Flattening is defined in a way that requires it to be applied while
 222   // traversing downward in the tree. We first identify nodes that are on the
 223   // path from the source to the destination (this is traversing upward), and
 224   // then we visit these nodes in reverse order, flattening as needed. We
 225   // early-out if we get to a node whose target node is the destination, since
 226   // we can then re-use the target space transform stored at that node. However,
 227   // we cannot re-use a stored target space transform if the destination has a
 228   // zero sublayer scale, since stored target space transforms have sublayer
 229   // scale baked in, but we need to compute an unscaled transform.
 230   std::vector<int> source_to_destination;
 231   source_to_destination.push_back(current->id);
 232   current = parent(current);
 233   bool destination_has_non_zero_sublayer_scale =
 234       dest->data.sublayer_scale.x() != 0.f &&
 235       dest->data.sublayer_scale.y() != 0.f;
 236   DCHECK(destination_has_non_zero_sublayer_scale ||
 237          !dest->data.ancestors_are_invertible);
 238   for (; current && current->id > dest_id; current = parent(current)) {
 239     if (destination_has_non_zero_sublayer_scale &&
 240         current->data.target_id == dest_id &&
 241         current->data.content_target_id == dest_id)
 242       break;
 243     source_to_destination.push_back(current->id);
 244   }
 245
 246   gfx::Transform combined_transform;
 247   if (current->id > dest_id) {
 248     combined_transform = current->data.to_target;
 249     // The stored target space transform has sublayer scale baked in, but we
 250     // need the unscaled transform.
 251     combined_transform.Scale(1.0f / dest->data.sublayer_scale.x(),
 252                              1.0f / dest->data.sublayer_scale.y());
 253   } else if (current->id < dest_id) {
 254     // We have reached the lowest common ancestor of the source and destination
 255     // nodes. This case can occur when we are transforming between a node
 256     // corresponding to a fixed-position layer (or its descendant) and the node
 257     // corresponding to the layer's render target. For example, consider the
 258     // layer tree R->T->S->F where F is fixed-position, S owns a render surface,
 259     // and T has a significant transform. This will yield the following
 260     // transform tree:
 261     //    R
 262     //    |
 263     //    T
 264     //   /|
 265     //  S F
 266     // In this example, T will have id 2, S will have id 3, and F will have id
 267     // 4. When walking up the ancestor chain from F, the first node with a
 268     // smaller id than S will be T, the lowest common ancestor of these nodes.
 269     // We compute the transform from T to S here, and then from F to T in the
 270     // loop below.
 271     DCHECK(IsDescendant(dest_id, current->id));
 272     CombineInversesBetween(current->id, dest_id, &combined_transform);
 273     DCHECK(combined_transform.IsApproximatelyIdentityOrTranslation(
 274         SkDoubleToMScalar(1e-4)));
 275   }
 276
 277   size_t source_to_destination_size = source_to_destination.size();
 278   for (size_t i = 0; i < source_to_destination_size; ++i) {
 279     size_t index = source_to_destination_size - 1 - i;
 280     const TransformNode* node = Node(source_to_destination[index]);
 281     if (node->data.flattens_inherited_transform)
 282       combined_transform.FlattenTo2d();
 283     combined_transform.PreconcatTransform(node->data.to_parent);
 284   }
 285
 286   transform->ConcatTransform(combined_transform);
 287   return true;
 288 }
 289
 290 bool TransformTree::CombineInversesBetween(int source_id,
 291                                            int dest_id,
 292                                            gfx::Transform* transform) const {
 293   DCHECK(source_id < dest_id);
 294   const TransformNode* current = Node(dest_id);
 295   const TransformNode* dest = Node(source_id);
 296   // Just as in CombineTransformsBetween, we can use screen space transforms in
 297   // this computation only when there isn't any non-trivial flattening
 298   // involved.
 299   if (current->data.ancestors_are_invertible &&
 300       current->data.node_and_ancestors_are_flat) {
 301     transform->PreconcatTransform(current->data.from_screen);
 302     if (dest)
 303       transform->PreconcatTransform(dest->data.to_screen);
 304     return true;
 305   }
 306
 307   // Inverting a flattening is not equivalent to flattening an inverse. This
 308   // means we cannot, for example, use the inverse of each node's to_parent
 309   // transform, flattening where needed. Instead, we must compute the transform
 310   // from the destination to the source, with flattening, and then invert the
 311   // result.
 312   gfx::Transform dest_to_source;
 313   CombineTransformsBetween(dest_id, source_id, &dest_to_source);
 314   gfx::Transform source_to_dest;
 315   bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
 316   transform->PreconcatTransform(source_to_dest);
 317   return all_are_invertible;
 318 }
 319
 320 void TransformTree::UpdateLocalTransform(TransformNode* node) {
 321   gfx::Transform transform = node->data.post_local;
 322   if (NeedsSourceToParentUpdate(node)) {
 323     gfx::Transform to_parent;
 324     ComputeTransform(node->data.source_node_id, node->parent_id, &to_parent);
 325     node->data.source_to_parent = to_parent.To2dTranslation();
 326   }
 327
 328   gfx::Vector2dF fixed_position_adjustment;
 329   if (node->data.affected_by_inner_viewport_bounds_delta_x)
 330     fixed_position_adjustment.set_x(inner_viewport_bounds_delta_.x());
 331   else if (node->data.affected_by_outer_viewport_bounds_delta_x)
 332     fixed_position_adjustment.set_x(outer_viewport_bounds_delta_.x());
 333
 334   if (node->data.affected_by_inner_viewport_bounds_delta_y)
 335     fixed_position_adjustment.set_y(inner_viewport_bounds_delta_.y());
 336   else if (node->data.affected_by_outer_viewport_bounds_delta_y)
 337     fixed_position_adjustment.set_y(outer_viewport_bounds_delta_.y());
 338
 339   transform.Translate(
 340       node->data.source_to_parent.x() - node->data.scroll_offset.x() +
 341           fixed_position_adjustment.x(),
 342       node->data.source_to_parent.y() - node->data.scroll_offset.y() +
 343           fixed_position_adjustment.y());
 344   transform.PreconcatTransform(node->data.local);
 345   transform.PreconcatTransform(node->data.pre_local);
 346   node->data.set_to_parent(transform);
 347   node->data.needs_local_transform_update = false;
 348 }
 349
 350 void TransformTree::UpdateScreenSpaceTransform(TransformNode* node,
 351                                                TransformNode* parent_node,
 352                                                TransformNode* target_node) {
 353   if (!parent_node) {
 354     node->data.to_screen = node->data.to_parent;
 355     node->data.ancestors_are_invertible = true;
 356     node->data.to_screen_is_animated = false;
 357     node->data.node_and_ancestors_are_flat = node->data.to_parent.IsFlat();
 358   } else {
 359     node->data.to_screen = parent_node->data.to_screen;
 360     if (node->data.flattens_inherited_transform)
 361       node->data.to_screen.FlattenTo2d();
 362     node->data.to_screen.PreconcatTransform(node->data.to_parent);
 363     node->data.ancestors_are_invertible =
 364         parent_node->data.ancestors_are_invertible;
 365     node->data.node_and_ancestors_are_flat =
 366         parent_node->data.node_and_ancestors_are_flat &&
 367         node->data.to_parent.IsFlat();
 368   }
 369
 370   if (!node->data.to_screen.GetInverse(&node->data.from_screen))
 371     node->data.ancestors_are_invertible = false;
 372 }
 373
 374 void TransformTree::UpdateSublayerScale(TransformNode* node) {
 375   // The sublayer scale depends on the screen space transform, so update it too.
 376   node->data.sublayer_scale =
 377       node->data.needs_sublayer_scale
 378           ? MathUtil::ComputeTransform2dScaleComponents(
 379                 node->data.to_screen, node->data.layer_scale_factor)
 380           : gfx::Vector2dF(1.0f, 1.0f);
 381 }
 382
 383 void TransformTree::UpdateTargetSpaceTransform(TransformNode* node,
 384                                                TransformNode* target_node) {
 385   if (node->data.needs_sublayer_scale) {
 386     node->data.to_target.MakeIdentity();
 387     node->data.to_target.Scale(node->data.sublayer_scale.x(),
 388                                node->data.sublayer_scale.y());
 389   } else {
 390     const bool target_is_root_surface = target_node->id == 1;
 391     // In order to include the root transform for the root surface, we walk up
 392     // to the root of the transform tree in ComputeTransform.
 393     int target_id = target_is_root_surface ? 0 : target_node->id;
 394     ComputeTransformWithDestinationSublayerScale(node->id, target_id,
 395                                                  &node->data.to_target);
 396   }
 397
 398   if (!node->data.to_target.GetInverse(&node->data.from_target))
 399     node->data.ancestors_are_invertible = false;
 400 }
 401
 402 void TransformTree::UpdateIsAnimated(TransformNode* node,
 403                                      TransformNode* parent_node) {
 404   if (parent_node) {
 405     node->data.to_screen_is_animated =
 406         node->data.is_animated || parent_node->data.to_screen_is_animated;
 407   }
 408 }
 409
 410 void TransformTree::UpdateSnapping(TransformNode* node) {
 411   if (!node->data.scrolls || node->data.to_screen_is_animated ||
 412       !node->data.to_target.IsScaleOrTranslation()) {
 413     return;
 414   }
 415
 416   // Scroll snapping must be done in target space (the pixels we care about).
 417   // This means we effectively snap the target space transform. If TT is the
 418   // target space transform and TT' is TT with its translation components
 419   // rounded, then what we're after is the scroll delta X, where TT * X = TT'.
 420   // I.e., we want a transform that will realize our scroll snap. It follows
 421   // that X = TT^-1 * TT'. We cache TT and TT^-1 to make this more efficient.
 422   gfx::Transform rounded = node->data.to_target;
 423   rounded.RoundTranslationComponents();
 424   gfx::Transform delta = node->data.from_target;
 425   delta *= rounded;
 426
 427   DCHECK(delta.IsApproximatelyIdentityOrTranslation(SkDoubleToMScalar(1e-4)))
 428       << delta.ToString();
 429
 430   gfx::Vector2dF translation = delta.To2dTranslation();
 431
 432   // Now that we have our scroll delta, we must apply it to each of our
 433   // combined, to/from matrices.
 434   node->data.to_parent.Translate(translation.x(), translation.y());
 435   node->data.to_target.Translate(translation.x(), translation.y());
 436   node->data.from_target.matrix().postTranslate(-translation.x(),
 437                                                 -translation.y(), 0);
 438   node->data.to_screen.Translate(translation.x(), translation.y());
 439   node->data.from_screen.matrix().postTranslate(-translation.x(),
 440                                                 -translation.y(), 0);
 441
 442   node->data.scroll_snap = translation;
 443 }
 444
 445 void TransformTree::SetInnerViewportBoundsDelta(gfx::Vector2dF bounds_delta) {
 446   if (inner_viewport_bounds_delta_ == bounds_delta)
 447     return;
 448
 449   inner_viewport_bounds_delta_ = bounds_delta;
 450
 451   if (nodes_affected_by_inner_viewport_bounds_delta_.empty())
 452     return;
 453
 454   set_needs_update(true);
 455   for (int i : nodes_affected_by_inner_viewport_bounds_delta_)
 456     Node(i)->data.needs_local_transform_update = true;
 457 }
 458
 459 void TransformTree::SetOuterViewportBoundsDelta(gfx::Vector2dF bounds_delta) {
 460   if (outer_viewport_bounds_delta_ == bounds_delta)
 461     return;
 462
 463   outer_viewport_bounds_delta_ = bounds_delta;
 464
 465   if (nodes_affected_by_outer_viewport_bounds_delta_.empty())
 466     return;
 467
 468   set_needs_update(true);
 469   for (int i : nodes_affected_by_outer_viewport_bounds_delta_)
 470     Node(i)->data.needs_local_transform_update = true;
 471 }
 472
 473 void TransformTree::AddNodeAffectedByInnerViewportBoundsDelta(int node_id) {
 474   nodes_affected_by_inner_viewport_bounds_delta_.push_back(node_id);
 475 }
 476
 477 void TransformTree::AddNodeAffectedByOuterViewportBoundsDelta(int node_id) {
 478   nodes_affected_by_outer_viewport_bounds_delta_.push_back(node_id);
 479 }
 480
 481 bool TransformTree::HasNodesAffectedByInnerViewportBoundsDelta() const {
 482   return !nodes_affected_by_inner_viewport_bounds_delta_.empty();
 483 }
 484
 485 bool TransformTree::HasNodesAffectedByOuterViewportBoundsDelta() const {
 486   return !nodes_affected_by_outer_viewport_bounds_delta_.empty();
 487 }
 488
 489 void OpacityTree::UpdateOpacities(int id) {
 490   OpacityNode* node = Node(id);
 491   node->data.screen_space_opacity = node->data.opacity;
 492
 493   OpacityNode* parent_node = parent(node);
 494   if (parent_node)
 495     node->data.screen_space_opacity *= parent_node->data.screen_space_opacity;
 496 }
 497
 498 void TransformTree::UpdateNodeAndAncestorsHaveIntegerTranslations(
 499     TransformNode* node,
 500     TransformNode* parent_node) {
 501   node->data.node_and_ancestors_have_only_integer_translation =
 502       node->data.to_parent.IsIdentityOrIntegerTranslation();
 503   if (parent_node)
 504     node->data.node_and_ancestors_have_only_integer_translation =
 505         node->data.node_and_ancestors_have_only_integer_translation &&
 506         parent_node->data.node_and_ancestors_have_only_integer_translation;
 507 }
 508
 509 PropertyTrees::PropertyTrees() : needs_rebuild(true), sequence_number(0) {
 510 }
 511
 512 }  // namespace cc