2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Кубический сплайн
Сообщение27.04.2006, 11:54 


27/04/06
5
Добрый день!

Передо мной стоит задача построения кубического сплайна по заданным (четырем) точкам (сплайны Безье, Т- и Б-сплайны и NURBS не подходят ввиду того, что сплайн должен проходить через контрольные точки). Выбор остановился на Cardinal, Catmull-Rom, Kochanek-Bartels сплайнах. Все они дают примерно одинаковые результаты. Если пропустить все выкладки, получим следующее: Есть 4 контрольные точки Р1, Р2, Р3, Р4 и нужно интерполировать сплайн между Р2 и Р3

S = \left | \begin{array}{c}s^3\\s^2\\s\\1\end{array}\right |, где s- положение искомой точки (0...1)

C = \left | \begin{array}{c}P2\\P3\\T2\\T3\end{array}\right | - вектор параметров кривой

Т2 = 0.5*(Р3-Р1), Т3 = 0.5*(Р4-Р2)
Вектор С может состоять и из |Р1,Р2,Р3,Р4| в зависимости от типа сплайна

и наконец матрица полиномов, например для hermite
сплайнов она имеет вид

h =\left | \begin{array}{cccc} 2&-2&1&1\\-3&3&-2&-1\\0&0&1&0\\1&0&0&0\end{array}\right |

Тогда искомые точки сплайна находятся как:

P = S * h * C.

Для Catmull-Rom сплайнов имеет место такая формула:
q(t) = 0.5*\left | \begin{array}{c}s^3\\s^2\\s\\1\end{array}\right |*
\left | \begin{array}{cccc} -1&3&-3&1\\2&-5&4&-1\\-1&0&1&0\\0&2&0&0\end{array}\right |*
 \left | \begin{array}{c}P2\\P3\\P2\\P3\end{array}\right |
и опять же матрица полиномов.

Теперь собственно сам вопрос. Как находится эта матрица полиномом?

И так как из вопроса видно, что я далек от математики, может уважаемые подскажут, как изменить/найти значения полиномов, чтобы сплайн приобрел более округлую форму?

как есть:
Изображение

как хотелось бы:
Изображение

---
Не тот раздел был. (dm)

 Профиль  
                  
 
 
Сообщение28.04.2006, 04:06 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Вы не могли бы

а) повторить (а лучше -- отредактировать) Ваши выкладки, используя math? Использование тега не обязательно, достаточно использовать знак долара вокруг формул. Без math же Ваш текст совершенно невозможно прочитать.

б) Привести координаты точек, которые Вы использовали для построения картинок? Чтобы можно было сопоставить? Кроме того, на картинках по шесть точек, а в Ваших объяснениях -- четыре.

 Профиль  
                  
 
 
Сообщение28.04.2006, 06:07 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Добавлю еще один вопрос, в несколько другом направлении. Сплайн (двумерный) есть кусочно-кубическая параметрическая кривая, с некоторым условием гладкго соединения между сегментами. Однако, через четыре точки можно провести достаточно много (два свободных параметра) параметрических кубических кривых. Посему вопрос -- пытаетесь ли Вы построить один сегмент сплайна? Или сплайн, концы сегментов которого -- заданные точки?

 Профиль  
                  
 
 
Сообщение28.04.2006, 11:05 


27/04/06
5
Прошу прощения за невнятный вопрос. Это потому, что у меня нет математической базы в
данной теме.

Насчет точек. Контрольных точек может быть неограниченное количество n, но для построения текущего отрезка сплайна необходимы 4ре "текущие" точки. Так для первого отрезка (между Р1 и Р2) мы берем Р1,Р1,Р2,Р3; для второго (между Р2 и Р3) Р1,Р2,Р3,Р4 и так далее. Последний будет вычисляться по контр. точкам Pn-2, Pn-1, Pn, Pn.

Постараюсь по-другому спросить. Есть опять же 4ре точки Р1, Р2, Р3,Р4. Для
того, чтобы построить по ним сплайн необходимо:

Р(t)= Р1*Н1(t) + Р2*Н1(t) + Р3*Н3(t) + Р4*Н4(t), где Н1(t), Н2(t), Н3(t),
Н4(t) некоторые функции (полином?), которые я понаходил в интернете.

Для каждого типа сплайнов (Вezier, Cardinal, Catmull-Rom и пр) эти функции
свои.

Например я использую (по моему Catmull-Rom) :

Н1(t) = 0.5*(-t^3 + 2.0*t^2  - t);

Н2(t) =  0.5*(3.0*t^3 - 5.0*t^2 + 2.0);

Н3(t) = 0.5*(-3.0*t^3 + 4.0*t^2 + t);

Н4(t) = 0.5*(t^3 - t^2).

Сейчас опять могу начать бред нести, но как я понимаю, коэффициенты для t^3,
t^2, t, 1 находятся из полинома. Они же и влияют на то, как будет проходить
сплайн через контрольные точки (ближе к прямой, соединяющей контр. точки,
или дальше от нее - более округло 8-) ). Эти коэффициенты я и записал в
матричной форме в предыдущем сообщении. Если это так, тогда хотелось бы
узнать, как эти коэффициенты находятся или как их можно изменить, для
изменения формы сплайна

 Профиль  
                  
 
 
Сообщение28.04.2006, 19:01 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Большое спасибо за исправление первого сообщения.

Боюсь, однако, Вам придется все же разбираться в математике. Нехитрая она здесь, (полиномы третьего порядка, пара производных, и все на отрезке от 0 до 1 -- в общем, школьная), но все же придется. Иначе будет каша.

Я не уверен, что то, что Вы делаете можно назвать сплайном (я не специалист, гарантировать не буду). Основная проблема -- нету гладкости при соединении сегментов. По одному из определений (быть может, упрощенному) сплайн -- это кусочно-полиномиальная функция, непрерывная вместе с некоторым количеством производных на отрезке, и минимизирующая некоторый функционал (задающий такие свойства, как "округлость", прохождение через контрольные точки и т.п.). То, что делаете Вы не имеет непрерывной даже первую производную (я проверил обе матрицы).

1) рассмотрим что происходит на сегменте.
На самом деле, происходит весьма простая вещь. Полиномы порядка не выше третьего образуют четырехмерное пространство. Мы можем внем выбрать произвольный базис из четырех линейно-независимых полиномов, и тогда любой полином раскладывается по этому базису. В зависимости от базиса, мы получаем разные коэффициенты разложения. Выбор полиномов определяется доступностью параметров. Например, в случае Эрмита, мы имеем: $P_{h}(0) = P_1$, $P_{h}(1) = P_2$, $P_{h}'(0) = P_3$, $P_{h}'(1) = P_4$. То есть, сегмент, построеннй по Эрмиту, проходит через точки $P_1$ и $P_2$, и его производные на концах отрезка задаются $P_3$ и $P_4$. Для Catmull-Rom имеем: $P_{cr}(0) = P_2$, $P_{cr}(1) = P_3$, $P_{cr}'(0) = (P_3-P_1)/2$, $P_{cr}'(1) = (P_4-P_2)/2$. Обратите внимание -- Catmull-Rom проходит через $P_2$ и $P_3$!

Фактически, выбрав систему параметров, мы автоматически выбираем систему полиномов -- она получается решением системы линейных уравнений невысокого порядка (для каждого из базовых полиномов $H_j(t)$ мы рассматриваем систему, когда отвечающий ему параметр $P_j = 1$, а остальные $P_k = 0$). Альтернативный подход -- выбрать базис (например, полиномы Бернштейна $B_j(t) = {\rm C}_3^j (1-t)^{3-j} t^j$ и посмотреть, как лягут точки (кривая Безье; заметьте, как похоже на Catmull-Rom).

2) Построение сплайна.
К сожалению, построение сплайна -- штука более тонкая. Сплайн всегда "глобален" в том смысле, что слегка подвинув $P_N$ мы изменяем поведение сплайна повсюду, в том числе на отрезке $[P_1, P_2]$. Он оптимизирует глобальный функционал, например, изогнутость. Поэтому приходится решать систему порядка $N$ для $N$-точечного сплайна. Другого на дано -- Вы не можете строить сплайн посегментно. Взгляните еще раз на Catmull-Rom: если $P_2$ и $P_3$ расположены близко, а $P_1$ и $P_4$ далеко от них, то сегмент получает неоправданно высокие значения производных, что и приводит к неприятностям -- изгибам, петлям и т.п..

Сплайн же оптимизирует это поведение за счет выбора $P'(0)$ и $P'(1)$. Они не вычисляются явно из заданных точек. Напротив, их нахождение -- серьезная вычислительная работа.

 Профиль  
                  
 
 
Сообщение28.04.2006, 22:38 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Судя по Вашей картинке, Вам нужен кубический сплайн (cubic spline) -- причем именно сплайн. Посмотрите также главу в Numerical Recipes in C.

 Профиль  
                  
 
 
Сообщение02.05.2006, 10:26 


