[chromium] Remove WebTransformationMatrix::mapPoint overrides
[WebKit-https.git] / Source / WebCore / platform / graphics / chromium / cc / CCMathUtil.cpp
1 /*
2  * Copyright (C) 2012 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1.  Redistributions of source code must retain the above copyright
8  *     notice, this list of conditions and the following disclaimer.
9  * 2.  Redistributions in binary form must reproduce the above copyright
10  *     notice, this list of conditions and the following disclaimer in the
11  *     documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
16  * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
17  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23  */
24
25 #include "config.h"
26
27 #include "cc/CCMathUtil.h"
28
29 #include "FloatPoint.h"
30 #include "FloatQuad.h"
31 #include "IntRect.h"
32 #include <public/WebTransformationMatrix.h>
33
34 using WebKit::WebTransformationMatrix;
35
36 namespace WebCore {
37
38 static HomogeneousCoordinate projectHomogeneousPoint(const WebTransformationMatrix& transform, const FloatPoint& p)
39 {
40     // In this case, the layer we are trying to project onto is perpendicular to ray
41     // (point p and z-axis direction) that we are trying to project. This happens when the
42     // layer is rotated so that it is infinitesimally thin, or when it is co-planar with
43     // the camera origin -- i.e. when the layer is invisible anyway.
44     if (!transform.m33())
45         return HomogeneousCoordinate(0, 0, 0, 1);
46
47     double x = p.x();
48     double y = p.y();
49     double z = -(transform.m13() * x + transform.m23() * y + transform.m43()) / transform.m33();
50     // implicit definition of w = 1;
51
52     double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41();
53     double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42();
54     double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43();
55     double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44();
56
57     return HomogeneousCoordinate(outX, outY, outZ, outW);
58 }
59
60 static HomogeneousCoordinate mapHomogeneousPoint(const WebTransformationMatrix& transform, const FloatPoint3D& p)
61 {
62     double x = p.x();
63     double y = p.y();
64     double z = p.z();
65     // implicit definition of w = 1;
66
67     double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41();
68     double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42();
69     double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43();
70     double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44();
71
72     return HomogeneousCoordinate(outX, outY, outZ, outW);
73 }
74
75 static HomogeneousCoordinate computeClippedPointForEdge(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2)
76 {
77     // Points h1 and h2 form a line in 4d, and any point on that line can be represented
78     // as an interpolation between h1 and h2:
79     //    p = (1-t) h1 + (t) h2
80     //
81     // We want to compute point p such that p.w == epsilon, where epsilon is a small
82     // non-zero number. (but the smaller the number is, the higher the risk of overflow)
83     // To do this, we solve for t in the following equation:
84     //    p.w = epsilon = (1-t) * h1.w + (t) * h2.w
85     //
86     // Once paramter t is known, the rest of p can be computed via p = (1-t) h1 + (t) h2.
87
88     // Technically this is a special case of the following assertion, but its a good idea to keep it an explicit sanity check here.
89     ASSERT(h2.w != h1.w);
90     // Exactly one of h1 or h2 (but not both) must be on the negative side of the w plane when this is called.
91     ASSERT(h1.shouldBeClipped() ^ h2.shouldBeClipped());
92
93     double w = 0.00001; // or any positive non-zero small epsilon
94
95     double t = (w - h1.w) / (h2.w - h1.w);
96
97     double x = (1-t) * h1.x + t * h2.x;
98     double y = (1-t) * h1.y + t * h2.y;
99     double z = (1-t) * h1.z + t * h2.z;
100
101     return HomogeneousCoordinate(x, y, z, w);
102 }
103
104 static inline void expandBoundsToIncludePoint(float& xmin, float& xmax, float& ymin, float& ymax, const FloatPoint& p)
105 {
106     xmin = std::min(p.x(), xmin);
107     xmax = std::max(p.x(), xmax);
108     ymin = std::min(p.y(), ymin);
109     ymax = std::max(p.y(), ymax);
110 }
111
112 static inline void addVertexToClippedQuad(const FloatPoint& newVertex, FloatPoint clippedQuad[8], int& numVerticesInClippedQuad)
113 {
114     clippedQuad[numVerticesInClippedQuad] = newVertex;
115     numVerticesInClippedQuad++;
116 }
117
118 IntRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, const IntRect& srcRect)
119 {
120     return enclosingIntRect(mapClippedRect(transform, FloatRect(srcRect)));
121 }
122
123 FloatRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, const FloatRect& srcRect)
124 {
125     if (transform.isIdentityOrTranslation()) {
126         FloatRect mappedRect(srcRect);
127         mappedRect.move(static_cast<float>(transform.m41()), static_cast<float>(transform.m42()));
128         return mappedRect;
129     }
130
131     // Apply the transform, but retain the result in homogeneous coordinates.
132     FloatQuad q = FloatQuad(FloatRect(srcRect));
133     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, q.p1());
134     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, q.p2());
135     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, q.p3());
136     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, q.p4());
137
138     return computeEnclosingClippedRect(h1, h2, h3, h4);
139 }
140
141 FloatRect CCMathUtil::projectClippedRect(const WebTransformationMatrix& transform, const FloatRect& srcRect)
142 {
143     // Perform the projection, but retain the result in homogeneous coordinates.
144     FloatQuad q = FloatQuad(FloatRect(srcRect));
145     HomogeneousCoordinate h1 = projectHomogeneousPoint(transform, q.p1());
146     HomogeneousCoordinate h2 = projectHomogeneousPoint(transform, q.p2());
147     HomogeneousCoordinate h3 = projectHomogeneousPoint(transform, q.p3());
148     HomogeneousCoordinate h4 = projectHomogeneousPoint(transform, q.p4());
149
150     return computeEnclosingClippedRect(h1, h2, h3, h4);
151 }
152
153 void CCMathUtil::mapClippedQuad(const WebTransformationMatrix& transform, const FloatQuad& srcQuad, FloatPoint clippedQuad[8], int& numVerticesInClippedQuad)
154 {
155     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, srcQuad.p1());
156     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, srcQuad.p2());
157     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, srcQuad.p3());
158     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, srcQuad.p4());
159
160     // The order of adding the vertices to the array is chosen so that clockwise / counter-clockwise orientation is retained.
161
162     numVerticesInClippedQuad = 0;
163
164     if (!h1.shouldBeClipped())
165         addVertexToClippedQuad(h1.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
166
167     if (h1.shouldBeClipped() ^ h2.shouldBeClipped())
168         addVertexToClippedQuad(computeClippedPointForEdge(h1, h2).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
169
170     if (!h2.shouldBeClipped())
171         addVertexToClippedQuad(h2.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
172
173     if (h2.shouldBeClipped() ^ h3.shouldBeClipped())
174         addVertexToClippedQuad(computeClippedPointForEdge(h2, h3).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
175
176     if (!h3.shouldBeClipped())
177         addVertexToClippedQuad(h3.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
178
179     if (h3.shouldBeClipped() ^ h4.shouldBeClipped())
180         addVertexToClippedQuad(computeClippedPointForEdge(h3, h4).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
181
182     if (!h4.shouldBeClipped())
183         addVertexToClippedQuad(h4.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
184
185     if (h4.shouldBeClipped() ^ h1.shouldBeClipped())
186         addVertexToClippedQuad(computeClippedPointForEdge(h4, h1).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
187
188     ASSERT(numVerticesInClippedQuad <= 8);
189 }
190
191 FloatRect CCMathUtil::computeEnclosingRectOfVertices(FloatPoint vertices[], int numVertices)
192 {
193     if (numVertices < 2)
194         return FloatRect();
195
196     float xmin = std::numeric_limits<float>::max();
197     float xmax = -std::numeric_limits<float>::max();
198     float ymin = std::numeric_limits<float>::max();
199     float ymax = -std::numeric_limits<float>::max();
200
201     for (int i = 0; i < numVertices; ++i)
202         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, vertices[i]);
203
204     return FloatRect(FloatPoint(xmin, ymin), FloatSize(xmax - xmin, ymax - ymin));
205 }
206
207 FloatRect CCMathUtil::computeEnclosingClippedRect(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2, const HomogeneousCoordinate& h3, const HomogeneousCoordinate& h4)
208 {
209     // This function performs clipping as necessary and computes the enclosing 2d
210     // FloatRect of the vertices. Doing these two steps simultaneously allows us to avoid
211     // the overhead of storing an unknown number of clipped vertices.
212
213     // If no vertices on the quad are clipped, then we can simply return the enclosing rect directly.
214     bool somethingClipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped();
215     if (!somethingClipped) {
216         FloatQuad mappedQuad = FloatQuad(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d());
217         return mappedQuad.boundingBox();
218     }
219
220     bool everythingClipped = h1.shouldBeClipped() && h2.shouldBeClipped() && h3.shouldBeClipped() && h4.shouldBeClipped();
221     if (everythingClipped)
222         return FloatRect();
223
224
225     float xmin = std::numeric_limits<float>::max();
226     float xmax = -std::numeric_limits<float>::max();
227     float ymin = std::numeric_limits<float>::max();
228     float ymax = -std::numeric_limits<float>::max();
229
230     if (!h1.shouldBeClipped())
231         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h1.cartesianPoint2d());
232
233     if (h1.shouldBeClipped() ^ h2.shouldBeClipped())
234         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h1, h2).cartesianPoint2d());
235
236     if (!h2.shouldBeClipped())
237         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h2.cartesianPoint2d());
238
239     if (h2.shouldBeClipped() ^ h3.shouldBeClipped())
240         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h2, h3).cartesianPoint2d());
241
242     if (!h3.shouldBeClipped())
243         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h3.cartesianPoint2d());
244
245     if (h3.shouldBeClipped() ^ h4.shouldBeClipped())
246         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h3, h4).cartesianPoint2d());
247
248     if (!h4.shouldBeClipped())
249         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h4.cartesianPoint2d());
250
251     if (h4.shouldBeClipped() ^ h1.shouldBeClipped())
252         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h4, h1).cartesianPoint2d());
253
254     return FloatRect(FloatPoint(xmin, ymin), FloatSize(xmax - xmin, ymax - ymin));
255 }
256
257 FloatQuad CCMathUtil::mapQuad(const WebTransformationMatrix& transform, const FloatQuad& q, bool& clipped)
258 {
259     if (transform.isIdentityOrTranslation()) {
260         FloatQuad mappedQuad(q);
261         mappedQuad.move(static_cast<float>(transform.m41()), static_cast<float>(transform.m42()));
262         clipped = false;
263         return mappedQuad;
264     }
265
266     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, q.p1());
267     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, q.p2());
268     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, q.p3());
269     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, q.p4());
270
271     clipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped();
272
273     // Result will be invalid if clipped == true. But, compute it anyway just in case, to emulate existing behavior.
274     return FloatQuad(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d());
275 }
276
277 FloatPoint CCMathUtil::mapPoint(const WebTransformationMatrix& transform, const FloatPoint& p, bool& clipped)
278 {
279     HomogeneousCoordinate h = mapHomogeneousPoint(transform, p);
280
281     if (h.w > 0) {
282         clipped = false;
283         return h.cartesianPoint2d();
284     }
285
286     // The cartesian coordinates will be invalid after dividing by w.
287     clipped = true;
288
289     // Avoid dividing by w if w == 0.
290     if (!h.w)
291         return FloatPoint();
292
293     // This return value will be invalid because clipped == true, but (1) users of this
294     // code should be ignoring the return value when clipped == true anyway, and (2) this
295     // behavior is more consistent with existing behavior of WebKit transforms if the user
296     // really does not ignore the return value.
297     return h.cartesianPoint2d();
298 }
299
300 FloatPoint3D CCMathUtil::mapPoint(const WebTransformationMatrix& transform, const FloatPoint3D& p, bool& clipped)
301 {
302     HomogeneousCoordinate h = mapHomogeneousPoint(transform, p);
303
304     if (h.w > 0) {
305         clipped = false;
306         return h.cartesianPoint3d();
307     }
308
309     // The cartesian coordinates will be invalid after dividing by w.
310     clipped = true;
311
312     // Avoid dividing by w if w == 0.
313     if (!h.w)
314         return FloatPoint3D();
315
316     // This return value will be invalid because clipped == true, but (1) users of this
317     // code should be ignoring the return value when clipped == true anyway, and (2) this
318     // behavior is more consistent with existing behavior of WebKit transforms if the user
319     // really does not ignore the return value.
320     return h.cartesianPoint3d();
321 }
322
323 FloatQuad CCMathUtil::projectQuad(const WebTransformationMatrix& transform, const FloatQuad& q, bool& clipped)
324 {
325     FloatQuad projectedQuad;
326     bool clippedPoint;
327     projectedQuad.setP1(projectPoint(transform, q.p1(), clippedPoint));
328     clipped = clippedPoint;
329     projectedQuad.setP2(projectPoint(transform, q.p2(), clippedPoint));
330     clipped |= clippedPoint;
331     projectedQuad.setP3(projectPoint(transform, q.p3(), clippedPoint));
332     clipped |= clippedPoint;
333     projectedQuad.setP4(projectPoint(transform, q.p4(), clippedPoint));
334     clipped |= clippedPoint;
335
336     return projectedQuad;
337 }
338
339 FloatPoint CCMathUtil::projectPoint(const WebTransformationMatrix& transform, const FloatPoint& p, bool& clipped)
340 {
341     HomogeneousCoordinate h = projectHomogeneousPoint(transform, p);
342
343     if (h.w > 0) {
344         // The cartesian coordinates will be valid in this case.
345         clipped = false;
346         return h.cartesianPoint2d();
347     }
348
349     // The cartesian coordinates will be invalid after dividing by w.
350     clipped = true;
351
352     // Avoid dividing by w if w == 0.
353     if (!h.w)
354         return FloatPoint();
355
356     // This return value will be invalid because clipped == true, but (1) users of this
357     // code should be ignoring the return value when clipped == true anyway, and (2) this
358     // behavior is more consistent with existing behavior of WebKit transforms if the user
359     // really does not ignore the return value.
360     return h.cartesianPoint2d();
361 }
362
363 } // namespace WebCore