Сплайны Эрмита

Министерство образования  и науки Российской Федерации

Иркутский государственный  технический университет

Кафедра технологии машиностроения

 

 

 

 

 

 

 

 

 

 

Курсовая работа по дисциплине Компьютерная геометрия и графика

на тему:

 

«Сплайны Эрмита»

 

 

 

 

 

 

 

 

 

 

 

Выполнила: студентка гр. ИСМ-10-1Лепеева А.С.

 

Проверил: Гаер М.А.

 

 

 

 

 

 

 

 

 

 

Иркутск, 2011

 

Оглавление

 

 

Введение

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

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

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

 

Сплайны

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

Основные типы задач, решающиеся с помощью сплайнов:

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

Задача ставится следующим образом: имеется совокупность точек в пространстве, радиус-векторы которых равны pi, где i = 0, 1,2, ..., n — номера точек; требуется построить линию, радиус-вектор которой при значениях параметра ti, i = 0, 1, 2, ..., n был бы равен pi. Другими словами, необходимо построить интерполяционную кривую. Точки рi которые определяют линию и являются ее внутренними данными, будем называть характеристическими точками кривой, точки ti на числовой оси будем называть узлами, а значения параметра ti будем называть узловыми.

 

Ломаная линия

Простейшей точечно-заданной линией является ломаная линия. Она состоит из отрезков, последовательно соединяющих заданные точки. Значение параметра в каждой последующей точке должно быть больше значения параметра в предыдущей точке ti < ti+1- Радиус-вектор ломаной определяется равенством

,

w =

, ,

 где ti £ t £ ti+1. Параметр w будем называть местным параметром на участке кривой между точками pi и Рi+1. Первая производная ломаной линии в точках pi терпит разрыв по длине и по направлению. Параметр ломаной линии изменяется в одномерном пространстве. В этом пространстве для определения параметра t мы вправе использовать любую систему координат. Для параметра можно использовать систему координат, где его значение в точке pi равно номеру точки: ti = i. Такая параметризация называется равномерной, а параметрическая длина ломаной в таком случае равна числу точек минус один. Ломаная линия приведена на рис. 1.1

Рис. 1.1 Ломаная линия

 

 

 

Ломаная может быть замкнутой, в этом случае первая характеристическая точка одновременно является и последней. Параметрическая длина замкнутой ломаной линии равна числу точек, на которых она задана. Ломаная обладает рядом полезных свойств:

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

 

Сплайны Эрмита

Шарль Эрмит

Шарль Эрмит (1822 – 1901) — французский математик, признанный лидер математиков Франции во второй половине XIX века. Член Парижской академии наук с 1856 года. Награждён орденом Почётного легиона (1892).

С 1842 по 1845 год учился в парижской Политехнической  школе. Защитив диссертацию, становится (1869) профессором Политехнической  школы, где преподавал до 1876 года. В 1869—1897 годах — профессор Парижского факультета наук, преподавал также в Нормальной школе.

Основные работы относятся  к теории чисел, теории квадратичных форм, теории инвариантов, ортогональных  многочленов, эллиптических функций  и алгебре. Исследовал класс ортогональных  многочленов (многочлены Эрмита). Внёс вклад в теорию алгебраических форм и их инвариантов, в том числе в теорию представления целых чисел алгебраическими формами и другие приложения к теории чисел. В ходе этих работ открыл особые билинейные формы (формы Эрмита). Эрмит показал, что число e (основание натурального логарифма) является трансцендентным.

Имя Эрмита носят:

• Эрмитовы операторы
• Эрмитовы матрицы
• Эрмитовы кубические сплайны (Сплайн Эрмита)
• Интерполяционный полином Эрмита
• Полиномы Эрмита
• Функции Эрмита

Сплайн Эрмита

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

