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

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