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

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

Уральский федеральный университет 
имени первого Президента России Б. Н. Ельцина 

А. Л. Крохин 

СПЛАЙНЫ В ВЫЧИСЛИТЕЛЬНОЙ  
МАТЕМАТИКЕ 
И КОМПЬЮТЕРНОЙ ГРАФИКЕ 

Учебное пособие 

Рекомендовано методическим советом  
Уральского федерального университета  
для студентов вуза, обучающихся по направлениям подготовки  
09.03.01 — Информатика и вычислительная техника,  
03.03.03 — Математическое обеспечение и администрирование  
информационных систем 

Екатеринбург 
Издательство Уральского университета 
2018 

УДК 519.6(075.8) 
ББК 22.19я73 
    К83 

Рецензенты:
кафедра Прикладной математики Уральского государственно-
го экономического университета (завкафедрой канд. физ.-мат. наук 
Ю. Б. Мельников);
д-р физ.-мат. наук, проф. кафедры № 804 Национального исследо-
вательского университета МАИ С. Н. Мартюшов 

К83
Крохин, А. Л.
Сплайны в вычислительной математике и компьютерной гра-
фике : учебное пособие / А. Л. Крохин. — Екатеринбург : Изд-
во Урал. ун-та, 2018. — 151, [1] с.
ISBN 978-5-7996-2384-5

Компьютерная графика в самом широком смысле слова может рассматри-
ваться в различных аспектах. Это и технические средства отображения, про-
граммное обеспечение и алгоритмы, принципы проецирования и преобра-
зований трехмерных моделей. Важным аспектом являются математические 
методы описания моделей геометрических объектов. Среди них особое ме-
сто занимают различные виды сплайнов. Специфические потребности ком-
пьютеризации различных областей человеческой деятельности иницииро-
вали новые задачи математики. Computer Aided Geometric Design (GAGD) 
подразумевает математические модели и методы, алгоритмы и ПО, обеспе-
чивающие разработку и проектирование автомобилей, самолетов, морских 
и речных судов и многого другого.
В учебном пособии рассматриваются как традиционные методы интер-
поляции, так и новые, в том числе B-сплайны и NURB.

Библиогр.: 23 назв. Рис. 47. Прил. 5.
УДК 519.6(075.8) 
ББК 22.19я73 

ISBN 978-5-7996-2384-5
© Уральский федеральный 
     университет, 2018

Оглавление

Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Глава 1. Метод координат
. . . . . . . . . . . . . . . . . . . . . . . . 11
1.1. Геометрические векторы и метод координат . . . . . . . . . . . . 11
1.2. Уравнения прямых и плоскостей в пространстве . . . . . . . . . . 17
1.3. Барицентрические координаты . . . . . . . . . . . . . . . . . . . . 20
1.4. Кривые второго порядка . . . . . . . . . . . . . . . . . . . . . . . 28
1.5. Математическое описание простых поверхностей
. . . . . . . . . 30

Глава 2. Преобразования координат . . . . . . . . . . . . . . . . . . 35
2.1. Преобразование координат на плоскости . . . . . . . . . . . . . . 35
2.2. Преобразование координат в пространстве . . . . . . . . . . . . . 41
2.3. Однородные координаты и преобразования . . . . . . . . . . . . . 43
2.4. Аффинные комбинации . . . . . . . . . . . . . . . . . . . . . . . . 46

Глава 3. Интерполяция
. . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1. Многочлен Лагранжа . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2. Многочлены Чебышёва . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3. Сплайны. Интерполяция сплайнами . . . . . . . . . . . . . . . . . 58
3.4. Альтернативный подход к построению кривых . . . . . . . . . . . 63

Глава 4. Кривые Безье
. . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1. Особенности вычислительной геометрии и ее отличие от анали-
тической
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2. Общее определение кривых Безье . . . . . . . . . . . . . . . . . . 70
4.3. Как найти точку на кривой Безье . . . . . . . . . . . . . . . . . . 75
4.4. Производные C(t) . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.5. Манипуляции с кривыми Безье
. . . . . . . . . . . . . . . . . . . 80
4.6. Геометрический подход к склеиванию кривых в узлах
. . . . . . 87

