Introduce Property Trees

cc/trees/property_tree_builder.cc

Index: cc/trees/property_tree_builder.cc
diff --git a/cc/trees/property_tree_builder.cc b/cc/trees/property_tree_builder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b1517063bdf973346fc6be331b39656a7d02003e
--- /dev/null
+++ b/cc/trees/property_tree_builder.cc
@@ -0,0 +1,306 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "cc/trees/property_tree_builder.h"
+
+#include <map>
+#include <set>
+
+#include "cc/base/math_util.h"
+#include "cc/layers/layer.h"
+#include "cc/trees/layer_tree_host.h"
+#include "ui/gfx/point_f.h"
+
+namespace cc {
+
+class LayerTreeHost;
+
+namespace {
+
+struct DataForRecursion {
+  TransformTree* transform_tree;
+  ClipTree* clip_tree;
+  Layer* transform_tree_parent;
+  Layer* transform_fixed_parent;
+  Layer* render_target;
+  int clip_tree_parent;
+  gfx::Vector2dF offset_to_transform_tree_parent;
+  gfx::Vector2dF offset_to_transform_fixed_parent;
+  const Layer* page_scale_layer;
+  float page_scale_factor;
+  float device_scale_factor;
+};
+
+static Layer* GetTransformParent(const DataForRecursion& data, Layer* layer) {
+  return layer->position_constraint().is_fixed_position()
+             ? data.transform_fixed_parent
+             : data.transform_tree_parent;
+}
+
+static ClipNode* GetClipParent(const DataForRecursion& data, Layer* layer) {
+  const bool inherits_clip = !layer->parent() || !layer->clip_parent();
+  const int id = inherits_clip ? data.clip_tree_parent
+                               : layer->clip_parent()->clip_tree_index();
+  return data.clip_tree->Node(id);
+}
+
+static bool RequiresClipNode(Layer* layer,
+                             bool axis_aligned_with_respect_to_parent) {
+  const bool render_surface_applies_non_axis_aligned_clip =
+      layer->render_surface() && !axis_aligned_with_respect_to_parent &&
+      layer->is_clipped();
+  const bool render_surface_may_grow_due_to_clip_children =
+      layer->render_surface() && layer->num_unclipped_descendants() > 0;
+
+  return !layer->parent() || layer->masks_to_bounds() || layer->mask_layer() ||
+         render_surface_applies_non_axis_aligned_clip ||
+         render_surface_may_grow_due_to_clip_children;
+}
+
+void AddClipNodeIfNeeded(const DataForRecursion& data_from_ancestor,
+                         Layer* layer,
+                         DataForRecursion* data_for_children) {
+  ClipNode* parent = GetClipParent(data_from_ancestor, layer);
+  int parent_id = parent->id;
+
+  const bool axis_aligned_with_respect_to_parent = Are2DAxisAligned(
+      *data_from_ancestor.transform_tree, layer->transform_tree_index(),
+      parent->data.transform_id);
+
+  // TODO(vollick): once Andrew refactors the surface determinations out of

[enne (OOO), 2014/12/10 23:45:59]

What's the status on this work?

[Ian Vollick, 2014/12/12 03:01:47]

Andrew's got a patch up for review. Ball's in Dana's court at the moment.

+  // CDP, the the layer->render_surface() check will be invalid.
+  const bool has_unclipped_surface =
+      layer->render_surface() &&
+      layer->render_surface()->clip_rect().IsEmpty() &&
+      layer->num_unclipped_descendants() == 0;
+
+  if (has_unclipped_surface)
+    parent_id = 0;
+
+  if (!RequiresClipNode(layer, axis_aligned_with_respect_to_parent)) {
+    // Unclipped surfaces reset the clip rect.
+    data_for_children->clip_tree_parent = parent_id;
+  } else if (layer->parent()) {
+    // Note the root clip gets handled elsewhere.
+    Layer* transform_parent = GetTransformParent(*data_for_children, layer);
+    ClipNode node;
+    node.data.clip = gfx::RectF(
+        gfx::PointF() + layer->offset_to_transform_parent(), layer->bounds());
+    node.data.transform_id = transform_parent->transform_tree_index();
+    node.data.target_id =
+        data_from_ancestor.render_target->transform_tree_index();
+
+    data_for_children->clip_tree_parent =
+        data_for_children->clip_tree->Insert(node, parent_id);
+  }
+
+  layer->set_clip_tree_index(
+      has_unclipped_surface ? 0 : data_for_children->clip_tree_parent);
+
+  // TODO(awoloszyn): Right now when we hit a node with a replica, we reset the
+  // clip for all children since we may need to draw. We need to figure out a
+  // better way, since we will need both the clipped and unclipped versions.
+}
+
+void AddTransformNodeIfNeeded(const DataForRecursion& data_from_ancestor,
+                              Layer* layer,
+                              DataForRecursion* data_for_children) {
+  const bool is_root = !layer->parent();
+  const bool is_page_scale_application_layer =
+      layer->parent() && layer->parent() == data_from_ancestor.page_scale_layer;
+  const bool is_scrollable = layer->scrollable();
+  const bool is_fixed = layer->position_constraint().is_fixed_position();
+
+  const bool has_significant_transform =
+      !layer->transform().IsIdentityOr2DTranslation();
+
+  const bool has_animated_transform =
+      layer->layer_animation_controller()->IsAnimatingProperty(
+          Animation::Transform);
+
+  const bool has_transform_origin = layer->transform_origin() != gfx::Point3F();
+
+  const bool has_surface = layer->render_surface();
+
+  const bool flattening_change = layer->parent() &&
+                                 layer->should_flatten_transform() &&
+                                 !layer->parent()->should_flatten_transform();
+
+  bool requires_node = is_root || is_scrollable || is_fixed ||
+                       has_significant_transform || has_animated_transform ||
+                       is_page_scale_application_layer || flattening_change ||
+                       has_transform_origin || has_surface;
+
+  Layer* transform_parent = GetTransformParent(data_from_ancestor, layer);
+
+  // May be non-zero if layer is fixed or has a scroll parent.
+  gfx::Vector2dF parent_offset;
+  if (transform_parent) {
+    // TODO(vollick): This is to mimic bugs in current CDP. Need to log a bug

[enne (OOO), 2014/12/10 23:45:59]

!!!

[Ian Vollick, 2014/12/12 03:01:47]

Yeah :( I've logged the bug and referenced it in this comment.

+    // about this and reference it here.
+    if (!is_fixed)
+      parent_offset = transform_parent->offset_to_transform_parent();
+
+    gfx::Transform to_parent;
+    Layer* source = data_from_ancestor.transform_tree_parent;
+    if (layer->scroll_parent()) {
+      source = layer->parent();
+      parent_offset += layer->parent()->offset_to_transform_parent();
+    }
+
+    ComputeTransform(*data_from_ancestor.transform_tree,
+                     source->transform_tree_index(),
+                     transform_parent->transform_tree_index(), &to_parent);
+
+    parent_offset += to_parent.To2dTranslation();
+  }
+
+  if (layer->IsContainerForFixedPositionLayers() || is_root)
+    data_for_children->transform_fixed_parent = layer;
+  data_for_children->transform_tree_parent = layer;
+
+  if (!requires_node) {
+    gfx::Vector2dF local_offset = layer->position().OffsetFromOrigin() +
+                                  layer->transform().To2dTranslation();
+    layer->set_offset_to_transform_parent(parent_offset + local_offset);
+    layer->set_transform_tree_index(transform_parent->transform_tree_index());
+    return;
+  }
+
+  if (!is_root) {
+    data_for_children->transform_tree->Insert(
+        TransformNode(), transform_parent->transform_tree_index());
+  }
+
+  TransformNode* node = data_for_children->transform_tree->back();
+
+  node->data.flattens = layer->should_flatten_transform();
+  node->data.target_id =
+      data_from_ancestor.render_target->transform_tree_index();
+
+  gfx::Transform transform;
+  float device_and_page_scale_factors = 1.0f;
+  if (is_root)
+    device_and_page_scale_factors = data_from_ancestor.device_scale_factor;
+  if (is_page_scale_application_layer)
+    device_and_page_scale_factors *= data_from_ancestor.page_scale_factor;
+
+  transform.Scale(device_and_page_scale_factors, device_and_page_scale_factors);
+
+  // NB: We've accounted for the scroll offset here but we haven't taken into
+  // account snapping to screen space pixels (since we haven't computed any
+  // screen space transforms). For the purposes of computing rects we need to
+  // record, this should be fine (the visible rects we compute may be slightly
+  // different than what we'd compute with snapping, but since we significantly
+  // expand the visible rect when determining what to record, the slight
+  // difference should be inconsequential).
+  gfx::Vector2dF position = layer->position().OffsetFromOrigin();
+  if (!layer->scroll_parent()) {
+    position -= gfx::Vector2dF(layer->TotalScrollOffset().x(),
+        layer->TotalScrollOffset().y());
+  }
+
+  position += parent_offset;
+
+  transform.Translate3d(position.x() + layer->transform_origin().x(),
+                        position.y() + layer->transform_origin().y(),
+                        layer->transform_origin().z());
+  transform.PreconcatTransform(layer->transform());
+  transform.Translate3d(-layer->transform_origin().x(),
+                        -layer->transform_origin().y(),
+                        -layer->transform_origin().z());
+
+  node->data.to_parent = transform;
+  node->data.is_invertible = transform.GetInverse(&node->data.from_parent);
+
+  UpdateScreenSpaceTransform(data_from_ancestor.transform_tree, node->id);
+
+  layer->set_offset_to_transform_parent(gfx::Vector2dF());
+  layer->set_transform_tree_index(node->id);
+}
+
+void BuildPropertyTreesInternal(Layer* layer,
+                                const DataForRecursion& data_from_parent) {
+  DataForRecursion data_for_children(data_from_parent);
+  if (layer->render_surface())
+    data_for_children.render_target = layer;
+
+  AddTransformNodeIfNeeded(data_from_parent, layer, &data_for_children);
+  AddClipNodeIfNeeded(data_from_parent, layer, &data_for_children);
+
+  for (size_t i = 0; i < layer->children().size(); ++i) {
+    if (!layer->children()[i]->scroll_parent())
+      BuildPropertyTreesInternal(layer->children()[i].get(), data_for_children);
+  }
+
+  if (layer->scroll_children()) {
+    for (Layer* scroll_child : *layer->scroll_children()) {
+      BuildPropertyTreesInternal(scroll_child, data_for_children);
+    }
+  }
+
+  if (layer->has_replica())
+    BuildPropertyTreesInternal(layer->replica_layer(), data_for_children);
+}
+
+}  // namespace
+
+void PropertyTreeBuilder::BuildPropertyTrees(
+    Layer* root_layer,
+    const Layer* page_scale_layer,
+    float page_scale_factor,
+    float device_scale_factor,
+    const gfx::Rect& viewport,
+    const gfx::Transform& device_transform,
+    TransformTree* transform_tree,
+    ClipTree* clip_tree) {
+  DataForRecursion data_for_recursion;
+  data_for_recursion.transform_tree = transform_tree;
+  data_for_recursion.clip_tree = clip_tree;
+  data_for_recursion.transform_tree_parent = nullptr;
+  data_for_recursion.transform_fixed_parent = nullptr;
+  data_for_recursion.render_target = root_layer;
+  data_for_recursion.clip_tree_parent = 0;
+  data_for_recursion.page_scale_layer = page_scale_layer;
+  data_for_recursion.page_scale_factor = page_scale_factor;
+  data_for_recursion.device_scale_factor = device_scale_factor;
+
+  int transform_root_id = 0;
+  int clip_root_id = 0;
+
+  // We only need to clip the root if we have a non-empty viewport. The root of

[enne (OOO), 2014/12/10 23:46:00]

When is the viewport empty?

[Ian Vollick, 2014/12/12 03:01:47]

This happens in unit tests and the assumption there is that we don't clip
anything.

[enne (OOO), 2014/12/12 19:05:49]

Can you leave a comment saying that empty viewport = no clipping, and only for
unit tests?  (I suppose we could also fix that too?)

[Ian Vollick, 2014/12/15 21:45:17]

This is now unnecessary due to hush's patch. Removed.

+  // the clip tree does not clip, so we need to add another node in this case.
+  if (!viewport.IsEmpty()) {
+    data_for_recursion.clip_tree_parent = clip_tree->Insert(ClipNode(), 0);
+    clip_root_id = data_for_recursion.clip_tree_parent;
+  }
+
+  BuildPropertyTreesInternal(root_layer, data_for_recursion);
+
+  TransformNode* transform_root = transform_tree->Node(transform_root_id);
+  ClipNode* clip_root = clip_tree->Node(clip_root_id);
+
+  gfx::Transform combined_transform =
+      device_transform * transform_root->data.to_parent;

[enne (OOO), 2014/12/10 23:45:59]

Is this ever not identity? Doesn't the transform root not have a parent?

[Ian Vollick, 2014/12/12 03:01:47]

The dsf (and device transform) are applied to the root transform. The to_parent
here can include the dsf.

[Ian Vollick, 2014/12/15 21:45:17]

I've added an extra "super root" to the transform tree that's always the
identity. This gets rid of this confusion, I think?

+
+  transform_root->data.set_to_parent(combined_transform);
+  gfx::RectF transformed_viewport = viewport;
+
+  if (!combined_transform.IsIdentity()) {
+    gfx::Transform inverse_transform;
+    if (!combined_transform.GetInverse(&inverse_transform)) {
+      // If we have an univertible transform, then we clip off the entire
+      // subtree.
+      transformed_viewport = gfx::RectF();
+    } else {
+      transformed_viewport =
+          MathUtil::ProjectClippedRect(inverse_transform, viewport);
+    }
+  }
+
+  clip_root->data.clip = transformed_viewport;

[enne (OOO), 2014/12/10 23:46:00]

Why do you need to inverse transform the viewport to get the clip rect?

[Ian Vollick, 2014/12/12 03:01:47]

To get to screen space (where this clip is applied), you use
ComputeTransform(src, -1). That is, it does include the transform of node 0.
This projection ensures that the clip is correct in screen space.

[enne (OOO), 2014/12/12 19:05:49]

Hmm.  Maybe I just figured that this function would just take the device
viewport and set it directly at the top.

[Ian Vollick, 2014/12/15 21:45:17]

Now that we have the super root, we don't need to transform the clip. It's
stored in that space.

+  clip_root->data.transform_id = transform_root->id;
+}
+
+}  // namespace cc