1 /*
2 * Copyright (c) 2020 Dmitry Kazakov <dimula73@gmail.com>
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18
19 #ifndef KISBEZIERUTILS_H
20 #define KISBEZIERUTILS_H
21
22 #include "kritaglobal_export.h"
23
24 #include <kis_algebra_2d.h>
25
26
27 namespace KisBezierUtils
28 {
29 using KisAlgebra2D::lerp;
30
31
32
33
bezierCurveDeriv(const QPointF p0,const QPointF p1,const QPointF p2,const QPointF p3,qreal t)34 inline QPointF bezierCurveDeriv(const QPointF p0,
35 const QPointF p1,
36 const QPointF p2,
37 const QPointF p3,
38 qreal t)
39 {
40 const qreal t_2 = pow2(t);
41 const qreal t_inv = 1.0 - t;
42 const qreal t_inv_2 = pow2(t_inv);
43
44 return
45 3 * t_inv_2 * (p1 - p0) +
46 6 * t_inv * t * (p2 - p1) +
47 3 * t_2 * (p3 - p2);
48 }
49
bezierCurveDeriv2(const QPointF p0,const QPointF p1,const QPointF p2,const QPointF p3,qreal t)50 inline QPointF bezierCurveDeriv2(const QPointF p0,
51 const QPointF p1,
52 const QPointF p2,
53 const QPointF p3,
54 qreal t)
55 {
56 const qreal t_inv = 1.0 - t;
57
58 return
59 6 * t_inv * (p2 - 2 * p1 + p0) +
60 6 * t * (p3 - 2 * p2 + p1);
61 }
62
63
deCasteljau(const QPointF & q0,const QPointF & q1,const QPointF & q2,const QPointF & q3,qreal t,QPointF * p0,QPointF * p1,QPointF * p2,QPointF * p3,QPointF * p4)64 inline void deCasteljau(const QPointF &q0,
65 const QPointF &q1,
66 const QPointF &q2,
67 const QPointF &q3,
68 qreal t,
69 QPointF *p0,
70 QPointF *p1,
71 QPointF *p2,
72 QPointF *p3,
73 QPointF *p4)
74 {
75 QPointF q[4];
76
77 q[0] = q0;
78 q[1] = q1;
79 q[2] = q2;
80 q[3] = q3;
81
82 // points of the new segment after the split point
83 QPointF p[3];
84
85 // the De Casteljau algorithm
86 for (unsigned short j = 1; j <= 3; ++j) {
87 for (unsigned short i = 0; i <= 3 - j; ++i) {
88 q[i] = (1.0 - t) * q[i] + t * q[i + 1];
89 }
90 p[j - 1] = q[0];
91 }
92
93 *p0 = p[0];
94 *p1 = p[1];
95 *p2 = p[2];
96 *p3 = q[1];
97 *p4 = q[2];
98 }
99
bezierCurve(const QPointF p0,const QPointF p1,const QPointF p2,const QPointF p3,qreal t)100 inline QPointF bezierCurve(const QPointF p0,
101 const QPointF p1,
102 const QPointF p2,
103 const QPointF p3,
104 qreal t)
105 {
106 #if 0
107 const qreal t_2 = pow2(t);
108 const qreal t_3 = t_2 * t;
109 const qreal t_inv = 1.0 - t;
110 const qreal t_inv_2 = pow2(t_inv);
111 const qreal t_inv_3 = t_inv_2 * t_inv;
112
113 return
114 t_inv_3 * p0 +
115 3 * t_inv_2 * t * p1 +
116 3 * t_inv * t_2 * p2 +
117 t_3 * p3;
118 #else
119 QPointF q0, q1, q2, q3, q4;
120 deCasteljau(p0, p1, p2, p3, t, &q0, &q1, &q2, &q3, &q4);
121 return q2;
122 #endif
123 }
124
bezierCurve(const QList<QPointF> & points,qreal t)125 inline QPointF bezierCurve(const QList<QPointF> &points,
126 qreal t)
127 {
128 QPointF result;
129
130 if (points.size() == 2) {
131 result = lerp(points.first(), points.last(), t);
132 } else if (points.size() == 3) {
133 result = bezierCurve(points[0], points[1], points[1], points[2], t);
134 } else if (points.size() == 4) {
135 result = bezierCurve(points[0], points[1], points[2], points[3], t);
136 } else {
137 KIS_SAFE_ASSERT_RECOVER_NOOP(0 && "Unsupported number of bezier control points");
138 }
139
140 return result;
141 }
142
143 inline bool isLinearSegmentByDerivatives(const QPointF &p0, const QPointF &d0,
144 const QPointF &p1, const QPointF &d1,
145 const qreal eps = 1e-4)
146 {
147 const QPointF diff = p1 - p0;
148 const qreal dist = KisAlgebra2D::norm(diff);
149
150 const qreal normCoeff = 1.0 / 3.0 / dist;
151
152 const qreal offset1 =
153 normCoeff * qAbs(KisAlgebra2D::crossProduct(diff, d0));
154 if (offset1 > eps) return false;
155
156 const qreal offset2 =
157 normCoeff * qAbs(KisAlgebra2D::crossProduct(diff, d1));
158 if (offset2 > eps) return false;
159
160 return true;
161 }
162
163 inline bool isLinearSegmentByControlPoints(const QPointF &p0, const QPointF &p1,
164 const QPointF &p2, const QPointF &p3,
165 const qreal eps = 1e-4)
166 {
167 return isLinearSegmentByDerivatives(p0, (p1 - p0) * 3.0, p3, (p3 - p2) * 3.0, eps);
168 }
169
bezierDegree(const QPointF p0,const QPointF p1,const QPointF p2,const QPointF p3)170 inline int bezierDegree(const QPointF p0,
171 const QPointF p1,
172 const QPointF p2,
173 const QPointF p3)
174 {
175 const qreal eps = 1e-4;
176
177 int degree = 3;
178
179 if (isLinearSegmentByControlPoints(p0, p1, p2, p3, eps)) {
180 degree = 1;
181 } else if (KisAlgebra2D::fuzzyPointCompare(p1, p2, eps)) {
182 degree = 2;
183 }
184
185 return degree;
186 }
187
188 KRITAGLOBAL_EXPORT
189 QVector<qreal> linearizeCurve(const QPointF p0,
190 const QPointF p1,
191 const QPointF p2,
192 const QPointF p3,
193 const qreal eps);
194 KRITAGLOBAL_EXPORT
195 QVector<qreal> mergeLinearizationSteps(const QVector<qreal> &a, const QVector<qreal> &b);
196
197 KRITAGLOBAL_EXPORT
198 qreal nearestPoint(const QList<QPointF> controlPoints, const QPointF &point, qreal *resultDistance = 0, QPointF *resultPoint = 0);
199
200 KRITAGLOBAL_EXPORT
201 int controlPolygonZeros(const QList<QPointF> &controlPoints);
202
203 /**
204 * @brief calculates local (u,v) coordinates of the patch corrresponding to \p globalPoint
205 *
206 * The function uses Krita's own level-based patch interpolation algorithm
207 *
208 * @param points control points as the layouted in KisBezierPatch
209 * @param globalPoint point in global coordinates
210 * @return point in local coordinates
211 */
212 KRITAGLOBAL_EXPORT
213 QPointF calculateLocalPos(const std::array<QPointF, 12> &points,
214 const QPointF &globalPoint);
215
216 /**
217 * @brief calculates global coordinate corresponding to the patch coordinate (u, v)
218 *
219 * The function uses Krita's own level-based patch interpolation algorithm
220 *
221 * @param points control points as the layouted in KisBezierPatch
222 * @param localPoint point in local coordinates
223 * @return point in global coordinates
224 */
225 KRITAGLOBAL_EXPORT
226 QPointF calculateGlobalPos(const std::array<QPointF, 12> &points, const QPointF &localPoint);
227
228 /**
229 * @brief calculates local (u,v) coordinates of the patch corrresponding to \p globalPoint
230 *
231 * The function uses SVG2 toon patches algorithm
232 *
233 * @param points control points as the layouted in KisBezierPatch
234 * @param globalPoint point in global coordinates
235 * @return point in local coordinates
236 */
237 KRITAGLOBAL_EXPORT
238 QPointF calculateLocalPosSVG2(const std::array<QPointF, 12> &points,
239 const QPointF &globalPoint);
240
241 /**
242 * @brief calculates global coordinate corresponding to the patch coordinate (u, v)
243 *
244 * The function uses SVG2 toon patches algorithm
245 *
246 * @param points control points as the layouted in KisBezierPatch
247 * @param localPoint point in local coordinates
248 * @return point in global coordinates
249 */
250 KRITAGLOBAL_EXPORT
251 QPointF calculateGlobalPosSVG2(const std::array<QPointF, 12> &points, const QPointF &localPoint);
252
253
254 /**
255 * @brief Interpolates quadric curve passing through given points
256 *
257 * Interpolates quadric curve passing through \p p0, \p pt and \p p2
258 * with ensuring that \p pt placed at position \p t
259 * @return interpolated value for control point p1
260 */
261 KRITAGLOBAL_EXPORT
262 QPointF interpolateQuadric(const QPointF &p0, const QPointF &p2, const QPointF &pt, qreal t);
263
264 /**
265 * @brief moves point \p t of the curve by offset \p offset
266 * @return proposed offsets for points p1 and p2 of the curve
267 */
268 KRITAGLOBAL_EXPORT
269 std::pair<QPointF, QPointF> offsetSegment(qreal t, const QPointF &offset);
270
271 KRITAGLOBAL_EXPORT
272 qreal curveLength(const QPointF p0,
273 const QPointF p1,
274 const QPointF p2,
275 const QPointF p3,
276 const qreal error);
277
278 KRITAGLOBAL_EXPORT
279 qreal curveLengthAtPoint(const QPointF p0,
280 const QPointF p1,
281 const QPointF p2,
282 const QPointF p3,
283 qreal t,
284 const qreal error);
285
286 KRITAGLOBAL_EXPORT
287 qreal curveParamByProportion(const QPointF p0,
288 const QPointF p1,
289 const QPointF p2,
290 const QPointF p3,
291 qreal proportion,
292 const qreal error);
293
294 KRITAGLOBAL_EXPORT
295 qreal curveProportionByParam(const QPointF p0, const QPointF p1, const QPointF p2, const QPointF p3, qreal t, const qreal error);
296
297 /**
298 * @brief Adjusts position for the bezier control points
299 * after removing a node.
300 *
301 * First source curve P: \p p0, \p p1, \p p2, \p p3
302 * Second source curve Q: \p p3, \p q1, \p q2, \p q3
303 *
304 * Node to remove: \p p3 and its control points \p p2 and \p q1
305 *
306 * @return a pair of new positions for \p p1 and \p q2
307 */
308 KRITAGLOBAL_EXPORT
309 std::pair<QPointF, QPointF> removeBezierNode(const QPointF &p0,
310 const QPointF &p1,
311 const QPointF &p2,
312 const QPointF &p3,
313 const QPointF &q1,
314 const QPointF &q2,
315 const QPointF &q3);
316
317 /**
318 * Find intersection points (their parameter values) between a cubic
319 * Bezier curve and a line.
320 *
321 * Curve: \p p0, \p p1, \p p2, \p p3
322 * Line: \p line
323 *
324 * For cubic Bezier curves there can be at most three intersection points.
325 */
326 KRITAGLOBAL_EXPORT
327 QVector<qreal> intersectWithLine(const QPointF &p0,
328 const QPointF &p1,
329 const QPointF &p2,
330 const QPointF &p3,
331 const QLineF &line,
332 qreal eps);
333
334 /**
335 * Find new nearest intersection point between a cubic Bezier curve and a line.
336 * The resulting point will be the nearest to \p nearestAnchor.
337 */
338 KRITAGLOBAL_EXPORT
339 boost::optional<qreal> intersectWithLineNearest(const QPointF &p0,
340 const QPointF &p1,
341 const QPointF &p2,
342 const QPointF &p3,
343 const QLineF &line,
344 const QPointF &nearestAnchor,
345 qreal eps);
346
347 }
348
349 #endif // KISBEZIERUTILS_H
350