ivanstudent

Путь к Файлу: /Введение в компьютерную графику / 15 / 55-60.DOC

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   ivanstudent
Добавлен:   24.12.2014
Размер:   68.5 КБ
СКАЧАТЬ

3.4. Геометрические сплайны

 

          Теория сплайнов – один из самых молодых разделов математики, первая работа в этом направлении опубликована Шенбергом в 1946г.

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

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

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

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

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

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

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

Типичная задача:  по массиву точек на  плоскости  или  в  пространстве построить кривую

- проходящую через эти точки (интерполяция);

- проходящую вблизи этих точек (сглаживание).

В качестве примера приведены на рис.13  верхняя кривая – интерполирующая, нижняя – сглаживающая.

          Сразу две проблемы:

- в каком классе кривых искать нужную;

- как искать.

Остановимся на первой проблеме.

 

55-60

Рис.13. Примеры интерполирующей (верхней) и сглаживающей

(нижней) кривых для одного и того же набора точек

 

Одно из требований - единственность  решения  задачи.  Второе  - построенная кривая должна изменяться плавно.

Пусть на плоскости задан набор точек  (х , у ), i = 0, 1, ..., m,  причем                   

                                                 х0 < x1 < x2 <...< xm ,  

и будем искать кривую в классе  многочленов (полиномов).

 

3.4.1. Интерполяционный полином Лагранжа

 

Известен полином, носящий имя Лагранжа                           

                   55-60

 

То, что эта функция является полиномом, видно из ее вида. Все значения х и у с индексами – это просто числа, а функциональная зависимость задается произведением ряда сомножителей, где всюду фигурирует выражение типа (х – х0) и т.д.  Нетрудно увидеть, что этот полином  по построению таков,  что кривая,  описываемая им, проходит через все заданные точки. В самом деле, если принять х = х0, то первая дробь (множитель перед у0) обращается в единицу, а остальные – в 0. В итоге при этом значении х = х0 получим у(х0) = у0. Аналогично при х = х1 получается у(х1) = у1, и т.д.

          Если нужно построить интерполяционный полином Лагранжа всего лишь для двух точек (х0, у0), (х1, у1), а такая задача тоже может ставиться, то выражение его будет

55-60

а это уравнение прямой, проходящей через заданные точки. Для заданных трех точек получится обычная парабола, для четырех точек – кубическая парабола, и.т.д. Если число заданных точек, пронумерованных от 0 до m, составляет m + 1, то степень соответствующего полинома Лагранжа на единицу меньше и равна m.

 

Достоинства:

1) полином просто строится, и соответствующее выражение при необходимости легко программируется;

2) полином однозначно определяется, т.е. при заданном наборе значений хi и уi его выражение всегда получается одним и тем же;

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

 

Недостатки:

1)  с  ростом  числа точек растет и степень полинома (m -1 при m точках), и растет степень уклонения кривой от аппроксимируемой зависимости;

2) изменение или добавление хотя бы одной точки приводит к изменению всего полинома.

Но наиболее неприятным является следующий недостаток полинома Лагранжа. Если построить кривую, проходящую через все заданные точки, то она получится при большом числе точек сильно осциллирующей, т.е. сильно уклоняющейся от среднего значения между двумя соседними точками. И хотя при этом кривая - таки проходит через все заданные точки, производные (до любого порядка существующие) могут иметь любые  значения между двумя точками, а не те, что отвечают общему характеру зависимости у = у(х). В этом отношении характерны кривые на рис.13: верхняя интерполирующая кривая проходит через все заданные точки, как и должно быть в соответствии с определением. Однако если взять производную – а ее величина определяется как тангенс угла наклона касательной к кривой – то на всем интервале наклон соответствующей касательной меняется от точки к точке очень заметно. Ясно, что «среднее» значение производной гораздо лучше получится, если его определить по сглаживающей кривой.

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

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

 

3.4.2. Кубические сплайны

 

Результат такой  аппроксимации  называется  сплайн-функцией  или просто сплайном.  Аналогия с чертежными сплайнами достаточно очевидна.  Более того,  если взять гибкую стальную линейку и с ее  помощью провести  кривую через  ряд  опор,  оказывается,  что  кривая будет представлять собой график функции у(х) на каждом участке между  опорами - полином третьей степени. На всем промежутке х0, х1, ... , хm этот полином – непрерывно дифференцируемая функция. Такие функции носят название интерполяционных кубических сплайнов.

 

Точное определение:      

Интерполяционным кубическим  сплайном  называется  функция S(x), для которой

1. S(xi) = yi ,  i = 0, 1, ..., m;

2. На каждом отрезке [xi, xi+1] ,   i = 0, 1, ..., m-1

55-60

3. На всем протяжении [x0,  xm ] у функции  S(x) есть  непрерывная  вторая (по меньшей мере) производная.

Так как на каждом отрезке полином третьей  степени  определяется  4 числами (коэффициентами), а участков m, то в итоге нужно найти 4m чисел.

Сформулируем условия, из которых можно однозначно определить эти коэффициенты. Для этого потребуется 4m соотношений, так как число неизвестных в системе уравнений должно быть равно числу уравнений. Из третьего условия требуем непрерывности сплайна во всех  внутренних узлах ( т.е.  S(xi - 0) = S(xi + 0),  i=1, 2, ..., m-1 ) - это m - 1 условий. Обратим внимание, что в крайних точках эти условия нельзя сформулировать. Для первой производной тоже m - 1 условий,  и для  второй.  Если учесть  еще первое требование – m + 1 условие - то всего получается 4m - 2 условия. Два недостающих условия получаются,  если задать, например, значения первых  производных  в  граничных  точках  при i = 0 и i =  m              (граничные условия)

                                       S(x0) = l0;   S(xm) = lm;

и тогда задача решается однозначно. Последние два условия, по существу, означают, что с их помощью мы можем задать направления «входа» в соответствующую кривую при х = х0 и выхода из нее при х = хm.

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

Пусть каждой точке на плоскости

 

(xi, yj), i  = 0, 1,...,m; j = 0, 1,..., n, (x0< x1<... < xm, y0< y1<...< yn )

 

отвечает точка zij; тогда существует массив

 

(xi, yj, zij), i = 0, 1, ..., m;  j = 0, 1, ..., n.

 

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

 

Определение

Интерполяционным бикубическим сплайном двух  переменных  называется функция S(x,y), для которой

1. S(xi,yj)=zij; i=0,1,...,m; j=0,1,...,n;

2. На каждом частичном прямоугольнике

      [xi ,xi+1 ]*[yj  ,y j+1], (i = 0, 1, ..., m-1; j = 0, 1, ... , n-1) эта функция имеет вид

                             55-60

 

3. На всем прямоугольнике [x0, xm ]*[y0, yn ] есть непрерывные первые и вторые производные у  функции S(x, y).

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

 

 

 

 

Достоинства сплайн-аппроксимаций:

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

2. Для решения линейных систем относительно искомых коэффициентов есть эффективные методы, тем более что системы достаточно просты.

 

Недостатки:

1. При  изменении положения хотя бы одной точки нужно пересчитывать все - что не всегда и нужно на практике.

2. Интерполирующие поверхности могут быть сильно осциллирующими при значительном числе точек.

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

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика