Способы представления геометрических объектов

Способы представления геометрических объектов

Декартова система координат — основа численного моделирования объектов. За единичными исключениями, все графические устройства работают на базе этой системы. Инженеры при необходимости используют и другие системы (полярные, сферические и т. п.), а непосредственно перед выводом информации на графические устройства значения могут быть пересчитаны.

Как задается точка знают все, а как задаются другие фигуры? Окружность задается тремя числами: x- и y-координатами центра и радиусом; для эллипса в дополнение к координатам центра нужно добавить величины двух его полуосей и еще направление одной из осей. Одну и ту же фигуру можно задать разными способами, но обычно выделяют те, для которых количество параметров является минимальным. Это минимальное количество называют «параметрическим числом образа». Составляя программы и алгоритмы машинной графики, надо знать параметрические числа основных геометрических образов.

Таблица параметрических чисел для некоторых геометрических образов
Объект	Размерность пространства	Параметрическое число
Отрезок на плоскости	2	4
Отрезок в пространстве	3	6
Окружность в пространстве	3	6
Сфера	3	4
Дуга окружности на плоскости	2	5
Прямоугольник общего положения	2	5
Эллипс общего положения	2	5
Эллипсоид	3	9
Поверхность второго порядка	3	9
Линия полинома степени n	2	n+1

В задании объекта могут также участвовать «логические параметры». При этом можно ограничиться числами 0 и 1 или же устанавливать параметр по знаку числа. Эти параметры не влияют на параметрические числа объектов. Например, точка на окружности может быть задана значением одной из ее координат (X или Y), но надо будет указать, на какой полуокружности она может находиться.

В машинной графике существенно, с какого конца вычерчивается геометрический компонент, в этом случае должно задаваться направление вычерчивания. Это нужно для определения видимости сторон. Направление обхода тела можно задавать знаком «+» или «-», можно воспользоваться касательными, но чаще всего используются касательные векторы, или «векторы направления». Вектор на плоскости можно задать двумя его проекциями, касательные векторы имеют произвольную длину — поэтому можно ограничиться одним числом, однако из соображения удобства пользуются проекциями. На рис. 1.1a показана дуга, построенная по двум конечным точкам и проведенным их них касательным векторам. Этот набор (конечные точки и касательные векторы) — одна из типичных конфигураций данных. Если направление одного из векторов изменить на противоположное, то мы увидим картину, показанную на рис. 1.1b .

Таким образом, у линии можно будет выделить две области («стороны»): «положительную», с которой будут располагаться нормальные векторы, и «отрицательную». Линии, проведенные на поверхности, делят поверхность, а поверхности делят пространство. Данная методика применяется для решения задач нанесения штриховки на различные элементы чертежа, определения принадлежности точки телу сложной формы, выделения видимых или ограниченных частей и поверхностей.

Способы представления объектов

Коснемся двух различных способов представления геометрических объектов в ЭВМ.

Первый способ — это аналитические модели. Аналитическая модель есть набор чисел и, если необходимо, логических параметров, которые играют роль коэффициентов и других величин в уравнениях, аналитических соотношениях, задающих объект данного типа. Например, для окружности основная форма аналитической модели — координаты центра и радиус, связанные известным соотношением: (x — x c ) 2 + (y — y c ) 2 — R 2 = 0.

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

Второй способ численного моделирования геометрических объектов в ЭВМ — это координатные модели. В простых случаях — это наборы точек, которые принадлежат объектам и задаются координатами. Для кривых и ломанных линий точки располагаются в том же порядке, что и на линии. Упорядочить точки поверхности — более сложная задача: в большинстве случаев точки последовательно размещаются на линиях, проведенных на поверхности.

Координатные модели имеют несколько разновидностей:

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

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

Источник

Способы представления геометрических объектов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Цели и задачи исследования. Целью магистерской работы является исследование способов представления моделей геометрических объектов и алгоритмов их синтеза.

Научная новизна состоит в разработке метода построения моделей геометрических объектов по произвольному параметрическому описанию образующих их частей (кривых или поверхностей).

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

Реализация результатов работы. Результат работы составляет библиотека функций, построенной по COM технологии. Библиотека включает:
— подсистему создания наращиваемой библиотеки символьных функций и компилятор функций;
— функции для работы с B-сплайнами;
— подсистему синтеза тверотельных моделей геометрических объектов в базисе B-сплайнов, описанных средствами библиотеки символьных функций.

СОДЕРЖАНИЕ РАБОТЫ

1 Способы представления моделей геометрических объектов

В общем случае в любой геометрической модели можно выделить две составляющие ее части (уровни):

• набор структурных элементов. Например, в полигональной модели это вершины, ребра и грани.
• топология, т.е. собственно структура, определяющая способ взаимосвязи элементов.

Структурный элемент как геометрический объект, вообще говоря, можно представить одним из способов:
1) параметрически (функциональная зависимость координат от переменных параметров):

2) неявно

m – размерность пространства (1 – одномерное, 2 – двумерное, 3 – трехмерное);
n – размерность элемента (0 – нульмерный, определяет точку; 1 – одномерный, определяет линию; 2 – определяет поверхность);
— m-мерная вектор-функция, определяющая форму параметрического элемента;
— m-мерная вектор-функция, задающая пределы изменения параметров ui;
— m-мерная вектор-функция, определяющая неявное уравнение геометрического элемента;
— m-мерный нулевой вектор.

Как видно неявное задание геометрического объекта более компактное. Тем не менее, параметрическому заданию отдается предпочтение в силу его удобства для решения задач нахождения:
— точки, принадлежащей объекту (вычисляется по параметру);
— нормали к кривой или поверхности;
— осуществления мэппинга поверхности;
— и др.
В зависимости от значений m и n сведем геометрические объекты для параметрического их представления в следующую таблицу.

Таблица 1 Классификация элементов геометрических объектов

Из таблицы видно, что m = 3)

список ребер. Здесь грань выражена через ребра:
V = – вершины |V| = n;
Е = < ek = (vi, vj [, fk(u)]) >– ребро. fk – уравнение линии;
F = < (ej1, ej2,…, ejk [, fj(u,v)]) >– грань (или патч fj), состоящая из k ребер (k >= 3).

«крылатое» представление. Эта модель является развитием модели, основанной на информации о ребрах. Отличие состоит в том, что в структуру, описывающую ребра, добавляется информация о взаимном расположении граней. Она включает:
V = – вершины |V| = n;
E = < ek = (vstart, vend, ncw, nccw, [, fk(u)]) >– ребро, где vstart – начало ребра, vend – конец ребра, ncw – следующее (предыдущее) ребро в той грани, где ek встречается в положительном направлении обхода вершин, nccw – следующее (предыдущее) ребро в другой грани (где ek встречается в отрицательном направлении).
F = < (first_edge, sign [, fj(u,v)]) >– грань (или патч fj), где first_edge – первое ребро в цепочке представления грани, sign – знак (+/-), определяющий, в каком направлении встречается ребро first_edge в данной грани.

«Крылатое» представление является наиболее удобным для реализации важнейших алгоритмов над геометрическими объектами:
— проверка правильности задания;
— алгоритмы для полигональных моделей, связанные с обходом ребер (выделение плоских контуров, упрощение модели путем удаления граней и другие).

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

В объемном представлении базовыми являются (3\2)-элементы или неявно представленные примитивы. Наиболее известны:
— воксели;
— метаболы [2];
— сплошные конструктивы.
Основой воксельного представления служит так называемый воксель (или ячейка), представляющий собой кубическую область пространства. Трехмерный объект определяется как массив вокселей. Можно выделить следующие топологии воксельного объекта:

1. простейшая – набор одинаковых вокселей, аппроксимирующий область пространства, занимаемую объектом;
   V = < (x x , <1,0>) > – элементу трехмерного массива вокселей размером L x M x N ставится в соответствие его заполненность (принадлежность объекту);
2. октальное дерево – рекурсивное разбиение пространства на 8 частей. При этом устанавливается некоторый минимальный размер вокселя. Лист дерева помечается заполненным, если он полностью принадлежит объекту. Т.о. топология представлена в виде дерева;
3. PM-октальные деревья – это гибрид октального дерева и полигональной модели для уменьшения погрешности аппроксимации при достижении минимального размера вокселя в рекурсивном разбиении пространства.

Воксельное представление является очень удобным для реализации пространственных алгоритмов и теоретико-множественных операций над объектами (объединение, вычитание, пересечение), но обладает рядом недостатков, которые ограничивают область его применения:
— низкая точность для представления для большинства объектов;
— большой объем занимаемой памяти;

Метаболы [2] – это шары различного радиуса (r), которые могут взаимодействовать в зависимости от близости и радиуса взаимодействия (R): Сфера = (координаты, радиус, вещество). Взаимодействие выражается через появление дополнительной «материи» между ними (см. рис 1.1). Топология как таковая здесь отсутствует.

Рисунок 1.1 Взаимодействие двух метаболов

При представлении объекта в виде сплошных конструктивов используют два набора:
— базовый набор примитивов (параллелепипед, сфера, конус, цилиндр, тор, призма, пирамида и т.п.), являющихся структурными элементами объекта;
— базовый набор теоретико-множественных операций: унарного аффинное преобразование (T) и бинарных операций вычитания (-), пересечения (*), объединения (+). Данный набор определяет топологию модели, которая реализуется в виде формулы теории множеств.

Например, если мы имеем три примитива A, B, C и формулу (A + T(B)) * C, то это означает, что мы объединяем объект А с трансформацией объекта В и пересекаем его с объектом С. Преимущество данного способа представления заключается в том, что таким образом можно относительно легко моделировать достаточно сложные объекты.

2 Синтез моделей геометрических объектов

Под синтезом модели геометрического объекта будем понимать преобразование модели одного и того же геометрического объекта в другую модель.

Рисунок 2.1 Синтез как процесс преобразования одной модели в другую

В настоящее время методы синтеза достигли такого многообразия благодаря современным мощным системам геометрического моделирования (3DStudioMAX, Autodesk AutoCAD, Autodesk Inventor, Rhino, Lightwave, Maya, “СПРУТ”, комплекс программ фирмы IDEA и др.), что выполнить обобщенную классификацию достаточно сложно. Поэтому составим ее по отдельным признакам.

Исходя из принятого выше разделения модели на два уровня можно выполнить поуровневую классификацию методов синтеза:

1. элементные. Преобразованию подвергаются только структурные элементы модели, но не затрагивается топология. Такое преобразование, вообще говоря, является приближенным. Например, в поверхностной модели – конвертирование Безье-патчей в NURBS-патчи;
2. топологические. Они преобразуют только топологию. Это однозначное преобразование. Примером может служить приведение топологии «список вершин» полигональной модели к топологии «крылатое представление»;
3. смешанные (элементно-топологические). Преобразованию подвергается как структурные компоненты, так и топология. Например:
   — аппроксимация патч-модели полигональной моделью;
   — преобразование области, ограниченной неявно заданной поверхностью, в воксельную модель.

В отдельный и наиболее широкий класс выделяют процедурные методы синтеза. Они составляются из комбинации предварительно определенных кривых, поверхностей, функциональных компонент и процедур, которые соотносят их для получения новой кривой или поверхности. Сюда относятся:
— кинематические методы получения поверхностей лофтинга, скиннинга, вращения, выдавливания, протягивания по кривым, используемым как направляющие или как образующие поверхность;
— методы получения новой поверхности из имеющихся: константные и функциональные поверхности смещения, теневые поверхности;
— получение поверхности с использованием кривой на другой поверхности: перпендикулярная поверхность, касательная поверхность, обрезка (усечение) поверхности кривыми;
— получение поверхности по кривым: поверхность по обозначающим ее краям.

Эти методы являются математически точными и универсальными. А кинематические методы используются для формирования базовых элементов твердотельного моделирования (AutoCAD).

Одним из мощных средств синтеза являются пространственные искажения (3D Studio MAX [2]), которые могут быть выражены как:

где
p – исходная точка;
p’ – преобразованная точка;
M(p) – матрица преобразования;
Примеры пространственных искажений: масштабирование, скос, скрутка, изгиб, заострение.

