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

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

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

А. Л. Крохин 

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

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

Рекомендовано методическим советом  
Уральского федерального университета  
для студентов вуза, обучающихся по направлениям подготовки  
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. Бюст царицы Нефертити