НАУКА и ОБРАЗОВАНИЕ

Харламов В.В.

Научный руководитель: к.ф.-м.н., доцент Храпов П.В.

Кафедра ФН1, МГТУ им. Н.Э. Баумана, Москва, Россия.

            Согласно современным историческим сведениям, сплайны (от англ. spline – длинная узкая полоса дерева или металла; рейка) использовались судостроителями еще в XVI веке. Перед ними стояла следующая задача: через опорные точки, расположение которых известно, требуется провести непрерывную гладкую кривую. Задача решалась путем закрепления в этих точках гибкой деревянной рейки, которая, изгибаясь, принимала требуемую форму. Для разрешения проблем подобного рода методами прикладной математики применяется интерполяция [2].

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

Форма физического сплайна (отклонение y) определяется уравнением Эйлера [1] для момента изгиба M(x) вдоль рейки:

где E – модуль Юнга, зависящий от свойств материала рейки, I – момент инерции, определяемый формой кривой, R(x) – радиус кривизны.

            Для малых отклонений (y’ << 1) справедливо приближенное равенство

Уравнение Эйлера принимает вид

Момент изгиба между точками закрепления изменяется линейно. Подставляя M(x) = Ax+B в уравнение Эйлера, получаем:

и после двойного интегрирования

Таким образом, форма сплайна задается кубическим полиномом.

Определение. Сплайном порядка m называется функция, которая является многочленом степени m на каждом из частичных интервалов [x_i-1, x_i] (i = 1, 2, …, n), принимает заданные значения y_i в узлах x_i (i = 0, 1, 2, …, n) и имеет непрерывные производные до (m – 1)-го порядка включительно.

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

Цель данной работы – разработка программы, строящей стереоизображение замкнутой сплайновой кривой, проходящей через заданные узловые точки с заданными радиус-векторами P₀,…, P_n (см. рис. 1).

Рис. 1

Векторное параметрическое уравнение сплайновой кривой на i-м частичном интервале имеет вид

            P(t) = A_i + B_i(t - t_i-1) + C_i(t - t_i-1)² + D_i(t - t_i-1)³,                                                     (1a)

где t_i-1 ≤ t ≤ t_i (i = 1, …, n), n – число сплайновых сегментов

Значения параметра в узловых точках задаются следующим образом: t₀ = 0, а разность t_i - t_i-1 (i = 1, …, n) принимается равной расстоянию между соответствующими узловыми точками.

Коэффициенты многочлена на каждом интервале определяют из условий в узлах:

- условие прохождения кривой через узловые точки:

P(t_i-1) = P_i-1 = A_i;                                                                                          (1b)

- условия непрерывности первой и второй производных в узловых точках:

P’(t_i - 0) = P’(t_i + 0);                                                                                     (1c)

P”(t_i - 0) = P”(t_i + 0);                                                                                    (1d)

            - циклические концевые условия (требование замкнутости кривой):

P’(t₀) = P’(t_n);                                                                                               (1e)

P”(t₀) = P”(t_n).                                                                                               (1f)

Из (1a):                                                                                                                                

            P(t_i) = A_i + B_ih_i + C_ih_i² + D_ih_i³,                                                                                (2)

где h_i = t_i - t_i-1, i = 1, …, n;

P’(t) = B_i + 2C_i(t - t_i-1) + 3D_i(t - t_i-1)²;                                                                     (3)

P”(t) = 2C_i + 6D_i(t - t_i-1).                                                                                          (4)

Из (3) и (1с):

            P’(t_i - 0) = B_i + 2C_ih_i + 3D_ih_i² = P’(t_i + 0) = B_i+1.                                                  (5)

Из (4) и (1d):

            P”(t_i - 0) = 2C_i + 6D_ih_i = P”(t_i + 0) = 2C_i+1.                                                           (6)

Из (6): D_i = (C_i+1 – C_i)/(3h_i).                                                                                               (7)

Из (1b), (2) и (7):

