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_ 115