Home | History | Annotate | Download | only in trees 
      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(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_
    115