Introduce Property Trees
Based of Andrew's work: crrev.com/642833002
This patch creates a transform and a clip tree and computes
visual content rects based on those.
BUG=386786
Review URL: https://codereview.chromium.org/687873004
Cr-Commit-Position: refs/heads/master@{#308724}
diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 9f3437c..47dcb6dc9 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -475,6 +475,8 @@
"trees/blocking_task_runner.h",
"trees/damage_tracker.cc",
"trees/damage_tracker.h",
+ "trees/draw_property_utils.cc",
+ "trees/draw_property_utils.h",
"trees/layer_sorter.cc",
"trees/layer_sorter.h",
"trees/layer_tree_host.cc",
@@ -492,6 +494,10 @@
"trees/occlusion.h",
"trees/occlusion_tracker.cc",
"trees/occlusion_tracker.h",
+ "trees/property_tree.cc",
+ "trees/property_tree.h",
+ "trees/property_tree_builder.cc",
+ "trees/property_tree_builder.h",
"trees/proxy.cc",
"trees/proxy.h",
"trees/proxy_timing_history.cc",
@@ -815,6 +821,7 @@
"trees/layer_tree_impl_unittest.cc",
"trees/occlusion_tracker_unittest.cc",
"trees/occlusion_unittest.cc",
+ "trees/property_tree_unittest.cc",
"trees/tree_synchronizer_unittest.cc",
# Surfaces test files.
diff --git a/cc/cc.gyp b/cc/cc.gyp
index 43e4b20..62655d7 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -504,6 +504,8 @@
'trees/blocking_task_runner.h',
'trees/damage_tracker.cc',
'trees/damage_tracker.h',
+ 'trees/draw_property_utils.cc',
+ 'trees/draw_property_utils.h',
'trees/layer_sorter.cc',
'trees/layer_sorter.h',
'trees/layer_tree_host.cc',
@@ -521,6 +523,10 @@
'trees/occlusion.h',
'trees/occlusion_tracker.cc',
'trees/occlusion_tracker.h',
+ 'trees/property_tree.cc',
+ 'trees/property_tree.h',
+ 'trees/property_tree_builder.cc',
+ 'trees/property_tree_builder.h',
'trees/proxy.cc',
'trees/proxy.h',
'trees/proxy_timing_history.cc',
diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 0eecc3d..181af37d 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -125,6 +125,7 @@
'trees/layer_tree_impl_unittest.cc',
'trees/occlusion_tracker_unittest.cc',
'trees/occlusion_unittest.cc',
+ 'trees/property_tree_unittest.cc',
'trees/tree_synchronizer_unittest.cc',
],
'cc_surfaces_unit_tests_source_files': [
diff --git a/cc/layers/layer.cc b/cc/layers/layer.cc
index 08f39b9..7c0341b 100644
--- a/cc/layers/layer.cc
+++ b/cc/layers/layer.cc
@@ -49,6 +49,9 @@
layer_tree_host_(nullptr),
scroll_clip_layer_id_(INVALID_ID),
num_descendants_that_draw_content_(0),
+ transform_tree_index_(-1),
+ opacity_tree_index_(-1),
+ clip_tree_index_(-1),
should_scroll_on_main_thread_(false),
have_wheel_event_handlers_(false),
have_scroll_event_handlers_(false),
@@ -67,6 +70,7 @@
draw_checkerboard_for_missing_tiles_(false),
force_render_surface_(false),
transform_is_invertible_(true),
+ has_render_surface_(false),
background_color_(0),
opacity_(1.f),
blend_mode_(SkXfermode::kSrcOver_Mode),
@@ -1241,4 +1245,30 @@
return false;
}
+gfx::Transform Layer::screen_space_transform_from_property_trees(
+ const TransformTree& tree) const {
+ gfx::Transform xform(1, 0, 0, 1, offset_to_transform_parent().x(),
+ offset_to_transform_parent().y());
+ if (transform_tree_index() >= 0) {
+ gfx::Transform ssxform = tree.Node(transform_tree_index())->data.to_screen;
+ xform.ConcatTransform(ssxform);
+ }
+ xform.Scale(1.0 / contents_scale_x(), 1.0 / contents_scale_y());
+ return xform;
+}
+
+gfx::Transform Layer::draw_transform_from_property_trees(
+ const TransformTree& tree) const {
+ gfx::Transform xform(1, 0, 0, 1, offset_to_transform_parent().x(),
+ offset_to_transform_parent().y());
+ if (transform_tree_index() >= 0) {
+ const TransformNode* node = tree.Node(transform_tree_index());
+ gfx::Transform ssxform;
+ tree.ComputeTransform(node->id, node->data.target_id, &ssxform);
+ xform.ConcatTransform(ssxform);
+ }
+ xform.Scale(1.0 / contents_scale_x(), 1.0 / contents_scale_y());
+ return xform;
+}
+
} // namespace cc
diff --git a/cc/layers/layer.h b/cc/layers/layer.h
index f372186..7714315 100644
--- a/cc/layers/layer.h
+++ b/cc/layers/layer.h
@@ -24,6 +24,7 @@
#include "cc/layers/paint_properties.h"
#include "cc/layers/render_surface.h"
#include "cc/output/filter_operations.h"
+#include "cc/trees/property_tree.h"
#include "skia/ext/refptr.h"
#include "third_party/skia/include/core/SkColor.h"
#include "third_party/skia/include/core/SkImageFilter.h"
@@ -180,7 +181,7 @@
bool transform_is_invertible() const { return transform_is_invertible_; }
void SetTransformOrigin(const gfx::Point3F&);
- gfx::Point3F transform_origin() { return transform_origin_; }
+ gfx::Point3F transform_origin() const { return transform_origin_; }
void SetScrollParent(Layer* parent);
@@ -462,6 +463,50 @@
void Set3dSortingContextId(int id);
int sorting_context_id() const { return sorting_context_id_; }
+ void set_transform_tree_index(int index) { transform_tree_index_ = index; }
+ void set_clip_tree_index(int index) { clip_tree_index_ = index; }
+ int clip_tree_index() const { return clip_tree_index_; }
+ int transform_tree_index() const { return transform_tree_index_; }
+
+ void set_offset_to_transform_parent(gfx::Vector2dF offset) {
+ offset_to_transform_parent_ = offset;
+ }
+ gfx::Vector2dF offset_to_transform_parent() const {
+ return offset_to_transform_parent_;
+ }
+
+ // TODO(vollick): Once we transition to transform and clip trees, rename these
+ // functions and related values. The "from property trees" functions below
+ // use the transform and clip trees. Eventually, we will use these functions
+ // to compute the official values, but these functions are retained for
+ // testing purposes until we've migrated.
+
+ const gfx::Rect& visible_rect_from_property_trees() const {
+ return visible_rect_from_property_trees_;
+ }
+ void set_visible_rect_from_property_trees(const gfx::Rect& rect) {
+ visible_rect_from_property_trees_ = rect;
+ }
+
+ gfx::Transform screen_space_transform_from_property_trees(
+ const TransformTree& tree) const;
+ gfx::Transform draw_transform_from_property_trees(
+ const TransformTree& tree) const;
+
+ // TODO(vollick): These values are temporary and will be removed as soon as
+ // render surface determinations are moved out of CDP. They only exist because
+ // certain logic depends on whether or not a layer would render to a separate
+ // surface, but CDP destroys surfaces and targets it doesn't need, so without
+ // this boolean, this is impossible to determine after the fact without
+ // wastefully recomputing it. This is public for the time being so that it can
+ // be accessed from CDP.
+ bool has_render_surface() const {
+ return has_render_surface_;
+ }
+ void SetHasRenderSurface(bool has_render_surface) {
+ has_render_surface_ = has_render_surface;
+ }
+
protected:
friend class LayerImpl;
friend class TreeSynchronizer;
@@ -589,6 +634,10 @@
// this layer.
int scroll_clip_layer_id_;
int num_descendants_that_draw_content_;
+ int transform_tree_index_;
+ int opacity_tree_index_;
+ int clip_tree_index_;
+ gfx::Vector2dF offset_to_transform_parent_;
bool should_scroll_on_main_thread_ : 1;
bool have_wheel_event_handlers_ : 1;
bool have_scroll_event_handlers_ : 1;
@@ -607,6 +656,7 @@
bool draw_checkerboard_for_missing_tiles_ : 1;
bool force_render_surface_ : 1;
bool transform_is_invertible_ : 1;
+ bool has_render_surface_ : 1;
Region non_fast_scrollable_region_;
Region touch_event_handler_region_;
gfx::PointF position_;
@@ -641,6 +691,7 @@
PaintProperties paint_properties_;
+ gfx::Rect visible_rect_from_property_trees_;
DISALLOW_COPY_AND_ASSIGN(Layer);
};
diff --git a/cc/layers/layer_impl.h b/cc/layers/layer_impl.h
index 12f1dca..4fae166 100644
--- a/cc/layers/layer_impl.h
+++ b/cc/layers/layer_impl.h
@@ -567,6 +567,14 @@
void Set3dSortingContextId(int id);
int sorting_context_id() { return sorting_context_id_; }
+ // TODO(vollick): These is temporary and will be removed as soon as render
+ // surface determinations are moved out of CDP. They only exist because
+ // certain logic depends on whether or not a layer would render to a separate
+ // surface, but CDP destroys surfaces and targets it doesn't need, so without
+ // this boolean, this is impossible to determine after the fact without
+ // wastefully recomputing it.
+ void SetHasRenderSurface(bool value) {}
+
protected:
LayerImpl(LayerTreeImpl* layer_impl, int id);
diff --git a/cc/layers/tiled_layer_unittest.cc b/cc/layers/tiled_layer_unittest.cc
index b4ee30f0..4b9430d 100644
--- a/cc/layers/tiled_layer_unittest.cc
+++ b/cc/layers/tiled_layer_unittest.cc
@@ -86,6 +86,7 @@
occlusion_(nullptr) {
settings_.max_partial_texture_updates = std::numeric_limits<size_t>::max();
settings_.layer_transforms_should_scale_layer_contents = true;
+ settings_.verify_property_trees = true;
}
void SetUp() override {
diff --git a/cc/test/fake_layer_tree_host.cc b/cc/test/fake_layer_tree_host.cc
index c0c6916c..fe0351d 100644
--- a/cc/test/fake_layer_tree_host.cc
+++ b/cc/test/fake_layer_tree_host.cc
@@ -17,6 +17,7 @@
scoped_ptr<FakeLayerTreeHost> FakeLayerTreeHost::Create(
FakeLayerTreeHostClient* client) {
LayerTreeSettings settings;
+ settings.verify_property_trees = true;
return make_scoped_ptr(new FakeLayerTreeHost(client, settings));
}
diff --git a/cc/test/layer_tree_test.cc b/cc/test/layer_tree_test.cc
index 15a509f3..0613f85 100644
--- a/cc/test/layer_tree_test.cc
+++ b/cc/test/layer_tree_test.cc
@@ -709,6 +709,7 @@
settings_.renderer_settings.refresh_rate = 200.0;
settings_.background_animation_rate = 200.0;
settings_.impl_side_painting = impl_side_painting;
+ settings_.verify_property_trees = true;
InitializeSettings(&settings_);
main_task_runner_->PostTask(
diff --git a/cc/trees/draw_property_utils.cc b/cc/trees/draw_property_utils.cc
new file mode 100644
index 0000000..cd69f92
--- /dev/null
+++ b/cc/trees/draw_property_utils.cc
@@ -0,0 +1,280 @@
+// 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/draw_property_utils.h"
+
+#include <vector>
+
+#include "cc/base/math_util.h"
+#include "cc/layers/layer.h"
+#include "cc/trees/property_tree.h"
+#include "cc/trees/property_tree_builder.h"
+#include "ui/gfx/geometry/rect_conversions.h"
+
+namespace cc {
+
+namespace {
+
+void CalculateVisibleRects(
+ const std::vector<Layer*>& layers_that_need_visible_rects,
+ const ClipTree& clip_tree,
+ const TransformTree& transform_tree) {
+ for (size_t i = 0; i < layers_that_need_visible_rects.size(); ++i) {
+ Layer* layer = layers_that_need_visible_rects[i];
+
+ // TODO(ajuma): Compute content_scale rather than using it. Note that for
+ // PictureLayer and PictureImageLayers, content_bounds == bounds and
+ // content_scale_x == content_scale_y == 1.0, so once impl painting is on
+ // everywhere, this code will be unnecessary.
+ gfx::Size layer_content_bounds = layer->content_bounds();
+ float contents_scale_x = layer->contents_scale_x();
+ float contents_scale_y = layer->contents_scale_y();
+ const bool has_clip = layer->clip_tree_index() > 0;
+ const TransformNode* transform_node =
+ transform_tree.Node(layer->transform_tree_index());
+ if (has_clip) {
+ const ClipNode* clip_node = clip_tree.Node(layer->clip_tree_index());
+ const TransformNode* clip_transform_node =
+ transform_tree.Node(clip_node->data.transform_id);
+ const TransformNode* target_node =
+ transform_tree.Node(layer->render_target()->transform_tree_index());
+
+ gfx::Transform clip_to_target;
+ gfx::Transform content_to_target;
+ gfx::Transform target_to_content;
+ gfx::Transform target_to_layer;
+
+ bool success =
+ transform_tree.ComputeTransform(clip_transform_node->id,
+ target_node->id, &clip_to_target) &&
+ transform_tree.ComputeTransform(transform_node->id, target_node->id,
+ &content_to_target) &&
+ transform_tree.ComputeTransform(target_node->id, transform_node->id,
+ &target_to_layer);
+
+ // This should only fail if we somehow got here with a singular ancestor.
+ DCHECK(success);
+
+ target_to_content.Scale(contents_scale_x, contents_scale_y);
+ target_to_content.Translate(-layer->offset_to_transform_parent().x(),
+ -layer->offset_to_transform_parent().y());
+ target_to_content.PreconcatTransform(target_to_layer);
+
+ content_to_target.Translate(layer->offset_to_transform_parent().x(),
+ layer->offset_to_transform_parent().y());
+ content_to_target.Scale(1.0 / contents_scale_x, 1.0 / contents_scale_y);
+
+ gfx::Rect layer_content_rect = gfx::Rect(layer_content_bounds);
+ gfx::RectF layer_content_bounds_in_target_space =
+ MathUtil::MapClippedRect(content_to_target, layer_content_rect);
+ gfx::RectF clip_rect_in_target_space;
+ if (target_node->id > clip_node->id) {
+ clip_rect_in_target_space = MathUtil::ProjectClippedRect(
+ clip_to_target, clip_node->data.combined_clip);
+ } else {
+ clip_rect_in_target_space = MathUtil::MapClippedRect(
+ clip_to_target, clip_node->data.combined_clip);
+ }
+
+ clip_rect_in_target_space.Intersect(layer_content_bounds_in_target_space);
+
+ gfx::Rect visible_rect =
+ gfx::ToEnclosingRect(MathUtil::ProjectClippedRect(
+ target_to_content, clip_rect_in_target_space));
+
+ visible_rect.Intersect(gfx::Rect(layer_content_bounds));
+
+ layer->set_visible_rect_from_property_trees(visible_rect);
+ } else {
+ layer->set_visible_rect_from_property_trees(
+ gfx::Rect(layer_content_bounds));
+ }
+ }
+}
+
+static bool IsRootLayerOfNewRenderingContext(Layer* layer) {
+ if (layer->parent())
+ return !layer->parent()->Is3dSorted() && layer->Is3dSorted();
+ return layer->Is3dSorted();
+}
+
+static inline bool LayerIsInExisting3DRenderingContext(Layer* layer) {
+ return layer->Is3dSorted() && layer->parent() &&
+ layer->parent()->Is3dSorted();
+}
+
+static bool TransformToScreenIsKnown(Layer* layer, const TransformTree& tree) {
+ const TransformNode* node = tree.Node(layer->transform_tree_index());
+ return !node->data.to_screen_is_animated;
+}
+
+static bool IsLayerBackFaceExposed(Layer* layer, const TransformTree& tree) {
+ if (!TransformToScreenIsKnown(layer, tree))
+ return false;
+ if (LayerIsInExisting3DRenderingContext(layer))
+ return layer->draw_transform_from_property_trees(tree).IsBackFaceVisible();
+ return layer->transform().IsBackFaceVisible();
+}
+
+static bool IsSurfaceBackFaceExposed(Layer* layer,
+ const TransformTree& tree) {
+ if (!TransformToScreenIsKnown(layer, tree))
+ return false;
+ if (LayerIsInExisting3DRenderingContext(layer))
+ return layer->draw_transform_from_property_trees(tree).IsBackFaceVisible();
+
+ if (IsRootLayerOfNewRenderingContext(layer))
+ return layer->transform().IsBackFaceVisible();
+
+ // If the render_surface is not part of a new or existing rendering context,
+ // then the layers that contribute to this surface will decide back-face
+ // visibility for themselves.
+ return false;
+}
+
+static bool HasSingularTransform(Layer* layer, const TransformTree& tree) {
+ const TransformNode* node = tree.Node(layer->transform_tree_index());
+ return !node->data.is_invertible || !node->data.ancestors_are_invertible;
+}
+
+static bool IsBackFaceInvisible(Layer* layer, const TransformTree& tree) {
+ Layer* backface_test_layer = layer;
+ if (layer->use_parent_backface_visibility()) {
+ DCHECK(layer->parent());
+ DCHECK(!layer->parent()->use_parent_backface_visibility());
+ backface_test_layer = layer->parent();
+ }
+ return !backface_test_layer->double_sided() &&
+ IsLayerBackFaceExposed(backface_test_layer, tree);
+}
+
+static bool IsInvisibleDueToTransform(Layer* layer, const TransformTree& tree) {
+ return HasSingularTransform(layer, tree) || IsBackFaceInvisible(layer, tree);
+}
+
+void FindLayersThatNeedVisibleRects(Layer* layer,
+ const TransformTree& tree,
+ bool subtree_is_visible_from_ancestor,
+ std::vector<Layer*>* layers_to_update) {
+ const bool subtree_is_invisble =
+ layer->opacity() == 0.0f ||
+ (layer->has_render_surface() && !layer->double_sided() &&
+ IsSurfaceBackFaceExposed(layer, tree));
+
+ if (subtree_is_invisble)
+ return;
+
+ bool layer_is_drawn =
+ layer->HasCopyRequest() ||
+ (subtree_is_visible_from_ancestor && !layer->hide_layer_and_subtree());
+
+ if (layer_is_drawn && layer->DrawsContent()) {
+ const bool visible = !IsInvisibleDueToTransform(layer, tree);
+ if (visible)
+ layers_to_update->push_back(layer);
+ }
+
+ for (size_t i = 0; i < layer->children().size(); ++i) {
+ FindLayersThatNeedVisibleRects(layer->children()[i].get(),
+ tree,
+ layer_is_drawn,
+ layers_to_update);
+ }
+}
+
+} // namespace
+
+void ComputeClips(ClipTree* clip_tree, const TransformTree& transform_tree) {
+ for (int i = 0; i < static_cast<int>(clip_tree->size()); ++i) {
+ ClipNode* clip_node = clip_tree->Node(i);
+
+ // Only descendants of a real clipping layer (i.e., not 0) may have their
+ // clip adjusted due to intersecting with an ancestor clip.
+ const bool is_clipped = clip_node->parent_id > 0;
+ if (!is_clipped) {
+ clip_node->data.combined_clip = clip_node->data.clip;
+ continue;
+ }
+
+ ClipNode* parent_clip_node = clip_tree->parent(clip_node);
+ const TransformNode* parent_transform_node =
+ transform_tree.Node(parent_clip_node->data.transform_id);
+ const TransformNode* transform_node =
+ transform_tree.Node(clip_node->data.transform_id);
+
+ // Clips must be combined in target space. We cannot, for example, combine
+ // clips in the space of the child clip. The reason is non-affine
+ // transforms. Say we have the following tree T->A->B->C, and B clips C, but
+ // draw into target T. It may be the case that A applies a perspective
+ // transform, and B and C are at different z positions. When projected into
+ // target space, the relative sizes and positions of B and C can shift.
+ // Since it's the relationship in target space that matters, that's where we
+ // must combine clips.
+ gfx::Transform parent_to_target;
+ gfx::Transform clip_to_target;
+ gfx::Transform target_to_clip;
+
+ bool success =
+ transform_tree.ComputeTransform(parent_transform_node->id,
+ clip_node->data.target_id,
+ &parent_to_target) &&
+ transform_tree.ComputeTransform(
+ transform_node->id, clip_node->data.target_id, &clip_to_target) &&
+ transform_tree.ComputeTransform(clip_node->data.target_id,
+ transform_node->id, &target_to_clip);
+
+ // If we can't compute a transform, it's because we had to use the inverse
+ // of a singular transform. We won't draw in this case, so there's no need
+ // to compute clips.
+ if (!success)
+ continue;
+
+ // In order to intersect with as small a rect as possible, we do a
+ // preliminary clip in target space so that when we project back, there's
+ // less likelihood of intersecting the view plane.
+ gfx::RectF inherited_clip_in_target_space = MathUtil::MapClippedRect(
+ parent_to_target, parent_clip_node->data.combined_clip);
+
+ gfx::RectF clip_in_target_space =
+ MathUtil::MapClippedRect(clip_to_target, clip_node->data.clip);
+
+ gfx::RectF intersected_in_target_space = gfx::IntersectRects(
+ inherited_clip_in_target_space, clip_in_target_space);
+
+ clip_node->data.combined_clip = MathUtil::ProjectClippedRect(
+ target_to_clip, intersected_in_target_space);
+
+ clip_node->data.combined_clip.Intersect(clip_node->data.clip);
+ }
+}
+
+void ComputeTransforms(TransformTree* transform_tree) {
+ for (int i = 0; i < static_cast<int>(transform_tree->size()); ++i)
+ transform_tree->UpdateScreenSpaceTransform(i);
+}
+
+void ComputeVisibleRectsUsingPropertyTrees(
+ 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) {
+ PropertyTreeBuilder::BuildPropertyTrees(
+ root_layer, page_scale_layer, page_scale_factor, device_scale_factor,
+ viewport, device_transform, transform_tree, clip_tree);
+ ComputeTransforms(transform_tree);
+ ComputeClips(clip_tree, *transform_tree);
+
+ std::vector<Layer*> layers_to_update;
+ const bool subtree_is_visible_from_ancestor = true;
+ FindLayersThatNeedVisibleRects(root_layer, *transform_tree,
+ subtree_is_visible_from_ancestor,
+ &layers_to_update);
+ CalculateVisibleRects(layers_to_update, *clip_tree, *transform_tree);
+}
+
+} // namespace cc
diff --git a/cc/trees/draw_property_utils.h b/cc/trees/draw_property_utils.h
new file mode 100644
index 0000000..6da912b1
--- /dev/null
+++ b/cc/trees/draw_property_utils.h
@@ -0,0 +1,47 @@
+// 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.
+
+#ifndef CC_TREES_DRAW_PROPERTY_UTILS_H_
+#define CC_TREES_DRAW_PROPERTY_UTILS_H_
+
+#include "cc/base/cc_export.h"
+
+namespace gfx {
+class Rect;
+class Transform;
+} // namespace gfx
+
+namespace cc {
+
+class ClipTree;
+class Layer;
+class TransformTree;
+
+// Computes combined clips for every node in |clip_tree|. This function requires
+// that |transform_tree| has been updated via |ComputeTransforms|.
+// TODO(vollick): ComputeClips and ComputeTransforms will eventually need to be
+// done on both threads.
+void CC_EXPORT
+ComputeClips(ClipTree* clip_tree, const TransformTree& transform_tree);
+
+// Computes combined (screen space) transforms for every node in the transform
+// tree. This must be done prior to calling |ComputeClips|.
+void CC_EXPORT ComputeTransforms(TransformTree* transform_tree);
+
+// Computes the visible content rect for every layer under |root_layer|. The
+// visible content rect is the clipped content space rect that will be used for
+// recording.
+void CC_EXPORT
+ComputeVisibleRectsUsingPropertyTrees(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);
+
+} // namespace cc
+
+#endif // CC_TREES_DRAW_PROPERTY_UTILS_H_
diff --git a/cc/trees/layer_tree_host.cc b/cc/trees/layer_tree_host.cc
index d192a9a..7c00672 100644
--- a/cc/trees/layer_tree_host.cc
+++ b/cc/trees/layer_tree_host.cc
@@ -873,7 +873,8 @@
GetRendererCapabilities().max_texture_size, settings_.can_use_lcd_text,
settings_.layers_always_allowed_lcd_text,
can_render_to_separate_surface,
- settings_.layer_transforms_should_scale_layer_contents, &update_list,
+ settings_.layer_transforms_should_scale_layer_contents,
+ settings_.verify_property_trees, &update_list,
render_surface_layer_list_id);
LayerTreeHostCommon::CalculateDrawProperties(&inputs);
diff --git a/cc/trees/layer_tree_host_common.cc b/cc/trees/layer_tree_host_common.cc
index 9a9650f..2022f46f 100644
--- a/cc/trees/layer_tree_host_common.cc
+++ b/cc/trees/layer_tree_host_common.cc
@@ -14,7 +14,9 @@
#include "cc/layers/layer_iterator.h"
#include "cc/layers/render_surface.h"
#include "cc/layers/render_surface_impl.h"
+#include "cc/trees/draw_property_utils.h"
#include "cc/trees/layer_sorter.h"
+#include "cc/trees/layer_tree_host.h"
#include "cc/trees/layer_tree_impl.h"
#include "ui/gfx/geometry/rect_conversions.h"
#include "ui/gfx/geometry/vector2d_conversions.h"
@@ -1839,6 +1841,9 @@
} else {
render_to_separate_surface = IsRootLayer(layer);
}
+
+ layer->SetHasRenderSurface(render_to_separate_surface);
+
if (render_to_separate_surface) {
// Check back-face visibility before continuing with this surface and its
// subtree
@@ -2430,6 +2435,14 @@
data_for_recursion->subtree_is_visible_from_ancestor = true;
}
+static bool ApproximatelyEqual(const gfx::Rect& r1, const gfx::Rect& r2) {
+ static const int tolerance = 1;
+ return std::abs(r1.x() - r2.x()) <= tolerance &&
+ std::abs(r1.y() - r2.y()) <= tolerance &&
+ std::abs(r1.width() - r2.width()) <= tolerance &&
+ std::abs(r1.height() - r2.height()) <= tolerance;
+}
+
void LayerTreeHostCommon::CalculateDrawProperties(
CalcDrawPropsMainInputs* inputs) {
LayerList dummy_layer_list;
@@ -2454,6 +2467,36 @@
// A root layer render_surface should always exist after
// CalculateDrawProperties.
DCHECK(inputs->root_layer->render_surface());
+
+ if (inputs->verify_property_trees) {
+ // TODO(ajuma): Can we efficiently cache some of this rather than
+ // starting from scratch every frame?
+ TransformTree transform_tree;
+ ClipTree clip_tree;
+ ComputeVisibleRectsUsingPropertyTrees(
+ inputs->root_layer, inputs->page_scale_application_layer,
+ inputs->page_scale_factor, inputs->device_scale_factor,
+ gfx::Rect(inputs->device_viewport_size), inputs->device_transform,
+ &transform_tree, &clip_tree);
+
+ bool failed = false;
+ LayerIterator<Layer> it, end;
+ for (it = LayerIterator<Layer>::Begin(inputs->render_surface_layer_list),
+ end = LayerIterator<Layer>::End(inputs->render_surface_layer_list);
+ it != end; ++it) {
+ Layer* current_layer = *it;
+ if (it.represents_itself()) {
+ if (!failed && current_layer->DrawsContent() &&
+ !ApproximatelyEqual(
+ current_layer->visible_content_rect(),
+ current_layer->visible_rect_from_property_trees())) {
+ failed = true;
+ }
+ }
+ }
+
+ CHECK(!failed);
+ }
}
void LayerTreeHostCommon::CalculateDrawProperties(
diff --git a/cc/trees/layer_tree_host_common.h b/cc/trees/layer_tree_host_common.h
index 81aca55..678ed75 100644
--- a/cc/trees/layer_tree_host_common.h
+++ b/cc/trees/layer_tree_host_common.h
@@ -45,6 +45,7 @@
bool layers_always_allowed_lcd_text,
bool can_render_to_separate_surface,
bool can_adjust_raster_scales,
+ bool verify_property_trees,
RenderSurfaceLayerListType* render_surface_layer_list,
int current_render_surface_layer_list_id)
: root_layer(root_layer),
@@ -61,6 +62,7 @@
layers_always_allowed_lcd_text(layers_always_allowed_lcd_text),
can_render_to_separate_surface(can_render_to_separate_surface),
can_adjust_raster_scales(can_adjust_raster_scales),
+ verify_property_trees(verify_property_trees),
render_surface_layer_list(render_surface_layer_list),
current_render_surface_layer_list_id(
current_render_surface_layer_list_id) {}
@@ -78,6 +80,7 @@
bool layers_always_allowed_lcd_text;
bool can_render_to_separate_surface;
bool can_adjust_raster_scales;
+ bool verify_property_trees;
RenderSurfaceLayerListType* render_surface_layer_list;
int current_render_surface_layer_list_id;
};
@@ -238,6 +241,7 @@
false,
true,
false,
+ true,
render_surface_layer_list,
0) {
DCHECK(root_layer);
@@ -265,6 +269,7 @@
false,
true,
false,
+ true,
render_surface_layer_list,
0) {
DCHECK(root_layer);
diff --git a/cc/trees/layer_tree_host_common_perftest.cc b/cc/trees/layer_tree_host_common_perftest.cc
index ab72cf96..812e2b4 100644
--- a/cc/trees/layer_tree_host_common_perftest.cc
+++ b/cc/trees/layer_tree_host_common_perftest.cc
@@ -105,6 +105,7 @@
layer_tree_host()
->settings()
.layer_transforms_should_scale_layer_contents,
+ layer_tree_host()->settings().verify_property_trees,
&update_list, 0);
LayerTreeHostCommon::CalculateDrawProperties(&inputs);
@@ -157,6 +158,7 @@
host_impl->settings().layers_always_allowed_lcd_text,
can_render_to_separate_surface,
host_impl->settings().layer_transforms_should_scale_layer_contents,
+ host_impl->settings().verify_property_trees,
&update_list, 0);
LayerTreeHostCommon::CalculateDrawProperties(&inputs);
}
diff --git a/cc/trees/layer_tree_host_common_unittest.cc b/cc/trees/layer_tree_host_common_unittest.cc
index f8e5be9..6581a713 100644
--- a/cc/trees/layer_tree_host_common_unittest.cc
+++ b/cc/trees/layer_tree_host_common_unittest.cc
@@ -670,7 +670,7 @@
gfx::Transform replica_composite_transform =
parent_composite_transform * replica_layer_transform *
Inverse(surface_sublayer_transform);
-
+ child_replica->SetIsDrawable(true);
// Child's render surface should not exist yet.
ASSERT_FALSE(child->render_surface());
diff --git a/cc/trees/layer_tree_host_unittest_no_message_loop.cc b/cc/trees/layer_tree_host_unittest_no_message_loop.cc
index 9e6611a..102e8ac 100644
--- a/cc/trees/layer_tree_host_unittest_no_message_loop.cc
+++ b/cc/trees/layer_tree_host_unittest_no_message_loop.cc
@@ -101,6 +101,7 @@
void SetupLayerTreeHost() {
LayerTreeSettings settings;
settings.single_thread_proxy_scheduler = false;
+ settings.verify_property_trees = true;
layer_tree_host_ = LayerTreeHost::CreateSingleThreaded(
this, this, nullptr, nullptr, settings, nullptr, nullptr);
layer_tree_host_->SetViewportSize(size_);
diff --git a/cc/trees/layer_tree_impl.cc b/cc/trees/layer_tree_impl.cc
index 6a88834..703c37b4 100644
--- a/cc/trees/layer_tree_impl.cc
+++ b/cc/trees/layer_tree_impl.cc
@@ -534,6 +534,7 @@
settings().can_use_lcd_text, settings().layers_always_allowed_lcd_text,
can_render_to_separate_surface,
settings().layer_transforms_should_scale_layer_contents,
+ settings().verify_property_trees,
&render_surface_layer_list_, render_surface_layer_list_id_);
LayerTreeHostCommon::CalculateDrawProperties(&inputs);
}
diff --git a/cc/trees/layer_tree_settings.cc b/cc/trees/layer_tree_settings.cc
index d8d8728..92702e6 100644
--- a/cc/trees/layer_tree_settings.cc
+++ b/cc/trees/layer_tree_settings.cc
@@ -66,7 +66,8 @@
scheduled_raster_task_limit(32),
use_occlusion_for_tile_prioritization(false),
record_full_layer(false),
- use_display_lists(false) {
+ use_display_lists(false),
+ verify_property_trees(false) {
}
LayerTreeSettings::~LayerTreeSettings() {}
diff --git a/cc/trees/layer_tree_settings.h b/cc/trees/layer_tree_settings.h
index b847d1f2..522565f 100644
--- a/cc/trees/layer_tree_settings.h
+++ b/cc/trees/layer_tree_settings.h
@@ -78,6 +78,7 @@
bool use_occlusion_for_tile_prioritization;
bool record_full_layer;
bool use_display_lists;
+ bool verify_property_trees;
LayerTreeDebugState initial_debug_state;
};
diff --git a/cc/trees/property_tree.cc b/cc/trees/property_tree.cc
new file mode 100644
index 0000000..95c2b5a
--- /dev/null
+++ b/cc/trees/property_tree.cc
@@ -0,0 +1,199 @@
+// 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),
+ is_animated(false),
+ to_screen_is_animated(false),
+ flattens(false) {
+}
+
+TransformNodeData::~TransformNodeData() {
+}
+
+ClipNodeData::ClipNodeData() : transform_id(-1), target_id(-1) {
+}
+
+bool TransformTree::ComputeTransform(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const {
+ transform->MakeIdentity();
+
+ if (source_id == dest_id)
+ return true;
+
+ if (source_id > dest_id && IsDescendant(source_id, dest_id))
+ return CombineTransformsBetween(source_id, dest_id, transform);
+
+ if (dest_id > source_id && IsDescendant(dest_id, source_id))
+ return CombineInversesBetween(source_id, dest_id, transform);
+
+ int lca = LowestCommonAncestor(source_id, dest_id);
+
+ bool no_singular_matrices_to_lca =
+ CombineTransformsBetween(source_id, lca, transform);
+
+ bool no_singular_matrices_from_lca =
+ CombineInversesBetween(lca, dest_id, transform);
+
+ return no_singular_matrices_to_lca && no_singular_matrices_from_lca;
+}
+
+bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
+ gfx::Transform transform;
+ return ComputeTransform(source_id, dest_id, &transform) &&
+ transform.Preserves2dAxisAlignment();
+}
+
+void TransformTree::UpdateScreenSpaceTransform(int id) {
+ TransformNode* current_node = Node(id);
+ TransformNode* parent_node = parent(current_node);
+ TransformNode* target_node = Node(current_node->data.target_id);
+
+ if (!parent_node) {
+ current_node->data.to_screen = current_node->data.to_parent;
+ current_node->data.ancestors_are_invertible = true;
+ current_node->data.to_screen_is_animated = false;
+ } else if (parent_node->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.
+ current_node->data.to_screen = target_node->data.to_screen;
+ gfx::Transform flattened;
+ ComputeTransform(parent_node->id, target_node->id, &flattened);
+ flattened.FlattenTo2d();
+ current_node->data.to_screen.PreconcatTransform(flattened);
+ current_node->data.to_screen.PreconcatTransform(
+ current_node->data.to_parent);
+ current_node->data.ancestors_are_invertible =
+ parent_node->data.ancestors_are_invertible;
+ } else {
+ current_node->data.to_screen = parent_node->data.to_screen;
+ current_node->data.to_screen.PreconcatTransform(
+ current_node->data.to_parent);
+ current_node->data.ancestors_are_invertible =
+ parent_node->data.ancestors_are_invertible;
+ }
+ if (!current_node->data.to_screen.GetInverse(¤t_node->data.from_screen))
+ current_node->data.ancestors_are_invertible = false;
+
+ if (parent_node) {
+ current_node->data.to_screen_is_animated =
+ current_node->data.is_animated ||
+ parent_node->data.to_screen_is_animated;
+ }
+}
+
+bool TransformTree::IsDescendant(int desc_id, int source_id) const {
+ while (desc_id != source_id) {
+ if (desc_id < 0)
+ return false;
+ desc_id = Node(desc_id)->parent_id;
+ }
+ return true;
+}
+
+int TransformTree::LowestCommonAncestor(int a, int b) const {
+ std::set<int> chain_a;
+ std::set<int> chain_b;
+ while (a || b) {
+ if (a) {
+ a = Node(a)->parent_id;
+ if (a > -1 && chain_b.find(a) != chain_b.end())
+ return a;
+ chain_a.insert(a);
+ }
+ if (b) {
+ b = Node(b)->parent_id;
+ if (b > -1 && chain_a.find(b) != chain_a.end())
+ return b;
+ chain_b.insert(b);
+ }
+ }
+ NOTREACHED();
+ return 0;
+}
+
+bool TransformTree::CombineTransformsBetween(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const {
+ const TransformNode* current = Node(source_id);
+ const TransformNode* dest = 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 = parent(current)) {
+ transform->ConcatTransform(current->data.to_parent);
+ if (!current->data.is_invertible)
+ all_are_invertible = false;
+ }
+
+ return all_are_invertible;
+}
+
+bool TransformTree::CombineInversesBetween(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const {
+ const TransformNode* current = Node(dest_id);
+ const TransformNode* dest = 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 = parent(current)) {
+ transform->PreconcatTransform(current->data.from_parent);
+ if (!current->data.is_invertible)
+ all_are_invertible = false;
+ }
+
+ return all_are_invertible;
+}
+
+} // namespace cc
diff --git a/cc/trees/property_tree.h b/cc/trees/property_tree.h
new file mode 100644
index 0000000..8e07683
--- /dev/null
+++ b/cc/trees/property_tree.h
@@ -0,0 +1,139 @@
+// 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.
+
+#ifndef CC_TREES_PROPERTY_TREE_H_
+#define CC_TREES_PROPERTY_TREE_H_
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "cc/base/cc_export.h"
+#include "ui/gfx/rect.h"
+#include "ui/gfx/transform.h"
+
+namespace cc {
+
+template <typename T>
+struct CC_EXPORT TreeNode {
+ TreeNode() : id(-1), parent_id(-1), data() {}
+ int id;
+ int parent_id;
+ T data;
+};
+
+struct CC_EXPORT TransformNodeData {
+ TransformNodeData();
+ ~TransformNodeData();
+
+ gfx::Transform to_parent;
+ gfx::Transform from_parent;
+
+ gfx::Transform to_screen;
+ gfx::Transform from_screen;
+
+ int target_id;
+
+ bool is_invertible;
+ bool ancestors_are_invertible;
+
+ bool is_animated;
+ bool to_screen_is_animated;
+
+ bool flattens;
+
+ void set_to_parent(const gfx::Transform& transform) {
+ to_parent = transform;
+ is_invertible = to_parent.GetInverse(&from_parent);
+ }
+};
+
+typedef TreeNode<TransformNodeData> TransformNode;
+
+struct CC_EXPORT ClipNodeData {
+ ClipNodeData();
+
+ gfx::RectF clip;
+ gfx::RectF combined_clip;
+ int transform_id;
+ int target_id;
+};
+
+typedef TreeNode<ClipNodeData> ClipNode;
+
+template <typename T>
+class CC_EXPORT PropertyTree {
+ public:
+ PropertyTree();
+ virtual ~PropertyTree();
+
+ int Insert(const T& tree_node, int parent_id);
+
+ T* Node(int i) { return i > -1 ? &nodes_[i] : nullptr; }
+ const T* Node(int i) const { return i > -1 ? &nodes_[i] : nullptr; }
+
+ T* parent(const T* t) {
+ return t->parent_id > -1 ? Node(t->parent_id) : nullptr;
+ }
+ const T* parent(const T* t) const {
+ return t->parent_id > -1 ? Node(t->parent_id) : nullptr;
+ }
+
+ T* back() { return size() ? &nodes_[nodes_.size() - 1] : nullptr; }
+ const T* back() const {
+ return size() ? &nodes_[nodes_.size() - 1] : nullptr;
+ }
+
+ void clear() { nodes_.clear(); }
+ size_t size() const { return nodes_.size(); }
+
+ private:
+ // Copy and assign are permitted. This is how we do tree sync.
+ std::vector<T> nodes_;
+};
+
+class CC_EXPORT TransformTree final : public PropertyTree<TransformNode> {
+ public:
+ // Computes the change of basis transform from node |source_id| to |dest_id|.
+ // The function returns false iff the inverse of a singular transform was
+ // used (and the result should, therefore, not be trusted).
+ bool ComputeTransform(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const;
+
+ // Returns true iff the nodes indexed by |source_id| and |dest_id| are 2D axis
+ // aligned with respect to one another.
+ bool Are2DAxisAligned(int source_id, int dest_id) const;
+
+ // This recomputes the screen space transform (and its inverse) for the node
+ // at |id|.
+ void UpdateScreenSpaceTransform(int id);
+
+ private:
+ // Returns true iff the node at |desc_id| is a descendant of the node at
+ // |anc_id|.
+ bool IsDescendant(int desc_id, int anc_id) const;
+
+ // Returns the index of the lowest common ancestor of the nodes |a| and |b|.
+ int LowestCommonAncestor(int a, int b) const;
+
+ // Computes the combined transform between |source_id| and |dest_id| and
+ // returns false if the inverse of a singular transform was used. These two
+ // nodes must be on the same ancestor chain.
+ bool CombineTransformsBetween(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const;
+
+ // Computes the combined inverse transform between |source_id| and |dest_id|
+ // and returns false if the inverse of a singular transform was used. These
+ // two nodes must be on the same ancestor chain.
+ bool CombineInversesBetween(int source_id,
+ int dest_id,
+ gfx::Transform* transform) const;
+};
+
+class CC_EXPORT ClipTree final : public PropertyTree<ClipNode> {};
+
+} // namespace cc
+
+#endif // CC_TREES_PROPERTY_TREE_H_
diff --git a/cc/trees/property_tree_builder.cc b/cc/trees/property_tree_builder.cc
new file mode 100644
index 0000000..cd0e52b
--- /dev/null
+++ b/cc/trees/property_tree_builder.cc
@@ -0,0 +1,280 @@
+// 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 =
+ data_from_ancestor.transform_tree->Are2DAxisAligned(
+ layer->transform_tree_index(), parent->data.transform_id);
+
+ // TODO(vollick): once Andrew refactors the surface determinations out of
+ // CDP, the the layer->render_surface() check will be invalid.
+ const bool has_unclipped_surface =
+ layer->render_surface() &&
+ !layer->render_surface()->is_clipped() &&
+ 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 existing bugs (crbug.com/441447).
+ 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();
+ }
+ data_from_ancestor.transform_tree->ComputeTransform(
+ 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();
+ node->data.is_animated = layer->TransformIsAnimating();
+
+ 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);
+
+ // TODO(vollick): We've accounted for the scroll offset here but we haven't
+ // taken into account snapping to screen space pixels. 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);
+
+ data_from_ancestor.transform_tree->UpdateScreenSpaceTransform(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 = transform_tree->Insert(TransformNode(), 0);
+
+ ClipNode root_clip;
+ root_clip.data.clip = viewport;
+ root_clip.data.transform_id = 0;
+ data_for_recursion.clip_tree_parent = clip_tree->Insert(root_clip, 0);
+
+ BuildPropertyTreesInternal(root_layer, data_for_recursion);
+
+ TransformNode* transform_root = transform_tree->Node(transform_root_id);
+ transform_root->data.set_to_parent(device_transform *
+ transform_root->data.to_parent);
+}
+
+} // namespace cc
diff --git a/cc/trees/property_tree_builder.h b/cc/trees/property_tree_builder.h
new file mode 100644
index 0000000..f949c9a
--- /dev/null
+++ b/cc/trees/property_tree_builder.h
@@ -0,0 +1,31 @@
+// 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.
+
+#ifndef CC_TREES_PROPERTY_TREE_BUILDER_H_
+#define CC_TREES_PROPERTY_TREE_BUILDER_H_
+
+#include <vector>
+
+#include "cc/trees/layer_tree_host_common.h"
+#include "cc/trees/property_tree.h"
+
+namespace cc {
+
+class LayerTreeHost;
+
+class PropertyTreeBuilder {
+ public:
+ static void 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);
+};
+
+} // namespace cc
+
+#endif // CC_TREES_PROPERTY_TREE_BUILDER_H_
diff --git a/cc/trees/property_tree_unittest.cc b/cc/trees/property_tree_unittest.cc
new file mode 100644
index 0000000..e6de967
--- /dev/null
+++ b/cc/trees/property_tree_unittest.cc
@@ -0,0 +1,207 @@
+// 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.h"
+
+#include "cc/test/geometry_test_utils.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+
+TEST(PropertyTreeTest, ComputeTransformRoot) {
+ TransformTree tree;
+ TransformNode& root = *tree.Node(0);
+ root.data.to_parent.Translate(2, 2);
+ root.data.from_parent.Translate(-2, -2);
+ tree.UpdateScreenSpaceTransform(0);
+
+ gfx::Transform expected;
+ gfx::Transform transform;
+ bool success = tree.ComputeTransform(0, 0, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.Translate(2, 2);
+ success = tree.ComputeTransform(0, -1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(-2, -2);
+ success = tree.ComputeTransform(-1, 0, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+}
+
+TEST(PropertyTreeTest, ComputeTransformChild) {
+ TransformTree tree;
+ TransformNode& root = *tree.Node(0);
+ root.data.to_parent.Translate(2, 2);
+ root.data.from_parent.Translate(-2, -2);
+ tree.UpdateScreenSpaceTransform(0);
+
+ TransformNode child;
+ child.data.to_parent.Translate(3, 3);
+ child.data.from_parent.Translate(-3, -3);
+
+ tree.Insert(child, 0);
+ tree.UpdateScreenSpaceTransform(1);
+
+ gfx::Transform expected;
+ gfx::Transform transform;
+
+ expected.Translate(3, 3);
+ bool success = tree.ComputeTransform(1, 0, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(-3, -3);
+ success = tree.ComputeTransform(0, 1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(5, 5);
+ success = tree.ComputeTransform(1, -1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(-5, -5);
+ success = tree.ComputeTransform(-1, 1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+}
+
+TEST(PropertyTreeTest, ComputeTransformSibling) {
+ TransformTree tree;
+ TransformNode& root = *tree.Node(0);
+ root.data.to_parent.Translate(2, 2);
+ root.data.from_parent.Translate(-2, -2);
+ tree.UpdateScreenSpaceTransform(0);
+
+ TransformNode child;
+ child.data.to_parent.Translate(3, 3);
+ child.data.from_parent.Translate(-3, -3);
+
+ TransformNode sibling;
+ sibling.data.to_parent.Translate(7, 7);
+ sibling.data.from_parent.Translate(-7, -7);
+
+ tree.Insert(child, 0);
+ tree.Insert(sibling, 0);
+
+ tree.UpdateScreenSpaceTransform(1);
+ tree.UpdateScreenSpaceTransform(2);
+
+ gfx::Transform expected;
+ gfx::Transform transform;
+
+ expected.Translate(4, 4);
+ bool success = tree.ComputeTransform(2, 1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(-4, -4);
+ success = tree.ComputeTransform(1, 2, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+}
+
+TEST(PropertyTreeTest, ComputeTransformSiblingSingularAncestor) {
+ // In this test, we have the following tree:
+ // root
+ // + singular
+ // + child
+ // + sibling
+ // Now singular has a singular transform, so we cannot use screen space
+ // transforms to compute change of basis transforms between |child| and
+ // |sibling|.
+ TransformTree tree;
+ TransformNode& root = *tree.Node(0);
+ root.data.to_parent.Translate(2, 2);
+ root.data.from_parent.Translate(-2, -2);
+ tree.UpdateScreenSpaceTransform(0);
+
+ TransformNode singular;
+ singular.data.to_parent.matrix().set(2, 2, 0.0);
+ singular.data.is_invertible = false;
+ singular.data.ancestors_are_invertible = false;
+
+ TransformNode child;
+ child.data.to_parent.Translate(3, 3);
+ child.data.from_parent.Translate(-3, -3);
+ child.data.ancestors_are_invertible = false;
+
+ TransformNode sibling;
+ sibling.data.to_parent.Translate(7, 7);
+ sibling.data.from_parent.Translate(-7, -7);
+ sibling.data.ancestors_are_invertible = false;
+
+ tree.Insert(singular, 0);
+ tree.Insert(child, 1);
+ tree.Insert(sibling, 1);
+
+ tree.UpdateScreenSpaceTransform(1);
+ tree.UpdateScreenSpaceTransform(2);
+ tree.UpdateScreenSpaceTransform(3);
+
+ gfx::Transform expected;
+ gfx::Transform transform;
+
+ expected.Translate(4, 4);
+ bool success = tree.ComputeTransform(3, 2, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ transform.MakeIdentity();
+ expected.MakeIdentity();
+ expected.Translate(-4, -4);
+ success = tree.ComputeTransform(2, 3, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+}
+
+TEST(PropertyTreeTest, MultiplicationOrder) {
+ TransformTree tree;
+ TransformNode& root = *tree.Node(0);
+ root.data.to_parent.Translate(2, 2);
+ root.data.from_parent.Translate(-2, -2);
+ tree.UpdateScreenSpaceTransform(0);
+
+ TransformNode child;
+ child.data.to_parent.Scale(2, 2);
+ child.data.from_parent.Scale(0.5, 0.5);
+
+ tree.Insert(child, 0);
+ tree.UpdateScreenSpaceTransform(1);
+
+ gfx::Transform expected;
+ expected.Translate(2, 2);
+ expected.Scale(2, 2);
+
+ gfx::Transform transform;
+ gfx::Transform inverse;
+
+ bool success = tree.ComputeTransform(1, -1, &transform);
+ EXPECT_TRUE(success);
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+
+ success = tree.ComputeTransform(-1, 1, &inverse);
+ EXPECT_TRUE(success);
+
+ transform = transform * inverse;
+ expected.MakeIdentity();
+ EXPECT_TRANSFORMATION_MATRIX_EQ(expected, transform);
+}
+
+} // namespace cc
diff --git a/ui/gfx/transform.h b/ui/gfx/transform.h
index eeb66206..85bab694 100644
--- a/ui/gfx/transform.h
+++ b/ui/gfx/transform.h
@@ -122,6 +122,11 @@
// Returns true if the matrix is either identity or pure translation.
bool IsIdentityOrTranslation() const { return matrix_.isTranslate(); }
+ // Returns true if the matrix is either the identity or a 2d translation.
+ bool IsIdentityOr2DTranslation() const {
+ return matrix_.isTranslate() && matrix_.get(2, 3) == 0;
+ }
+
// Returns true if the matrix is either identity or pure translation,
// allowing for an amount of inaccuracy as specified by the parameter.
bool IsApproximatelyIdentityOrTranslation(SkMScalar tolerance) const;