cc/trees/layer_sorter.h

   1 // Copyright 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef CC_TREES_LAYER_SORTER_H_
   6 #define CC_TREES_LAYER_SORTER_H_
   7
   8 #include <vector>
   9
  10 #include "base/basictypes.h"
  11 #include "base/containers/hash_tables.h"
  12 #include "cc/base/cc_export.h"
  13 #include "cc/layers/layer_impl.h"
  14 #include "ui/gfx/geometry/point3_f.h"
  15 #include "ui/gfx/geometry/quad_f.h"
  16 #include "ui/gfx/geometry/rect_f.h"
  17 #include "ui/gfx/geometry/vector3d_f.h"
  18
  19 namespace gfx {
  20 class Transform;
  21 }
  22
  23 namespace cc {
  24 struct GraphEdge;
  25
  26 // Holds various useful properties derived from a layer's 3D outline.
  27 struct CC_EXPORT LayerShape {
  28   LayerShape();
  29   LayerShape(float width, float height, const gfx::Transform& draw_transform);
  30   ~LayerShape();
  31
  32   float LayerZFromProjectedPoint(const gfx::PointF& p) const;
  33
  34   gfx::Vector3dF layer_normal;
  35   gfx::Point3F transform_origin;
  36   gfx::QuadF projected_quad;
  37   gfx::RectF projected_bounds;
  38 };
  39
  40 struct GraphNode {
  41   explicit GraphNode(LayerImpl* layer_impl);
  42   ~GraphNode();
  43
  44   LayerImpl* layer;
  45   LayerShape shape;
  46   std::vector<GraphEdge*> incoming;
  47   std::vector<GraphEdge*> outgoing;
  48   float incoming_edge_weight;
  49 };
  50
  51 struct GraphEdge {
  52   GraphEdge(GraphNode* from_node, GraphNode* to_node, float weight)
  53       : from(from_node),
  54         to(to_node),
  55         weight(weight) {}
  56
  57   GraphNode* from;
  58   GraphNode* to;
  59   float weight;
  60 };
  61
  62
  63
  64 class CC_EXPORT LayerSorter {
  65  public:
  66   LayerSorter();
  67   ~LayerSorter();
  68
  69   void Sort(LayerImplList::iterator first, LayerImplList::iterator last);
  70
  71   enum ABCompareResult {
  72     ABeforeB,
  73     BBeforeA,
  74     None
  75   };
  76
  77   static ABCompareResult CheckOverlap(LayerShape* a,
  78                                       LayerShape* b,
  79                                       float z_threshold,
  80                                       float* weight);
  81
  82  private:
  83   typedef std::vector<GraphNode> NodeList;
  84   typedef std::vector<GraphEdge> EdgeList;
  85   NodeList nodes_;
  86   EdgeList edges_;
  87   float z_range_;
  88
  89   typedef base::hash_map<GraphEdge*, GraphEdge*> EdgeMap;
  90   EdgeMap active_edges_;
  91
  92   void CreateGraphNodes(LayerImplList::iterator first,
  93                         LayerImplList::iterator last);
  94   void CreateGraphEdges();
  95   void RemoveEdgeFromList(GraphEdge* graph, std::vector<GraphEdge*>* list);
  96
  97   DISALLOW_COPY_AND_ASSIGN(LayerSorter);
  98 };
  99
 100 }  // namespace cc
 101 #endif  // CC_TREES_LAYER_SORTER_H_