Дискретные периодические сплайны с векторными коэффициентами и поверхности Кунса

Область прикладной математики, называемая геометрическим моделированием (компьютерная геометрия, Computer Aided, Geometric Design, CAGD), активно развивается с середины 20-го века (см. [27]). В этой области изучаются способы построения кривых, поверхностей и тел, а также компьютерная реализация различных операций, производимых с ними. Геометрическому моделированию посвящены несколько книг и монографий, из которых можно выделить следующие [1, 2, 28, 36, 42, 45]. Кроме того, эта область является темой множества статей, часть из которых выходит в специализированных журналах (Computer Aided Geometric Design, Computers & Graphics, Computer Graphics and Image Processing).

Обычно в геометрическом моделировании кривая определяется как множество значений непрерывной вектор-функции, заданной на отрезке вещественной оси. Например, для построения замкнутых кривых можно использовать тригонометрические полиномы (см. [40, 43]). Однако реально используются значения вектор-функции только в некотором конечном числе точек. Поэтому можно с самого начала определять кривую при помощи вектор-функции, заданной на дискретном множестве. В случае замкнутой кривой для этой цели можно применить дискретные периодические сплайны [9], которые были введены для нужд дискретного гармонического анализа. Если в гармоническом анализе рассматривались сплайны с комплексными коэффициентами, то в геометрическом моделировании естественно использовать вещественные векторные коэффициенты. При этом свойства дискретных сплайнов можно распространить на получаемые кривые. Особенно важно свойство минимальной нормы, которое гарантирует, что построенные кривые не будут иметь нежелательных осцилляций.

Поверхность в геометрическом моделировании определяется вектор-функцией от двух параметров, заданных на прямоугольной или треугольной области. Существуют различные подходы к построению поверхностей. Один из способов предложил Стивен Куне (Steven Coons) в работе [26]. Он указал формулу поверхности, границей которой является заданный криволинейный четырёхугольник. Поверхности такого вида называются теперь билинейными поверхностями Кунса. В работе [26] вводится также бикубическая поверхность Кунса, которая интерполирует не только значения, но и производные на границе четырёхугольной области. Описание поверхностей Кунса в более простых обозначениях приведено в [29].

Часто для получения поверхности нужной формы недостаточно задать её граничные кривые. В таких случаях определяют сеть из пересекающихся кривых, через которые должна проходить поверхность. Требуемую поверхность можно составить из нескольких бикубических поверхностей Кунса, но для обеспечения гладкости необходимо согласовывать значения производных на кривых и в узлах сетки. Чтобы избежать связанных с этим трудностей, Уильям Гордон (William Gordon) предложил в [31] способ, позволяющий задать всю поверхность одной формулой. Построенная поверхность проходит через все кривые и обладает требуемой гладкостью. Поверхности такого вида называются поверхностями Гордона.

Идеи Кунса применимы не только для получения поверхностей с четырёхугольной областью определения параметров. В статье [24] показано, как построить поверхность, границей которой является заданный криволинейный треугольник. В отличие от поверхностей Кунса на четырёхугольнике, для треугольников существуют различные способы решения этой задачи (см. [33, 38]). Дальнейшие исследования привели к построению поверхности, заполняющей внутренность криволинейного пятиугольника [25] и, в общем случае, п-угольника [34, 35].

Изначально поверхности Кунса были получены как наиболее простые поверхности, удовлетворяющие заданным граничным условиям. При этом существует бесконечное множество других поверхностей, удовлетворяющих тем же условиям. Оказалось, что для некоторых видов граничных условий можно определить целевой функционал таким образом, что соответствующая поверхность Кунса будет доставлять минимум этому функционалу на множестве всех поверхностей, удовлетворяющих заданным условиям (см. [31, 37, 39]). Это свойство называется свойством минимальной нормы.

Были описаны различные способы обобщения поверхностей Кунса. В [30] показано, как обобщить формулу поверхности Кунса со случая двух переменных на случай произвольного количества переменных. Работа [41] посвящена рассмотрению вида зависимости внутренних точек поверхности Кунса от точек на границе. Например, каждая точка билинейной поверхности Кунса является линейной комбинацией восьми граничных точек. В общем случае зависимость может выражаться суммой граничных точек с некоторыми коэффициентами или даже интегралом по границе с некоторым весом. В статье [44] условия для поверхности Кунса задаются не граничными кривыми, а граничными поверхностями. Это позволяет строить поверхности Кунса, гладким образом заполняющие отверстия различной формы.

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

