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/point3_f.h"
  15 #include "ui/gfx/quad_f.h"
  16 #include "ui/gfx/rect_f.h"
  17 #include "ui/gfx/vector3d_f.h"
  18
  19 #if defined(COMPILER_GCC)
  20 namespace cc { struct GraphEdge; }
  21
  22 namespace BASE_HASH_NAMESPACE {
  23 template <>
  24 struct hash<cc::GraphEdge*> {
  25   size_t operator()(cc::GraphEdge* ptr) const {
  26     return hash<size_t>()(reinterpret_cast<size_t>(ptr));
  27   }
  28 };
  29 }  // namespace BASE_HASH_NAMESPACE
  30 #endif  // COMPILER
  31
  32 namespace gfx {
  33 class Transform;
  34 }
  35
  36 namespace cc {
  37 struct GraphEdge;
  38
  39 // Holds various useful properties derived from a layer's 3D outline.
  40 struct CC_EXPORT LayerShape {
  41   LayerShape();
  42   LayerShape(float width, float height, const gfx::Transform& draw_transform);
  43   ~LayerShape();
  44
  45   float LayerZFromProjectedPoint(const gfx::PointF& p) const;
  46
  47   gfx::Vector3dF layer_normal;
  48   gfx::Point3F transform_origin;
  49   gfx::QuadF projected_quad;
  50   gfx::RectF projected_bounds;
  51 };
  52
  53 struct GraphNode {
  54   explicit GraphNode(LayerImpl* layer_impl);
  55   ~GraphNode();
  56
  57   LayerImpl* layer;
  58   LayerShape shape;
  59   std::vector<GraphEdge*> incoming;
  60   std::vector<GraphEdge*> outgoing;
  61   float incoming_edge_weight;
  62 };
  63
  64 struct GraphEdge {
  65   GraphEdge(GraphNode* from_node, GraphNode* to_node, float weight)
  66       : from(from_node),
  67         to(to_node),
  68         weight(weight) {}
  69
  70   GraphNode* from;
  71   GraphNode* to;
  72   float weight;
  73 };
  74
  75
  76
  77 class CC_EXPORT LayerSorter {
  78  public:
  79   LayerSorter();
  80   ~LayerSorter();
  81
  82   void Sort(LayerImplList::iterator first, LayerImplList::iterator last);
  83
  84   enum ABCompareResult {
  85     ABeforeB,
  86     BBeforeA,
  87     None
  88   };
  89
  90   static ABCompareResult CheckOverlap(LayerShape* a,
  91                                       LayerShape* b,
  92                                       float z_threshold,
  93                                       float* weight);
  94
  95  private:
  96   typedef std::vector<GraphNode> NodeList;
  97   typedef std::vector<GraphEdge> EdgeList;
  98   NodeList nodes_;
  99   EdgeList edges_;
 100   float z_range_;
 101
 102   typedef base::hash_map<GraphEdge*, GraphEdge*> EdgeMap;
 103   EdgeMap active_edges_;
 104
 105   void CreateGraphNodes(LayerImplList::iterator first,
 106                         LayerImplList::iterator last);
 107   void CreateGraphEdges();
 108   void RemoveEdgeFromList(GraphEdge* graph, std::vector<GraphEdge*>* list);
 109
 110   DISALLOW_COPY_AND_ASSIGN(LayerSorter);
 111 };
 112
 113 }  // namespace cc
 114 #endif  // CC_TREES_LAYER_SORTER_H_