Оптимизация алгоритма параметризации кубической кривой безье

Question

За исключением использования справочных таблиц, есть ли другой способ оптимизировать алгоритм параметризации кубической кривой Безье как это? (5000 шагов для хорошей параметризации просто слишком много для более медленного компьютера, как мне нужно, чтобы вызвать эту функцию много раз в 1 секунду):

function parameterizeCurve(path, partArc, initialT) 
{ 
    // curve length is already known and globally defined 
    // brute force 
    var STEPS = 5000; // > precision 
    var t = 1/STEPS; 
    var aX=0; 
    var aY=0; 
    var bX=path[0], bY=path[1]; 
    var dX=0, dY=0; 
    var dS = 0; 
    var sumArc = 0; 
    var arrT = new Array(Math.round(partArc)); 
    var z = 1; 
    arrT[0] = -1; 

    var oldpartArc = partArc; 
    partArc = partArc - initialT; 

    var j = 0; 

    for (var i=0; i<STEPS; j = j + t) { 
     aX = bezierPoint(j, path[0], path[2], path[4], path[6]); 
     aY = bezierPoint(j, path[1], path[3], path[5], path[7]); 

     dX = aX - bX; 
     dY = aY - bY; 
     // deltaS. Pitagora 
     dS = Math.sqrt((dX * dX) + (dY * dY)); 
     sumArc = sumArc + dS; 
     if (sumArc >= partArc) { 
     arrT[z] = j; // save current t 
     z++; 
     sumArc = 0; 
     partArc = oldpartArc; 
     } 
     bX = aX; 
     bY = aY; 
     i++; 
    } 

    return arrT; 
} 


    function bezierPoint(t, o1, c1, c2, e1) { 
     var C1 = (e1 - (3.0 * c2) + (3.0 * c1) - o1); 
     var C2 = ((3.0 * c2) - (6.0 * c1) + (3.0 * o1)); 
     var C3 = ((3.0 * c1) - (3.0 * o1)); 
     var C4 = (o1); 

     return ((C1*t*t*t) + (C2*t*t) + (C3*t) + C4) 
    } 

Answer 1

Если я угадал, что вы пытаетесь прийти с кубической параметризацией кривой Безье, которая движется с постоянной скоростью вдоль кривой.

Итак, зачем вам 5000 шагов? Минимальный ход по кривой - один пиксель. Безье остается в выпуклой оболочке четырех контрольных точек, поэтому длина кривой будет меньше длины полилинии P0 -> P1 -> P2 -> P3. Поэтому найдите эту длину в пикселях и используйте ее (вместо 5000).

Сообщите мне, если это ускоряет работу.