khtml/misc/borderarcstroker.cpp

   1 /*
   2  * Copyright (C) 2008-2009 Fredrik Höglund <fredrik@kde.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public License
  15  * along with this library; see the file COPYING.LIB.  If not, write to
  16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 #include "borderarcstroker.h"
  21 #include <cmath>
  22
  23 #if defined(__GNUC__)
  24 #  define K_ALIGN(n) __attribute((aligned(n)))
  25 #  if defined(__SSE__)
  26 #    define HAVE_SSE
  27 #  endif
  28 #elif defined(__INTEL_COMPILER)
  29 #  define K_ALIGN(n) __declspec(align(n))
  30 #  define HAVE_SSE
  31 #else
  32 #  define K_ALIGN(n)
  33 #endif
  34
  35 #ifdef HAVE_SSE
  36 #  include <xmmintrin.h>
  37 #endif
  38
  39
  40 namespace khtml {
  41
  42
  43 // This is a helper class used by BorderArcStroker
  44 class KCubicBezier
  45 {
  46 public:
  47     KCubicBezier() {}
  48     KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3);
  49
  50     void split(KCubicBezier *a, KCubicBezier *b, qreal t = .5) const;
  51     KCubicBezier section(qreal t1, qreal t2) const;
  52     KCubicBezier leftSection(qreal t) const;
  53     KCubicBezier rightSection(qreal t) const;
  54     KCubicBezier derivative() const;
  55     QPointF pointAt(qreal t) const;
  56     QPointF deltaAt(qreal t) const;
  57     QLineF normalVectorAt(qreal t) const;
  58     qreal slopeAt(qreal t) const;
  59     qreal tAtLength(qreal l) const;
  60     qreal tAtIntersection(const QLineF &line) const;
  61     QLineF chord() const;
  62     qreal length() const;
  63     qreal convexHullLength() const;
  64
  65     QPointF p0() const { return QPointF(x0, y0); }
  66     QPointF p1() const { return QPointF(x1, y1); }
  67     QPointF p2() const { return QPointF(x2, y2); }
  68     QPointF p3() const { return QPointF(x3, y3); }
  69
  70 public:
  71     qreal x0, y0, x1, y1, x2, y2, x3, y3;
  72 };
  73
  74
  75 KCubicBezier::KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3)
  76 {
  77     x0 = p0.x();
  78     y0 = p0.y();
  79     x1 = p1.x();
  80     y1 = p1.y();
  81     x2 = p2.x();
  82     y2 = p2.y();
  83     x3 = p3.x();
  84     y3 = p3.y();
  85 }
  86
  87 // Splits the curve at t, using the de Casteljau algorithm.
  88 // This function is not atomic, so do not pass a pointer to the curve being split.
  89 void KCubicBezier::split(KCubicBezier *a, KCubicBezier *b, qreal t) const
  90 {
  91     a->x0 = x0;
  92     a->y0 = y0;
  93
  94     b->x3 = x3;
  95     b->y3 = y3;
  96
  97     a->x1 = x0 + (x1 - x0) * t;
  98     a->y1 = y0 + (y1 - y0) * t;
  99
 100     b->x2 = x2 + (x3 - x2) * t;
 101     b->y2 = y2 + (y3 - y2) * t;
 102
 103     // The point on the line (p1, p2).
 104     const qreal x = x1 + (x2 - x1) * t;
 105     const qreal y = y1 + (y2 - y1) * t;
 106
 107     a->x2 = a->x1 + (x - a->x1) * t;
 108     a->y2 = a->y1 + (y - a->y1) * t;
 109
 110     b->x1 = x + (b->x2 - x) * t;
 111     b->y1 = y + (b->y2 - y) * t;
 112
 113     a->x3 = b->x0 = a->x2 + (b->x1 - a->x2) * t;
 114     a->y3 = b->y0 = a->y2 + (b->y1 - a->y2) * t;
 115 }
 116
 117 // Returns a new bezier curve that is the interval between t1 and t2 in this curve
 118 KCubicBezier KCubicBezier::section(qreal t1, qreal t2) const
 119 {
 120     return leftSection(t2).rightSection(t1 / t2);
 121 }
 122
 123 // Returns a new bezier curve that is the section of this curve left of t
 124 KCubicBezier KCubicBezier::leftSection(qreal t) const
 125 {
 126     KCubicBezier left, right;
 127     split(&left, &right, t);
 128     return left;
 129 }
 130
 131 // Returns a new bezier curve that is the section of this curve right of t
 132 KCubicBezier KCubicBezier::rightSection(qreal t) const
 133 {
 134     KCubicBezier left, right;
 135     split(&left, &right, t);
 136     return right;
 137 }
 138
 139 // Returns the point at t
 140 QPointF KCubicBezier::pointAt(qreal t) const
 141 {
 142     const qreal m_t = 1 - t;
 143     const qreal m_t2 = m_t * m_t;
 144     const qreal m_t3 = m_t2 * m_t;
 145     const qreal t2 = t * t;
 146     const qreal t3 = t2 * t;
 147
 148     const qreal x = m_t3 * x0 + 3 * t * m_t2 * x1 + 3 * t2 * m_t * x2 + t3 * x3;
 149     const qreal y = m_t3 * y0 + 3 * t * m_t2 * y1 + 3 * t2 * m_t * y2 + t3 * y3;
 150
 151     return QPointF(x, y);
 152 }
 153
 154 // Returns the delta at t, i.e. the first derivative of the cubic equation at t.
 155 QPointF KCubicBezier::deltaAt(qreal t) const
 156 {
 157     const qreal m_t = 1 - t;
 158     const qreal m_t2 = m_t * m_t;
 159     const qreal t2 = t * t;
 160
 161     const qreal dx = 3 * (x1 - x0) * m_t2 + 3 * (x2 - x1) * 2 * t * m_t + 3 * (x3 - x2) * t2;
 162     const qreal dy = 3 * (y1 - y0) * m_t2 + 3 * (y2 - y1) * 2 * t * m_t + 3 * (y3 - y2) * t2;
 163
 164     return QPointF(dx, dy);
 165 }
 166
 167 // Returns the slope at t (dy / dx)
 168 qreal KCubicBezier::slopeAt(qreal t) const
 169 {
 170     const QPointF delta = deltaAt(t);
 171     return qFuzzyCompare(delta.x() + 1.0, 1.0) ?
 172                 (delta.y() < 0 ? -1 : 1) : delta.y() / delta.x();
 173 }
 174
 175 // Returns the normal vector at t
 176 QLineF KCubicBezier::normalVectorAt(qreal t) const
 177 {
 178     const QPointF point = pointAt(t);
 179     const QPointF delta = deltaAt(t);
 180
 181     return QLineF(point, point + delta).normalVector();
 182 }
 183
 184 // Returns a curve that is the first derivative of this curve.
 185 // The first derivative of a cubic bezier curve is a quadratic bezier curve,
 186 // but this function elevates it to a cubic curve.
 187 KCubicBezier KCubicBezier::derivative() const
 188 {
 189     KCubicBezier c;
 190
 191     c.x0 = 3 * (x1 - x0);
 192     c.x1 = x1 - x0 + 2 * (x2 - x1);
 193     c.x2 = 2 * (x2 - x1) + x3 - x2;
 194     c.x3 = 3 * (x3 - x2);
 195
 196     c.y0 = 3 * (y1 - y0);
 197     c.y1 = y1 - y0 + 2 * (y2 - y1);
 198     c.y2 = 2 * (y2 - y1) + y3 - y2;
 199     c.y3 = 3 * (y3 - y2);
 200
 201     return c;
 202 }
 203
 204 // Returns the sum of the lengths of the lines connecting the control points
 205 qreal KCubicBezier::convexHullLength() const
 206 {
 207 #ifdef HAVE_SSE
 208     K_ALIGN(16) float vals[4];
 209
 210     __m128 m1, m2;
 211     m1 = _mm_set_ps(0, x1 - x0, x2 - x1, x3 - x2);
 212     m2 = _mm_set_ps(0, y1 - y0, y2 - y1, y3 - y2);
 213     m1 = _mm_add_ps(_mm_mul_ps(m1, m1), _mm_mul_ps(m2, m2));
 214     _mm_store_ps(vals, _mm_sqrt_ps(m1));
 215
 216     return vals[0] + vals[1] + vals[2];
 217 #else
 218     return QLineF(x0, y0, x1, y1).length() + QLineF(x1, y1, x2, y2).length() + QLineF(x2, y2, x3, y3).length();
 219 #endif
 220 }
 221
 222 // Returns the chord, i.e. the line that connects the two endpoints of the curve
 223 QLineF KCubicBezier::chord() const
 224 {
 225     return QLineF(x0, y0, x3, y3);
 226 }
 227
 228 // Returns the arc length of the bezier curve, computed by recursively subdividing the
 229 // curve until the difference between the length of the convex hull of the section
 230 // and its chord is less than .01 device units.
 231 qreal KCubicBezier::length() const
 232 {
 233     const qreal error = .01;
 234     const qreal len = convexHullLength();
 235
 236     if ((len - chord().length()) > error) {
 237         KCubicBezier left, right;
 238         split(&left, &right);
 239         return left.length() + right.length();
 240     }
 241
 242     return len;
 243 }
 244
 245 // Returns the value for the t parameter that corresponds to the point
 246 // l device units from the starting point of the curve.
 247 qreal KCubicBezier::tAtLength(qreal l) const
 248 {
 249     const qreal error = 0.1;
 250
 251     if (l <= 0)
 252         return 0;
 253
 254     qreal len = length();
 255
 256     if (l > len || qFuzzyCompare(l + 1.0, len + 1.0))
 257         return 1;
 258
 259     qreal upperT = 1;
 260     qreal lowerT = 0;
 261
 262     while (1)
 263     {
 264         const qreal t = lowerT + (upperT - lowerT) / 2;
 265         const qreal len = leftSection(t).length();
 266
 267         if (qAbs(l - len) < error)
 268             return t;
 269
 270         if (l > len)
 271             lowerT = t;
 272         else
 273             upperT = t;
 274     }
 275 }
 276
 277 // Returns the value of t at the point where the given line intersects
 278 // the bezier curve. The line is treated as an infinitely long line.
 279 // Note that this implementation assumes that there is a single point of
 280 // intersection, that both control points are on the same side of
 281 // the curve, and that the curve is not self intersecting.
 282 qreal KCubicBezier::tAtIntersection(const QLineF &line) const
 283 {
 284     const qreal error = 0.1;
 285
 286     // Extend the line to make it a reasonable approximation of an infinitely long line
 287     const qreal len = line.length();
 288     const QLineF l = QLineF(line.pointAt(1.0 / len * -1e10), line.pointAt(1.0 / len * 1e10));
 289
 290     // Check if the line intersects the curve at all
 291     if (chord().intersect(l, 0) != QLineF::BoundedIntersection)
 292         return 1;
 293
 294     qreal upperT = 1;
 295     qreal lowerT = 0;
 296
 297     KCubicBezier c = *this;
 298
 299     while (1)
 300     {
 301         const qreal t = lowerT + (upperT - lowerT) / 2;
 302         if (c.length() < error)
 303             return t;
 304
 305         KCubicBezier left, right;
 306         c.split(&left, &right);
 307
 308         // If the line intersects the left section
 309         if (left.chord().intersect(l, 0) == QLineF::BoundedIntersection) {
 310             upperT = t;
 311             c = left;
 312         } else {
 313             lowerT = t;
 314             c = right;
 315         }
 316     }
 317 }
 318
 319
 320
 321 // ----------------------------------------------------------------------------
 322
 323
 324
 325 BorderArcStroker::BorderArcStroker()
 326 {
 327 }
 328
 329 BorderArcStroker::~BorderArcStroker()
 330 {
 331 }
 332
 333 QPainterPath BorderArcStroker::createStroke(qreal *nextOffset) const
 334 {
 335     const QRectF outerRect = rect;
 336     const QRectF innerRect = rect.adjusted(hlw, vlw, -hlw, -vlw);
 337
 338     QPainterPath innerPath, outerPath;
 339     innerPath.arcMoveTo(innerRect, angle);
 340     outerPath.arcMoveTo(outerRect, angle);
 341     innerPath.arcTo(innerRect, angle, sweepLength);
 342     outerPath.arcTo(outerRect, angle, sweepLength);
 343
 344     Q_ASSERT(qAbs(sweepLength) <= 90);
 345     Q_ASSERT(innerPath.elementCount() == 4 && outerPath.elementCount() == 4);
 346
 347     const KCubicBezier inner(innerPath.elementAt(0), innerPath.elementAt(1), innerPath.elementAt(2), innerPath.elementAt(3));
 348     const KCubicBezier outer(outerPath.elementAt(0), outerPath.elementAt(1), outerPath.elementAt(2), outerPath.elementAt(3));
 349
 350     qreal a = std::fmod(angle, qreal(360.0));
 351     if (a < 0)
 352         a += 360.0;
 353
 354     // Figure out which border we're starting from
 355     qreal initialWidth;
 356     if ((a >= 0 && a < 90) || (a >= 180 && a < 270))
 357         initialWidth = sweepLength > 0 ? hlw : vlw;
 358     else
 359         initialWidth = sweepLength > 0 ? vlw : hlw;
 360
 361     const qreal finalWidth = QLineF(outer.p3(), inner.p3()).length();
 362     const qreal dashAspect  = (pattern[0] / initialWidth);
 363     const qreal spaceAspect = (pattern[1] / initialWidth);
 364     const qreal length = inner.length();
 365
 366     QPainterPath path;
 367     qreal innerStart = 0, outerStart = 0;
 368     qreal pos = 0;
 369     bool dash = true;
 370
 371     qreal offset = fmod(patternOffset, pattern[0] + pattern[1]);
 372     if (offset < 0) {
 373         offset += pattern[0] + pattern[1];
 374     }
 375
 376     if (offset > 0) {
 377         if (offset >= pattern[0]) {
 378             offset -= pattern[0];
 379             dash = false;
 380         } else
 381             dash = true;
 382         pos = -offset;
 383     }
 384
 385     while (innerStart < 1) {
 386         const qreal lineWidth = QLineF(outer.pointAt(outerStart), inner.pointAt(innerStart)).length();
 387         const qreal length = lineWidth * (dash ? dashAspect : spaceAspect);
 388         pos += length;
 389
 390         if (pos > 0) {
 391             const qreal innerEnd = inner.tAtLength(pos);
 392             const QLineF normal = inner.normalVectorAt(innerEnd);
 393             const qreal outerEnd = outer.tAtIntersection(normal);
 394
 395             if (dash) {
 396                 // The outer and inner curves of the dash
 397                 const KCubicBezier a = outer.section(outerStart, outerEnd);
 398                 const KCubicBezier b = inner.section(innerStart, innerEnd);
 399
 400                 // Add the dash to the path
 401                 path.moveTo(a.p0());
 402                 path.cubicTo(a.p1(), a.p2(), a.p3());
 403                 path.lineTo(b.p3());
 404                 path.cubicTo(b.p2(), b.p1(), b.p0());
 405                 path.closeSubpath();
 406             }
 407
 408             innerStart = innerEnd;
 409             outerStart = outerEnd;
 410         }
 411
 412         dash = !dash;
 413     }
 414
 415     if (nextOffset) {
 416         const qreal remainder = pos - length;
 417
 418         if (dash)
 419             *nextOffset = -remainder;
 420         else
 421             *nextOffset = (pattern[0] / initialWidth) * finalWidth - remainder;
 422    }
 423
 424     return path;
 425 }
 426
 427 } // namespace khtml
 428