File indexing completed on 2023-12-03 07:43:20

0001 /*
0002  * Copyright (C) 2008-2009 Fredrik Höglund <fredrik@kde.org>
0003  *
0004  * This library is free software; you can redistribute it and/or
0005  * modify it under the terms of the GNU Library General Public
0006  * License as published by the Free Software Foundation; either
0007  * version 2 of the License, or (at your option) any later version.
0008  *
0009  * This library is distributed in the hope that it will be useful,
0010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0012  * Library General Public License for more details.
0013  *
0014  * You should have received a copy of the GNU Library General Public License
0015  * along with this library; see the file COPYING.LIB.  If not, write to
0016  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
0017  * Boston, MA 02110-1301, USA.
0018  */
0019 
0020 #include "borderarcstroker.h"
0021 #include <cmath>
0022 
0023 #if defined(__GNUC__)
0024 #  define K_ALIGN(n) __attribute((aligned(n)))
0025 #  if defined(__SSE__)
0026 #    define HAVE_SSE
0027 #  endif
0028 #elif defined(__INTEL_COMPILER)
0029 #  define K_ALIGN(n) __declspec(align(n))
0030 #  define HAVE_SSE
0031 #else
0032 #  define K_ALIGN(n)
0033 #endif
0034 
0035 #ifdef HAVE_SSE
0036 #  include <xmmintrin.h>
0037 #endif
0038 
0039 namespace khtml
0040 {
0041 
0042 // This is a helper class used by BorderArcStroker
0043 class KCubicBezier
0044 {
0045 public:
0046     KCubicBezier() {}
0047     KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3);
0048 
0049     void split(KCubicBezier *a, KCubicBezier *b, qreal t = .5) const;
0050     KCubicBezier section(qreal t1, qreal t2) const;
0051     KCubicBezier leftSection(qreal t) const;
0052     KCubicBezier rightSection(qreal t) const;
0053     KCubicBezier derivative() const;
0054     QPointF pointAt(qreal t) const;
0055     QPointF deltaAt(qreal t) const;
0056     QLineF normalVectorAt(qreal t) const;
0057     qreal slopeAt(qreal t) const;
0058     qreal tAtLength(qreal l) const;
0059     qreal tAtIntersection(const QLineF &line) const;
0060     QLineF chord() const;
0061     qreal length() const;
0062     qreal convexHullLength() const;
0063 
0064     QPointF p0() const
0065     {
0066         return QPointF(x0, y0);
0067     }
0068     QPointF p1() const
0069     {
0070         return QPointF(x1, y1);
0071     }
0072     QPointF p2() const
0073     {
0074         return QPointF(x2, y2);
0075     }
0076     QPointF p3() const
0077     {
0078         return QPointF(x3, y3);
0079     }
0080 
0081 public:
0082     qreal x0, y0, x1, y1, x2, y2, x3, y3;
0083 };
0084 
0085 KCubicBezier::KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3)
0086 {
0087     x0 = p0.x();
0088     y0 = p0.y();
0089     x1 = p1.x();
0090     y1 = p1.y();
0091     x2 = p2.x();
0092     y2 = p2.y();
0093     x3 = p3.x();
0094     y3 = p3.y();
0095 }
0096 
0097 // Splits the curve at t, using the de Casteljau algorithm.
0098 // This function is not atomic, so do not pass a pointer to the curve being split.
0099 void KCubicBezier::split(KCubicBezier *a, KCubicBezier *b, qreal t) const
0100 {
0101     a->x0 = x0;
0102     a->y0 = y0;
0103 
0104     b->x3 = x3;
0105     b->y3 = y3;
0106 
0107     a->x1 = x0 + (x1 - x0) * t;
0108     a->y1 = y0 + (y1 - y0) * t;
0109 
0110     b->x2 = x2 + (x3 - x2) * t;
0111     b->y2 = y2 + (y3 - y2) * t;
0112 
0113     // The point on the line (p1, p2).
0114     const qreal x = x1 + (x2 - x1) * t;
0115     const qreal y = y1 + (y2 - y1) * t;
0116 
0117     a->x2 = a->x1 + (x - a->x1) * t;
0118     a->y2 = a->y1 + (y - a->y1) * t;
0119 
0120     b->x1 = x + (b->x2 - x) * t;
0121     b->y1 = y + (b->y2 - y) * t;
0122 
0123     a->x3 = b->x0 = a->x2 + (b->x1 - a->x2) * t;
0124     a->y3 = b->y0 = a->y2 + (b->y1 - a->y2) * t;
0125 }
0126 
0127 // Returns a new bezier curve that is the interval between t1 and t2 in this curve
0128 KCubicBezier KCubicBezier::section(qreal t1, qreal t2) const
0129 {
0130     return leftSection(t2).rightSection(t1 / t2);
0131 }
0132 
0133 // Returns a new bezier curve that is the section of this curve left of t
0134 KCubicBezier KCubicBezier::leftSection(qreal t) const
0135 {
0136     KCubicBezier left, right;
0137     split(&left, &right, t);
0138     return left;
0139 }
0140 
0141 // Returns a new bezier curve that is the section of this curve right of t
0142 KCubicBezier KCubicBezier::rightSection(qreal t) const
0143 {
0144     KCubicBezier left, right;
0145     split(&left, &right, t);
0146     return right;
0147 }
0148 
0149 // Returns the point at t
0150 QPointF KCubicBezier::pointAt(qreal t) const
0151 {
0152     const qreal m_t = 1 - t;
0153     const qreal m_t2 = m_t * m_t;
0154     const qreal m_t3 = m_t2 * m_t;
0155     const qreal t2 = t * t;
0156     const qreal t3 = t2 * t;
0157 
0158     const qreal x = m_t3 * x0 + 3 * t * m_t2 * x1 + 3 * t2 * m_t * x2 + t3 * x3;
0159     const qreal y = m_t3 * y0 + 3 * t * m_t2 * y1 + 3 * t2 * m_t * y2 + t3 * y3;
0160 
0161     return QPointF(x, y);
0162 }
0163 
0164 // Returns the delta at t, i.e. the first derivative of the cubic equation at t.
0165 QPointF KCubicBezier::deltaAt(qreal t) const
0166 {
0167     const qreal m_t = 1 - t;
0168     const qreal m_t2 = m_t * m_t;
0169     const qreal t2 = t * t;
0170 
0171     const qreal dx = 3 * (x1 - x0) * m_t2 + 3 * (x2 - x1) * 2 * t * m_t + 3 * (x3 - x2) * t2;
0172     const qreal dy = 3 * (y1 - y0) * m_t2 + 3 * (y2 - y1) * 2 * t * m_t + 3 * (y3 - y2) * t2;
0173 
0174     return QPointF(dx, dy);
0175 }
0176 
0177 // Returns the slope at t (dy / dx)
0178 qreal KCubicBezier::slopeAt(qreal t) const
0179 {
0180     const QPointF delta = deltaAt(t);
0181     return qFuzzyIsNull(delta.x()) ?
0182            (delta.y() < 0 ? -1 : 1) : delta.y() / delta.x();
0183 }
0184 
0185 // Returns the normal vector at t
0186 QLineF KCubicBezier::normalVectorAt(qreal t) const
0187 {
0188     const QPointF point = pointAt(t);
0189     const QPointF delta = deltaAt(t);
0190 
0191     return QLineF(point, point + delta).normalVector();
0192 }
0193 
0194 // Returns a curve that is the first derivative of this curve.
0195 // The first derivative of a cubic bezier curve is a quadratic bezier curve,
0196 // but this function elevates it to a cubic curve.
0197 KCubicBezier KCubicBezier::derivative() const
0198 {
0199     KCubicBezier c;
0200 
0201     c.x0 = 3 * (x1 - x0);
0202     c.x1 = x1 - x0 + 2 * (x2 - x1);
0203     c.x2 = 2 * (x2 - x1) + x3 - x2;
0204     c.x3 = 3 * (x3 - x2);
0205 
0206     c.y0 = 3 * (y1 - y0);
0207     c.y1 = y1 - y0 + 2 * (y2 - y1);
0208     c.y2 = 2 * (y2 - y1) + y3 - y2;
0209     c.y3 = 3 * (y3 - y2);
0210 
0211     return c;
0212 }
0213 
0214 // Returns the sum of the lengths of the lines connecting the control points
0215 qreal KCubicBezier::convexHullLength() const
0216 {
0217 #ifdef HAVE_SSE
0218     K_ALIGN(16) float vals[4];
0219 
0220     __m128 m1, m2;
0221     m1 = _mm_set_ps(0, x1 - x0, x2 - x1, x3 - x2);
0222     m2 = _mm_set_ps(0, y1 - y0, y2 - y1, y3 - y2);
0223     m1 = _mm_add_ps(_mm_mul_ps(m1, m1), _mm_mul_ps(m2, m2));
0224     _mm_store_ps(vals, _mm_sqrt_ps(m1));
0225 
0226     return vals[0] + vals[1] + vals[2];
0227 #else
0228     return QLineF(x0, y0, x1, y1).length() + QLineF(x1, y1, x2, y2).length() + QLineF(x2, y2, x3, y3).length();
0229 #endif
0230 }
0231 
0232 // Returns the chord, i.e. the line that connects the two endpoints of the curve
0233 QLineF KCubicBezier::chord() const
0234 {
0235     return QLineF(x0, y0, x3, y3);
0236 }
0237 
0238 // Returns the arc length of the bezier curve, computed by recursively subdividing the
0239 // curve until the difference between the length of the convex hull of the section
0240 // and its chord is less than .01 device units.
0241 qreal KCubicBezier::length() const
0242 {
0243     const qreal error = .01;
0244     const qreal len = convexHullLength();
0245 
0246     if ((len - chord().length()) > error) {
0247         KCubicBezier left, right;
0248         split(&left, &right);
0249         return left.length() + right.length();
0250     }
0251 
0252     return len;
0253 }
0254 
0255 // Returns the value for the t parameter that corresponds to the point
0256 // l device units from the starting point of the curve.
0257 qreal KCubicBezier::tAtLength(qreal l) const
0258 {
0259     const qreal error = 0.1;
0260 
0261     if (l <= 0) {
0262         return 0;
0263     }
0264 
0265     qreal len = length();
0266 
0267     if (l > len || qFuzzyCompare(l + 1.0, len + 1.0)) {
0268         return 1;
0269     }
0270 
0271     qreal upperT = 1;
0272     qreal lowerT = 0;
0273 
0274     while (1) {
0275         const qreal t = lowerT + (upperT - lowerT) / 2;
0276         const qreal len = leftSection(t).length();
0277 
0278         if (qAbs(l - len) < error) {
0279             return t;
0280         }
0281 
0282         if (l > len) {
0283             lowerT = t;
0284         } else {
0285             upperT = t;
0286         }
0287     }
0288 }
0289 
0290 // Returns the value of t at the point where the given line intersects
0291 // the bezier curve. The line is treated as an infinitely long line.
0292 // Note that this implementation assumes that there is a single point of
0293 // intersection, that both control points are on the same side of
0294 // the curve, and that the curve is not self intersecting.
0295 qreal KCubicBezier::tAtIntersection(const QLineF &line) const
0296 {
0297     const qreal error = 0.1;
0298 
0299     // Extend the line to make it a reasonable approximation of an infinitely long line
0300     const qreal len = line.length();
0301     const QLineF l = QLineF(line.pointAt(1.0 / len * -1e10), line.pointAt(1.0 / len * 1e10));
0302 
0303     // Check if the line intersects the curve at all
0304     if (chord().intersect(l, nullptr) != QLineF::BoundedIntersection) {
0305         return 1;
0306     }
0307 
0308     qreal upperT = 1;
0309     qreal lowerT = 0;
0310 
0311     KCubicBezier c = *this;
0312 
0313     while (1) {
0314         const qreal t = lowerT + (upperT - lowerT) / 2;
0315         if (c.length() < error) {
0316             return t;
0317         }
0318 
0319         KCubicBezier left, right;
0320         c.split(&left, &right);
0321 
0322         // If the line intersects the left section
0323         if (left.chord().intersect(l, nullptr) == QLineF::BoundedIntersection) {
0324             upperT = t;
0325             c = left;
0326         } else {
0327             lowerT = t;
0328             c = right;
0329         }
0330     }
0331 }
0332 
0333 // ----------------------------------------------------------------------------
0334 
0335 BorderArcStroker::BorderArcStroker()
0336 {
0337 }
0338 
0339 BorderArcStroker::~BorderArcStroker()
0340 {
0341 }
0342 
0343 QPainterPath BorderArcStroker::createStroke(qreal *nextOffset) const
0344 {
0345     const QRectF outerRect = rect;
0346     const QRectF innerRect = rect.adjusted(hlw, vlw, -hlw, -vlw);
0347 
0348     // Avoid hitting the assert below if the radius is smaller than the border width
0349     if (!outerRect.isValid() || !innerRect.isValid()) {
0350         return QPainterPath();
0351     }
0352 
0353     QPainterPath innerPath, outerPath;
0354     innerPath.arcMoveTo(innerRect, angle);
0355     outerPath.arcMoveTo(outerRect, angle);
0356     innerPath.arcTo(innerRect, angle, sweepLength);
0357     outerPath.arcTo(outerRect, angle, sweepLength);
0358 
0359     Q_ASSERT(qAbs(sweepLength) <= 90);
0360     Q_ASSERT(innerPath.elementCount() == 4 && outerPath.elementCount() == 4);
0361 
0362     const KCubicBezier inner(innerPath.elementAt(0), innerPath.elementAt(1), innerPath.elementAt(2), innerPath.elementAt(3));
0363     const KCubicBezier outer(outerPath.elementAt(0), outerPath.elementAt(1), outerPath.elementAt(2), outerPath.elementAt(3));
0364 
0365     qreal a = std::fmod(angle, qreal(360.0));
0366     if (a < 0) {
0367         a += 360.0;
0368     }
0369 
0370     // Figure out which border we're starting from
0371     qreal initialWidth;
0372     if ((a >= 0 && a < 90) || (a >= 180 && a < 270)) {
0373         initialWidth = sweepLength > 0 ? hlw : vlw;
0374     } else {
0375         initialWidth = sweepLength > 0 ? vlw : hlw;
0376     }
0377 
0378     const qreal finalWidth = qMax(qreal(0.1), QLineF(outer.p3(), inner.p3()).length());
0379     const qreal dashAspect  = (pattern[0] / initialWidth);
0380     const qreal spaceAspect = (pattern[1] / initialWidth);
0381     const qreal length = inner.length();
0382 
0383     QPainterPath path;
0384     qreal innerStart = 0, outerStart = 0;
0385     qreal pos = 0;
0386     bool dash = true;
0387 
0388     qreal offset = fmod(patternOffset, pattern[0] + pattern[1]);
0389     if (offset < 0) {
0390         offset += pattern[0] + pattern[1];
0391     }
0392 
0393     if (offset > 0) {
0394         if (offset >= pattern[0]) {
0395             offset -= pattern[0];
0396             dash = false;
0397         } else {
0398             dash = true;
0399         }
0400         pos = -offset;
0401     }
0402 
0403     while (innerStart < 1) {
0404         const qreal lineWidth = QLineF(outer.pointAt(outerStart), inner.pointAt(innerStart)).length();
0405         const qreal length = lineWidth * (dash ? dashAspect : spaceAspect);
0406         pos += length;
0407 
0408         if (pos > 0) {
0409             const qreal innerEnd = inner.tAtLength(pos);
0410             const QLineF normal = inner.normalVectorAt(innerEnd);
0411             const qreal outerEnd = outer.tAtIntersection(normal);
0412 
0413             if (dash) {
0414                 // The outer and inner curves of the dash
0415                 const KCubicBezier a = outer.section(outerStart, outerEnd);
0416                 const KCubicBezier b = inner.section(innerStart, innerEnd);
0417 
0418                 // Add the dash to the path
0419                 path.moveTo(a.p0());
0420                 path.cubicTo(a.p1(), a.p2(), a.p3());
0421                 path.lineTo(b.p3());
0422                 path.cubicTo(b.p2(), b.p1(), b.p0());
0423                 path.closeSubpath();
0424             }
0425 
0426             innerStart = innerEnd;
0427             outerStart = outerEnd;
0428         }
0429 
0430         dash = !dash;
0431     }
0432 
0433     if (nextOffset) {
0434         const qreal remainder = pos - length;
0435 
0436         if (dash) {
0437             *nextOffset = -remainder;
0438         } else {
0439             *nextOffset = (pattern[0] / initialWidth) * finalWidth - remainder;
0440         }
0441     }
0442 
0443     return path;
0444 }
0445 
0446 } // namespace khtml
0447