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 "cc/base/math_util.h"
6
7#include <algorithm>
8#include <cmath>
9#include <limits>
10
11#include "base/values.h"
12#include "ui/gfx/quad_f.h"
13#include "ui/gfx/rect.h"
14#include "ui/gfx/rect_conversions.h"
15#include "ui/gfx/rect_f.h"
16#include "ui/gfx/transform.h"
17#include "ui/gfx/vector2d_f.h"
18
19namespace cc {
20
21const double MathUtil::kPiDouble = 3.14159265358979323846;
22const float MathUtil::kPiFloat = 3.14159265358979323846f;
23
24static HomogeneousCoordinate ProjectHomogeneousPoint(
25    const gfx::Transform& transform,
26    gfx::PointF p) {
27  // In this case, the layer we are trying to project onto is perpendicular to
28  // ray (point p and z-axis direction) that we are trying to project. This
29  // happens when the layer is rotated so that it is infinitesimally thin, or
30  // when it is co-planar with the camera origin -- i.e. when the layer is
31  // invisible anyway.
32  if (!transform.matrix().get(2, 2))
33    return HomogeneousCoordinate(0.0, 0.0, 0.0, 1.0);
34
35  SkMScalar z = -(transform.matrix().get(2, 0) * p.x() +
36             transform.matrix().get(2, 1) * p.y() +
37             transform.matrix().get(2, 3)) /
38             transform.matrix().get(2, 2);
39  HomogeneousCoordinate result(p.x(), p.y(), z, 1.0);
40  transform.matrix().mapMScalars(result.vec, result.vec);
41  return result;
42}
43
44static HomogeneousCoordinate MapHomogeneousPoint(
45    const gfx::Transform& transform,
46    const gfx::Point3F& p) {
47  HomogeneousCoordinate result(p.x(), p.y(), p.z(), 1.0);
48  transform.matrix().mapMScalars(result.vec, result.vec);
49  return result;
50}
51
52static HomogeneousCoordinate ComputeClippedPointForEdge(
53    const HomogeneousCoordinate& h1,
54    const HomogeneousCoordinate& h2) {
55  // Points h1 and h2 form a line in 4d, and any point on that line can be
56  // represented as an interpolation between h1 and h2:
57  //    p = (1-t) h1 + (t) h2
58  //
59  // We want to compute point p such that p.w == epsilon, where epsilon is a
60  // small non-zero number. (but the smaller the number is, the higher the risk
61  // of overflow)
62  // To do this, we solve for t in the following equation:
63  //    p.w = epsilon = (1-t) * h1.w + (t) * h2.w
64  //
65  // Once paramter t is known, the rest of p can be computed via
66  //    p = (1-t) h1 + (t) h2.
67
68  // Technically this is a special case of the following assertion, but its a
69  // good idea to keep it an explicit sanity check here.
70  DCHECK_NE(h2.w(), h1.w());
71  // Exactly one of h1 or h2 (but not both) must be on the negative side of the
72  // w plane when this is called.
73  DCHECK(h1.ShouldBeClipped() ^ h2.ShouldBeClipped());
74
75  SkMScalar w = 0.00001;  // or any positive non-zero small epsilon
76
77  SkMScalar t = (w - h1.w()) / (h2.w() - h1.w());
78
79  SkMScalar x = (1 - t) * h1.x() + t * h2.x();
80  SkMScalar y = (1 - t) * h1.y() + t * h2.y();
81  SkMScalar z = (1 - t) * h1.z() + t * h2.z();
82
83  return HomogeneousCoordinate(x, y, z, w);
84}
85
86static inline void ExpandBoundsToIncludePoint(float* xmin,
87                                              float* xmax,
88                                              float* ymin,
89                                              float* ymax,
90                                              gfx::PointF p) {
91  *xmin = std::min(p.x(), *xmin);
92  *xmax = std::max(p.x(), *xmax);
93  *ymin = std::min(p.y(), *ymin);
94  *ymax = std::max(p.y(), *ymax);
95}
96
97static inline void AddVertexToClippedQuad(gfx::PointF new_vertex,
98                                          gfx::PointF clipped_quad[8],
99                                          int* num_vertices_in_clipped_quad) {
100  clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
101  (*num_vertices_in_clipped_quad)++;
102}
103
104gfx::Rect MathUtil::MapClippedRect(const gfx::Transform& transform,
105                                   gfx::Rect src_rect) {
106  return gfx::ToEnclosingRect(MapClippedRect(transform, gfx::RectF(src_rect)));
107}
108
109gfx::RectF MathUtil::MapClippedRect(const gfx::Transform& transform,
110                                    const gfx::RectF& src_rect) {
111  if (transform.IsIdentityOrTranslation())
112    return src_rect +
113           gfx::Vector2dF(
114               static_cast<float>(transform.matrix().getDouble(0, 3)),
115               static_cast<float>(transform.matrix().getDouble(1, 3)));
116
117  // Apply the transform, but retain the result in homogeneous coordinates.
118
119  double quad[4 * 2];  // input: 4 x 2D points
120  quad[0] = src_rect.x();
121  quad[1] = src_rect.y();
122  quad[2] = src_rect.right();
123  quad[3] = src_rect.y();
124  quad[4] = src_rect.right();
125  quad[5] = src_rect.bottom();
126  quad[6] = src_rect.x();
127  quad[7] = src_rect.bottom();
128
129  double result[4 * 4];  // output: 4 x 4D homogeneous points
130  transform.matrix().map2(quad, 4, result);
131
132  HomogeneousCoordinate hc0(result[0], result[1], result[2], result[3]);
133  HomogeneousCoordinate hc1(result[4], result[5], result[6], result[7]);
134  HomogeneousCoordinate hc2(result[8], result[9], result[10], result[11]);
135  HomogeneousCoordinate hc3(result[12], result[13], result[14], result[15]);
136  return ComputeEnclosingClippedRect(hc0, hc1, hc2, hc3);
137}
138
139gfx::RectF MathUtil::ProjectClippedRect(const gfx::Transform& transform,
140                                        const gfx::RectF& src_rect) {
141  if (transform.IsIdentityOrTranslation()) {
142    return src_rect +
143           gfx::Vector2dF(
144               static_cast<float>(transform.matrix().getDouble(0, 3)),
145               static_cast<float>(transform.matrix().getDouble(1, 3)));
146  }
147
148  // Perform the projection, but retain the result in homogeneous coordinates.
149  gfx::QuadF q = gfx::QuadF(src_rect);
150  HomogeneousCoordinate h1 = ProjectHomogeneousPoint(transform, q.p1());
151  HomogeneousCoordinate h2 = ProjectHomogeneousPoint(transform, q.p2());
152  HomogeneousCoordinate h3 = ProjectHomogeneousPoint(transform, q.p3());
153  HomogeneousCoordinate h4 = ProjectHomogeneousPoint(transform, q.p4());
154
155  return ComputeEnclosingClippedRect(h1, h2, h3, h4);
156}
157
158void MathUtil::MapClippedQuad(const gfx::Transform& transform,
159                              const gfx::QuadF& src_quad,
160                              gfx::PointF clipped_quad[8],
161                              int* num_vertices_in_clipped_quad) {
162  HomogeneousCoordinate h1 =
163      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p1()));
164  HomogeneousCoordinate h2 =
165      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p2()));
166  HomogeneousCoordinate h3 =
167      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p3()));
168  HomogeneousCoordinate h4 =
169      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p4()));
170
171  // The order of adding the vertices to the array is chosen so that
172  // clockwise / counter-clockwise orientation is retained.
173
174  *num_vertices_in_clipped_quad = 0;
175
176  if (!h1.ShouldBeClipped()) {
177    AddVertexToClippedQuad(
178        h1.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
179  }
180
181  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped()) {
182    AddVertexToClippedQuad(
183        ComputeClippedPointForEdge(h1, h2).CartesianPoint2d(),
184        clipped_quad,
185        num_vertices_in_clipped_quad);
186  }
187
188  if (!h2.ShouldBeClipped()) {
189    AddVertexToClippedQuad(
190        h2.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
191  }
192
193  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped()) {
194    AddVertexToClippedQuad(
195        ComputeClippedPointForEdge(h2, h3).CartesianPoint2d(),
196        clipped_quad,
197        num_vertices_in_clipped_quad);
198  }
199
200  if (!h3.ShouldBeClipped()) {
201    AddVertexToClippedQuad(
202        h3.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
203  }
204
205  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped()) {
206    AddVertexToClippedQuad(
207        ComputeClippedPointForEdge(h3, h4).CartesianPoint2d(),
208        clipped_quad,
209        num_vertices_in_clipped_quad);
210  }
211
212  if (!h4.ShouldBeClipped()) {
213    AddVertexToClippedQuad(
214        h4.CartesianPoint2d(), clipped_quad, num_vertices_in_clipped_quad);
215  }
216
217  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
218    AddVertexToClippedQuad(
219        ComputeClippedPointForEdge(h4, h1).CartesianPoint2d(),
220        clipped_quad,
221        num_vertices_in_clipped_quad);
222  }
223
224  DCHECK_LE(*num_vertices_in_clipped_quad, 8);
225}
226
227gfx::RectF MathUtil::ComputeEnclosingRectOfVertices(gfx::PointF vertices[],
228                                                    int num_vertices) {
229  if (num_vertices < 2)
230    return gfx::RectF();
231
232  float xmin = std::numeric_limits<float>::max();
233  float xmax = -std::numeric_limits<float>::max();
234  float ymin = std::numeric_limits<float>::max();
235  float ymax = -std::numeric_limits<float>::max();
236
237  for (int i = 0; i < num_vertices; ++i)
238    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax, vertices[i]);
239
240  return gfx::RectF(gfx::PointF(xmin, ymin),
241                    gfx::SizeF(xmax - xmin, ymax - ymin));
242}
243
244gfx::RectF MathUtil::ComputeEnclosingClippedRect(
245    const HomogeneousCoordinate& h1,
246    const HomogeneousCoordinate& h2,
247    const HomogeneousCoordinate& h3,
248    const HomogeneousCoordinate& h4) {
249  // This function performs clipping as necessary and computes the enclosing 2d
250  // gfx::RectF of the vertices. Doing these two steps simultaneously allows us
251  // to avoid the overhead of storing an unknown number of clipped vertices.
252
253  // If no vertices on the quad are clipped, then we can simply return the
254  // enclosing rect directly.
255  bool something_clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
256                           h3.ShouldBeClipped() || h4.ShouldBeClipped();
257  if (!something_clipped) {
258    gfx::QuadF mapped_quad = gfx::QuadF(h1.CartesianPoint2d(),
259                                        h2.CartesianPoint2d(),
260                                        h3.CartesianPoint2d(),
261                                        h4.CartesianPoint2d());
262    return mapped_quad.BoundingBox();
263  }
264
265  bool everything_clipped = h1.ShouldBeClipped() && h2.ShouldBeClipped() &&
266                            h3.ShouldBeClipped() && h4.ShouldBeClipped();
267  if (everything_clipped)
268    return gfx::RectF();
269
270  float xmin = std::numeric_limits<float>::max();
271  float xmax = -std::numeric_limits<float>::max();
272  float ymin = std::numeric_limits<float>::max();
273  float ymax = -std::numeric_limits<float>::max();
274
275  if (!h1.ShouldBeClipped())
276    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
277                               h1.CartesianPoint2d());
278
279  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped())
280    ExpandBoundsToIncludePoint(&xmin,
281                               &xmax,
282                               &ymin,
283                               &ymax,
284                               ComputeClippedPointForEdge(h1, h2)
285                                   .CartesianPoint2d());
286
287  if (!h2.ShouldBeClipped())
288    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
289                               h2.CartesianPoint2d());
290
291  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped())
292    ExpandBoundsToIncludePoint(&xmin,
293                               &xmax,
294                               &ymin,
295                               &ymax,
296                               ComputeClippedPointForEdge(h2, h3)
297                                   .CartesianPoint2d());
298
299  if (!h3.ShouldBeClipped())
300    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
301                               h3.CartesianPoint2d());
302
303  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped())
304    ExpandBoundsToIncludePoint(&xmin,
305                               &xmax,
306                               &ymin,
307                               &ymax,
308                               ComputeClippedPointForEdge(h3, h4)
309                                   .CartesianPoint2d());
310
311  if (!h4.ShouldBeClipped())
312    ExpandBoundsToIncludePoint(&xmin, &xmax, &ymin, &ymax,
313                               h4.CartesianPoint2d());
314
315  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped())
316    ExpandBoundsToIncludePoint(&xmin,
317                               &xmax,
318                               &ymin,
319                               &ymax,
320                               ComputeClippedPointForEdge(h4, h1)
321                                   .CartesianPoint2d());
322
323  return gfx::RectF(gfx::PointF(xmin, ymin),
324                    gfx::SizeF(xmax - xmin, ymax - ymin));
325}
326
327gfx::QuadF MathUtil::MapQuad(const gfx::Transform& transform,
328                             const gfx::QuadF& q,
329                             bool* clipped) {
330  if (transform.IsIdentityOrTranslation()) {
331    gfx::QuadF mapped_quad(q);
332    mapped_quad +=
333        gfx::Vector2dF(static_cast<float>(transform.matrix().getDouble(0, 3)),
334                       static_cast<float>(transform.matrix().getDouble(1, 3)));
335    *clipped = false;
336    return mapped_quad;
337  }
338
339  HomogeneousCoordinate h1 =
340      MapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
341  HomogeneousCoordinate h2 =
342      MapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
343  HomogeneousCoordinate h3 =
344      MapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
345  HomogeneousCoordinate h4 =
346      MapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
347
348  *clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
349            h3.ShouldBeClipped() || h4.ShouldBeClipped();
350
351  // Result will be invalid if clipped == true. But, compute it anyway just in
352  // case, to emulate existing behavior.
353  return gfx::QuadF(h1.CartesianPoint2d(),
354                    h2.CartesianPoint2d(),
355                    h3.CartesianPoint2d(),
356                    h4.CartesianPoint2d());
357}
358
359gfx::PointF MathUtil::MapPoint(const gfx::Transform& transform,
360                               gfx::PointF p,
361                               bool* clipped) {
362  HomogeneousCoordinate h = MapHomogeneousPoint(transform, gfx::Point3F(p));
363
364  if (h.w() > 0) {
365    *clipped = false;
366    return h.CartesianPoint2d();
367  }
368
369  // The cartesian coordinates will be invalid after dividing by w.
370  *clipped = true;
371
372  // Avoid dividing by w if w == 0.
373  if (!h.w())
374    return gfx::PointF();
375
376  // This return value will be invalid because clipped == true, but (1) users of
377  // this code should be ignoring the return value when clipped == true anyway,
378  // and (2) this behavior is more consistent with existing behavior of WebKit
379  // transforms if the user really does not ignore the return value.
380  return h.CartesianPoint2d();
381}
382
383gfx::Point3F MathUtil::MapPoint(const gfx::Transform& transform,
384                                const gfx::Point3F& p,
385                                bool* clipped) {
386  HomogeneousCoordinate h = MapHomogeneousPoint(transform, p);
387
388  if (h.w() > 0) {
389    *clipped = false;
390    return h.CartesianPoint3d();
391  }
392
393  // The cartesian coordinates will be invalid after dividing by w.
394  *clipped = true;
395
396  // Avoid dividing by w if w == 0.
397  if (!h.w())
398    return gfx::Point3F();
399
400  // This return value will be invalid because clipped == true, but (1) users of
401  // this code should be ignoring the return value when clipped == true anyway,
402  // and (2) this behavior is more consistent with existing behavior of WebKit
403  // transforms if the user really does not ignore the return value.
404  return h.CartesianPoint3d();
405}
406
407gfx::QuadF MathUtil::ProjectQuad(const gfx::Transform& transform,
408                                 const gfx::QuadF& q,
409                                 bool* clipped) {
410  gfx::QuadF projected_quad;
411  bool clipped_point;
412  projected_quad.set_p1(ProjectPoint(transform, q.p1(), &clipped_point));
413  *clipped = clipped_point;
414  projected_quad.set_p2(ProjectPoint(transform, q.p2(), &clipped_point));
415  *clipped |= clipped_point;
416  projected_quad.set_p3(ProjectPoint(transform, q.p3(), &clipped_point));
417  *clipped |= clipped_point;
418  projected_quad.set_p4(ProjectPoint(transform, q.p4(), &clipped_point));
419  *clipped |= clipped_point;
420
421  return projected_quad;
422}
423
424gfx::PointF MathUtil::ProjectPoint(const gfx::Transform& transform,
425                                   gfx::PointF p,
426                                   bool* clipped) {
427  HomogeneousCoordinate h = ProjectHomogeneousPoint(transform, p);
428
429  if (h.w() > 0) {
430    // The cartesian coordinates will be valid in this case.
431    *clipped = false;
432    return h.CartesianPoint2d();
433  }
434
435  // The cartesian coordinates will be invalid after dividing by w.
436  *clipped = true;
437
438  // Avoid dividing by w if w == 0.
439  if (!h.w())
440    return gfx::PointF();
441
442  // This return value will be invalid because clipped == true, but (1) users of
443  // this code should be ignoring the return value when clipped == true anyway,
444  // and (2) this behavior is more consistent with existing behavior of WebKit
445  // transforms if the user really does not ignore the return value.
446  return h.CartesianPoint2d();
447}
448
449static inline float ScaleOnAxis(double a, double b, double c) {
450  return std::sqrt(a * a + b * b + c * c);
451}
452
453gfx::Vector2dF MathUtil::ComputeTransform2dScaleComponents(
454    const gfx::Transform& transform,
455    float fallback_value) {
456  if (transform.HasPerspective())
457    return gfx::Vector2dF(fallback_value, fallback_value);
458  float x_scale = ScaleOnAxis(transform.matrix().getDouble(0, 0),
459                              transform.matrix().getDouble(1, 0),
460                              transform.matrix().getDouble(2, 0));
461  float y_scale = ScaleOnAxis(transform.matrix().getDouble(0, 1),
462                              transform.matrix().getDouble(1, 1),
463                              transform.matrix().getDouble(2, 1));
464  return gfx::Vector2dF(x_scale, y_scale);
465}
466
467float MathUtil::SmallestAngleBetweenVectors(gfx::Vector2dF v1,
468                                            gfx::Vector2dF v2) {
469  double dot_product = gfx::DotProduct(v1, v2) / v1.Length() / v2.Length();
470  // Clamp to compensate for rounding errors.
471  dot_product = std::max(-1.0, std::min(1.0, dot_product));
472  return static_cast<float>(Rad2Deg(std::acos(dot_product)));
473}
474
475gfx::Vector2dF MathUtil::ProjectVector(gfx::Vector2dF source,
476                                       gfx::Vector2dF destination) {
477  float projected_length =
478      gfx::DotProduct(source, destination) / destination.LengthSquared();
479  return gfx::Vector2dF(projected_length * destination.x(),
480                        projected_length * destination.y());
481}
482
483scoped_ptr<base::Value> MathUtil::AsValue(gfx::Size s) {
484  scoped_ptr<base::DictionaryValue> res(new base::DictionaryValue());
485  res->SetDouble("width", s.width());
486  res->SetDouble("height", s.height());
487  return res.PassAs<base::Value>();
488}
489
490scoped_ptr<base::Value> MathUtil::AsValue(gfx::SizeF s) {
491  scoped_ptr<base::DictionaryValue> res(new base::DictionaryValue());
492  res->SetDouble("width", s.width());
493  res->SetDouble("height", s.height());
494  return res.PassAs<base::Value>();
495}
496
497scoped_ptr<base::Value> MathUtil::AsValue(gfx::Rect r) {
498  scoped_ptr<base::ListValue> res(new base::ListValue());
499  res->AppendInteger(r.x());
500  res->AppendInteger(r.y());
501  res->AppendInteger(r.width());
502  res->AppendInteger(r.height());
503  return res.PassAs<base::Value>();
504}
505
506bool MathUtil::FromValue(const base::Value* raw_value, gfx::Rect* out_rect) {
507  const base::ListValue* value = NULL;
508  if (!raw_value->GetAsList(&value))
509    return false;
510
511  if (value->GetSize() != 4)
512    return false;
513
514  int x, y, w, h;
515  bool ok = true;
516  ok &= value->GetInteger(0, &x);
517  ok &= value->GetInteger(1, &y);
518  ok &= value->GetInteger(2, &w);
519  ok &= value->GetInteger(3, &h);
520  if (!ok)
521    return false;
522
523  *out_rect = gfx::Rect(x, y, w, h);
524  return true;
525}
526
527scoped_ptr<base::Value> MathUtil::AsValue(gfx::PointF pt) {
528  scoped_ptr<base::ListValue> res(new base::ListValue());
529  res->AppendDouble(pt.x());
530  res->AppendDouble(pt.y());
531  return res.PassAs<base::Value>();
532}
533
534scoped_ptr<base::Value> MathUtil::AsValue(const gfx::QuadF& q) {
535  scoped_ptr<base::ListValue> res(new base::ListValue());
536  res->AppendDouble(q.p1().x());
537  res->AppendDouble(q.p1().y());
538  res->AppendDouble(q.p2().x());
539  res->AppendDouble(q.p2().y());
540  res->AppendDouble(q.p3().x());
541  res->AppendDouble(q.p3().y());
542  res->AppendDouble(q.p4().x());
543  res->AppendDouble(q.p4().y());
544  return res.PassAs<base::Value>();
545}
546
547scoped_ptr<base::Value> MathUtil::AsValue(const gfx::RectF& rect) {
548  scoped_ptr<base::ListValue> res(new base::ListValue());
549  res->AppendDouble(rect.x());
550  res->AppendDouble(rect.y());
551  res->AppendDouble(rect.width());
552  res->AppendDouble(rect.height());
553  return res.PassAs<base::Value>();
554}
555
556scoped_ptr<base::Value> MathUtil::AsValue(const gfx::Transform& transform) {
557  scoped_ptr<base::ListValue> res(new base::ListValue());
558  const SkMatrix44& m = transform.matrix();
559  for (int row = 0; row < 4; ++row) {
560    for (int col = 0; col < 4; ++col)
561      res->AppendDouble(m.getDouble(row, col));
562  }
563  return res.PassAs<base::Value>();
564}
565
566scoped_ptr<base::Value> MathUtil::AsValueSafely(double value) {
567  return scoped_ptr<base::Value>(base::Value::CreateDoubleValue(
568      std::min(value, std::numeric_limits<double>::max())));
569}
570
571scoped_ptr<base::Value> MathUtil::AsValueSafely(float value) {
572  return scoped_ptr<base::Value>(base::Value::CreateDoubleValue(
573      std::min(value, std::numeric_limits<float>::max())));
574}
575
576}  // namespace cc
577