1/**
2 * Copyright (c) 2006-2023 LOVE Development Team
3 *
4 * This software is provided 'as-is', without any express or implied
5 * warranty. In no event will the authors be held liable for any damages
6 * arising from the use of this software.
7 *
8 * Permission is granted to anyone to use this software for any purpose,
9 * including commercial applications, and to alter it and redistribute it
10 * freely, subject to the following restrictions:
11 *
12 * 1. The origin of this software must not be misrepresented; you must not
13 * claim that you wrote the original software. If you use this software
14 * in a product, an acknowledgment in the product documentation would be
15 * appreciated but is not required.
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 * 3. This notice may not be removed or altered from any source distribution.
19 **/
20
21// LOVE
22#include "BezierCurve.h"
23#include "common/Exception.h"
24
25#include <cmath>
26#include <algorithm>
27
28using namespace std;
29
30namespace
31{
32
33/**
34 * Subdivide Bezier polygon.
35 **/
36void subdivide(vector<love::Vector2> &points, int k)
37{
38 if (k <= 0)
39 return;
40
41 // subdivision using de casteljau - subdivided control polygons are
42 // on the 'edges' of the computation scheme, e.g:
43 //
44 // ------LEFT------->
45 // b00 b10 b20 b30
46 // b01 b11 b21 .---
47 // b02 b12 .---'
48 // b03 .---'RIGHT
49 // <--'
50 //
51 // the subdivided control polygon is:
52 // b00, b10, b20, b30, b21, b12, b03
53 vector<love::Vector2> left, right;
54 left.reserve(points.size());
55 right.reserve(points.size());
56
57 for (size_t step = 1; step < points.size(); ++step)
58 {
59 left.push_back(points[0]);
60 right.push_back(points[points.size() - step]);
61 for (size_t i = 0; i < points.size() - step; ++i)
62 points[i] = (points[i] + points[i+1]) * .5;
63 }
64 left.push_back(points[0]);
65 right.push_back(points[0]);
66
67 // recurse
68 subdivide(left, k-1);
69 subdivide(right, k-1);
70
71 // merge (right is in reversed order)
72 points.resize(left.size() + right.size() - 1);
73 for (size_t i = 0; i < left.size(); ++i)
74 points[i] = left[i];
75 for (size_t i = 1; i < right.size(); ++i)
76 points[i-1 + left.size()] = right[right.size() - i - 1];
77}
78
79}
80
81namespace love
82{
83namespace math
84{
85
86love::Type BezierCurve::type("BezierCurve", &Object::type);
87
88BezierCurve::BezierCurve(const vector<Vector2> &pts)
89 : controlPoints(pts)
90{
91}
92
93
94BezierCurve BezierCurve::getDerivative() const
95{
96 if (getDegree() < 1)
97 throw Exception("Cannot derive a curve of degree < 1.");
98 // actually we can, it just doesn't make any sense.
99
100 vector<Vector2> forward_differences(controlPoints.size()-1);
101 float degree = float(getDegree());
102 for (size_t i = 0; i < forward_differences.size(); ++i)
103 forward_differences[i] = (controlPoints[i+1] - controlPoints[i]) * degree;
104
105 return BezierCurve(forward_differences);
106}
107
108const Vector2 &BezierCurve::getControlPoint(int i) const
109{
110 if (controlPoints.size() == 0)
111 throw Exception("Curve contains no control points.");
112
113 while (i < 0)
114 i += controlPoints.size();
115
116 while ((size_t) i >= controlPoints.size())
117 i -= controlPoints.size();
118
119 return controlPoints[i];
120}
121
122void BezierCurve::setControlPoint(int i, const Vector2 &point)
123{
124 if (controlPoints.size() == 0)
125 throw Exception("Curve contains no control points.");
126
127 while (i < 0)
128 i += controlPoints.size();
129
130 while ((size_t) i >= controlPoints.size())
131 i -= controlPoints.size();
132
133 controlPoints[i] = point;
134}
135
136void BezierCurve::insertControlPoint(const Vector2 &point, int i)
137{
138 if (controlPoints.size() == 0)
139 i = 0;
140
141 while (i < 0)
142 i += controlPoints.size();
143
144 while ((size_t) i > controlPoints.size())
145 i -= controlPoints.size();
146
147 controlPoints.insert(controlPoints.begin() + i, point);
148}
149
150void BezierCurve::removeControlPoint(int i)
151{
152 if (controlPoints.size() == 0)
153 throw Exception("No control points to remove.");
154
155 while (i < 0)
156 i += controlPoints.size();
157
158 while ((size_t) i >= controlPoints.size())
159 i -= controlPoints.size();
160
161 controlPoints.erase(controlPoints.begin() + i);
162}
163
164void BezierCurve::translate(const Vector2 &t)
165{
166 for (size_t i = 0; i < controlPoints.size(); ++i)
167 controlPoints[i] += t;
168}
169
170void BezierCurve::rotate(double phi, const Vector2 &center)
171{
172 float c = cos(phi), s = sin(phi);
173 for (size_t i = 0; i < controlPoints.size(); ++i)
174 {
175 Vector2 v = controlPoints[i] - center;
176 controlPoints[i].x = c * v.x - s * v.y + center.x;
177 controlPoints[i].y = s * v.x + c * v.y + center.y;
178 }
179}
180
181void BezierCurve::scale(double s, const Vector2 &center)
182{
183 for (size_t i = 0; i < controlPoints.size(); ++i)
184 controlPoints[i] = (controlPoints[i] - center) * s + center;
185}
186
187Vector2 BezierCurve::evaluate(double t) const
188{
189 if (t < 0 || t > 1)
190 throw Exception("Invalid evaluation parameter: must be between 0 and 1");
191 if (controlPoints.size() < 2)
192 throw Exception("Invalid Bezier curve: Not enough control points.");
193
194 // de casteljau
195 vector<Vector2> points(controlPoints);
196 for (size_t step = 1; step < controlPoints.size(); ++step)
197 for (size_t i = 0; i < controlPoints.size() - step; ++i)
198 points[i] = points[i] * (1-t) + points[i+1] * t;
199
200 return points[0];
201}
202
203BezierCurve* BezierCurve::getSegment(double t1, double t2) const
204{
205 if (t1 < 0 || t2 > 1)
206 throw Exception("Invalid segment parameters: must be between 0 and 1");
207 if (t2 <= t1)
208 throw Exception("Invalid segment parameters: t1 must be smaller than t2");
209
210 // First, sudivide the curve at t2, then subdivide the "left"
211 // sub-curve at t1/t2. The "right" curve is the segment.
212 vector<Vector2> points(controlPoints);
213 vector<Vector2> left, right;
214 left.reserve(points.size());
215 right.reserve(points.size());
216
217 // first subdivision at t2 (take only the left curve)
218 for (size_t step = 1; step < points.size(); ++step)
219 {
220 left.push_back(points[0]);
221 for (size_t i = 0; i < points.size() - step; ++i)
222 points[i] += (points[i+1] - points[i]) * t2; // p_i <- (1-t2)*p_i + t2*p_{i+1}
223 }
224 left.push_back(points[0]);
225
226 // second subdivion at t1/t2 (take only the right curve)
227 double s = t1/t2;
228 for (size_t step = 1; step < left.size(); ++step)
229 {
230 right.push_back(left[left.size() - step]);
231 for (size_t i = 0; i < left.size() - step; ++i)
232 left[i] += (left[i+1] - left[i]) * s;
233 }
234 right.push_back(left[0]);
235
236 // control points for right curve were added in reversed order
237 std::reverse(right.begin(), right.end());
238 return new BezierCurve(right);
239}
240
241vector<Vector2> BezierCurve::render(int accuracy) const
242{
243 if (controlPoints.size() < 2)
244 throw Exception("Invalid Bezier curve: Not enough control points.");
245 vector<Vector2> vertices(controlPoints);
246 subdivide(vertices, accuracy);
247 return vertices;
248}
249
250vector<Vector2> BezierCurve::renderSegment(double start, double end, int accuracy) const
251{
252 if (controlPoints.size() < 2)
253 throw Exception("Invalid Bezier curve: Not enough control points.");
254 vector<Vector2> vertices(controlPoints);
255 subdivide(vertices, accuracy);
256 if (start == end)
257 {
258 vertices.clear();
259 }
260 else if (start < end)
261 {
262 size_t start_idx = size_t(start * vertices.size());
263 size_t end_idx = size_t(end * vertices.size() + 0.5);
264 return std::vector<Vector2>(vertices.begin() + start_idx, vertices.begin() + end_idx);
265 }
266 else if (end > start)
267 {
268 size_t start_idx = size_t(end * vertices.size() + 0.5);
269 size_t end_idx = size_t(start * vertices.size());
270 return std::vector<Vector2>(vertices.begin() + start_idx, vertices.begin() + end_idx);
271 }
272 return vertices;
273}
274
275} // namespace math
276} // namespace love
277