cc/base/math_util.cc

   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/trace_event/trace_event_argument.h"
  12 #include "base/values.h"
  13 #include "ui/gfx/geometry/quad_f.h"
  14 #include "ui/gfx/geometry/rect.h"
  15 #include "ui/gfx/geometry/rect_conversions.h"
  16 #include "ui/gfx/geometry/rect_f.h"
  17 #include "ui/gfx/geometry/vector2d_f.h"
  18 #include "ui/gfx/transform.h"
  19
  20 namespace cc {
  21
  22 const double MathUtil::kPiDouble = 3.14159265358979323846;
  23 const float MathUtil::kPiFloat = 3.14159265358979323846f;
  24
  25 static 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
  45 static 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
  54 static 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
  62 static 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
  96 static 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
 107 static 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
 114 static 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
 121 gfx::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
 131 gfx::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
 161 gfx::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
 172 gfx::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
 190 gfx::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
 225 void 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
 294 bool 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
 364 gfx::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
 382 gfx::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
 465 gfx::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
 496 gfx::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
 537 gfx::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
 561 gfx::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
 585 gfx::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
 602 gfx::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
 617 gfx::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
 626 gfx::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
 646 static inline bool NearlyZero(double value) {
 647   return std::abs(value) < std::numeric_limits<double>::epsilon();
 648 }
 649
 650 static 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
 662 gfx::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
 676 float 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
 684 gfx::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
 692 scoped_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.Pass();
 697 }
 698
 699 scoped_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.Pass();
 706 }
 707
 708 bool MathUtil::FromValue(const base::Value* raw_value, gfx::Rect* out_rect) {
 709   const base::ListValue* value = nullptr;
 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
 729 scoped_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.Pass();
 734 }
 735
 736 void MathUtil::AddToTracedValue(const char* name,
 737                                 const gfx::Size& s,
 738                                 base::trace_event::TracedValue* res) {
 739   res->BeginDictionary(name);
 740   res->SetDouble("width", s.width());
 741   res->SetDouble("height", s.height());
 742   res->EndDictionary();
 743 }
 744
 745 void MathUtil::AddToTracedValue(const char* name,
 746                                 const gfx::SizeF& s,
 747                                 base::trace_event::TracedValue* res) {
 748   res->BeginDictionary(name);
 749   res->SetDouble("width", s.width());
 750   res->SetDouble("height", s.height());
 751   res->EndDictionary();
 752 }
 753
 754 void MathUtil::AddToTracedValue(const char* name,
 755                                 const gfx::Rect& r,
 756                                 base::trace_event::TracedValue* res) {
 757   res->BeginArray(name);
 758   res->AppendInteger(r.x());
 759   res->AppendInteger(r.y());
 760   res->AppendInteger(r.width());
 761   res->AppendInteger(r.height());
 762   res->EndArray();
 763 }
 764
 765 void MathUtil::AddToTracedValue(const char* name,
 766                                 const gfx::PointF& pt,
 767                                 base::trace_event::TracedValue* res) {
 768   res->BeginArray(name);
 769   res->AppendDouble(pt.x());
 770   res->AppendDouble(pt.y());
 771   res->EndArray();
 772 }
 773
 774 void MathUtil::AddToTracedValue(const char* name,
 775                                 const gfx::Point3F& pt,
 776                                 base::trace_event::TracedValue* res) {
 777   res->BeginArray(name);
 778   res->AppendDouble(pt.x());
 779   res->AppendDouble(pt.y());
 780   res->AppendDouble(pt.z());
 781   res->EndArray();
 782 }
 783
 784 void MathUtil::AddToTracedValue(const char* name,
 785                                 const gfx::Vector2d& v,
 786                                 base::trace_event::TracedValue* res) {
 787   res->BeginArray(name);
 788   res->AppendInteger(v.x());
 789   res->AppendInteger(v.y());
 790   res->EndArray();
 791 }
 792
 793 void MathUtil::AddToTracedValue(const char* name,
 794                                 const gfx::Vector2dF& v,
 795                                 base::trace_event::TracedValue* res) {
 796   res->BeginArray(name);
 797   res->AppendDouble(v.x());
 798   res->AppendDouble(v.y());
 799   res->EndArray();
 800 }
 801
 802 void MathUtil::AddToTracedValue(const char* name,
 803                                 const gfx::ScrollOffset& v,
 804                                 base::trace_event::TracedValue* res) {
 805   res->BeginArray(name);
 806   res->AppendDouble(v.x());
 807   res->AppendDouble(v.y());
 808   res->EndArray();
 809 }
 810
 811 void MathUtil::AddToTracedValue(const char* name,
 812                                 const gfx::QuadF& q,
 813                                 base::trace_event::TracedValue* res) {
 814   res->BeginArray(name);
 815   res->AppendDouble(q.p1().x());
 816   res->AppendDouble(q.p1().y());
 817   res->AppendDouble(q.p2().x());
 818   res->AppendDouble(q.p2().y());
 819   res->AppendDouble(q.p3().x());
 820   res->AppendDouble(q.p3().y());
 821   res->AppendDouble(q.p4().x());
 822   res->AppendDouble(q.p4().y());
 823   res->EndArray();
 824 }
 825
 826 void MathUtil::AddToTracedValue(const char* name,
 827                                 const gfx::RectF& rect,
 828                                 base::trace_event::TracedValue* res) {
 829   res->BeginArray(name);
 830   res->AppendDouble(rect.x());
 831   res->AppendDouble(rect.y());
 832   res->AppendDouble(rect.width());
 833   res->AppendDouble(rect.height());
 834   res->EndArray();
 835 }
 836
 837 void MathUtil::AddToTracedValue(const char* name,
 838                                 const gfx::Transform& transform,
 839                                 base::trace_event::TracedValue* res) {
 840   res->BeginArray(name);
 841   const SkMatrix44& m = transform.matrix();
 842   for (int row = 0; row < 4; ++row) {
 843     for (int col = 0; col < 4; ++col)
 844       res->AppendDouble(m.getDouble(row, col));
 845   }
 846   res->EndArray();
 847 }
 848
 849 void MathUtil::AddToTracedValue(const char* name,
 850                                 const gfx::BoxF& box,
 851                                 base::trace_event::TracedValue* res) {
 852   res->BeginArray(name);
 853   res->AppendInteger(box.x());
 854   res->AppendInteger(box.y());
 855   res->AppendInteger(box.z());
 856   res->AppendInteger(box.width());
 857   res->AppendInteger(box.height());
 858   res->AppendInteger(box.depth());
 859   res->EndArray();
 860 }
 861
 862 double MathUtil::AsDoubleSafely(double value) {
 863   return std::min(value, std::numeric_limits<double>::max());
 864 }
 865
 866 float MathUtil::AsFloatSafely(float value) {
 867   return std::min(value, std::numeric_limits<float>::max());
 868 }
 869
 870 }  // namespace cc