Introduce Property Trees

cc/trees/property_tree.cc

Index: cc/trees/property_tree.cc
diff --git a/cc/trees/property_tree.cc b/cc/trees/property_tree.cc
new file mode 100644
index 0000000000000000000000000000000000000000..e43c7c298323cfbc8f68aa08523225ff712250c9
--- /dev/null
+++ b/cc/trees/property_tree.cc
@@ -0,0 +1,187 @@
+// 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 <set>
+
+#include "base/logging.h"
+#include "cc/trees/property_tree.h"
+
+namespace cc {
+
+template <typename T>
+PropertyTree<T>::PropertyTree() {
+  nodes_.push_back(T());
+  back()->id = 0;
+  back()->parent_id = -1;
+}
+
+template <typename T>
+PropertyTree<T>::~PropertyTree() {
+}
+
+template <typename T>
+int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
+  DCHECK_GT(nodes_.size(), 0u);
+  nodes_.push_back(tree_node);
+  T& node = nodes_.back();
+  node.parent_id = parent_id;
+  node.id = static_cast<int>(nodes_.size()) - 1;
+  return node.id;
+}
+
+template class PropertyTree<TransformNode>;
+template class PropertyTree<ClipNode>;
+
+TransformNodeData::TransformNodeData()
+    : target_id(-1),
+      is_invertible(true),
+      ancestors_are_invertible(true),
+      flattens(false) {
+}
+
+TransformNodeData::~TransformNodeData() {
+}
+
+ClipNodeData::ClipNodeData() : transform_id(-1), target_id(-1) {
+}
+
+bool IsDescendant(const TransformTree& tree, int desc_id, int source_id) {
+  while (desc_id != source_id) {
+    if (desc_id < 0)
+      return false;
+    desc_id = tree.Node(desc_id)->parent_id;
+  }
+  return true;
+}
+
+int LowestCommonAncestor(const TransformTree& tree, int a, int b) {
+  std::set<int> chain_a;
+  std::set<int> chain_b;
+  while (a || b) {
+    if (a) {
+      a = tree.Node(a)->parent_id;
+      if (a > -1 && chain_b.find(a) != chain_b.end())
+        return a;
+      chain_a.insert(a);
+    }
+    if (b) {
+      b = tree.Node(b)->parent_id;
+      if (b > -1 && chain_a.find(b) != chain_a.end())
+        return b;
+      chain_b.insert(b);
+    }
+  }
+  NOTREACHED();
+  return 0;
+}
+
+bool CombineTransformsBetween(const TransformTree& tree,
+                              int source_id,
+                              int dest_id,
+                              gfx::Transform* transform) {
+  const TransformNode* current = tree.Node(source_id);
+  const TransformNode* dest = tree.Node(dest_id);
+  if (!dest || dest->data.ancestors_are_invertible) {
+    transform->ConcatTransform(current->data.to_screen);
+    if (dest)
+      transform->ConcatTransform(dest->data.from_screen);
+    return true;
+  }
+
+  bool all_are_invertible = true;
+  for (; current && current->id > dest_id; current = tree.parent(current)) {
+    transform->ConcatTransform(current->data.to_parent);
+    if (!current->data.is_invertible)
+      all_are_invertible = false;
+  }
+
+  return all_are_invertible;
+}
+
+bool CombineInversesBetween(const TransformTree& tree,
+                            int source_id,
+                            int dest_id,
+                            gfx::Transform* transform) {
+  const TransformNode* current = tree.Node(dest_id);
+  const TransformNode* dest = tree.Node(source_id);
+  if (current->data.ancestors_are_invertible) {
+    transform->PreconcatTransform(current->data.from_screen);
+    if (dest)
+      transform->PreconcatTransform(dest->data.to_screen);
+    return true;
+  }
+
+  bool all_are_invertible = true;
+  for (; current && current->id > source_id; current = tree.parent(current)) {
+    transform->PreconcatTransform(current->data.from_parent);
+    if (!current->data.is_invertible)
+      all_are_invertible = false;
+  }
+
+  return all_are_invertible;
+}
+
+bool ComputeTransform(const TransformTree& tree,

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

This probably needs a note that transform should be initialized to identity? Or,
maybe it'd be safer to initialize to identity in that first case and not
initialize the transform that you pass in here?

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

I actually take advantage of the fact that it doesn't reset to identity to tack
on some scales and transforms before making this call. Check out lth.cc and
Layer::draw_transform_from_property_trees. wdyt, too ugly?

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

It still looks to me like you're just passing identity ssxform into
ComputeTransform in that function.  Am I missing something?

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

Sorry, I pointed you at the wrong function. But in any case, I've taken your
suggestion and done a MakeIdentity.

+                      int source_id,
+                      int dest_id,
+                      gfx::Transform* transform) {
+  if (source_id == dest_id)
+    return true;
+
+  if (source_id > dest_id && IsDescendant(tree, source_id, dest_id))
+    return CombineTransformsBetween(tree, source_id, dest_id, transform);
+
+  if (dest_id > source_id && IsDescendant(tree, dest_id, source_id))
+    return CombineInversesBetween(tree, source_id, dest_id, transform);
+
+  int lca = LowestCommonAncestor(tree, source_id, dest_id);
+
+  bool no_singular_matrices_to_lca =
+      CombineTransformsBetween(tree, source_id, lca, transform);
+
+  bool no_singular_matrices_from_lca =
+      CombineInversesBetween(tree, lca, dest_id, transform);
+
+  return no_singular_matrices_to_lca && no_singular_matrices_from_lca;
+}
+
+bool Are2DAxisAligned(const TransformTree& tree, int source_id, int dest_id) {
+  gfx::Transform transform;
+  return ComputeTransform(tree, source_id, dest_id, &transform) &&
+         transform.Preserves2dAxisAlignment();
+}
+
+void UpdateScreenSpaceTransform(TransformTree* tree, int id) {
+  TransformNode* node = tree->Node(id);
+  TransformNode* parent = tree->parent(node);
+  TransformNode* target = tree->Node(node->data.target_id);
+
+  if (!parent) {
+    node->data.to_screen = node->data.to_parent;
+    node->data.ancestors_are_invertible = true;
+  } else if (parent->data.flattens) {
+    // Flattening is tricky. Once a layer is drawn into its render target, it
+    // cannot escape, so we only need to consider transforms between the layer
+    // and its target when flattening (i.e., its draw transform). To compute the
+    // screen space transform when flattening is involved we combine three
+    // transforms, A * B * C, where A is the screen space transform of the
+    // target, B is the flattened draw transform of the layer's parent, and C is
+    // the local transform.
+    node->data.to_screen = target->data.to_screen;
+    gfx::Transform flattened;
+    ComputeTransform(*tree, parent->id, target->id, &flattened);
+    flattened.FlattenTo2d();
+    node->data.to_screen.PreconcatTransform(flattened);
+    node->data.to_screen.PreconcatTransform(node->data.to_parent);
+    node->data.ancestors_are_invertible = parent->data.ancestors_are_invertible;
+  } else {
+    node->data.to_screen = parent->data.to_screen;
+    node->data.to_screen.PreconcatTransform(node->data.to_parent);
+    node->data.ancestors_are_invertible = parent->data.ancestors_are_invertible;
+  }
+  if (!node->data.to_screen.GetInverse(&node->data.from_screen))
+    node->data.ancestors_are_invertible = false;
+}
+
+}  // namespace cc