1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qbezier_p.h"
41#include <qdebug.h>
42#include <qline.h>
43#include <qpolygon.h>
44#include <qvector.h>
45#include <qlist.h>
46#include <qmath.h>
47
48#include <private/qnumeric_p.h>
49
50QT_BEGIN_NAMESPACE
51
52//#define QDEBUG_BEZIER
53
54/*!
55 \internal
56*/
57QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2,
58 const QPointF &p3, const QPointF &p4)
59{
60 QBezier b;
61 b.x1 = p1.x();
62 b.y1 = p1.y();
63 b.x2 = p2.x();
64 b.y2 = p2.y();
65 b.x3 = p3.x();
66 b.y3 = p3.y();
67 b.x4 = p4.x();
68 b.y4 = p4.y();
69 return b;
70}
71
72/*!
73 \internal
74*/
75QPolygonF QBezier::toPolygon(qreal bezier_flattening_threshold) const
76{
77 // flattening is done by splitting the bezier until we can replace the segment by a straight
78 // line. We split further until the control points are close enough to the line connecting the
79 // boundary points.
80 //
81 // the Distance of a point p from a line given by the points (a,b) is given by:
82 //
83 // d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length
84 //
85 // We can stop splitting if both control points are close enough to the line.
86 // To make the algorithm faster we use the manhattan length of the line.
87
88 QPolygonF polygon;
89 polygon.append(QPointF(x1, y1));
90 addToPolygon(&polygon, bezier_flattening_threshold);
91 return polygon;
92}
93
94QBezier QBezier::mapBy(const QTransform &transform) const
95{
96 return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4()));
97}
98
99QBezier QBezier::getSubRange(qreal t0, qreal t1) const
100{
101 QBezier result;
102 QBezier temp;
103
104 // cut at t1
105 if (qFuzzyIsNull(t1 - qreal(1.))) {
106 result = *this;
107 } else {
108 temp = *this;
109 temp.parameterSplitLeft(t1, &result);
110 }
111
112 // cut at t0
113 if (!qFuzzyIsNull(t0))
114 result.parameterSplitLeft(t0 / t1, &temp);
115
116 return result;
117}
118
119void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold) const
120{
121 QBezier beziers[10];
122 int levels[10];
123 beziers[0] = *this;
124 levels[0] = 9;
125 QBezier *b = beziers;
126 int *lvl = levels;
127
128 while (b >= beziers) {
129 // check if we can pop the top bezier curve from the stack
130 qreal y4y1 = b->y4 - b->y1;
131 qreal x4x1 = b->x4 - b->x1;
132 qreal l = qAbs(x4x1) + qAbs(y4y1);
133 qreal d;
134 if (l > 1.) {
135 d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
136 + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
137 } else {
138 d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
139 qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
140 l = 1.;
141 }
142 if (d < bezier_flattening_threshold*l || *lvl == 0) {
143 // good enough, we pop it off and add the endpoint
144 polygon->append(QPointF(b->x4, b->y4));
145 --b;
146 --lvl;
147 } else {
148 // split, second half of the polygon goes lower into the stack
149 b->split(b+1, b);
150 lvl[1] = --lvl[0];
151 ++b;
152 ++lvl;
153 }
154 }
155}
156
157void QBezier::addToPolygon(QDataBuffer<QPointF> &polygon, qreal bezier_flattening_threshold) const
158{
159 QBezier beziers[10];
160 int levels[10];
161 beziers[0] = *this;
162 levels[0] = 9;
163 QBezier *b = beziers;
164 int *lvl = levels;
165
166 while (b >= beziers) {
167 // check if we can pop the top bezier curve from the stack
168 qreal y4y1 = b->y4 - b->y1;
169 qreal x4x1 = b->x4 - b->x1;
170 qreal l = qAbs(x4x1) + qAbs(y4y1);
171 qreal d;
172 if (l > 1.) {
173 d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
174 + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
175 } else {
176 d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
177 qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
178 l = 1.;
179 }
180 if (d < bezier_flattening_threshold*l || *lvl == 0) {
181 // good enough, we pop it off and add the endpoint
182 polygon.add(QPointF(b->x4, b->y4));
183 --b;
184 --lvl;
185 } else {
186 // split, second half of the polygon goes lower into the stack
187 b->split(b+1, b);
188 lvl[1] = --lvl[0];
189 ++b;
190 ++lvl;
191 }
192 }
193}
194
195QRectF QBezier::bounds() const
196{
197 qreal xmin = x1;
198 qreal xmax = x1;
199 if (x2 < xmin)
200 xmin = x2;
201 else if (x2 > xmax)
202 xmax = x2;
203 if (x3 < xmin)
204 xmin = x3;
205 else if (x3 > xmax)
206 xmax = x3;
207 if (x4 < xmin)
208 xmin = x4;
209 else if (x4 > xmax)
210 xmax = x4;
211
212 qreal ymin = y1;
213 qreal ymax = y1;
214 if (y2 < ymin)
215 ymin = y2;
216 else if (y2 > ymax)
217 ymax = y2;
218 if (y3 < ymin)
219 ymin = y3;
220 else if (y3 > ymax)
221 ymax = y3;
222 if (y4 < ymin)
223 ymin = y4;
224 else if (y4 > ymax)
225 ymax = y4;
226 return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
227}
228
229
230enum ShiftResult {
231 Ok,
232 Discard,
233 Split,
234 Circle
235};
236
237static ShiftResult good_offset(const QBezier *b1, const QBezier *b2, qreal offset, qreal threshold)
238{
239 const qreal o2 = offset*offset;
240 const qreal max_dist_line = threshold*offset*offset;
241 const qreal max_dist_normal = threshold*offset;
242 const qreal spacing = qreal(0.25);
243 for (qreal i = spacing; i < qreal(0.99); i += spacing) {
244 QPointF p1 = b1->pointAt(i);
245 QPointF p2 = b2->pointAt(i);
246 qreal d = (p1.x() - p2.x())*(p1.x() - p2.x()) + (p1.y() - p2.y())*(p1.y() - p2.y());
247 if (qAbs(d - o2) > max_dist_line)
248 return Split;
249
250 QPointF normalPoint = b1->normalVector(i);
251 qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
252 if (l != qreal(0.0)) {
253 d = qAbs( normalPoint.x()*(p1.y() - p2.y()) - normalPoint.y()*(p1.x() - p2.x()) ) / l;
254 if (d > max_dist_normal)
255 return Split;
256 }
257 }
258 return Ok;
259}
260
261static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)
262{
263 int map[4];
264 bool p1_p2_equal = qFuzzyCompare(orig->x1, orig->x2) && qFuzzyCompare(orig->y1, orig->y2);
265 bool p2_p3_equal = qFuzzyCompare(orig->x2, orig->x3) && qFuzzyCompare(orig->y2, orig->y3);
266 bool p3_p4_equal = qFuzzyCompare(orig->x3, orig->x4) && qFuzzyCompare(orig->y3, orig->y4);
267
268 QPointF points[4];
269 int np = 0;
270 points[np] = QPointF(orig->x1, orig->y1);
271 map[0] = 0;
272 ++np;
273 if (!p1_p2_equal) {
274 points[np] = QPointF(orig->x2, orig->y2);
275 ++np;
276 }
277 map[1] = np - 1;
278 if (!p2_p3_equal) {
279 points[np] = QPointF(orig->x3, orig->y3);
280 ++np;
281 }
282 map[2] = np - 1;
283 if (!p3_p4_equal) {
284 points[np] = QPointF(orig->x4, orig->y4);
285 ++np;
286 }
287 map[3] = np - 1;
288 if (np == 1)
289 return Discard;
290
291 QRectF b = orig->bounds();
292 if (np == 4 && b.width() < .1*offset && b.height() < .1*offset) {
293 qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
294 (orig->y1 - orig->y2)*(orig->y1 - orig->y2) *
295 (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
296 (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
297 qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
298 (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
299 if (dot < 0 && dot*dot < 0.8*l)
300 // the points are close and reverse dirction. Approximate the whole
301 // thing by a semi circle
302 return Circle;
303 }
304
305 QPointF points_shifted[4];
306
307 QLineF prev = QLineF(QPointF(), points[1] - points[0]);
308 QPointF prev_normal = prev.normalVector().unitVector().p2();
309
310 points_shifted[0] = points[0] + offset * prev_normal;
311
312 for (int i = 1; i < np - 1; ++i) {
313 QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);
314 QPointF next_normal = next.normalVector().unitVector().p2();
315
316 QPointF normal_sum = prev_normal + next_normal;
317
318 qreal r = qreal(1.0) + prev_normal.x() * next_normal.x()
319 + prev_normal.y() * next_normal.y();
320
321 if (qFuzzyIsNull(r)) {
322 points_shifted[i] = points[i] + offset * prev_normal;
323 } else {
324 qreal k = offset / r;
325 points_shifted[i] = points[i] + k * normal_sum;
326 }
327
328 prev_normal = next_normal;
329 }
330
331 points_shifted[np - 1] = points[np - 1] + offset * prev_normal;
332
333 *shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],
334 points_shifted[map[2]], points_shifted[map[3]]);
335
336 if (np > 2)
337 return good_offset(orig, shifted, offset, threshold);
338 return Ok;
339}
340
341// This value is used to determine the length of control point vectors
342// when approximating arc segments as curves. The factor is multiplied
343// with the radius of the circle.
344#define KAPPA qreal(0.5522847498)
345
346
347static bool addCircle(const QBezier *b, qreal offset, QBezier *o)
348{
349 QPointF normals[3];
350
351 normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);
352 qreal dist = qSqrt(normals[0].x()*normals[0].x() + normals[0].y()*normals[0].y());
353 if (qFuzzyIsNull(dist))
354 return false;
355 normals[0] /= dist;
356 normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);
357 dist = qSqrt(normals[2].x()*normals[2].x() + normals[2].y()*normals[2].y());
358 if (qFuzzyIsNull(dist))
359 return false;
360 normals[2] /= dist;
361
362 normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);
363 normals[1] /= -1*qSqrt(normals[1].x()*normals[1].x() + normals[1].y()*normals[1].y());
364
365 qreal angles[2];
366 qreal sign = 1.;
367 for (int i = 0; i < 2; ++i) {
368 qreal cos_a = normals[i].x()*normals[i+1].x() + normals[i].y()*normals[i+1].y();
369 if (cos_a > 1.)
370 cos_a = 1.;
371 if (cos_a < -1.)
372 cos_a = -1;
373 angles[i] = qAcos(cos_a) * qreal(M_1_PI);
374 }
375
376 if (angles[0] + angles[1] > 1.) {
377 // more than 180 degrees
378 normals[1] = -normals[1];
379 angles[0] = 1. - angles[0];
380 angles[1] = 1. - angles[1];
381 sign = -1.;
382
383 }
384
385 QPointF circle[3];
386 circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;
387 circle[1] = QPointF(qreal(0.5)*(b->x1 + b->x4), qreal(0.5)*(b->y1 + b->y4)) + normals[1]*offset;
388 circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;
389
390 for (int i = 0; i < 2; ++i) {
391 qreal kappa = qreal(2.0) * KAPPA * sign * offset * angles[i];
392
393 o->x1 = circle[i].x();
394 o->y1 = circle[i].y();
395 o->x2 = circle[i].x() - normals[i].y()*kappa;
396 o->y2 = circle[i].y() + normals[i].x()*kappa;
397 o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;
398 o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;
399 o->x4 = circle[i+1].x();
400 o->y4 = circle[i+1].y();
401
402 ++o;
403 }
404 return true;
405}
406
407int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const
408{
409 Q_ASSERT(curveSegments);
410 Q_ASSERT(maxSegments > 0);
411
412 if (qFuzzyCompare(x1, x2) && qFuzzyCompare(x1, x3) && qFuzzyCompare(x1, x4) &&
413 qFuzzyCompare(y1, y2) && qFuzzyCompare(y1, y3) && qFuzzyCompare(y1, y4))
414 return 0;
415
416 --maxSegments;
417 QBezier beziers[10];
418redo:
419 beziers[0] = *this;
420 QBezier *b = beziers;
421 QBezier *o = curveSegments;
422
423 while (b >= beziers) {
424 int stack_segments = b - beziers + 1;
425 if ((stack_segments == 10) || (o - curveSegments == maxSegments - stack_segments)) {
426 threshold *= qreal(1.5);
427 if (threshold > qreal(2.0))
428 goto give_up;
429 goto redo;
430 }
431 ShiftResult res = shift(b, o, offset, threshold);
432 if (res == Discard) {
433 --b;
434 } else if (res == Ok) {
435 ++o;
436 --b;
437 } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
438 // add semi circle
439 if (addCircle(b, offset, o))
440 o += 2;
441 --b;
442 } else {
443 b->split(b+1, b);
444 ++b;
445 }
446 }
447
448give_up:
449 while (b >= beziers) {
450 ShiftResult res = shift(b, o, offset, threshold);
451
452 // if res isn't Ok or Split then *o is undefined
453 if (res == Ok || res == Split)
454 ++o;
455
456 --b;
457 }
458
459 Q_ASSERT(o - curveSegments <= maxSegments);
460 return o - curveSegments;
461}
462
463#ifdef QDEBUG_BEZIER
464static QDebug operator<<(QDebug dbg, const QBezier &bz)
465{
466 dbg << '[' << bz.x1<< ", " << bz.y1 << "], "
467 << '[' << bz.x2 <<", " << bz.y2 << "], "
468 << '[' << bz.x3 <<", " << bz.y3 << "], "
469 << '[' << bz.x4 <<", " << bz.y4 << ']';
470 return dbg;
471}
472#endif
473
474qreal QBezier::length(qreal error) const
475{
476 qreal length = qreal(0.0);
477
478 addIfClose(&length, error);
479
480 return length;
481}
482
483void QBezier::addIfClose(qreal *length, qreal error) const
484{
485 QBezier left, right; /* bez poly splits */
486
487 qreal len = qreal(0.0); /* arc length */
488 qreal chord; /* chord length */
489
490 len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();
491 len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();
492 len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();
493
494 chord = QLineF(QPointF(x1, y1),QPointF(x4, y4)).length();
495
496 if((len-chord) > error) {
497 split(&left, &right); /* split in two */
498 left.addIfClose(length, error); /* try left side */
499 right.addIfClose(length, error); /* try right side */
500 return;
501 }
502
503 *length = *length + len;
504
505 return;
506}
507
508qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const
509{
510 qreal py0 = pointAt(t0).y();
511 qreal py1 = pointAt(t1).y();
512
513 if (py0 > py1) {
514 qSwap(py0, py1);
515 qSwap(t0, t1);
516 }
517
518 Q_ASSERT(py0 <= py1);
519
520 if (py0 >= y)
521 return t0;
522 else if (py1 <= y)
523 return t1;
524
525 Q_ASSERT(py0 < y && y < py1);
526
527 qreal lt = t0;
528 qreal dt;
529 do {
530 qreal t = qreal(0.5) * (t0 + t1);
531
532 qreal a, b, c, d;
533 QBezier::coefficients(t, a, b, c, d);
534 qreal yt = a * y1 + b * y2 + c * y3 + d * y4;
535
536 if (yt < y) {
537 t0 = t;
538 py0 = yt;
539 } else {
540 t1 = t;
541 py1 = yt;
542 }
543 dt = lt - t;
544 lt = t;
545 } while (qAbs(dt) > qreal(1e-7));
546
547 return t0;
548}
549
550int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const
551{
552 // y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4
553 // y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)
554 // y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))
555
556 const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;
557 const qreal b = 2 * y1 - 4 * y2 + 2 * y3;
558 const qreal c = -y1 + y2;
559
560 if (qFuzzyIsNull(a)) {
561 if (qFuzzyIsNull(b))
562 return 0;
563
564 t0 = -c / b;
565 return t0 > 0 && t0 < 1;
566 }
567
568 qreal reciprocal = b * b - 4 * a * c;
569
570 if (qFuzzyIsNull(reciprocal)) {
571 t0 = -b / (2 * a);
572 return t0 > 0 && t0 < 1;
573 } else if (reciprocal > 0) {
574 qreal temp = qSqrt(reciprocal);
575
576 t0 = (-b - temp)/(2*a);
577 t1 = (-b + temp)/(2*a);
578
579 if (t1 < t0)
580 qSwap(t0, t1);
581
582 int count = 0;
583 qreal t[2] = { 0, 1 };
584
585 if (t0 > 0 && t0 < 1)
586 t[count++] = t0;
587 if (t1 > 0 && t1 < 1)
588 t[count++] = t1;
589
590 t0 = t[0];
591 t1 = t[1];
592
593 return count;
594 }
595
596 return 0;
597}
598
599qreal QBezier::tAtLength(qreal l) const
600{
601 qreal len = length();
602 qreal t = qreal(1.0);
603 const qreal error = qreal(0.01);
604 if (l > len || qFuzzyCompare(l, len))
605 return t;
606
607 t *= qreal(0.5);
608 //int iters = 0;
609 //qDebug()<<"LEN is "<<l<<len;
610 qreal lastBigger = qreal(1.0);
611 while (1) {
612 //qDebug()<<"\tt is "<<t;
613 QBezier right = *this;
614 QBezier left;
615 right.parameterSplitLeft(t, &left);
616 qreal lLen = left.length();
617 if (qAbs(lLen - l) < error)
618 break;
619
620 if (lLen < l) {
621 t += (lastBigger - t) * qreal(0.5);
622 } else {
623 lastBigger = t;
624 t -= t * qreal(0.5);
625 }
626 //++iters;
627 }
628 //qDebug()<<"number of iters is "<<iters;
629 return t;
630}
631
632QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const
633{
634 if (t0 == 0 && t1 == 1)
635 return *this;
636
637 QBezier bezier = *this;
638
639 QBezier result;
640 bezier.parameterSplitLeft(t0, &result);
641 qreal trueT = (t1-t0)/(1-t0);
642 bezier.parameterSplitLeft(trueT, &result);
643
644 return result;
645}
646
647QT_END_NAMESPACE
648