SkCubicSolver.h 1.8 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
  1. /*
  2. * Copyright 2018 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef SkCubicSolver_DEFINED
  8. #define SkCubicSolver_DEFINED
  9. #include "include/core/SkTypes.h"
  10. #include "include/private/SkFloatingPoint.h"
  11. //#define CUBICMAP_TRACK_MAX_ERROR
  12. namespace SK_OPTS_NS {
  13. static float eval_poly(float t, float b) {
  14. return b;
  15. }
  16. template <typename... Rest>
  17. static float eval_poly(float t, float m, float b, Rest... rest) {
  18. return eval_poly(t, sk_fmaf(m,t,b), rest...);
  19. }
  20. inline float cubic_solver(float A, float B, float C, float D) {
  21. #ifdef CUBICMAP_TRACK_MAX_ERROR
  22. static int max_iters = 0;
  23. #endif
  24. #ifdef SK_DEBUG
  25. auto valid = [](float t) {
  26. return t >= 0 && t <= 1;
  27. };
  28. #endif
  29. auto guess_nice_cubic_root = [](float a, float b, float c, float d) {
  30. return -d;
  31. };
  32. float t = guess_nice_cubic_root(A, B, C, D);
  33. int iters = 0;
  34. const int MAX_ITERS = 8;
  35. for (; iters < MAX_ITERS; ++iters) {
  36. SkASSERT(valid(t));
  37. float f = eval_poly(t, A,B,C,D); // f = At^3 + Bt^2 + Ct + D
  38. if (sk_float_abs(f) <= 0.00005f) {
  39. break;
  40. }
  41. float fp = eval_poly(t, 3*A, 2*B, C); // f' = 3At^2 + 2Bt + C
  42. float fpp = eval_poly(t, 3*A+3*A, 2*B); // f'' = 6At + 2B
  43. float numer = 2 * fp * f;
  44. float denom = sk_fmaf(2*fp, fp, -(f*fpp));
  45. t -= numer / denom;
  46. }
  47. #ifdef CUBICMAP_TRACK_MAX_ERROR
  48. if (max_iters < iters) {
  49. max_iters = iters;
  50. SkDebugf("max_iters %d\n", max_iters);
  51. }
  52. #endif
  53. SkASSERT(valid(t));
  54. return t;
  55. }
  56. } // namespace SK_OPTS_NS
  57. #endif