| OLD | NEW |
|---|
| (Empty) |
| 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 WebTransformationMatr
ix& 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 happen
s when the | |
| 22 // layer is rotated so that it is infinitesimally thin, or when it is co-pla
nar 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 HomogeneousCoordin
ate& h1, const HomogeneousCoordinate& h2) | |
| 56 { | |
| 57 // Points h1 and h2 form a line in 4d, and any point on that line can be rep
resented | |
| 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 s
mall | |
| 62 // non-zero number. (but the smaller the number is, the higher the risk of o
verflow) | |
| 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 th
e 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& y
min, 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, FloatPoin
t clippedQuad[8], int& numVerticesInClippedQuad) | |
| 93 { | |
| 94 clippedQuad[numVerticesInClippedQuad] = newVertex; | |
| 95 numVerticesInClippedQuad++; | |
| 96 } | |
| 97 | |
| 98 IntRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, con
st IntRect& srcRect) | |
| 99 { | |
| 100 return enclosingIntRect(mapClippedRect(transform, FloatRect(srcRect))); | |
| 101 } | |
| 102 | |
| 103 FloatRect CCMathUtil::mapClippedRect(const WebTransformationMatrix& transform, c
onst 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& transfor
m, 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, numVerticesIn
ClippedQuad); | |
| 146 | |
| 147 if (h1.shouldBeClipped() ^ h2.shouldBeClipped()) | |
| 148 addVertexToClippedQuad(computeClippedPointForEdge(h1, h2).cartesianPoint
2d(), clippedQuad, numVerticesInClippedQuad); | |
| 149 | |
| 150 if (!h2.shouldBeClipped()) | |
| 151 addVertexToClippedQuad(h2.cartesianPoint2d(), clippedQuad, numVerticesIn
ClippedQuad); | |
| 152 | |
| 153 if (h2.shouldBeClipped() ^ h3.shouldBeClipped()) | |
| 154 addVertexToClippedQuad(computeClippedPointForEdge(h2, h3).cartesianPoint
2d(), clippedQuad, numVerticesInClippedQuad); | |
| 155 | |
| 156 if (!h3.shouldBeClipped()) | |
| 157 addVertexToClippedQuad(h3.cartesianPoint2d(), clippedQuad, numVerticesIn
ClippedQuad); | |
| 158 | |
| 159 if (h3.shouldBeClipped() ^ h4.shouldBeClipped()) | |
| 160 addVertexToClippedQuad(computeClippedPointForEdge(h3, h4).cartesianPoint
2d(), clippedQuad, numVerticesInClippedQuad); | |
| 161 | |
| 162 if (!h4.shouldBeClipped()) | |
| 163 addVertexToClippedQuad(h4.cartesianPoint2d(), clippedQuad, numVerticesIn
ClippedQuad); | |
| 164 | |
| 165 if (h4.shouldBeClipped() ^ h1.shouldBeClipped()) | |
| 166 addVertexToClippedQuad(computeClippedPointForEdge(h4, h1).cartesianPoint
2d(), 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& h
1, const HomogeneousCoordinate& h2, const HomogeneousCoordinate& h3, const Homog
eneousCoordinate& h4) | |
| 188 { | |
| 189 // This function performs clipping as necessary and computes the enclosing 2
d | |
| 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 enc
losing rect directly. | |
| 194 bool somethingClipped = h1.shouldBeClipped() || h2.shouldBeClipped() || h3.s
houldBeClipped() || h4.shouldBeClipped(); | |
| 195 if (!somethingClipped) { | |
| 196 FloatQuad mappedQuad = FloatQuad(h1.cartesianPoint2d(), h2.cartesianPoin
t2d(), 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, computeClippedPointFo
rEdge(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, computeClippedPointFo
rEdge(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, computeClippedPointFo
rEdge(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, computeClippedPointFo
rEdge(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 Fl
oatQuad& 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.cartesianP
oint2d(), 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 i
f the user | |
| 276 // really does not ignore the return value. | |
| 277 return h.cartesianPoint2d(); | |
| 278 } | |
| 279 | |
| 280 FloatPoint3D CCMathUtil::mapPoint(const WebTransformationMatrix& transform, cons
t 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 i
f the user | |
| 299 // really does not ignore the return value. | |
| 300 return h.cartesianPoint3d(); | |
| 301 } | |
| 302 | |
| 303 FloatQuad CCMathUtil::projectQuad(const WebTransformationMatrix& transform, cons
t 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, co
nst 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 i
f 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 orth
ographic | |
| 349 // projection was added to the matrix sequence. | |
| 350 // - For z values, the new transform overrides any effect that the transfor
m had on | |
| 351 // z, and instead it preserves the z value for any points that are transf
ormed. | |
| 352 // - Because of linearity of transforms, this flattened transform also pres
erves 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 FloatSi
ze& 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& de
stination) | |
| 373 { | |
| 374 float sourceDotDestination = source.width() * destination.width() + source.h
eight() * destination.height(); | |
| 375 float projectedLength = sourceDotDestination / destination.diagonalLengthSqu
ared(); | |
| 376 return FloatSize(projectedLength * destination.width(), projectedLength * de
stination.height()); | |
| 377 } | |
| 378 | |
| 379 } // namespace cc | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 11122003:
[cc] Rename all cc/ filenames to Chromium style (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src