Глава 5. B-сплайны . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.1. Определение и основные свойства . . . . . . . . . . . . . . . . . . 92
5.2. B-сплайн кривые . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.3. Однородный B-сплайн третьей степени . . . . . . . . . . . . . . . 107

Оглавление

Глава 6. Пространственные кривые и поверхности
. . . . . . . .111
6.1. Неоднородные рациональные B-сплайны (NURB) . . . . . . . . . 112
6.2. Поверхности в компьютерной графике
. . . . . . . . . . . . . . . 114
6.3. Триангуляция Безье . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4. Recursive Subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Глава 7. Инструментальные средства . . . . . . . . . . . . . . . . .127
7.1. Проблемы визуализации
. . . . . . . . . . . . . . . . . . . . . . . 127
7.2. Средства подготовки публикаций и презентаций . . . . . . . . . . 128
7.3. Системы с графическим интерфейсом . . . . . . . . . . . . . . . . 131

Список литературы
. . . . . . . . . . . . . . . . . . . . . . . . . . . .133

Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .136
Приложение А. Вычисление определителя Вандермонда . . . . . . . . 136
Приложение Б. Пример программы построения кубического сплайна 139
Приложение В. Интерполяция по Лагранжу
. . . . . . . . . . . . . . 142
Приложение Г. Программа построения поверхности Безье . . . . . . . 145
Приложение Д. Построение В-сплайнов . . . . . . . . . . . . . . . . . 148

Введение

The purpose of computing is
insight, not numbers

R. Hamming

An equation for a sphere is possible, but
how about an equation for a telephone,
or a face?

Развитие вычислительной техники превратило ее из инструмента ученых
и инженеров в обиходное средство практически любого работника. Огромную
роль в этом сыграл переход от алфавитно-цифрового представления данных
к их визуализации.
Работа современных терминалов была бы невозможна без соответствую-
щего программного обеспечения, которое базируется на результатах матема-
тических наук. Классическая геометрия, породившая аналитическую геомет-
рию, в наше время стала вычислительной.
Задача аналитического описания формы различных объектов всегда была
актуальна. Для математики это была часть более общей задачи интерполяции
и апроксимации различных функций.
В последние десятилетия появилась новая научная и инженерная дисци-
плина — компьютерная графика. Среди множества вопросов, входящих в ее
состав, особняком стоят задачи приближенного математического описания
формы трехмерного объекта в виде 3D-модели; преобразований этой модели
при трансляциях и поворотах; перспективных искажений.
Может показаться удивительным, но для описания преобразования плос-
ких фигур — 2 измерения — удобным оказалось использование 3-мерных ко-
ординат. А для произвольного преобразования простанственных объектов —

Введение

