transform_operation.cc 19 KB

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