Самый быстрый способ рассчитать кубические кривые Безье?

Question

Прямо сейчас я вычисляю это так:

    double dx1 = a.RightHandle.x - a.UserPoint.x;
    double dy1 = a.RightHandle.y - a.UserPoint.y;
    double dx2 = b.LeftHandle.x - a.RightHandle.x;
    double dy2 = b.LeftHandle.y - a.RightHandle.y;
    double dx3 = b.UserPoint.x - b.LeftHandle.x;
    double dy3 = b.UserPoint.y - b.LeftHandle.y;

    float len = sqrt(dx1 * dx1 + dy1 * dy1) + 
        sqrt(dx2 * dx2 + dy2 * dy2) + 
        sqrt(dx3 * dx3 + dy3 * dy3);




    int NUM_STEPS =  int(len * 0.05);

    if(NUM_STEPS > 55)
    {
        NUM_STEPS = 55;
    }
    double subdiv_step  = 1.0 / (NUM_STEPS + 1);
    double subdiv_step2 = subdiv_step*subdiv_step;
    double subdiv_step3 = subdiv_step*subdiv_step*subdiv_step;

    double pre1 = 3.0 * subdiv_step;
    double pre2 = 3.0 * subdiv_step2;
    double pre4 = 6.0 * subdiv_step2;
    double pre5 = 6.0 * subdiv_step3;



    double tmp1x = a.UserPoint.x - a.RightHandle.x * 2.0 + b.LeftHandle.x;
    double tmp1y = a.UserPoint.y - a.RightHandle.y  * 2.0 + b.LeftHandle.y;

    double tmp2x = (a.RightHandle.x - b.LeftHandle.x)*3.0 - a.UserPoint.x + b.UserPoint.x;
    double tmp2y = (a.RightHandle.y - b.LeftHandle.y)*3.0 - a.UserPoint.y + b.UserPoint.y;

    double fx = a.UserPoint.x;
    double fy = a.UserPoint.y;

    //a user
    //a right
    //b left
    //b user

    double dfx = (a.RightHandle.x - a.UserPoint.x)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
    double dfy = (a.RightHandle.y - a.UserPoint.y)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3;

    double ddfx = tmp1x*pre4 + tmp2x*pre5;
    double ddfy = tmp1y*pre4 + tmp2y*pre5;

    double dddfx = tmp2x*pre5;
    double dddfy = tmp2y*pre5;

    int step = NUM_STEPS;



    while(step--)
    {


        fx   += dfx;
        fy   += dfy;
        dfx  += ddfx;
        dfy  += ddfy;
        ddfx += dddfx;
        ddfy += dddfy;
        temp[0] = fx;
        temp[1] = fy;
        Contour[currentcontour].DrawingPoints.push_back(temp);
    }


    temp[0] = (GLdouble)b.UserPoint.x;
    temp[1] = (GLdouble)b.UserPoint.y;
    Contour[currentcontour].DrawingPoints.push_back(temp);

Мне интересно, есть ли более быстрый способ интерполировать кубические Безье?

Спасибо

Answer 1

Посмотрите на прямое дифференцирование для более быстрого метода. Необходимо соблюдать осторожность при устранении ошибок округления.

Метод адаптивного подразделения с некоторыми проверками может быть быстрым и точным.

Answer 2

Есть еще один момент, который также очень важен, это то, что вы аппроксимируете свою кривую, используя множество прямых отрезков фиксированной длины.Это неэффективно в областях, где ваша кривая почти прямая, и может привести к неприятной угловой ломаной линии, где кривая очень изогнута.Не существует простого компромисса, который будет работать для высокой и низкой кривизны.

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

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

Как только вы нарисуете «хорошо», вы можете посмотреть, как сделать необходимые вычисления «быстрее».

Answer 3

Обратите внимание, как можно рассчитать «достаточно плоский». «Плоскостность» представляет собой меру минимального абсолютного угла (между 0 и 180 °) между двумя последовательными сегментами, но вам не нужно вычислять фактический угол, потому что эта плоскостность также эквивалентна установке минимального значения в косинус . от их относительного угла.

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

Обратите внимание, что "квадрат косинуса" также "один минус квадрат синуса". Максимальное значение квадратного косинуса также является минимальным значением квадратного синуса ... Теперь вы знаете, какой тип «векторного произведения» использовать: самым быстрым и простым для вычисления является скалярное произведение, квадрат которого пропорционален квадратному синусу двух векторы и на произведение длин квадратов обоих векторов.

Таким образом, проверить, является ли кривая «достаточно плоской», просто: вычислите отношение между двумя скалярными произведениями и посмотрите, находится ли это отношение ниже значения константы «плоскостности» (минимального квадратного синуса). Нет деления на ноль, потому что вы определите, какой из двух векторов самый длинный, и если этот квадрат имеет длину квадрата меньше 1/4, ваша кривая уже достаточно плоская для разрешения рендеринга; в противном случае проверьте это соотношение между самым длинным и самым коротким вектором (образованным пересечением диагоналей выпуклой оболочки, содержащей конечные точки и контрольные точки):

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

• с кубическими Безье выпуклый корпус представляет собой выпуклый многоугольник с 4 сторонами, и диагонали могут либо соединять конечную точку с одной из двух контрольных точек, либо соединять вместе две конечные точки и две контрольные точки и у вас есть шесть возможностей

Используйте комбинацию, дающую максимальную длину для первого вектора между 1-й конечной точкой и одной из трех других точек, второй вектор соединяет две другие точки):

