]> git.sesse.net Git - kdenlive/blob - src/beziercurve/cubicbezierspline.cpp
Bezier Spline:
[kdenlive] / src / beziercurve / cubicbezierspline.cpp
1 /***************************************************************************
2  *   Copyright (C) 2010 by Till Theato (root@ttill.de)                     *
3  *   This file is part of Kdenlive (www.kdenlive.org).                     *
4  *                                                                         *
5  *   Kdenlive is free software: you can redistribute it and/or modify      *
6  *   it under the terms of the GNU General Public License as published by  *
7  *   the Free Software Foundation, either version 2 of the License, or     *
8  *   (at your option) any later version.                                   *
9  *                                                                         *
10  *   Kdenlive is distributed in the hope that it will be useful,           *
11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
13  *   GNU General Public License for more details.                          *
14  *                                                                         *
15  *   You should have received a copy of the GNU General Public License     *
16  *   along with Kdenlive.  If not, see <http://www.gnu.org/licenses/>.     *
17  ***************************************************************************/
18
19 #include "cubicbezierspline.h"
20
21 #include <KDebug>
22
23 /** @brief For sorting a Bezier spline. Whether a is before b. */
24 static bool pointLessThan(const BPoint &a, const BPoint &b)
25 {
26     return a.p.x() < b.p.x();
27 }
28
29 CubicBezierSpline::CubicBezierSpline(QObject* parent) :
30         QObject(parent),
31         m_validSpline(false),
32         m_precision(100)
33 {
34     BPoint start;
35     start.p.setX(0);
36     start.p.setY(0);
37     start.h1.setX(0);
38     start.h1.setY(0);
39     start.h2.setX(0.1);
40     start.h2.setY(0.1);
41     m_points.append(start);
42
43     BPoint end;
44     end.p.setX(1);
45     end.p.setY(1);
46     end.h1.setX(0.9);
47     end.h1.setY(0.9);
48     end.h2.setX(1);
49     end.h2.setY(1);
50     m_points.append(end);
51 }
52
53 CubicBezierSpline::CubicBezierSpline(const CubicBezierSpline& spline, QObject* parent) :
54         QObject(parent)
55 {
56     m_precision = spline.m_precision;
57     m_points = spline.m_points;
58     m_validSpline = false;
59 }
60
61 CubicBezierSpline& CubicBezierSpline::operator=(const CubicBezierSpline& spline)
62 {
63     m_precision = spline.m_precision;
64     m_points = spline.m_points;
65     return *this;
66 }
67
68 void CubicBezierSpline::fromString(const QString& spline)
69 {
70     m_points.clear();
71     m_validSpline = false;
72
73     QStringList bpoints = spline.split('|');
74     foreach(const QString &bpoint, bpoints) {
75         QStringList points = bpoint.split('#');
76         QList <QPointF> values;
77         foreach(const QString &point, points) {
78             QStringList xy = point.split(';');
79             if (xy.count() == 2)
80                 values.append(QPointF(xy.at(0).toDouble(), xy.at(1).toDouble()));
81         }
82         if (values.count() == 3) {
83             BPoint bp;
84             bp.h1 = values.at(0);
85             bp.p  = values.at(1);
86             bp.h2 = values.at(2);
87             m_points.append(bp);
88         }
89     }
90
91     keepSorted();
92     validatePoints();
93 }
94
95 QString CubicBezierSpline::toString() const
96 {
97     QStringList spline;
98     foreach(const BPoint &p, m_points) {
99         spline << (QString::number(p.h1.x()) + ";" + QString::number(p.h1.y())
100                         + "#" + QString::number(p.p.x())  + ";" + QString::number(p.p.y())
101                         + "#" + QString::number(p.h2.x()) + ";" + QString::number(p.h2.y()));
102     }
103     return spline.join("|");
104 }
105
106 int CubicBezierSpline::setPoint(int ix, const BPoint& point)
107 {
108     m_points[ix] = point;
109     keepSorted();
110     validatePoints();
111     m_validSpline = false;
112     return indexOf(point); // in case it changed
113 }
114
115 QList <BPoint> CubicBezierSpline::points()
116 {
117     return m_points;
118 }
119
120 void CubicBezierSpline::removePoint(int ix)
121 {
122     m_points.removeAt(ix);
123     m_validSpline = false;
124 }
125
126 int CubicBezierSpline::addPoint(const BPoint& point)
127 {
128     m_points.append(point);
129     keepSorted();
130     validatePoints();
131     m_validSpline = false;
132     return indexOf(point);
133 }
134
135 void CubicBezierSpline::setPrecision(int pre)
136 {
137     if (pre != m_precision) {
138         m_precision = pre;
139         m_validSpline = false;
140     }
141 }
142
143 int CubicBezierSpline::getPrecision()
144 {
145     return m_precision;
146 }
147
148 qreal CubicBezierSpline::value(qreal x, bool cont)
149 {
150     update();
151
152     if (!cont)
153         m_i = m_spline.constBegin();
154     if (m_i != m_spline.constBegin())
155         --m_i;
156
157     double diff = qAbs(x - m_i.key());
158     double y = m_i.value();
159     while (m_i != m_spline.constEnd()) {
160         if (qAbs(x - m_i.key()) > diff)
161             break;
162
163         diff = qAbs(x - m_i.key());
164         y = m_i.value();
165         ++m_i;
166     }
167     return qBound((qreal)0.0, y, (qreal)1.0);
168 }
169
170 void CubicBezierSpline::validatePoints()
171 {
172     BPoint p1, p2;
173     for (int i = 0; i < m_points.count() - 1; ++i) {
174         p1 = m_points.at(i);
175         p2 = m_points.at(i+1);
176         p1.h2.setX(qBound(p1.p.x(), p1.h2.x(), p2.p.x()));
177         p2.h1.setX(qBound(p1.p.x(), p2.h1.x(), p2.p.x()));
178         m_points[i] = p1;
179         m_points[i+1] = p2;
180     }
181 }
182
183 void CubicBezierSpline::keepSorted()
184 {
185     qSort(m_points.begin(), m_points.end(), pointLessThan);
186 }
187
188 QPointF CubicBezierSpline::point(double t, const QList< QPointF >& points)
189 {
190     // coefficients from Bernstein basis polynomial of degree 3
191     double c1 = (1-t) * (1-t) * (1-t);
192     double c2 = 3 * t * (1-t) * (1-t);
193     double c3 = 3 * t * t * (1-t);
194     double c4 = t * t * t;
195     
196     return QPointF(points[0].x()*c1 + points[1].x()*c2 + points[2].x()*c3 + points[3].x()*c4,
197                    points[0].y()*c1 + points[1].y()*c2 + points[2].y()*c3 + points[3].y()*c4);
198 }
199
200 void CubicBezierSpline::update()
201 {
202     if (m_validSpline)
203         return;
204
205     m_validSpline = true;
206     m_spline.clear();
207
208     QList <QPointF> points;
209     QPointF p;
210     for (int i = 0; i < m_points.count() - 1; ++i) {
211         points.clear();
212         points << m_points.at(i).p
213                 << m_points.at(i).h2
214                 << m_points.at(i+1).h1
215                 << m_points.at(i+1).p;
216
217         int numberOfValues = (int)((points[3].x() - points[0].x()) * m_precision * 5);
218         if (numberOfValues == 0)
219             numberOfValues = 1;
220         double step = 1 / (double)numberOfValues;
221         double t = 0;
222         while (t <= 1) {
223             p = point(t, points);
224             m_spline.insert(p.x(), p.y());
225             t += step;
226         }
227     }
228 }
229
230 int CubicBezierSpline::indexOf(const BPoint& p)
231 {
232     if (m_points.indexOf(p) == -1) {
233         // point changed during validation process
234         for (int i = 0; i < m_points.count(); ++i) {
235             // this condition should be sufficient, too
236             if (m_points.at(i).p == p.p)
237                 return i;
238         }
239     } else {
240         return m_points.indexOf(p);
241     }
242     return -1;
243 }
244
245 #include "cubicbezierspline.moc"