Сплайны
В практической жизни и деятельности кривые встречаются достаточно часто. Мы уже подробно рассмотрели классические виды кривых: эллипс, гиперболу, параболу и их свойства. А сегодняшнее занятие будет посвящено кривым, без которых немыслима никакая современная графическая система. Даже всем известный стандартный графический редактор Paint.
Задание: изобразить в графическом редакторе кривые различной формы и убедиться, что для того, чтобы создать нужную форму, надо знать принципы построения произвольных кривых, а также их аналитического описания.
Но точное описание произвольной кривой практически невозможно, но можно подобрать такую функцию, которая бы задавала кривую, проходящую через заданные точки и максимально близкую к заданной. Это фактически задача аппроксимации.
Функции, используемые для аппроксимации произвольных гладких кривых называются математическими сплайнами.
Термин «сплайн» происходит от английского spline, что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например, для построения обводов или самолетов.
Свойства таких функций:
1) функция должна проходить через все заданные точки;
2) функция должна иметь непрерывную вторую производную на всей области определения.
Сплайн – это такая кривая или поверхность, для которой сравнительно просто вычислить координаты ее точек.
Будем искать описание кривой в параметрическом виде. Преимущества параметрического описания – легко описываются кривые и поверхности, отвечающие неоднозначным функциям. Описание можно сделать таким образом, что формула не будет существенно изменяться при поворотах и масштабировании.
Одним из способов задания сплайновой кривой является указание координат ключевых точек. Его придумал француз Пьер Безье. Он предложил разбить кривую на куски, каждый из которых задать четырьмя точками.
Гладкая кривая, состоящая из серий по четыре контрольные точки, которые в разной мере определяют ее направление. Совершенно необязательно условие прохождения кривой через все контрольные точки.
P1, P4 – начальная и конечная точки
P2, P3 – ключевые точки, определяющие направление кривой.
Возможен случай: P2=P3
С него и начнем изучение кривых Безье.
Квадратичная кривая Безье
Заданы три контрольные точки P0, P1 и P2. Применим процедуру деления, используя параметр t – число от 0 до 1 (например t=0,75):
1) Вычислим точку P1(1) на отрезке P0P1 по следующей формуле:
P1(1) = (1-t) P0 + t P1
2) Вычислим точку P2(1) на отрезке P1P2 по формуле:
P2(1) = (1-t) P1 + t P2
3) Вычислим точку P2(2) на отрезке P1(1)P2(1) по формуле:
P2(2)=(1-t)P1(1)+tP2(1)
5) Обозначим P(t)=P2(2)
Уравнение кривой
Рассмотрим эту процедуру с точки зрения использования параметров. Каждая из точек P1(1), P2(1) и P2(2) зависит от параметра t , и P2(2) принимает значение, соответствующее значению параметра t. Таким образом, P(t) является функциональным представлением кривой Безье.
Запишем это алгебраически:
P(t) = P2(2)(t) = (1-t)P1(1)(t)+tP2(1)(t), где P1(1)=(1-t)P0+tP1
P2(1)=(1-t)P1+tP2
(Заметим, что мы обозначили P1(1), P2(1) как функции от t).
Подставив эти два выражения в первоначальное, получим
P(t) = (1-t) ((1-t) P0 + tP1) + t((1-t)P1+tP2) =
= (1-t)[(1-t)P0+tP1]+t[(1-t)P1+tP2] =
= (1-t)2P0+(1-t)tP1+t(1-t)P1+t2P2 =
= (1-t)2P0+ 2t(1-t)P1+t2P2
Это квадратичный полином (или линейная комбинация квадратичных полиномов), следовательно, это параболическая кривая. Она и получила название квадратичной кривой Безье.
Свойства квадратичной кривой
1) P(0)=P0 и P(1)=P2, кривая проходит через контрольные точки P0 и P2
2) Кривая P(t) является непрерывной и все ее производные так же непрерывны (это следует из свойств полиномов)
3) Продифференцируем P(t) по t и получим: = 2[(1-t)(P1-P0)+t(P2-P1)]
Таким образом, , при t=0 и это тангенс вектор при t=1. Это означает, что наклон кривой при t=0 такой же, как и у вектора 2(P1-P0) , а наклон кривой при t=1 такой же, как и у вектора 2(P2-P1).
4) Функции (1-t)2, 2t(1-t) и t2 являются полиномами Бернштейна 2-й степени. Сами функции и их сумма неотрицательны: (1-t)2+2t(1-t)+t2=1-2t+t2+2t-2t2+t2=1
5) Кривая лежит внутри треугольника P0P1P2.
P(t) является аффинной комбинацией точек P0, P1 и P2. Таким образом, P(t) будет лежать в выпуклой области контрольных точек при всех , а выпуклая область треугольника и есть сам треугольник.
6) Если точки P0, P1, P2 коллинеарны, то кривая есть прямая линия.
Если точки коллинеарны, то выпуклой областью является прямая, и, следовательно, квадратичная кривая будет прямой линией.
Вывод:
1.Геометрический метод построения квадратичной кривой Безье
2.Аналитический метод построения квадратичной кривой Безье
Кубическая кривая Безье
Заданы четыре контрольные точки P0, P1, P2, P3 .
Пусть P1(1)(t)=tP1+(1-t)P0
P2(1)(t)=tP2+(1-t)P1
P3(1)(t)=tP3+(1-t)P2
P2(2)(t)=tP2(1)(t)+(1-t)P1(1)(t)
P3(2)(t)=tP3(1)(t)+(1-t)P2(1)(t)
P3(3)(t)=tP3(2)(t)+(1-t)P2(2)(t)
Обозначим P3(3)(t) как P(t)
Заметим, что процесс построения такой же, как и квадратичной кривой Безье, добавился лишь один уровень.
Упрощая написанную выше конструкцию, получим:
Свойства кубической кривой Безье
Кубическая кривая Безье имеет свойства, схожие со свойствами квадратичной кривой.
, где .
Вывод:
1.Геометрический метод построения квадратичной кривой Безье
Задав точки P0, P1, P2, P3 и выбрав значение t из [0,1] сгенерировать точку P(t) на кривой Безье:
P(t)=P3(3)(t) , где
2.Аналитический метод построения квадратичной кривой Безье
, где B0(t)=(1-t)3
B1(t)=3t(1-t)2 - полиномы Бернштейна
B2(t)=3t2(1-t) третьей степени
B3(t)=t3
Кубические сплайны находят самое большое применение в практике, так как третья степень – наименьшая из степеней, позволяющих описать любую форму (любой сложности), и при стыковке различных сплайнов можно обеспечить непрерывную первую производную (кривая или поверхность будет без изломов в местах стыка).
Можно для аппроксимации использовать и квадратичные кривые. Они гораздо проще, чем кубический сплайн, но тогда для аппроксимации произвольных линий таких кривых понадобилось бы больше.
Так, например, для построения окружности (или эллипса) с хорошей точностью достаточно четырех кубических сплайнов, а квадратичных надо как минимум 10-12 (см. рис.).
На рисунке эллипс – светло-серая кривая – практически невозможно отличить от кубического сплайна (тонкая черная кривая), построенного по точкам A, Aζ, Bξ и B. Контрольные точки Aζ и Bξ подбирались так, чтобы в точках A и B совпадали радиусы кривизны сплайна и исходной кривой (эллипса).
Квадратичный сплайн (кривая Безье второго порядка, построенная по точкам A, C и B), как видно на рисунке, в точках A и B касается исходной кривой, но в промежутке между этими точками существенно от нее отклоняется.
Геометрические сплайны
Задание
1. Проверить точность аппроксимации в рамках реализованного алгоритма.
Исходными данными на выполнение работы являются: метод аппроксимации и вид кривой (график). Необходимо аппроксимировать заданную кривую с помощью кубической.
Результаты работы: значения параметров построенной кубической кривой, графики промежуточных результатов и график конечного результата.
2. Написать программу построения кривой Безье на экране компьютера. При этом необходимо предусмотреть работу программы в следующих режимах:
- построение кубической кривой по заданным параметрам;
- аппроксимация заданной кривой с кубической путем подбора параметров.
Исходные данные:
№
вари-анта Параметры кубической кривой
Р1х Р1y Р2х Р2y Р3х Р3y Р4х Р4y
1 -30 10 -30 -20 20 30 20 -10
2 -30 10 0 10 20 30 20 -10
3 -20 20 -60 60 50 50 10 10
4 -20 20 20 -20 -30 -30 10 10
Варианты заданий:
