230         }

   231     }

   232 }

   233 

   234 void QBezier::addToPolygonMixed(QPolygonF *polygon) const

   235 {

   236     qreal ax = -x1 + 3*x2 - 3*x3 + x4;

   237     qreal ay = -y1 + 3*y2 - 3*y3 + y4;

   238     qreal bx = 3*x1 - 6*x2 + 3*x3;

   239     qreal by = 3*y1 - 6*y2 + 3*y3;

   240     qreal cx = -3*x1 + 3*x2;

   241     qreal cy = -3*y1 + 2*y2;

   242     qreal a = 6 * (ay * bx - ax * by);

   243     qreal b = 6 * (ay * cx - ax * cy);

   244     qreal c = 2 * (by * cx - bx * cy);

   245 

   246     if ((qFuzzyIsNull(a) && qFuzzyIsNull(b)) ||

   247         (b * b - 4 * a *c) < 0) {

   248         QBezier bez(*this);

   249         flattenBezierWithoutInflections(bez, polygon);

   250         polygon->append(QPointF(x4, y4));

   251     } else {

   252         QBezier beziers[32];

   253         beziers[0] = *this;

   254         QBezier *b = beziers;

   255 

   256         while (b >= beziers) {

   257             // check if we can pop the top bezier curve from the stack

   258             qreal y4y1 = b->y4 - b->y1;

   259             qreal x4x1 = b->x4 - b->x1;

   260             qreal l = qAbs(x4x1) + qAbs(y4y1);

   261             qreal d;

   262             if (l > 1.) {

   263                 d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )

   264                     + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );

   265             } else {

   266                 d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +

   267                     qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);

   268                 l = 1.;

   269             }

   270             if (d < .5*l || b == beziers + 31) {

   271                 // good enough, we pop it off and add the endpoint

   272                 polygon->append(QPointF(b->x4, b->y4));

   273                 --b;

   274             } else {

   275                 // split, second half of the polygon goes lower into the stack

   276                 b->split(b+1, b);

   277                 ++b;

   278             }

   591 #if 0

   592 static inline bool IntersectBB(const QBezier &a, const QBezier &b)

   593 {

   594     return a.bounds().intersects(b.bounds());

   595 }

   596 #else

   597 static int IntersectBB(const QBezier &a, const QBezier &b)

   598 {

   599     // Compute bounding box for a

   600     qreal minax, maxax, minay, maxay;

   601     if (a.x1 > a.x4)	 // These are the most likely to be extremal

   602 	minax = a.x4, maxax = a.x1;

   603     else

   604 	minax = a.x1, maxax = a.x4;

   605 

   606     if (a.x3 < minax)

   607 	minax = a.x3;

   608     else if (a.x3 > maxax)

   609 	maxax = a.x3;

   610 

   611     if (a.x2 < minax)

   612 	minax = a.x2;

   613     else if (a.x2 > maxax)

   614 	maxax = a.x2;

   615 

   616     if (a.y1 > a.y4)

   617 	minay = a.y4, maxay = a.y1;

   618     else

   619 	minay = a.y1, maxay = a.y4;

   620 

   621     if (a.y3 < minay)

   622 	minay = a.y3;

   623     else if (a.y3 > maxay)

   624 	maxay = a.y3;

   625 

   626     if (a.y2 < minay)

   627 	minay = a.y2;

   628     else if (a.y2 > maxay)

   629 	maxay = a.y2;

   630 

   631     // Compute bounding box for b

   632     qreal minbx, maxbx, minby, maxby;

   633     if (b.x1 > b.x4)

   634 	minbx = b.x4, maxbx = b.x1;

   635     else

   636 	minbx = b.x1, maxbx = b.x4;

   637 

   638     if (b.x3 < minbx)

   639 	minbx = b.x3;

   640     else if (b.x3 > maxbx)

   641 	maxbx = b.x3;

   642 

   643     if (b.x2 < minbx)

   644 	minbx = b.x2;

   645     else if (b.x2 > maxbx)

   646 	maxbx = b.x2;

   647 

   648     if (b.y1 > b.y4)

   649 	minby = b.y4, maxby = b.y1;

   650     else

   651 	minby = b.y1, maxby = b.y4;

   652 

   653     if (b.y3 < minby)

   654 	minby = b.y3;

   655     else if (b.y3 > maxby)

   656 	maxby = b.y3;

   657 

   658     if (b.y2 < minby)

   659 	minby = b.y2;

   660     else if (b.y2 > maxby)

   661 	maxby = b.y2;

   662 

   663     // Test bounding box of b against bounding box of a

   664     if ((minax > maxbx) || (minay > maxby)  // Not >= : need boundary case

   665 	|| (minbx > maxax) || (minby > maxay))

   666 	return 0; // they don't intersect

   667     else

   668 	return 1; // they intersect

   669 }

   670 #endif

   671 

   672 

   684 static bool RecursivelyIntersect(const QBezier &a, qreal t0, qreal t1, int deptha,

   685                                  const QBezier &b, qreal u0, qreal u1, int depthb,

   686                                  QVector<QPair<qreal, qreal> > *t)

   687 {

   688 #ifdef QDEBUG_BEZIER

   689     static int I = 0;

   690     int currentD = I;

   691     fprintf(stderr, "%d) t0 = %lf, t1 = %lf, deptha = %d\n"

   692             "u0 = %lf, u1 = %lf, depthb = %d\n", I++, t0, t1, deptha,

   693             u0, u1, depthb);

   694 #endif

   695     if (deptha > 0) {

   696 	QBezier A[2];

   697         a.split(&A[0], &A[1]);

   698 	qreal tmid = (t0+t1)*0.5;

   699         //qDebug()<<"\t1)"<<A[0];

   700         //qDebug()<<"\t2)"<<A[1];

   701 	deptha--;

   702 	if (depthb > 0) {

   703 	    QBezier B[2];

   704             b.split(&B[0], &B[1]);

   705             //qDebug()<<"\t3)"<<B[0];

   706             //qDebug()<<"\t4)"<<B[1];

   707 	    qreal umid = (u0+u1)*0.5;

   708 	    depthb--;

   709 	    if (IntersectBB(A[0], B[0])) {

   710                 //fprintf(stderr, "\t 1 from %d\n", currentD);

   711 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   712 				     B[0], u0, umid, depthb,

   713 				     t) && !t)

   714                     return true;

   715             }

   716 	    if (IntersectBB(A[1], B[0])) {

   717                 //fprintf(stderr, "\t 2 from %d\n", currentD);

   718 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   719                                      B[0], u0, umid, depthb,

   720                                      t) && !t)

   721                     return true;

   722             }

   723 	    if (IntersectBB(A[0], B[1])) {

   724                 //fprintf(stderr, "\t 3 from %d\n", currentD);

   725 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   726                                      B[1], umid, u1, depthb,

   727                                      t) && !t)

   728                     return true;

   729             }

   730 	    if (IntersectBB(A[1], B[1])) {

   731                 //fprintf(stderr, "\t 4 from %d\n", currentD);

   732 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   733 				     B[1], umid, u1, depthb,

   734 				     t) && !t)

   735                     return true;

   736             }

   737             return t ? !t->isEmpty() : false;

   738         } else {

   739 	    if (IntersectBB(A[0], b)) {

   740                 //fprintf(stderr, "\t 5 from %d\n", currentD);

   741 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   742 				     b, u0, u1, depthb,

   743 				     t) && !t)

   744                     return true;

   745             }

   746 	    if (IntersectBB(A[1], b)) {

   747                 //fprintf(stderr, "\t 6 from %d\n", currentD);

   748 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   749                                      b, u0, u1, depthb,

   750                                      t) && !t)

   751                     return true;

   752             }

   753             return t ? !t->isEmpty() : false;

   754         }

   755     } else {

   756 	if (depthb > 0) {

   757 	    QBezier B[2];

   758             b.split(&B[0], &B[1]);

   759 	    qreal umid = (u0 + u1)*0.5;

   760 	    depthb--;

   761 	    if (IntersectBB(a, B[0])) {

   762                 //fprintf(stderr, "\t 7 from %d\n", currentD);

   763 		if (RecursivelyIntersect(a, t0, t1, deptha,

   764                                      B[0], u0, umid, depthb,

   765                                      t) && !t)

   766                     return true;

   767             }

   768 	    if (IntersectBB(a, B[1])) {

   769                 //fprintf(stderr, "\t 8 from %d\n", currentD);

   770 		if (RecursivelyIntersect(a, t0, t1, deptha,

   771                                      B[1], umid, u1, depthb,

   772                                      t) && !t)

   773                     return true;

   774             }

   775             return t ? !t->isEmpty() : false;

   776         }

   777 	else {

   778             // Both segments are fully subdivided; now do line segments

   779 	    qreal xlk = a.x4 - a.x1;

   780 	    qreal ylk = a.y4 - a.y1;

   781 	    qreal xnm = b.x4 - b.x1;

   782 	    qreal ynm = b.y4 - b.y1;

   783 	    qreal xmk = b.x1 - a.x1;

   784 	    qreal ymk = b.y1 - a.y1;

   785 	    qreal det = xnm * ylk - ynm * xlk;

   786 	    if (1.0 + det == 1.0) {

   787 		return false;

   788             } else {

   789                 qreal detinv = 1.0 / det;

   790                 qreal rs = (xnm * ymk - ynm *xmk) * detinv;

   791                 qreal rt = (xlk * ymk - ylk * xmk) * detinv;

   792                 if ((rs < 0.0) || (rs > 1.0) || (rt < 0.0) || (rt > 1.0))

   793                     return false;

   794 

   795                 if (t) {

   796                     const qreal alpha_a = t0 + rs * (t1 - t0);

   797                     const qreal alpha_b = u0 + rt * (u1 - u0);

   798 

   799                     *t << qMakePair(alpha_a, alpha_b);

   800                 }

   801 

   802                 return true;

   803             }

   804         }

   805     }

   806 }

   807 

   808 QVector< QPair<qreal, qreal> > QBezier::findIntersections(const QBezier &a, const QBezier &b)

   809 {

   810     QVector< QPair<qreal, qreal> > v(2);

   811     findIntersections(a, b, &v);

   812     return v;

   813 }

   814 

   815 bool QBezier::findIntersections(const QBezier &a, const QBezier &b,

   816                                 QVector<QPair<qreal, qreal> > *t)

   817 {

   818     if (IntersectBB(a, b)) {

   819         QPointF la1(qFabs((a.x3 - a.x2) - (a.x2 - a.x1)),

   820                     qFabs((a.y3 - a.y2) - (a.y2 - a.y1)));

   821 	QPointF la2(qFabs((a.x4 - a.x3) - (a.x3 - a.x2)),

   822                     qFabs((a.y4 - a.y3) - (a.y3 - a.y2)));

   823 	QPointF la;

   824 	if (la1.x() > la2.x()) la.setX(la1.x()); else la.setX(la2.x());

   825 	if (la1.y() > la2.y()) la.setY(la1.y()); else la.setY(la2.y());

   826 	QPointF lb1(qFabs((b.x3 - b.x2) - (b.x2 - b.x1)),

   827                     qFabs((b.y3 - b.y2) - (b.y2 - b.y1)));

   828 	QPointF lb2(qFabs((b.x4 - b.x3) - (b.x3 - b.x2)),

   829                     qFabs((b.y4 - b.y3) - (b.y3 - b.y2)));

   830 	QPointF lb;

   831 	if (lb1.x() > lb2.x()) lb.setX(lb1.x()); else lb.setX(lb2.x());

   832 	if (lb1.y() > lb2.y()) lb.setY(lb1.y()); else lb.setY(lb2.y());

   833 	qreal l0;

   834 	if (la.x() > la.y())

   835 	    l0 = la.x();

   836 	else

   837 	    l0 = la.y();

   838 	int ra;

   839 	if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)

   840 	    ra = 0;

   841 	else

   842 	    ra = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));

   843 	if (lb.x() > lb.y())

   844 	    l0 = lb.x();

   845 	else

   846 	    l0 = lb.y();

   847 	int rb;

   848 	if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)

   849 	    rb = 0;

   850 	else

   851 	    rb = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));

   852 

   853         // if qreal is float then halve the number of subdivisions

   854         if (sizeof(qreal) == 4) {

   855             ra /= 2;

   856             rb /= 2;

   857         }

   858 

   859 	return RecursivelyIntersect(a, 0., 1., ra, b, 0., 1., rb, t);

   860     }

   861 

   862     //Don't sort here because it breaks the orders of corresponding

   863     //  intersections points. this way t's at the same locations correspond

   864     //  to the same intersection point.

   865     //qSort(parameters[0].begin(), parameters[0].end(), qLess<qreal>());

   866     //qSort(parameters[1].begin(), parameters[1].end(), qLess<qreal>());

   867 

   868     return false;

   869 }

   870 

   897 }

   898 

   899 QVector< QList<QBezier> > QBezier::splitAtIntersections(QBezier &b)

   900 {

   901     QVector< QList<QBezier> > curves(2);

   902 

   903     QVector< QPair<qreal, qreal> > allInters = findIntersections(*this, b);

   904 

   905     QList<qreal> inters1;

   906     QList<qreal> inters2;

   907 

   908     for (int i = 0; i < allInters.size(); ++i) {

   909         inters1 << allInters[i].first;

   910         inters2 << allInters[i].second;

   911     }

   912 

   913     qSort(inters1.begin(), inters1.end(), qLess<qreal>());

   914     qSort(inters2.begin(), inters2.end(), qLess<qreal>());

   915 

   916     Q_ASSERT(inters1.count() == inters2.count());

   917 

   918     int i;

   919     for (i = 0; i < inters1.count(); ++i) {

   920         qreal t1 = inters1.at(i);

   921         qreal t2 = inters2.at(i);

   922 

   923         QBezier curve1, curve2;

   924         parameterSplitLeft(t1, &curve1);

   925 	b.parameterSplitLeft(t2, &curve2);

   926         curves[0].append(curve1);

   927         curves[0].append(curve2);

   928     }

   929     curves[0].append(*this);

   930     curves[1].append(b);

   931 

   932     return curves;

  1022 

  1023     QList<qreal> result;

  1102 

  1103 static inline void bindInflectionPoint(const QBezier &bez, const qreal t,

  1104                                        qreal *tMinus , qreal *tPlus)

  1105 {

  1106     if (t <= 0) {

  1107         *tMinus = *tPlus = -1;

  1108         return;

  1109     } else if (t >= 1) {

  1110         *tMinus = *tPlus = 2;

  1111         return;

  1112     }

  1113 

  1114     QBezier left, right;

  1115     splitBezierAt(bez, t, &left, &right);

  1116 

  1117     qreal ax = -right.x1 + 3*right.x2 - 3*right.x3 + right.x4;

  1118     qreal ay = -right.y1 + 3*right.y2 - 3*right.y3 + right.y4;

  1119     qreal ex = 3 * (right.x2 - right.x3);

  1120     qreal ey = 3 * (right.y2 - right.y3);

  1121 

  1122     qreal s4 = qAbs(6 * (ey * ax - ex * ay) / qSqrt(ex * ex + ey * ey)) + 0.00001f;

  1123     qreal tf = qPow(qreal(9 * flatness / s4), qreal(1./3.));

  1124     *tMinus = t - (1 - t) * tf;

  1125     *tPlus  = t + (1 - t) * tf;

  1126 }

  1127 

  1128 void QBezier::addToPolygonIterative(QPolygonF *p) const

  1129 {

  1130     qreal t1, t2, tcusp;

  1131     qreal t1min, t1plus, t2min, t2plus;

  1132 

  1133     qreal ax = -x1 + 3*x2 - 3*x3 + x4;

  1134     qreal ay = -y1 + 3*y2 - 3*y3 + y4;

  1135     qreal bx = 3*x1 - 6*x2 + 3*x3;

  1136     qreal by = 3*y1 - 6*y2 + 3*y3;

  1137     qreal cx = -3*x1 + 3*x2;

  1138     qreal cy = -3*y1 + 2*y2;

  1139 

  1140     if (findInflections(6 * (ay * bx - ax * by),

  1141                         6 * (ay * cx - ax * cy),

  1142                         2 * (by * cx - bx * cy),

  1143                         &t1, &t2, &tcusp)) {

  1144         bindInflectionPoint(*this, t1, &t1min, &t1plus);

  1145         bindInflectionPoint(*this, t2, &t2min, &t2plus);

  1146 

  1147         QBezier tmpBez = *this;

  1148         QBezier left, right, bez1, bez2, bez3;

  1149 	if (t1min > 0) {

  1150             if (t1min >= 1) {

  1151                 flattenBezierWithoutInflections(tmpBez, p);

  1152             } else {

  1153                 splitBezierAt(tmpBez, t1min, &left, &right);

  1154                 flattenBezierWithoutInflections(left, p);

  1155                 p->append(tmpBez.pointAt(t1min));

  1156 

  1157                 if (t2min < t1plus) {

  1158                     if (tcusp < 1) {

  1159                         p->append(tmpBez.pointAt(tcusp));

  1160                     }

  1161                     if (t2plus < 1) {

  1162                         splitBezierAt(tmpBez, t2plus, &left, &right);

  1163                         flattenBezierWithoutInflections(right, p);

  1164                     }

  1165                 } else if (t1plus < 1) {

  1166                     if (t2min < 1) {

  1167                         splitBezierAt(tmpBez, t2min, &bez3, &right);

  1168                         splitBezierAt(bez3, t1plus, &left, &bez2);

  1169 

  1170                         flattenBezierWithoutInflections(bez2, p);

  1171                         p->append(tmpBez.pointAt(t2min));

  1172 

  1173                         if (t2plus < 1) {

  1174                             splitBezierAt(tmpBez, t2plus, &left, &bez2);

  1175                             flattenBezierWithoutInflections(bez2, p);

  1176                         }

  1177                     } else {

  1178                         splitBezierAt(tmpBez, t1plus, &left, &bez2);

  1179                         flattenBezierWithoutInflections(bez2, p);

  1180                     }

  1181                 }

  1182             }

  1183 	} else if (t1plus > 0) {

  1184             p->append(QPointF(x1, y1));

  1185             if (t2min < t1plus)	{

  1186                 if (tcusp < 1) {

  1187                     p->append(tmpBez.pointAt(tcusp));

  1188                 }

  1189                 if (t2plus < 1) {

  1190                     splitBezierAt(tmpBez, t2plus, &left, &bez2);

  1191                     flattenBezierWithoutInflections(bez2, p);

  1192                 }

  1193             } else if (t1plus < 1) {

  1194                 if (t2min < 1) {

  1195                     splitBezierAt(tmpBez, t2min, &bez3, &right);

  1196                     splitBezierAt(bez3, t1plus, &left, &bez2);

  1197 

  1198                     flattenBezierWithoutInflections(bez2, p);

  1199 

  1200                     p->append(tmpBez.pointAt(t2min));

  1201                     if (t2plus < 1) {

  1202                         splitBezierAt(tmpBez, t2plus, &left, &bez2);

  1203                         flattenBezierWithoutInflections(bez2, p);

  1204                     }

  1205                 } else {

  1206                     splitBezierAt(tmpBez, t1plus, &left, &bez2);

  1207                     flattenBezierWithoutInflections(bez2, p);

  1208                 }

  1209             }

  1210         } else if (t2min > 0) {

  1211             if (t2min < 1) {

  1212                 splitBezierAt(tmpBez, t2min, &bez1, &right);

  1213                 flattenBezierWithoutInflections(bez1, p);

  1214                 p->append(tmpBez.pointAt(t2min));

  1215 

  1216                 if (t2plus < 1) {

  1217                     splitBezierAt(tmpBez, t2plus, &left, &bez2);

  1218                     flattenBezierWithoutInflections(bez2, p);

  1219                 }

  1220             } else {

  1221                 //### in here we should check whether the area of the

  1222                 //    triangle formed between pt1/pt2/pt3 is smaller

  1223                 //    or equal to 0 and then do iterative flattening

  1224                 //    if not we should fallback and do the recursive

  1225                 //    flattening.

  1226                 flattenBezierWithoutInflections(tmpBez, p);

  1227             }

  1228         } else if (t2plus > 0) {

  1229             p->append(QPointF(x1, y1));

  1230             if (t2plus < 1) {

  1231                 splitBezierAt(tmpBez, t2plus, &left, &bez2);

  1232                 flattenBezierWithoutInflections(bez2, p);

  1233             }

  1234         } else {

  1235             flattenBezierWithoutInflections(tmpBez, p);

  1236         }

  1237     } else {

  1238         QBezier bez = *this;

  1239         flattenBezierWithoutInflections(bez, p);

  1240     }

  1241 

  1242     p->append(QPointF(x4, y4));

  1243 }

  1244