1 /*
2 Copyright (C) 2005-2006 Remon Sijrier
3
4 Original version from Ardour curve.cc, modified
5 in order to fit Traverso's lockless design
6
7 Copyright (C) 2001-2003 Paul Davis
8
9 Contains ideas derived from "Constrained Cubic Spline Interpolation"
10 by CJC Kruger (www.korf.co.uk/spline.pdf).
11
12 This file is part of Traverso
13
14 Traverso is free software; you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation; either version 2 of the License, or
17 (at your option) any later version.
18
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
27
28 */
29
30 #include "Curve.h"
31 #include <cmath>
32
33
34 #include "Sheet.h"
35 #include "Track.h"
36 #include "InputEngine.h"
37 #include "Utils.h"
38 #include <QStringList>
39 #include <QThread>
40 #include <AddRemove.h>
41 #include <Command.h>
42 #include <CommandGroup.h>
43 #include "Mixer.h"
44 #include "Information.h"
45
46 // Always put me below _all_ includes, this is needed
47 // in case we run with memory leak detection enabled!
48 #include "Debugger.h"
49
50 using namespace std;
51
52
53 class MoveNode : public Command
54 {
55
56 public:
57 MoveNode(Curve* curve, CurveNode* node, double when, double val, const QString& des);
58
59 int prepare_actions();
60 int do_action();
61 int undo_action();
62
63 private :
64 CurveNode* m_node;
65 double m_origWhen;
66 double m_origVal;
67 double m_newWhen;
68 double m_newVal;
69 };
70
71
MoveNode(Curve * curve,CurveNode * node,double when,double val,const QString & des)72 MoveNode::MoveNode(Curve* curve, CurveNode* node, double when, double val, const QString& des)
73 : Command(curve, des)
74 {
75 m_node = node;
76 m_origWhen = m_node->get_when();
77 m_origVal = m_node->get_value();
78 m_newWhen = when;
79 m_newVal = val;
80 }
81
prepare_actions()82 int MoveNode::prepare_actions()
83 {
84 return 1;
85 }
86
do_action()87 int MoveNode::do_action()
88 {
89 m_node->set_when_and_value(m_newWhen, m_newVal);
90 return 1;
91 }
92
undo_action()93 int MoveNode::undo_action()
94 {
95 m_node->set_when_and_value(m_origWhen, m_origVal);
96 return 1;
97 }
98
99
100
Curve(ContextItem * parent)101 Curve::Curve(ContextItem* parent)
102 : ContextItem(parent)
103 {
104 PENTERCONS;
105 m_id = create_id();
106 init();
107 }
108
Curve(ContextItem * parent,const QDomNode node)109 Curve::Curve(ContextItem* parent, const QDomNode node )
110 : ContextItem(parent)
111 {
112 init();
113 set_state(node);
114 }
115
~Curve()116 Curve::~Curve()
117 {
118 APILinkedListNode* node = m_nodes.first();
119 while (node) {
120 CurveNode* q = (CurveNode*)node;
121 node = node->next;
122 delete q;
123 }
124 }
125
init()126 void Curve::init( )
127 {
128 QObject::tr("Curve");
129 QObject::tr("CurveNode");
130 m_changed = true;
131 m_lookup_cache.left = -1;
132 m_defaultValue = 1.0f;
133 m_sheet = 0;
134
135 connect(this, SIGNAL(nodePositionChanged()), this, SLOT(set_changed()));
136 }
137
138
get_state(QDomDocument doc,const QString & name)139 QDomNode Curve::get_state(QDomDocument doc, const QString& name)
140 {
141 PENTER3;
142 QDomElement domNode = doc.createElement(name);
143
144 QStringList nodesList;
145
146 apill_foreach(CurveNode* cn, CurveNode, m_nodes) {
147 nodesList << QString::number(cn->when, 'g', 24).append(",").append(QString::number(cn->value));
148 }
149
150 if (m_nodes.size() == 0) {
151 nodesList << "1," + QString::number(m_defaultValue);
152 }
153
154 domNode.setAttribute("nodes", nodesList.join(";"));
155 domNode.setAttribute("defaulvalue", m_defaultValue);
156 domNode.setAttribute("id", m_id);
157
158
159 return domNode;
160 }
161
set_state(const QDomNode & node)162 int Curve::set_state( const QDomNode & node )
163 {
164 PENTER;
165 QDomElement e = node.toElement();
166
167 QStringList nodesList = e.attribute( "nodes", "" ).split(";");
168 m_defaultValue = e.attribute( "defaulvalue", "1.0" ).toDouble();
169 m_id = e.attribute("id", "0" ).toLongLong();
170 if (m_id == 0) {
171 m_id = create_id();
172 }
173
174 for (int i=0; i<nodesList.size(); ++i) {
175 QStringList whenValueList = nodesList.at(i).split(",");
176 double when = whenValueList.at(0).toDouble();
177 double value = whenValueList.at(1).toDouble();
178 CurveNode* node = new CurveNode(this, when, value);
179 private_add_node(node);
180 }
181
182 return 1;
183 }
184
process(audio_sample_t ** buffer,const TimeRef & startlocation,const TimeRef & endlocation,nframes_t nframes,uint channels,float makeupgain)185 int Curve::process(
186 audio_sample_t** buffer,
187 const TimeRef& startlocation,
188 const TimeRef& endlocation,
189 nframes_t nframes,
190 uint channels,
191 float makeupgain
192 )
193 {
194 // Do nothing if there are no nodes!
195 if (m_nodes.isEmpty()) {
196 return 0;
197 }
198
199 // Check if we are beyond the last node and only apply gain if != 1.0
200 if (endlocation > qint64(get_range())) {
201 float gain = ((CurveNode*)m_nodes.last())->value * makeupgain;
202
203 if (gain == 1.0f) {
204 return 0;
205 }
206
207 for (uint chan=0; chan<channels; ++chan) {
208 Mixer::apply_gain_to_buffer(buffer[chan], nframes, gain);
209 }
210
211 return 1;
212 }
213
214 // Calculate the vector, an apply to the buffer including the makeup gain.
215 get_vector(startlocation.universal_frame(), endlocation.universal_frame(), m_sheet->mixdown, nframes);
216
217 for (uint chan=0; chan<channels; ++chan) {
218 for (nframes_t n = 0; n < nframes; ++n) {
219 buffer[chan][n] *= (m_sheet->mixdown[n] * makeupgain);
220 }
221 }
222
223 return 1;
224 }
225
226
solve()227 void Curve::solve ()
228 {
229 uint32_t npoints;
230
231 if (!m_changed) {
232 printf("Curve::solve, no data change\n");
233 return;
234 }
235
236 if ((npoints = m_nodes.size()) > 2) {
237
238 /* Compute coefficients needed to efficiently compute a constrained spline
239 curve. See "Constrained Cubic Spline Interpolation" by CJC Kruger
240 (www.korf.co.uk/spline.pdf) for more details.
241 */
242
243 double x[npoints];
244 double y[npoints];
245 uint32_t i;
246 QList<CurveNode* >::iterator xx;
247
248 CurveNode* cn;
249 i = 0;
250 for(APILinkedListNode* node = m_nodes.first(); node!=0; node = node->next, ++i) {
251 cn = (CurveNode*)node;
252 x[i] = cn->when;
253 y[i] = cn->value;
254 }
255
256 double lp0, lp1, fpone;
257
258 lp0 =(x[1] - x[0])/(y[1] - y[0]);
259 lp1 = (x[2] - x[1])/(y[2] - y[1]);
260
261 if ( (lp0*lp1) < 0 ) {
262 fpone = 0;
263 } else {
264 fpone = 2 / (lp1 + lp0);
265 }
266
267 double fplast = 0;
268
269 i = 0;
270 for(APILinkedListNode* node = m_nodes.first(); node!=0; node = node->next, ++i) {
271
272 cn = (CurveNode*)node;
273
274 if (cn == 0) {
275 /* qCritical << _("programming error: ")
276 << X_("non-CurvePoint event found in event list for a Curve")
277 << endmsg;*/
278 /*NOTREACHED*/
279 }
280
281 double xdelta; /* gcc is wrong about possible uninitialized use */
282 double xdelta2; /* ditto */
283 double ydelta; /* ditto */
284 double fppL, fppR;
285 double fpi;
286
287 if (i > 0) {
288 xdelta = x[i] - x[i-1];
289 xdelta2 = xdelta * xdelta;
290 ydelta = y[i] - y[i-1];
291 }
292
293 /* compute (constrained) first derivatives */
294
295 if (i == 0) {
296
297 /* first segment */
298
299 fplast = ((3 * (y[1] - y[0]) / (2 * (x[1] - x[0]))) - (fpone * 0.5));
300
301 /* we don't store coefficients for i = 0 */
302
303 continue;
304
305 } else if (i == npoints - 1) {
306
307 /* last segment */
308
309 fpi = ((3 * ydelta) / (2 * xdelta)) - (fplast * 0.5);
310
311 } else {
312
313 /* all other segments */
314
315 double slope_before = ((x[i+1] - x[i]) / (y[i+1] - y[i]));
316 double slope_after = (xdelta / ydelta);
317
318 if ((slope_after * slope_before) < 0.0) {
319 /* slope m_changed sign */
320 fpi = 0.0;
321 } else {
322 fpi = 2 / (slope_before + slope_after);
323 }
324
325 }
326
327 /* compute second derivative for either side of control point `i' */
328 double fractal = ((6 * ydelta) / xdelta2); // anyone knows a better name for it?
329 fppL = (((-2 * (fpi + (2 * fplast))) / (xdelta))) + fractal;
330 fppR = (2 * ((2 * fpi) + fplast) / xdelta) - fractal;
331
332 /* compute polynomial coefficients */
333
334 double b, c, d;
335
336 d = (fppR - fppL) / (6 * xdelta);
337 c = ((x[i] * fppL) - (x[i-1] * fppR))/(2 * xdelta);
338
339 double xim12, xim13;
340 double xi2, xi3;
341
342 xim12 = x[i-1] * x[i-1]; /* "x[i-1] squared" */
343 xim13 = xim12 * x[i-1]; /* "x[i-1] cubed" */
344 xi2 = x[i] * x[i]; /* "x[i] squared" */
345 xi3 = xi2 * x[i]; /* "x[i] cubed" */
346
347 b = (ydelta - (c * (xi2 - xim12)) - (d * (xi3 - xim13))) / xdelta;
348
349 /* store */
350
351 cn->coeff[0] = y[i-1] - (b * x[i-1]) - (c * xim12) - (d * xim13);
352 cn->coeff[1] = b;
353 cn->coeff[2] = c;
354 cn->coeff[3] = d;
355
356 fplast = fpi;
357 }
358 }
359
360 m_changed = false;
361 }
362
363
get_vector(double x0,double x1,float * vec,int32_t veclen)364 void Curve::get_vector (double x0, double x1, float *vec, int32_t veclen)
365 {
366 double rx, dx, lx, hx, max_x, min_x;
367 int32_t i;
368 int32_t original_veclen;
369 int32_t npoints;
370
371 if ((npoints = m_nodes.size()) == 0) {
372 for (i = 0; i < veclen; ++i) {
373 vec[i] = m_defaultValue;
374 }
375 return;
376 }
377
378 /* nodes is now known not to be empty */
379
380 CurveNode* lastnode = (CurveNode*)m_nodes.last();
381 CurveNode* firstnode = (CurveNode*)m_nodes.first();
382
383 max_x = lastnode->when;
384 min_x = firstnode->when;
385
386 lx = max (min_x, x0);
387
388 if (x1 < 0) {
389 x1 = lastnode->when;
390 }
391
392 hx = min (max_x, x1);
393
394
395 original_veclen = veclen;
396
397 if (x0 < min_x) {
398
399 /* fill some beginning section of the array with the
400 initial (used to be default) value
401 */
402
403 double frac = (min_x - x0) / (x1 - x0);
404 int32_t subveclen = (int32_t) floor (veclen * frac);
405
406 subveclen = min (subveclen, veclen);
407
408 for (i = 0; i < subveclen; ++i) {
409 vec[i] = firstnode->value;
410 }
411
412 veclen -= subveclen;
413 vec += subveclen;
414 }
415
416 if (veclen && x1 > max_x) {
417
418 /* fill some end section of the array with the default or final value */
419
420 double frac = (x1 - max_x) / (x1 - x0);
421
422 int32_t subveclen = (int32_t) floor (original_veclen * frac);
423
424 float val;
425
426 subveclen = min (subveclen, veclen);
427
428 val = lastnode->value;
429
430 i = veclen - subveclen;
431
432 for (i = veclen - subveclen; i < veclen; ++i) {
433 vec[i] = val;
434 }
435
436 veclen -= subveclen;
437 }
438
439 if (veclen == 0) {
440 return;
441 }
442
443 if (npoints == 1 ) {
444
445 for (i = 0; i < veclen; ++i) {
446 vec[i] = firstnode->value;
447 }
448 return;
449 }
450
451
452 if (npoints == 2) {
453
454 /* linear interpolation between 2 points */
455
456 /* XXX I'm not sure that this is the right thing to
457 do here. but its not a common case for the envisaged
458 uses.
459 */
460
461 if (veclen > 1) {
462 dx = (hx - lx) / (veclen - 1) ;
463 } else {
464 dx = 0; // not used
465 }
466
467 double slope = (lastnode->value - firstnode->value) /
468 (lastnode->when - firstnode->when );
469 double yfrac = dx*slope;
470
471 vec[0] = firstnode->value + slope * (lx - firstnode->when);
472
473 for (i = 1; i < veclen; ++i) {
474 vec[i] = vec[i-1] + yfrac;
475 }
476
477 return;
478 }
479
480 if (m_changed) {
481 solve ();
482 }
483
484 rx = lx;
485
486 if (veclen > 1) {
487
488 dx = (hx - lx) / veclen;
489
490 for (i = 0; i < veclen; ++i, rx += dx) {
491 vec[i] = multipoint_eval (rx);
492 }
493 }
494 }
495
multipoint_eval(double x)496 double Curve::multipoint_eval(double x)
497 {
498 if ((m_lookup_cache.left < 0) ||
499 ((m_lookup_cache.left > x) || (m_lookup_cache.range.second->when < x))) {
500
501 CurveNode cn (this, x, 0.0);
502
503 APILinkedListNode* first = m_nodes.first();
504 APILinkedListNode* last = m_nodes.last();
505 APILinkedListNode* middle;
506 bool validrange = false;
507 int len = m_nodes.size() - 1;
508 int half;
509
510 while (len > 0) {
511 half = len >> 1;
512 middle = first;
513 // advance middle by half
514 int n = half;
515 while (n--) {
516 middle = middle->next;
517 }
518 //start compare
519 if (((CurveNode*)middle)->when < cn.when) {
520 first = middle;
521 first = first->next;
522 len = len - half - 1;
523 } else if (cn.when < ((CurveNode*)middle)->when) {
524 len = half;
525 } else {
526 // lower bound (using first/middle)
527 APILinkedListNode* lbfirst = first;
528 APILinkedListNode* lblast = middle;
529 APILinkedListNode* lbmiddle;
530 // start distance.
531 int lblen = 0;
532 APILinkedListNode* temp = lbfirst;
533 while (temp != lblast) {
534 temp = temp->next;
535 ++lblen;
536 }
537
538 int lbhalf;
539 while (lblen > 0) {
540 lbhalf = lblen >> 1;
541 lbmiddle = lbfirst;
542 // advance middle by half
543 n = lbhalf;
544 while (n--) {
545 lbmiddle = lbmiddle->next;
546 }
547 if (((CurveNode*)lbmiddle)->when < cn.when) {
548 lbfirst = lbmiddle;
549 lbfirst = lbfirst->next;
550 lblen = lblen - lbhalf - 1;
551 } else {
552 lblen = lbhalf;
553 }
554 }
555 m_lookup_cache.range.first = (CurveNode*)lbfirst;
556
557
558 // upper bound
559 APILinkedListNode* ubfirst = middle->next;
560 APILinkedListNode* ublast = last;
561 APILinkedListNode* ubmiddle;
562 // start distance.
563 int ublen = 0;
564 temp = ubfirst;
565 while (temp != ublast) {
566 temp = temp->next;
567 ++ublen;
568 }
569
570 int ubhalf;
571 while (ublen > 0) {
572 ubhalf = ublen >> 1;
573 ubmiddle = ubfirst;
574 // advance middle by half
575 n = ubhalf;
576 while (n--) {
577 ubmiddle = ubmiddle->next;
578 }
579
580 if (cn.when < ((CurveNode*)ubmiddle)->when) {
581 ublen = ubhalf;
582 } else {
583 ubfirst = ubmiddle;
584 ubfirst = ubfirst->next;
585 ublen = ublen - ubhalf - 1;
586 }
587 }
588 m_lookup_cache.range.second = (CurveNode*)ubfirst;
589
590 validrange = true;
591 break;
592 }
593 }
594 if (!validrange) {
595 m_lookup_cache.range.first = (CurveNode*)first;
596 m_lookup_cache.range.second = (CurveNode*)first;
597 }
598 }
599
600 /* EITHER
601
602 a) x is an existing control point, so first == existing point, second == next point
603
604 OR
605
606 b) x is between control points, so range is empty (first == second, points to where
607 to insert x)
608
609 */
610
611 if (m_lookup_cache.range.first == m_lookup_cache.range.second) {
612
613 /* x does not exist within the list as a control point */
614
615 m_lookup_cache.left = x;
616
617 double x2 = x * x;
618 CurveNode* cn = m_lookup_cache.range.second;
619
620 return cn->coeff[0] + (cn->coeff[1] * x) + (cn->coeff[2] * x2) + (cn->coeff[3] * x2 * x);
621 }
622
623 /* x is a control point in the data */
624 /* invalidate the cached range because its not usable */
625 m_lookup_cache.left = -1;
626 return m_lookup_cache.range.first->value;
627 }
628
set_range(double when)629 void Curve::set_range(double when)
630 {
631 if (m_nodes.isEmpty()) {
632 printf("Curve::set_range: no nodes!!");
633 return;
634 }
635
636 CurveNode* lastnode = (CurveNode*)m_nodes.last();
637
638 if (lastnode->when == when) {
639 // printf("Curve::set_range: new range == current range!\n");
640 return;
641 }
642
643 if (when < 0.0 ) {
644 printf("Curve::set_range: error, when < 0.0 ! (%f)\n", when);
645 return;
646 }
647
648 Q_ASSERT(when >= 0.0);
649
650 double factor = when / lastnode->when;
651
652 if (factor == 1.0)
653 return;
654
655 x_scale (factor);
656
657 set_changed();
658 }
659
x_scale(double factor)660 void Curve::x_scale(double factor)
661 {
662 Q_ASSERT(factor != 0.0);
663
664 apill_foreach(CurveNode* node, CurveNode, m_nodes) {
665 node->set_when(node->when * factor);
666 }
667 }
668
set_changed()669 void Curve::set_changed( )
670 {
671 m_lookup_cache.left = -1;
672 m_changed = true;
673 }
674
675
676 /**
677 * Add a new Node to this Curve.
678 *
679 * The returned Command object can be placed on the history stack,
680 * to make un-redo possible (the default (??) when called from the InputEngine)
681 *
682 * Note: This function should only be called from the GUI thread!
683 *
684 * @param node CurveNode to add to this Curve
685 * @param historable Should the returned Command object be placed on the
686 history stack?
687 * @return A Command object, if the call was generated from the InputEngine,
688 it can be leaved alone, if it was a direct call, use Command::process_command()
689 to do the actuall work!!
690 */
add_node(CurveNode * node,bool historable)691 Command* Curve::add_node(CurveNode* node, bool historable)
692 {
693 PENTER2;
694
695 apill_foreach(CurveNode* cn, CurveNode, m_nodes) {
696 if (node->when == cn->when && node->value == cn->value) {
697 info().warning(tr("There is allready a node at this exact position, not adding a new node"));
698 delete node;
699 return 0;
700 }
701 }
702
703
704 AddRemove* cmd;
705 cmd = new AddRemove(this, node, historable, m_sheet,
706 "private_add_node(CurveNode*)", "nodeAdded(CurveNode*)",
707 "private_remove_node(CurveNode*)", "nodeRemoved(CurveNode*)",
708 tr("Add CurveNode"));
709
710 return cmd;
711 }
712
713
714 /**
715 * Remove a Node from this Curve.
716 *
717 * The returned Command object can be placed on the history stack,
718 * to make un-redo possible (the default (??) when called from the InputEngine)
719 *
720 * Note: This function should only be called from the GUI thread!
721 *
722 * @param node CurveNode to be removed from this Curve
723 * @param historable Should the returned Command object be placed on the
724 history stack?
725 * @return A Command object, if the call was generated from the InputEngine,
726 it can be leaved alone, if it was a direct call, use Command::process_command()
727 to do the actuall work!!
728 */
remove_node(CurveNode * node,bool historable)729 Command* Curve::remove_node(CurveNode* node, bool historable)
730 {
731 PENTER2;
732
733 if (m_nodes.first() == node) {
734 MoveNode* cmd;
735
736 cmd = new MoveNode(this, node, 0.0f, 1.0f, tr("Remove CurveNode"));
737
738 return cmd;
739 }
740
741
742 AddRemove* cmd;
743
744 cmd = new AddRemove(this, node, historable, m_sheet,
745 "private_remove_node(CurveNode*)", "nodeRemoved(CurveNode*)",
746 "private_add_node(CurveNode*)", "nodeAdded(CurveNode*)",
747 tr("Remove CurveNode"));
748
749 return cmd;
750 }
751
private_add_node(CurveNode * node)752 void Curve::private_add_node( CurveNode * node )
753 {
754 m_nodes.add_and_sort(node);
755 set_changed();
756 }
757
private_remove_node(CurveNode * node)758 void Curve::private_remove_node( CurveNode * node )
759 {
760 m_nodes.remove(node);
761 set_changed();
762 }
763
set_sheet(Sheet * sheet)764 void Curve::set_sheet(Sheet * sheet)
765 {
766 m_sheet = sheet;
767 set_history_stack(m_sheet->get_history_stack());
768 }
769
770