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