• Все, что вам нужно, это определить «минимальную квадратную длину» сегментов, начиная с одной конечной точки или контрольной точки до следующей контрольной точки или конечной точки в последовательности. (в квадратичном Безье вы просто сравниваете два сегмента, с квадратичным Безье вы проверяете 3 сегмента)

• Если эта «минимальная длина квадрата» меньше 1/4, вы можете остановиться там, кривая «достаточно плоская».

• Затем определите «максимальную квадратную длину» сегментов, начиная с одной конечной точки до любой другой конечной точки или контрольной точки (с квадратичным Безье вы можете безопасно использовать те же 2 сегмента, что и выше, с кубическим Безье вы отбрасываете один из 3 сегментов, использованных выше, соединяя две контрольные точки, но добавляете сегмент, соединяющий два конечных узла).

• Затем убедитесь, что «минимальная длина квадрата» меньше, чем произведение постоянной «плоскостности» (минимального синуса квадрата) на «максимальную длину квадрата» (если так, то кривая «достаточно плоская».

• В обоих случаях, когда ваша кривая "достаточно плоская", вам просто нужно нарисовать отрезок, соединяющий две конечные точки. В противном случае вы рекурсивно разбиваете сплайн.

Вы можете включить ограничение рекурсии, но на практике оно никогда не будет достигнуто, если выпуклая оболочка кривой не покрывает очень большую область в очень большой области рисования; даже с 32 уровнями отказов он никогда не взорвется в прямоугольной области рисования, диагональ которой меньше 2 ^ 32 пикселей (предел будет достигнут только в том случае, если вы разбиваете «виртуальный Безье» на практически бесконечное пространство с плавающей точкой координаты, но вы не собираетесь рисовать его напрямую, потому что у вас не будет ограничения в 1/2 пикселя в таком пространстве, и только если вы установите значение extreme для "плоскостности", так что ваш постоянный параметр "минимальный квадратный синус" равен 1/2 ^ 32 или ниже).

Answer 4

На самом деле вы должны продолжать расщепление до тех пор, пока две линии, соединяющие точки на кривой (конечные узлы) и их самые дальние контрольные точки, не станут «достаточно плоскими»: - либо полностью выровнены, либо - их пересечение находится в положении, «квадратное расстояние» которого от обоихконечные узлы меньше половины "квадратного пикселя") - обратите внимание, что вам не нужно вычислять фактическое расстояние, так как это потребует вычисления квадратного корня, что очень медленно)

Когда вы достигнете этой ситуации,игнорируйте контрольные точки и соедините две конечные точки с прямым отрезком.

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

Примечание: вы должны учитывать дробные биты конечных точек, чтобы правильно установить начальное значение переменной ошибки, накапливающей различия и используемой инкрементным алгоритмом Брезенхэма, чтобы получить лучшие результаты (особенно когдапоследний сегмент для рисования оченьблизко от горизонтали или вертикали или от двух диагоналей);в противном случае вы получите видимые артефакты.

Классический алгоритм Брезенхема для рисования линий между точками, которые выровнены на целочисленной сетке, инициализирует эту переменную ошибки в ноль для позиции первого конечного узла.Но незначительная модификация алгоритма Брезенхема масштабирует две переменные расстояния и значение ошибки просто на постоянную степень два, прежде чем использовать приращения 0 / + 1 для переменной x или y, которые остаются немасштабированными.

Старшие биты переменной error также позволяют вычислять альфа-значение, которое можно использовать для рисования двух сложенных пикселей с правильной альфа-заливкой.В большинстве случаев ваши изображения будут использовать не более 8-битных цветовых плоскостей, поэтому вам не потребуется более 8 бит дополнительной точности для значения ошибки, а масштабирование может быть ограничено коэффициентом 256: вы можете использовать егорисовать «плавные» линии.

Но вы можете ограничиться коэффициентом масштабирования 16 (четыре бита): типичные растровые изображения, которые вы должны рисовать, не очень широки, а их разрешение намного ниже +/- 2миллиарды (предел 32-разрядного целого числа со знаком): когда вы увеличите координаты в 16 раз, для работы останется 28 битов, но вы уже должны были «обрезать» геометрию до области просмотра вашегорастровое изображение для рендеринга, и переменная ошибки алгоритма Брезенхэма во всех случаях останется ниже 56 битов и все равно поместится в 64-битное целое число.

Если ваша переменная ошибки 32-битная, вы должны ограничитьмасштабированные координаты ниже 2 ^ 15 (не более 15 бит) для наихудшего случая (в противном случае проверка знака допустимой ошибки, используемая Брезенхэмом, будетЯ не работаю из-за целочисленного переполнения в худшем случае), и с коэффициентом масштабирования 16 (4 бита) вы будете ограничены в рисовании изображений размером не более 11 бит в ширину или высоту, то есть 2048x2048 изображений.

Но если ваша область рисования эффективно меньше 2048x2048 пикселей, нет проблем с рисованием линий, сглаженных по 16 альфа-закрашенным значениям цвета рисования (чтобы нарисовать альфа-заштрихованные пиксели, вам нужно прочитать значение пиксела оригинала в изображении досмешивание альфа-затененного цвета, если только вычисленный оттенок не равен 0% для первого пикселя с разбивкой, который вам не нужно рисовать, и 100% для второго скомпонованного пикселя, который можно перезаписать непосредственно с помощью обычного цвета рисования)

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

С переменной ошибки, используемой алгоритмом Брезенхэма, вообще нет проблем, вызванных ошибками округления, поскольку они учитываются этой переменной. Поэтому установите его начальное значение правильно (альтернатива, просто увеличив масштаб всех координат в 16 раз, прежде чем начать рекурсивное деление, сплайн в 16 раз медленнее в самом алгоритме Брезенхэма).