Геометрическое моделирование с использованием составных кривых и поверхностей Безье тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

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

На правах рукописи

Григорьев Михаил Игоревич

/

ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ СОСТАВНЫХ КРИВЫХ И ПОВЕРХНОСТЕЙ БЕЗЬЕ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

003470702

Санкт-Петербург 2009 г.

003470702

Работа выполнена на кафедре исследования операций

математика-механического факультета Санкт-Петербургского государственного университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

доктор физико-математических наук, профессор Малозёмов Василий Николаевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор физико-математических наук, профессор Даугавет Игорь Карлович, (Санкт-Петербургский государственный университет)

доктор физико-математических наук, профессор

Певчий Александр Борисович (Сыктывкарский государственный университет)

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Академический физико-технологический университет РАН (Санкт-Петербург)

Защита состоится « И » 2009 г. в в часов на заседании совета Д 212.232.49

по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д. 28, математико-механический факультет, ауд. 405. /V

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан «_/_» ¡АШЗ 2009 г.

Учёный секретарь диссертационного сонета, доктор физико-математических наук, профессор

А. А. Архипова

Общая характеристика работы

Актуальность темы. Геометрическое моделирование {компьютерная геометрия, Computer Aided Geometric Design., CAGD) — относительно молодое направление в прикладной математике, выделившееся в CO-70-x годах прошлого века. Оно объединило некоторые идеи из геометрии и вычислительной математики ira базе компьютерных технологий. В геометрическом моделировании изучаются методы построения кривых, поверхностей и тел, а также способы выполнения над пиши различных операций.

К настоящему времени опубликовано большое количество работ по геометрическому моделированию. Можно выделить книгу Фарипа1, выдержавшую пять изданий. С 1984 года выходит специализированный журнал «Computer Aided Géométrie Design».

Значительный вклад в становление данного направления внесли П. Бсзье и П. Кастель-жо. Они предложили простой и эффективный метод построения кривых и поверхностей. Исходным объектом в их подходе является упорядоченный набор полюсов — точек в конечномерном евклидовом пространстве. Построение осуществляется с помощью параметрического варианта метода последовательных линейных интерполяций. Теперь этот метод называется алгоритмо\1 Кастслъжо, а кривые и поверхности, построенные по алгоритму Кастельжо, — кривым,и и поверхностями Безье.

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

Наиболее просто строятся кривые Безье невысоких порядков (2-го, 3-го и 4-го). Но их возможности не позволяют получать кривые сложной формы. Имеются следующие выходы из данной ситуации.

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

Кроме того, применяются обобщения кривых Безье, связанные с обобщением понятия полипома Бернштейна.

Активно используются гак называемые проективные кривые Безье. Каждому полюсу обычной кривой Безье приписывается положительный вес, после чего осуществляется построение кривой Безье в пространстве на единицу большей размерности. Затем, используя центральную проекцию с центром в начало координат, получаем новую кривую в исходном пространстве, которая и называется проективной кривой Безье. Формой такой кривой можно дополнительно управлять, изменяя значения весов при неизменном положении полюсов.

Дальнейшее развитие теории кривых Безье связано с теорией полярных форл!.. Полярные формы являются классическим математическим инструментом при работе с полиномами. Использование полярных форм для полиномов в форме Бернштейна значительно упрощает описание алгоритмов и доказательство различных свойств кривых Безье.

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

'Farin G. Curves and Surfaces for CAGD. 5th cd. Acadcmic Press, 2002. 520 p.

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

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

Цель работы.

1) Исследование свойств составных кривых Белье на основе свойств полиномов Берниапейна.

2) Поиск возможных обобщений кривых Безье.

3) Исследование свойств составных поверхностей Безье на основе свойств полиномов Бернштейиа от двух переменных.

4) Выяснение предельных возможностей проективных поверхностей Безье второго порядка.

5) Построение теории полярных форм полиномов от двух переменных и её использование при построении составных поверхностей Безье.

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

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

Научная новизна. В диссертации получены следующие основные результаты.

1) Разработана схема построения составных кривых Безье заданной гладкости.

2) Проведено исследование проективных кривых Бсзье второго порядка и замкнутых проективных кривых Безье третьего порядка.

3) Предложен новым способ обобщения кривых Безье.

4) Раз;тботана схема построения составных поверхностей Безье.

~>) Показано, как построить поверхности тора и сферы при помощи проективных поверхностей Безье второго порядка.

6) Предложен способ обобщения поверхностей вращения. Показано, как строить такие поверхности.

7) Построена теория полярных форм для полиномов от. двух переменных.

8) С помощью основной леммы теории полярных форм получены, условия, гладкости заданного порядка составной поверхности Безьс.

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

Апробация работы. По результатам диссертации были сделаны доклады на следующих научных конференциях и семинарах:

• Международная научная конференция «Космос, астрономия и программирование? (Лавровские чтения) (Санкт-Петербург, 20-22 мая 2008 г.);

• семинар кафедры исследования операций математико-механического факультета СПбГУ;

• семинар кафедры вычислительной математики математико-механического факультета СПбГУ;

• семинар по дискретному гармоническому анализу и геометрическому моделированию (ОНА к САСП).

Публикации. По теме диссертации опубликовано шесть работ [1-6), перечисленных в конце автореферата. Статьи [2,3,5] опубликованы в изданиях, входящих в перечень ВАК.

Работы [3-6] написаны в соавторстве. В статье (3) Малозсмову В. Н. принадлежит вывод и обоснование уравнения в барицентрических координатах для дробно-рациональной кривой Безье второго порядка. Диссертантом осуществлена классификация таких кривых. Сергеев А. Н. внёс уточнение в алгоритм построения окружности при помощи дробно-рациональных кривых Безье. В работе [4[ Сергеевым А. Н. был предложен подход к доказательству основной леммы теории полярных форм. Диссертанту принадлежит реализация данного подхода. Малозёмов В. Н. предложил улучшение некоторых доказательств. В статье [5| соавторам принадлежит общая постановка задачи и указание на идею исследования. Детальная реализация идеи осуществлена диссертантом. В работе [б| Сергееву А. Н. принадлежит идея обобщения теории полярных форм на алгебраические полиномы от двух переменных. Реализация этой идеи осуществлена диссертантом.

Структура и объем работы. Диссертация состоит из введения, 2 глав, разбитых на 17 параграфов, списка литературы и одного приложения. Объём диссертации — 126 страниц. Список литературы насчитывает 48 наименований. В диссертации имеется 67 рисунков.

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

Первая глава посвящена кривым Безье.

В § 1 содержатся вспомогательные сведения о базисных полипомах Бернштейна Щх) = С£ хк (1 - х)'1~к, к е 0 : п, п = 0,1,..., и полиномах в форме Бернштейна

п

В(х) = £>«£(*)■

и-=о

Введём треугольный массив {«£}, / € 0 : п, к е О : п — г, по рекуррентной формуле а\ = (1 - г) «[Г1 + г 6 1 : п, к е 0 : п - ¡:

а° = к 6 0: п.

ПРЕДЛОЖЕНИЕ 1.6. При, фиксированном х производную и-го порядка от полинома в форме Берпштейна можно вычислить по формуле

= Л^(Д"оп-")п, I/ е 0 : п,

где (А" ап~")0 = — конечная разность вперёд и-го порядка и

А"п = п(п - 1) - ■ - (п - 1/4-1).

В частности, при ^ = 0 имеем В(х) = Од. Таким образом, значение полинома Берн-штейна можно быстро вычислить с помощью схемы (1).

Рассмотрим полином в форме Бернштейпа с векторными коэффициентами

п

В(и)=$>*6?(1х),

к=0

где а/с = (ак1,..., а^). Полином В(и), и е [0,1], задаст кривую в пространстве К', которая называется кривой Безье. Векторный вариант быстрого алгоритма (1) соответствует алгоритму Кастельжо построения точки па кривой Белье (см. рис. 1). Этим вопросам посвящен §2.

а2

Рис. 1. Алгоритм Кастельжо

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

8Ы = /Ч<и) ПРИ "€[-1-0]. |В(и) при и е [0,1],

где С}(г/) — полипом в форме Бершптейпа степени ш, ориентированный на отрезок [—1,0].

ПРЕДЛОЖЕНИЕ 3.2. Функция в(п) будет г рал непрерывно дифференцируемой на от,резке [—1,1] при г < тт{т, п} тогда и только тогда, когда выполняется условие

С;(Уа)0 = С,' (Д"'а)0, / е 1 :

{Здесь (У'а)0 — конечная ралностъ назад ¿-го порядка.)

Рис. 2. Составная кривая Безье при г = 2

Функция S (и) задаст составную кривую, сшитую из двух кривых Бсзье (рис. 2).

В §4 изучаются проективные кривые Безье. Зафиксируем полюсы ао,...,а„ е К' и положительные веса и^, к £ 0 : п. Формула

Ек=о">кЩи)

определяет кривую в R', которая называется проективной кривой Безье порядка п. Ее формой при неизменном положении полюсов а* можно управлять, варьируя веса м,'ь

Интерес представляют проективные кривые Бсзье небольших порядков. В § 5 рассматриваются проективные кривые Бсзье второго порядка, которые определяются тремя точками па плоскости ао, аь а2, и тремя положительными весами ujo, Wi, wq. Выводится уравнение таких кривых в барицентрических координатах. Оно содержит один независимый параметр ц = w\/(wa u>2).

ПРЕДЛОЖЕНИЕ 5.3. Проективная кривая Безье второго порядка в барицентрических относительно точек ад, аь а2 координатах определяется уравнением

4 ¡1А0 Аг = А;.

Дастся полная классификация проективных кривых Бсзье второго порядка в зависимости от значений параметра ц.

В § G исследуются замкнутые проективные кривые Безье третьего порядка, строящиеся по трём точкам ао, а:, а2, я четырём весам w0, wi, w2, W3. Выводится уравнение кривой в барицентрических координатах — в данном случае оно содержит два независимых параметра

«'О U'2 Wi w3

/'о = —2 11 /'1 = —г~ ■ wf w*

ПРЕДЛОЖЕНИЕ 6.2. Замкнутая проективная кривая Безье третьего порядка в барицентрических 0mn0r.umeji.hH0 точек а<), aj. а2 координатах определяется неявным уравнением

/'о Af + А2 - ЗА0А! Aj = 0.

Показано, как строится поле проективных кривых Безье третьего порядка, проходящих через фиксированную точку (рис. 3). Получены условия, при которых через две фиксированные точки можно провести замкнутую проективную кривую (рис. 4).

В § 7 описан способ обобщения кривых Безье, основанный на способе обобщения полиномов Бсргпнтсйна, предложенном В. С. Видспским2. Базисные полиномы Бсрнштсйна

2Виделский В- С. Линейные положительные операторы конечного ранга. Л.: ЛГПИ им. А. И. Гордона, 1985. 67 с.

можно определить с помощью производящей функции [ху + (1 - х)]" = Ук■

В. С. Виденский рассмотрел более общую производящую функцию и ввёл обобщённые полиномы Бсрнпггейпа р\(х):

п п

9п(х,у) ~ ЦЫхУу+ 0 - Л-(-сШ = i't

1=1 <-=0

Здесь hi(x),..., h„(x) : [0,1] —> [0,1] — непрерывные функции, удовлетворяющие условиям Л,(0) = 0, hi{ 1) = 1 при всех i 6 1 : п.

Введём обобщённый полином Всрнштейна с векторными коэффициентами

ti

Н(ч) = Х>*й(«), и € [0,1],

к=о

где an.ai,.. .,ап принадлежат R'. Вектор Н(и) при фиксированном и £ [0,1] является выпуклой комбинацией полюсов ао,аь ... ,а„. Когда и изменяется от 0 до 1, вектор Н(и) описывает кривую в пространстве R'. Назовём сё обобщённой кривой Безье. Эта кривая соединяет точки ао и ап, не покидая выпуклую оболочку полюсов.

Зафиксируем и 6 (0,1). Для вычисления Н(и) построим треугольный массив {a¿} с помощью рекуррентных соотношений

а° = afc, к € 0 : п;

аI = (1 - Л„_у+1(и)) а ¡Г1 + Кч+1{и) a.[~+v k е 0 : п - j, je 1 : п.

ПРЕДЛОЖЕНИЕ 7.3. Справедливо равенство Н(и) = ag .

На рис. 5 слева изображена кривая Бсзьс, построенная по полюсам а*. = (£, (—l)fe), А: б 0 : п. Справа приведена обобщённая кривая Безье, построенная по тем же полюсам. Использованы дробно-линейные функции

при специальном выборе узлов ^ £ й \ [0,1], ¿61: п. Вторая глава посвящена поверхностям Бсзьс.

В § 8 и § 10 рассматриваются поверхности Безье на четырехугольнике и их проективное обобщение. Пусть в пространстве 18' заданы полюсы а*», к 6 0 : т, я 6 0 : п. Поверхность Безье порядка т х п определяется формулой

т п

в(«,«) = Е Еч» г; € 1°' ч-

А:=0 8=0

Рис. 5

На оснопс быстрого алгоритма вычисления значения полинома в форме Бертнтсйиа строится аналог алгоритма Кастельжо для таких поверхностей. Зафиксируем и, и € [0.1]. Введём полюсы

к е 0 : m - г, г € 0 : m, s е 0 : п - j, j 6 0 : n, с помощью рекуррентных соотношений

ajj, = (1 — и) aj~Ij + v aj"1^,, к е 0 : m - i, i el: m; a¡¿ = (l-t-)a^-I + t»a^;\, s€0:n-j, j € 1 : n; aj" = atí, i-eO: m, s e 0 : n. ПРЕДЛОЖЕНИЕ 8.1. Для полюсов (2) справедливо представление

(2)

о=0 (3=0

При г = ;;¡, j = ,1 имеем a£,"(u,v) = £3=о aaP &"(«) W = В(и/о). Зафиксируем положительные веса wks, к е 0 : т, s £ 0 : п. Проективная поверхность Белье порядка т х и определяется формулой

Её формой при неизменном положении полюсов а^ можно дополнительно управлять, варьируя веса

В §0 предлагается схема построения составных поверхностей Безье. Рассмотрим составную поверхность Безье

S(u,v)

Q(u. u), и 6 [—1,0], и G [0,1]; B(u,îi), ue[o,i], «e[o,i],

где поверхность Q(», l<) задана на квадрате [—1,0] х [0,1] и строится по полюсам к € 0 : р, s 6 0 : п. Поверхности Q(u, v) и B(u, v) имеют общее ребро Q(0,îi) = В(0, г), v 6 [0.1]. Введём оператор взятия конечной разности на двухиндексиом множестве элементов (A"at,s)fc = E.'U-1)""^^,..

ПРЕДЛОЖЕНИЕ 9.1. Для того, чтобы поверхность S(i/, v) обладала гладкостью г-го порядка (г < min{m,p}) необходимо и достаточно выполнение условий

= s е 0 : п, « 6 1 : г. (3)

На рис. 6 слева изображены две поверхности Безье, сшитые с сохранением гладкости 1-го порядка. Полюсы, отмеченные на рисунке, связаны условиями (3).

Также в § 9 рассмотрен случай состыковки четырех поверхностей, имеющих общие рёбра и один общий узел. Пример такой составной поверхности, сшитой из четырёх поверхностей Безье при т = п — 3, г = 2, приведён на рис. 6 справа.

a-i.o ада а!п

В § 11 исследуются предельные возможности проективных поверхностей Безье второго порядка. Показывается, как построить поверхности сферы и тора с помощью проективных поверхностей Безье (см. рис. 7). Используются девять полюсов и специальный набор весов.

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

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

На рис. 8 приведён пример обобщённой поверхности вращения. Исходные кривая радиусов F и кривая центров С представлены на рис. 9.

В § 13 рассматриваются полиномы Бсршитейна от двух переменных. Обозначим базисные полиномы Бернштейна от двух переменных

l>L(z,V) = C*-axkys(l-z-y)n-k-', ¿6 0:п, seOin-k,

Рис. 8

х

Рис. 9

где С^ = к,аЧ,?_к_а), ■ Полином вида

п ч-А:

называется полиномом в форме Бсртнтсйна от двух переменных степени п.

Зафиксируем произвольные вещественные х, у. Для вычисления значения Ъ(х,,у) введём п + 1 треугольных массивов с помощью рекуррентных соотношений

аь = "«.■»• к еО : п, в е 0 : п — к;

<4 = (1 " * - У) «ь1 + г + У 4^+1. (4)

к € 0 : п — г, я е 0 : п — г — к, г = 1,..., п. ПРЕДЛОЖЕНИЕ 13.2. Справедливо равенство Щх,у) = а£0.

ПРЕДЛОЖЕНИЕ 13.3. При фиксированных х, у частные производные от полином,а в форме Бернштейна, можно вычислить по (формуле

(Здесь (Д";3

а" — конечная разность на треугольном массиве коэффициентов.)

В § 14 строится теория полярных форм полиномов от двух переменных. Точки из К2 будем обозначать £ = (.г. у), = (х,. у,). Введём основные симметрические полиномы над переменными из К2:

<7оо(ч1.....6.) = 1.

.....£ £ II'- 11%- (5)

4сл' лсч^'к

А:, О О, +

Суммирование в правой части (а) ведётся но всем подмножествам множества ЛГ -= {1____,п}. содержащим ровно к элементов, и по всем подмножествам 3, множества Лг \ 1к, содержащим ровно в элементов. Полярной формой полинома степени п от

двух гтсремешгых вида

п n—fr к=О s—О

называется выражение

п п—к )с=П s=0

Полярная форма является симметричной функцией своих аргументов. С порождающим полиномом ее связывает соотношение р(£,-..,0 = Р(0- Значение р(£ь • ■ -, £„) ПРИ конкретных значениях аргументов ..., £„ называется полюсом полипома Р(£) вида (6). Важным свойством полярной формы является мультиаффинность.

ПРЕДЛОЖЕНИЕ 14.1. При любом г € 1 : п справедливо равенство

р«1,..., «с + <', ...,£„) = «p(Ci,..., С- --.и +

если и + v = I.

Полюсы полярной формы можно вычислять эффективно. Зафиксируем и

построим п + 1 треугольных массивов {d"ks} по правилу

d°ks = dks, кеО-.п, s 6 0 : n - fc; < = С' + 4+V, + Уп-t+i d£+i -

fc € 0 : n - г, s 6 0 : n — г* — к, г = 1,..., п.

ПРЕДЛОЖЕНИЕ 14.2. Справедливо равенство р(£г,... ,£„) = ¿м-

Пусть на плоскости выбраны три точки £о> £2, не лежащие на одной прямой. Зафиксируем числа ai.,, А; 6 0 : п, s 6 0 : п — к, и рассмотрим задачу интерполяции по полюсам: найти полином Р(£) вида (С), такой, что

= <«*., fce0:n,e60:n-fe. (7)

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

ПРЕДЛОЖЕНИЕ 14.3. Единственным решением интерполяционной задачи (7) является полином Бернштейна

п п~к /с=0 s=0

где £ = (1 - и - v) + и + v & ■

В § 15 в терминах полярных форм получены условия совпадения в точке двух полипомов от двух переменных вместе со всеми их частными производными до требуемого порядка (основная лемма теории полярных форм).

Рассмотрим два полинома А(?) и степени п с соответствующими полярными

формами р1((ь..., £„) и р2(£ь ...,£„).

ЛЕММА 15.3 (Основная). Для того чтобы в некоторой точке г/ 6 К2 полиномы Л(0 и Рг(£) совпадали вместе со всеми своими наемными производными до ц-го порядка включительно, необходимо и достаточно, чтобы при любых щ_____ щ ил К2 выполнялось \ю-

венство

Р1(ГГ".Г! 1.....,к)=р1[гГ',-Чп----г1<1).

В § 16 исследуются поверхности Безье па треугольнике. Введем полином степени п от двух перемешшых в форме БсрнштсГша с векторными коэффициентами, ориентированный на треугольник с вершинами (о. чь £г :

и »-I

В (О = Щи, V) = £ %(«,«), (9)

к=о *=о

где £ = (1 — и — и) ¡;0 + и £1 + и Полином (9) определяет поверхность в К', которая называется поверхностью Безье на треугольнике. Векторный вариант быстрого алгоритма (4) вычисления значения полинома Бернштсйна соответствует алгоритму Кастельжо построения точки на поверхности Бозье (см. рис. 10). Основной процедурой в данном алгоритме является двумерная линейная интерполяция.

Теорию полярных форм полиномов от двух переменных можно обобщить на случай полиномов с векторными коэффициентами. Обозначим b(£i,..., £„) полярную форму полинома Значения этой полярной формы вида

Ь(£Г1г",,£1\£), keQ-.n, s £ 0: и - к, (10)

известны, они совпадают с полюсами а*, поверхности Бозье 93(£) (Предложение 14.3).

Поверхность 25(£) задана па треугольнике Очевидно, можно расширить об-

ласть определения поверхности на всю плоскость К2. Зафиксируем три точки r¡o, tji, г)2 па плоскости, не лежащие на одной прямой. По полюсам (10) найдём псе полюсы вида

ь('/о rlí, П2) у keQ: п, s 6 0 : п - к,

которые определяют порцию поверхности 23(£) над треугольникомrjo í)i Щ-

На рис. 11 приведен пример использования данного алгоритма. Слева показано, как расположены точки r/a, rjy, r¡2 и £ui £1. £2 • Справа изображены соответствующие порции поверхности 93(£).

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

В § 17 рассматривается сшивка поверхностей Безье на треугольнике. Зафиксируем в плоскости параметров точку £з так, чтобы треугольники £2 и £1 £г£з не пересекались. Пусть на СгСг^з задана поверхность Безье порядка п. Обозначим её полярную форму Ч(£ь • • • С помощью основной леммы теории полярных форм можно получить условия гладкой сшивки до г-го порядка (г 6 1 : п) поверхностей 23(£) и на общем ребре

й, й) = ЬКГ-*"', Й).

к е 0 : г, в € 0 : п - к,

или

чкг*-, & й) = Е Е «^ '*>••

1=0 ]-а (12)

к е о : г, в 6 0 :п-к,

где = (1 — и» — V.) £0 + и. £1 + с, £2- Полюсы поверхности 0(0. на которые наложены условия, являются связанными. Остальные полюсы поверхности £3(£) можно выбирать произвольно.

На рис. 13 изображены полюсы двух поверхностей Безье 3-го порядка, сшитых с сохранением гладкости 1-го порядка. Точками выделены полюсы, на которые наложены условия гладкости. Сшитая из этих поверхностей С'-гладкая поверхность приведена па рис. 14.

Также в § 17 рассмотрен случай, когда стыкуются три поверхности Безье, попарно имеющие общие рёбра и один общий узел (рис. 15). Для данной конфигурации возникает неоднозначность при определении положения связанных полюсов. Получены достаточные условия, которые данную неоднозначность разрешают. Приме)) такой составной поверхности для п = 3, г = 2 приведён на рис. 16.

Основные результаты диссертации опубликованы в работах

1. Григорьев М. И. Полиномы Бернштейна от двух переменных // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2008-05.

(http://www.mathsoc.spb.ru/preprint/2008/index.html#05).

2. Григорьев M. И. Построение сферы с помощью проективных поверхностей Бс:п>е и Вести. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 3. С. 127-131.

3. Григорьев М. И., Малозёмов В. Н., Сергеев А. Н. О классификации дробно-рацио-нальпых кривых Безье второго порядка jj Вести. С.-Петерб. ун-та. Сор. 1. 2008. Вып. 2. С. 103-108.

4. Григорьев М. П., Малозёмов В. Н., Сергеев А. Н. Основная лемма теории полярных форм полиномов от двух переменных j j Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2008-07.

(http://www.mathsoc.spb.ru/preprint/2008/index.html#07).

5. Григорьев M. И., Малозёмов В. H., Сергеев А. Н. Полиномы Бернштейна и составные кривые Безье // Журн. вычисл. мат. и матем. физ. 2006. Т. 46. -V' 11. С. 1962-1971.

6. Григорьев М. П., Сергеев А. Н. Полярная форма полиномов от двух переменных // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2008-06. (http://www.mathsoc.spb.ru/preprint/2008/index.html#06).

Подписано к печати 23.04.09. Формат 60 х 84 Vi6. Бумага офсетная. Гарнитура Times. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4451.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

Введение.

Глава I. Кривые Безье.

§ 1. Полиномы в форме Бернштейна.

§2. Кривые Безье.

§ 3. Построение составных кривых.

§4. Проективные кривые Безье.

§ 5. Классификация проективных кривых Безье второго порядка

§ 6. Поле замкнутых кривых Безье.

§ 7. Обобщённые кривые Безье.

Глава II. Поверхности Безье.

§8. Поверхности Безье на четырёхугольнике.

§ 9. Составные поверхности Безье.

§ 10. Проективные поверхности Безье на четырёхугольнике

§ 11. Построение поверхностей тора и сферы.

§ 12. Обобщённые поверхности вращения.

§ 13. Полиномы Бернштейна от двух переменных.

§ 14. Полярная форма полиномов от двух переменных.

§ 15. Основная лемма теории полярных форм.

§ 16. Поверхности Безье на треугольнике.

§ 17. Сшивка поверхностей Безье.

Геометрическое моделирование (компьютерная геометрия, Computer Aided Geometric Design, CAGD) — относительно молодое направление в прикладной математике, выделившееся в 60-70-х годах прошлого века. Оно объединило некоторые идеи из геометрии и вычислительной математики на базе компьютерных технологий. В геометрическом моделировании изучаются методы построения кривых, поверхностей и тел, а также способы выполнения над ними различных операций. Компьютерная геометрия используется, в частности, при разработке систем автоматического проектирования.

К настоящему времени опубликованы несколько монографий по геометрическому моделированию [27, 28, 36, 38, 41, 42, 46, 48], в том числе — две на русском языке [4, 5]. Книга Фарипа [33] выдержала пять изданий. С 1984 года выходит специализированный журнал «Computer Aided Geometric Design».

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

Значительный вклад в становление данного направления внесли П. Безье и П. Кастельжо [1, 19, 29]. Они предложили простой и эффективный метод построения кривых и поверхностей. Исходным объектом в их подходе является упорядоченный набор полюсов — точек в конечномерном евклидовом пространстве. Построение осуществляется с помощью параметрического варианта метода последовательных линейных интерполяций. Теперь этот метод называется алгоритмом Кастелъоюо [33, с. 45], а кривые и поверхности, построенные по алгоритму Кастельжо, — кривыми и поверхностями Безье.

Форрест установил связь между кривыми Безье и полиномами в форме Бернштейна. Он показал [34], что функция, задающая кривую Безье может быть представлена в виде линейной комбинации базисных полиномов Бернштейна. Это позволило исследовать свойства кривых Безье, опираясь на свойства данных полиномов.

Наиболее просто строятся кривые Безье невысоких порядков (2-го, 3-го и 4-го). Но их возможности не позволяют получать кривые сложной формы. Имеются следующие выходы из данной ситуации.

Можно использовать составные кривые, сшитые из сегментов, каждый из которых является кривой Безье невысокого порядка. При этом обеспечение гладкости достигается за счёт условий, накладываемых на полюсы сшиваемых кривых. Получающаяся составная кривая является, по сути, параметрическим вариантом полиномиального сплайна [4, 39].

Кроме того, применяются обобщения кривых Безье, связанные с обобщением понятия полинома Бернштейна [3, 32, 37, 47].

Активно используются так называемые проективные кривые Безье [33, 36, 38]. Каждому полюсу обычной кривой Безье приписывается положительный вес, после чего осуществляется построение кривой Безье в пространстве на единицу большей размерности. Затем, используя центральную проекцию с центром в начале координат, получаем новую кривую в исходном пространстве, которая и называется проективной кривой Безье. Формой такой кривой можно дополнительно управлять, изменяя значения весов при неизменном положении полюсов.

Дальнейшее развитие теории кривых Безье связано с теорией полярных форм [20, 40, 45]. Полярные формы являются классическим математическим инструментом при работе с полиномами. Использование полярных форм для полиномов в форме Бернштейна значительно упрощает описание алгоритмов и доказательство различных свойств кривых Безье.

Перейти от кривых к поверхностям Безье можно двумя способами. В первом вводятся так называемые образующие кривые Безье, имеющие одинаковую параметризацию. При каждом значении параметра по точкам на этих кривых в свою очередь строится кривая Безье. Перемещаясь по образующим кривым, получаем поверхность, которая называется поверхностью Безье на четырёхугольнике [5, 33, 48]. Областью задания параметров такой поверхности является прямоугольник.

Другой подход использует естественное обобщение полиномов Бернштейна на случай двух переменных. Поверхность, которая задается таким полиномом, называется поверхностью Безье на треугольнике [4, 27, 33, 42, 48]. Она имеет треугольную область задания параметров. Треугольник является базовым элементом при разбиении двумерных областей, поэтому поверхности Безье на треугольнике нашли широкое применение в численных методах.

Целью диссертационной работы является:

1. Исследование свойств составных кривых Безье на основе свойств полиномов Бернштейна.

2. Поиск возможных обобщений кривых Безье.

3. Исследование свойств составных поверхностей Безье на основе свойств полиномов Бернштейна от двух переменных.

4. Выяснение предельных возможностей проективных поверхностей Безъе второго порядка.

5. Построение теории полярных форм полиномов от двух переменных и её использование при построении составных поверхностей Безье.

6. Разработка программной системы компьютерного моделирования с использованием составных кривых и поверхностей Безье.

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

Первая глава посвящена кривым Безье.

В первом параграфе содержатся вспомогательные сведения о базисных полиномах Бернштейна и полиномах в форме Бернштейна. Выведены рекуррентные соотношения для базисных полиномов Бернштейна. На их основе получен быстрый алгоритм вычисления значений полинома в форме Бернштейна и всех его производных в фиксированной точке.

Геометрическая интерпретация вышеуказанного быстрого алгоритма приводит к алгоритму Кастельжо построения кривых Безье. Этому вопросу посвящен второй параграф.

В третьем параграфе предлагается схема построения составных кривых Безье. Условия гладкости формулируются в виде соотношений, наложенных на полюсы сшиваемых кривых.

В четвёртом параграфе изучаются проективные кривые Безье. Показано, как изменение весов влияет на форму кривой.

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

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

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

Вторая глава посвящена поверхностям Безье.

В восьмом и десятом параграфах рассматриваются поверхности Безье на четырехугольнике и их проективное обобщение. На основе быстрого алгоритма вычисления значения полинома в форме Бернштейна строится аналог алгоритма Кастельжо для таких поверхностей.

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

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

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

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

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

В пятнадцатом параграфе в терминах полярных форм получены условия совпадения в точке двух полиномов от двух переменных вместе со всеми их частными производными до требуемого порядка (основная лемма теории полярных форм).

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

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

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

В процессе работы над диссертацией была создана программная система моделирования, основным аппаратом в которой являются составные кривые и поверхности Безье. При этом использовались работы [18, 25, 30, 31, 43, 44].

На защиту выносятся следующие основные результаты:

1. Разработана схема построения составных кривых Безье заданной гладкости.

2. Проведено исследование проективных кривых Безье второго порядка и замкнутых проективных кривых Безье третьего порядка.

3. Предложен новый способ обобщения кривых Безье.

4- Разработана схема построения составных поверхностей Безье.

5. Показано, как построить поверхности тора и сферы при помощи проективных поверхностей Безье второго порядка.

6. Предложен способ обобщения поверхностей вращения. Показано, как строить такие поверхности.

7. Построена теория полярных форм для полиномов от двух переменных.

8. С помощью основной леммы теории полярных форм получены условия гладкости заданного порядка составной поверхности Безье.

9. Разработана программная система компьютерного моделирования с использованием составных кривых и поверхностей Безье.

Основные результаты диссертации опубликованы в работах [10, 11, 14-17]. Предварительные результаты обсуждались на семинаре по дискретному гармоническому анализу и геометрическому моделированию ([7-9, 12, 13]). По результатам диссертации были сделаны доклады на международной научной конференции «Космос, астрономия и программирование» (Лавровские чтения) [6] и на семинарах кафедры исследования операций и кафедры вычислительной математики математико-меха-нического факультета СПбГУ.

Автор искренне благодарен своему научному руководителю В. Н. Ма-лозёмову за помощь в выборе направления, внимательное участие в постановке задач и анализе результатов, и, больше всего, за бесценный опыт, полученный в течение работы над диссертацией. Также автор глубоко признателен доц. А. Н. Сергееву за внимание к работе и поддержку и О. В. Просекову за ценные советы и помощь в постижении тонкостей полиграфической системы Т^К.

1. Безье П. Геометрические методы. В кн.: Математика и САПР. 2. Пер. с франц. М.: Мир, 1989. С. 96-257.

2. Виденский В. С. Линейные положительные операторы конечного ранга. JL: ЛГПИ им. А. И. Герцена, 1985. 67 с.

3. Виденский В. С. Многочлены Бернштейна. Л.: ЛГПИ им. А. И. Герцена, 1990. 63 с.

4. Голованов Н. Н. Геометрическое моделирование. М.: Физматлит, 2002. 472 с.

5. Голованов Н. Н., Ильютко Д. П., Носовский Г. В., Фоменко А. Т. Компьютерная геометрия. М.: Академия, 2006. 512 с.

6. Григорьев М. И. Геометрическое моделирование с использованием проективных кривых и поверхностей Безье // Тр. междунар. науч. конф. «Космос, астрономия и программирование» (Лавровские чтения). 20-22 мая 2008 г. СПб.: Изд-во С.-Петерб. ун-та. С. 200-205.

7. Григорьев М. И. Моделирование поверхностей вращения // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 27 июня 2007 г. (http://www.dha.spb.ru/reps07.shtml#0627).

8. Григорьев M. И. Обобщённые поверхности вращения // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 15 сентября 2007 г. (http://www.dha.spb.ru/reps07.shtml#0915).

9. Григорьев M. И. Полиномы Бернштейна от двух переменных // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2008-05.http://www.mathsoc.spb.ru/preprint/2008/index.html#05).

10. Григорьев M. И. Построение сферы с помощью проективных поверхностей Безье // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 3. С. 127-131.

11. Григорьев М. И., Малозёмов В. Н. Поле замкнутых кривых Безье // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 24 марта 2007 г. (http://www.dha.spb.ru/reps07.shtml#0324).

12. Григорьев M. И., Малозёмов В. H., Сергеев А. Н. О классифшкации дробно-рациональных кривых Безье второго порядка // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 2. С. 103-108.

13. Григорьев M. П., Малозёмов В. H., Сергеев А. Н. Полиномы Бернштейна и составные кривые Безье // Журн. вычисл. мат. и матем. физ. 2006. Т. 46. № 11. С. 1962 1971.

14. Григорьев М. И., Сергеев А. Н. Полярная форма полиномов от двух переменных // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2008-06.http://www.mathsoc.spb.ru/preprint/2008/index.html#06).

15. Иванов В. П., Батраков А. С. Трехмерная компьютерная графика. М.: Радио и связь, 1995. 224 с.

16. Кастельжо П. Теория полюсов. В кн.: Математика и САПР. 1. Пер. с франц. М.: Мир, 1988. С. 130-200.

17. Малозёмов В. Н., Сергеев А. Н. Аналитические основы теории полярных форм // Алгебра и анализ. 1998. Т. 10. Вып. 6. С. 156-185.

18. Мысовских И. П. Лекции по численным методам. Изд. второе. СПб.: Изд-во СПбГУ, 1998. 472 с.

19. Погорелов А. И. Дифференциальная геометрия. 6-е изд. М.: Наука, 1974. 176 с.

20. Привалов И. И. Аналитическая геометрия. 35-е изд. Лань, 2005. 304 с.

21. Роджерс Д., Адаме Дж. Математические основы машинной графики. Пер. с англ. М.: Мир, 2001. 604 с.

22. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 2001. 464 с.

23. Шикин Е. В., Плис А. И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. М.: ДИАЛОГ-МИФИ, 1996. 240 с.

24. Agoston М. Computer Graphics and Geometric Modeling. Mathematics. Springer, 2005. 971 p.

25. Agoston M. Computer Graphics and Geometric Modeling. Implementation and Algorithms. Springer, 2005. 920 p.

26. Bezier P. Numerical Control: Mathematics and Applications. Translated from the French by A. R. Forrest. Wiley, 1972. 256 p.

27. Dempski K. Focus on Curves and Surfaces. Premier, 2003. 269 p.

28. Eberly D. H. 3D Game Engine Design. A Practical Approach to RealTime Computer Graphics. Morgan-Kaufmann, 2002. 586 p.

29. Farin G. Class A Bezier curves // J. Computer Aided Geometric Design, 2006. No. 23. P. 573-581.

30. Farin G. Curves and Surfaces for CAGD. 5th ed. Academic Press, 2002. 520 p.

31. Forrest A. R. Interactive interpolation and approximation by Bezier polinomials // The Computer Journal. 1972. V. 15. No. 1. P. 71-79.

32. Herman I. The use of projective geometry in computer graphics. Springer, 1992. 151 p.

33. Marsh D. Applied Geometry for Computer Graphics and CAD. 2nd ed. Springer, 2005. 361 p.

34. Oruc II., Phillips G. M. q-Bernstein polynomials and Bezier curves // J. of Сотр. and Appl. Math., 2003. No. 151. P. 1-12.

35. Paoluzzi A. Geometric programming for computer aided design. Wiley, 2003. 799 p.

36. Piegl L., Tiller W. The NURBS Book 2nd ed. Springer, 1997. 646 p.

37. Ramshaw L. Blossoms are polar forms // Computer Aided Geometric Design 6, 1989. P. 323-358.

38. Sarfraz M. Advances in Geometric Modeling. Wiley, 2003. 319 p.

39. Salomon D. Curves and Surfaces for Computer Graphics. Springer, 2006. 465 p.

40. Salomon D. Transformations and Projections in Computer Graphics. Springer, 2006. 283 p.

41. Schneider P. J., Eberly D. H. Geometric tools for computer graphics. Elsevier, 2003. 1043 p.

42. Seidel H.-P. An introduction to polar forms // IEEE Computer Graphics and Applications. 1993. V. 13. No. 1. P. 38-46.

43. Vince J. Mathematics for computer graphics. 2nd ed. Springer, 2006. 251 p.

44. Winkel R. Generalized Bernstein Polynomials and Bezier Curves: An Application of Umbral Calculus to Computer Aided Geometric Design // J. Advances in Appl. Math., 2001. No. 27. P. 51-81.

45. Yamaguchi F. Curves and surfaces in computer aided geometric design. Springer, 1988. 390 p.