Интерполяция NURBS кривой

[renegator]

У меня есть задача - интерполировать точки на плоскости кривой NURBS. 3-й степени, например. Т.е. по n заданным точкам найти контрольные точки NURBS. Задача несложная, сводится к решению СЛАУ с трехдиагональной матрицей (в случае кривой 3-й степени). Но есть подробность - сделать интерполяцию так, как в довольно известной Rhinoceros 3D. Решение СЛАУ, построенной по n точкам дает n контрольных точек. А вот как строит Rhino:


Как вы видите, по 4 точкам он построил кривую с 6-ю контрольными точками. 2 крайние совпадают с точками интерполяции, а 2 дополнительные - на касательных в этих точках

Вот интерполяция по трем точкам:


В связи с этим вопрос: как можно выбрать направление касательной? Автор Rhino мистер Макнил меня с этим вопросом послал. Попытка провести локальную кривую Безье и взять касательную к ней дает не то

[Panfilov]

renegator в сообщении #922066 писал(а):

Вот интерполяция по трем точкам:

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

renegator в сообщении #922066 писал(а):

А вот как строит Rhino:

Картинка вполне соответствует такому варианту.

Вот любопытная ссылка по теме (сам полностью еще не вникал)
http://rznusl.ucoz.ru/forum/50-123-1

Мой вопрос по схожей теме. post918508.html#p918508
Надеюсь информация полезна, хотя не на поставленный вопрос.

[Алексей К.]

Вы пишете про NURBSы, и при этом не упоминаете важного понятия knot vector.
Построение NURBS-кривой определяется не только контрольными точками, а зависит от этого вектора (по сути, способа разбиения интервала параметра $[t_{\min}; t_{\max}]$ на участки; в частности, некоторые участки могут быть нулевой длины).

Известно ли Вам, что NURBS-кривая с четырьмя контрольными точками может быть просто ломаной, соединяющей эти точки? А может быть приливычной гладенькой кривой Безье. Или парой коник, гладко сопряжённых. И, похоже, необязательно будет начинаться в первой контрольной точке и заканчиваться в последней.

Я не знаю, по каким принципам строит Rhino (когда-то видел этот ресурс), но скорее всего, ежели ему подали так мало информации (всего лишь контрольные точки), то остальное он восполняет какими-то default'ами. И от Вашего NURBS остаётся только RBS, или NUBS, а то и просто BS.

renegator в сообщении #922066 писал(а):

как можно выбрать направление касательной? Автор Rhino мистер Макнил меня с этим вопросом послал.

David Rogers в гл.3.5 книги An Introduction to NURBS писал(а):

The behavior of an open B-spline curve is in many respects analogous to that of Bezier curve. ... For an open B-spline curve of any order the first and last points of the curve are coincident with the first and last polygon vertices. Furthermore, the slope of the B-spline curve at the first and last polygon vertices is equal to the slope of the first and last polygon spans.