4-мерные однородные координаты. Кроме традиционных для аналитической
геометрии систем координат и соответствующего описания простейших гео-
метрических объектов, мы рассмотрим также и обобщенные однородные ко-
ординаты на плоскости и в пространстве.
Сами модели могут быть получены различными способами:
• в процессе лазерного (или рентгеновского) сканирования реального
объекта (см. рис. В.1, с. 9), это достаточно трудоемкий процесс;
• как представление форм деталей и изделий в процессе конструирования;
• как представление результатов физических экспериментов или расчетов;
• в результате создания визуализаций абстрактных моделей и учебных
наглядностей;
• интерактивное «свободное» моделирование (кузовы автомобилей, юве-
лирные изделия, орнаменты).
Разработанные математиками методы аппроксимации во многих случаях
дают прекрасные результаты. Они особенно удобны при описании формы тела, 
основа которой получена с помощью экспериментов или математических
расчетов и обусловлена функционалом изделия, взаимным расположением
отдельных деталей, наконец технологией изготовления. Это, например, крыло 
самолета, составные части двигателей, механические и структурные детали. 
Существует, однако, и другой класс задач, когда решение зависит как
от функциональных, так и от эстетических требований, например дизайн поверхности 
машины, фюзеляжа самолета, формы корабля, мебели или посуды.
Метод кривых Безье был разработан независимо Пьером Безье (Pierre
B´ezier) и Полем Де Кастельо (Paul de Casteljau1) в конце 1950-х — начале
1960-х гг. для использования в автомобильной промышленности. Он оказался 
плодотворным и получил существенное развитие для удобного описания
геометрических моделей как полученных в результате точных расчетов, так
и в процессе свободной реализации воображения дизайнера.
Нельзя не отметить еще одну область применения — новые технологии
образования. Лектор-математик объясняет студентам совершенно абстракт-
ный материал, ведь все объекты математики существуют только идеально —
в нашем воображении. Конечно, у математиков есть специальный язык
и символика для работы с этими объектами, но начинающему студенту фор-
мальное определение, скажем, производной дается очень трудно. Для облег-
чения усвоения преподаватели математики всегда используют визуализации,
и здесь результат также определяется своеобразным эстетическим чувством
и педагогическим опытом (см. [1]).

1Есть и другие варианты транскрипции этой фамилии.

В последние годы компьютерная графика завоевывает кинематограф, при-
чем не только мультфильмы. Ни один приключенческий и остросюжетный
фильм не обходится без визуальных эффектов, созданных в рамках матема-
тических моделей.
Анимация также во многом сводится к задаче интерполяции. Художник
прорабатывает ключевые моменты кадра, а промежуточное положение любо-
го элемента экранного образа интерполируется компьютером. И здесь также
требуется возможность свободного вмешательства в свойства этой функции,
причем что именно надо сделать, режиссер вряд ли сможет четко сформули-
ровать.
Кроме количественных критериев, здесь требуется учет практического
опыта, и часто необходимо интерактивное вмешательство разработчика.
Классические объекты вычислительной математики, в частности кубиче-
ские сплайны, неудобны для интерактивной работы. Направление и величина
касательных не дают необходимого интуитивного представления о кривой,
так как не очевидна связь между набором чисел и формой соответствующей
кривой.
Пьер Безье [2] предложил другой метод создания кривых и поверхно-
стей любой формы. Его идеи были плодотворно развиты, так появились В-
сплайны, сначала однородные, а потом и неоднородные и рациональные. Лю-
бопытно, что в 90-е годы многие предлагали шутливую расшифровку аббре-
виатуры NURBS — Nobody Undestands Rational B-Splines, а в настоящее
время данная методика вошла в виде алгоритмов в программные продукты,
используемые по всему миру.
Настоящее учебное пособие предназначено перекинуть мостики между та-
кими математическими курсами, как аналитическая геометрия, вычисли-
тельная математика и компьютерная графика и показать генетическую связь
между ними.
Мы рассмотрим математические методы описания положения в пространстве 
линий и поверхностей. Особое внимание будет уделяться параметрическому 
описанию, как наиболее приспособленному для компьютерной
обработки.
Кроме известной из классической математики непрерывности, нам понадобится 
еще и т. н. геометрическая непрерывность, которую также обозначают
G0, G1, G2.
Геометрическая непрерывность G0 просто означает, что конец дуги одной
кривой совпадает с началом другой. Если речь идет об автомобилях, то этот
тип непрерывности используется в только самых малозначимых местах кузо-

Введение

