1 //=============================================================================
2 // MuseScore
3 // Music Composition & Notation
4 //
5 // Copyright (C) 2009-2011 Werner Schweer
6 //
7 // This program is free software; you can redistribute it and/or modify
8 // it under the terms of the GNU General Public License version 2
9 // as published by the Free Software Foundation and appearing in
10 // the file LICENCE.GPL
11 //=============================================================================
12
13 /**
14 \file
15 Implementation of class ChangeMap.
16 */
17
18 #include "changeMap.h"
19
20 namespace Ms {
21
22 //---------------------------------------------------------
23 // interpolateVelocity
24 /// the maths looks complex, but is just a series of graph transformations.
25 /// You can see these graphically at: https://www.desmos.com/calculator/kk89ficmjk
26 //---------------------------------------------------------
27
interpolate(Fraction & eventTick,ChangeEvent & event,Fraction & tick)28 int ChangeMap::interpolate(Fraction& eventTick, ChangeEvent& event, Fraction& tick)
29 {
30 Q_ASSERT(event.type == ChangeEventType::RAMP);
31
32 // Prevent zero-division error
33 if (event.cachedStartVal == event.cachedEndVal || event.length.isZero()) {
34 return event.cachedStartVal;
35 }
36
37 // Ticks to change expression over
38 int exprTicks = event.length.ticks();
39 int exprDiff = event.cachedEndVal - event.cachedStartVal;
40
41 std::function<int(int)> valueFunction;
42 switch (event.method) {
43 case ChangeMethod::EXPONENTIAL:
44 // Due to the nth-root, exponential functions do not flip with negative values, and cause errors,
45 // so treat it as a piecewise function.
46 if (exprDiff > 0) {
47 valueFunction = [&](int ct) { return int(
48 pow(
49 pow((exprDiff + 1), 1.0 / double(exprTicks)), // the exprTicks root of d+1
50 double(ct) // to the power of the current tick (exponential)
51 ) - 1
52 ); };
53 }
54 else {
55 valueFunction = [&](int ct) { return -int(
56 pow(
57 pow((-exprDiff + 1), 1.0 / double(exprTicks)), // the exprTicks root of 1-d
58 double(ct) // again to the power of ct
59 ) + 1
60 ); };
61 }
62 break;
63 // Uses sin x transformed, which _does_ flip with negative numbers
64 case ChangeMethod::EASE_IN_OUT:
65 valueFunction = [&](int ct) { return int(
66 (double(exprDiff) / 2.0) * (
67 sin(
68 double(ct) * (
69 double(M_PI / double(exprTicks))
70 ) - double(M_PI / 2.0)
71 ) + 1
72 )
73 ); };
74 break;
75 case ChangeMethod::EASE_IN:
76 valueFunction = [&](int ct) { return int(
77 double(exprDiff) * (
78 sin(
79 double(ct - double(exprTicks)) * (
80 double(M_PI / double(2 * exprTicks))
81 )
82 ) + 1
83 )
84 ); };
85 break;
86 case ChangeMethod::EASE_OUT:
87 valueFunction = [&](int ct) { return int(
88 double(exprDiff) * sin(
89 double(ct) * (
90 double(M_PI / double(2 * exprTicks))
91 )
92 )
93 ); };
94 break;
95 case ChangeMethod::NORMAL:
96 default:
97 valueFunction = [&](int ct) { return int(
98 double(exprDiff) * (double(ct) / double(exprTicks))
99 ); };
100 break;
101 }
102
103 return event.cachedStartVal + valueFunction(tick.ticks() - eventTick.ticks());
104 }
105
106 //---------------------------------------------------------
107 // val
108 /// return value at tick position. Do not confuse with
109 /// `value`, which is a method of QMultiMap.
110 //---------------------------------------------------------
111
val(Fraction tick)112 int ChangeMap::val(Fraction tick)
113 {
114 if (!cleanedUp)
115 cleanup();
116
117 auto eventIter = upperBound(tick);
118 if (eventIter == begin()) {
119 return DEFAULT_VALUE;
120 }
121
122 eventIter--;
123 bool foundRamp = false;
124 ChangeEvent& rampFound = eventIter.value(); // only used to init
125 Fraction rampFoundStartTick = eventIter.key();
126 for (auto& event : values(rampFoundStartTick)) {
127 if (event.type == ChangeEventType::RAMP) {
128 foundRamp = true;
129 rampFound = event;
130 }
131 }
132
133 if (!foundRamp) {
134 // Last event must be a fix, since there are max two events at one tick
135 return eventIter.value().value;
136 }
137
138 if (tick >= (rampFoundStartTick + rampFound.length)) {
139 return rampFound.cachedEndVal;
140 }
141 else {
142 // Do some maths!
143 return interpolate(rampFoundStartTick, rampFound, tick); // NOTE:JT check should rampFound be eventIter.value()
144 }
145 }
146
147 //---------------------------------------------------------
148 // addFixed
149 //---------------------------------------------------------
150
addFixed(Fraction tick,int value)151 void ChangeMap::addFixed(Fraction tick, int value)
152 {
153 insert(tick, ChangeEvent(value));
154 cleanedUp = false;
155 }
156
157 //---------------------------------------------------------
158 // addRamp
159 /// A `change` of 0 means that the change in velocity should be calculated from the next fixed
160 /// velocity event.
161 //---------------------------------------------------------
162
addRamp(Fraction stick,Fraction etick,int change,ChangeMethod method,ChangeDirection direction)163 void ChangeMap::addRamp(Fraction stick, Fraction etick, int change, ChangeMethod method, ChangeDirection direction)
164 {
165 change = abs(change);
166 change *= (direction == ChangeDirection::INCREASING) ? 1 : -1;
167 insert(stick, ChangeEvent(stick, etick, change, method, direction));
168 cleanedUp = false;
169 }
170
171 //---------------------------------------------------------
172 // cleanupStage0
173 /// put the ramps in size order if they start at the same point
174 //---------------------------------------------------------
175
cleanupStage0()176 void ChangeMap::cleanupStage0()
177 {
178 for (auto& tick : uniqueKeys()) {
179 // rampEvents will contain all the ramps at this tick
180 std::vector<ChangeEvent> rampEvents;
181 for (auto& event : values(tick)) {
182 if (event.type == ChangeEventType::FIX)
183 continue;
184 rampEvents.push_back(event);
185 }
186
187 if (int(rampEvents.size()) > 1) {
188 // Sort rampEvents so that the longest ramps come first -
189 // this is important for when we remove ramps/fixes enclosed wihtin other
190 // ramps during stage 1.
191 std::sort(rampEvents.begin(), rampEvents.end(), ChangeMap::compareRampEvents);
192 for (auto& event : rampEvents) {
193 insert(tick, event);
194 }
195 }
196 }
197 }
198
199 //---------------------------------------------------------
200 // cleanupStage1
201 /// remove any ramps or fixes that are completely enclosed within other ramps
202 //---------------------------------------------------------
203
cleanupStage1()204 void ChangeMap::cleanupStage1()
205 {
206 Fraction currentRampStart = Fraction(-1, 1); // start point of ramp we're in
207 Fraction currentRampEnd = Fraction(-1, 1); // end point of ramp we're in
208 Fraction lastFix = Fraction(-1, 1); // the position of the last fix event
209 bool inRamp = false; // whether we're in a ramp or not
210
211 // Keep a record of the endpoints
212 EndPointsVector endPoints;
213 std::vector<bool> startsInRamp;
214
215 auto i = begin();
216 while (i != end()) {
217 Fraction tick = i.key();
218 ChangeEvent& event = i.value();
219 Fraction etick = tick + event.length;
220
221 // Reset if we've left the ramp we were in
222 if (currentRampEnd < tick)
223 inRamp = false;
224
225 if (event.type == ChangeEventType::RAMP) {
226 if (inRamp) {
227 if (etick <= currentRampEnd) {
228 // delete, this event is enveloped
229 i = erase(i);
230 // don't add to the end points
231 continue;
232 }
233 else {
234 currentRampStart = tick;
235 currentRampEnd = etick;
236 startsInRamp.push_back(true);
237 }
238 }
239 else {
240 currentRampStart = tick;
241 currentRampEnd = etick;
242 inRamp = true;
243 startsInRamp.push_back(false);
244 }
245
246 endPoints.push_back(std::make_pair(tick, etick));
247 }
248 else if (event.type == ChangeEventType::FIX) {
249 if (inRamp) {
250 if (tick != currentRampStart && tick != currentRampEnd && lastFix != tick) {
251 // delete, this event is enveloped or at the same point as another fix
252 i = erase(i);
253 continue;
254 }
255 }
256
257 lastFix = tick;
258 }
259
260 i++;
261 }
262
263 cleanupStage2(startsInRamp, endPoints);
264 }
265
266 //---------------------------------------------------------
267 // cleanupStage2
268 /// readjust lengths of any colliding ramps
269 //---------------------------------------------------------
270
cleanupStage2(std::vector<bool> & startsInRamp,EndPointsVector & endPoints)271 void ChangeMap::cleanupStage2(std::vector<bool>& startsInRamp, EndPointsVector& endPoints)
272 {
273 // moveTo stores the events that need to be moved to a Fraction position
274 std::map<Fraction, ChangeEvent> moveTo;
275 auto i = begin();
276 int j = -1;
277 while (i != end()) {
278 Fraction tick = i.key();
279 ChangeEvent& event = i.value();
280 if (event.type != ChangeEventType::RAMP) {
281 i++;
282 continue;
283 }
284
285 j++;
286 if (!startsInRamp[j]) {
287 i++;
288 continue;
289 }
290
291 // Take a copy of the event and remove it
292 Fraction newTick = endPoints[j-1].second;
293 event.length -= (newTick - tick);
294 moveTo[newTick] = event;
295 i = erase(i);
296 }
297
298 // Re-insert the events that we need to move in their new positions
299 for (auto k = moveTo.begin(); k != moveTo.end(); k++) {
300 insert(k->first, k->second);
301 }
302 }
303
304 //---------------------------------------------------------
305 // cleanupStage3
306 /// cache start and end values for each ramp
307 //---------------------------------------------------------
308
cleanupStage3()309 void ChangeMap::cleanupStage3()
310 {
311 for (auto i = begin(); i != end(); i++) {
312 Fraction tick = i.key();
313 auto& event = i.value();
314 if (event.type != ChangeEventType::RAMP)
315 continue;
316
317 // Phase 1: cache a start value for the ramp
318 // Try and get a fix at the tick of this ramp
319 bool foundFix = false;
320 for (auto& currentChangeEvent : values(tick)) {
321 if (currentChangeEvent.type == ChangeEventType::FIX) {
322 event.cachedStartVal = currentChangeEvent.value;
323 foundFix = true;
324 break;
325 }
326 }
327
328 // If there isn't a fix, use from the last event:
329 // - the cached end value if it's a ramp
330 // - the value if it's a fix
331 if (!foundFix) {
332 if (i != begin()) {
333 auto prevChangeEventIter = i;
334 prevChangeEventIter--;
335
336 // Look for a ramp first
337 bool foundRamp = false;
338 for (auto& prevChangeEvent : values(prevChangeEventIter.key())) {
339 if (prevChangeEvent.type == ChangeEventType::RAMP) {
340 event.cachedStartVal = prevChangeEvent.cachedEndVal;
341 foundRamp = true;
342 break;
343 }
344 }
345
346 if (!foundRamp) {
347 // prevChangeEventIter must point to a fix in this case
348 event.cachedStartVal = prevChangeEventIter.value().value;
349 }
350 }
351 else {
352 event.cachedStartVal = DEFAULT_VALUE;
353 }
354 }
355
356 // Phase 2: cache an end value for the ramp
357 // If there's no set velocity change:
358 if (event.value == 0) {
359 auto nextChangeEventIter = i;
360 nextChangeEventIter++;
361 // There's a chance that the next event is a fix at the same tick as the
362 // start of the current ramp. If so, get the next event, which is assured
363 // to be a different (larger) tick
364 if (nextChangeEventIter != end() && nextChangeEventIter.key() == tick)
365 nextChangeEventIter++;
366
367 // If this is the last event, there is no change
368 if (nextChangeEventIter == end()) {
369 event.cachedEndVal = event.cachedStartVal;
370 }
371 else {
372 // Search for a fixed event at the next event point
373 bool foundFix2 = false;
374 for (auto& nextChangeEvent : values(nextChangeEventIter.key())) {
375 if (nextChangeEvent.type == ChangeEventType::FIX) {
376 event.cachedEndVal = nextChangeEvent.value;
377 foundFix2 = true;
378 break;
379 }
380 }
381
382 // We haven't found a fix, so there must be a ramp. What does the user want?
383 // A good guess would to be to interpolate, but that might get complex, so just ignore
384 // this ramp and set the ending to be the same as the start.
385 // TODO: implementing some form of smart interpolation would be nice.
386 if (!foundFix2) {
387 event.cachedEndVal = event.cachedStartVal;
388 }
389 }
390 }
391 else {
392 event.cachedEndVal = event.cachedStartVal + event.value;
393 }
394
395 // And finally... if something's wrong, make it not wrong
396 if ((event.cachedStartVal > event.cachedEndVal && event.direction == ChangeDirection::INCREASING) ||
397 (event.cachedStartVal < event.cachedEndVal && event.direction == ChangeDirection::DECREASING)) {
398 event.cachedEndVal = event.cachedStartVal;
399 }
400 }
401
402 }
403
404 //---------------------------------------------------------
405 // cleanup
406 //---------------------------------------------------------
407
cleanup()408 void ChangeMap::cleanup()
409 {
410 if (cleanedUp)
411 return;
412
413 // qDebug() << "Before cleanup:";
414 // dump();
415
416 cleanupStage0();
417 cleanupStage1();
418 cleanupStage3();
419 cleanedUp = true;
420
421 // qDebug() << "After cleanup:";
422 // dump();
423 }
424
425 //---------------------------------------------------------
426 // changesInRange
427 /// returns a list of changes in a range, and their start and end points
428 //---------------------------------------------------------
429
changesInRange(Fraction stick,Fraction etick)430 std::vector<std::pair<Fraction, Fraction>> ChangeMap::changesInRange(Fraction stick, Fraction etick)
431 {
432 if (!cleanedUp)
433 cleanup();
434
435 std::vector<std::pair<Fraction, Fraction>> tempChanges;
436
437 // Force a new event on every noteon, in case the velocity has changed
438 tempChanges.push_back(std::make_pair(stick, stick));
439 for (auto iter = lowerBound(stick); iter != end(); iter++) {
440 Fraction tick = iter.key();
441 if (tick > etick)
442 break;
443
444 auto& event = iter.value();
445 if (event.type == ChangeEventType::FIX)
446 tempChanges.push_back(std::make_pair(tick, tick));
447 else if (event.type == ChangeEventType::RAMP) {
448 Fraction eventEtick = tick + event.length;
449 Fraction useEtick = eventEtick > etick ? etick : eventEtick;
450 tempChanges.push_back(std::make_pair(tick, useEtick));
451 }
452 }
453
454 // And also go back one and try to find ramp coming into this range
455 auto iter = lowerBound(stick);
456 if (iter != begin()) {
457 iter--;
458 auto& event = iter.value();
459 if (event.type == ChangeEventType::RAMP) {
460 Fraction eventEtick = iter.key() + event.length;
461 if (eventEtick > stick) {
462 tempChanges.push_back(std::make_pair(stick, eventEtick));
463 }
464 }
465 }
466 return tempChanges;
467 }
468
469 //---------------------------------------------------------
470 // changeMethodTable
471 //---------------------------------------------------------
472
473 const std::vector<ChangeMap::ChangeMethodItem> ChangeMap::changeMethodTable {
474 { ChangeMethod::NORMAL, "normal" },
475 { ChangeMethod::EASE_IN, "ease-in" },
476 { ChangeMethod::EASE_OUT, "ease-out" },
477 { ChangeMethod::EASE_IN_OUT, "ease-in-out" },
478 { ChangeMethod::EXPONENTIAL, "exponential" },
479 };
480
481 //---------------------------------------------------------
482 // changeMethodToName
483 //---------------------------------------------------------
484
changeMethodToName(ChangeMethod method)485 QString ChangeMap::changeMethodToName(ChangeMethod method)
486 {
487 for (auto i : ChangeMap::changeMethodTable) {
488 if (i.method == method)
489 return i.name;
490 }
491 qFatal("Unrecognised change method!");
492 return "none"; // silence a compiler warning
493 }
494
495 //---------------------------------------------------------
496 // nameToChangeMethod
497 //---------------------------------------------------------
498
nameToChangeMethod(QString name)499 ChangeMethod ChangeMap::nameToChangeMethod(QString name)
500 {
501 for (auto i : ChangeMap::changeMethodTable) {
502 if (i.name == name)
503 return i.method;
504 }
505 return ChangeMethod::NORMAL; // default
506 }
507
508 //---------------------------------------------------------
509 // dump
510 //---------------------------------------------------------
511
dump()512 void ChangeMap::dump()
513 {
514 qDebug("\n\n=== ChangeMap: dump ===");
515 for (auto i = begin(); i != end(); i++) {
516 Fraction tick = i.key();
517 auto& event = i.value();
518 if (event.type == ChangeEventType::FIX) {
519 qDebug().nospace() << "===" << tick.ticks() << " : FIX " << event.value;
520 }
521 else if (event.type == ChangeEventType::RAMP) {
522 qDebug().nospace() << "===" << tick.ticks() << " to " << (tick + event.length).ticks() << " : RAMP diff " << event.value << " " << ChangeMap::changeMethodToName(event.method) << " (" << event.cachedStartVal << ", " << event.cachedEndVal << ")";
523 }
524 else if (event.type == ChangeEventType::INVALID) {
525 qDebug().nospace() << "===" << tick.ticks() << " : INVALID value" << event.value;
526 }
527 }
528 qDebug("=== ChangeMap: dump end ===\n\n");
529 }
530
531 //---------------------------------------------------------
532 // operator==
533 //---------------------------------------------------------
534
operator ==(const ChangeEvent & event) const535 bool ChangeEvent::operator==(const ChangeEvent& event) const
536 {
537 return (
538 value == event.value &&
539 type == event.type &&
540 length == event.length &&
541 method == event.method &&
542 direction == event.direction
543 );
544 }
545
546 }
547
548