Оценка кривой Безье

Question

Я следую этой статье здесь, используя алгоритм де Кастельжау http://www.cgafaq.info/wiki/B%C3%A9zier_curve_evaluation, и я попытался использовать тему Рисование кривых Безье с использованием алгоритма Де Кастельжау в C ++, OpenGL .Безуспешно.

Мои кривые Безье при оценке выглядят так:

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

Вот мои точки на верхней кривой на этом изображении: (0,0) (2,0) (2,2) (4,2) Вторая кривая использует тот же набор точек, за исключением того, что третья точка - это (0,2), то есть на две единицы выше первой точки, образуя более крутую кривую.

Что-то не так.Я должен положить 0,25 для t, и он должен выплевывать 1,0 для значения X, а 0,75 всегда должен возвращать 3. Предположим, t - время.Это должно прогрессировать с постоянной скоростью, да?Точно 25% пути, значение X должно быть 1,0, а затем Y должен быть связан с этим значением.

Есть ли адекватные способы для оценки кривой Безье?Кто-нибудь знает, что здесь происходит?

Спасибо за любую помощь!:)

РЕДАКТИРОВАТЬ ------

Я нашел эту книгу в поиске Google http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf и вот страница, которую я нашел в явном виде/ непараметрические кривые Безье.Это полиномы, представленные в виде кривых Безье, что я и собираюсь здесь представить.Вот эта страница из книги:

Кто-нибудь знает, как преобразовать кривую Безье в параметрическую кривую?Теперь я могу открыть другую ветку ...

РЕДАКТИРОВАТЬ СНОВА С 1 НОЯБРЯ 2011 г. -------

Я понял, что был толькозадавать вопрос примерно вдвое яснее, чем следовало.То, что я пытаюсь построить, похоже на редактор анимационных графиков Maya, такой как http://www.youtube.com/watch?v=tckN35eYJtg&t=240, где контрольные точки Безье, которые используются для изменения кривой, больше похожи на модификаторы касательной одинаковой длины.Я не помню их равной длины, если честно.Используя такую ​​систему, вы можете на 100% убедиться, что результат является функцией и не содержит перекрывающихся сегментов.

Я нашел это, и на мой ответ может быть http://create.msdn.com/en-US/education/catalog/utility/curve_editor

Answer 1

Здесь вы можете увидеть алгоритм, реализованный в Mathematica, следуя номенклатуре в вашей ссылке , и вашим двум графикам:

(*Function Definitions*)

lerp[a_, b_, t_] := (1 - t) a + t b;
pts1[t_] := {
   lerp[pts[[1]], pts[[2]], t],
   lerp[pts[[2]], pts[[3]], t],
   lerp[pts[[3]], pts[[4]], t]};
pts2[t_] := {
   lerp[pts1[t][[1]], pts1[t][[2]], t],
   lerp[pts1[t][[2]], pts1[t][[3]], t]};
pts3[t_] := {
   lerp[pts2[t][[1]], pts2[t][[2]], t]};

(*Usages*)

pts = {{0, 0}, {2, 0}, {2, 2}, {4, 2}};
Framed@Show[ParametricPlot[pts3[t], {t, 0, 1}, Axes -> True], 
            Graphics[{Red, PointSize[Large], Point@pts}]]

pts = {{0, 0}, {2, 0}, {0, 2}, {4, 2}};
Framed@Show[ParametricPlot[pts3[t], {t, 0, 1}, Axes -> True], 
            Graphics[{Red, PointSize[Large], Point@pts}]]

BTW,кривые определяются следующими параметрическими уравнениями, которые являются функциями pts3[t] в приведенном выше коде:

c1[t_] := {2 t (3 + t (-3 + 2 t)), (* <- X component *)
                 2 (3 - 2 t) t^2}  (* <- Y component *)

и

c2[t_] := {2 t (3 + t (-6 + 5 t)), (* <- X component *)
               , 2 (3 - 2 t) t^2}  (* <- Y component *)

Попробуйте построить их!

Взяв любое из этих кривых уравнений и решив кубический многочлен, вы можете в этих случаях получить выражение для y [x], что, конечно, не всегда возможно.Просто для того, чтобы вы почувствовали его вкус, начиная с первой кривой (синтаксис C):

y[x]= 3 - x - 3/Power(-2 + x + Sqrt(5 + (-4 + x)*x),1/3) + 
              3*Power(-2 + x + Sqrt(5 + (-4 + x)*x),1/3)

Try plotting it!

Редактировать

Просто забавы:

Mathematica - довольно мощный функциональный язык, и фактически весь алгоритм может быть выражен в виде одной строки:

f = Nest[(1 - t) #[[1]] + t #[[2]] & /@ Partition[#, 2, 1] &, #, Length@# - 1] &

Такая

f@{{0, 0}, {2, 0}, {0, 2}, {4, 2}}

дает приведенные выше результаты, но поддерживает любое количество баллов.

Давайте попробуем с шестью случайными точками:

p = RandomReal[1, {6, 2}];
Framed@Show[
  Graphics[{Red, PointSize[Large], Point@p}],
  ParametricPlot[f@p, {t, 0, 1}, Axes -> True]]

Более того, эта же функция работает в 3D:

p = RandomReal[1, {4, 3}];
Framed@Show[
  Graphics3D[{Red, PointSize[Large], Point@p}],
  ParametricPlot3D[f[p], {t, 0, 1}, Axes -> True]]

Answer 2

Кривая Безье может быть решена путем решения следующих параметрических уравнений для координат x, y и z (если это просто 2D, делайте только x и y):

Px = (1-t)^3(P1x) + 3t(1-t)^2(P2x) + 3t^2(1-t)(P3x) + t^3(P4x)
Py = (1-t)^3(P1y) + 3t(1-t)^2(P2y) + 3t^2(1-t)(P3y) + t^3(P4y)
Pz = (1-t)^3(P1z) + 3t(1-t)^2(P2z) + 3t^2(1-t)(P3z) + t^3(P4z)

Вы также можете решитьэто путем умножения матричного уравнения ABC = X, где:

1. матрица A является матрицей 1x4 и представляет значения степеней t
2. , матрица B - коэффициентыстепеней t и представляет собой матрицу 4x4 в нижней треугольнике
3. матрица C представляет собой матрицу 4x3, которая представляет каждую из четырех точек Безье в 3D-пространстве (это будет матрица 4x2 в 2D-пространстве)

Это будет выглядеть следующим образом:

(Обновление - нижний левый 1 должен быть -1)

Важным примечанием в обеих формах уравнения (параметрической и матричной формах) является то, что t находится в диапазоне [0, 1].

Вместо того, чтобы пытаться решитьзначения для t, которые дадут вам интегральные значения x и y, что будетотнимает много времени, учитывая, что вы в основном решаете для реального корня многочлена 3-й степени, гораздо лучше просто создать достаточно маленький дифференциал в вашем t значении, чтобы разница между любыми двумя точками на кривой была меньшечем приращение значения пикселя.Другими словами, расстояние между двумя точками P(t1) и P(t2) таково, что оно меньше значения пикселя.В качестве альтернативы, вы можете использовать больший дифференциал в t и просто линейно интерполировать между P(t1) и P(t2), имея в виду, что кривая может быть не "гладкой", если дифференциал между P(t1) и P(t2) равеннедостаточно маленький для заданного диапазона t из [0, 1].

Хороший способ найти необходимый дифференциал в t для создания довольно «гладкой» кривой с визуальной точки зрения состоит в том, чтобына самом деле измерить расстояние между четырьмя точками, которые определяют кривую Безье.Измерьте расстояние от P1 до P2, от P2 до P3 и от P3 до P4.Затем возьмите самое длинное расстояние и используйте обратное значение этого значения в качестве дифференциала для t.Возможно, вам все-таки потребуется выполнить некоторую линейную интерполяцию между точками, но количество пикселей в каждой «линейной» подкриве должно быть довольно небольшим, и поэтому сама кривая будет выглядеть довольно гладкой.Вы всегда можете уменьшить дифференциальное значение на t от этого начального значения, чтобы сделать его «более плавным».

Наконец, чтобы ответить на ваш вопрос:

Предположим, что это время.Это должно прогрессировать с постоянной скоростью, да?Точно 25% пути, значение X должно быть 1,0, а затем Y должен быть связан с этим значением.

Нет, это не правильно, и причина в том, что векторы (P2- P1) и (P3 - P4) не только касаются кривой Безье в точках P1 и P4, но и их длины определяют скорость вдоль кривой в этих точках.Таким образом, если вектор (P2 - P1) находится на небольшом расстоянии, это означает, что в течение заданного промежутка времени t вы не будете перемещаться очень далеко от точки P1 ... это переводится в значения x, y вдольКривая очень плотно упакована для заданного фиксированного дифференциала t.Вы эффективно «замедляете» скорость по мере продвижения к P1.Тот же эффект имеет место в точке P4 на кривой в зависимости от длины вектора (P3 - P4).Единственный способ, которым скорость вдоль кривой будет «постоянной», и, следовательно, расстояние между любыми точками для общего дифференциала t будет одинаковым, будет, если длины всех трех сегментов (P2 - P1),(P3 - P2) и (P4 - P3) были одинаковыми.Тогда это указывало бы на то, что вдоль кривой не было изменений скорости.

Answer 3

Похоже, что вы на самом деле просто хотите 1D кубическую кривую Безье вместо 2D, который у вас есть. В частности, то, что вам действительно нужно, это просто кубический полиномиальный сегмент, который начинается с 0 и достигает 2 при оценке по области от 0 до 4. Таким образом, вы можете использовать некоторую базовую математику и просто найти полином:

f(x) = a + b*x + c*x^2 + d*x^3
f(0) = 0
f(4) = 2

Это оставляет две степени свободы.
Возьмем производную функции:

f'(x) = b + 2*c*x + 3*d*x^2

Если вы хотите, чтобы он был крутым в начале, а затем выровнялся в конце, вы можете сказать что-то вроде:

f'(0) = 10
f'(4) = 0

Тогда мы можем включить значения. a и b приходят бесплатно, потому что мы оцениваем в ноль.

a = 0
b = 10

Итак, мы имеем:

f(4) = 2 = 40 + c*16 + d*64
f'(4) = 0 = 10 + c*8 + d*48

Это довольно простая линейная система для решения. Для полноты мы получаем:

16c + 64d = -38
 8c + 48d = -10

1024 * Так что- *

1/(16*48 - 8*64)|48 -64||-38| = |c| = |-37/8 |
                |-8  16||-10|   |d|   |  9/16|

f(x) = 10*x - (37/8)*x^2 + (9/16)*x^3

Если вместо этого вы решите, что хотите использовать контрольные точки Безье, просто выберите свои 4 контрольные точки значения y и узнайте, что для получения t в [0,1], вы просто должен сказать t=x/4 (помня, что если вам также нужны производные, вам тоже придется внести изменения).

---

Добавлено:

Если вам известны точки и производные, которые вы хотите начать и закончить, но вы хотите использовать контрольные точки Безье P1 , P2 , P3 и P4 , отображение как раз (при условии, что кривая параметризована от 0 до 1):

P1 = f(0)
P2 = f'(0)/3 + f(0)
P3 = f(1) - f'(1)/3
P4 = f(1)

Если по какой-то причине вы хотели придерживаться контрольных точек 2D Безье и хотели, чтобы размер x линейно увеличивался с 0 до 2, тогда как t повышался с 0 до 1, то вы можете сделать это с контрольными точками (0,y1) (2/3,y2) (4/3,y3) (2,y4). Вы можете видеть, что я только что сделал размерность x , начинающуюся с 0, заканчивающуюся 2, и имеющую постоянный наклон (производную) 2 (относительно t ). Тогда вы просто делаете Y-координату такой, какой вам нужна. Различные размеры по существу не зависят друг от друга.

Answer 4

«Предположим, что это время.»

Это проблема - не время. Кривая имеет собственную скорость изменения t в зависимости от величины касательных. Как сказал Джейсон, расстояние между последовательными точками должно быть одинаковым, чтобы t было таким же, как время. Это именно то, что представляет собой невзвешенный режим (который используется по умолчанию) в редакторе кривых Maya. Так что это был очень хороший ответ, как решить эту проблему. Чтобы это работало для произвольных касательных, вы должны преобразовать время в t. Вы можете найти t, рассчитав уравнение Безье в направлении x (или времени).

Px = (1-t) ^ 3 (P1x) + 3t (1-t) ^ 2 (P2x) + 3t ^ 2 (1-t) (P3x) + t ^ 3 (P4x)

Пкс - твое время, так что ты все здесь знаешь, кроме т. Вы должны решить кубическое уравнение, чтобы найти корни. Есть хитрая часть, чтобы найти точный корень, который вам нужен. Затем вы решаете другое уравнение, чтобы найти Py (фактическое значение, которое вы ищете), зная теперь t:

Py = (1-t) ^ 3 (P1y) + 3t (1-t) ^ 2 (P2y) + 3t ^ 2 (1-t) (P3y) + t ^ 3 (P4y)

Это и есть весовые кривые в майя. Я знаю, что вопрос старый, но я потерял целый день, исследуя эту простую вещь, и никто точно не объясняет, что происходит. В противном случае сам процесс расчета написан во многих местах, например, в руководстве по API для Maya. Для этого у Maya devkit также есть исходный код.

Answer 5

После всего этого времени я искал кривые Эрмита.Отшельники хороши тем, что в одном измерении они гарантированно дают функциональную кривую, которая может быть оценена до точки XYЯ путал Эрмита с Безье.