cc/base/math_util.h

   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 #ifndef CC_BASE_MATH_UTIL_H_
   6 #define CC_BASE_MATH_UTIL_H_
   7
   8 #include <algorithm>
   9 #include <cmath>
  10 #include <vector>
  11
  12 #include "base/logging.h"
  13 #include "base/memory/scoped_ptr.h"
  14 #include "cc/base/cc_export.h"
  15 #include "ui/gfx/geometry/box_f.h"
  16 #include "ui/gfx/geometry/point3_f.h"
  17 #include "ui/gfx/geometry/point_f.h"
  18 #include "ui/gfx/geometry/scroll_offset.h"
  19 #include "ui/gfx/geometry/size.h"
  20 #include "ui/gfx/transform.h"
  21
  22 namespace base {
  23 class Value;
  24 namespace trace_event {
  25 class TracedValue;
  26 }
  27 }  // namespace base
  28
  29 namespace gfx {
  30 class QuadF;
  31 class Rect;
  32 class RectF;
  33 class Transform;
  34 class Vector2dF;
  35 class Vector2d;
  36 class Vector3dF;
  37 }
  38
  39 namespace cc {
  40
  41 struct HomogeneousCoordinate {
  42   HomogeneousCoordinate(SkMScalar x, SkMScalar y, SkMScalar z, SkMScalar w) {
  43     vec[0] = x;
  44     vec[1] = y;
  45     vec[2] = z;
  46     vec[3] = w;
  47   }
  48
  49   bool ShouldBeClipped() const { return w() <= 0.0; }
  50
  51   gfx::PointF CartesianPoint2d() const {
  52     if (w() == SK_MScalar1)
  53       return gfx::PointF(x(), y());
  54
  55     // For now, because this code is used privately only by MathUtil, it should
  56     // never be called when w == 0, and we do not yet need to handle that case.
  57     DCHECK(w());
  58     SkMScalar inv_w = SK_MScalar1 / w();
  59     return gfx::PointF(x() * inv_w, y() * inv_w);
  60   }
  61
  62   gfx::Point3F CartesianPoint3d() const {
  63     if (w() == SK_MScalar1)
  64       return gfx::Point3F(x(), y(), z());
  65
  66     // For now, because this code is used privately only by MathUtil, it should
  67     // never be called when w == 0, and we do not yet need to handle that case.
  68     DCHECK(w());
  69     SkMScalar inv_w = SK_MScalar1 / w();
  70     return gfx::Point3F(x() * inv_w, y() * inv_w, z() * inv_w);
  71   }
  72
  73   SkMScalar x() const { return vec[0]; }
  74   SkMScalar y() const { return vec[1]; }
  75   SkMScalar z() const { return vec[2]; }
  76   SkMScalar w() const { return vec[3]; }
  77
  78   SkMScalar vec[4];
  79 };
  80
  81 class CC_EXPORT MathUtil {
  82  public:
  83   static const double kPiDouble;
  84   static const float kPiFloat;
  85
  86   static double Deg2Rad(double deg) { return deg * kPiDouble / 180.0; }
  87   static double Rad2Deg(double rad) { return rad * 180.0 / kPiDouble; }
  88
  89   static float Deg2Rad(float deg) { return deg * kPiFloat / 180.0f; }
  90   static float Rad2Deg(float rad) { return rad * 180.0f / kPiFloat; }
  91
  92   static float Round(float f) {
  93     return (f > 0.f) ? std::floor(f + 0.5f) : std::ceil(f - 0.5f);
  94   }
  95   static double Round(double d) {
  96     return (d > 0.0) ? std::floor(d + 0.5) : std::ceil(d - 0.5);
  97   }
  98
  99   // Returns true if rounded up value does not overflow, false otherwise.
 100   template <typename T>
 101   static bool VerifyRoundup(T n, T mul) {
 102     return mul && (n <= (std::numeric_limits<T>::max() -
 103                          (std::numeric_limits<T>::max() % mul)));
 104   }
 105
 106   // Rounds up a given |n| to be a multiple of |mul|, but may overflow.
 107   // Examples:
 108   //    - RoundUp(123, 50) returns 150.
 109   //    - RoundUp(-123, 50) returns -100.
 110   template <typename T>
 111   static T UncheckedRoundUp(T n, T mul) {
 112     static_assert(std::numeric_limits<T>::is_integer,
 113                   "T must be an integer type");
 114     DCHECK(VerifyRoundup(n, mul));
 115     return RoundUpInternal(n, mul);
 116   }
 117
 118   // Similar to UncheckedRoundUp(), but dies with a CRASH() if rounding up a
 119   // given |n| overflows T.
 120   template <typename T>
 121   static T CheckedRoundUp(T n, T mul) {
 122     static_assert(std::numeric_limits<T>::is_integer,
 123                   "T must be an integer type");
 124     CHECK(VerifyRoundup(n, mul));
 125     return RoundUpInternal(n, mul);
 126   }
 127
 128   // Returns true if rounded down value does not underflow, false otherwise.
 129   template <typename T>
 130   static bool VerifyRoundDown(T n, T mul) {
 131     return mul && (n >= (std::numeric_limits<T>::min() -
 132                          (std::numeric_limits<T>::min() % mul)));
 133   }
 134
 135   // Rounds down a given |n| to be a multiple of |mul|, but may underflow.
 136   // Examples:
 137   //    - RoundDown(123, 50) returns 100.
 138   //    - RoundDown(-123, 50) returns -150.
 139   template <typename T>
 140   static T UncheckedRoundDown(T n, T mul) {
 141     static_assert(std::numeric_limits<T>::is_integer,
 142                   "T must be an integer type");
 143     DCHECK(VerifyRoundDown(n, mul));
 144     return RoundDownInternal(n, mul);
 145   }
 146
 147   // Similar to UncheckedRoundDown(), but dies with a CRASH() if rounding down a
 148   // given |n| underflows T.
 149   template <typename T>
 150   static T CheckedRoundDown(T n, T mul) {
 151     static_assert(std::numeric_limits<T>::is_integer,
 152                   "T must be an integer type");
 153     CHECK(VerifyRoundDown(n, mul));
 154     return RoundDownInternal(n, mul);
 155   }
 156
 157   template <typename T> static T ClampToRange(T value, T min, T max) {
 158     return std::min(std::max(value, min), max);
 159   }
 160
 161   // Background: Existing transform code does not do the right thing in
 162   // MapRect / MapQuad / ProjectQuad when there is a perspective projection that
 163   // causes one of the transformed vertices to go to w < 0. In those cases, it
 164   // is necessary to perform clipping in homogeneous coordinates, after applying
 165   // the transform, before dividing-by-w to convert to cartesian coordinates.
 166   //
 167   // These functions return the axis-aligned rect that encloses the correctly
 168   // clipped, transformed polygon.
 169   static gfx::Rect MapEnclosingClippedRect(const gfx::Transform& transform,
 170                                            const gfx::Rect& rect);
 171   static gfx::RectF MapClippedRect(const gfx::Transform& transform,
 172                                    const gfx::RectF& rect);
 173   static gfx::Rect ProjectEnclosingClippedRect(const gfx::Transform& transform,
 174                                                const gfx::Rect& rect);
 175   static gfx::RectF ProjectClippedRect(const gfx::Transform& transform,
 176                                        const gfx::RectF& rect);
 177
 178   // This function is only valid when the transform preserves 2d axis
 179   // alignment and the resulting rect will not be clipped.
 180   static gfx::Rect MapEnclosedRectWith2dAxisAlignedTransform(
 181       const gfx::Transform& transform,
 182       const gfx::Rect& rect);
 183
 184   // Returns an array of vertices that represent the clipped polygon. After
 185   // returning, indexes from 0 to num_vertices_in_clipped_quad are valid in the
 186   // clipped_quad array. Note that num_vertices_in_clipped_quad may be zero,
 187   // which means the entire quad was clipped, and none of the vertices in the
 188   // array are valid.
 189   static void MapClippedQuad(const gfx::Transform& transform,
 190                              const gfx::QuadF& src_quad,
 191                              gfx::PointF clipped_quad[8],
 192                              int* num_vertices_in_clipped_quad);
 193   static bool MapClippedQuad3d(const gfx::Transform& transform,
 194                                const gfx::QuadF& src_quad,
 195                                gfx::Point3F clipped_quad[8],
 196                                int* num_vertices_in_clipped_quad);
 197
 198   static gfx::RectF ComputeEnclosingRectOfVertices(const gfx::PointF vertices[],
 199                                                    int num_vertices);
 200   static gfx::RectF ComputeEnclosingClippedRect(
 201       const HomogeneousCoordinate& h1,
 202       const HomogeneousCoordinate& h2,
 203       const HomogeneousCoordinate& h3,
 204       const HomogeneousCoordinate& h4);
 205
 206   // NOTE: These functions do not do correct clipping against w = 0 plane, but
 207   // they correctly detect the clipped condition via the boolean clipped.
 208   static gfx::QuadF MapQuad(const gfx::Transform& transform,
 209                             const gfx::QuadF& quad,
 210                             bool* clipped);
 211   static gfx::QuadF MapQuad3d(const gfx::Transform& transform,
 212                               const gfx::QuadF& q,
 213                               gfx::Point3F* p,
 214                               bool* clipped);
 215   static gfx::PointF MapPoint(const gfx::Transform& transform,
 216                               const gfx::PointF& point,
 217                               bool* clipped);
 218   static gfx::Point3F MapPoint(const gfx::Transform&,
 219                                const gfx::Point3F&,
 220                                bool* clipped);
 221   static gfx::QuadF ProjectQuad(const gfx::Transform& transform,
 222                                 const gfx::QuadF& quad,
 223                                 bool* clipped);
 224   static gfx::PointF ProjectPoint(const gfx::Transform& transform,
 225                                   const gfx::PointF& point,
 226                                   bool* clipped);
 227   // Identical to the above function, but coerces the homogeneous coordinate to
 228   // a 3d rather than a 2d point.
 229   static gfx::Point3F ProjectPoint3D(const gfx::Transform& transform,
 230                                      const gfx::PointF& point,
 231                                      bool* clipped);
 232
 233   static gfx::Vector2dF ComputeTransform2dScaleComponents(const gfx::Transform&,
 234                                                           float fallbackValue);
 235
 236   // Makes a rect that has the same relationship to input_outer_rect as
 237   // scale_inner_rect has to scale_outer_rect. scale_inner_rect should be
 238   // contained within scale_outer_rect, and likewise the rectangle that is
 239   // returned will be within input_outer_rect at a similar relative, scaled
 240   // position.
 241   static gfx::RectF ScaleRectProportional(const gfx::RectF& input_outer_rect,
 242                                           const gfx::RectF& scale_outer_rect,
 243                                           const gfx::RectF& scale_inner_rect);
 244
 245   // Returns the smallest angle between the given two vectors in degrees.
 246   // Neither vector is assumed to be normalized.
 247   static float SmallestAngleBetweenVectors(const gfx::Vector2dF& v1,
 248                                            const gfx::Vector2dF& v2);
 249
 250   // Projects the |source| vector onto |destination|. Neither vector is assumed
 251   // to be normalized.
 252   static gfx::Vector2dF ProjectVector(const gfx::Vector2dF& source,
 253                                       const gfx::Vector2dF& destination);
 254
 255   // Conversion to value.
 256   static scoped_ptr<base::Value> AsValue(const gfx::Size& s);
 257   static scoped_ptr<base::Value> AsValue(const gfx::Rect& r);
 258   static bool FromValue(const base::Value*, gfx::Rect* out_rect);
 259   static scoped_ptr<base::Value> AsValue(const gfx::PointF& q);
 260
 261   static void AddToTracedValue(const char* name,
 262                                const gfx::Size& s,
 263                                base::trace_event::TracedValue* res);
 264   static void AddToTracedValue(const char* name,
 265                                const gfx::SizeF& s,
 266                                base::trace_event::TracedValue* res);
 267   static void AddToTracedValue(const char* name,
 268                                const gfx::Rect& r,
 269                                base::trace_event::TracedValue* res);
 270   static void AddToTracedValue(const char* name,
 271                                const gfx::PointF& q,
 272                                base::trace_event::TracedValue* res);
 273   static void AddToTracedValue(const char* name,
 274                                const gfx::Point3F&,
 275                                base::trace_event::TracedValue* res);
 276   static void AddToTracedValue(const char* name,
 277                                const gfx::Vector2d& v,
 278                                base::trace_event::TracedValue* res);
 279   static void AddToTracedValue(const char* name,
 280                                const gfx::Vector2dF& v,
 281                                base::trace_event::TracedValue* res);
 282   static void AddToTracedValue(const char* name,
 283                                const gfx::ScrollOffset& v,
 284                                base::trace_event::TracedValue* res);
 285   static void AddToTracedValue(const char* name,
 286                                const gfx::QuadF& q,
 287                                base::trace_event::TracedValue* res);
 288   static void AddToTracedValue(const char* name,
 289                                const gfx::RectF& rect,
 290                                base::trace_event::TracedValue* res);
 291   static void AddToTracedValue(const char* name,
 292                                const gfx::Transform& transform,
 293                                base::trace_event::TracedValue* res);
 294   static void AddToTracedValue(const char* name,
 295                                const gfx::BoxF& box,
 296                                base::trace_event::TracedValue* res);
 297
 298   // Returns a base::Value representation of the floating point value.
 299   // If the value is inf, returns max double/float representation.
 300   static double AsDoubleSafely(double value);
 301   static float AsFloatSafely(float value);
 302
 303   // Returns vector that x axis (1,0,0) transforms to under given transform.
 304   static gfx::Vector3dF GetXAxis(const gfx::Transform& transform);
 305
 306   // Returns vector that y axis (0,1,0) transforms to under given transform.
 307   static gfx::Vector3dF GetYAxis(const gfx::Transform& transform);
 308
 309  private:
 310   template <typename T>
 311   static T RoundUpInternal(T n, T mul) {
 312     return (n > 0) ? ((n + mul - 1) / mul) * mul : (n / mul) * mul;
 313   }
 314
 315   template <typename T>
 316   static T RoundDownInternal(T n, T mul) {
 317     return (n > 0) ? (n / mul) * mul : (n == 0) ? 0
 318                                                 : ((n - mul + 1) / mul) * mul;
 319   }
 320 };
 321
 322 }  // namespace cc
 323
 324 #endif  // CC_BASE_MATH_UTIL_H_