Debian Codegraph @

third-party/boost-math/include/boost/math/interpolators/detail/bezier_polynomial_detail.hpp

raw
1 // Copyright Nick Thompson, 2021
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt
5 // or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 #ifndef BOOST_MATH_INTERPOLATORS_BEZIER_POLYNOMIAL_DETAIL_HPP
8 #define BOOST_MATH_INTERPOLATORS_BEZIER_POLYNOMIAL_DETAIL_HPP
9
10 #include <stdexcept>
11 #include <iostream>
12 #include <string>
13 #include <limits>
14
15 namespace boost::math::interpolators::detail {
16
17
18 template <class RandomAccessContainer>
19 static inline RandomAccessContainer& get_bezier_storage()
20 {
21 static thread_local RandomAccessContainer the_storage;
22 return the_storage;
23 }
24
25
26 template <class RandomAccessContainer>
27 class bezier_polynomial_imp
28 {
29 public:
30 using Point = typename RandomAccessContainer::value_type;
31 using Real = typename Point::value_type;
32 using Z = typename RandomAccessContainer::size_type;
33
34 bezier_polynomial_imp(RandomAccessContainer && control_points)
35 {
36 using std::to_string;
37 if (control_points.size() < 2) {
38 std::string err = std::string(__FILE__) + ":" + to_string(__LINE__)
39 + " At least two points are required to form a Bezier curve. Only " + to_string(control_points.size()) + " points have been provided.";
40 throw std::logic_error(err);
41 }
42 Z dimension = control_points[0].size();
43 for (Z i = 0; i < control_points.size(); ++i) {
44 if (control_points[i].size() != dimension) {
45 std::string err = std::string(__FILE__) + ":" + to_string(__LINE__)
46 + " All points passed to the Bezier polynomial must have the same dimension.";
47 throw std::logic_error(err);
48 }
49 }
50 control_points_ = std::move(control_points);
51 auto & storage = get_bezier_storage<RandomAccessContainer>();
52 if (storage.size() < control_points_.size() -1) {
53 storage.resize(control_points_.size() -1);
54 }
55 }
56
57 inline Point operator()(Real t) const
58 {
59 if (t < 0 || t > 1) {
60 std::cerr << __FILE__ << ":" << __LINE__ << ":" << __func__ << "\n";
61 std::cerr << "Querying the Bezier curve interpolator at t = " << t << " is not allowed; t in [0,1] is required.\n";
62 Point p;
63 for (Z i = 0; i < p.size(); ++i) {
64 p[i] = std::numeric_limits<Real>::quiet_NaN();
65 }
66 return p;
67 }
68
69 auto & scratch_space = get_bezier_storage<RandomAccessContainer>();
70 for (Z i = 0; i < control_points_.size() - 1; ++i) {
71 for (Z j = 0; j < control_points_[0].size(); ++j) {
72 scratch_space[i][j] = (1-t)*control_points_[i][j] + t*control_points_[i+1][j];
73 }
74 }
75
76 decasteljau_recursion(scratch_space, control_points_.size() - 1, t);
77 return scratch_space[0];
78 }
79
80 Point prime(Real t) {
81 auto & scratch_space = get_bezier_storage<RandomAccessContainer>();
82 for (Z i = 0; i < control_points_.size() - 1; ++i) {
83 for (Z j = 0; j < control_points_[0].size(); ++j) {
84 scratch_space[i][j] = control_points_[i+1][j] - control_points_[i][j];
85 }
86 }
87 decasteljau_recursion(scratch_space, control_points_.size() - 1, t);
88 for (Z j = 0; j < control_points_[0].size(); ++j) {
89 scratch_space[0][j] *= (control_points_.size()-1);
90 }
91 return scratch_space[0];
92 }
93
94
95 void edit_control_point(Point const & p, Z index)
96 {
97 if (index >= control_points_.size()) {
98 std::cerr << __FILE__ << ":" << __LINE__ << ":" << __func__ << "\n";
99 std::cerr << "Attempting to edit a control point outside the bounds of the container; requested edit of index " << index << ", but there are only " << control_points_.size() << " control points.\n";
100 return;
101 }
102 control_points_[index] = p;
103 }
104
105 RandomAccessContainer const & control_points() const {
106 return control_points_;
107 }
108
109 // See "Bezier and B-spline techniques", section 2.7:
110 // I cannot figure out why this doesn't work.
111 /*RandomAccessContainer indefinite_integral() const {
112 using std::fma;
113 // control_points_.size() == n + 1
114 RandomAccessContainer c(control_points_.size() + 1);
115 // This is the constant of integration, chosen arbitrarily to be zero:
116 for (Z j = 0; j < control_points_[0].size(); ++j) {
117 c[0][j] = Real(0);
118 }
119
120 // Make the reciprocal approximation to unroll the iteration into a pile of fma's:
121 Real rnp1 = Real(1)/control_points_.size();
122 for (Z i = 1; i < c.size(); ++i) {
123 for (Z j = 0; j < control_points_[0].size(); ++j) {
124 //c[i][j] = c[i-1][j] + control_points_[i-1][j]*rnp1;
125 c[i][j] = fma(rnp1, control_points_[i-1][j], c[i-1][j]);
126 }
127 }
128 return c;
129 }*/
130
131 friend std::ostream& operator<<(std::ostream& out, bezier_polynomial_imp<RandomAccessContainer> const & bp) {
132 out << "{";
133 for (Z i = 0; i < bp.control_points_.size() - 1; ++i) {
134 out << "(";
135 for (Z j = 0; j < bp.control_points_[0].size() - 1; ++j) {
136 out << bp.control_points_[i][j] << ", ";
137 }
138 out << bp.control_points_[i][bp.control_points_[0].size() - 1] << "), ";
139 }
140 out << "(";
141 for (Z j = 0; j < bp.control_points_[0].size() - 1; ++j) {
142 out << bp.control_points_.back()[j] << ", ";
143 }
144 out << bp.control_points_.back()[bp.control_points_[0].size() - 1] << ")}";
145 return out;
146 }
147
148 private:
149
150 void decasteljau_recursion(RandomAccessContainer & points, Z n, Real t) const {
151 if (n <= 1) {
152 return;
153 }
154 for (Z i = 0; i < n - 1; ++i) {
155 for (Z j = 0; j < points[0].size(); ++j) {
156 points[i][j] = (1-t)*points[i][j] + t*points[i+1][j];
157 }
158 }
159 decasteljau_recursion(points, n - 1, t);
160 }
161
162 RandomAccessContainer control_points_;
163 };
164
165
166 }
167 #endif