3 Параметрическое заданние геометрических объектов

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

p = F(u) = (Fx(u), Fy(u), Fz(u)),

а для поверхности – функция двух переменных:

p = F(u, v) = (Fx(u, v), Fy(u, v), Fz(u, v)).

Вообще говоря, вид функции F может произвольным. Но на практике ограничивают набор функций, которые представляют наиболее часто встречающиеся геометрические объекты, из которых затем составляют более сложные. К ним относятся [3]:

1) плоские линии: прямые, окружности, эллипсы, и их отрезки, спирали Архимеда, эквидистанты;
2) пространственные линии: спирали;
3) поверхности: плоские, сферические, цилиндрические, конические, торические, пружинные.

Как видно их перечень невелик. А потому для моделирования кривых и поверхностей, которые не вписываются в этот набор, используется сплайны и патчи. Наиболее употребляемые виды сплайнов: сплайны Безье, B-сплайны (NURBS). Среди патчей можно выделить: патчи NURBS, Безье-патчи, N-патчи, билинейные патчи, патчи Кунса. Тем не менее, большинство пакетов использует эти инструменты для аппроксимации вышеперечисленных кривых и поверхностей и не имеют автоматических средств для аппроксимации пользовательский кривых (параболы, гиперболы, синусоиды) и поверхностей (параболоиды, конусы с образующей заданного вида и др.) с помощью перечисленных сплайнов и патчей.

Данная работа как раз и посвящается изучению и разрешению данной проблемы. Сформулируем основные задачи, которые должны быть при этом решены:

1) гибкость и универсальность определения пользовательских функций (расширяет область применения);
2) высокая скорость вычисления (обеспечивает возможность построения интерактивных приложений);
3) контролируемая точность аппроксимации функций (обеспечивает адекватность оценки полученных результатов);
4) минимизация результата аппроксимации (экономит память);
5) взаимодействие с другими системами;
6) универсализация механизма синтеза геометрических моделей.

В последующих разделах будут описаны пути решения поставленных задач.

4 Библиотека произвольных символьных функций

Для построения любой сложной системы необходимы:
— набор базовых элементов;
— правила построения новых элементов из уже имеющихся.

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

• операнды (числа и аргументы функции);
• арифметические операции (+, -, *, /, ^);
• скобки управления приоритетом операций;
• функциональную зависимость выражений. И с целью сохранения общности снимем ограничения на число аргументов функции.

Теперь определим тело произвольной функции, используюя формализм Бекуса-Нура:

Определим также общепринятый приоритет операций по убыванию:

Для обеспечения преемственности объявлений функций введем понятие библиотеки функций:

Определим для нее следующие операции, которые можно выразить тривиальными операциями над множествами:
— добавить определения элементарных функции;
— добавить новое тело функции с заданным именем;
— удалить функцию по имени;
— очистить библиотеку.

Таким образом мы обеспечили решение первой поставленной задачи.

4.1 Синтаксический разбор и оптимизация

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

• линейная (польская инверсная запись). После расчленения выражения на операции и операнды оно преобразуется в список в префиксной форме.
  Например, a + (b * c – d / e) преобразуется в a b c * d e / — +;
• древовидная. В данном случае в узлах дерева окажутся операции, а в листьях – операнды. Например, для выше приведенного выражения получим дерево, изображенное на рисунке 1.

Рисунок 4.1 Дерево, представляющее арифметическое выражение

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

::= | | ( < ><, >) |	(4.1)
::=	(4.2)

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

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

возможно следующее упрощение (sqrt – функция вычисления квадратного корня):

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

4.2 Вычисление функции и компиляция

Имея структуру, представляющую тело функции можно вычислять ее значение по заданным значениям аргументов. Рекурсивный алгоритм 4.1 вычисления следует из определений (4.1), ( 4.2). Причем:

Данный алгоритм реализует интерпретатор. Однако интерпретатор выполняет множество лишних манипуляций данными (копирование во вспомогательные переменные, дополнительные проверки условий), которых можно избежать при вычислении конкретной функции. Этого можно добиться путем генерации (компиляции) ее исполнимого кода. Компиляция решает вторую из поставленных задачу – высокая скорость вычислений.

