| // Copyright 2012 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "config.h" |
| |
| #include "CCMathUtil.h" |
| |
| #include "FloatPoint.h" |
| #include "FloatQuad.h" |
| #include "IntRect.h" |
| #include <public/WebTransformationMatrix.h> |
| |
| using WebKit::WebTransformationMatrix; |
| |
| namespace cc { |
| |
| static HomogeneousCoordinate projectHomogeneousPoint(const WebTransformationMatrix& transform, const FloatPoint& p) |
| { |
| // In this case, the layer we are trying to project onto is perpendicular to ray |
| // (point p and z-axis direction) that we are trying to project. This happens when the |
| // layer is rotated so that it is infinitesimally thin, or when it is co-planar with |
| // the camera origin -- i.e. when the layer is invisible anyway. |
| if (!transform.m33()) |
| return HomogeneousCoordinate(0, 0, 0, 1); |
| |
| double x = p.x(); |
| double y = p.y(); |
| double z = -(transform.m13() * x + transform.m23() * y + transform.m43()) / transform.m33(); |
| // implicit definition of w = 1; |
| |
| double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41(); |
| double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42(); |
| double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43(); |
| double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44(); |
| |
| return HomogeneousCoordinate(outX, outY, outZ, outW); |
| } |
| |
| static HomogeneousCoordinate mapHomogeneousPoint(const WebTransformationMatrix& transform, const FloatPoint3D& p) |
| { |
| double x = p.x(); |
| double y = p.y(); |
| double z = p.z(); |
| // implicit definition of w = 1; |
| |
| double outX = x * transform.m11() + y * transform.m21() + z * transform.m31() + transform.m41(); |
| double outY = x * transform.m12() + y * transform.m22() + z * transform.m32() + transform.m42(); |
| double outZ = x * transform.m13() + y * transform.m23() + z * transform.m33() + transform.m43(); |
| double outW = x * transform.m14() + y * transform.m24() + z * transform.m34() + transform.m44(); |
| |
| return HomogeneousCoordinate(outX, outY, outZ, outW); |
| } |
| |
| static HomogeneousCoordinate computeClippedPointForEdge(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2) |
| { |
| // Points h1 and h2 form a line in 4d, and any point on that line can be represented |
| // as an interpolation between h1 and h2: |
| // p = (1-t) h1 + (t) h2 |
| // |
| // We want to compute point p such that p.w == epsilon, where epsilon is a small |
| // non-zero number. (but the smaller the number is, the higher the risk of overflow) |
| // To do this, we solve for t in the following equation: |
| // p.w = epsilon = (1-t) * h1.w + (t) * h2.w |
| // |
| // Once paramter t is known, the rest of p can be computed via p = (1-t) h1 + (t) h2. |
| |
| // Technically this is a special case of the following assertion, but its a good idea to keep it an explicit sanity check here. |
| ASSERT(h2.w != h1.w); |
| // Exactly one of h1 or h2 (but not both) must be on the negative side of the w plane when this is called. |
| ASSERT(h1.shouldBeClipped() ^ h2.shouldBeClipped()); |
| |
| double w = 0.00001; // or any positive non-zero small epsilon |
| |
| double t = (w - h1.w) / (h2.w - h1.w); |
| |
| double x = (1-t) * h1.x + t * h2.x; |
| double y = (1-t) * h1.y + t * h2.y; |
| double z = (1-t) * h1.z + t * h2.z; |
| |
| return HomogeneousCoordinate(x, y, z, w); |
| } |
| |
| static inline void expandBoundsToIncludePoint(float& xmin, float& xmax, float& ymin, float& ymax, const FloatPoint& p) |
| { |
| xmin = std::min(p.x(), xmin); |
| xmax = std::max(p.x(), xmax); |
| ymin = std::min(p.y(), ymin); |
| ymax = std::max(p.y(), ymax); |
| } |
| |
| static inline void addVertexToClippedQuad(const FloatPoint& newVertex, FloatPoint clippedQuad[8], int& numVerticesInClippedQuad) |
| { |
| clippedQuad[numVerticesInClippedQuad] = newVertex; |
| numVerticesInClippedQuad++; |
| } |
| |
| IntRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, const IntRect& srcRect) |
| { |
| return enclosingIntRect(mapClippedRect(transform, FloatRect(srcRect))); |
| } |
| |
| FloatRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, const FloatRect& srcRect) |
| { |
| if (transform.isIdentityOrTranslation()) { |
| FloatRect mappedRect(srcRect); |
| mappedRect.move(static_cast<float>(transform.m41()), static_cast<float>(transform.m42())); |
| return mappedRect; |
| } |
| |
| // Apply the transform, but retain the result in homogeneous coordinates. |
| FloatQuad q = FloatQuad(FloatRect(srcRect)); |
| HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, q.p1()); |
| HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, q.p2()); |
| HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, q.p3()); |
| HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, q.p4()); |
| |
| return computeEnclosingClippedRect(h1, h2, h3, h4); |
| } |
| |
| FloatRect CCMathUtil::projectClippedRect(const WebTransformationMatrix& transform, const FloatRect& srcRect) |
| { |
| // Perform the projection, but retain the result in homogeneous coordinates. |
| FloatQuad q = FloatQuad(FloatRect(srcRect)); |
| HomogeneousCoordinate h1 = projectHomogeneousPoint(transform, q.p1()); |
| HomogeneousCoordinate h2 = projectHomogeneousPoint(transform, q.p2()); |
| HomogeneousCoordinate h3 = projectHomogeneousPoint(transform, q.p3()); |
| HomogeneousCoordinate h4 = projectHomogeneousPoint(transform, q.p4()); |
| |
| return computeEnclosingClippedRect(h1, h2, h3, h4); |
| } |
| |
| void CCMathUtil::mapClippedQuad(const WebTransformationMatrix& transform, const FloatQuad& srcQuad, FloatPoint clippedQuad[8], int& numVerticesInClippedQuad) |
| { |
| HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, srcQuad.p1()); |
| HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, srcQuad.p2()); |
| HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, srcQuad.p3()); |
| HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, srcQuad.p4()); |
| |
| // The order of adding the vertices to the array is chosen so that clockwise / counter-clockwise orientation is retained. |
| |
| numVerticesInClippedQuad = 0; |
| |
| if (!h1.shouldBeClipped()) |
| addVertexToClippedQuad(h1.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (h1.shouldBeClipped() ^ h2.shouldBeClipped()) |
| addVertexToClippedQuad(computeClippedPointForEdge(h1, h2).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (!h2.shouldBeClipped()) |
| addVertexToClippedQuad(h2.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (h2.shouldBeClipped() ^ h3.shouldBeClipped()) |
| addVertexToClippedQuad(computeClippedPointForEdge(h2, h3).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (!h3.shouldBeClipped()) |
| addVertexToClippedQuad(h3.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (h3.shouldBeClipped() ^ h4.shouldBeClipped()) |
| addVertexToClippedQuad(computeClippedPointForEdge(h3, h4).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (!h4.shouldBeClipped()) |
| addVertexToClippedQuad(h4.cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| if (h4.shouldBeClipped() ^ h1.shouldBeClipped()) |
| addVertexToClippedQuad(computeClippedPointForEdge(h4, h1).cartesianPoint2d(), clippedQuad, numVerticesInClippedQuad); |
| |
| ASSERT(numVerticesInClippedQuad <= 8); |
| } |
| |
| FloatRect CCMathUtil::computeEnclosingRectOfVertices(FloatPoint vertices[], int numVertices) |
| { |
| if (numVertices < 2) |
| return FloatRect(); |
| |
| float xmin = std::numeric_limits<float>::max(); |
| float xmax = -std::numeric_limits<float>::max(); |
| float ymin = std::numeric_limits<float>::max(); |
| float ymax = -std::numeric_limits<float>::max(); |
| |
| for (int i = 0; i < numVertices; ++i) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, vertices[i]); |
| |
| return FloatRect(FloatPoint(xmin, ymin), FloatSize(xmax - xmin, ymax - ymin)); |
| } |
| |
| FloatRect CCMathUtil::computeEnclosingClippedRect(const HomogeneousCoordinate& h1, const HomogeneousCoordinate& h2, const HomogeneousCoordinate& h3, const HomogeneousCoordinate& h4) |
| { |
| // This function performs clipping as necessary and computes the enclosing 2d |
| // FloatRect of the vertices. Doing these two steps simultaneously allows us to avoid |
| // the overhead of storing an unknown number of clipped vertices. |
| |
| // If no vertices on the quad are clipped, then we can simply return the enclosing rect directly. |
| bool somethingClipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped(); |
| if (!somethingClipped) { |
| FloatQuad mappedQuad = FloatQuad(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d()); |
| return mappedQuad.boundingBox(); |
| } |
| |
| bool everythingClipped = h1.shouldBeClipped() && h2.shouldBeClipped() && h3.shouldBeClipped() && h4.shouldBeClipped(); |
| if (everythingClipped) |
| return FloatRect(); |
| |
| |
| float xmin = std::numeric_limits<float>::max(); |
| float xmax = -std::numeric_limits<float>::max(); |
| float ymin = std::numeric_limits<float>::max(); |
| float ymax = -std::numeric_limits<float>::max(); |
| |
| if (!h1.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h1.cartesianPoint2d()); |
| |
| if (h1.shouldBeClipped() ^ h2.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h1, h2).cartesianPoint2d()); |
| |
| if (!h2.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h2.cartesianPoint2d()); |
| |
| if (h2.shouldBeClipped() ^ h3.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h2, h3).cartesianPoint2d()); |
| |
| if (!h3.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h3.cartesianPoint2d()); |
| |
| if (h3.shouldBeClipped() ^ h4.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h3, h4).cartesianPoint2d()); |
| |
| if (!h4.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, h4.cartesianPoint2d()); |
| |
| if (h4.shouldBeClipped() ^ h1.shouldBeClipped()) |
| expandBoundsToIncludePoint(xmin, xmax, ymin, ymax, computeClippedPointForEdge(h4, h1).cartesianPoint2d()); |
| |
| return FloatRect(FloatPoint(xmin, ymin), FloatSize(xmax - xmin, ymax - ymin)); |
| } |
| |
| FloatQuad CCMathUtil::mapQuad(const WebTransformationMatrix& transform, const FloatQuad& q, bool& clipped) |
| { |
| if (transform.isIdentityOrTranslation()) { |
| FloatQuad mappedQuad(q); |
| mappedQuad.move(static_cast<float>(transform.m41()), static_cast<float>(transform.m42())); |
| clipped = false; |
| return mappedQuad; |
| } |
| |
| HomogeneousCoordinate h1 = mapHomogeneousPoint(transform, q.p1()); |
| HomogeneousCoordinate h2 = mapHomogeneousPoint(transform, q.p2()); |
| HomogeneousCoordinate h3 = mapHomogeneousPoint(transform, q.p3()); |
| HomogeneousCoordinate h4 = mapHomogeneousPoint(transform, q.p4()); |
| |
| clipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.shouldBeClipped() || h4.shouldBeClipped(); |
| |
| // Result will be invalid if clipped == true. But, compute it anyway just in case, to emulate existing behavior. |
| return FloatQuad(h1.cartesianPoint2d(), h2.cartesianPoint2d(), h3.cartesianPoint2d(), h4.cartesianPoint2d()); |
| } |
| |
| FloatPoint CCMathUtil::mapPoint(const WebTransformationMatrix& transform, const FloatPoint& p, bool& clipped) |
| { |
| HomogeneousCoordinate h = mapHomogeneousPoint(transform, p); |
| |
| if (h.w > 0) { |
| clipped = false; |
| return h.cartesianPoint2d(); |
| } |
| |
| // The cartesian coordinates will be invalid after dividing by w. |
| clipped = true; |
| |
| // Avoid dividing by w if w == 0. |
| if (!h.w) |
| return FloatPoint(); |
| |
| // This return value will be invalid because clipped == true, but (1) users of this |
| // code should be ignoring the return value when clipped == true anyway, and (2) this |
| // behavior is more consistent with existing behavior of WebKit transforms if the user |
| // really does not ignore the return value. |
| return h.cartesianPoint2d(); |
| } |
| |
| FloatPoint3D CCMathUtil::mapPoint(const WebTransformationMatrix& transform, const FloatPoint3D& p, bool& clipped) |
| { |
| HomogeneousCoordinate h = mapHomogeneousPoint(transform, p); |
| |
| if (h.w > 0) { |
| clipped = false; |
| return h.cartesianPoint3d(); |
| } |
| |
| // The cartesian coordinates will be invalid after dividing by w. |
| clipped = true; |
| |
| // Avoid dividing by w if w == 0. |
| if (!h.w) |
| return FloatPoint3D(); |
| |
| // This return value will be invalid because clipped == true, but (1) users of this |
| // code should be ignoring the return value when clipped == true anyway, and (2) this |
| // behavior is more consistent with existing behavior of WebKit transforms if the user |
| // really does not ignore the return value. |
| return h.cartesianPoint3d(); |
| } |
| |
| FloatQuad CCMathUtil::projectQuad(const WebTransformationMatrix& transform, const FloatQuad& q, bool& clipped) |
| { |
| FloatQuad projectedQuad; |
| bool clippedPoint; |
| projectedQuad.setP1(projectPoint(transform, q.p1(), clippedPoint)); |
| clipped = clippedPoint; |
| projectedQuad.setP2(projectPoint(transform, q.p2(), clippedPoint)); |
| clipped |= clippedPoint; |
| projectedQuad.setP3(projectPoint(transform, q.p3(), clippedPoint)); |
| clipped |= clippedPoint; |
| projectedQuad.setP4(projectPoint(transform, q.p4(), clippedPoint)); |
| clipped |= clippedPoint; |
| |
| return projectedQuad; |
| } |
| |
| FloatPoint CCMathUtil::projectPoint(const WebTransformationMatrix& transform, const FloatPoint& p, bool& clipped) |
| { |
| HomogeneousCoordinate h = projectHomogeneousPoint(transform, p); |
| |
| if (h.w > 0) { |
| // The cartesian coordinates will be valid in this case. |
| clipped = false; |
| return h.cartesianPoint2d(); |
| } |
| |
| // The cartesian coordinates will be invalid after dividing by w. |
| clipped = true; |
| |
| // Avoid dividing by w if w == 0. |
| if (!h.w) |
| return FloatPoint(); |
| |
| // This return value will be invalid because clipped == true, but (1) users of this |
| // code should be ignoring the return value when clipped == true anyway, and (2) this |
| // behavior is more consistent with existing behavior of WebKit transforms if the user |
| // really does not ignore the return value. |
| return h.cartesianPoint2d(); |
| } |
| |
| void CCMathUtil::flattenTransformTo2d(WebTransformationMatrix& transform) |
| { |
| // Set both the 3rd row and 3rd column to (0, 0, 1, 0). |
| // |
| // One useful interpretation of doing this operation: |
| // - For x and y values, the new transform behaves effectively like an orthographic |
| // projection was added to the matrix sequence. |
| // - For z values, the new transform overrides any effect that the transform had on |
| // z, and instead it preserves the z value for any points that are transformed. |
| // - Because of linearity of transforms, this flattened transform also preserves the |
| // effect that any subsequent (post-multiplied) transforms would have on z values. |
| // |
| transform.setM13(0); |
| transform.setM23(0); |
| transform.setM31(0); |
| transform.setM32(0); |
| transform.setM33(1); |
| transform.setM34(0); |
| transform.setM43(0); |
| } |
| |
| float CCMathUtil::smallestAngleBetweenVectors(const FloatSize& v1, const FloatSize& v2) |
| { |
| float dotProduct = (v1.width() * v2.width() + v1.height() * v2.height()) / (v1.diagonalLength() * v2.diagonalLength()); |
| // Clamp to compensate for rounding errors. |
| dotProduct = std::max(-1.f, std::min(1.f, dotProduct)); |
| return rad2deg(acosf(dotProduct)); |
| } |
| |
| FloatSize CCMathUtil::projectVector(const FloatSize& source, const FloatSize& destination) |
| { |
| float sourceDotDestination = source.width() * destination.width() + source.height() * destination.height(); |
| float projectedLength = sourceDotDestination / destination.diagonalLengthSquared(); |
| return FloatSize(projectedLength * destination.width(), projectedLength * destination.height()); |
| } |
| |
| } // namespace cc |