Построение сплайнов с использованием библиотеки OpenGL

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

А.Г. ЗАДОРОЖНЫЙ, Д.С. КИСЕЛЕВ 

ПОСТРОЕНИЕ СПЛАЙНОВ 

С ИСПОЛЬЗОВАНИЕМ 
БИБЛИОТЕКИ OPENGL 

Утверждено 

Редакционно-издательским советом университета 

в качестве учебного пособия 

НОВОСИБИРСК 

2019 

УДК 004.92(075.8) 
         З-156

Рецензенты: 

канд. техн. наук, доцент В.С. Карманов 
доктор техн. наук, профессор М.Э. Рояк 

Работа подготовлена на кафедре прикладной математики НГТУ 

Задорожный А.Г. 

З-156      Построение сплайнов с использованием библиотеки OpenGL: 

учебное пособие / А.Г. Задорожный, Д.С. Киселев. – Новосибирск: Изд-во НГТУ, 2019. – 88 с. 

ISBN 978-5-7782-4069-8 

В данном учебном пособии рассмотрены элементы теории построения 

сплайнов и соответствующие функции графической библиотеки OpenGL. Пособие может быть рекомендовано как для самостоятельного изучения курсов 
«Компьютерная графика» и «Численные методы», так и для подготовки к лабораторным, практическим и расчетно-графическим заданиям. 

УДК 004.92(075.8) 

ISBN 978-5-7782-4069-8
 Задорожный А.Г., Киселев Д.С, 2019

 Новосибирский государственный

технический университет, 2019

ОБЩИЕ СВЕДЕНИЯ 

Исторически, сплайн (spline) – это металлическая линейка (лекало) 

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

В математике же под сплайном понимают кривую, описывающую 

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

Однако сплайны используются не только для описания некоторых 

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

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

 

 

Рис.1. Гибкая металлическая линейка для рисования кривых  
(https://ru.qwertyu.wiki/wiki/Non-uniform_rational_B-spline). 

 

        
                     

Рис.2. Примеры наборов лекал 

(https://ru.wikipedia.org/wiki/Лекало). 

МНОГОЧЛЕНЫ 

Одночлен (моном) – это произведение, состоящее из числового 

множителя и   переменных, взятых в неотрицательной целой степени:  

                   

  

 

   

     

     

       

    

где множитель     называется коэффициентом одночлена, а множество индексов               – мультииндексом.  

Степенью одночлена называется сумма показателей степеней всех 

его переменных (сумма всех элементов мультииндекса):  

          . 

Одночлен с     называется свободным членом и представляет 

собою вещественное число, при этом число 0 является одночленом с 
неопределенной степенью (нулевым одночленом). 

Многочлен (полином) от m переменных – это линейная комбинация  

k  одночленов:  

                      

   

 

   

 

 

   

  

Степенью многочлена называется максимальная из степеней его 

одночленов.  

При     многочлен состоит из двух одночленов и называется 

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

В задачах геометрического программирования понятие монома 

расширяется (в частности, разрешается использование вещественных 
чисел в показателях), а линейная комбинация таких расширенных мономов называется позиномом. 

БИНОМ НЬЮТОНА 

Бином Ньютона – это формула построения многочлена для целой 

неотрицательной степени   суммы двух переменных   и  : 

                   

 

   

  

где     

  

          – это биномиальные коэффициенты, которые могут 

быть обобщенны на область вещественных чисел. 

Поскольку непосредственное вычисление коэффициента     имеет 

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

 
     

    при условии хранения всех получаемых значений. 

Другой вариант – использование формулы Стирлинга (МуавраСтирлинга), которая  является приближением, полученным из разложения факториала в ряд Стирлинга с использованием классических 
чисел   и  : 




5

2
3
4

1
1
1
571

288
51840
2488320

39
!
2
1
12

n
n
n
n
n
e
n
n
O
n
n






























.  

Бином Ньютона, в свою очередь, может быть обобщен до 

полинома Ньютона, представляющего собой возведение в степень   
суммы   слагаемых: 

    

 

   

 

 

     

             

  

 

   

 

     

  

где:   
                  
        – это всевозможные уникальные комбинации це
лых неотрицательных чисел   , сумма которых равна  ; 

         

          

  

              – это мультиномиальные (полиномиальные) 

коэффициенты, частным случаем которых и являются биномиальные 
коэффициенты. 

АЛГЕБРАИЧЕСКИЕ ПОЛИНОМЫ 

Алгебраический полином степени n – это многочлен степени n от 

одной переменной:  

            

 

   

                          

причем     .  

Коэффициент    называется старшим коэффициентом, одночлен 

      – старшим членом, а коэффициент    – свободным членом. Если     , тогда алгебраический полином называется нормированным.  

Число    является корнем полинома      , если         . По тео
реме Гаусса любой алгебраический полином имеет хотя бы один корень (действительный или комплексный). 

По теореме Безу для    выполняется следующее равенство (деление 

многочлена без остатка): 

                      

где         – это алгебраический полином степени  –  . 

Таким образом, число    является корнем кратности r, если        

можно представить в виде  

                     , 

причем          .  

Можно убедиться, что корень кратности   по отношению к произ
водной полинома       является корнем кратности  –  .  

Исходя из вышеизложенного, полином       может быть разложен 

на линейные множители: 

                  

 

   

  

где    – это корни кратности   , причем 

1

m

k

k

r
n





. 

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

называется дробно-рациональной функцией     : 

          

        

Соответственно, при      такая дробь называется правильной, 

а при         такая функция становится дробно-линейной. 

МНОГОЧЛЕНЫ ЧЕБЫШЕВА 

Многочлены Чебышева  –  это две последовательности ортого
нальных многочленов       и      , названные в честь российского 
математика Пафнутия Чебышева. 

Многочлен Чебышева первого рода       характеризуется как 

многочлен степени   со старшим коэффициентом     , который 
меньше всего отклоняется от нуля на отрезке  –     : 

          

               

     

   

  

Многочлен Чебышева второго рода       характеризуется как 

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

            

                 

     

   

  

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

        

 
    

 
          

   
        
       

МНОГОЧЛЕН ТЕЙЛОРА 

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

        

  
       

 

   

  

который при     становится рядом Маклорена. 

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

В теории приближений важную роль играет многочлен Тейлора 

      степени   для приближения функции      в окрестности точки 
 , представляющий собой  сумму первых   членов ряда Тейлора: 

              

  
       

 

   

  

По теореме Тейлора функцию      можно представить в виде 

суммы многочлена Тейлора       и некоторого остаточного члена 
     : 

                  

Если      дифференцируема     раз, тогда для нее остаточный 

член при         можно выписать в форме Лагранжа 

               

                 

а его величину можно оценить по следующей формуле (при условии, 
что            ): 

                  

        

МНОГОЧЛЕНЫ БЕРНШТЕЙНА 

Многочлены Бернштейна (многочлены в форме Бернштейна) – это 

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

                 

 

   

  

где                         – базисный многочлен Бернштейн. 

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

в любой точке равна 1, а начальные полиномы имеют следующий вид: 

           
             
           
                
                  
            

Первая производная полинома         рассчитывается по следую
щей формуле: 

    

 
                               

Полиномы Бернштейна были описаны еще в начале XX века рос
сийским математиком С. Н. Бернштейном, а спустя полвека они стали 
использоваться при построении кривых Безье. 

Для повышения устойчивости при расчете       французским ма
тематиком Полем де Фаже де Кастельжо был предложен рекурсивный 
метод (алгоритм де Кастельжо): 

        

        

где 
  

         

                   

                  
               
     , 

причем   

         .