1// Copyright 2012 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#include "cc/base/math_util.h"
6
7#include <algorithm>
8#include <cmath>
9#include <limits>
10
11#include "base/debug/trace_event_argument.h"
12#include "base/values.h"
13#include "ui/gfx/quad_f.h"
14#include "ui/gfx/rect.h"
15#include "ui/gfx/rect_conversions.h"
16#include "ui/gfx/rect_f.h"
17#include "ui/gfx/transform.h"
18#include "ui/gfx/vector2d_f.h"
19
20namespace cc {
21
22const double MathUtil::kPiDouble = 3.14159265358979323846;
23const float MathUtil::kPiFloat = 3.14159265358979323846f;
24
25static HomogeneousCoordinate ProjectHomogeneousPoint(
26    const gfx::Transform& transform,
27    const gfx::PointF& p) {
28  // In this case, the layer we are trying to project onto is perpendicular to
29  // ray (point p and z-axis direction) that we are trying to project. This
30  // happens when the layer is rotated so that it is infinitesimally thin, or
31  // when it is co-planar with the camera origin -- i.e. when the layer is
32  // invisible anyway.
33  if (!transform.matrix().get(2, 2))
34    return HomogeneousCoordinate(0.0, 0.0, 0.0, 1.0);
35
36  SkMScalar z = -(transform.matrix().get(2, 0) * p.x() +
37             transform.matrix().get(2, 1) * p.y() +
38             transform.matrix().get(2, 3)) /
39             transform.matrix().get(2, 2);
40  HomogeneousCoordinate result(p.x(), p.y(), z, 1.0);
41  transform.matrix().mapMScalars(result.vec, result.vec);
42  return result;
43}
44
45static HomogeneousCoordinate ProjectHomogeneousPoint(
46    const gfx::Transform& transform,
47    const gfx::PointF& p,
48    bool* clipped) {
49  HomogeneousCoordinate h = ProjectHomogeneousPoint(transform, p);
50  *clipped = h.w() <= 0;
51  return h;
52}
53
54static HomogeneousCoordinate MapHomogeneousPoint(
55    const gfx::Transform& transform,
56    const gfx::Point3F& p) {
57  HomogeneousCoordinate result(p.x(), p.y(), p.z(), 1.0);
58  transform.matrix().mapMScalars(result.vec, result.vec);
59  return result;
60}
61
62static HomogeneousCoordinate ComputeClippedPointForEdge(
63    const HomogeneousCoordinate& h1,
64    const HomogeneousCoordinate& h2) {
65  // Points h1 and h2 form a line in 4d, and any point on that line can be
66  // represented as an interpolation between h1 and h2:
67  //    p = (1-t) h1 + (t) h2
68  //
69  // We want to compute point p such that p.w == epsilon, where epsilon is a
70  // small non-zero number. (but the smaller the number is, the higher the risk
71  // of overflow)
72  // To do this, we solve for t in the following equation:
73  //    p.w = epsilon = (1-t) * h1.w + (t) * h2.w
74  //
75  // Once paramter t is known, the rest of p can be computed via
76  //    p = (1-t) h1 + (t) h2.
77
78  // Technically this is a special case of the following assertion, but its a
79  // good idea to keep it an explicit sanity check here.
80  DCHECK_NE(h2.w(), h1.w());
81  // Exactly one of h1 or h2 (but not both) must be on the negative side of the
82  // w plane when this is called.
83  DCHECK(h1.ShouldBeClipped() ^ h2.ShouldBeClipped());
84
85  // ...or any positive non-zero small epsilon
86  SkMScalar w = 0.00001f;
87  SkMScalar t = (w - h1.w()) / (h2.w() - h1.w());
88
89  SkMScalar x = (SK_MScalar1 - t) * h1.x() + t * h2.x();
90  SkMScalar y = (SK_MScalar1 - t) * h1.y() + t * h2.y();
91  SkMScalar z = (SK_MScalar1 - t) * h1.z() + t * h2.z();
92
93  return HomogeneousCoordinate(x, y, z, w);
94}
95
96static inline void ExpandBoundsToIncludePoint(float* xmin,
97                                              float* xmax,
98                                              float* ymin,
99                                              float* ymax,
100                                              const gfx::PointF& p) {
101  *xmin = std::min(p.x(), *xmin);
102  *xmax = std::max(p.x(), *xmax);
103  *ymin = std::min(p.y(), *ymin);
104  *ymax = std::max(p.y(), *ymax);
105}
106
107static inline void AddVertexToClippedQuad(const gfx::PointF& new_vertex,
108                                          gfx::PointF clipped_quad[8],
109                                          int* num_vertices_in_clipped_quad) {
110  clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
111  (*num_vertices_in_clipped_quad)++;
112}
113
114static inline void AddVertexToClippedQuad3d(const gfx::Point3F& new_vertex,
115                                            gfx::Point3F clipped_quad[8],
116                                            int* num_vertices_in_clipped_quad) {
117  clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
118  (*num_vertices_in_clipped_quad)++;
119}
120
121gfx::Rect MathUtil::MapEnclosingClippedRect(const gfx::Transform& transform,
122                                            const gfx::Rect& src_rect) {
123  if (transform.IsIdentityOrIntegerTranslation()) {
124    gfx::Vector2d offset(static_cast<int>(transform.matrix().getFloat(0, 3)),
125                         static_cast<int>(transform.matrix().getFloat(1, 3)));
126    return src_rect + offset;
127  }
128  return gfx::ToEnclosingRect(MapClippedRect(transform, gfx::RectF(src_rect)));
129}
130
131gfx::RectF MathUtil::MapClippedRect(const gfx::Transform& transform,
132                                    const gfx::RectF& src_rect) {
133  if (transform.IsIdentityOrTranslation()) {
134    gfx::Vector2dF offset(transform.matrix().getFloat(0, 3),
135                          transform.matrix().getFloat(1, 3));
136    return src_rect + offset;
137  }
138
139  // Apply the transform, but retain the result in homogeneous coordinates.
140
141  SkMScalar quad[4 * 2];  // input: 4 x 2D points
142  quad[0] = src_rect.x();
143  quad[1] = src_rect.y();
144  quad[2] = src_rect.right();
145  quad[3] = src_rect.y();
146  quad[4] = src_rect.right();
147  quad[5] = src_rect.bottom();
148  quad[6] = src_rect.x();
149  quad[7] = src_rect.bottom();
150
151  SkMScalar result[4 * 4];  // output: 4 x 4D homogeneous points
152  transform.matrix().map2(quad, 4, result);
153
154  HomogeneousCoordinate hc0(result[0], result[1], result[2], result[3]);
155  HomogeneousCoordinate hc1(result[4], result[5], result[6], result[7]);
156  HomogeneousCoordinate hc2(result[8], result[9], result[10], result[11]);
157  HomogeneousCoordinate hc3(result[12], result[13], result[14], result[15]);
158  return ComputeEnclosingClippedRect(hc0, hc1, hc2, hc3);
159}
160
161gfx::Rect MathUtil::ProjectEnclosingClippedRect(const gfx::Transform& transform,
162                                                const gfx::Rect& src_rect) {
163  if (transform.IsIdentityOrIntegerTranslation()) {
164    gfx::Vector2d offset(static_cast<int>(transform.matrix().getFloat(0, 3)),
165                         static_cast<int>(transform.matrix().getFloat(1, 3)));
166    return src_rect + offset;
167  }
168  return gfx::ToEnclosingRect(
169      ProjectClippedRect(transform, gfx::RectF(src_rect)));
170}
171
172gfx::RectF MathUtil::ProjectClippedRect(const gfx::Transform& transform,
173                                        const gfx::RectF& src_rect) {
174  if (transform.IsIdentityOrTranslation()) {
175    gfx::Vector2dF offset(transform.matrix().getFloat(0, 3),
176                          transform.matrix().getFloat(1, 3));
177    return src_rect + offset;
178  }
179
180  // Perform the projection, but retain the result in homogeneous coordinates.
181  gfx::QuadF q = gfx::QuadF(src_rect);
182  HomogeneousCoordinate h1 = ProjectHomogeneousPoint(transform, q.p1());
183  HomogeneousCoordinate h2 = ProjectHomogeneousPoint(transform, q.p2());
184  HomogeneousCoordinate h3 = ProjectHomogeneousPoint(transform, q.p3());
185  HomogeneousCoordinate h4 = ProjectHomogeneousPoint(transform, q.p4());
186
187  return ComputeEnclosingClippedRect(h1, h2, h3, h4);
188}
189
190gfx::Rect MathUtil::MapEnclosedRectWith2dAxisAlignedTransform(
191    const gfx::Transform& transform,
192    const gfx::Rect& rect) {
193  DCHECK(transform.Preserves2dAxisAlignment());
194
195  if (transform.IsIdentityOrIntegerTranslation()) {
196    gfx::Vector2d offset(static_cast<int>(transform.matrix().getFloat(0, 3)),
197                         static_cast<int>(transform.matrix().getFloat(1, 3)));
198    return rect + offset;
199  }
200  if (transform.IsIdentityOrTranslation()) {
201    gfx::Vector2dF offset(transform.matrix().getFloat(0, 3),
202                          transform.matrix().getFloat(1, 3));
203    return gfx::ToEnclosedRect(rect + offset);
204  }
205
206  SkMScalar quad[2 * 2];  // input: 2 x 2D points
207  quad[0] = rect.x();
208  quad[1] = rect.y();
209  quad[2] = rect.right();
210  quad[3] = rect.bottom();
211
212  SkMScalar result[4 * 2];  // output: 2 x 4D homogeneous points
213  transform.matrix().map2(quad, 2, result);
214
215  HomogeneousCoordinate hc0(result[0], result[1], result[2], result[3]);
216  HomogeneousCoordinate hc1(result[4], result[5], result[6], result[7]);
217  DCHECK(!hc0.ShouldBeClipped());
218  DCHECK(!hc1.ShouldBeClipped());
219
220  gfx::PointF top_left(hc0.CartesianPoint2d());
221  gfx::PointF bottom_right(hc1.CartesianPoint2d());
222  return gfx::ToEnclosedRect(gfx::BoundingRect(top_left, bottom_right));
223}
224
225void MathUtil::MapClippedQuad(const gfx::Transform& transform,
226                              const gfx::QuadF& src_quad,
227                              gfx::PointF clipped_quad[8],
228                              int* num_vertices_in_clipped_quad) {
229  HomogeneousCoordinate h1 =
230      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p1()));
231  HomogeneousCoordinate h2 =
232      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p2()));
233  HomogeneousCoordinate h3 =
234      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p3()));
235  HomogeneousCoordinate h4 =
236      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p4()));
237
238  // The order of adding the vertices to the array is chosen so that
239  // clockwise / counter-clockwise orientation is retained.
240
241  *num_vertices_in_clipped_quad = 0;
242
243  if (!h1.ShouldBeClipped()) {
244    AddVertexToClippedQuad(
245        h1.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
246  }
247
248  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped()) {
249    AddVertexToClippedQuad(
250        ComputeClippedPointForEdge(h1, h2).CartesianPoint2d(),
251        clipped_quad,
252        num_vertices_in_clipped_quad);
253  }
254
255  if (!h2.ShouldBeClipped()) {
256    AddVertexToClippedQuad(
257        h2.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
258  }
259
260  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped()) {
261    AddVertexToClippedQuad(
262        ComputeClippedPointForEdge(h2, h3).CartesianPoint2d(),
263        clipped_quad,
264        num_vertices_in_clipped_quad);
265  }
266
267  if (!h3.ShouldBeClipped()) {
268    AddVertexToClippedQuad(
269        h3.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
270  }
271
272  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped()) {
273    AddVertexToClippedQuad(
274        ComputeClippedPointForEdge(h3, h4).CartesianPoint2d(),
275        clipped_quad,
276        num_vertices_in_clipped_quad);
277  }
278
279  if (!h4.ShouldBeClipped()) {
280    AddVertexToClippedQuad(
281        h4.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
282  }
283
284  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
285    AddVertexToClippedQuad(
286        ComputeClippedPointForEdge(h4, h1).CartesianPoint2d(),
287        clipped_quad,
288        num_vertices_in_clipped_quad);
289  }
290
291  DCHECK_LE(*num_vertices_in_clipped_quad, 8);
292}
293
294bool MathUtil::MapClippedQuad3d(const gfx::Transform& transform,
295                                const gfx::QuadF& src_quad,
296                                gfx::Point3F clipped_quad[8],
297                                int* num_vertices_in_clipped_quad) {
298  HomogeneousCoordinate h1 =
299      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p1()));
300  HomogeneousCoordinate h2 =
301      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p2()));
302  HomogeneousCoordinate h3 =
303      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p3()));
304  HomogeneousCoordinate h4 =
305      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p4()));
306
307  // The order of adding the vertices to the array is chosen so that
308  // clockwise / counter-clockwise orientation is retained.
309
310  *num_vertices_in_clipped_quad = 0;
311
312  if (!h1.ShouldBeClipped()) {
313    AddVertexToClippedQuad3d(
314        h1.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
315  }
316
317  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped()) {
318    AddVertexToClippedQuad3d(
319        ComputeClippedPointForEdge(h1, h2).CartesianPoint3d(),
320        clipped_quad,
321        num_vertices_in_clipped_quad);
322  }
323
324  if (!h2.ShouldBeClipped()) {
325    AddVertexToClippedQuad3d(
326        h2.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
327  }
328
329  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped()) {
330    AddVertexToClippedQuad3d(
331        ComputeClippedPointForEdge(h2, h3).CartesianPoint3d(),
332        clipped_quad,
333        num_vertices_in_clipped_quad);
334  }
335
336  if (!h3.ShouldBeClipped()) {
337    AddVertexToClippedQuad3d(
338        h3.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
339  }
340
341  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped()) {
342    AddVertexToClippedQuad3d(
343        ComputeClippedPointForEdge(h3, h4).CartesianPoint3d(),
344        clipped_quad,
345        num_vertices_in_clipped_quad);
346  }
347
348  if (!h4.ShouldBeClipped()) {
349    AddVertexToClippedQuad3d(
350        h4.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
351  }
352
353  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
354    AddVertexToClippedQuad3d(
355        ComputeClippedPointForEdge(h4, h1).CartesianPoint3d(),
356        clipped_quad,
357        num_vertices_in_clipped_quad);
358  }
359
360  DCHECK_LE(*num_vertices_in_clipped_quad, 8);
361  return (*num_vertices_in_clipped_quad >= 4);
362}
363
364gfx::RectF MathUtil::ComputeEnclosingRectOfVertices(
365    const gfx::PointF vertices[],
366    int num_vertices) {
367  if (num_vertices < 2)
368    return gfx::RectF();
369
370  float xmin = std::numeric_limits<float>::max();
371  float xmax = -std::numeric_limits<float>::max();
372  float ymin = std::numeric_limits<float>::max();
373  float ymax = -std::numeric_limits<float>::max();
374
375  for (int i = 0; i < num_vertices; ++i)
376    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax, vertices[i]);
377
378  return gfx::RectF(gfx::PointF(xmin, ymin),
379                    gfx::SizeF(xmax - xmin, ymax - ymin));
380}
381
382gfx::RectF MathUtil::ComputeEnclosingClippedRect(
383    const HomogeneousCoordinate& h1,
384    const HomogeneousCoordinate& h2,
385    const HomogeneousCoordinate& h3,
386    const HomogeneousCoordinate& h4) {
387  // This function performs clipping as necessary and computes the enclosing 2d
388  // gfx::RectF of the vertices. Doing these two steps simultaneously allows us
389  // to avoid the overhead of storing an unknown number of clipped vertices.
390
391  // If no vertices on the quad are clipped, then we can simply return the
392  // enclosing rect directly.
393  bool something_clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
394                           h3.ShouldBeClipped() || h4.ShouldBeClipped();
395  if (!something_clipped) {
396    gfx::QuadF mapped_quad = gfx::QuadF(h1.CartesianPoint2d(),
397                                        h2.CartesianPoint2d(),
398                                        h3.CartesianPoint2d(),
399                                        h4.CartesianPoint2d());
400    return mapped_quad.BoundingBox();
401  }
402
403  bool everything_clipped = h1.ShouldBeClipped() && h2.ShouldBeClipped() &&
404                            h3.ShouldBeClipped() && h4.ShouldBeClipped();
405  if (everything_clipped)
406    return gfx::RectF();
407
408  float xmin = std::numeric_limits<float>::max();
409  float xmax = -std::numeric_limits<float>::max();
410  float ymin = std::numeric_limits<float>::max();
411  float ymax = -std::numeric_limits<float>::max();
412
413  if (!h1.ShouldBeClipped())
414    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
415                               h1.CartesianPoint2d());
416
417  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped())
418    ExpandBoundsToIncludePoint(&xmin,
419                               &xmax,
420                               &ymin,
421                               &ymax,
422                               ComputeClippedPointForEdge(h1, h2)
423                                   .CartesianPoint2d());
424
425  if (!h2.ShouldBeClipped())
426    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
427                               h2.CartesianPoint2d());
428
429  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped())
430    ExpandBoundsToIncludePoint(&xmin,
431                               &xmax,
432                               &ymin,
433                               &ymax,
434                               ComputeClippedPointForEdge(h2, h3)
435                                   .CartesianPoint2d());
436
437  if (!h3.ShouldBeClipped())
438    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
439                               h3.CartesianPoint2d());
440
441  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped())
442    ExpandBoundsToIncludePoint(&xmin,
443                               &xmax,
444                               &ymin,
445                               &ymax,
446                               ComputeClippedPointForEdge(h3, h4)
447                                   .CartesianPoint2d());
448
449  if (!h4.ShouldBeClipped())
450    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
451                               h4.CartesianPoint2d());
452
453  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped())
454    ExpandBoundsToIncludePoint(&xmin,
455                               &xmax,
456                               &ymin,
457                               &ymax,
458                               ComputeClippedPointForEdge(h4, h1)
459                                   .CartesianPoint2d());
460
461  return gfx::RectF(gfx::PointF(xmin, ymin),
462                    gfx::SizeF(xmax - xmin, ymax - ymin));
463}
464
465gfx::QuadF MathUtil::MapQuad(const gfx::Transform& transform,
466                             const gfx::QuadF& q,
467                             bool* clipped) {
468  if (transform.IsIdentityOrTranslation()) {
469    gfx::QuadF mapped_quad(q);
470    mapped_quad += gfx::Vector2dF(transform.matrix().getFloat(0, 3),
471                                  transform.matrix().getFloat(1, 3));
472    *clipped = false;
473    return mapped_quad;
474  }
475
476  HomogeneousCoordinate h1 =
477      MapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
478  HomogeneousCoordinate h2 =
479      MapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
480  HomogeneousCoordinate h3 =
481      MapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
482  HomogeneousCoordinate h4 =
483      MapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
484
485  *clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
486            h3.ShouldBeClipped() || h4.ShouldBeClipped();
487
488  // Result will be invalid if clipped == true. But, compute it anyway just in
489  // case, to emulate existing behavior.
490  return gfx::QuadF(h1.CartesianPoint2d(),
491                    h2.CartesianPoint2d(),
492                    h3.CartesianPoint2d(),
493                    h4.CartesianPoint2d());
494}
495
496gfx::QuadF MathUtil::MapQuad3d(const gfx::Transform& transform,
497                               const gfx::QuadF& q,
498                               gfx::Point3F* p,
499                               bool* clipped) {
500  if (transform.IsIdentityOrTranslation()) {
501    gfx::QuadF mapped_quad(q);
502    mapped_quad += gfx::Vector2dF(transform.matrix().getFloat(0, 3),
503                                  transform.matrix().getFloat(1, 3));
504    *clipped = false;
505    p[0] = gfx::Point3F(mapped_quad.p1().x(), mapped_quad.p1().y(), 0.0f);
506    p[1] = gfx::Point3F(mapped_quad.p2().x(), mapped_quad.p2().y(), 0.0f);
507    p[2] = gfx::Point3F(mapped_quad.p3().x(), mapped_quad.p3().y(), 0.0f);
508    p[3] = gfx::Point3F(mapped_quad.p4().x(), mapped_quad.p4().y(), 0.0f);
509    return mapped_quad;
510  }
511
512  HomogeneousCoordinate h1 =
513      MapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
514  HomogeneousCoordinate h2 =
515      MapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
516  HomogeneousCoordinate h3 =
517      MapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
518  HomogeneousCoordinate h4 =
519      MapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
520
521  *clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
522             h3.ShouldBeClipped() || h4.ShouldBeClipped();
523
524  // Result will be invalid if clipped == true. But, compute it anyway just in
525  // case, to emulate existing behavior.
526  p[0] = h1.CartesianPoint3d();
527  p[1] = h2.CartesianPoint3d();
528  p[2] = h3.CartesianPoint3d();
529  p[3] = h4.CartesianPoint3d();
530
531  return gfx::QuadF(h1.CartesianPoint2d(),
532                    h2.CartesianPoint2d(),
533                    h3.CartesianPoint2d(),
534                    h4.CartesianPoint2d());
535}
536
537gfx::PointF MathUtil::MapPoint(const gfx::Transform& transform,
538                               const gfx::PointF& p,
539                               bool* clipped) {
540  HomogeneousCoordinate h = MapHomogeneousPoint(transform, gfx::Point3F(p));
541
542  if (h.w() > 0) {
543    *clipped = false;
544    return h.CartesianPoint2d();
545  }
546
547  // The cartesian coordinates will be invalid after dividing by w.
548  *clipped = true;
549
550  // Avoid dividing by w if w == 0.
551  if (!h.w())
552    return gfx::PointF();
553
554  // This return value will be invalid because clipped == true, but (1) users of
555  // this code should be ignoring the return value when clipped == true anyway,
556  // and (2) this behavior is more consistent with existing behavior of WebKit
557  // transforms if the user really does not ignore the return value.
558  return h.CartesianPoint2d();
559}
560
561gfx::Point3F MathUtil::MapPoint(const gfx::Transform& transform,
562                                const gfx::Point3F& p,
563                                bool* clipped) {
564  HomogeneousCoordinate h = MapHomogeneousPoint(transform, p);
565
566  if (h.w() > 0) {
567    *clipped = false;
568    return h.CartesianPoint3d();
569  }
570
571  // The cartesian coordinates will be invalid after dividing by w.
572  *clipped = true;
573
574  // Avoid dividing by w if w == 0.
575  if (!h.w())
576    return gfx::Point3F();
577
578  // This return value will be invalid because clipped == true, but (1) users of
579  // this code should be ignoring the return value when clipped == true anyway,
580  // and (2) this behavior is more consistent with existing behavior of WebKit
581  // transforms if the user really does not ignore the return value.
582  return h.CartesianPoint3d();
583}
584
585gfx::QuadF MathUtil::ProjectQuad(const gfx::Transform& transform,
586                                 const gfx::QuadF& q,
587                                 bool* clipped) {
588  gfx::QuadF projected_quad;
589  bool clipped_point;
590  projected_quad.set_p1(ProjectPoint(transform, q.p1(), &clipped_point));
591  *clipped = clipped_point;
592  projected_quad.set_p2(ProjectPoint(transform, q.p2(), &clipped_point));
593  *clipped |= clipped_point;
594  projected_quad.set_p3(ProjectPoint(transform, q.p3(), &clipped_point));
595  *clipped |= clipped_point;
596  projected_quad.set_p4(ProjectPoint(transform, q.p4(), &clipped_point));
597  *clipped |= clipped_point;
598
599  return projected_quad;
600}
601
602gfx::PointF MathUtil::ProjectPoint(const gfx::Transform& transform,
603                                   const gfx::PointF& p,
604                                   bool* clipped) {
605  HomogeneousCoordinate h = ProjectHomogeneousPoint(transform, p, clipped);
606  // Avoid dividing by w if w == 0.
607  if (!h.w())
608    return gfx::PointF();
609
610  // This return value will be invalid if clipped == true, but (1) users of
611  // this code should be ignoring the return value when clipped == true anyway,
612  // and (2) this behavior is more consistent with existing behavior of WebKit
613  // transforms if the user really does not ignore the return value.
614  return h.CartesianPoint2d();
615}
616
617gfx::Point3F MathUtil::ProjectPoint3D(const gfx::Transform& transform,
618                                      const gfx::PointF& p,
619                                      bool* clipped) {
620  HomogeneousCoordinate h = ProjectHomogeneousPoint(transform, p, clipped);
621  if (!h.w())
622    return gfx::Point3F();
623  return h.CartesianPoint3d();
624}
625
626gfx::RectF MathUtil::ScaleRectProportional(const gfx::RectF& input_outer_rect,
627                                           const gfx::RectF& scale_outer_rect,
628                                           const gfx::RectF& scale_inner_rect) {
629  gfx::RectF output_inner_rect = input_outer_rect;
630  float scale_rect_to_input_scale_x =
631      scale_outer_rect.width() / input_outer_rect.width();
632  float scale_rect_to_input_scale_y =
633      scale_outer_rect.height() / input_outer_rect.height();
634
635  gfx::Vector2dF top_left_diff =
636      scale_inner_rect.origin() - scale_outer_rect.origin();
637  gfx::Vector2dF bottom_right_diff =
638      scale_inner_rect.bottom_right() - scale_outer_rect.bottom_right();
639  output_inner_rect.Inset(top_left_diff.x() / scale_rect_to_input_scale_x,
640                          top_left_diff.y() / scale_rect_to_input_scale_y,
641                          -bottom_right_diff.x() / scale_rect_to_input_scale_x,
642                          -bottom_right_diff.y() / scale_rect_to_input_scale_y);
643  return output_inner_rect;
644}
645
646static inline bool NearlyZero(double value) {
647  return std::abs(value) < std::numeric_limits<double>::epsilon();
648}
649
650static inline float ScaleOnAxis(double a, double b, double c) {
651  if (NearlyZero(b) && NearlyZero(c))
652    return std::abs(a);
653  if (NearlyZero(a) && NearlyZero(c))
654    return std::abs(b);
655  if (NearlyZero(a) && NearlyZero(b))
656    return std::abs(c);
657
658  // Do the sqrt as a double to not lose precision.
659  return static_cast<float>(std::sqrt(a * a + b * b + c * c));
660}
661
662gfx::Vector2dF MathUtil::ComputeTransform2dScaleComponents(
663    const gfx::Transform& transform,
664    float fallback_value) {
665  if (transform.HasPerspective())
666    return gfx::Vector2dF(fallback_value, fallback_value);
667  float x_scale = ScaleOnAxis(transform.matrix().getDouble(0, 0),
668                              transform.matrix().getDouble(1, 0),
669                              transform.matrix().getDouble(2, 0));
670  float y_scale = ScaleOnAxis(transform.matrix().getDouble(0, 1),
671                              transform.matrix().getDouble(1, 1),
672                              transform.matrix().getDouble(2, 1));
673  return gfx::Vector2dF(x_scale, y_scale);
674}
675
676float MathUtil::SmallestAngleBetweenVectors(const gfx::Vector2dF& v1,
677                                            const gfx::Vector2dF& v2) {
678  double dot_product = gfx::DotProduct(v1, v2) / v1.Length() / v2.Length();
679  // Clamp to compensate for rounding errors.
680  dot_product = std::max(-1.0, std::min(1.0, dot_product));
681  return static_cast<float>(Rad2Deg(std::acos(dot_product)));
682}
683
684gfx::Vector2dF MathUtil::ProjectVector(const gfx::Vector2dF& source,
685                                       const gfx::Vector2dF& destination) {
686  float projected_length =
687      gfx::DotProduct(source, destination) / destination.LengthSquared();
688  return gfx::Vector2dF(projected_length * destination.x(),
689                        projected_length * destination.y());
690}
691
692scoped_ptr<base::Value> MathUtil::AsValue(const gfx::Size& s) {
693  scoped_ptr<base::DictionaryValue> res(new base::DictionaryValue());
694  res->SetDouble("width", s.width());
695  res->SetDouble("height", s.height());
696  return res.PassAs<base::Value>();
697}
698
699scoped_ptr<base::Value> MathUtil::AsValue(const gfx::Rect& r) {
700  scoped_ptr<base::ListValue> res(new base::ListValue());
701  res->AppendInteger(r.x());
702  res->AppendInteger(r.y());
703  res->AppendInteger(r.width());
704  res->AppendInteger(r.height());
705  return res.PassAs<base::Value>();
706}
707
708bool MathUtil::FromValue(const base::Value* raw_value, gfx::Rect* out_rect) {
709  const base::ListValue* value = NULL;
710  if (!raw_value->GetAsList(&value))
711    return false;
712
713  if (value->GetSize() != 4)
714    return false;
715
716  int x, y, w, h;
717  bool ok = true;
718  ok &= value->GetInteger(0, &x);
719  ok &= value->GetInteger(1, &y);
720  ok &= value->GetInteger(2, &w);
721  ok &= value->GetInteger(3, &h);
722  if (!ok)
723    return false;
724
725  *out_rect = gfx::Rect(x, y, w, h);
726  return true;
727}
728
729scoped_ptr<base::Value> MathUtil::AsValue(const gfx::PointF& pt) {
730  scoped_ptr<base::ListValue> res(new base::ListValue());
731  res->AppendDouble(pt.x());
732  res->AppendDouble(pt.y());
733  return res.PassAs<base::Value>();
734}
735
736void MathUtil::AddToTracedValue(const gfx::Size& s,
737                                base::debug::TracedValue* res) {
738  res->SetDouble("width", s.width());
739  res->SetDouble("height", s.height());
740}
741
742void MathUtil::AddToTracedValue(const gfx::SizeF& s,
743                                base::debug::TracedValue* res) {
744  res->SetDouble("width", s.width());
745  res->SetDouble("height", s.height());
746}
747
748void MathUtil::AddToTracedValue(const gfx::Rect& r,
749                                base::debug::TracedValue* res) {
750  res->AppendInteger(r.x());
751  res->AppendInteger(r.y());
752  res->AppendInteger(r.width());
753  res->AppendInteger(r.height());
754}
755
756void MathUtil::AddToTracedValue(const gfx::PointF& pt,
757                                base::debug::TracedValue* res) {
758  res->AppendDouble(pt.x());
759  res->AppendDouble(pt.y());
760}
761
762void MathUtil::AddToTracedValue(const gfx::Point3F& pt,
763                                base::debug::TracedValue* res) {
764  res->AppendDouble(pt.x());
765  res->AppendDouble(pt.y());
766  res->AppendDouble(pt.z());
767}
768
769void MathUtil::AddToTracedValue(const gfx::Vector2d& v,
770                                base::debug::TracedValue* res) {
771  res->AppendInteger(v.x());
772  res->AppendInteger(v.y());
773}
774
775void MathUtil::AddToTracedValue(const gfx::Vector2dF& v,
776                                base::debug::TracedValue* res) {
777  res->AppendDouble(v.x());
778  res->AppendDouble(v.y());
779}
780
781void MathUtil::AddToTracedValue(const gfx::QuadF& q,
782                                base::debug::TracedValue* res) {
783  res->AppendDouble(q.p1().x());
784  res->AppendDouble(q.p1().y());
785  res->AppendDouble(q.p2().x());
786  res->AppendDouble(q.p2().y());
787  res->AppendDouble(q.p3().x());
788  res->AppendDouble(q.p3().y());
789  res->AppendDouble(q.p4().x());
790  res->AppendDouble(q.p4().y());
791}
792
793void MathUtil::AddToTracedValue(const gfx::RectF& rect,
794                                base::debug::TracedValue* res) {
795  res->AppendDouble(rect.x());
796  res->AppendDouble(rect.y());
797  res->AppendDouble(rect.width());
798  res->AppendDouble(rect.height());
799}
800
801void MathUtil::AddToTracedValue(const gfx::Transform& transform,
802                                base::debug::TracedValue* res) {
803  const SkMatrix44& m = transform.matrix();
804  for (int row = 0; row < 4; ++row) {
805    for (int col = 0; col < 4; ++col)
806      res->AppendDouble(m.getDouble(row, col));
807  }
808}
809
810void MathUtil::AddToTracedValue(const gfx::BoxF& box,
811                                base::debug::TracedValue* res) {
812  res->AppendInteger(box.x());
813  res->AppendInteger(box.y());
814  res->AppendInteger(box.z());
815  res->AppendInteger(box.width());
816  res->AppendInteger(box.height());
817  res->AppendInteger(box.depth());
818}
819
820double MathUtil::AsDoubleSafely(double value) {
821  return std::min(value, std::numeric_limits<double>::max());
822}
823
824float MathUtil::AsFloatSafely(float value) {
825  return std::min(value, std::numeric_limits<float>::max());
826}
827
828}  // namespace cc
829