1 // Copyright 2013 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 // Needed on Windows to get |M_PI| from <cmath> 6 #ifdef _WIN32 7 #define _USE_MATH_DEFINES 8 #endif 9 10 #include <algorithm> 11 #include <cmath> 12 #include <limits> 13 14 #include "base/logging.h" 15 #include "cc/animation/transform_operation.h" 16 #include "cc/animation/transform_operations.h" 17 #include "ui/gfx/box_f.h" 18 #include "ui/gfx/transform_util.h" 19 #include "ui/gfx/vector3d_f.h" 20 21 namespace { 22 const SkMScalar kAngleEpsilon = 1e-4f; 23 } 24 25 namespace cc { 26 27 bool TransformOperation::IsIdentity() const { 28 return matrix.IsIdentity(); 29 } 30 31 static bool IsOperationIdentity(const TransformOperation* operation) { 32 return !operation || operation->IsIdentity(); 33 } 34 35 static bool ShareSameAxis(const TransformOperation* from, 36 const TransformOperation* to, 37 SkMScalar* axis_x, 38 SkMScalar* axis_y, 39 SkMScalar* axis_z, 40 SkMScalar* angle_from) { 41 if (IsOperationIdentity(from) && IsOperationIdentity(to)) 42 return false; 43 44 if (IsOperationIdentity(from) && !IsOperationIdentity(to)) { 45 *axis_x = to->rotate.axis.x; 46 *axis_y = to->rotate.axis.y; 47 *axis_z = to->rotate.axis.z; 48 *angle_from = 0; 49 return true; 50 } 51 52 if (!IsOperationIdentity(from) && IsOperationIdentity(to)) { 53 *axis_x = from->rotate.axis.x; 54 *axis_y = from->rotate.axis.y; 55 *axis_z = from->rotate.axis.z; 56 *angle_from = from->rotate.angle; 57 return true; 58 } 59 60 SkMScalar length_2 = from->rotate.axis.x * from->rotate.axis.x + 61 from->rotate.axis.y * from->rotate.axis.y + 62 from->rotate.axis.z * from->rotate.axis.z; 63 SkMScalar other_length_2 = to->rotate.axis.x * to->rotate.axis.x + 64 to->rotate.axis.y * to->rotate.axis.y + 65 to->rotate.axis.z * to->rotate.axis.z; 66 67 if (length_2 <= kAngleEpsilon || other_length_2 <= kAngleEpsilon) 68 return false; 69 70 SkMScalar dot = to->rotate.axis.x * from->rotate.axis.x + 71 to->rotate.axis.y * from->rotate.axis.y + 72 to->rotate.axis.z * from->rotate.axis.z; 73 SkMScalar error = 74 std::abs(SK_MScalar1 - (dot * dot) / (length_2 * other_length_2)); 75 bool result = error < kAngleEpsilon; 76 if (result) { 77 *axis_x = to->rotate.axis.x; 78 *axis_y = to->rotate.axis.y; 79 *axis_z = to->rotate.axis.z; 80 // If the axes are pointing in opposite directions, we need to reverse 81 // the angle. 82 *angle_from = dot > 0 ? from->rotate.angle : -from->rotate.angle; 83 } 84 return result; 85 } 86 87 static SkMScalar BlendSkMScalars(SkMScalar from, 88 SkMScalar to, 89 SkMScalar progress) { 90 return from * (1 - progress) + to * progress; 91 } 92 93 bool TransformOperation::BlendTransformOperations( 94 const TransformOperation* from, 95 const TransformOperation* to, 96 SkMScalar progress, 97 gfx::Transform* result) { 98 if (IsOperationIdentity(from) && IsOperationIdentity(to)) 99 return true; 100 101 TransformOperation::Type interpolation_type = 102 TransformOperation::TransformOperationIdentity; 103 if (IsOperationIdentity(to)) 104 interpolation_type = from->type; 105 else 106 interpolation_type = to->type; 107 108 switch (interpolation_type) { 109 case TransformOperation::TransformOperationTranslate: { 110 SkMScalar from_x = IsOperationIdentity(from) ? 0 : from->translate.x; 111 SkMScalar from_y = IsOperationIdentity(from) ? 0 : from->translate.y; 112 SkMScalar from_z = IsOperationIdentity(from) ? 0 : from->translate.z; 113 SkMScalar to_x = IsOperationIdentity(to) ? 0 : to->translate.x; 114 SkMScalar to_y = IsOperationIdentity(to) ? 0 : to->translate.y; 115 SkMScalar to_z = IsOperationIdentity(to) ? 0 : to->translate.z; 116 result->Translate3d(BlendSkMScalars(from_x, to_x, progress), 117 BlendSkMScalars(from_y, to_y, progress), 118 BlendSkMScalars(from_z, to_z, progress)); 119 break; 120 } 121 case TransformOperation::TransformOperationRotate: { 122 SkMScalar axis_x = 0; 123 SkMScalar axis_y = 0; 124 SkMScalar axis_z = 1; 125 SkMScalar from_angle = 0; 126 SkMScalar to_angle = IsOperationIdentity(to) ? 0 : to->rotate.angle; 127 if (ShareSameAxis(from, to, &axis_x, &axis_y, &axis_z, &from_angle)) { 128 result->RotateAbout(gfx::Vector3dF(axis_x, axis_y, axis_z), 129 BlendSkMScalars(from_angle, to_angle, progress)); 130 } else { 131 gfx::Transform to_matrix; 132 if (!IsOperationIdentity(to)) 133 to_matrix = to->matrix; 134 gfx::Transform from_matrix; 135 if (!IsOperationIdentity(from)) 136 from_matrix = from->matrix; 137 *result = to_matrix; 138 if (!result->Blend(from_matrix, progress)) 139 return false; 140 } 141 break; 142 } 143 case TransformOperation::TransformOperationScale: { 144 SkMScalar from_x = IsOperationIdentity(from) ? 1 : from->scale.x; 145 SkMScalar from_y = IsOperationIdentity(from) ? 1 : from->scale.y; 146 SkMScalar from_z = IsOperationIdentity(from) ? 1 : from->scale.z; 147 SkMScalar to_x = IsOperationIdentity(to) ? 1 : to->scale.x; 148 SkMScalar to_y = IsOperationIdentity(to) ? 1 : to->scale.y; 149 SkMScalar to_z = IsOperationIdentity(to) ? 1 : to->scale.z; 150 result->Scale3d(BlendSkMScalars(from_x, to_x, progress), 151 BlendSkMScalars(from_y, to_y, progress), 152 BlendSkMScalars(from_z, to_z, progress)); 153 break; 154 } 155 case TransformOperation::TransformOperationSkew: { 156 SkMScalar from_x = IsOperationIdentity(from) ? 0 : from->skew.x; 157 SkMScalar from_y = IsOperationIdentity(from) ? 0 : from->skew.y; 158 SkMScalar to_x = IsOperationIdentity(to) ? 0 : to->skew.x; 159 SkMScalar to_y = IsOperationIdentity(to) ? 0 : to->skew.y; 160 result->SkewX(BlendSkMScalars(from_x, to_x, progress)); 161 result->SkewY(BlendSkMScalars(from_y, to_y, progress)); 162 break; 163 } 164 case TransformOperation::TransformOperationPerspective: { 165 SkMScalar from_perspective_depth = 166 IsOperationIdentity(from) ? std::numeric_limits<SkMScalar>::max() 167 : from->perspective_depth; 168 SkMScalar to_perspective_depth = 169 IsOperationIdentity(to) ? std::numeric_limits<SkMScalar>::max() 170 : to->perspective_depth; 171 if (from_perspective_depth == 0.f || to_perspective_depth == 0.f) 172 return false; 173 174 SkMScalar blended_perspective_depth = BlendSkMScalars( 175 1.f / from_perspective_depth, 1.f / to_perspective_depth, progress); 176 177 if (blended_perspective_depth == 0.f) 178 return false; 179 180 result->ApplyPerspectiveDepth(1.f / blended_perspective_depth); 181 break; 182 } 183 case TransformOperation::TransformOperationMatrix: { 184 gfx::Transform to_matrix; 185 if (!IsOperationIdentity(to)) 186 to_matrix = to->matrix; 187 gfx::Transform from_matrix; 188 if (!IsOperationIdentity(from)) 189 from_matrix = from->matrix; 190 *result = to_matrix; 191 if (!result->Blend(from_matrix, progress)) 192 return false; 193 break; 194 } 195 case TransformOperation::TransformOperationIdentity: 196 // Do nothing. 197 break; 198 } 199 200 return true; 201 } 202 203 // If p = (px, py) is a point in the plane being rotated about (0, 0, nz), this 204 // function computes the angles we would have to rotate from p to get to 205 // (length(p), 0), (-length(p), 0), (0, length(p)), (0, -length(p)). If nz is 206 // negative, these angles will need to be reversed. 207 static void FindCandidatesInPlane(float px, 208 float py, 209 float nz, 210 double* candidates, 211 int* num_candidates) { 212 double phi = atan2(px, py); 213 *num_candidates = 4; 214 candidates[0] = phi; 215 for (int i = 1; i < *num_candidates; ++i) 216 candidates[i] = candidates[i - 1] + M_PI_2; 217 if (nz < 0.f) { 218 for (int i = 0; i < *num_candidates; ++i) 219 candidates[i] *= -1.f; 220 } 221 } 222 223 static float RadiansToDegrees(float radians) { 224 return (180.f * radians) / M_PI; 225 } 226 227 static float DegreesToRadians(float degrees) { 228 return (M_PI * degrees) / 180.f; 229 } 230 231 static void BoundingBoxForArc(const gfx::Point3F& point, 232 const TransformOperation* from, 233 const TransformOperation* to, 234 SkMScalar min_progress, 235 SkMScalar max_progress, 236 gfx::BoxF* box) { 237 const TransformOperation* exemplar = from ? from : to; 238 gfx::Vector3dF axis(exemplar->rotate.axis.x, 239 exemplar->rotate.axis.y, 240 exemplar->rotate.axis.z); 241 242 const bool x_is_zero = axis.x() == 0.f; 243 const bool y_is_zero = axis.y() == 0.f; 244 const bool z_is_zero = axis.z() == 0.f; 245 246 // We will have at most 6 angles to test (excluding from->angle and 247 // to->angle). 248 static const int kMaxNumCandidates = 6; 249 double candidates[kMaxNumCandidates]; 250 int num_candidates = kMaxNumCandidates; 251 252 if (x_is_zero && y_is_zero && z_is_zero) 253 return; 254 255 SkMScalar from_angle = from ? from->rotate.angle : 0.f; 256 SkMScalar to_angle = to ? to->rotate.angle : 0.f; 257 258 // If the axes of rotation are pointing in opposite directions, we need to 259 // flip one of the angles. Note, if both |from| and |to| exist, then axis will 260 // correspond to |from|. 261 if (from && to) { 262 gfx::Vector3dF other_axis( 263 to->rotate.axis.x, to->rotate.axis.y, to->rotate.axis.z); 264 if (gfx::DotProduct(axis, other_axis) < 0.f) 265 to_angle *= -1.f; 266 } 267 268 float min_degrees = 269 SkMScalarToFloat(BlendSkMScalars(from_angle, to_angle, min_progress)); 270 float max_degrees = 271 SkMScalarToFloat(BlendSkMScalars(from_angle, to_angle, max_progress)); 272 if (max_degrees < min_degrees) 273 std::swap(min_degrees, max_degrees); 274 275 gfx::Transform from_transform; 276 from_transform.RotateAbout(axis, min_degrees); 277 gfx::Transform to_transform; 278 to_transform.RotateAbout(axis, max_degrees); 279 280 *box = gfx::BoxF(); 281 282 gfx::Point3F point_rotated_from = point; 283 from_transform.TransformPoint(&point_rotated_from); 284 gfx::Point3F point_rotated_to = point; 285 to_transform.TransformPoint(&point_rotated_to); 286 287 box->set_origin(point_rotated_from); 288 box->ExpandTo(point_rotated_to); 289 290 if (x_is_zero && y_is_zero) { 291 FindCandidatesInPlane( 292 point.x(), point.y(), axis.z(), candidates, &num_candidates); 293 } else if (x_is_zero && z_is_zero) { 294 FindCandidatesInPlane( 295 point.z(), point.x(), axis.y(), candidates, &num_candidates); 296 } else if (y_is_zero && z_is_zero) { 297 FindCandidatesInPlane( 298 point.y(), point.z(), axis.x(), candidates, &num_candidates); 299 } else { 300 gfx::Vector3dF normal = axis; 301 normal.Scale(1.f / normal.Length()); 302 303 // First, find center of rotation. 304 gfx::Point3F origin; 305 gfx::Vector3dF to_point = point - origin; 306 gfx::Point3F center = 307 origin + gfx::ScaleVector3d(normal, gfx::DotProduct(to_point, normal)); 308 309 // Now we need to find two vectors in the plane of rotation. One pointing 310 // towards point and another, perpendicular vector in the plane. 311 gfx::Vector3dF v1 = point - center; 312 float v1_length = v1.Length(); 313 if (v1_length == 0.f) 314 return; 315 316 v1.Scale(1.f / v1_length); 317 gfx::Vector3dF v2 = gfx::CrossProduct(normal, v1); 318 // v1 is the basis vector in the direction of the point. 319 // i.e. with a rotation of 0, v1 is our +x vector. 320 // v2 is a perpenticular basis vector of our plane (+y). 321 322 // Take the parametric equation of a circle. 323 // x = r*cos(t); y = r*sin(t); 324 // We can treat that as a circle on the plane v1xv2. 325 // From that we get the parametric equations for a circle on the 326 // plane in 3d space of: 327 // x(t) = r*cos(t)*v1.x + r*sin(t)*v2.x + cx 328 // y(t) = r*cos(t)*v1.y + r*sin(t)*v2.y + cy 329 // z(t) = r*cos(t)*v1.z + r*sin(t)*v2.z + cz 330 // Taking the derivative of (x, y, z) and solving for 0 gives us our 331 // maximum/minimum x, y, z values. 332 // x'(t) = r*cos(t)*v2.x - r*sin(t)*v1.x = 0 333 // tan(t) = v2.x/v1.x 334 // t = atan2(v2.x, v1.x) + n*M_PI; 335 candidates[0] = atan2(v2.x(), v1.x()); 336 candidates[1] = candidates[0] + M_PI; 337 candidates[2] = atan2(v2.y(), v1.y()); 338 candidates[3] = candidates[2] + M_PI; 339 candidates[4] = atan2(v2.z(), v1.z()); 340 candidates[5] = candidates[4] + M_PI; 341 } 342 343 double min_radians = DegreesToRadians(min_degrees); 344 double max_radians = DegreesToRadians(max_degrees); 345 346 for (int i = 0; i < num_candidates; ++i) { 347 double radians = candidates[i]; 348 while (radians < min_radians) 349 radians += 2.0 * M_PI; 350 while (radians > max_radians) 351 radians -= 2.0 * M_PI; 352 if (radians < min_radians) 353 continue; 354 355 gfx::Transform rotation; 356 rotation.RotateAbout(axis, RadiansToDegrees(radians)); 357 gfx::Point3F rotated = point; 358 rotation.TransformPoint(&rotated); 359 360 box->ExpandTo(rotated); 361 } 362 } 363 364 bool TransformOperation::BlendedBoundsForBox(const gfx::BoxF& box, 365 const TransformOperation* from, 366 const TransformOperation* to, 367 SkMScalar min_progress, 368 SkMScalar max_progress, 369 gfx::BoxF* bounds) { 370 bool is_identity_from = IsOperationIdentity(from); 371 bool is_identity_to = IsOperationIdentity(to); 372 if (is_identity_from && is_identity_to) { 373 *bounds = box; 374 return true; 375 } 376 377 TransformOperation::Type interpolation_type = 378 TransformOperation::TransformOperationIdentity; 379 if (is_identity_to) 380 interpolation_type = from->type; 381 else 382 interpolation_type = to->type; 383 384 switch (interpolation_type) { 385 case TransformOperation::TransformOperationIdentity: 386 *bounds = box; 387 return true; 388 case TransformOperation::TransformOperationTranslate: 389 case TransformOperation::TransformOperationSkew: 390 case TransformOperation::TransformOperationPerspective: 391 case TransformOperation::TransformOperationScale: { 392 gfx::Transform from_transform; 393 gfx::Transform to_transform; 394 if (!BlendTransformOperations(from, to, min_progress, &from_transform) || 395 !BlendTransformOperations(from, to, max_progress, &to_transform)) 396 return false; 397 398 *bounds = box; 399 from_transform.TransformBox(bounds); 400 401 gfx::BoxF to_box = box; 402 to_transform.TransformBox(&to_box); 403 bounds->ExpandTo(to_box); 404 405 return true; 406 } 407 case TransformOperation::TransformOperationRotate: { 408 SkMScalar axis_x = 0; 409 SkMScalar axis_y = 0; 410 SkMScalar axis_z = 1; 411 SkMScalar from_angle = 0; 412 if (!ShareSameAxis(from, to, &axis_x, &axis_y, &axis_z, &from_angle)) 413 return false; 414 415 bool first_point = true; 416 for (int i = 0; i < 8; ++i) { 417 gfx::Point3F corner = box.origin(); 418 corner += gfx::Vector3dF(i & 1 ? box.width() : 0.f, 419 i & 2 ? box.height() : 0.f, 420 i & 4 ? box.depth() : 0.f); 421 gfx::BoxF box_for_arc; 422 BoundingBoxForArc( 423 corner, from, to, min_progress, max_progress, &box_for_arc); 424 if (first_point) 425 *bounds = box_for_arc; 426 else 427 bounds->Union(box_for_arc); 428 first_point = false; 429 } 430 return true; 431 } 432 case TransformOperation::TransformOperationMatrix: 433 return false; 434 } 435 NOTREACHED(); 436 return false; 437 } 438 439 } // namespace cc 440
