KHtml

borderarcstroker.cpp
1 /*
2  * Copyright (C) 2008-2009 Fredrik Höglund <[email protected]>
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 namespace khtml
40 {
41 
42 // This is a helper class used by BorderArcStroker
43 class KCubicBezier
44 {
45 public:
46  KCubicBezier() {}
47  KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3);
48 
49  void split(KCubicBezier *a, KCubicBezier *b, qreal t = .5) const;
50  KCubicBezier section(qreal t1, qreal t2) const;
51  KCubicBezier leftSection(qreal t) const;
52  KCubicBezier rightSection(qreal t) const;
53  KCubicBezier derivative() const;
54  QPointF pointAt(qreal t) const;
55  QPointF deltaAt(qreal t) const;
56  QLineF normalVectorAt(qreal t) const;
57  qreal slopeAt(qreal t) const;
58  qreal tAtLength(qreal l) const;
59  qreal tAtIntersection(const QLineF &line) const;
60  QLineF chord() const;
61  qreal length() const;
62  qreal convexHullLength() const;
63 
64  QPointF p0() const
65  {
66  return QPointF(x0, y0);
67  }
68  QPointF p1() const
69  {
70  return QPointF(x1, y1);
71  }
72  QPointF p2() const
73  {
74  return QPointF(x2, y2);
75  }
76  QPointF p3() const
77  {
78  return QPointF(x3, y3);
79  }
80 
81 public:
82  qreal x0, y0, x1, y1, x2, y2, x3, y3;
83 };
84 
85 KCubicBezier::KCubicBezier(const QPointF &p0, const QPointF &p1, const QPointF &p2, const QPointF &p3)
86 {
87  x0 = p0.x();
88  y0 = p0.y();
89  x1 = p1.x();
90  y1 = p1.y();
91  x2 = p2.x();
92  y2 = p2.y();
93  x3 = p3.x();
94  y3 = p3.y();
95 }
96 
97 // Splits the curve at t, using the de Casteljau algorithm.
98 // This function is not atomic, so do not pass a pointer to the curve being split.
99 void KCubicBezier::split(KCubicBezier *a, KCubicBezier *b, qreal t) const
100 {
101  a->x0 = x0;
102  a->y0 = y0;
103 
104  b->x3 = x3;
105  b->y3 = y3;
106 
107  a->x1 = x0 + (x1 - x0) * t;
108  a->y1 = y0 + (y1 - y0) * t;
109 
110  b->x2 = x2 + (x3 - x2) * t;
111  b->y2 = y2 + (y3 - y2) * t;
112 
113  // The point on the line (p1, p2).
114  const qreal x = x1 + (x2 - x1) * t;
115  const qreal y = y1 + (y2 - y1) * t;
116 
117  a->x2 = a->x1 + (x - a->x1) * t;
118  a->y2 = a->y1 + (y - a->y1) * t;
119 
120  b->x1 = x + (b->x2 - x) * t;
121  b->y1 = y + (b->y2 - y) * t;
122 
123  a->x3 = b->x0 = a->x2 + (b->x1 - a->x2) * t;
124  a->y3 = b->y0 = a->y2 + (b->y1 - a->y2) * t;
125 }
126 
127 // Returns a new bezier curve that is the interval between t1 and t2 in this curve
128 KCubicBezier KCubicBezier::section(qreal t1, qreal t2) const
129 {
130  return leftSection(t2).rightSection(t1 / t2);
131 }
132 
133 // Returns a new bezier curve that is the section of this curve left of t
134 KCubicBezier KCubicBezier::leftSection(qreal t) const
135 {
136  KCubicBezier left, right;
137  split(&left, &right, t);
138  return left;
139 }
140 
141 // Returns a new bezier curve that is the section of this curve right of t
142 KCubicBezier KCubicBezier::rightSection(qreal t) const
143 {
144  KCubicBezier left, right;
145  split(&left, &right, t);
146  return right;
147 }
148 
149 // Returns the point at t
150 QPointF KCubicBezier::pointAt(qreal t) const
151 {
152  const qreal m_t = 1 - t;
153  const qreal m_t2 = m_t * m_t;
154  const qreal m_t3 = m_t2 * m_t;
155  const qreal t2 = t * t;
156  const qreal t3 = t2 * t;
157 
158  const qreal x = m_t3 * x0 + 3 * t * m_t2 * x1 + 3 * t2 * m_t * x2 + t3 * x3;
159  const qreal y = m_t3 * y0 + 3 * t * m_t2 * y1 + 3 * t2 * m_t * y2 + t3 * y3;
160 
161  return QPointF(x, y);
162 }
163 
164 // Returns the delta at t, i.e. the first derivative of the cubic equation at t.
165 QPointF KCubicBezier::deltaAt(qreal t) const
166 {
167  const qreal m_t = 1 - t;
168  const qreal m_t2 = m_t * m_t;
169  const qreal t2 = t * t;
170 
171  const qreal dx = 3 * (x1 - x0) * m_t2 + 3 * (x2 - x1) * 2 * t * m_t + 3 * (x3 - x2) * t2;
172  const qreal dy = 3 * (y1 - y0) * m_t2 + 3 * (y2 - y1) * 2 * t * m_t + 3 * (y3 - y2) * t2;
173 
174  return QPointF(dx, dy);
175 }
176 
177 // Returns the slope at t (dy / dx)
178 qreal KCubicBezier::slopeAt(qreal t) const
179 {
180  const QPointF delta = deltaAt(t);
181  return qFuzzyIsNull(delta.x()) ?
182  (delta.y() < 0 ? -1 : 1) : delta.y() / delta.x();
183 }
184 
185 // Returns the normal vector at t
186 QLineF KCubicBezier::normalVectorAt(qreal t) const
187 {
188  const QPointF point = pointAt(t);
189  const QPointF delta = deltaAt(t);
190 
191  return QLineF(point, point + delta).normalVector();
192 }
193 
194 // Returns a curve that is the first derivative of this curve.
195 // The first derivative of a cubic bezier curve is a quadratic bezier curve,
196 // but this function elevates it to a cubic curve.
197 KCubicBezier KCubicBezier::derivative() const
198 {
199  KCubicBezier c;
200 
201  c.x0 = 3 * (x1 - x0);
202  c.x1 = x1 - x0 + 2 * (x2 - x1);
203  c.x2 = 2 * (x2 - x1) + x3 - x2;
204  c.x3 = 3 * (x3 - x2);
205 
206  c.y0 = 3 * (y1 - y0);
207  c.y1 = y1 - y0 + 2 * (y2 - y1);
208  c.y2 = 2 * (y2 - y1) + y3 - y2;
209  c.y3 = 3 * (y3 - y2);
210 
211  return c;
212 }
213 
214 // Returns the sum of the lengths of the lines connecting the control points
215 qreal KCubicBezier::convexHullLength() const
216 {
217 #ifdef HAVE_SSE
218  K_ALIGN(16) float vals[4];
219 
220  __m128 m1, m2;
221  m1 = _mm_set_ps(0, x1 - x0, x2 - x1, x3 - x2);
222  m2 = _mm_set_ps(0, y1 - y0, y2 - y1, y3 - y2);
223  m1 = _mm_add_ps(_mm_mul_ps(m1, m1), _mm_mul_ps(m2, m2));
224  _mm_store_ps(vals, _mm_sqrt_ps(m1));
225 
226  return vals[0] + vals[1] + vals[2];
227 #else
228  return QLineF(x0, y0, x1, y1).length() + QLineF(x1, y1, x2, y2).length() + QLineF(x2, y2, x3, y3).length();
229 #endif
230 }
231 
232 // Returns the chord, i.e. the line that connects the two endpoints of the curve
233 QLineF KCubicBezier::chord() const
234 {
235  return QLineF(x0, y0, x3, y3);
236 }
237 
238 // Returns the arc length of the bezier curve, computed by recursively subdividing the
239 // curve until the difference between the length of the convex hull of the section
240 // and its chord is less than .01 device units.
241 qreal KCubicBezier::length() const
242 {
243  const qreal error = .01;
244  const qreal len = convexHullLength();
245 
246  if ((len - chord().length()) > error) {
247  KCubicBezier left, right;
248  split(&left, &right);
249  return left.length() + right.length();
250  }
251 
252  return len;
253 }
254 
255 // Returns the value for the t parameter that corresponds to the point
256 // l device units from the starting point of the curve.
257 qreal KCubicBezier::tAtLength(qreal l) const
258 {
259  const qreal error = 0.1;
260 
261  if (l <= 0) {
262  return 0;
263  }
264 
265  qreal len = length();
266 
267  if (l > len || qFuzzyCompare(l + 1.0, len + 1.0)) {
268  return 1;
269  }
270 
271  qreal upperT = 1;
272  qreal lowerT = 0;
273 
274  while (1) {
275  const qreal t = lowerT + (upperT - lowerT) / 2;
276  const qreal len = leftSection(t).length();
277 
278  if (qAbs(l - len) < error) {
279  return t;
280  }
281 
282  if (l > len) {
283  lowerT = t;
284  } else {
285  upperT = t;
286  }
287  }
288 }
289 
290 // Returns the value of t at the point where the given line intersects
291 // the bezier curve. The line is treated as an infinitely long line.
292 // Note that this implementation assumes that there is a single point of
293 // intersection, that both control points are on the same side of
294 // the curve, and that the curve is not self intersecting.
295 qreal KCubicBezier::tAtIntersection(const QLineF &line) const
296 {
297  const qreal error = 0.1;
298 
299  // Extend the line to make it a reasonable approximation of an infinitely long line
300  const qreal len = line.length();
301  const QLineF l = QLineF(line.pointAt(1.0 / len * -1e10), line.pointAt(1.0 / len * 1e10));
302 
303  // Check if the line intersects the curve at all
304  if (chord().intersect(l, nullptr) != QLineF::BoundedIntersection) {
305  return 1;
306  }
307 
308  qreal upperT = 1;
309  qreal lowerT = 0;
310 
311  KCubicBezier c = *this;
312 
313  while (1) {
314  const qreal t = lowerT + (upperT - lowerT) / 2;
315  if (c.length() < error) {
316  return t;
317  }
318 
319  KCubicBezier left, right;
320  c.split(&left, &right);
321 
322  // If the line intersects the left section
323  if (left.chord().intersect(l, nullptr) == QLineF::BoundedIntersection) {
324  upperT = t;
325  c = left;
326  } else {
327  lowerT = t;
328  c = right;
329  }
330  }
331 }
332 
333 // ----------------------------------------------------------------------------
334 
335 BorderArcStroker::BorderArcStroker()
336 {
337 }
338 
339 BorderArcStroker::~BorderArcStroker()
340 {
341 }
342 
343 QPainterPath BorderArcStroker::createStroke(qreal *nextOffset) const
344 {
345  const QRectF outerRect = rect;
346  const QRectF innerRect = rect.adjusted(hlw, vlw, -hlw, -vlw);
347 
348  // Avoid hitting the assert below if the radius is smaller than the border width
349  if (!outerRect.isValid() || !innerRect.isValid()) {
350  return QPainterPath();
351  }
352 
353  QPainterPath innerPath, outerPath;
354  innerPath.arcMoveTo(innerRect, angle);
355  outerPath.arcMoveTo(outerRect, angle);
356  innerPath.arcTo(innerRect, angle, sweepLength);
357  outerPath.arcTo(outerRect, angle, sweepLength);
358 
359  Q_ASSERT(qAbs(sweepLength) <= 90);
360  Q_ASSERT(innerPath.elementCount() == 4 && outerPath.elementCount() == 4);
361 
362  const KCubicBezier inner(innerPath.elementAt(0), innerPath.elementAt(1), innerPath.elementAt(2), innerPath.elementAt(3));
363  const KCubicBezier outer(outerPath.elementAt(0), outerPath.elementAt(1), outerPath.elementAt(2), outerPath.elementAt(3));
364 
365  qreal a = std::fmod(angle, qreal(360.0));
366  if (a < 0) {
367  a += 360.0;
368  }
369 
370  // Figure out which border we're starting from
371  qreal initialWidth;
372  if ((a >= 0 && a < 90) || (a >= 180 && a < 270)) {
373  initialWidth = sweepLength > 0 ? hlw : vlw;
374  } else {
375  initialWidth = sweepLength > 0 ? vlw : hlw;
376  }
377 
378  const qreal finalWidth = qMax(qreal(0.1), QLineF(outer.p3(), inner.p3()).length());
379  const qreal dashAspect = (pattern[0] / initialWidth);
380  const qreal spaceAspect = (pattern[1] / initialWidth);
381  const qreal length = inner.length();
382 
383  QPainterPath path;
384  qreal innerStart = 0, outerStart = 0;
385  qreal pos = 0;
386  bool dash = true;
387 
388  qreal offset = fmod(patternOffset, pattern[0] + pattern[1]);
389  if (offset < 0) {
390  offset += pattern[0] + pattern[1];
391  }
392 
393  if (offset > 0) {
394  if (offset >= pattern[0]) {
395  offset -= pattern[0];
396  dash = false;
397  } else {
398  dash = true;
399  }
400  pos = -offset;
401  }
402 
403  while (innerStart < 1) {
404  const qreal lineWidth = QLineF(outer.pointAt(outerStart), inner.pointAt(innerStart)).length();
405  const qreal length = lineWidth * (dash ? dashAspect : spaceAspect);
406  pos += length;
407 
408  if (pos > 0) {
409  const qreal innerEnd = inner.tAtLength(pos);
410  const QLineF normal = inner.normalVectorAt(innerEnd);
411  const qreal outerEnd = outer.tAtIntersection(normal);
412 
413  if (dash) {
414  // The outer and inner curves of the dash
415  const KCubicBezier a = outer.section(outerStart, outerEnd);
416  const KCubicBezier b = inner.section(innerStart, innerEnd);
417 
418  // Add the dash to the path
419  path.moveTo(a.p0());
420  path.cubicTo(a.p1(), a.p2(), a.p3());
421  path.lineTo(b.p3());
422  path.cubicTo(b.p2(), b.p1(), b.p0());
423  path.closeSubpath();
424  }
425 
426  innerStart = innerEnd;
427  outerStart = outerEnd;
428  }
429 
430  dash = !dash;
431  }
432 
433  if (nextOffset) {
434  const qreal remainder = pos - length;
435 
436  if (dash) {
437  *nextOffset = -remainder;
438  } else {
439  *nextOffset = (pattern[0] / initialWidth) * finalWidth - remainder;
440  }
441  }
442 
443  return path;
444 }
445 
446 } // namespace khtml
447 
BoundedIntersection
void closeSubpath()
This file is part of the HTML rendering engine for KDE.
QTextStream & right(QTextStream &stream)
void cubicTo(const QPointF &c1, const QPointF &c2, const QPointF &endPoint)
QPainterPath::Element elementAt(int index) const const
void moveTo(const QPointF &point)
int elementCount() const const
QTextStream & left(QTextStream &stream)
qreal length() const const
qreal x() const const
qreal y() const const
QString pattern(Mode mode=Reading)
QLineF normalVector() const const
void lineTo(const QPointF &endPoint)
void arcMoveTo(const QRectF &rectangle, qreal angle)
void error(QWidget *parent, const QString &text, const QString &caption=QString(), Options options=Notify)
bool isValid() const const
QPointF pointAt(qreal t) const const
QRectF adjusted(qreal dx1, qreal dy1, qreal dx2, qreal dy2) const const
void arcTo(const QRectF &rectangle, qreal startAngle, qreal sweepLength)
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Tue Oct 26 2021 22:47:58 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.