HDK
UT_RootFinder.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Root finding (C++)
7  *
9  *
10  */
11
12 #ifndef _UT_RootFinder_h_
13 #define _UT_RootFinder_h_
14
15 #include "UT_API.h"
16
17 #include "UT_MatrixFwd.h"
18 #include "UT_VectorFwd.h"
19 #include "UT_VectorTypes.h"
20 #include "UT_Complex.h"
21 #include <SYS/SYS_Types.h>
22
23 template <typename T>
25 {
26 public:
27  // 1D root finders:
28  //
29
30  // Finds the real roots of a polynomial. The coefficients of the
31  // polynomial are specified in 'cf'. 'cf(i)' should contain the
32  // coefficient for x^i.
33  //
34  // The roots are appended to 'roots'
35  static void laguerre(const UT_ValArray<T> &cf, UT_ValArray<T> &roots,
36  int maxIters = 200);
37
38  // Returns number of real roots. The roots are found in v0 & v1.
39  // This is quite a stable solver handling many bad cases.
40  //
41  // Note: if a, b and c are all zero, this function will return
42  // zero roots, even though the equation is zero for all values of v.
43  static int quadratic(T a, T b, T c, T &v0, T &v1);
44
45  // Returns number of real roots but calculates all of the roots,
46  // the real returned in r_roots and imaginary in i_roots
47  static int quadratic(T a, T b, T c,
48  UT_Vector2T<T> &r_roots, UT_Vector2T<T> &i_roots);
49
50  // Returns number of real roots. The roots are found in v0, v1, & v2.
51  // a*v^3 + b*v^2 + c*v + d = 0
52  //
53  // Note: if a, b, c and d are all zero, this function will return
54  // zero roots, even though the equation is zero for all values of v.
55  static int cubic(T a, T b, T c, T d, T &v0, T &v1, T &v2);
56
57  // Returns number of real roots. Finds all the roots, however,
58  // real parts in r_roots and imaginary in i_roots
59  //
60  // Note: if a, b, c and d are all zero, this function will return
61  // zero roots, even though the equation is zero for all values of v.
62  static int cubic(T a, T b, T c, T d,
63  UT_Vector3T<T> &r_roots, UT_Vector3T<T> &i_roots);
64
65  // Returns number of real roots. The user must provide an interval [x1,x2]
66  // which is to contain the roots they're interested in. It is possible that
67  // roots virtually on the end points might be missed, so increase your
68  // interval to compensate.
69  static int cubic(T a, T b, T c, T d, T x1, T x2, T r[3]);
70
71  // Returns number of real roots. The user must provide an interval [x1,x2]
72  // which is to contain the roots they're interested in. It is possible that
73  // roots virtually on the end points might be missed, so increase your
74  // interval to compensate.
75  static int quartic(T a, T b, T c, T d, T e, T x1, T x2, T r[4]);
76
77
78  // No derivative is needed. Root bracketed by [x1,x2].
79  static int brent(T (*func)(T x, void *data), void *data,
80  T x1, T x2, T tol, T &result, int maxIter=200);
81
82  // Derivative is needed. Root bracketed by [x1,x2].
83  static int newton(void (*func)(T x, T &val, T &der, void *data), void *data,
84  T x1, T x2, T tol, T &result, int maxIter=200);
85
86  // Multi-dimensional root finders:
87  //
88
89  // Jacobian is needed. Specify initial guess in result.
90  template <typename S>
91  static int newton(void (*func)(const UT_VectorT<S> &x, UT_VectorT<S> &val, UT_MatrixT<T> &jacobi, void *data),
92  void *data,
93  S tolx, S tolf,
94  UT_VectorT<S> &result, int maxIter=200);
95
96  // Jacobian is needed. Specify initial guess in result.
97  // [x1,x2] specify the boundary that the func is defined within.
98  template <typename S>
99  static int newton(void (*func)(const UT_VectorT<S> &x, UT_VectorT<S> &val, UT_MatrixT<T> &jacobi, void *data),
100  void *data,
101  const UT_VectorT<S> &x1, const UT_VectorT<S> &x2,
102  S tolx, S tolf,
103  UT_VectorT<S> &result, int maxIter=200);
104 };
105
106 // Specialized cubic root finder to evaluate bezier curve parametric coordinate
107 // given a local time.
108 // Only the d coefficient depends on the evaluation time.
109 template <typename T>
111 {
112 public:
113  void init(T a, T b, T c, T d);
114
115  T findRoot(T t) const;
116
117 private:
118  T _fa,_fb,_fc,_fd;
119  T _a,_b,_c;
120  bool _a_less_than_tiny;
121  fpreal64 _inva;
122  fpreal64 _Q, _R, _Q3, _R2;
123  fpreal64 _m2Q;
124  fpreal64 _sqrtQ3;
125  fpreal64 _b_div_3;
126 };
127
132
137
138 #endif
UT_RootFinderT< float > UT_RootFinder
UT_RootFinderT< fpreal64 > UT_RootFinderD
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
#define UT_API
Definition: UT_API.h:14
**But if you need a result
UT_BezierRootFinderT< fpreal64 > UT_BezierRootFinderD
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:818
UT_RootFinderT< fpreal > UT_RootFinderR
3D Vector class.
2D Vector class.
Definition: UT_Vector2.h:159
GLdouble GLdouble x2
double fpreal64
Definition: SYS_Types.h:201
UT_RootFinderT< fpreal32 > UT_RootFinderF
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
GLint GLenum GLint x
Definition: glcorearb.h:409
GLdouble t
GLfloat v0
Definition: glcorearb.h:816
UT_BezierRootFinderT< fpreal > UT_BezierRootFinderR
GLenum func
Definition: glcorearb.h:783
GLfloat GLfloat v1
Definition: glcorearb.h:817
GLuint GLfloat * val
Definition: glcorearb.h:1608
UT_BezierRootFinderT< fpreal32 > UT_BezierRootFinderF
GLboolean r
Definition: glcorearb.h:1222
UT_BezierRootFinderT< float > UT_BezierRootFinder
Definition: format.h:895