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