Сплайны и их применение

СОДЕРЖАНИЕ

Введение…………………………………………………………………………..3

ГЛАВА I.  СПЛАЙНЫ…………………………………………………………..4

1.1   Кривые Безье…………………………………………………………4

1.2   Виды кривых Безье…………………………………………………..5

1.3   Построение кривых Безье…………………………………………...7

1.4   Применение в компьютерной графике……………………………..9

1.5   Преобразование квадратичных кривых Безье в кубические…….10

ГЛАВА II.  ФИНИТНЫЕ ФУНКЦИИ………………………………………11

2.1 Теория аппроксимации финитными функциями Стренга-Фикса………………………………………………………………..12

ГЛАВА III.  В-СПЛАЙНЫ ШЁНБЕРГА……………………………………15

Заключение……………………………………………………………………...19

Список использованной литературы………………………………………..20

Введение

Функции, подобные тем, что сейчас называют сплайнами были известны математикам давно, начиная как минимум с Эйлера, но их интенсивное изучение началось, фактически, только в середине XX века. В 1946 году Исаак Шёнберг впервые употребил этот термин в качестве обозначения класса полиномиальных сплайнов. До 1960 годов сплайны были в основном инструментом теоретических исследований, они часто появлялись в качестве решений различных экстремальных и вариационных задач, особенно в теории приближений.

После 1960 года с развитием вычислительной техники началось использование сплайнов в компьютерной графике и моделировании, что продолжается по сей день.

ГЛАВА I.  СПЛАЙНЫ

Под сплайном (от англ. spline – планка, рейка) обычно понимают кусочно-заданную функцию, совпадающую с функциями более простой природы на каждом элементе разбиения своей области определения.

Классический сплайн одной переменной строится так: область определения разбивается на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1.

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

1.1 Кривые Безье

Кривые Безье́ или Кривые Бернштейна-Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье и Полем де Кастельжо.

Впервые кривые были представлены широкой публике в 1962 году французским инженером Пьером Безье, который, разработав их независимо от де Кастельжо, использовал их для компьютерного проектирования автомобильных кузовов. Кривые были названы именем Безье, а именем де Кастельжо назван разработанный им рекурсивный способ определения кривых (алгоритм де Кастельжо).

Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики.

Определение

Кривая Безье – параметрическая кривая, задаваемая выражением:

                                                                      (1.1)

где – функция компонент векторов опорных вершин, а – базисные функции кривой Безье, называемые также полиномами Бернштейна.

                                                                                    (1.2)

,                                                                                                  (1.3)

где n – степень полинома, i – порядковый номер опорной вершины

1.2 Виды кривых Безье:

1. Линейные кривые

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец. Кривая задаётся уравнением:

                                                        (1.4)

2. Квадратичные кривые

Квадратичная кривая Безье (n = 2) задаётся 3-мя опорными точками: P0, P1 и P2:

              (1.5)

Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF файлах.

3. Кубические кривые

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

(1.6)

Четыре опорные точки P0, P1, P2 и P3, заданные в 2-х или 3-мерном пространстве определяют форму кривой.

Линия берёт начало из точки P0 направляясь к P1 и заканчивается в точке P3 подходя к ней со стороны P2. То есть кривая не проходит через точки P1 и P2, они используются для указания её направления. Длина отрезка между P0 и P1 определяет, как скоро кривая повернёт к P3.

Рисунок 1 Кубическая кривая Безье

В матричной форме кубическая кривая Безье записывается следующим образом:
,                                                                      (1.7)

где называется базисной матрицей Безье:

                                                                                    (1.8)

В современных графических системах, таких как PostScript, Metafont и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.

1.3 Построение кривых Безье

1. Линейные кривые

Параметр t в функции, описывающей линейный случай кривой Безье, определяет где именно на расстоянии от P0 до P1 находится B(t). Например, при t = 0,25 значение функции B(t) соответствует четверти расстояния между точками P0 и P1. Параметр t изменяется от 0 до 1, а B(t) описывает отрезок прямой между точками P0 и P1.

Рисунок 2 Построение линейной кривой Безье

2. Квадратичные кривые

Для построения квадратичных кривых Безье требуется выделение двух промежуточных точек Q0 и Q1 из условия чтобы параметр t изменялся от 0 до 1:

