OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef GeometryMapper_h | 5 #ifndef GeometryMapper_h |
6 #define GeometryMapper_h | 6 #define GeometryMapper_h |
7 | 7 |
8 #include "platform/geometry/FloatRect.h" | 8 #include "platform/geometry/FloatRect.h" |
9 #include "platform/graphics/paint/PropertyTreeState.h" | 9 #include "platform/graphics/paint/GeometryPropertyTreeState.h" |
10 #include "platform/transforms/TransformationMatrix.h" | 10 #include "platform/transforms/TransformationMatrix.h" |
11 #include "wtf/HashMap.h" | 11 #include "wtf/HashMap.h" |
12 | 12 |
13 namespace blink { | 13 namespace blink { |
14 | 14 |
15 struct PrecomputedDataForAncestor { | 15 struct PrecomputedDataForAncestor { |
16 // Maps from a transform node that is a descendant of the ancestor to the co
mbined | 16 // Maps from a transform node that is a descendant of the ancestor to the co
mbined |
17 // transform between the descendant's and the ancestor's coordinate space. | 17 // transform between the descendant's and the ancestor's coordinate space. |
18 HashMap<const TransformPaintPropertyNode*, TransformationMatrix> toAncestorT
ransforms; | 18 HashMap<const TransformPaintPropertyNode*, TransformationMatrix> toAncestorT
ransforms; |
19 | 19 |
20 // Maps from a descendant clip node to its equivalent "clip visual rect" in
the space of the ancestor. | 20 // Maps from a descendant clip node to its equivalent "clip visual rect" in
the space of the ancestor. |
21 // The clip visual rect is defined as the intersection of all clips between
the descendant | 21 // The clip visual rect is defined as the intersection of all clips between
the descendant |
22 // and the ancestor (*not* including the ancestor) in the clip tree, individ
ually transformed from their | 22 // and the ancestor (*not* including the ancestor) in the clip tree, individ
ually transformed from their |
23 // localTransformSpace into the ancestor's localTransformSpace. | 23 // localTransformSpace into the ancestor's localTransformSpace. |
24 HashMap<const ClipPaintPropertyNode*, FloatRect> toAncestorClipRects; | 24 HashMap<const ClipPaintPropertyNode*, FloatRect> toAncestorClipRects; |
25 | 25 |
26 static std::unique_ptr<PrecomputedDataForAncestor> create() | 26 static std::unique_ptr<PrecomputedDataForAncestor> create() |
27 { | 27 { |
28 return wrapUnique(new PrecomputedDataForAncestor()); | 28 return wrapUnique(new PrecomputedDataForAncestor()); |
29 } | 29 } |
30 }; | 30 }; |
31 | 31 |
32 // GeometryMapper is a helper class for fast computations of transformed and vis
ual rects in different | 32 // GeometryMapper is a helper class for fast computations of transformed and vis
ual rects in |
33 // PropertyTreeStates. The design document has a number of details on use cases,
algorithmic definitions, | 33 // different GeometryPropertyTreeStates. The design document has a number of det
ails on use cases, |
34 // and running times. | 34 // algorithmic definitions, and running times. |
35 // | 35 // |
36 // NOTE: a GeometryMapper object is only valid for property trees that do not ch
ange. If any mutation occurs, | 36 // NOTE: A GeometryMapper object is only valid for property trees that do not ch
ange. If any |
37 // a new GeometryMapper object must be allocated corresponding to the new state. | 37 // mutation occurs, a new GeometryMapper object must be allocated corresponding
to the new state. |
38 // | 38 // |
39 // Design document: http://bit.ly/28P4FDA | 39 // Design document: http://bit.ly/28P4FDA |
40 // | 40 // |
41 // TODO(chrishtr): take effect and scroll trees into account. | 41 // TODO(chrishtr): take effect tree into account. |
42 class PLATFORM_EXPORT GeometryMapper { | 42 class PLATFORM_EXPORT GeometryMapper { |
43 public: | 43 public: |
44 GeometryMapper() {} | 44 GeometryMapper() {} |
45 // The runtime of m calls among localToVisualRectInAncestorSpace, localToAnc
estorRect or ancestorToLocalRect | 45 // The runtime of m calls among localToVisualRectInAncestorSpace, localToAnc
estorRect or ancestorToLocalRect |
46 // with the same |ancestorState| parameter is guaranteed to be O(n + m), wh
ere n is the number of transform and clip | 46 // with the same |ancestorState| parameter is guaranteed to be O(n + m), wh
ere n is the number of transform and clip |
47 // nodes in their respective property trees. | 47 // nodes in their respective property trees. |
48 | 48 |
49 // If the clips and transforms of |sourceState| are equal to or descendants
of those of |destinationState|, returns | 49 // If the clips and transforms of |sourceState| are equal to or descendants
of those of |destinationState|, returns |
50 // the same value as localToVisualRectInAncestorSpace. Otherwise, maps the i
nput rect to the transform state which is | 50 // the same value as localToVisualRectInAncestorSpace. Otherwise, maps the i
nput rect to the transform state which is |
51 // the least common ancestor of |sourceState.transform| and |destinationStat
e.transform|, then multiplies it by | 51 // the least common ancestor of |sourceState.transform| and |destinationStat
e.transform|, then multiplies it by |
52 // the the inverse transform mapping from the least common ancestor to |dest
inationState.transform|. | 52 // the the inverse transform mapping from the least common ancestor to |dest
inationState.transform|. |
53 // | 53 // |
54 // If that inverse transform is not invertible, sets |success| to false and
returns the input rect. Otherwise, sets | 54 // If that inverse transform is not invertible, sets |success| to false and
returns the input rect. Otherwise, sets |
55 // |success| to true. | 55 // |success| to true. |
56 FloatRect mapToVisualRectInDestinationSpace(const FloatRect&, | 56 FloatRect mapToVisualRectInDestinationSpace(const FloatRect&, |
57 const PropertyTreeState& sourceState, | 57 const GeometryPropertyTreeState& sourceState, |
58 const PropertyTreeState& destinationState, | 58 const GeometryPropertyTreeState& destinationState, |
59 bool& success); | 59 bool& success); |
60 | 60 |
61 // Same as mapToVisualRectInDestinationSpace() except that *no* clip is appl
ied. | 61 // Same as mapToVisualRectInDestinationSpace() except that *no* clip is appl
ied. |
62 FloatRect mapRectToDestinationSpace(const FloatRect&, | 62 FloatRect mapRectToDestinationSpace(const FloatRect&, |
63 const PropertyTreeState& sourceState, | 63 const GeometryPropertyTreeState& sourceState, |
64 const PropertyTreeState& destinationState, | 64 const GeometryPropertyTreeState& destinationState, |
65 bool& success); | 65 bool& success); |
66 | 66 |
67 // Maps from a rect in |localTransformSpace| to its visual rect in |ancestor
State|. This is computed | 67 // Maps from a rect in |localTransformSpace| to its visual rect in |ancestor
State|. This is computed |
68 // by multiplying the rect by its combined transform between |localTransform
Space| and |ancestorSpace|, | 68 // by multiplying the rect by its combined transform between |localTransform
Space| and |ancestorSpace|, |
69 // then flattening into 2D space, then intersecting by the "clip visual rect
" for |localTransformState|'s clips. | 69 // then flattening into 2D space, then intersecting by the "clip visual rect
" for |localTransformState|'s clips. |
70 // See above for the definition of "clip visual rect". | 70 // See above for the definition of "clip visual rect". |
71 // | 71 // |
72 // Note that the clip of |ancestorState| is *not* applied. | 72 // Note that the clip of |ancestorState| is *not* applied. |
73 // | 73 // |
74 // If any of the paint property tree nodes in |localTransformState| are not
equal | 74 // If any of the paint property tree nodes in |localTransformState| are not
equal |
75 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, | 75 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, |
76 // sets |success| to true. | 76 // sets |success| to true. |
77 FloatRect localToVisualRectInAncestorSpace(const FloatRect&, | 77 FloatRect localToVisualRectInAncestorSpace(const FloatRect&, |
78 const PropertyTreeState& localTransformState, | 78 const GeometryPropertyTreeState& localTransformState, |
79 const PropertyTreeState& ancestorState, | 79 const GeometryPropertyTreeState& ancestorState, |
80 bool& success); | 80 bool& success); |
81 | 81 |
82 // Maps from a rect in |localTransformSpace| to its transformed rect in |anc
estorSpace|. This is computed | 82 // Maps from a rect in |localTransformSpace| to its transformed rect in |anc
estorSpace|. This is computed |
83 // by multiplying the rect by the combined transform between |localTransform
State| and |ancestorState|, | 83 // by multiplying the rect by the combined transform between |localTransform
State| and |ancestorState|, |
84 // then flattening into 2D space. | 84 // then flattening into 2D space. |
85 // | 85 // |
86 // If any of the paint property tree nodes in |localTransformState| are not
equal | 86 // If any of the paint property tree nodes in |localTransformState| are not
equal |
87 // to or a descendant of that in |ancestorState|, returns the passed-in rec
and sets |success| to false. Otherwise, | 87 // to or a descendant of that in |ancestorState|, returns the passed-in rec
and sets |success| to false. Otherwise, |
88 // sets |success| to true. | 88 // sets |success| to true. |
89 // | 89 // |
90 // If any of the paint property tree nodes in |localTransformState| are not
equal | 90 // If any of the paint property tree nodes in |localTransformState| are not
equal |
91 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, | 91 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, |
92 // sets |success| to true. | 92 // sets |success| to true. |
93 FloatRect localToAncestorRect(const FloatRect&, | 93 FloatRect localToAncestorRect(const FloatRect&, |
94 const PropertyTreeState& localTransformState, | 94 const GeometryPropertyTreeState& localTransformState, |
95 const PropertyTreeState& ancestorState, | 95 const GeometryPropertyTreeState& ancestorState, |
96 bool& success); | 96 bool& success); |
97 | 97 |
98 // Maps from a rect in |ancestorSpace| to its transformed rect in |localTran
sformSpace|. This is computed | 98 // Maps from a rect in |ancestorSpace| to its transformed rect in |localTran
sformSpace|. This is computed |
99 // by multiplying the rect by the inverse combined transform between |localT
ransformState| and |ancestorState|, | 99 // by multiplying the rect by the inverse combined transform between |localT
ransformState| and |ancestorState|, |
100 // if the transform is invertible. | 100 // if the transform is invertible. |
101 // | 101 // |
102 // If any of the paint property tree nodes in |localTransformState| are not
equal | 102 // If any of the paint property tree nodes in |localTransformState| are not
equal |
103 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, | 103 // to or a descendant of that in |ancestorState|, returns the passed-in rect
and sets |success| to false. Otherwise, |
104 // sets |success| to true. | 104 // sets |success| to true. |
105 FloatRect ancestorToLocalRect(const FloatRect&, | 105 FloatRect ancestorToLocalRect(const FloatRect&, |
106 const PropertyTreeState& localTransformState, | 106 const GeometryPropertyTreeState& localTransformState, |
107 const PropertyTreeState& ancestorState, | 107 const GeometryPropertyTreeState& ancestorState, |
108 bool& success); | 108 bool& success); |
109 | 109 |
110 private: | 110 private: |
111 // Used by mapToVisualRectInDestinationSpace() after fast mapping (assuming
destination is an ancestor of source) failed. | 111 // Used by mapToVisualRectInDestinationSpace() after fast mapping (assuming
destination is an ancestor of source) failed. |
112 FloatRect slowMapToVisualRectInDestinationSpace(const FloatRect&, | 112 FloatRect slowMapToVisualRectInDestinationSpace(const FloatRect&, |
113 const PropertyTreeState& sourceState, | 113 const GeometryPropertyTreeState& sourceState, |
114 const PropertyTreeState& destinationState, | 114 const GeometryPropertyTreeState& destinationState, |
115 bool& success); | 115 bool& success); |
116 | 116 |
117 // Used by mapRectToDestinationSpace() after fast mapping (assuming destinat
ion is an ancestor of source) failed. | 117 // Used by mapRectToDestinationSpace() after fast mapping (assuming destinat
ion is an ancestor of source) failed. |
118 FloatRect slowMapRectToDestinationSpace(const FloatRect&, | 118 FloatRect slowMapRectToDestinationSpace(const FloatRect&, |
119 const PropertyTreeState& sourceState, | 119 const GeometryPropertyTreeState& sourceState, |
120 const PropertyTreeState& destinationState, | 120 const GeometryPropertyTreeState& destinationState, |
121 bool& success); | 121 bool& success); |
122 | 122 |
123 // Returns the matrix used in |LocalToAncestorRect|. Sets |success| to fails
e iff |localTransformNode| is not | 123 // Returns the matrix used in |LocalToAncestorRect|. Sets |success| to fails
e iff |localTransformNode| is not |
124 // equal to or a descendant of |ancestorState.transform|. | 124 // equal to or a descendant of |ancestorState.transform|. |
125 const TransformationMatrix& localToAncestorMatrix( | 125 const TransformationMatrix& localToAncestorMatrix( |
126 const TransformPaintPropertyNode* localTransformNode, | 126 const TransformPaintPropertyNode* localTransformNode, |
127 const PropertyTreeState& ancestorState, | 127 const GeometryPropertyTreeState& ancestorState, |
128 bool& success); | 128 bool& success); |
129 | 129 |
130 // Returns the "clip visual rect" between |localTransformState| and |ancesto
rState|. See above for the definition | 130 // Returns the "clip visual rect" between |localTransformState| and |ancesto
rState|. See above for the definition |
131 // of "clip visual rect". | 131 // of "clip visual rect". |
132 FloatRect localToAncestorClipRect( | 132 FloatRect localToAncestorClipRect( |
133 const PropertyTreeState& localTransformState, | 133 const GeometryPropertyTreeState& localTransformState, |
134 const PropertyTreeState& ancestorState, | 134 const GeometryPropertyTreeState& ancestorState, |
135 bool& success); | 135 bool& success); |
136 | 136 |
137 // Returns the precomputed data if already set, or adds and memoizes a new P
recomputedDataForAncestor otherwise. | 137 // Returns the precomputed data if already set, or adds and memoizes a new P
recomputedDataForAncestor otherwise. |
138 PrecomputedDataForAncestor& getPrecomputedDataForAncestor(const PropertyTree
State&); | 138 PrecomputedDataForAncestor& getPrecomputedDataForAncestor(const GeometryProp
ertyTreeState&); |
139 | 139 |
140 // Returns the least common ancestor in the transform tree. | 140 // Returns the least common ancestor in the transform tree. |
141 PassRefPtr<TransformPaintPropertyNode> leastCommonAncestor(PassRefPtr<Transf
ormPaintPropertyNode>, PassRefPtr<TransformPaintPropertyNode>); | 141 PassRefPtr<TransformPaintPropertyNode> leastCommonAncestor(PassRefPtr<Transf
ormPaintPropertyNode>, PassRefPtr<TransformPaintPropertyNode>); |
142 | 142 |
143 friend class GeometryMapperTest; | 143 friend class GeometryMapperTest; |
144 | 144 |
145 HashMap<const TransformPaintPropertyNode*, std::unique_ptr<PrecomputedDataFo
rAncestor>> m_data; | 145 HashMap<const TransformPaintPropertyNode*, std::unique_ptr<PrecomputedDataFo
rAncestor>> m_data; |
146 | 146 |
147 const TransformationMatrix m_identity; | 147 const TransformationMatrix m_identity; |
148 | 148 |
149 DISALLOW_COPY_AND_ASSIGN(GeometryMapper); | 149 DISALLOW_COPY_AND_ASSIGN(GeometryMapper); |
150 }; | 150 }; |
151 | 151 |
152 } // namespace blink | 152 } // namespace blink |
153 | 153 |
154 #endif // GeometryMapper_h | 154 #endif // GeometryMapper_h |
OLD | NEW |