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