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

• Григорьев, Михаил Игоревич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Григорьев, Михаил Игоревич

Введение.

Глава 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] и на семинарах кафедры исследования операций и кафедры вычислительной математики математико-меха-нического факультета СПбГУ.

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

Список литературы диссертационного исследования кандидат физико-математических наук Григорьев, Михаил Игоревич, 2009 год

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.