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