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

source code of qtbase/src/gui/painting/qbezier.cpp