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.
5 #ifndef CC_LAYER_SORTER_H_
6 #define CC_LAYER_SORTER_H_
8 #include "base/basictypes.h"
9 #include "base/hash_tables.h"
10 #include "cc/cc_export.h"
11 #include "cc/layer_impl.h"
12 #include "ui/gfx/point3_f.h"
13 #include "ui/gfx/quad_f.h"
14 #include "ui/gfx/rect_f.h"
15 #include "ui/gfx/vector3d_f.h"
17 #if defined(COMPILER_GCC)
23 namespace BASE_HASH_NAMESPACE
{
25 struct hash
<cc::GraphEdge
*> {
26 size_t operator()(cc::GraphEdge
* ptr
) const {
27 return hash
<size_t>()(reinterpret_cast<size_t>(ptr
));
30 } // namespace BASE_HASH_NAMESPACE
34 class WebTransformationMatrix
;
41 // Holds various useful properties derived from a layer's 3D outline.
42 struct CC_EXPORT LayerShape
{
44 LayerShape(float width
, float height
, const WebKit::WebTransformationMatrix
& drawTransform
);
47 float layerZFromProjectedPoint(const gfx::PointF
&) const;
49 gfx::Vector3dF layerNormal
;
50 gfx::Point3F transformOrigin
;
51 gfx::QuadF projectedQuad
;
52 gfx::RectF projectedBounds
;
56 explicit GraphNode(LayerImpl
* layerImpl
);
61 std::vector
<GraphEdge
*> incoming
;
62 std::vector
<GraphEdge
*> outgoing
;
63 float incomingEdgeWeight
;
67 GraphEdge(GraphNode
* fromNode
, GraphNode
* toNode
, float weight
)
81 class CC_EXPORT LayerSorter
{
86 typedef std::vector
<LayerImpl
*> LayerList
;
88 void sort(LayerList::iterator first
, LayerList::iterator last
);
90 enum ABCompareResult
{
96 static ABCompareResult
checkOverlap(LayerShape
*, LayerShape
*, float zThreshold
, float& weight
);
99 typedef std::vector
<GraphNode
> NodeList
;
100 typedef std::vector
<GraphEdge
> EdgeList
;
105 typedef base::hash_map
<GraphEdge
*, GraphEdge
*> EdgeMap
;
106 EdgeMap m_activeEdges
;
108 void createGraphNodes(LayerList::iterator first
, LayerList::iterator last
);
109 void createGraphEdges();
110 void removeEdgeFromList(GraphEdge
*, std::vector
<GraphEdge
*>&);
112 DISALLOW_COPY_AND_ASSIGN(LayerSorter
);
116 #endif // CC_LAYER_SORTER_H_