Печать страницы - Вычислить кадр мувика

Добрый день

Задан диапазон кадров R[2], напр [5..10] (играть с 5-го по 10-й включительно) или [10..5] (играть в обратном порядке с 10-го по 5-й). После того как достигнут последний или первый кадр диапазона мувик должен проигрываться в обратном порядке, напр
5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 6...

Требуется ф-ция которая возвращает любой следующий кадр от текущего

Код

C++ (Qt)
int NextFrame( int currentFrame, int step, .. );

Для последовательности кадров выше

NextFrame(9, 1) = 10
NextFrame(9, 2) = 9

Спасибо

Набил на скорую руку, вроде работает

Код:

int NextFrame(int currentFrame, int step, int x0, int x1) {
    int dPosFirst = x1>x0? 1: -1; // направление в первой последовательности
    int size = abs(x1-x0)+1;

    int posCurrentFrame = (currentFrame - x0) * dPosFirst;
    if(posCurrentFrame >= size || posCurrentFrame<0) return 0; //TODO error: число не принадлежит последовательности

    posCurrentFrame += step; // new Frame;

    if(x0 == x1)return x0; // если один кадр
    int sizeWithBack = size*2 - 2; // размер последовательности включая обратную(не правильно считает для одного кадра x0==x1, но этот случай отсекли)
    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack; // теперь новый кадр будет лежать в диапазоне [0, sizeWithBack), так как данная последовательность повторяется

    return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                   x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}

если у вас может быть отрицательной позиция кадра, добавить после строки
posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
строку:
if(posCurrentFrame<0) posCurrentFrame += sizeWithBack;

p.s. имхо, я бы разбил на 2 функции:

int nextFrame = pos2frame( frame2pos( currentFrame ) + step )

а если видео нужно гонять в цикле, то итератор подошел бы

class zzzz{int data, direction ... int operator ++() { data += direction; if(direction == x0 || direction == x1) direction = -direction; return data; } } // direction = +1 / -1, для x0==x1 direction=0;

Цитировать

Набил на скорую руку, вроде работает

Можно попроще

Код

C++ (Qt)
inline int NextFrame(int currentFrame, int step, int min, int max)
{
    const int T = 2*(max - min);
 
    auto toFrame = [&](int x)->int
    {
        return (x <= T/2) ? (min + x) : (T - x + min);
    };
 
    int x = currentFrame - min;
 
    int n = trunc(double(step)/T);
 
    return toFrame(x + step - T*n);
}

Цитировать

а если видео нужно гонять в цикле, то итератор подошел бы

Итераторы здесь, это больная тема :)

Цитата: m_ax от Май 22, 2017, 13:28

Можно попроще

не спорю, но "int x = currentFrame - min;" некорректно, так как в условии " или [10..5] (играть в обратном порядке с 10-го по 5-й)"
нет проверки на диапазон, да и вообще она неверный результат на тесте выводит.

int n = trunc(double(step)/T); лучше floor - для отрицательных значений(из условия неясно могут ли кадры быть отрицательными) у trunc результат неверный будет
Вообще переводить в double, лишние операции, мой вариант проще :)

В предложенные решения пока глубоко не вникал (просто это трудно несмотря на внешнюю простоту задачки), но хочу обратить Ваше внимание на такую деталь

Цитата: Igors от Май 22, 2017, 07:08

5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 6...
...
NextFrame(9, 1) = 10
NextFrame(9, 2) = 9

А "от какого" 9? Не вижу как это учтено в Ваших исходниках. Вводить доп переменные не запрещено, можно и просто переставить диапазон R. Но все равно спасибо за участие :)

Цитата: m_ax от Май 22, 2017, 13:28

Итераторы здесь, это больная тема :)

Здесь как раз нужен прямой доступ. Если мувик не укладывается в заданный FPS и включена стандартная опция "drop frames", то кадры должны пропускаться. Пример: на данный момент должно быть показано уже 10 кадров, а успели всего 6 - грузим 4-й кадр от текущего. Собсно за этим и нужна такая ф-ция.

Да, и в "геометрии" там задачка давно плачет по Вашему академическому образованию :)

Цитата: m_ax от Май 22, 2017, 13:54

На каком именно тесте?

for(int i=-20; i<20; ++i) qDebug() << NextFrame(9,i,5,10); //
for(int i=-20; i<20; ++i) qDebug() << NextFrame(9,i,10,5); //

можно с нуля начинать, но так как автор не указал допустимы ли отрицательная позиция кадра, я начал с -20.
Мой пример выводит корректно, хотя я бы сам его переписал. х0,х1 диапазон 5 и 10, или 10 и 5 например(плохие имена переменных)

Цитата: Igors от Май 22, 2017, 14:07

[5 6 7 8 9 10] 9 8 7 6 5 6 7 ... - из основного диапазона (в скобках []) 9-ку брал, можно аргумент ввести если из следующего перевернутого брать
if(isReverseFind==true) posCurrentFrame = sizeWithBack - posCurrentFrame;

Цитата: Igors от Май 23, 2017, 12:42

Мой вариант
int relF = qAbs(curFrame - R[0]) + step; // frame to relative

А если R[10,5], то фрейм 8 окажеться на -2 месте, и следующий кадр укажет на 9, а не на 7.

Моя программа выводит:
for(int i=-20; i<20; ++i) qDebug() << NextFrame(9,i,5,10);
9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8
for(int i=-20; i<20; ++i) qDebug() << NextFrame(9,i,10,5);
9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10

А вот данная программа выводит:
-11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 5 6 7 8 9 10 9 8 7 6 5 5 6
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 6 7 8 9 10 10 9 8 7 6 5 6 7 8 9

Ладно, пусть i<0 это наверное не нужно(кадры, возможно, не могут быть отрицательными), но вот 5 5 подряд вроде не должно быть? или я не понял что должна функция делать?

Цитата: deMax от Май 24, 2017, 10:25

Ладно, пусть i<0 это наверное не нужно(кадры, возможно, не могут быть отрицательными), но вот 5 5 подряд вроде не должно быть? или я не понял что должна функция делать?

Параметр step (у Вас "i") это не кадр, а смещение кадра относительно текущего. Пример

currentFrame = 5; // текущий кадр мувика = 5
step = 2; // на какое число кадров сдвинуться? (на 2 собаки вперед)

Т.е. какой кадр мувика (лежащий в диапазоне R) станет текущим? При этом еcли смещение = периоду то следующий кадр будет тем же (напр 5). Отрицательное смещение не рассматривается - время-то идет только вперед :)

Это понятно, просто при "i < -curFramePos" позиция в последовательности станет отрицательной.

>> Отрицательное смещение не рассматривается - время-то идет только вперед
Вам виднее, тогда uint step ;)

мне не известно и не интересно зачем вам гонять фрагмент видео. Я только написал рабочее решение для int step,
остальные программы работают неправильно :P
Возможно нет смысла проверять currentFrame на принадлежность диапазону(уже проверенно).

Цитировать

остальные программы работают неправильно

Всё работает как надо) Слегка подправил для для обратного порядка и на проверку на диапазон.

Код

C++ (Qt)
inline int NextFrame(int currentFrame, int step, int x0, int x1) throw (std::logic_error)
{
    if ((currentFrame < std::min(x0, x1)) || (currentFrame > std::max(x0, x1)))
        throw std::logic_error("out of range");
 
    int sign = (x1 > x0) ? 1 : -1;
 
    const int T = 2*sign*(x1 - x0);
 
    auto toFrame = [&](int x)->int
    {
        return (x <= T/2) ? (x0 + sign*x) : (sign*(T - x) + x0);
    };
 
    int x = sign*(currentFrame - x0);
 
    return toFrame((x + step % T) % T);
}

По моему это гораздо проще и нагляднее)

m_ax
теперь работает, но есть мелкие придирки
1. uint step - для отрицательных чисел у вас алгоритм вычисляет неправильно(автору не нужно)
2. при x0 == x1 у вас T == 0 -> %T сгенерирует ошибку и программа упадет без обработчика
3. Названия переменных T -> cycleSize, toFrame -> pos2numFrame, x -> pos
4. имхо, через деление выражение ((x + step % T) % T) быстрее будет
5. std::min и max тоже можно убрать повысив производительность, if((sign>0 && currentFrame<x0 ?&& currentFrame>x1) || (sign<0 && currentFrame<x1 ?&& currentFrame>x0)) throw std::logic_error("out of range");

Цитировать

1. uint step - для отрицательных чисел у вас алгоритм вычисляет неправильно(автору не нужно)