Точка Q0 изменяется от P0 до P1 и описывает линейную кривую Безье.

Точка Q1 изменяется от P1 до P2 и также описывает линейную кривую Безье.

Точка B изменяется от Q0 до Q1 и описывает квадратичную кривую Безье.

Рисунок 3 Построение квадратичной кривой Безье

3. Кривые высших степеней

Для построения кривых высших порядков соответственно требуется и больше промежуточных точек. Для кубической кривой это промежуточные точки Q0, Q1 и Q2, описывающие линейные кривые, а также точки R0 и R1, которые описывают квадратичные кривые: более простое уравнение p0q0/p0q1=q1p1/p1p2=bq0/q1q0

Рисунок 4 Построение кубической кривой Безье

Для кривых четвёртой степени это будут точки Q0, Q1, Q2 и Q3, описывающие линейные кривые, R0, R1 и R2, которые описывают квадратичные кривые, а также точки S0 и S1, описывающие кубические кривые Безье:

Рисунок 5 Построение кривой Безье 4-ой степени

1.4 Применение в компьютерной графике

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

Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой.

1.5 Преобразование квадратичных кривых Безье в кубические

Квадратичная кривая Безье с координатами преобразовывается в кубическую кривую Безье с координатами:

ГЛАВА II.  ФИНИТНЫЕ ФУНКЦИИ

Финитной называется функция , определенная для всех , но отличная от нуля лишь на некоторой конечной области , называемой конечным носителем:

                                                                                                                (2.1)

Для , определенных на , построение базиса из финитных функций осуществляется следующим образом. Сначала область , в которой решается задача, некоторым регулярным образом покрывается конечным числом перекрывающихся подобластей , например как на рис. 6.1:

                                          (2.2)

Желательно, чтобы только для , смежных с .

Подобласти получили название конечные элементы.

Затем на каждом как на конечном носителе строим базисную финитную функцию . Все функции таким образом выбранного базиса линейно независимы в силу условий (2.1), (2.2).

Отметим преимущества такого выбора базиса:

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

              (2.3)

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

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

Основная трудность аппроксимации финитными функциями состоит в сопряжении финитных функций на границах k таким образом, чтобы функция в целом была непрерывна вместе со своими производными достаточно высокого порядка.

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

.                                                                                                                (2.4)

На все эти вопросы частично дает ответ теория Стренга-Фикса.

2.1 Теория аппроксимации финитными функциями Стренга-Фикса

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

Область покрываем равномерной сеткой

, [p] – целая часть p.

Конечные элементы выберем как отрезки длиной с центром в точке : . Если , смежные элементы не пересекаются и их длина равна : если , то длина пересечения равна , длина равна ; при – длина пересечения , длина равна . Заметим, что такое покрытие полностью удовлетворяет условиям (2.2). Все базисные финитные функции с носителями выберем одинаковой формы как сдвиги одной «стандартной» финитной функции :

;                             (2.5)

Если «стандартная» функция нормирована к единице, то ее сдвиги записываются в виде

                            (2.6)

Теорема Стренга-Фикса (один из вариантов)

Допустим, что . В этом случае для существует преобразование Фурье:

прямое обратное

Допустим, что для преобразования Фурье стандартной финитной функции выполнено условие

и при                             (2.7)

(т.е. в точках имеет нули й кратности).

Тогда существуют такие , что при

.

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

Наличие такой центральной теоремы, а также еще ряда доказанных Стренгом-Фиксом теорем, в частности о существовании функций, удовлетворяющих условиям (2.7), дает алгоритм для построения базисных финитных функций, обладающих необходимыми аппроксимационными свойствами.

ГЛАВА III.  В-СПЛАЙНЫ ШЁНБЕРГА

В вычислительной математике B-сплайном называют сплайн-функцию, имеющую наименьший носитель для заданной степени, порядка гладкости и разбиения области определения. Фундаментальная теорема устанавливает, что любая сплайн-функция для заданной степени, гладкости и области определения может быть представлена как линейная комбинация B-сплайнов той же степени и гладкости на той же области определения. Термин B-сплайн был введён И. Шёнбергом и является сокращением от словосочетания «базисный сплайн». B-сплайны могут быть вычислены с помощью алгоритма де Бора, обладающего устойчивостью.