0
I’m developing a 3d program in c/c++, I’ve done the rendering part of the objects, I’m missing the animation part, basically I want to use a list of values (frames) each containing the frame time, the position (value) frame and 2 controls to use in the interpolation of Bezier curves, because I want to create quite long animations that I cannot use a list of values frame by frame, so I’ll use a well spaced list and use the Bezier interpolation to get a smooth interpolated value between 2 frames.
// possibilidade de estrutura para armazenar a informação
// dos frames em um array ou vetor que posteriormente será interpolado.
struct frame{
float time; // tempo do frame em que 1 unidade = 16.67ms
float point; // valor do frame
float c1 // control point 1, usado na interpolação com o frame anterior
float c2 // control point 2, usado na interpolação com o próximo frame
};
// C1 e C2 são os pontos de controle usados na interpolação
// com a função de curvas bezier para dar uma suavidade na
// animação (mas possivelmente vou modificar o que cada um significa)
// obs: No caso do primeiro frame o ponto de controle C1
// apesar de existente não é usado, no caso do ultimo frame
// da animação o ponto de controle C2 não é utilizado.
// exemplo de uso das estruturas frame, provavelmente será
// um vetor com centenas de frames (talvez milhares dependendo da animação)
std::vector<frame> frames;
// declaração da função bezier ainda não implementada, mas
// sua implementação é simples para mim e está fora do
// escopo da pergunta, pois apenas faz a interpolação entre 2 pontos
float bezier(frame& p1, frame& p2, float t);
// Exemplo de procura funcional, mas deixa a desejar em
// processamento necessário para encontrar o frame a ser
// usado devido a probabilidade de ter que atravessar uma
// gigantesca lista de frames comparando milhares de valores
// até ser encontrado o valor procurado.
float getFramePos(float time){ // primeira versão
for (int i = 0; i < frames.size(); i++){
if (frames[i].time => time)
return bezier(frames[i-1], frames[i], time);
};
};
// Bezier é uma função que pega como argumentos 2 frames
// e o tempo e faz os devidos cálculos e retorna o valor da
// interpolação bezier, mas sua implementação está fora
// do escopo da questão.
float position = getFramePos(236.57f);
// tempo provavelmente será 1.0f = 1 segundo/60 fps, pois 1 é
// igual a 1 frame em taxas de atualização de 60 quadros por
// segundo, utilizo float por também poder rodar a mais de 60
// FPS, então se caso for 120 fps pode-se usar 0.5 para cada
// quadro e 0.25 para cada quadro a 240 fps. Ajuda a ter boa
// interpolação de animação e taxa de quadros variáveis,
// é possível que seja substituído por double para maior
// precisão em animações longas
In a short list that function getFramePos() is fast, as there are few comparisons, but in a large list of thousands of frames, with many objects that each have their own animation and possibly have more than one animation running at the same time, the function becomes a disaster in the search mainly when the time sought in the animation is at the end of the list of frames, as you end up going through the whole list and comparing all times.
My question is: What is the fastest way to get the desired value from the list of frames looking for a certain time?
Note: Frames list time values will always be in ascending order.
Second version towards optimization:
// implementação via classe
struct frame{
float time;
float point; // atualmente float para simplicidade e melhor
//depuração, mais tarde também adicionarei float2, float3
//(mais usado) e matrix3x3 ou matrix4x4 (otimização para
//evitar de se ficar criando matix de transformação a cada frame)
float c1;
float c2;
};
class animation {
std::vector<frame> frames;
float lastTime; // ajuda para procura
int lastFrame; // ajuda para procura
// em animação linear ajuda muito a não precisar ficar
// procurando em toda a lista de frames, pois é quase certo que
// o próximo tempo pode ser o mesmo frame ou o próximo
// frame, isso só em animação linear, mas se caso for pegar
// um tempo aleatório é praticamente inútil.
animation(vector &v): lastTime(0), lastFrame(0){};
~animation(){
frames.clear();
};
// função melhorada para animação linear/sequencial
float get(float time){
int i = 0;
if (time >= lastTime && time <= frames[frames.size()-1].time)
i = lastFrame;
for (; i < frames.size(); i++){
if (frames[i].time >= time && frames[i-1].time <= time){
lastFrame = i-1;
lastTime = time;
return bezier(frames[i-1], frames[i], time);
};
};
};
};
A future modification will be to move lastTime and lastFrame out of the class, into the code they call by get() and pass the values lastTime and lastFrame as an argument, because more than one object may be using the same animation accessing different times. I haven’t implemented yet, but I believe that binary search can bring great savings of comparisons (in non-sequential random accesses), providing gains in performance and lower CPU usage, which is my goal.
But my question is still: Is the use of the last time and frame result for linear execution and binary search for random access cases the best optimization possible to use? Or is there some more efficient alternative or some more test that can further decrease the amount of time comparisons?