Компиляции состоит в формировании кода их базовых наборов команд:

• действия при входе в тело функции;
• действия при выходе из тела функции;
• возврат их функции;
• помещения в стек аргумента функции;
• помещение в стек константы;
• удаления из стека заданного числа значений;
• операции со стеком математического сопроцессора (копирование, извлечение, дублирование, обмен значений и др.);
• реализация операции математического сопроцессора (сложения, вычитания, умножения, деления).

5 Аппроксимация произвольных функций с помощью B-сплайнов

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

Выбор B-сплайнов (NURBS) в качестве аппроксимирующих функций обусловлен следующими причинами:

• они является наиболее общим видом сплайнов, благодаря наиболее широкому набору полезных математических свойств (о которых будет сказано в следующем пункте), чем у других видов, а, следовательно, с их помощью можно наиболее точно приблизить функцию;
• они являются стандартом для граничного представления SGM в современных CAD-системах (Autodesk Inventor, Rhinoceros и др.), в т.ч. используемых ими для обмена форматов файлов (IGES, PHIGS и др.).

5.1 Кривые и поверхности NURBS

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

Рисунок 5.1 В-сплайн с управляющей точкой Р4 в нескольких положениях.

Рассмотрим различные виды В-сплайнов [4].

В-сплайн интерполирует набор из р+1 управляющей точки: и состоит из р-(n-1) сегментов кривой: . Кроме того, мы можем определить общий параметр t, нежели отдельный для каждого сегмента в интервале от 0 до 1. Таким образом, для каждого сегмента кривой t будет принадлежать интервалу . Более того, на каждый сегмент будет влиять ровно n управляющих точек: от до .

Для каждого i >= n существует узел между и для значения ti параметра t. Для В-сплайна существует p-n-2 узлов. Отсюда исходит понятие однородности: если узлы равномерно распределены на интервале от 0 до 1, т.е. , то говорят, что В-сплайн равномерный. В противном случае – неравномерный. Стоит также обратить внимание на факт, что эти определения касаются узлов, возрастающих по значению, т.е. .

Теперь предположим, что координаты (x, y, z) точки кривой представлены в виде рациональной дроби. В этом случае говорят, что В-сплайн рациональный, иначе – нерациональный

Подводя итог, можно указать на существование 4 типов В-сплайнов:
— равномерные нерациональные;
— неравномерные нерациональные;
— равномерные рациональные;
— неравномерные рациональные.

Последний тип и представляет собой NURBS как наиболее общий случай В-сплайнов.

Теперь рассмотрим математическое описание NURBS. NURBS кривая и поверхность соответственно выражаются следующими двумя параметрическими уравнениями:

(5.1)

(5.2)

где, Pi — управляющая точка, wi — ассоциированный с ней вес и — базовая функция, определенная рекурсивно следующим образом:

(5.3)

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

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

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

Единственный недостаток – это несколько более сложное математическое описание NURBS по сравнению с Безье сплайнами, однако порядок этого усложнения не высок.

Итак, NURBS предоставляет точность, гибкость и совместимость с другими системами.

5.2 Аппроксимация функции одной переменной

В общем виде аппроксимацию функции F(t) можно представить следующим образом:

(5.4)

где
gi – известные базовые функции
ai – неизвестные коэффициенты

Для простоты будем полагать, что параметр t лежит в пределах от 0 до 1.
Определение неизвестных сводится к заданию (p+1)-го ограничения на значения функций или их производных для конкретных значений параметра u и решению системы линейных алгебраических уравнений относительно ai.

Для NURB сплайнов ситуация усложняется тем, что они имеют множество неизвестных величин, которые можно менять в широких пределах. К ним относятся:

1) количество управляющих точек p + 1 (p – порядок);
2) количество сегментов q;
3) n – степень базисных функций;
4) управляющие точки Pi;
5) значения весов wi;
6) значения узлов knoti.

Однако первые три величины связаны соотношением:

p + 1 = n + q.

(5.5)

