2 * Copyright (c) 2005 Casper Boemann <cbr@boemann.dk>
3 * Copyright (c) 2009 Dmitry Kazakov <dimula73@gmail.com>
4 * Copyright (c) 2010 Cyrille Berger <cberger@cberger.net>
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 #include "kis_cubic_curve.h"
25 #include <QSharedData>
26 #include <QStringList>
29 class KisTridiagonalSystem
33 * |b0 c0 0 0 0| |x0| |f0|
34 * |a0 b1 c1 0 0| |x1| |f1|
35 * |0 a1 b2 c2 0|*|x2|=|f2|
36 * |0 0 a2 b3 c3| |x3| |f3|
37 * |0 0 0 a3 b4| |x4| |f4|
43 * @return - vector that is storing x[]
46 QVector<T> calculate(QList<T> &a,
57 Q_ASSERT(a.size() == size - 1 &&
58 c.size() == size - 1 &&
64 * Check for special case when
65 * order of the matrix is equal to 1
80 alpha[1] = -c[0] / b[0];
81 beta[1] = f[0] / b[0];
83 for (i = 1; i < size - 1; i++) {
85 (a[i-1] * alpha[i] + b[i]);
87 beta[i+1] = (f[i] - a[i-1] * beta[i])
89 (a[i-1] * alpha[i] + b[i]);
92 x.last() = (f.last() - a.last() * beta.last())
94 (b.last() + a.last() * alpha.last());
96 for (i = size - 2; i >= 0; i--)
97 x[i] = alpha[i+1] * x[i+1] + beta[i+1];
103 template <typename T_point, typename T>
109 * 1/2 * c[i] * (x-x[i])^2 +
110 * 1/6 * d[i] * (x-x[i])^3
129 KisCubicSpline(const QList<T_point> &a) {
134 * Create new spline and precalculate some values
137 * @a - base points of the spline
139 void createSpline(const QList<T_point> &a) {
140 int intervals = m_intervals = a.size() - 1;
142 m_begin = a.first().x();
143 m_end = a.last().x();
146 m_b.resize(intervals);
148 m_d.resize(intervals);
149 m_h.resize(intervals);
151 for (i = 0; i < intervals; i++) {
152 m_h[i] = a[i+1].x() - a[i].x();
153 m_a.append(a[i].y());
155 m_a.append(a.last().y());
160 QList<T> tri_a; /* equals to @tri_c */
162 for (i = 0; i < intervals - 1; i++) {
163 tri_b.append(2.*(m_h[i] + m_h[i+1]));
165 tri_f.append(6.*((m_a[i+2] - m_a[i+1]) / m_h[i+1] - (m_a[i+1] - m_a[i]) / m_h[i]));
167 for (i = 1; i < intervals - 1; i++)
168 tri_a.append(m_h[i]);
171 KisTridiagonalSystem<T> tridia;
172 m_c = tridia.calculate(tri_a, tri_b, tri_a, tri_f);
177 for (i = 0; i < intervals; i++)
178 m_d[i] = (m_c[i+1] - m_c[i]) / m_h[i];
180 for (i = 0; i < intervals; i++)
181 m_b[i] = -0.5 * (m_c[i] * m_h[i]) - (1 / 6.0) * (m_d[i] * m_h[i] * m_h[i]) + (m_a[i+1] - m_a[i]) / m_h[i];
185 * Get value of precalculated spline in the point @x
187 T getValue(T x) const {
189 int i = findRegion(x, x0);
190 /* TODO: check for asm equivalent */
193 0.5 * m_c[i] *(x - x0) *(x - x0) +
194 (1 / 6.0)* m_d[i] *(x - x0) *(x - x0) *(x - x0);
208 * findRegion - Searches for the region containing @x
209 * @x0 - out parameter, containing beginning of the region
210 * @return - index of the region
212 int findRegion(T x, T &x0) const {
215 for (i = 0; i < m_intervals; i++) {
216 if (x >= x0 && x < x0 + m_h[i])
221 x0 -= m_h[m_intervals-1];
222 return m_intervals - 1;
225 qDebug("X value: %f\n", x);
226 qDebug("m_begin: %f\n", m_begin);
227 qDebug("m_end : %f\n", m_end);
228 Q_ASSERT_X(0, "findRegion", "X value is outside regions");
229 /* **never reached** */
234 static bool pointLessThan(const QPointF &a, const QPointF &b)
236 return a.x() < b.x();
239 struct KisCubicCurve::Data : public QSharedData {
243 Data(const Data& data) : QSharedData() {
245 points = data.points;
249 validU16Transfer = false;
250 validFTransfer = false;
254 mutable KisCubicSpline<QPointF, qreal> spline;
255 QList<QPointF> points;
256 mutable bool validSpline;
257 mutable QVector<quint16> u16Transfer;
258 mutable bool validU16Transfer;
259 mutable QVector<qreal> fTransfer;
260 mutable bool validFTransfer;
263 qreal value(qreal x);
265 template<typename _T_, typename _T2_>
266 void updateTransfer(QVector<_T_>* transfer, bool& valid, _T2_ min, _T2_ max, int size);
269 void KisCubicCurve::Data::updateSpline()
271 if (validSpline) return;
273 spline.createSpline(points);
276 void KisCubicCurve::Data::invalidate()
279 validFTransfer = false;
280 validU16Transfer = false;
283 void KisCubicCurve::Data::keepSorted()
285 qSort(points.begin(), points.end(), pointLessThan);
288 qreal KisCubicCurve::Data::value(qreal x)
291 /* Automatically extend non-existing parts of the curve
292 * (e.g. before the first point) and cut off big y-values
294 x = qBound(spline.begin(), x, spline.end());
295 qreal y = spline.getValue(x);
296 return qBound((qreal)0.0, y, (qreal)1.0);
299 template<typename _T_, typename _T2_>
300 void KisCubicCurve::Data::updateTransfer(QVector<_T_>* transfer, bool& valid, _T2_ min, _T2_ max, int size)
302 if (!valid || transfer->size() != size) {
303 if (transfer->size() != size) {
304 transfer->resize(size);
306 qreal end = 1.0 / (size - 1);
307 for (int i = 0; i < size; ++i) {
308 /* Direct uncached version */
309 _T2_ val = value(i * end) * max;
310 val = qBound(min, val, max);
311 (*transfer)[i] = val;
317 struct KisCubicCurve::Private {
318 QSharedDataPointer<Data> data;
321 KisCubicCurve::KisCubicCurve() : d(new Private)
327 d->data->points.append(p);
330 d->data->points.append(p);
333 KisCubicCurve::KisCubicCurve(const QList<QPointF>& points) : d(new Private)
336 d->data->points = points;
337 d->data->keepSorted();
340 KisCubicCurve::KisCubicCurve(const KisCubicCurve& curve) : d(new Private(*curve.d))
344 KisCubicCurve::~KisCubicCurve()
349 KisCubicCurve& KisCubicCurve::operator=(const KisCubicCurve & curve)
355 bool KisCubicCurve::operator==(const KisCubicCurve& curve) const
357 if (d->data == curve.d->data) return true;
358 return d->data->points == curve.d->data->points;
361 qreal KisCubicCurve::value(qreal x) const
363 return d->data->value(x);
366 QList<QPointF> KisCubicCurve::points() const
368 return d->data->points;
371 void KisCubicCurve::setPoints(const QList<QPointF>& points)
374 d->data->points = points;
375 d->data->invalidate();
378 void KisCubicCurve::setPoint(int idx, const QPointF& point)
381 d->data->points[idx] = point;
382 d->data->keepSorted();
383 d->data->invalidate();
386 int KisCubicCurve::addPoint(const QPointF& point)
389 d->data->points.append(point);
390 d->data->keepSorted();
391 d->data->invalidate();
392 return d->data->points.indexOf(point);
395 void KisCubicCurve::removePoint(int idx)
398 d->data->points.removeAt(idx);
399 d->data->invalidate();
402 QString KisCubicCurve::toString() const
405 foreach(const QPointF & pair, d->data->points) {
406 sCurve += QString::number(pair.x());
408 sCurve += QString::number(pair.y());
414 void KisCubicCurve::fromString(const QString& string)
416 QStringList data = string.split(';');
418 QList<QPointF> points;
420 foreach(const QString & pair, data) {
421 if (pair.indexOf(',') > -1) {
423 p.rx() = pair.section(',', 0, 0).toDouble();
424 p.ry() = pair.section(',', 1, 1).toDouble();
431 QVector<quint16> KisCubicCurve::uint16Transfer(int size) const
433 d->data->updateTransfer<quint16, int>(&d->data->u16Transfer, d->data->validU16Transfer, 0x0, 0xFFFF, size);
434 return d->data->u16Transfer;
437 QVector<qreal> KisCubicCurve::floatTransfer(int size) const
439 d->data->updateTransfer<qreal, qreal>(&d->data->fTransfer, d->data->validFTransfer, 0.0, 1.0, size);
440 return d->data->fTransfer;