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

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

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

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

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

Кривая, построенная на основе B-сплайн-базиса, описывается следующим образом [лит]:

(5.13)

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

(5.14)

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

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

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

Из (5.13) и (5.14) следует, что B-сплайн-кривая является полиномом степени (k–1) на каждом интервале (x_i,x_i+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-сплайн-базиса, размером (NWF, 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