1. Построение замкнутых кривых при помощи дискретных периодических сплайнов с векторными коэффициентами и исследование свойств таких кривых.

2. Обобщение поверхностей Кунса, позволяющее определять замкнутые поверхности на базе дискретных периодических сплайнов.

3. Установление свойств минимальной нормы для получаемых кривых и поверхностей.

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

Первая глава посвящена построению кривых при помощи дискретных периодических сплайнов с векторными коэффициентами.

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

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

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

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

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

Шестой параграф посвящён предельным свойствам интерполяционных функций, введённых в предыдущем параграфе. Рассматривается последовательность mn-периодических вектор-функций, проходящих через фиксированные т точек и имеющих в них заданные направления. Устанавливается, что в пределе при п стремящемся к бесконечности множества значений интерполяционных вектор-функций сходятся к множеству значений некоторого полиномиального периодического сплайна от вещественной переменной. Для предельного сплайна доказывается свойство минимальной нормы.

Вторая часть диссертации посвящена поверхностям Кунса и их обобщениям.

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

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

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

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

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

Иллюстрации были получены при помощи разработанной автором программной системы, при реализации которой использовались работы [3, 23, 32].

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

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

2. Найдены предельные кривые для интерполяционных дискретных периодических сплайнов.

3. Разработан способ построения замкнутых кривых, проходящих через заданные точки и имеющих в них зада, нные направления. Исследованы экстремальные и предельные свойства этих кривых.

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

5. Установлено свойство минимальной нормы для обобщённой поверхности Кунса.

6. Найден предел дискретных поверхностей Кунса при уменьшении шага дискретизации и доказано свойство минимальной нормы для предельной поверхности.

Основные результаты опубликованы в работах [12, 13, 16, 17, 21, 22]. Предварительные результаты обсуждались на семинаре «Дискретный гармонический анализ и геометрическое моделирование» ([18−20]). По результатам работы были сделаны доклады на международной научной конференции «Космос, астрономия и программирование» (Лавровские чтения) [11] и на семинарах кафедры вычислительной математики и кафедры исследования операций математико-механического факультета СПбГУ.

Автор глубоко признателен своему научному руководителю профессору В. Н. Малозёмову за постановку интересных задач, обсуждение полученных результатов и постоянное внимание в процессе работы над диссертацией. Также автор благодарен О. В. Просекову и М. И. Григорьеву за советы по оформлению текстов, формул и рисунков в издательской системе Ш^Х.

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

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

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

4. Игнатов М. И., Певный А. Б. Натуральные сплайны многих переменных. Л.: Наука, 1991. 125 с.

5. Крылов В. И. Приближённое вычисление интегралов. 2-е изд. М.: Наука, 1967. 500 с.

6. Малозёмов В. Н., Машарский С. М. Основы дискретного гармонического анализа. Часть первая. СПб.: НИИММ, 2003. 100 с.

7. Малозёмов В. Н., Машарский С. М. Основы дискретного гармонического анализа. Часть третья. СПб.: НИИММ, 2003. 88 с.

8. Малозёмов В. Н., Певный А. Б. Дискретные периодические В-сплай-ны // Вестн. С.-Петерб. ун-та. Сер. 1. 1997. Вып. 4 (№ 22). С. 14−19.

9. Малозёмов В. Н., Певный А. Б. Дискретные периодические сплайны и их вычислительные применения // Журн. вычисл. мат. и матем. физ. 1998. Т. 38. № 8. С. 1235−1246.

10. Малозёмов В. Н., Певный А. Б. Полиномиальные сплайны. JL: Изд-во Ленингр. ун-та, 1986. 120 с.

11. Малозёмов В. Н., Чашников Н. В. Дискретные периодические сплайны с векторными коэффициентами и геометрическое моделирование // Доклады РАН. 2009. Т. 429. № 1. С. 19—21.

12. Малозёмов В. Н., Чашников Н. В. Параметрические поверхности Кунса // Вестн. С.-Петерб. ун-та. Сер. 10. 2008. Вып. 2. С. 16−22.

13. Натансон И. П. Теория функций вещественной переменной. 3-е изд. СПб.: Лань, 1999. 560 с.

14. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. 8-е изд. М.: Физматлит, 2006. Т. 1. 680 с.

15. Чашников Н. В. Составные параметрические поверхности Кунса // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Вып. 2. С. 141−145.

16. Чашников Н. В. Аналог эрмитовой интерполяции в дискретном периодическом случае // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2009;09.http://www.mathsoc.spb.ru/preprint/2009/index.html#09).

17. Чашников H. В. Обобщённые и составные поверхности Кунса // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 15 марта 2008 г. (http://www.dha.spb.ru/reps08.shtml#0315).

18. Чашников Н. В. Поверхность вращения как поверхность Кунса // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 28 августа 2007 г. (http://www.dha.spb.ru/reps07.shtml#0828).

19. Чашников H. В. Поверхности Кунса класса С2 // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD). Избранные доклады. 16 мая 2009 г. http://www.dha.spb.ru/reps09.shtml#0516).

20. Чашников H. В. Предельные кривые для дискретного аналога эрмитовой сплайн-интерполяции // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2009;11.http://www.mathsoc.spb.ru/preprint/2009/index.html#ll).

21. Чашников H. В. Предельные кривые для дискретных периодических сплайнов // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2009;08.http://www.mathsoc.spb.ru/preprint/2009/index.html#08).

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

23. Barnhill R., Birkhoff G., Gordon W. Smooth interpolation in triangles //J. of Approximation Theory. 1973. № 8. P. 114−128.

24. Charrot P., Gregory J. A pentagonal surface patch for computer aided geometric design // Computer Aided Geometric Design. 1984. Vol. 1. № 1. P. 87−94.

25. Coons S. Surfaces for computer aided design of space forms. Technical report, MIT, 1967.

26. Farin G. A history of curves and surfaces in CAGD. In book: Handbook of Computer Aided Geometric Design. Elsevier, 2002. P. 1−21.

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

28. Forrest A. On Coons and other methods for the representation of curved surfaces //Computer Graphics and Image Processing. 1972. Vol. 1. № 4. P. 341−359.

29. Gordon W. Blending-function methods of biuariate and multivariate interpolation and approximation // J. Numer. Anal. 1971. Vol. 8. № 1. P. 158−177.

30. Gordon W. Spline-blended surface interpolation through curve networks // J. of Math, and Mechanics. 1969. Vol. 18. № 10. P. 931−952.

31. Gouraud H. Continuous shading of curves surfaces // IEEE Transaction on computers. 1971. Vol. 20. № 6. P. 623−628.

32. Gregory J. Interpolation to boundary data on the simplex j/ Computer Aided Geometric Design. 1985. Vol. 2. № 1. P. 43−52.

33. Gregory J., Lau V., Zhou J. Smooth parametric surfaces and n-sided patches. In book: Computation of Curves and Surfaces. Kluwer Academic Publishers, 1990. P. 457—498.

34. Gregory J, Lau V., Hahn J. High order continuous polygonal patches. In book: Geometric Modelling. Springer, 1993. P. 117−132.

35. Heckbert P. Graphics Gems IV. Academic Press, 1994.

36. Nielson G. Minimum norm interpolation in triangles // J. Numer. Anal. 1980. Vol. 17. № 1. P. 44−62.

37. Nielson G. The Side-Vertex Method for Interpolation in Triangles // J. of Approximation Theory. 1979. № 25. P. 318−336.

38. Qu R., Ye J. Approximation of Minimum Energy Surfaces Using Optimal Twists // Mathl. Comput. Modelling. 1998. Vol. 28. № 11. P. 41−48.

39. Roth A., Juhasz I., Schicho Л., Hoffmann M. A cyclic basis for closed curve and surface modeling // Computer Aided Geometric Design. 2009. Vol. 26. № 5. P. 528−546.

40. Sabin M. Transfinite Surface Interpolation // Proceedings of the 6th IMA Conference on the Mathematics of Surfaces. 1994. P. 517−534.

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

42. Sanchez-Reyes J. Periodic Bezier curves // Computer Aided Geometric Design. 2009. Vol. 26. № 9. P. 989−1005.

43. Szilvasi-Nagy M., Szabo I. Generalization of Coons' construction // Computers & Graphics. 2006. Vol. 30. № 4. P. 588—597.

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