B_i = (P_i – P_i-1)/h_i – C_ih_i – D_ih_i² =

                = (P_i – P_i-1)/h_i – C_ih_i - h_i²(C_i+1 – C_i)/(3h_i) =

                = (P_i – P_i-1)/h_i – h_i(2C_i + C_i+1)/3.                                                                        (8)

Подставим (7) и (8) в (5):

            (P_i – P_i-1)/h_i – h_i(2C_i + C_i+1)/3 + 2C_ih + 3h_i²(C_i+1 – C_i)/(3h_i) =

             = (P_i+1 – P_i)/h_i+1 – h_i+1(2C_i+1 + C_i+2)/3; =>

=>        h_iC_i/3 + (2h_i/3 + 2h_i+1/3)C_i+1 + h_i+1C_i+2/3 = (P_i+1 – P_i)/h_i+1 - (P_i – P_i-1)/h_i.          (*)

Из (1e) и (3):

            B₁ = B_n + 2C_nh_n + 3D_nh_n².                                                                                     (9)

Подставим (7) и (8) в (9):

(P₁ – P₀)/h₁ – h₁(2C₁ + C₂)/3 = (P_n - P_n-1)/h_n –

– h_n(2C_n + C_n+1)/3 + 2C_nh_n + 3h_n²(C_n+1 – C_n)/(3h_n); =>

=>       2h₁C₁ + h₁C₂ + h_nC_n + 2h_nC_n+1 = 3(P₁ - P₀)/h₁ – 3(P_n - P_n-1)/h_n.                         (**)

Из (1f) и (4):

            2C₁ = 2C_n + 6D_nh_n.                                                                                                (10)

Подставим (7) в (10):

            2C₁ = 2C_n + 6h_n(C_n+1 – C_n)/(3h_n), => C₁ – C_n+1 = 0.                                            (***)

            Уравнения (*), (**) и (***) образуют систему линейных алгебраических уравнений (СЛАУ) с n + 1 уравнениями и неизвестными. Из нее находятся коэффициенты C_i, затем коэффициенты A_i, B_i, D_i находятся из уравнений (1b), (8), (7). Полученная СЛАУ не является системой специального вида, и к ней неприменимы специальные методы решения. В разработанной демонстрационной программе эта система уравнений решается методом Гаусса с выбором главного элемента [3].

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

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

Один из методов создания стереоизображений называется цветовым анаглифом [1]. Суть его в том, что создаются двумя разными цветами два изображения – одно для левого и другое для правого глаза. При просмотре через соответствующие светофильтры левый глаз видит только левое изображение, а правый – только правое. Система глаз-мозг объединяет оба плоских изображений в одно трехмерное.

            На рис. 2 показана схема хода лучей при просмотре стереоизображения, а также приведены расчетные схемы и зависимости, необходимые для вычисления координат точек стереоизображения.

Рис. 2

            Здесь P – точка видимого трехмерного изображения, P_R и P_L – точки на экране, предназначенные для наблюдения правым и левым глазами соответственно. Приведенные зависимости позволяют для каждой найденной точки P сплайновой кривой определить экранные координаты соответствующих ей точек P_R и P_L стереоизображения, которое, так же как и сплайн, строится методом линейной аппроксимации.

            Демонстрационная программа написана на языке C++ с использованием графической библиотеки OpenGL и предназначена для функционирования в операционной системе MS Windows XP [3]. Программа позволяет интерактивно задавать узловые точки сплайна, а также осуществлять вращение кривой для удобства просмотра.

Замечание: для наблюдения стереоизображения необходимы анаглифические очки с красным и синим светофильтрами.

Пример работы программы приведен на рис. 3.

Рис. 3

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

Литература

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

2. Самарский А. А., Гулин А. В. Численные методы: учебное пособие для вузов. – М.: Наука. Гл. ред. физ-мат. лит., 1989.

3. Черносвитов. А. Visual C++ 7: учебный курс. – СПб.: Питер, 2001.