ва и практически всегда применяется при проектировании различных деталей, 
таких, как двигатель, коробка передач и т. д. Так сопрягаются все детали,
где дизайн не имеет большого значения. Все равно форма этих деталей, которая 
будет получаться в процессе изготовления, будет описана гораздо более
точно в соответствующих чертежах.
G1 — это когда одна кривая (или поверхность) переходит в другую с совпадающими 
направлениями касательной, но с разными радиусами кривизны.
Для реализации достаточно кривой третьей степени.
G2 — это Curvature continuity. Самый популярный тип геометрической
непрерывности в производстве промышленных изделий любого типа: пыле-
сосы, фены, мобильные телефоны и т. д. G2 — это когда одна кривая (или
поверхность) переходит в другую с равными направлениями касательной и
одинаковым радиусом кривизны.
Есть и более высокие требования к гладкости сопряжения участков по-
верхностей.
Квадратичные кривые Безье формируют основу для широко используемой
системы шрифтов TrueType.
Другая распространенная система — PostScript — использует кубические
кривые Безье. Кривые Безье применял при разработке семейств шрифтов
(см. рис. В.2, с. 10) ) и Дональд Кнут в своей знаменитой программе TEX, в
которой, между прочим, набрана и сверстана настоящая работа.
Пожалуй, самая свежая область применения дизайна трехмерных по-
верхностей — это технология трехмерной «печати». Пресловутый термин
«3D-принтер» можно рассматривать как рекламную метафору, опирающу-
юся на знакомое каждому устройство. Речь идет о достаточно хитроумной
новой технологии производства изделий по геометрической модели, разрабо-
танной на компьютере и описанной в специального вида файле.
Пользователь этого девайса может в домашних условиях изготовить ко-
пию классической скульптуры. Например, приведенный на рис. В.1, с. 9 бюст
Нефертити. Использованы результаты тремерного лазерного сканирования,
имеющиеся в открытом доступе в виде файла nefertiti.obj. Облако коорди-
нат точек триангулировано в поверхность и результат приведен к формату
u3d, который можно внедрить в pdf как «живое» изображение. В печатном
варианте получается плоская неподвижная проекция, хотя исходный файл
содержит трехмерное изображение, которое можно поворачивать, масштаби-
ровать и пр. Требуется еще перекомпилировать файл в формат, понятный для
3D-принтера. Грамотное использование данной технологии также опирается
на знания вычислительной геометрии, описанные в данном пособии.

Рис. В.1. Бюст царицы Нефертити

Введение

Рис. В.2. Вот так описывается сплайнами буква S в шрифте Postscript Times Roman.
Черные точки изображают т. н. контрольные точки сплайнов, более подробное
рассмотрение будет в основной части работы

Глава 1

Метод координат. Описание простейших
геометрических объектов

Во времена Архимеда (287—212 гг. до н. э.) геометрические объекты опи-
сывались заданием свойств составляющих их точек. Например, окружность
состояла из всех точек плоскости, отстоящих на равном расстоянии от центра. 
Парабола — из всех точек плоскости, равноудаленных от выделенной
точки и прямой. Многие задачи, решенные Архимедом, для современного
студента никакой сложности не представляют. Знаменитая задача о площади
параболического сегмента (площадь равна 4/3 площади вписанного в сегмент
треугольника, см. рис. 1.1) решается вычислением несложного интеграла.
А попробуйте обойтись без интеграла и без уравнения параболы!
Гигантским шагом в развитии математики было введение метода координат. 
Он позволил использовать для решения геометрических задач алгебраические 
методы. Взаимное расположение линий, расстояния от точки до точки,
от точки до плоскости, между плоскостями и многие другие задачи свелись к
решению уравнений и систем уравнений. На основе метода координат развивались 
дифференциальное и интегральное исчисления. С их помощью задачи
вычисления длин кривых, площадей поверхностей и объемов по сложности
стали доступны студентам младших курсов.

1.1.
Геометрические векторы и метод координат

Основой аналитической геометрии явилась идея введения координат в
пространстве. В дальнейшем мы будем использовать исключительно прямоугольную 
декартову систему координат.
Система координат: рассматриваются три взаимно перпендикулярных
прямых, которые пересекаются в одной точке O — начале координат. Каждая 
из этих прямых является числовой осью, т. е. устанавливается взаимно-