Да вроде и с отрицательными работает нормально)

Цитировать

2. при x0 == x1 у вас T == 0 -> %T сгенерирует ошибку и программа упадет без обработчика

Да, согласен)

Цитировать

4. имхо, через деление выражение ((x + step % T) % T) быстрее будет

Не знаю.. думаю сейчас, это больше от компилятора зависит..

Цитировать

5. std::min и max тоже можно убрать повысив производительность, if((sign>0 && currentFrame<x0 ?&& currentFrame>x1) || (sign<0 && currentFrame<x1 ?&& currentFrame>x0)) throw std::logic_error("out of range");

Здесь, думаю, тож спорно в плане производительности.. Я за читабельность в данном случае)

Цитата: m_ax от Май 25, 2017, 14:43

Да вроде и с отрицательными работает нормально)

9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8
9 18 17 16 15 14 13 12 11 10 9 18 17 16 15 14 13 12 11 10 9 8 7 6 5 6 7 8 9 10 9 8 7 6 5 6 7 8 9 10
нет ерунда, да еще за диапазон вышла. Но автор сказал не надо, значит uint

Цитировать

Не знаю.. думаю сейчас, это больше от компилятора зависит..

Моя функция 20млн.раз выполняется за 301мс(с поддержкой отрицательного шага 324), а ваша 640.
Возможно лямбда здесь лишняя, кстати зачем она тут?

имхо это сильно быстрее ваших двух остатков от деления(жирная операция)

Код:

    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
    if(posCurrentFrame<0) posCurrentFrame += sizeWithBack; // это для отрицательных шагов(т.е. удалить), т.к. -0.5 округляют не в меньшую сторону, а к нулю(можно floor использовать)

Цитировать

Здесь, думаю, тож спорно в плане производительности.. Я за читабельность в данном случае)

перемудрил:
if((currentFrame<x0 && currentFrame<x1) || (currentFrame>x1 && currentFrame>x0)) throw std::logic_error("out of range");
но ваше std::min читается получше, хоть и медленнее. хотя, имихо, это условие вообще должно вне функции проверяться, чтобы не терять производительность), т.к. эта функция скорее всего принимает curFrame как свое возвращаемое значение.

Цитировать

нет ерунда, да еще за диапазон вышла.

Я вот на таком тесте

Код

C++ (Qt)
#include <iostream>
#include <random>
#include <cmath>
#include <stdexcept>
 
 
inline int NextFrame_m_ax(int currentFrame, int step, int x0, int x1) throw (std::logic_error)
{
    if ((currentFrame < std::min(x0, x1)) || (currentFrame > std::max(x0, x1)))
        throw std::logic_error("out of range");
 
    if (x0 == x1) return x0;
 
    const int sign = (x1 > x0) ? 1 : -1;
 
    const int T = 2*sign*(x1 - x0);
 
    auto toFrame = [&](int x)->int
    {
        return (x <= T/2) ? (x0 + sign*x) : (sign*(T - x) + x0);
    };
 
    int x = sign*(currentFrame - x0);
 
    return toFrame((x + step % T) % T);
}
 
 
int NextFrame_deMax(int currentFrame, int step, int x0, int x1) {
    int dPosFirst = x1>x0? 1: -1; // направление в первой последовательности
    int size = abs(x1-x0)+1;
 
    int posCurrentFrame = (currentFrame - x0) * dPosFirst;
    if(posCurrentFrame >= size || posCurrentFrame<0) return 0; //TODO error: число не принадлежит последовательности
 
    posCurrentFrame += step; // new Frame;
 
    if(x0 == x1)return x0; // если один кадр
    int sizeWithBack = size*2 - 2; // размер последовательности включая обратную(не правильно считает для одного кадра x0==x1, но этот случай отсекли)
    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack; // теперь новый кадр будет лежать в диапазоне [0, sizeWithBack), так как данная последовательность повторяется
 
    return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                   x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}
 
 
int main()
{
    int f0 = 5;
    int f1 = 10;
    int frame = 9;
 
    std::cout << "m_ax \t deMax" << std::endl;
 
    for(int i=-20; i<20; ++i)
    {
        std::cout <<  NextFrame_m_ax(frame, i, f0, f1) << "\t" << NextFrame_deMax(frame, i, f0, f1) << std::endl;
    }
 
    return 0;
}

получил следующее:

Код

Bash
m_ax    deMax
9	-1
0	0
1	1
2	2
3	3
4	4
5	5
6	-4
7	-3
8	-2
9	-1
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	10
9	9
8	8
7	7
6	6
5	5
6	6
7	7
8	8
9	9
10	10
9	9
8	8
7	7
6	6
5	5
6	6
7	7
8	8

т.е. у вас она уходит в отрицательные значения..

Если изменить порядок диапазона:

Код

C++ (Qt)
    int f0 = 10;
    int f1 = 5;

то обе реализации выдают ерунду (

Код

Bash
m_ax 	 deMax
9	19
18	18
17	17
16	16
15	15
14	14
13	13
12	12
11	11
10	10
9	19
18	18
17	17
16	16
15	15
14	14
13	13
12	12
11	11
10	10
9	9
8	8
7	7
6	6
5	5
6	6
7	7
8	8
9	9
10	10
9	9
8	8
7	7
6	6
5	5
6	6
7	7
8	8
9	9
10	10

Я написал что добавил строчку, но не выложил код

Код:

inline int NextFrame(int currentFrame, int step, int x0, int x1) {
    int dPosFirst = x1>x0? 1: -1;
    int size = abs(x1-x0)+1;

    int posCurrentFrame = (currentFrame - x0) * dPosFirst;
    if(posCurrentFrame >= size) return 0; //TODO error

    posCurrentFrame += step; // new Frame;
    int sizeWithBack = size*2 - 2;

    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
    if(posCurrentFrame<0) posCurrentFrame += sizeWithBack; // без этой строчки у меня текущий кадр при отрицательном шаге сваливается в отрицательное значение, не из диапазона [0, sizeWithBack) и получается ерунда

    return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                   x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}

Цитировать

У меня другие результаты - противоположные..

Сделал вашу функцию инлайн и результаты примерно выровнялись:

Код

Bash
m_ax, total time: 296
deMax, total time: 305
 
m_ax, total time: 296
deMax, total time: 304
 
m_ax, total time: 297
deMax, total time: 303

(результаты после 3-х запусков), что говорит о том, что компилятор не видит особой разницы между

Код

C++ (Qt)
posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
if(posCurrentFrame<0) posCurrentFrame += sizeWithBack;

и этим

Код

C++ (Qt)
return toFrame((x + step % T) % T);

m_ax,

Цитировать

Сделал вашу функцию инлайн и результаты примерно выровнялись:

если удалить "if(posCurrentFrame<0) posCurrentFrame += sizeWithBack;" (у вас то отрицательные позиции не работают), то еще одинаковей будет.

Igors

Цитировать

А "от какого" 9? Не вижу как это учтено в Ваших исходниках.

вроде отвечал уже:

Цитата: Igors от Май 22, 2017, 14:07

если нужно хранить позицию девятки (isReverse = false от x0 к x1; true от x1 к x0)

Код:

inline int NextFrame(int currentFrame, uint step, int x0, int x1, bool &isReverse) {
    int dPosFirst = x1>x0? 1: -1;
    int size = abs(x1-x0)+1;

    int posCurrentFrame = (currentFrame - x0) * dPosFirst;
    if(posCurrentFrame >= size) return 0; //TODO error
    if(isReverseFind == true) posCurrentFrame = sizeWithBack - posCurrentFrame;

    posCurrentFrame += step; // new Frame;
    int sizeWithBack = size*2 - 2;

    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
//    if(posCurrentFrame<0) posCurrentFrame += sizeWithBack; // без этой строчки у меня текущий кадр при отрицательном шаге сваливается в отрицательное значение, не из диапазона [0, sizeWithBack) и получается ерунда
    isReverse = posCurrentFrame >= size;
    return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                   x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}

но здесь итератор просится, чем эта функция с кучей параметров

Цитата: deMax от Июнь 01, 2017, 09:39

вроде отвечал уже:

...можно аргумент ввести если из следующего перевернутого брать

...если нужно хранить позицию девятки

А что, можно как-то "не хранить"? Не вижу как, если известен только текущий фрейм (напр 9) то однозначного рез-та не получить. Поэтому не надо "делать одолжение", давайте обсуждать только полные решения

Цитата: deMax от Июнь 01, 2017, 09:39

Код:

inline int NextFrame(int currentFrame, uint step, int x0, int x1, bool &isReverse) {
    int dPosFirst = x1>x0? 1: -1;
    int size = abs(x1-x0)+1;

    int posCurrentFrame = (currentFrame - x0) * dPosFirst;
    if(posCurrentFrame >= size) return 0; //TODO error
    if(isReverseFind == true) posCurrentFrame = sizeWithBack - posCurrentFrame;

    posCurrentFrame += step; // new Frame;
    int sizeWithBack = size*2 - 2;

    posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
//    if(posCurrentFrame<0) posCurrentFrame += sizeWithBack; // без этой строчки у меня текущий кадр при отрицательном шаге сваливается в отрицательное значение, не из диапазона [0, sizeWithBack) и получается ерунда
    isReverse = posCurrentFrame >= size;
    return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                   x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}

Мда, ну как-то "чижело" :) (хотя может и правильно).

