cc/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 "config.h"
   6
   7 #include "cc/math_util.h"
   8
   9 #include <cmath>
  10 #include <limits>
  11
  12 #include "ui/gfx/quad_f.h"
  13 #include "ui/gfx/rect.h"
  14 #include "ui/gfx/rect_conversions.h"
  15 #include "ui/gfx/rect_f.h"
  16 #include "ui/gfx/vector2d_f.h"
  17 #include <public/WebTransformationMatrix.h>
  18
  19 using WebKit::WebTransformationMatrix;
  20
  21 namespace cc {
  22
  23 const double MathUtil::PI_DOUBLE = 3.14159265358979323846;
  24 const float MathUtil::PI_FLOAT = 3.14159265358979323846f;
  25
  26 static HomogeneousCoordinate projectHomogeneousPoint(const WebTransformationMatrix& transform, const gfx::PointF& p)
  27 {
  28     // In this case, the layer we are trying to project onto is perpendicular to ray
  29     // (point p and z-axis direction) that we are trying to project. This happens when the
  30     // layer is rotated so that it is infinitesimally thin, or when it is co-planar with
  31     // the camera origin -- i.e. when the layer is invisible anyway.
  32     if (!transform.m33())
  33         return HomogeneousCoordinate(0, 0, 0, 1);
  34
  35     double x = p.x();
  36     double y = p.y();
  37     double z = -(transform.m13() * x + transform.m23() * y + transform.m43()) / transform.m33();
  38     // implicit definition of w = 1;
  39
  40     double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41();
  41     double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42();
  42     double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43();
  43     double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44();
  44
  45     return HomogeneousCoordinate(outX, outY, outZ, outW);
  46 }
  47
  48 static HomogeneousCoordinate mapHomogeneousPoint(const WebTransformationMatrix& transform, const gfx::Point3F& p)
  49 {
  50     double x = p.x();
  51     double y = p.y();
  52     double z = p.z();
  53     // implicit definition of w = 1;
  54
  55     double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41();
  56     double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42();
  57     double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43();
  58     double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44();
  59
  60     return HomogeneousCoordinate(outX, outY, outZ, outW);
  61 }
  62
  63 static HomogeneousCoordinate computeClippedPointForEdge(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2)
  64 {
  65     // Points h1 and h2 form a line in 4d, and any point on that line can be represented
  66     // 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 small
  70     // non-zero number. (but the smaller the number is, the higher the risk of overflow)
  71     // To do this, we solve for t in the following equation:
  72     //    p.w = epsilon = (1-t) * h1.w + (t) * h2.w
  73     //
  74     // Once paramter t is known, the rest of p can be computed via p = (1-t) h1 + (t) h2.
  75
  76     // Technically this is a special case of the following assertion, but its a good idea to keep it an explicit sanity check here.
  77     DCHECK(h2.w != h1.w);
  78     // Exactly one of h1 or h2 (but not both) must be on the negative side of the w plane when this is called.
  79     DCHECK(h1.shouldBeClipped() ^ h2.shouldBeClipped());
  80
  81     double w = 0.00001; // or any positive non-zero small epsilon
  82
  83     double t = (w - h1.w) / (h2.w - h1.w);
  84
  85     double x = (1-t) * h1.x + t * h2.x;
  86     double y = (1-t) * h1.y + t * h2.y;
  87     double z = (1-t) * h1.z + t * h2.z;
  88
  89     return HomogeneousCoordinate(x, y, z, w);
  90 }
  91
  92 static inline void expandBoundsToIncludePoint(float& xmin, float& xmax, float& ymin, float& ymax, const gfx::PointF& p)
  93 {
  94     xmin = std::min(p.x(), xmin);
  95     xmax = std::max(p.x(), xmax);
  96     ymin = std::min(p.y(), ymin);
  97     ymax = std::max(p.y(), ymax);
  98 }
  99
 100 static inline void addVertexToClippedQuad(const gfx::PointF& newVertex, gfx::PointF clippedQuad[8], int& numVerticesInClippedQuad)
 101 {
 102     clippedQuad[numVerticesInClippedQuad] = newVertex;
 103     numVerticesInClippedQuad++;
 104 }
 105
 106 gfx::Rect MathUtil::mapClippedRect(const WebTransformationMatrix& transform, const gfx::Rect& srcRect)
 107 {
 108     return gfx::ToEnclosingRect(mapClippedRect(transform, gfx::RectF(srcRect)));
 109 }
 110
 111 gfx::RectF MathUtil::mapClippedRect(const WebTransformationMatrix& transform, const gfx::RectF& srcRect)
 112 {
 113     if (transform.isIdentityOrTranslation()) {
 114         gfx::RectF mappedRect(srcRect);
 115         mappedRect.Offset(static_cast<float>(transform.m41()), static_cast<float>(transform.m42()));
 116         return mappedRect;
 117     }
 118
 119     // Apply the transform, but retain the result in homogeneous coordinates.
 120     gfx::QuadF q = gfx::QuadF(gfx::RectF(srcRect));
 121     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
 122     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
 123     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
 124     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
 125
 126     return computeEnclosingClippedRect(h1, h2, h3, h4);
 127 }
 128
 129 gfx::RectF MathUtil::projectClippedRect(const WebTransformationMatrix& transform, const gfx::RectF& srcRect)
 130 {
 131     // Perform the projection, but retain the result in homogeneous coordinates.
 132     gfx::QuadF q = gfx::QuadF(gfx::RectF(srcRect));
 133     HomogeneousCoordinate h1 = projectHomogeneousPoint(transform, q.p1());
 134     HomogeneousCoordinate h2 = projectHomogeneousPoint(transform, q.p2());
 135     HomogeneousCoordinate h3 = projectHomogeneousPoint(transform, q.p3());
 136     HomogeneousCoordinate h4 = projectHomogeneousPoint(transform, q.p4());
 137
 138     return computeEnclosingClippedRect(h1, h2, h3, h4);
 139 }
 140
 141 void MathUtil::mapClippedQuad(const WebTransformationMatrix& transform, const gfx::QuadF& srcQuad, gfx::PointF clippedQuad[8], int& numVerticesInClippedQuad)
 142 {
 143     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, gfx::Point3F(srcQuad.p1()));
 144     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, gfx::Point3F(srcQuad.p2()));
 145     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, gfx::Point3F(srcQuad.p3()));
 146     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, gfx::Point3F(srcQuad.p4()));
 147
 148     // The order of adding the vertices to the array is chosen so that clockwise / counter-clockwise orientation is retained.
 149
 150     numVerticesInClippedQuad = 0;
 151
 152     if (!h1.shouldBeClipped())
 153         addVertexToClippedQuad(h1.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 154
 155     if (h1.shouldBeClipped() ^ h2.shouldBeClipped())
 156         addVertexToClippedQuad(computeClippedPointForEdge(h1, h2).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 157
 158     if (!h2.shouldBeClipped())
 159         addVertexToClippedQuad(h2.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 160
 161     if (h2.shouldBeClipped() ^ h3.shouldBeClipped())
 162         addVertexToClippedQuad(computeClippedPointForEdge(h2, h3).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 163
 164     if (!h3.shouldBeClipped())
 165         addVertexToClippedQuad(h3.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 166
 167     if (h3.shouldBeClipped() ^ h4.shouldBeClipped())
 168         addVertexToClippedQuad(computeClippedPointForEdge(h3, h4).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 169
 170     if (!h4.shouldBeClipped())
 171         addVertexToClippedQuad(h4.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 172
 173     if (h4.shouldBeClipped() ^ h1.shouldBeClipped())
 174         addVertexToClippedQuad(computeClippedPointForEdge(h4, h1).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad);
 175
 176     DCHECK(numVerticesInClippedQuad <= 8);
 177 }
 178
 179 gfx::RectF MathUtil::computeEnclosingRectOfVertices(gfx::PointF vertices[], int numVertices)
 180 {
 181     if (numVertices < 2)
 182         return gfx::RectF();
 183
 184     float xmin = std::numeric_limits<float>::max();
 185     float xmax = -std::numeric_limits<float>::max();
 186     float ymin = std::numeric_limits<float>::max();
 187     float ymax = -std::numeric_limits<float>::max();
 188
 189     for (int i = 0; i < numVertices; ++i)
 190         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, vertices[i]);
 191
 192     return gfx::RectF(gfx::PointF(xmin, ymin), gfx::SizeF(xmax - xmin, ymax - ymin));
 193 }
 194
 195 gfx::RectF MathUtil::computeEnclosingClippedRect(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2, const HomogeneousCoordinate& h3, const HomogeneousCoordinate& h4)
 196 {
 197     // This function performs clipping as necessary and computes the enclosing 2d
 198     // gfx::RectF of the vertices. Doing these two steps simultaneously allows us to avoid
 199     // the overhead of storing an unknown number of clipped vertices.
 200
 201     // If no vertices on the quad are clipped, then we can simply return the enclosing rect directly.
 202     bool somethingClipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped();
 203     if (!somethingClipped) {
 204         gfx::QuadF mappedQuad = gfx::QuadF(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d());
 205         return mappedQuad.BoundingBox();
 206     }
 207
 208     bool everythingClipped = h1.shouldBeClipped() && h2.shouldBeClipped() && h3.shouldBeClipped() && h4.shouldBeClipped();
 209     if (everythingClipped)
 210         return gfx::RectF();
 211
 212
 213     float xmin = std::numeric_limits<float>::max();
 214     float xmax = -std::numeric_limits<float>::max();
 215     float ymin = std::numeric_limits<float>::max();
 216     float ymax = -std::numeric_limits<float>::max();
 217
 218     if (!h1.shouldBeClipped())
 219         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h1.cartesianPoint2d());
 220
 221     if (h1.shouldBeClipped() ^ h2.shouldBeClipped())
 222         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h1, h2).cartesianPoint2d());
 223
 224     if (!h2.shouldBeClipped())
 225         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h2.cartesianPoint2d());
 226
 227     if (h2.shouldBeClipped() ^ h3.shouldBeClipped())
 228         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h2, h3).cartesianPoint2d());
 229
 230     if (!h3.shouldBeClipped())
 231         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h3.cartesianPoint2d());
 232
 233     if (h3.shouldBeClipped() ^ h4.shouldBeClipped())
 234         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h3, h4).cartesianPoint2d());
 235
 236     if (!h4.shouldBeClipped())
 237         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h4.cartesianPoint2d());
 238
 239     if (h4.shouldBeClipped() ^ h1.shouldBeClipped())
 240         expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h4, h1).cartesianPoint2d());
 241
 242     return gfx::RectF(gfx::PointF(xmin, ymin), gfx::SizeF(xmax - xmin, ymax - ymin));
 243 }
 244
 245 gfx::QuadF MathUtil::mapQuad(const WebTransformationMatrix& transform, const gfx::QuadF& q, bool& clipped)
 246 {
 247     if (transform.isIdentityOrTranslation()) {
 248         gfx::QuadF mappedQuad(q);
 249         mappedQuad += gfx::Vector2dF(static_cast<float>(transform.m41()), static_cast<float>(transform.m42()));
 250         clipped = false;
 251         return mappedQuad;
 252     }
 253
 254     HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
 255     HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
 256     HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
 257     HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
 258
 259     clipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped();
 260
 261     // Result will be invalid if clipped == true. But, compute it anyway just in case, to emulate existing behavior.
 262     return gfx::QuadF(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d());
 263 }
 264
 265 gfx::PointF MathUtil::mapPoint(const WebTransformationMatrix& transform, const gfx::PointF& p, bool& clipped)
 266 {
 267     HomogeneousCoordinate h = mapHomogeneousPoint(transform, gfx::Point3F(p));
 268
 269     if (h.w > 0) {
 270         clipped = false;
 271         return h.cartesianPoint2d();
 272     }
 273
 274     // The cartesian coordinates will be invalid after dividing by w.
 275     clipped = true;
 276
 277     // Avoid dividing by w if w == 0.
 278     if (!h.w)
 279         return gfx::PointF();
 280
 281     // This return value will be invalid because clipped == true, but (1) users of this
 282     // code should be ignoring the return value when clipped == true anyway, and (2) this
 283     // behavior is more consistent with existing behavior of WebKit transforms if the user
 284     // really does not ignore the return value.
 285     return h.cartesianPoint2d();
 286 }
 287
 288 gfx::Point3F MathUtil::mapPoint(const WebTransformationMatrix& transform, const gfx::Point3F& p, bool& clipped)
 289 {
 290     HomogeneousCoordinate h = mapHomogeneousPoint(transform, p);
 291
 292     if (h.w > 0) {
 293         clipped = false;
 294         return h.cartesianPoint3d();
 295     }
 296
 297     // The cartesian coordinates will be invalid after dividing by w.
 298     clipped = true;
 299
 300     // Avoid dividing by w if w == 0.
 301     if (!h.w)
 302         return gfx::Point3F();
 303
 304     // This return value will be invalid because clipped == true, but (1) users of this
 305     // code should be ignoring the return value when clipped == true anyway, and (2) this
 306     // behavior is more consistent with existing behavior of WebKit transforms if the user
 307     // really does not ignore the return value.
 308     return h.cartesianPoint3d();
 309 }
 310
 311 gfx::QuadF MathUtil::projectQuad(const WebTransformationMatrix& transform, const gfx::QuadF& q, bool& clipped)
 312 {
 313     gfx::QuadF projectedQuad;
 314     bool clippedPoint;
 315     projectedQuad.set_p1(projectPoint(transform, q.p1(), clippedPoint));
 316     clipped = clippedPoint;
 317     projectedQuad.set_p2(projectPoint(transform, q.p2(), clippedPoint));
 318     clipped |= clippedPoint;
 319     projectedQuad.set_p3(projectPoint(transform, q.p3(), clippedPoint));
 320     clipped |= clippedPoint;
 321     projectedQuad.set_p4(projectPoint(transform, q.p4(), clippedPoint));
 322     clipped |= clippedPoint;
 323
 324     return projectedQuad;
 325 }
 326
 327 gfx::PointF MathUtil::projectPoint(const WebTransformationMatrix& transform, const gfx::PointF& p, bool& clipped)
 328 {
 329     HomogeneousCoordinate h = projectHomogeneousPoint(transform, p);
 330
 331     if (h.w > 0) {
 332         // The cartesian coordinates will be valid in this case.
 333         clipped = false;
 334         return h.cartesianPoint2d();
 335     }
 336
 337     // The cartesian coordinates will be invalid after dividing by w.
 338     clipped = true;
 339
 340     // Avoid dividing by w if w == 0.
 341     if (!h.w)
 342         return gfx::PointF();
 343
 344     // This return value will be invalid because clipped == true, but (1) users of this
 345     // code should be ignoring the return value when clipped == true anyway, and (2) this
 346     // behavior is more consistent with existing behavior of WebKit transforms if the user
 347     // really does not ignore the return value.
 348     return h.cartesianPoint2d();
 349 }
 350
 351 void MathUtil::flattenTransformTo2d(WebTransformationMatrix& transform)
 352 {
 353     // Set both the 3rd row and 3rd column to (0, 0, 1, 0).
 354     //
 355     // One useful interpretation of doing this operation:
 356     //  - For x and y values, the new transform behaves effectively like an orthographic
 357     //    projection was added to the matrix sequence.
 358     //  - For z values, the new transform overrides any effect that the transform had on
 359     //    z, and instead it preserves the z value for any points that are transformed.
 360     //  - Because of linearity of transforms, this flattened transform also preserves the
 361     //    effect that any subsequent (post-multiplied) transforms would have on z values.
 362     //
 363     transform.setM13(0);
 364     transform.setM23(0);
 365     transform.setM31(0);
 366     transform.setM32(0);
 367     transform.setM33(1);
 368     transform.setM34(0);
 369     transform.setM43(0);
 370 }
 371
 372 static inline float scaleOnAxis(double a, double b, double c)
 373 {
 374     return std::sqrt(a * a + b * b + c * c);
 375 }
 376
 377 gfx::Vector2dF MathUtil::computeTransform2dScaleComponents(const WebTransformationMatrix& transform)
 378 {
 379     if (transform.hasPerspective())
 380         return gfx::Vector2dF(1, 1);
 381     float xScale = scaleOnAxis(transform.m11(), transform.m12(), transform.m13());
 382     float yScale = scaleOnAxis(transform.m21(), transform.m22(), transform.m23());
 383     return gfx::Vector2dF(xScale, yScale);
 384 }
 385
 386 float MathUtil::smallestAngleBetweenVectors(gfx::Vector2dF v1, gfx::Vector2dF v2)
 387 {
 388     double dotProduct = gfx::DotProduct(v1, v2) / v1.Length() / v2.Length();
 389     // Clamp to compensate for rounding errors.
 390     dotProduct = std::max(-1.0, std::min(1.0, dotProduct));
 391     return static_cast<float>(Rad2Deg(std::acos(dotProduct)));
 392 }
 393
 394 gfx::Vector2dF MathUtil::projectVector(gfx::Vector2dF source, gfx::Vector2dF destination)
 395 {
 396     float projectedLength = gfx::DotProduct(source, destination) / destination.LengthSquared();
 397     return gfx::Vector2dF(projectedLength * destination.x(), projectedLength * destination.y());
 398 }
 399
 400 }  // namespace cc