Во многих практических задачах требуется построить плавную кривую линию, проходящую через заданные точки. Для этих целей строятся сплайны. Термин «сплайн» для кривых линий заимствован у названия чертежного инструмента — упругой гибкой линейки, которая может изгибаться так, чтобы проходить через заданные точки. Если задана последовательность m + 1 точек, через которую должна пройти кривая, и производные ее радиус-вектора в этих точках, то по этим данным можно построить сплайн, описываемый полиномом степени 2m + 1 и носящий имя Эрмита. Мы рассмотрим частный случай сплайна Эрмита для m = 1. Ломаную линию можно рассматривать в качестве составной кривой, построенной из отрезков прямой линии. По аналогии можно построить составную кубическую кривую, состоящую из сплайнов Эрмита третьей степени, гладко стыкующихся между собой.

Составной сплайн Эрмита

Составной сплайн Эрмита предназначен для построения кривой заданной степени гладкости, проходящей через заданную последовательность опорных точек. Он получается путем  соединения соседних опорных точек  сплайнами Эрмита одного и того же порядка. При этом значения производных радиус-вектора в опорных точках (требуемые для построения составляющих сплайнов Эрмита) необходимо как-то доопределять. Это можно сделать по-разному, исходя из различных соображений. Простые способы доопределения производных приводят к простым вычислениям, однако при неравномерном расположении опорных точек такой сплайн может образовывать необоснованные петли и изгибы. Более сложные способы доопределения производных (псевдоупругие сплайны Эрмита, например) дают хорошие результаты, но приводят к большим вычислениям.

Пример:

Составной сплайн Эрмита порядка 3 (m = 1). Для построения такого сплайна необходимо предварительно доопределить первые производные радиус-вектора  в опорных точках p0,…, pn . Для промежуточных и крайних опорных точек способ доопределения различен.

1. Промежуточные опорные точки. В промежуточных опорных точках можно, например, положить производные равными

 

т. е. рассмотреть аппроксимацию  производных.

 

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

или

,

где  - расстояние между соседними опорными точками.

 

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

Построим составной  сплайн Эрмита, проходящий через заданную последовательность точек и имеющий в этих точках заданные производные. Пусть радиус-векторы этих точек равны pi, векторы производных кривой в этих точках равны qi, а значение параметра в этих точках равны ti (ti < ti+1), где i = 0, 1, 2, ..., n — номера точек. На участке между точками рi и pi+1 составной сплайн Эрмита является полиномом третьей степени местного параметра w

,

Местный параметр w изменяется от 0 до 1. Векторы аj , j = 0, 1, 2, 3 найдем из условий на границе участка кривой

 

После решения этой системы  уравнений и подстановки искомых значений в (2), получим зависимость радиус-вектора для сплайна Эрмита

w = , ,

 

где t_i £ t £ t_i+1. В (3) введены обозначения для функций

 

 

 

удовлетворяющих равенствам:

 

         

 

 

где штрих означает дифференцирование  по w. Если точки pi расположены равномерно, то можно принять значения параметра в точках pi равные номерам точек: ti = i. При неравномерном расположении точек pi параметрическое расстояние ti+1 – ti можно положить пропорциональным расстоянию между соответствующими точками |pi+1 – pi|. Составной сплайн Эрмита может быть замкнутым.

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

 

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

 

 

где si = |pi – pi-1|, si+1 = |pi+1 – pi| — расстояния между соседними точками.

По третьей схеме  меняются местами вклады расстояний между соседними точками:

 

На рис. 1.2 приведены ломаная линия и составной сплайн Эрмита, построенный данным способом — по характеристическим точкам ломаной.

 

1.2 Ломаная линия и  составной сплайн Эрмита

 

 

При неравномерном расположении точек данный способ определения производных qi, как и первый способ, может привести к появлению петель. Предложенные схемы не позволяют получить производные радиус-вектора кривой на ее краях, если она не замкнута. Производные на краях можно получить исходя из целей, которые преследуются при построении кривой. Найдем производные в крайних точках составной кривой из условия, что в этих точках обращаются в нуль третьи производные радиус-вектора. Для этого вычислим по (3) производные для соответствующих участков и подставим в них соответствующие значения параметра, в результате получим

 

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

 

Заключение

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

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

 

Список используемой литературы:

1. Голованов Н.Н. «Геометрическое моделирование», Москва, издательство физико-математической литературы ,2002-472 с.
2. Никулин Е.А. «Компьютерная геометрия и алгоритмы машинной графики», Санкт-Петербург, 2003.-560 с.