5.9. Аппроксимация на основе B-сплайнов

Основу метода Безье составляет аппроксимация многочленами Бернштейна. Однако можно выбрать и другие наборы базисных функ­ций, например B-сплайны, по отношению к которым базис Бернштейна является частным случаем. В сравнении с многочленами Бернштейна B-сплайны обладают следующими дополнительными преимуществами [15], [16]:

1. Аппроксимация B-сплайнами обеспечивает более точное приб­лижение ломаной, чем ап­прок­си­ма­ция многочленами Бернштейна.

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

3. Единственным путем увеличения (уменьшения) порядка кривой Безье является уве­ли­че­ние (уменьшение) числа вершин и соответст­вующей ломаной Безье. В методе B-сплай­нов эти два параметра независимы и, следовательно, могут быть выбраны произвольно.

Кривая, построенная на основе B-сплайн-базиса, описывается следующим образом [см. СПИСОК ЛИТЕРАТУРЫ]:

(5.13)
где - радиус-вектор точек на кривой, - вершины аппрокси­мируемой ломаной (всего вершин n+1), а Nik(t) - весовая функция i-й нормализованной B-сплайн базисной кривой порядка k (т. е. степени k-1), задаваемая рекуррентными соотношениями:

(5.14)

Здесь xi – элементы узлового вектора, а t – параметр, изменяю­щийся в диапазоне от 0 до tmax=(n – k+2).


Рис.5.9. Изображение нескольких B-сплайн-кривых различного порядка.

Узловой вектор, длина которого (n+k+1), вводится для учета собственной кривизны B-сплайн-кривых и представляет собой неубы­вающую последовательность целых чисел - параметрических узлов. Узловой вектор определяется числом точек в аппроксимируемой ломаной, порядком кривой, а также наличием сложных (кратных) узлов.

Из (5.13) и (5.14) следует, что B-сплайн-кривая является полиномом степени (k–1) на каждом интервале (xi, xi+1) и что все ее производные до (k–2)-го порядка включительно непрерывны вдоль всей кривой. То есть эта кривая представляет собой сплайн-функцию порядка k (степени k–1).

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


Рис.5.10. B-сплайн-кривые со сдвоенной вершиной. В этой вер­шине в кривой третьего порядка образуется излом

В формируемые кривые можно вносить изломы путем включения в соответствующую ломаную кратных вершин. Так, для образования излома в кривой третьего порядка необходима сдвоенная вершина (рис.5.10). А чтобы создать излом в кривой четвертого порядка, потребуется вершина с кратностью три и т. д.

Большое количество примеров, иллюстрирующих различные спо­собы построения B-сплайн-кривых, читатель может найти в [см. СПИСОК ЛИТЕРАТУРЫ].

Аппроксимация B-сплайнами реализована в программах BSPLN2 и BSPLN3. Первая из них предназначена для формирования плоских, а вторая - пространственных B-сплайн-кривых.

Программа BSPLN2(K,XP,YP,NPLG,XC,YC,NPTS,WFUN,NWF,VKNOTS,NKNOTS) поз­во­ля­ет вычислить значения координат точек плоской B-сплайн-кривой, ап­прок­си­ми­рую­щей заданную совокупность точек. Программа имеет следующие параметры:

K
порядок аппроксимирующей кривой (ее степень равна K-1), 2 < K < NPLG;
XP,YP
векторы значений соответственно X-, и Y-координат заданной совокупности точек (аппроксимируемой ломаной) длины NPLG;
NPLG
число точек в аппроксимируемой ломаной;
XC,YC
векторы значений соответственно X-, и Y-координат аппроксимирующей B-сплайн-кривой (длины NPTS);
NPTS
число точек в аппроксимирующей B-сплайн-кривой;
WFUN
двумерный рабочий массив, предназначенный для разме­щения весовых функций B-сплайн-базиса, размером (NW,K);
NWF
максимальное значение, принимаемое первым индексом рабочего массива WFUN, NWF = (NPLG+K-1);
VKNOTS
одномерный рабочий массив, предназначенный для раз­мещения эле­мен­тов уз­ло­во­го вектора, длины NKNOTS;
NKNOTS
длина узлового вектора, NKNOTS = (NPLG+K).

Программа BSPLN3(K,XP,YP,ZP,NPLG,XC,YC,ZC,NPTS,WFUN,NWF,VKNOTS,NKNOTS) позволяет вычислить значения координат точек пространственной B-сплайн-кривой, аппроксимирующей заданную со­вокупность точек. Параметры программы следующие:

XP,YP,ZP
векторы значений соответственно X-, Y- и Z-ко­ординат заданной совокупности точек аппроксимируемой ломаной длины NPLG;
XC,YC,ZC
векторы значений соответственно X-,Y- и Z-коор­динат ап­прок­си­ми­рую­щей B-сплайн-кривой длины NPTS.

Остальные параметры имеют то же значение, что и в программе BSPLN2.

В программах BSPLN2 и BSPLN3 используются служебные програм­мы KNOTV2(K,XP,YP,NPLG,VKNOTS,NKNOTS) и KNOTV3(K,XP,YP,ZP,NPLG,VKNOTS,NKNOTS) с по­мо­щью которых строятся узловые векторы соответственно для двумерного и трех­мер­но­го случаев. Параметры этих программ имеют то же значение, что и в программах BSPLN2 и BSPLN3.

Ниже приведена программа, с помощью которой выполнялось по­строение рис.5.10. 

     REAL XP(6),YP(6)
     REAL XC1(41),YC1(41),XC2(41),YC2(41),XC3(41),YC3(41)
     REAL WF1(8,3),WF2(10,5),WF3(11,6),VK(13)
     DATA XP/2.,1.,2*5.,9.,8./
     DATA YP/9.,5.,2*1.,5.,9./,NP,NS/6,41/
     CALL BSPLN2(3,XP,YP,NP,XC1,YC1,NS,WF1,8,VK,9)
     CALL BSPLN2(5,XP,YP,NP,XC2,YC2,NS,WF2,10,VK,11)
     CALL BSPLN2(6,XP,YP,NP,XC3,YC3,NS,WF3,11,VK,12)
     CALL PAGE(18.,18.,'5.10',4,0)
     CALL REGION(1.,1.,16.,16.,0,0,1)
     CALL AXES('X',1,0.,5,'Y',1,0.,5,0)
     CALL LINEMO(XP,YP,NP,1,-1)
     CALL LINEO(XC1,YC1,NS)
     CALL LINEO(XC2,YC2,NS)
     CALL LINEO(XC3,YC3,NS)
     CALL ENDPG(0)
     END