diff options
Diffstat (limited to 'chromium/cc/trees/layer_sorter.cc')
| -rw-r--r-- | chromium/cc/trees/layer_sorter.cc | 469 |
1 files changed, 469 insertions, 0 deletions
diff --git a/chromium/cc/trees/layer_sorter.cc b/chromium/cc/trees/layer_sorter.cc new file mode 100644 index 00000000000..73fe3efcb1e --- /dev/null +++ b/chromium/cc/trees/layer_sorter.cc @@ -0,0 +1,469 @@ +// Copyright 2011 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/layer_sorter.h" + +#include <algorithm> +#include <deque> +#include <limits> +#include <vector> + +#include "base/logging.h" +#include "cc/base/math_util.h" +#include "cc/layers/render_surface_impl.h" +#include "ui/gfx/transform.h" + +namespace cc { + +// This epsilon is used to determine if two layers are too close to each other +// to be able to tell which is in front of the other. It's a relative epsilon +// so it is robust to changes in scene scale. This value was chosen by picking +// a value near machine epsilon and then increasing it until the flickering on +// the test scene went away. +const float k_layer_epsilon = 1e-4f; + +inline static float PerpProduct(gfx::Vector2dF u, gfx::Vector2dF v) { + return u.x() * v.y() - u.y() * v.x(); +} + +// Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. +// Returns true and the point of intersection if they do and false otherwise. +static bool EdgeEdgeTest(gfx::PointF a, + gfx::PointF b, + gfx::PointF c, + gfx::PointF d, + gfx::PointF* r) { + gfx::Vector2dF u = b - a; + gfx::Vector2dF v = d - c; + gfx::Vector2dF w = a - c; + + float denom = PerpProduct(u, v); + + // If denom == 0 then the edges are parallel. While they could be overlapping + // we don't bother to check here as the we'll find their intersections from + // the corner to quad tests. + if (!denom) + return false; + + float s = PerpProduct(v, w) / denom; + if (s < 0.f || s > 1.f) + return false; + + float t = PerpProduct(u, w) / denom; + if (t < 0.f || t > 1.f) + return false; + + u.Scale(s); + *r = a + u; + return true; +} + +GraphNode::GraphNode(LayerImpl* layer_impl) + : layer(layer_impl), + incoming_edge_weight(0.f) {} + +GraphNode::~GraphNode() {} + +LayerSorter::LayerSorter() + : z_range_(0.f) {} + +LayerSorter::~LayerSorter() {} + +static float CheckFloatingPointNumericAccuracy(float a, float b) { + float abs_dif = std::abs(b - a); + float abs_max = std::max(std::abs(b), std::abs(a)); + // Check to see if we've got a result with a reasonable amount of error. + return abs_dif / abs_max; +} + +// Checks whether layer "a" draws on top of layer "b". The weight value returned +// is an indication of the maximum z-depth difference between the layers or zero +// if the layers are found to be intesecting (some features are in front and +// some are behind). +LayerSorter::ABCompareResult LayerSorter::CheckOverlap(LayerShape* a, + LayerShape* b, + float z_threshold, + float* weight) { + *weight = 0.f; + + // Early out if the projected bounds don't overlap. + if (!a->projected_bounds.Intersects(b->projected_bounds)) + return None; + + gfx::PointF aPoints[4] = { a->projected_quad.p1(), + a->projected_quad.p2(), + a->projected_quad.p3(), + a->projected_quad.p4() }; + gfx::PointF bPoints[4] = { b->projected_quad.p1(), + b->projected_quad.p2(), + b->projected_quad.p3(), + b->projected_quad.p4() }; + + // Make a list of points that inside both layer quad projections. + std::vector<gfx::PointF> overlap_points; + + // Check all four corners of one layer against the other layer's quad. + for (int i = 0; i < 4; ++i) { + if (a->projected_quad.Contains(bPoints[i])) + overlap_points.push_back(bPoints[i]); + if (b->projected_quad.Contains(aPoints[i])) + overlap_points.push_back(aPoints[i]); + } + + // Check all the edges of one layer for intersection with the other layer's + // edges. + gfx::PointF r; + for (int ea = 0; ea < 4; ++ea) + for (int eb = 0; eb < 4; ++eb) + if (EdgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4], + bPoints[eb], bPoints[(eb + 1) % 4], + &r)) + overlap_points.push_back(r); + + if (overlap_points.empty()) + return None; + + // Check the corresponding layer depth value for all overlap points to + // determine which layer is in front. + float max_positive = 0.f; + float max_negative = 0.f; + + // This flag tracks the existance of a numerically accurate seperation + // between two layers. If there is no accurate seperation, the layers + // cannot be effectively sorted. + bool accurate = false; + + for (size_t o = 0; o < overlap_points.size(); o++) { + float za = a->LayerZFromProjectedPoint(overlap_points[o]); + float zb = b->LayerZFromProjectedPoint(overlap_points[o]); + + // Here we attempt to avoid numeric issues with layers that are too + // close together. If we have 2-sided quads that are very close + // together then we will draw them in document order to avoid + // flickering. The correct solution is for the content maker to turn + // on back-face culling or move the quads apart (if they're not two + // sides of one object). + if (CheckFloatingPointNumericAccuracy(za, zb) > k_layer_epsilon) + accurate = true; + + float diff = za - zb; + if (diff > max_positive) + max_positive = diff; + if (diff < max_negative) + max_negative = diff; + } + + // If we can't tell which should come first, we use document order. + if (!accurate) + return ABeforeB; + + float max_diff = + std::abs(max_positive) > std::abs(max_negative) ? + max_positive : max_negative; + + // If the results are inconsistent (and the z difference substantial to rule + // out numerical errors) then the layers are intersecting. We will still + // return an order based on the maximum depth difference but with an edge + // weight of zero these layers will get priority if a graph cycle is present + // and needs to be broken. + if (max_positive > z_threshold && max_negative < -z_threshold) + *weight = 0.f; + else + *weight = std::abs(max_diff); + + // Maintain relative order if the layers have the same depth at all + // intersection points. + if (max_diff <= 0.f) + return ABeforeB; + + return BBeforeA; +} + +LayerShape::LayerShape() {} + +LayerShape::LayerShape(float width, + float height, + const gfx::Transform& draw_transform) { + gfx::QuadF layer_quad(gfx::RectF(0.f, 0.f, width, height)); + + // Compute the projection of the layer quad onto the z = 0 plane. + + gfx::PointF clipped_quad[8]; + int num_vertices_in_clipped_quad; + MathUtil::MapClippedQuad(draw_transform, + layer_quad, + clipped_quad, + &num_vertices_in_clipped_quad); + + if (num_vertices_in_clipped_quad < 3) { + projected_bounds = gfx::RectF(); + return; + } + + projected_bounds = + MathUtil::ComputeEnclosingRectOfVertices(clipped_quad, + num_vertices_in_clipped_quad); + + // NOTE: it will require very significant refactoring and overhead to deal + // with generalized polygons or multiple quads per layer here. For the sake of + // layer sorting it is equally correct to take a subsection of the polygon + // that can be made into a quad. This will only be incorrect in the case of + // intersecting layers, which are not supported yet anyway. + projected_quad.set_p1(clipped_quad[0]); + projected_quad.set_p2(clipped_quad[1]); + projected_quad.set_p3(clipped_quad[2]); + if (num_vertices_in_clipped_quad >= 4) { + projected_quad.set_p4(clipped_quad[3]); + } else { + // This will be a degenerate quad that is actually a triangle. + projected_quad.set_p4(clipped_quad[2]); + } + + // Compute the normal of the layer's plane. + bool clipped = false; + gfx::Point3F c1 = + MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 0.f, 0.f), &clipped); + gfx::Point3F c2 = + MathUtil::MapPoint(draw_transform, gfx::Point3F(0.f, 1.f, 0.f), &clipped); + gfx::Point3F c3 = + MathUtil::MapPoint(draw_transform, gfx::Point3F(1.f, 0.f, 0.f), &clipped); + // TODO(shawnsingh): Deal with clipping. + gfx::Vector3dF c12 = c2 - c1; + gfx::Vector3dF c13 = c3 - c1; + layer_normal = gfx::CrossProduct(c13, c12); + + transform_origin = c1; +} + +LayerShape::~LayerShape() {} + +// Returns the Z coordinate of a point on the layer that projects +// to point p which lies on the z = 0 plane. It does it by computing the +// intersection of a line starting from p along the Z axis and the plane +// of the layer. +float LayerShape::LayerZFromProjectedPoint(gfx::PointF p) const { + gfx::Vector3dF z_axis(0.f, 0.f, 1.f); + gfx::Vector3dF w = gfx::Point3F(p) - transform_origin; + + float d = gfx::DotProduct(layer_normal, z_axis); + float n = -gfx::DotProduct(layer_normal, w); + + // Check if layer is parallel to the z = 0 axis which will make it + // invisible and hence returning zero is fine. + if (!d) + return 0.f; + + // The intersection point would be given by: + // p + (n / d) * u but since we are only interested in the + // z coordinate and p's z coord is zero, all we need is the value of n/d. + return n / d; +} + +void LayerSorter::CreateGraphNodes(LayerImplList::iterator first, + LayerImplList::iterator last) { + DVLOG(2) << "Creating graph nodes:"; + float min_z = FLT_MAX; + float max_z = -FLT_MAX; + for (LayerImplList::const_iterator it = first; it < last; it++) { + nodes_.push_back(GraphNode(*it)); + GraphNode& node = nodes_.at(nodes_.size() - 1); + RenderSurfaceImpl* render_surface = node.layer->render_surface(); + if (!node.layer->DrawsContent() && !render_surface) + continue; + + DVLOG(2) << "Layer " << node.layer->id() << + " (" << node.layer->bounds().width() << + " x " << node.layer->bounds().height() << ")"; + + gfx::Transform draw_transform; + float layer_width, layer_height; + if (render_surface) { + draw_transform = render_surface->draw_transform(); + layer_width = render_surface->content_rect().width(); + layer_height = render_surface->content_rect().height(); + } else { + draw_transform = node.layer->draw_transform(); + layer_width = node.layer->content_bounds().width(); + layer_height = node.layer->content_bounds().height(); + } + + node.shape = LayerShape(layer_width, layer_height, draw_transform); + + max_z = std::max(max_z, node.shape.transform_origin.z()); + min_z = std::min(min_z, node.shape.transform_origin.z()); + } + + z_range_ = std::abs(max_z - min_z); +} + +void LayerSorter::CreateGraphEdges() { + DVLOG(2) << "Edges:"; + // Fraction of the total z_range below which z differences + // are not considered reliable. + const float z_threshold_factor = 0.01f; + float z_threshold = z_range_ * z_threshold_factor; + + for (size_t na = 0; na < nodes_.size(); na++) { + GraphNode& node_a = nodes_[na]; + if (!node_a.layer->DrawsContent() && !node_a.layer->render_surface()) + continue; + for (size_t nb = na + 1; nb < nodes_.size(); nb++) { + GraphNode& node_b = nodes_[nb]; + if (!node_b.layer->DrawsContent() && !node_b.layer->render_surface()) + continue; + float weight = 0.f; + ABCompareResult overlap_result = CheckOverlap(&node_a.shape, + &node_b.shape, + z_threshold, + &weight); + GraphNode* start_node = NULL; + GraphNode* end_node = NULL; + if (overlap_result == ABeforeB) { + start_node = &node_a; + end_node = &node_b; + } else if (overlap_result == BBeforeA) { + start_node = &node_b; + end_node = &node_a; + } + + if (start_node) { + DVLOG(2) << start_node->layer->id() << " -> " << end_node->layer->id(); + edges_.push_back(GraphEdge(start_node, end_node, weight)); + } + } + } + + for (size_t i = 0; i < edges_.size(); i++) { + GraphEdge& edge = edges_[i]; + active_edges_[&edge] = &edge; + edge.from->outgoing.push_back(&edge); + edge.to->incoming.push_back(&edge); + edge.to->incoming_edge_weight += edge.weight; + } +} + +// Finds and removes an edge from the list by doing a swap with the +// last element of the list. +void LayerSorter::RemoveEdgeFromList(GraphEdge* edge, + std::vector<GraphEdge*>* list) { + std::vector<GraphEdge*>::iterator iter = + std::find(list->begin(), list->end(), edge); + DCHECK(iter != list->end()); + list->erase(iter); +} + +// Sorts the given list of layers such that they can be painted in a +// back-to-front order. Sorting produces correct results for non-intersecting +// layers that don't have cyclical order dependencies. Cycles and intersections +// are broken (somewhat) aribtrarily. Sorting of layers is done via a +// topological sort of a directed graph whose nodes are the layers themselves. +// An edge from node A to node B signifies that layer A needs to be drawn before +// layer B. If A and B have no dependency between each other, then we preserve +// the ordering of those layers as they were in the original list. +// +// The draw order between two layers is determined by projecting the two +// triangles making up each layer quad to the Z = 0 plane, finding points of +// intersection between the triangles and backprojecting those points to the +// plane of the layer to determine the corresponding Z coordinate. The layer +// with the lower Z coordinate (farther from the eye) needs to be rendered +// first. +// +// If the layer projections don't intersect, then no edges (dependencies) are +// created between them in the graph. HOWEVER, in this case we still need to +// preserve the ordering of the original list of layers, since that list should +// already have proper z-index ordering of layers. +// +void LayerSorter::Sort(LayerImplList::iterator first, + LayerImplList::iterator last) { + DVLOG(2) << "Sorting start ----"; + CreateGraphNodes(first, last); + + CreateGraphEdges(); + + std::vector<GraphNode*> sorted_list; + std::deque<GraphNode*> no_incoming_edge_node_list; + + // Find all the nodes that don't have incoming edges. + for (NodeList::iterator la = nodes_.begin(); la < nodes_.end(); la++) { + if (!la->incoming.size()) + no_incoming_edge_node_list.push_back(&(*la)); + } + + DVLOG(2) << "Sorted list: "; + while (active_edges_.size() || no_incoming_edge_node_list.size()) { + while (no_incoming_edge_node_list.size()) { + // It is necessary to preserve the existing ordering of layers, when there + // are no explicit dependencies (because this existing ordering has + // correct z-index/layout ordering). To preserve this ordering, we process + // Nodes in the same order that they were added to the list. + GraphNode* from_node = no_incoming_edge_node_list.front(); + no_incoming_edge_node_list.pop_front(); + + // Add it to the final list. + sorted_list.push_back(from_node); + + DVLOG(2) << from_node->layer->id() << ", "; + + // Remove all its outgoing edges from the graph. + for (size_t i = 0; i < from_node->outgoing.size(); i++) { + GraphEdge* outgoing_edge = from_node->outgoing[i]; + + active_edges_.erase(outgoing_edge); + RemoveEdgeFromList(outgoing_edge, &outgoing_edge->to->incoming); + outgoing_edge->to->incoming_edge_weight -= outgoing_edge->weight; + + if (!outgoing_edge->to->incoming.size()) + no_incoming_edge_node_list.push_back(outgoing_edge->to); + } + from_node->outgoing.clear(); + } + + if (!active_edges_.size()) + break; + + // If there are still active edges but the list of nodes without incoming + // edges is empty then we have run into a cycle. Break the cycle by finding + // the node with the smallest overall incoming edge weight and use it. This + // will favor nodes that have zero-weight incoming edges i.e. layers that + // are being occluded by a layer that intersects them. + float min_incoming_edge_weight = FLT_MAX; + GraphNode* next_node = NULL; + for (size_t i = 0; i < nodes_.size(); i++) { + if (nodes_[i].incoming.size() && + nodes_[i].incoming_edge_weight < min_incoming_edge_weight) { + min_incoming_edge_weight = nodes_[i].incoming_edge_weight; + next_node = &nodes_[i]; + } + } + DCHECK(next_node); + // Remove all its incoming edges. + for (size_t e = 0; e < next_node->incoming.size(); e++) { + GraphEdge* incoming_edge = next_node->incoming[e]; + + active_edges_.erase(incoming_edge); + RemoveEdgeFromList(incoming_edge, &incoming_edge->from->outgoing); + } + next_node->incoming.clear(); + next_node->incoming_edge_weight = 0.f; + no_incoming_edge_node_list.push_back(next_node); + DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " << + next_node->layer->id() << + " (weight = " << min_incoming_edge_weight << ")"; + } + + // Note: The original elements of the list are in no danger of having their + // ref count go to zero here as they are all nodes of the layer hierarchy and + // are kept alive by their parent nodes. + int count = 0; + for (LayerImplList::iterator it = first; it < last; it++) + *it = sorted_list[count++]->layer; + + DVLOG(2) << "Sorting end ----"; + + nodes_.clear(); + edges_.clear(); + active_edges_.clear(); +} + +} // namespace cc |