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