Матричные методы рекластеризации составных объектов Безье

УДК 681.3.513

Е.А. Никулин

МАТРИЧНЫЕ МЕТОДЫ РЕКЛАСТЕРИЗАЦИИ СОСТАВНЫХ ОБЪЕКТОВ БЕЗЬЕ

Нижегородский государственный технический университет им. Р.Е. Алексеева

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

Метод решения. Алгоритмы рекластеризации основаны на матричном подходе, дающем единую компактную формулу пересчета кластеров как в сторону увеличения, так и уменьшения их размеров.

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

Ключевые слова: кривая, поверхность, Безье, полином, сегмент, сопряжение.

Широкое распространение в САПР получили объекты (линии и поверхности) Безье благодаря простоте их построения, хорошей гибкости и редактируемости. Ввиду ослабления влияния узловой вершины характеристической сети на форму объекта при ее удалении от краев сети лучше разделить сеть большого размера на кластеры небольших (не более пятого-шестого) порядков так, чтобы каждый кластер управлял формой своего сегмента.

К примеру, г-й полиномиальный сегмент составной линии порядка пг>1 может быть построен на характеристической полилинии (ХП) и^и^.-.и^, как бинарное разложение по узловым точкам, составляющим кластерную вектор-строку и, =[и/0 иг1 ... ип], и базисным функциям параметра составляющим вектор-столбец Тп, (?)=[1 1 ... ]т :

Р,-= и,И,ТП1

к=0 у=0

Для целых т > 1 верхняя треугольная (т+1)х(т+1)-матрица Нт заполнена коэффициентами

кк]={-\У~катС) 0 < к < / < т.

Гладкое сопряжение сегментов рг(^) и рг+1(^) достигается выбором характеристических узлов уравнивающих векторов их первых двух производных в общей точке ип. = и,-+1 о = Ч,- :

У,- (1)=п (Ч/ - и/лг -1 )=п/+1(и/+1,1 - Ч/ )= У+Л0)'

А,-

На рис. 1 приведен пример шестисегментной составной линии Безье с порядками сегментов п1 = п2 = 5, п3 = 6, п4 = 4, п5 = 1, п6 = 3, гладким сопряжением сегментов в точке q1 и дважды гладким сопряжением в точке q2.

Составная поверхность Безье строится на характеристической полигональной сети (ХПС), матрично разбитой на N х М кластеров игу. Параметрическая модель (г, у)-го сегмента с порядками полиномов пг х т¡- имеет вид

р,

На рис. 2 показана поверхность Безье, составленная из 5 х 4 = 20-ти бикубических сегментов с первым порядком гладкости их сопряжения друг с другом.

© Никулин Е.А., 2012.

Рис. 1. Составная линия Безье

Рис. 2. Составная поверхность Безье

В [1] предложен новый, матричный метод решения одной из задач модификации объектов Безье — изменения (увеличения и уменьшения) порядков полиномов линий и поверхностей с сохранением их формы. В данной статье рассматриваются еще две модификации, связанные с рекластеризацией узловой сети — изменением ее структуры путем разделения одного кластера на несколько или объединения нескольких кластеров в один. Учебники по компьютерной геометрии и графике [2, 3] содержат решение лишь линейного варианта задачи разделения одного сегмента на два такого же порядка. Целью настоящей работы является получение компактных матричных решений обеих задач рекластеризации как для линий, так и для поверхностей, и к тому же с выбором порядков сегментов.

Разделение линии Безье

Начнем с разделения линии Безье р(^) порядка п, построенной на ХП и = и0и ... ип, на два сегмента р1(^) и р2(^) порядков V > 1 и д > 1 с параметрическими моделями

р

Новые сегменты и их кластеры Б = Ь0Ь1 ... Ь и С = с0с1 ... сд граничат по точке разделения р1(1) = К = р2(0) = с0. Рассмотрим два способа деления линии Безье и их свойства.

Ручной разрез исходной ХП по внутренней вершине и с номером vе[1, п - 1] разбивает ее на два кластера Б = и0 ... и^и и С = и^+1 ... ип порядков V и д = п - V. Поскольку линия р(^) не проходит через внутренний узел и^ а линии р1(^) и р2(^) в нем соединяются, то форма составной линии после такого деления изменяется (рис. 3, а). Кроме того, из-за произвольного расположения вершин и^ и и^2 новые кластеры не удовлетворяют условиям гладкого сопряжения (3). В результате сопряжение новых сегментов происходит с изломом, т. е. с потерей гладкости.

В рамках алгоритмического подхода полилиния и заменяется такими кластерами Б и С, что составная линия р1(^) и р2(^) совпадает с линией р(^) (рис. 3, б). Назначим параметр ге (0, 1), задающий точку разделения рг = р(г). Линии Безье трех сегментов представляют один и тот же полином в разных комбинациях параметра V.

р1

Подставив модели сегментов (5) в (6), сведем уравнения связи векторных полиномов к порядкам кластеров В и С путем изменения порядка вектора базовых функций по формуле т„(0 = Е„+1.,„+1Т,„(0, в которой Е,/.у обозначает М /Л'-матрицу, заполненную нулями и тт(М, Щ единицами на главной диагонали:

У+1Ту

u

u,

uA

а)

v+1

С

1С

u

p

S С2 . 2

u,

2/

b , c„

v 0

v—1

Ь2 P(t) ' i

u

ui bi b0

0

п=у=д

б)

u,

c b. b ^ u7

u n 0o-% 3 ° 2 u4 ciïf

4b2

2 N\ I 1 ^

v=4 2 Д;"1

^=3 Pi(t) \p2(0

Pr

n=5 c ^

b

c,

u

u

в)

Рис. 3. Разделение линии Безье: а - ручное, б, в - алгоритмическое

Составим невырожденную матрицу преобразования Тп(т) = Ъп(т^)Тп(1) из шкалы параметра I в шкалу масштабированного и смещенного параметра т = т1 +

" 1 " " 1 " " 1 0 0 . 0 "

mt+^ t s m 0 . 0

(mt+^ )n tn _ sn Clnmsn-1 C2m2sn-2 . . mn

Переведем с помощью этой матрицы векторы базовых функций из произвольных параметрических шкал rte [0, r] и (1 - r)t + re [r, 1] в нормированную шкалу te [0, 1]

Tv(rt) = Dv(r, 0)Tv(t), Тц((1 - r)t + r) = D(1 - r, r)T^(t) и разрешим уравнения (7) относительно искомых векторов B и C для всех значений t:

B=UH „E„+1,v+1Dv(r,0)H-1, C=UH „Еи+1 +1D^(l- r,r)H-1.

Унд .

Обоснуем выполненные в (7) преобразования векторов базисных функций в зависимости от соотношений порядков исходного сегмента р(^) и разделенных сегментов р1(^) и р2(0: • при выборе порядков V > п и д > п замены вектора Тп векторами

En+1,v+1Tv :

T

O

v-n,1

еп+1,д+1тд :

T

O

д-п,1

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

вн = [вн„ 1°1,у-и J, внц = [вн„ 101,ц-й ]

будут содержать справа V - п и, соответственно, д - п нулевых столбцов;

• при выборе порядков V < п или д < п (рис. 3, в) замены вектора Тп векторами

г т .

En+1,v+1 Tv "

T

O

n-v,1

Г T .

Еи+1,ц+1 Ад :

T

O

п-д,1

возможны лишь при условии, что реальная степень полинома р(^) не превышает значений V или д, а дефект степени ё > п - V или ё > п - д. Для этого вектор полиномиальных коэффициентов разделяемого сегмента должен содержать справа п - V или п - д нулевых столбцов:

внп = [вну ! °1,и_у J, внп = [вн„ ! °1,й-д J.

c

Неравенство v|bv - bv-i| ф ^jci - co| длин параллельных касательных векторов, хорошо заметное на рис. 3, б, означает, что полученные после разделения новые сегменты Безье обладают лишь нормированной гладкостью сопряжения друг с другом, а также с окружающими старыми сегментами. Моделирование выявило следующие зависимости векторов двух производных полиномов p1(í) и p2(t) в точке деления pr:

Отсюда видно, что только при выборе параметра разделения r = 0.5 сопряжение новых сегментов становится согласно (3) дважды гладким.

Пример 1. Разделить линию Безье, построенную на ХП с вершинами и0 =[10 0]т,

и =[22 6]т, и2 =[19 12]т, и3 =[11 15]т, и4 =[8 12]т и и5 =[20 0]т, на два сегмента с параметром разделения г = 0.6 (рис. 3, в).

Решение. Сформировав из характеристических вершин и по формуле (2) матрицы

U5 =

10 22 19 11 8 20 0 6 12 15 12 0

И,

1 - 5 10 -10 5 -1" 0 5 -20 30 -20 5 0 0 10 -30 30 -10 0 0 0 10 -20 10 0 0 0 0 5 - 5

0 0 0 0 0 1_ вычислим точку разделения линии Безье, имеющей формальную степень п = 5:

pr = UH5T5(r)=[13.6 11.52]г.

S=UH

5 -

D4 (0.6,0)=diag

D3 (0.4,0.6)=

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

"10 60 -150 100 0 0" 0 30 0 -30 0 0

означают дефект степени полинома ё = 2 и его реальную степень п - ё = 3.

Выбрав степени новых полиномов V = 4 > 3, д = 3 и сформировав по (8) матрицы 1 0 0 0 0 " 0 0.6 0 0 0 0 0 0.36 0 0 0 0 0 0.216 0 0 0 0 0 0.1296

вычислим по

В=ттн Е П Г06 0^Н-! =[Ю 19 19 15.4 13.6 В=ЦН^^(°.6,°)Н4 = 0 4.5 9 11.88 11.52

" 13.6 16 22 10 11.52 12 6 0

и составим полиномиальные модели линий Безье с реальными степенями, равными трем:

10 0 0 0.6 0.4 0 0 0.36 0.48 0.16 0 0.216 0.432 0.288 0.064

C=UH 5E64D3 (0.4,0.6)h-1 =

Р1 (t )=BH 4T4 (t )=

10+36t -54t2 + 21.6t3

18t - 6.48t

3

, P2 (t )=CH3T3 (t )=

13.6 - 4.8t+4.8t2 + 6.4t3 11.52 -0.96t-8.64t2 -1.92t3

Анализируя пары векторов двух производных в точке сопряжения

V(1)=4(Ь4 -Ьэ)=[-7.2 -1.44] и У2(0)=3(с )=[-4.8 -0.96], А1 (1)=12(Ь4-2Ь3 + Ь2)=[21.6 -38.88] и А2(0)=6(с2 -2с1 + с0)=[9.6 -17.28],

убеждаемся в их коллинеарности, но отношении длин в г / (1 - г) = 1.5 и Г  / (1 - г)2 = 2.25 раз. Это подтверждает вывод, что при коэффициенте г Ф 0.5 кривая Безье разделяется на сегменты, обладающие лишь нормированной двойной гладкостью сопряжения.

Объединение линий Безье

Рассмотрим два способа и свойства объединения двух линий Безье р^) и р2(0, построенных по (5) на узловых кластерах В = ЬоЬ1 ... Ь и С = СоС1 ... сд порядков V и д, в одну линию р(^), включая выбор ее порядка п и вершин кластера и = и0и1 ... ип.

Простое соединение полилиний В и С по их общей вершине Ь = с0 в полилинию и = Ь0 ... Ь^ ... сд порядка п = V + д дает сегмент р(^) = иНпТп(0, не совпадающий с линиями р1(1) и р2(1;), так как точка ^ = К = с0 не является концевой в кластере и (см. рис. 3, а). Благодаря вхождению цепочек Ь0Ь1Ь2 и сд-2сд-1сд в объединение и = В и С условия сопряжения линии р(1;) с окружающими ее сегментами сохраняются.

По второму алгоритмическому способу кластеры В и С заменяются такой характеристической полилинией и, что построенный на ней сегмент Безье р(1;) точно совпадает с составной линией р1(1) и р2(1;) (см. рис. 3, б, в). По сути эта задача обратна рассмотренной выше задаче разделения кластера и входит в круг задач редактирования составных линий Безье.

Если при разделении кластера параметр г задавался произвольно, то в обратной задаче его нужно каким-то образом вычислить. Поскольку линии р1(1) и р2(1;) сопряжены гладко, пусть и нормированно, то в точке К = с0 векторы направлений У1(1) = v(bV - Ь^) и У2(0) = д(с1 - с0) коллинеарны. Их длины связаны между собой первым в (10) соотношением, из которого и находится параметр разделения:

__1_

При равенстве векторов У1(1) = У2(0) в (11) будет получено г = 0.5. Другие значения г означают не полную, а лишь нормированную гладкость сопряжения линий р1(^) и р2(0, при которой в (3) совпадают лишь направления векторов производных.

Замена двух сегментов Безье одним возможна лишь тогда, когда все три линии представляют один и тот же полином. Именно из этих свойств (6) и получены зависимости (9) между тремя кластерами и, В и С. Здесь же нужно проверить способность кластеров В и С быть основами разных частей единого сегмента р1(^) и р2(0 без привлечения неизвестного пока кластера и. Приведя соотношения (7) к единому порядку п

ВНЕ+^Тпф = иНпБп(г, 0)Тп(0, СНдЕд+1,п+1Тп(0 = иН^О - г, г)Тп(0, (12) получим благодаря невырожденности матрицы (8) тест возможности объединения сегментов Безье р1(^) и р2(^) в одну линию р(^):

1Б-!(г,0)=СИдЕд^Б-1 (1-г,г).

В^Е+1,и+1Б

Из тех же соотношений находится искомый вектор вершин объединяющего кластера:

и=BИvEv+l/г+lD-1(г,0)И-1.

и«-1

I

с ✓

д

и

п

// \ Ч р(0 /?Ь2

«ь1

I

\

«I I 1 с^ — -

Ь

\

и

0 и

и2

с Ь

с .

v=4

д=3

п=3

Ь0С^

и0

0Ь4 Ь

о. 3 \

ч Ь

? 2

I - •

Ж

Р2(^) с3

и3

и,

с

а) б)

Рис. 4. Объединение линий Безье

Если полилинии В и С не удовлетворяют условию (13), то в (14) будет получен кластер линии Безье, не проходящей по исходным линиям р^/) и р2(/), как показано на рис. 4, а. В расчетах с обратной матрицей (8) можно использовать ее свойство

БТ (т-1,-.™-1).

Сделанные в (12) подстановки Ту(0 = ЕУ+1,И+1Т„(^) и Тд(/) = Ец+1,„+1Т„(^) возможны всегда при выборе порядка объединенного сегмента п > шах(у, д}. Наименьшее значение п, при котором задача объединения имеет точное решение (14) при условии (13), ограничено наибольшей реальной степенью полиномов р1(^) и р2(/).

Пример 2. Объединить по возможности сегменты Безье р1(1) и р2(1;) порядков V = 4 и д = 3 (см. рис. 3,в) в одну линию минимального порядка.

Решение. В примере 1 показано, что реальные степени дважды гладко сопряженных сегментов р1(^) и р2(/) равны трем. Если возможность объединения этих сегментов существует, то минимальная степень полинома р(/) также будет составлять п = 3.

Используя найденное там же соотношение длин касательных векторов в точке сопряжения |У1(1)| / |У2(0)| = 1.5, вычислим по (11) параметр деления г = 1 / (1 + 2/3) = 0.6 и проведем тест (13) с обратными матрицами Б-1 (3/5,0)=Б3(5/3,0) и Б-1(2/5,3/5)=Б3(5/3,-1):

ВН4Е54Б3 (5/3,0)=СН3Б3 (У3,-1)=[^0 60 Т 100"

Таким образом, объединение сегментов возможно.

Вычислив по (14) матрицу вершин объединяющего кластера, построим на нем параметрическую модель линии Безье третьего порядка (рис. 4, б):

"10 30 0 20" / ч_ттжт „ /

0 10 20 0 , р(/)=ин3X3^ 30/-30Г

и=ВН4Е54Б3 (53,0)н-1 =

10+60/ -150/2 +100/3

3

Разделение поверхности Безье

Распространим линейный алгоритм (6) ^ (9) на задачу разделения поверхности Безье

р

построенной на ХПС и = (игу} порядков п х т, на четыре сегмента р11(/,т) ^ р22(/,т) с моделями (4) порядков п1 х т1 ^ п2 х т2. Целью разделения узловой сети и на кластеры и11 ^ и22 является увеличение числа и уменьшение порядков сегментов, что, в конечном итоге, повышает гибкость построенной на них составной поверхности.

Назначим параметры г, ре (0, 1) и точку разделения рф = р(г,р), в которой новые кластеры и сегменты соединяются углами. Деление надвое каждого параметрического интервала /, те [0, 1] дает сегменты (4), представляющие один и тот же полином в разных комбинациях параметров {/,т} и совместно покрывающие исходный сегмент р(/,т):

ри(/,т) = р(г^ РтХ р12(/,т) = рС^ (1 - р)т + рХ

р21(/,т) = р((1 - г)/ + г, рт), р22(/,т) = р((1 - г)/ + г, (1 - р)т + р).

Подставив сюда модели сегментов (4) и (15), получим систему четырех уравнений

' хт (/)нт ииН„ Т (т)=XI (г/)Ещ +1,И+1НПинтЕт+1,т +1Тт (рт),

(/)НТи12Нт2Тт2 (т)= Т^ (г/)Ет1 +1,т+1НТиНтЕт+1,т2 +1Тт2 ((l-р)т+р),

ТИТ2 (/)Н^2 и21Нт Тт1 (т)= Т* ((1-г)/ + Г)Е„2 +1П+1НПиНтЕт+2т1 +1^ И,

Т, (/)Н1 и22Нт Тт (т)= Т* ((1-Г)/ + Г)Е„ ^Н^тЕтЦ т Л ((1-р)Т+р).

Наконец, четырежды применив преобразование (8), получим формулы вычисления матриц узловых кластеров разделенных сегментов:

Uii =(нпЕИ+1,И1 +iD (r,0)НИ;) ü(hotEm+i;mi +iDm! (p,0)hJ1 )i

Dm2 (i"PiP)Hmi2 )i

Ui2 =

При разделении кластера U лишь по одному параметрическому направлению его замещают не четыре, а только два новых кластера:

/: Uii =(HnEn+i,ni +iDni (r,0)H-i )тU, Ü2i = ^+^2 +iDn2 (i-r,r)H-2 )т U ,

i: Un = U(HmEm+i,mi +iD

Dmi (P,0)Hmi ), Ui2 = U(HmEm+i,m2+iDm2 (i-PiP^ ).

Выбор порядков новых сегментов щ и т определяется структурой матриц полиномиальных коэффициентов 8=И^ПНт и Б- = И^.Ц-Н :

• значения п/ > п и ту > т возможны всегда, но реальные степени новых сегментов все равно будут равны п и т. При этом их матрицы Б/у будут содержать снизу щ - п нулевых строк и/или справа ту - т нулевых столбцов:

S

O,

i -n,mj +i

SO

S j Oni+i,mj-m

S

' On +i,m j-m .L_.-----j---

O 'O

nj-nmj +i 1 nj-nrnj-m

• выбор п/ < п или ту < т обусловлен наличием у полинома р(^,т) дефектов степеней > п - п/ или 5у > т - ту. Для этого матрица Б полиномиальных коэффициентов разделяемого сегмента должна содержать снизу ё нулевых строк и/или справа 5 нулевых столбцов:

S;,

O

d ,m j +i

[Sj- °+i,g]

!o

nj +i,mj-m

5

Od ,m,+n Od ,5

Как и в (10), двойная гладкость сопряжения новых сегментов друг с другом получится только при г = р = 0.5 — делении сегмента средне-параметрической точкой.

Испытаем разработанный алгоритм на разделении поверхности Безье из [1, рис. 3], построенной на характеристической сети узловой размерности 10 х 10 (рис. 6, а). Необходимость сильного удаления околоцентральных вершин ХПС подтверждает свойство их слабого влияния на поверхность Безье при высоких порядках ее модели (15). Подобрав параметры г = 0.4 и р = 0.5, при которых точка деления ргр находится на острие «носа», получим по формулам (17) четыре кластера Бц ^ и22, очень плотно охватывающих составную поверхность (рис. 6, б) в отличие от «рыхлой» исходной сети.

U

Uii

. U12

U,

22

Рис. 6. Разделение поверхности Безье

<

Теперь, с превращением односегментной поверхности в составную, появились более мощные возможности ее редактирования. Одна из них - перемещение точки деления и окружающих ее восьми узловых точек - показана на рис. 6, в, и такой остроты «носа» нельзя достичь без разделения кластера.

U =

Пример 3. Разделить на четыре сегмента минимальных степеней поверхность Безье (рис. 7, а), у которой вершины ХПС порядков n = m = 3 составляют матрицу

[8 0 0] [8 0 -12] [-8 0 -12] [-8 0 0] " [6 - 4 0] [6 - 4 - 9] [- 6 - 4 - 9] [- 6 - 4 0] [4 - 4 0] [4 - 4 - 6] [- 4 - 4 - 6] [- 4 - 4 0] [2 0 0] [2 0 - 3] [- 2 0 - 3] [-2 0 0]

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

"[8 0 0] [0 0 -36] [-48 0 36] [32 0 0] " [- 6 -12 0] [0 0 27] [36 0 -27] [-24 0 0] [0 12 0] [0 0 0] [0 0 0] [0 0 0] [0 00] [00 0] [0 00] [00 0]

В ней есть одна нижняя нулевая строка, значит, в /-направлении поверхность является параболической с дефектом степени d = 1, в т-направлении - кубической, а минимальные степени новых сегментов равны ni = n2 = n - d = 2 и mi = m2 = 3.

S=Щ UH 3

u v^

u02

u

03

u

13

01

U12

U11

u21 * U11

11

U20 .

21

10

а) б)

Рис. 7. Пример разделения поверхности Безье

Задав параметры разделения г = р = 0.5 и вычислив по (17) матрицы кластеров Цл ^ и22, убеждаемся, что построенные на них по (4) поверхности Безье точно совпадают с исходной поверхностью (рис. 7, б).

Объединение поверхностей Безье

Цель данной задачи - объединение кластеров в один для упрощения структуры составной поверхности без изменения ее формы путем уменьшения числа сегментов и, возможно, вершин ХПС. Она, по сути, обратна к задаче разделения кластера. Следует, однако, понимать, что объединение сегментов Безье с сохранением формы поверхности возможно при жестких ограничениях на расположение узловых вершин объединяемых кластеров.

По аналогии с (11) ^ (14) составим алгоритм замены четырех матрично организованных кластеров Ц/ с порядками пг х Ш/ при г,/е{1, 2} одним кластером и порядка п х т, поверхность которого р(/,т) совпадает с объединением поверхностей рг/(/,т). Используем для вычисления параметров разделения г и р точку ргр = р11(1,1) = р12(1,0) = р21(0,1) = р22(0,0) и четыре окружающие ее граничные вершины кластеров

.11

.12

v0 " u«! —1,m1 " unx-1,0 ,

21

22

v1 - u1,m - u1,o:

r -

1+-

«2 Prp — v1

«1 Prp — v0

V—1

, p-

1+-

11 21

- u щ,т\—1 - u0,m1—1, w1

> 1

m2 Prp — w1

m1 Prp — w 0 J

.12 . '«1,1"

22 . *0,1 .

Возможность алгоритмического объединения четырех сегментов сильно ограничена таким расположением вершин в кластерах Цп ^ Ц22, что построенные на них поверхности Безье рг/(/,т) представляют единый полином от разных комбинаций параметров I, те[0, 1]. Приведя уравнения (16) к порядкам п и т, получим соотношения

=К (г,0)ип ин тът (р,о),

= (г,0)НПинтБт (1-р,р),

= К (1-Г,Г )НП ин тБт (р,0),

= БП (1-Г,Г )н П ин т Бт (1-р,р).

Отсюда вытекают, во-первых, тест возможности объединения сегментов р11(/,т) ^ р22(/,т) в один сегмент р (/,т) в виде системы трех матричных уравнений

Г trT TT П lf

Еи+1,и! +1H« U 11Hmj +1,m+1 ' Еи+1,и! +1H«U12 Hm2 ЕИ2 +1,m+1  Еи+1,и2 +1H «2 U 21Hmx Emx +1,m+1" Еи+1,и2 +1H «2 U 22 Hm2 Em2 +1,m+1 "

U, , Hm, „^Dm1

11Hmj Emj +1,m+1Dm

0—1 (r

Dm1 (p,0)-U22 Hm Em

12 Hm2 Em2 +1,m+1Dm

U^E« +1,«+1D-1 (r,0)-U T1H„2 E „2 ^D—1 (1—r,r),

' 22Hm2 Em2 +1,m+1Dm '

U H E D

U 21 Hmj Emj +1,m+1 Dm

1Б~т(1 -р,р),

а во-вторых, формула вычисления матрицы вершин объединяющего кластера Ц по матрице лишь одного узлового кластера, например, Ц11:

и=

Для объединения сегментов лишь по одному параметрическому направлению (/ либо т) в (18) ^ (20) берутся соответствующие параметр разделения (г либо р) и пара тестируемых кластеров ({Ц11, Ц21} либо {Ц11, Ц12}).

При выводе формулы

равносильны всегда, если порядки искомого сегмента п > тах{п1, п2} и т > тах{ть т2}. Наименьшие значения п и т, при которых задача объединения при условиях (19) имеет точное решение (20), ограничено наибольшими реальными степенями полиномов рг/(/,т).

Испытаем разработанный алгоритм на объединение четырех сегментов Безье с кластерами Ц11 ^ Ц22 порядков п1 = п2 = 2 и т1 = т2 = 3 (см. рис. 7, б) в поверхность минимальных степеней п = 2 и т = 3, определяемых максимальными степенями объединяемых сегментов в соответствующих параметрических направлениях (рис. 8).

0

<

22 11 21 По точке ргр = и00 и четырем граничным вершинам кластеров V0 = и 13, V 1 = и 13

11 12

"0 = и32 и = и31 находим по (18) параметры разделения г = р = 0.5. Убедившись в выполнении теста (19), находим по (20) матрицу вершин ХПС

" [8 0 0] [8 0 -12] [- 8 0 -12] [-8 0 0] Ц = [5 -6 0] [5 -6 -7.5] [-5 -6 -7.5] [-5 -6 0] [2 0 0] [2 0 - 3] [- 2 0 - 3] [-2 0 0]

Сравнение с узловой матрицей той же поверхности из примера 3 (см. рис. 7, а) свидетельствует об избыточности модели со степенью п = 3, которая имеет реальное значение п = 2.

Выводы

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

Библиографический список

1. Никулин, Е.А. Новый метод изменения порядков кривых и поверхностей Безье // Труды Ни-жегород. гос. техн. ун-та им. Р.Е. Алексеева; НГТУ. - Н. Новгород. 2011. № 1 (86). С. 70-77.

2. Компьютерная геометрия: учеб. пособие для студ. вузов / Н.Н. Голованов [и др.]. - М.: Издательский центр «Академия», 2006. - 512 с.

3. Роджерс, Д. Математические основы машинной графики / Д. Роджерс, Дж. Адамс. - М.: Мир, 2001. - 604 с.

Дата поступления в редакцию 06. 04.2012

E.A. Nikulin

MATRIX BASED METHODS OF COMPOSITE BEZIER OBJECTS RECLASTERIZATION

Nizhny Novgorod State Technical University n.a. R.Y. Alekseev

Subject: modification algorithms for node networks which are used to create compound lines and Bezier surfaces, allowing to randomly change cluster count and dimensions keeping segment shape unchanged, are developed. Purpose: on the one hand it is to increase a modification flexibility of compound Bezier objects while increasing clu s-ter count and dimensions, on the other hand it is to simplify as much as possible their models due to reducing cluster count and dimensions.

Methodology: proposed reclusterization algorithms use a matrix based approach which provides a single short formula to recalculate clusters increasing their size as well as reducing it.

Originality/value: methods developed in the present study allow to increase cluster dimensions to any value and decrease them to limiting values keeping the Bezier object shape intact.

Findings: the article finds unique matrix-based algorithms for node network restructurization of compound lines and Bezier objects, which increases their utilization flexibility.

Key words: curve, surface, Bezier, polynom, segment, conjugation.