Из (5.1) видно, что управляющие точки Pi являются определяющими, поскольку только с помощью этих значений независимо от весовых коэффициентов можно получить любое значение функции Q(t). Кроме того, использование весов создает иррациональность при составлении системы алгебраических уравнений, а также создает зависимость систем уравнений для отдельных координат управляющих точек плоских и пространственных кривых NURBS (для всех координат веса одинаковые). Эти проблемы легко устраняются, если задать значения весов равными 1. Тогда NURBS-приближение для функции одной переменной примет вид:

(5.6)

В целях определенности в качестве ограничений будем использовать ограничения на значения функции при заданных, а не ее производные, параметрах со следующими оговорками для замкнутых кривых (F(0) = F(1)):

1) Q'(0) = Q'(1), если F'(0) = F'(1)
2) Q'(0) = F'(0), если F'(0) <> F'(1)

Первое условие необходимо для сохранения непрерывности соединения кривой, а второе только для обеспечения недостающего (n+1)-го ограничения. Ограничения на значения функции примут вид:

(5.7)

Выбор и распределение ti должно определяться поведение функции. Очевидно, что для уменьшения числа ti необходимо их расставить прежде всего в точках резкого изменения функции F (экстремумах и точках перегибов), т.е. для исходного набора ti имеем:

Задачи нахождения экстремумов и точек перегиба можно решить следующими способами:

1) использование соответствующих численных методов непосредственно (методы дихотомии, «золотого» сечения, наискорейшего спуска и т.д.);

2) поэтапное вычисление:

• найти производную в символьном виде, получив новую функцию (для второй производной выполнить этот шаг два раза);
• откомпилировать полученную функцию;
• найти корни полученной функции на заданном интервале.

Второй способ является более приемлемым, поскольку:

• численные методы решения задачи F'(t) = 0 не всегда дает все решения;
• задачу нахождения корней функции можно решать с использованием символьного ее анализа – а, значит, более точно – если известны характеристики базовых функций библиотеки (экстремумы, монотонность и т.п.). Приведем методику получения корней функции, основанной на методе «разделяй и властвуй».

f(x), g(x) – функции с известными экстремумами;
f(ai) = 0, g(bj) = 0, где = A, = B.

• для уравнений f(x) + g(x) = 0 и f(x) — g(x) = 0 корни можно численно (например, методом Ньютона) на отрезках между экстремумами обеих функций (можно показать, что на таких отрезках не более одного корня);
• для уравнения f(x) * g(x) = 0 = A + B;
• для уравнения f(x) / g(x) = 0 = A;
• для уравнения f(g(x)) = 0 = A, т.е. необходимо численно решить |A| уравнений типа g(x) — a = 0.

Еще один момент, на который следует обратить внимание – это область определения функции f (D(f)). D(f) необходимо учитывать в целях надежности и контроля ошибок, которые может допустить пользователь при составлении новых функций и использовании их для построения геометрических объектов. В этом случае для аргумента функции f должно выполняться: [0,1] Є D(f).

Нахождение D(f) может производится при составлении функции, исходя из следующих очевидных утверждений:

• для выражений f(x) + g(x), f(x) — g(x), f(x) * g(x) D = D(f) * D(g);
• для f(x) / g(x) D = D(f) * D(g) * 0>;
• для f(g(x)) D = D(g) * .

Узлы knoti NURB сплайнов играют роль точек соединения его сегментов и как видно из (5.3) влияют на точность вычисления значений функций между узлами: чем больше knot[[i+1]]-knot[[i]], тем точнее результат вычисления на интервале [ knot[[i]], knot[[i+1]] ]. Поэтому узлы можно распределить пропорционально расстоянию между точками (ti, f(ti)) и (t[[i+1]], f(t[[i+1]])) графика функции f.

Поскольку возможен случай линейности функции f, то целесообразно начинать процесс аппроксимации с NURB сплайна первой степени (n = 1). Отсюда количество управляющих точек p+1 можно найти из (5.5):

p + 1 = n + q = n + |K|

Т.о. мы определили все неизвестные величины NURB. Далее, имея некоторую допустимую погрешность error, для которой должно выполняться условие аппроксимации

Источник