12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright 2011 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef CC_TREES_LAYER_SORTER_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define CC_TREES_LAYER_SORTER_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <vector> 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "cc/base/cc_export.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "cc/layers/layer_impl.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/point3_f.h" 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/quad_f.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/rect_f.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/vector3d_f.h" 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#if defined(COMPILER_GCC) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace cc { struct GraphEdge; } 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace BASE_HASH_NAMESPACE { 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <> 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct hash<cc::GraphEdge*> { 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t operator()(cc::GraphEdge* ptr) const { 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return hash<size_t>()(reinterpret_cast<size_t>(ptr)); 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace BASE_HASH_NAMESPACE 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // COMPILER 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace gfx { 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class Transform; 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace cc { 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct GraphEdge; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Holds various useful properties derived from a layer's 3D outline. 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct CC_EXPORT LayerShape { 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerShape(); 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerShape(float width, float height, const gfx::Transform& draw_transform); 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~LayerShape(); 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) float LayerZFromProjectedPoint(const gfx::PointF& p) const; 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Vector3dF layer_normal; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Point3F transform_origin; 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::QuadF projected_quad; 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::RectF projected_bounds; 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct GraphNode { 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit GraphNode(LayerImpl* layer_impl); 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~GraphNode(); 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerImpl* layer; 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerShape shape; 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<GraphEdge*> incoming; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<GraphEdge*> outgoing; 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float incoming_edge_weight; 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct GraphEdge { 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GraphEdge(GraphNode* from_node, GraphNode* to_node, float weight) 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : from(from_node), 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) to(to_node), 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) weight(weight) {} 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GraphNode* from; 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GraphNode* to; 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float weight; 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class CC_EXPORT LayerSorter { 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerSorter(); 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~LayerSorter(); 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void Sort(LayerImplList::iterator first, LayerImplList::iterator last); 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) enum ABCompareResult { 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ABeforeB, 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BBeforeA, 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) None 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static ABCompareResult CheckOverlap(LayerShape* a, 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LayerShape* b, 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float z_threshold, 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float* weight); 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<GraphNode> NodeList; 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<GraphEdge> EdgeList; 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NodeList nodes_; 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EdgeList edges_; 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float z_range_; 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef base::hash_map<GraphEdge*, GraphEdge*> EdgeMap; 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) EdgeMap active_edges_; 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 105c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void CreateGraphNodes(LayerImplList::iterator first, 106c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) LayerImplList::iterator last); 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void CreateGraphEdges(); 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void RemoveEdgeFromList(GraphEdge* graph, std::vector<GraphEdge*>* list); 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(LayerSorter); 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 113c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace cc 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // CC_TREES_LAYER_SORTER_H_ 115