// 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(const gfx::Vector2dF& u, | |

const 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(const gfx::PointF& a, | |

const gfx::PointF& b, | |

const gfx::PointF& c, | |

const 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(const 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 |