Цитата: deMax от Июнь 01, 2017, 09:39

но здесь итератор просится, чем эта функция с кучей параметров

И если поступило указание "на 100 собак вперед" - то мы 100 раз зовем ++it, расписываясь в том что "просто посчитать" не умеем. Ну как-то неудобно :)

Да, а мой вариант чем плох? Если нужно и отрицательное смещение (мне нет), то может проще всего свести его к положительному

Код

C++ (Qt)
period = qAbs(R[1] - R[0]) * 2 + 1;
step = (step % period) + period;

В общем, если есть желание - попинайте меня вместо m_ax :) Спасибо

Итератор будет внутри хранить текущую позицию(а не номер фрейма), у него будет расчитан размер...
Вроде все тоже самое что и функция, только первая часть будет вызвана один раз в конструкторе и наружу не лезет всякая ерунда типа reverse, и при вызове функции не инлайн один аргумент - смещение (в стек будет лишний мусор копироваться). Хотя при времени выполнения функции 300/20е6 секунды, может и не стоит этим заниматься.

p.s. можете назвать его по другому, т.к. у вас в отличие от полноценного итератора будет только конструктор и метод сдвига.

как то так:

Код:

class NextFrame
{
    int x0, x1;
    int posCurrentFrame, dPosFirst, size, sizeWithBack;
    bool isReverse;
public:
    NextFrame(int currentFrame, int x0, int x1, bool isReverse): x0(x0), x1(x1), isReverse(isReverse) {
        dPosFirst = x1>x0? 1: -1;
        size = abs(x1-x0)+1;
        sizeWithBack = size*2 - 2;

        posCurrentFrame = (currentFrame - x0) * dPosFirst;
        if(posCurrentFrame >= size) return; //TODO error
        if(isReverse == true) posCurrentFrame = sizeWithBack - posCurrentFrame; }
    int operator+=(uint step)
    {
        posCurrentFrame += step; // new Frame;

        posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
        //    if(posCurrentFrame<0) posCurrentFrame += sizeWithBack; // без этой строчки у меня текущий кадр при отрицательном шаге сваливается в отрицательное значение, не из диапазона [0, sizeWithBack) и получается ерунда
        isReverse = posCurrentFrame >= size;
        return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                       x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
    }
};

...

//вроде работает :)
    NextFrame nf(9, 5, 10);
    for(int i=0; i<20; ++i)
        qDebug() << (nf+=1);

Это на скорую руку, если есть желание можно проверить производительность, хотя за счет вызова функции наверное уменьшиться.

Цитата: deMax от Июнь 01, 2017, 14:44

Итератор будет внутри хранить текущую позицию(а не номер фрейма), у него будет расчитан размер...

Понял - с идеей инкапсуляции. По-моему особого смысла в ней здесь нет, больше "обвязок" придется писать (а потом читать). Хотя конечно - дело вкуса.

Цитата: deMax от Июнь 01, 2017, 14:44

..и при вызове функции не инлайн один аргумент - смещение (в стек будет лишний мусор копироваться). Хотя при времени выполнения функции 300/20е6 секунды, может и не стоит этим заниматься.
...
...если есть желание можно проверить производительность, хотя за счет вызова функции наверное уменьшиться.

Я тоже за производительность, но уверен - это не то место где надо оптимизировать :)

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Igors от Май 22, 2017, 07:08