27/04/06
5
Благодарю за ссылки. Но приведенный там алгоритм не борется с петлями и изогнутостями (а именно это мне и нужно)

 Профиль  
                  
 
 
Сообщение02.05.2006, 11:06 


27/04/06
5
>>Они не вычисляются явно из заданных точек. Напротив, их нахождение -- серьезная вычислительная работа.

А может есть какой нибудь явный способ вычисления производных (касательных) по заданным точкам, который бы решал проблемы с петлями? Пусть упрощенный и неточный, но быстрый

 Профиль  
                  
 
 
Сообщение02.05.2006, 19:14 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
PLUG- писал(а):
>>Они не вычисляются явно из заданных точек. Напротив, их нахождение -- серьезная вычислительная работа.

А может есть какой нибудь явный способ вычисления производных (касательных) по заданным точкам, который бы решал проблемы с петлями? Пусть упрощенный и неточный, но быстрый

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

Возвращаясь к петлям. Я не знаю, заметили ли Вы, но все источики строят сплайн с равноотстоящими узлами. Оно, конечно проще, да и нет прямой информации о шаге параметра. Но -- непонятно, почему это так. Если рассматривать кривую как, например, траекторию, то естественный параметр -- это время. То, что мы его потеряли -- еще не повод для того, чтоб считать узлы равноотстоящими. Посему: попробуйте сделать узлы неравномерными. Первое, что приходит в голову -- расстояние между точками как аппроксимация времени. И поэкпериментируйте.

Если Вам что-либо еще нужно, расскажите больше о задаче. А то непонятны граничные условия решения... Что Вам нужно -- время, пространство на диске, время вырезания детали?

 Профиль  
                  
 
 
Сообщение02.05.2006, 19:33 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Если Вам не нужен сплайн, а достаточно семейства кривых Безье, то quick and dirty решения, конечно же, существуют. Например, рассмотрим $P_1, P_2, P_3, P_4$. Каждая пара отрезков $P_1P_2$, $P_2P_3$ и $P_2P_3$, $P_3P_4$ задает два угла -- один больший, другой меньший 180 градусов. Разделим больший биссекрисой. В большинстве случаев эти биссектрисы пересекутся (это не совсем точное утверждение. Имеется в виду, пересекутся в хорошем месте). Возьмите в качестве внутренних контрольных точек середины сторон получившегося треугольника. Если же имеет место быть перегиб ломанной, то можно просто отложить на биссектрисах фиксированную часть $P_2P_3$. Дальше, опять таки, можно констатны сделать функциями углов, и т.п.

В любом случае -- не называйте это сплайном!

 Профиль  
                  
 
 
Сообщение03.05.2006, 09:12 


27/04/06
5
Благодарю за Ваше терпение и ответы! 8-)
1. Насчет биссектрис я думал, но находить по заданным точкам еще одни контрольные точки не очень красиво. Легче уж исходную модель создавать прямо в NURBS или Безье. Но этот подход менее приемлим.
2 Нужна кривая, проходящая через заданные контрольные точки. Что это будет: кубический сплайн, параболический или еще что-то - не так важно. Главное, чтобы ими можно было аппроксимировать почти любую гладкую поверхность. Это необходимо для игрового движка.
3 Основные условия - скорость вычисления интерполирыемых значений кривой, возможность гладкой стыковки двух кривых.
4 Я вот тут поэкспериментировал с Catmull-Rom и Kochanek-Bartels сплайнами. Попробовал убрать петли. Для этого я тангент Т2 = a*(P3-P1) и Т3 = a*(P4-P2) привязал к длине вектора P=P3-P2 (нормировал T2 и умножил на длину P) и так сделал со всеми тангентами - привязал их длину к соответствующему отрезку. Вы скажете, что с математической точки зрения такой подход неверен, т.к. в точке Р3 для отрезка Р2Р3 тангент имеет одну длину, а для Р3Р4 - другую, но с геометрией - все нормально, т.к. тангент и там и там имеет одно направление. Петли убрались, но кривая изменилась так, как будто в сплайне Кочанека-Бартельса изменили один из параметров tension, continuity, bias (жаль картинку вставить нельзя). Не знаете ли почему так?

И еще уточню. Я так замарачиваюсь впринципе только из-за одного, хочу чтобы кривая описала окружность 4мя точками. NURBS и Безье сплайны - описывают (с небольшой погрешностью), а у сплайнов, которые проходят через контрольные точки (Catmull-Rom, Kochanek-Bartels, Cardinal и пр ) получается что-то типа сглаженного квадрата.



P.S. Я только что заметил, в первом сообщении рисунки перепутаны местами

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group