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