(насколько я понял, "open B-spline curve" здесь не означает "незамкнутую кривую", а означает кривую с open knot vector'ом, т.е. вектором с определённой кратностью точек та концах, типа 0,0,0,1/3,2/3,1,1,1).

(Оффтоп)

Скорее всего, мистер Макнил послал Вас отказался Вам помогать по той причине, что испугался: он понял, что Вам надо излагать целый курс теории NURBS. А эта штука требует основательного знания математики. В отличие от игрушки --- двигания контрольных точечек кривой Безье, чем может поразвлекать себя любая домохозяйка, пока жарится лук.

15 лет назад, делая шабашку, я хорошо (а может и досконально) разобрался с NURBS, и даже купил себе вышепроцитированную книжку. Потом, не пользуясь более этим инструментом, столь же основательно его позабыл.
Боясь наговорить глупостей, я два дня не писал в эту тему --- надеялся, что кто-то всё знает и отпишется. Сегодня, прежде чем писать, я к утреннему кофию открыл ту книжку и около часа восстанавливал память (в выходной можно). С нубсами разобрался, но на нуpбсах заглох... Захотелось чего-то попроще --- луку пожарить, или постирать чего-нибудь, или даже JPEG2000 поучить...

Повторюсь:

Алексей К. в сообщении #485303 писал(а):

Нурбсами предлагаю не заморачиваться. Сделают они то же самое, только у Вас будет ещё перелом головы.

[renegator]

Panfilov в сообщении #922622 писал(а):

renegator в сообщении #922066 писал(а):

Вот интерполяция по трем точкам:

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

renegator в сообщении #922066 писал(а):

А вот как строит Rhino:

Картинка вполне соответствует такому варианту.

При количестве точек, которое Вы назвали - конечно. Но Rhino не ограничивает себя локальной интерполяцией. Это глобальная интерполяция - вот например по 7 точкам:


-- 25.10.2014, 14:12 --

Алексей К. в сообщении #922811 писал(а):

Вы пишете про NURBSы, и при этом не упоминаете важного понятия knot vector.
Построение NURBS-кривой определяется не только контрольными точками, а зависит от этого вектора (по сути, способа разбиения интервала параметра $[t_{\min}; t_{\max}]$ на участки; в частности, некоторые участки могут быть нулевой длины).

Я ориентируюсь на книжку Piegl, Tiller "The NURBS Book". В главе 9.2 описана именно глобальная интерполяция с различными заданными параметрами . В 9.2.1 приведено несколько вариантов расчета узловых векторов - я использовал "по длине хорды" (chord length).

Алексей К. в сообщении #922811 писал(а):

Известно ли Вам, что NURBS-кривая с четырьмя контрольными точками может быть просто ломаной, соединяющей эти точки? А может быть приливычной гладенькой кривой Безье. Или парой коник, гладко сопряжённых. И, похоже, необязательно будет начинаться в первой контрольной точке и заканчиваться в последней.

Я не знаю, по каким принципам строит Rhino (когда-то видел этот ресурс), но скорее всего, ежели ему подали так мало информации (всего лишь контрольные точки), то остальное он восполняет какими-то default'ами. И от Вашего NURBS остаётся только RBS, или NUBS, а то и просто BS.

Это не контрольные точки, а точки интерполяции, заметьте. Кривая обязана через них проходить и конечные точки тут обязательно совпадают с контрольными.
Мои клиенты просят проникнуть именно в ход мыслей Макнила и употребляют слово NURBS. Может быть, кому то известны априорные, эвристические или иные резоны выбрать направление касательных на на конечных точках?

renegator в сообщении #922066 писал(а):

как можно выбрать направление касательной? Автор Rhino мистер Макнил меня с этим вопросом послал.

David Rogers в гл.3.5 книги An Introduction to NURBS писал(а):

The behavior of an open B-spline curve is in many respects analogous to that of Bezier curve. ... For an open B-spline curve of any order the first and last points of the curve are coincident with the first and last polygon vertices. Furthermore, the slope of the B-spline curve at the first and last polygon vertices is equal to the slope of the first and last polygon spans.

(насколько я понял, "open B-spline curve" здесь не означает "незамкнутую кривую", а означает кривую с open knot vector'ом, т.е. вектором с определённой кратностью точек та концах, типа 0,0,0,1/3,2/3,1,1,1).

Алексей К. в сообщении #922811 писал(а):

(Оффтоп)

Скорее всего, мистер Макнил послал Вас отказался Вам помогать по той причине, что испугался: он понял, что Вам надо излагать целый курс теории NURBS. А эта штука требует основательного знания математики. В отличие от игрушки --- двигания контрольных точечек кривой Безье, чем может поразвлекать себя любая домохозяйка, пока жарится лук.

15 лет назад, делая шабашку, я хорошо (а может и досконально) разобрался с NURBS, и даже купил себе вышепроцитированную книжку. Потом, не пользуясь более этим инструментом, столь же основательно его позабыл.
Боясь наговорить глупостей, я два дня не писал в эту тему --- надеялся, что кто-то всё знает и отпишется. Сегодня, прежде чем писать, я к утреннему кофию открыл ту книжку и около часа восстанавливал память (в выходной можно). С нубсами разобрался, но на нуpбсах заглох... Захотелось чего-то попроще --- луку пожарить, или постирать чего-нибудь, или даже JPEG2000 поучить...

Повторюсь:

Алексей К. в сообщении #485303 писал(а):

Нурбсами предлагаю не заморачиваться. Сделают они то же самое, только у Вас будет ещё перелом головы.

:) Кроме коммерческой Rhino Макнил разрабатывает открытую OpenNURBS, которая, тем не менее не содержит функций интерполяции. Вот включил бы туда - и я бы не мешал Вам и Макнилу спокойно пить кофе

[Panfilov]

renegator в сообщении #922826 писал(а):

Может быть, кому то известны априорные, эвристические или иные резоны выбрать направление касательных на на конечных точках?

renegator в сообщении #922826 писал(а):

Это глобальная интерполяция - вот например по 7 точкам:

Извиняюсь за свое участие с популярной математикой. Видел нечто подобное в статье журнала "Квант" Н.Б. Васильева "Гексаграммы Паскаля и кубические кривые" например издание Н.Б.Васильев "Избранные статьи" Москва 1998г. стр.107.

[Алексей К.]

renegator в сообщении #922826 писал(а):

кому то известны априорные, эвристические или иные резоны выбрать направление касательных на на конечных точках?

Дугу окружности (прямой, как возможного частного случая) через 3 соседние точки проведите, и позаимствуйте у неё наклон касательной. Просто и надёжно.
Про параболу и другие коники подумать надо.

-- 25 окт 2014, 18:50:00 --

Параболу (прямую, как возможный частный случай) тоже, наверное, можно через любые три точки плоскости провести, но там не будет гарантии что она проходит через $1\to2\to3$. А построение $1\to3\to2$ Вас не устроит.
А у окружности будет гарантия.