Сплайны, финитные функции

Понятие и классификация кривых Безье, их разновидности и методика, основные этапы построения. Порядок и условия применения данных кривых в компьютерной графике. Преобразование квадратичных кривых в кубические. Финитные функции. В-сплайны Шёнберга.

Рубрика Математика
Вид реферат
Язык русский
Дата добавления 14.01.2011
Размер файла 456,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

17

Реферат:

«Сплайны. Финитные функции. Основные понятия, назначение. В сплайны Шенберга»

Введение

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

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

1. Сплайны

Под сплайном (от англ. 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 Преобразование квадратичных кривых Безье в кубические

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

2. Финитные функции

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

(2.1)

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

(2.2)

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

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

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

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

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

(2.3)

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

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

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

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

. (2.4)

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

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

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

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

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

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

; (2.5)

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

(2.6)

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

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

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

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

и при (2.7)

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

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

.

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

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

3. B-сплайны Шёнберга

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

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

Когда узлы равноудалены друг от друга, говорят, что B-сплайн является однородным, в противном случае его называют неоднородным.

Когда количество узлов совпадает со степенью сплайна, B-сплайн вырождается в кривую Безье. Форма базисной функции определяется расположением узлов. Масштабирование или параллельный перенос базисного вектора не влияет на базисную функцию.

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

Базисный сплайн степени n: .

не обращается в нуль только на промежутке [ti, ti+n+1], то есть:

. (3.1)

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

Базисная функция может быть получена из полинома Бернштейна

В-сплайн и некоторые наиболее часто используемые базисы

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

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

. (3.2)

Как видим, функция (6.8) удовлетворяет всем условиям (6.7).

Базис из ступенек

Довольно просто показать, что при

(3.3)

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

Базис из крышек

Рассмотрим В-сплайн степени : . Из этого соотношения следует, что получается как свертка функций =

После несложных преобразований получаем:

(3.4)

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

Кроме того, у этого базиса, ввиду того, что p=1, есть одна особенность - для аппроксимируемой функции значения коэффициентов совпадают со значениями функции в узлах сетки , что позволяет быстро находить начальные приближения для .

В-сплайн степени представляет собой кусочно-полиноминальный кубический сплайн, который получается сверткой:

.

(3.5)

Размер носителя при увеличился до четырех (). Заметим, что для обеспечения непрерывности второй производной в точках выполняется условие . Как уже отмечалось, аппроксимация по норме имеет четвертый порядок, по норме - третий.

Литература

1. Роджерс Д., Адамс Дж. Математические основы машинной графики. - М.: Мир, 2001.

2. Корнейчук, Н.П., Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов / отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АН Украины, Ин-т математики.-К.: Наукова думка, 1992.-304 с.

3. Роджерс Д., Адамс Дж. Математические основы машинной графики. - М.: Мир, 2001.

4. Лившиц Евгений Давидович. Непрерывные E-выборки для приближения полиномиальными и рациональными сплайнами: Дис. … канд. физ.-мат. наук: 01.01.01 Москва, 2005 90 с.

5. Алберг Дж., Нильсон Э., Уолш Дж. - Теория сплайнов и ее приложения

6. Винниченко Л.Ф. Экспоненциальные гистосплайны: предпосылки введения // Publishing house Education and Science s.r.o., конференция «Европейская наука XXI века», 2009

7. Корнейчук, Н.П., Бабенко, В.Ф., Лигун, А.А. Экстремальные свойства полиномов и сплайнов / отв. ред. А.И. Степанец; ред. С.Д. Кошис, О.Д. Мельник, АН Украины, Ин-т математики. - К.: Наукова думка, 1992.-304 с.


Подобные документы

  • Понятие и свойства плоских кривых, история их исследований, способы их образования, разновидности и свойства нормали. Методы построения некоторых видов кривых, называемых "Декартов лист", лемнискаты Бернулли, улитки Паскаля, строфоиды, циссоиды Диокла.

    курсовая работа [3,1 M], добавлен 29.03.2011

  • Понятие и способы образования плоских и кривых линий. Примеры пересечения алгебраической кривой линии. Поверхность в геометрии. Аргументы вектор-функции. Уравнения семейства линий. Способ построения касательной и нормали в произвольной точке лемнискаты.

    контрольная работа [329,5 K], добавлен 19.12.2014

  • Порядок и основные этапы построения квадратичных двумерных стационарных систем с заданными интегралами, условия их существования. Методика качественного исследования одной системы первого и второго класса построенных двумерных стационарных систем.

    дипломная работа [125,4 K], добавлен 05.09.2009

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

    курсовая работа [654,1 K], добавлен 28.09.2019

  • Доказательство теоремы единственности для кривых второго порядка. Преимущества и недостатки разных способов доказательства теоремы единственности. Пучок кривых второго порядка. Методы решения теоремы единственности для поверхностей второго порядка.

    курсовая работа [302,7 K], добавлен 22.01.2011

  • Сведения о плоских кривых. Замечательные кривые третьего порядка. Классификация Ньютона кривых третьего порядка. Циссоида и ее свойства. Преобразования плоскости, переводящие кривые второго порядка в кривые третьего порядка. Преобразования Маклорена.

    дипломная работа [960,1 K], добавлен 22.04.2011

  • Система кривых Пирсона. Применение ортогональных полиномов Чебышева при нахождении кривых распределения вероятностей. Примеры нахождения кривых распределения вероятностей и программное обеспечение.

    дипломная работа [230,5 K], добавлен 13.03.2003

  • Понятие и свойства плоских кривых, история их исследований. Способы образования и разновидности плоских кривых. Кривые, изучаемые в школьном курсе математики. Разработка плана факультативных занятий по математике по теме "Кривые" в профильной школе.

    дипломная работа [906,7 K], добавлен 24.02.2010

  • Преподавательская работа швейцарского математика Габриэля Крамера, введение в анализ алгебраических кривых. Система произвольного количества линейных уравнений с квадратной матрицей Крамера. Классификация и порядок математических и алгебраических кривых.

    реферат [47,6 K], добавлен 17.05.2011

  • Представление о взаимном расположении поверхностей в пространстве. Линейчатые и нелинейчатые поверхности вращения. Пересечение кривых поверхностей. Общие сведения о поверхностях. Общий способ построения линии пересечения одной поверхности другою.

    реферат [5,4 M], добавлен 10.01.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.