Введение в математические основы систем автоматизации проектных работ (САПР)

– для описания данных используется специальный язык, называемый Express.

Формат одновременно разрабатывается несколькими комитетами и рабочими группами, отвечающими за каждую конкретную часть стандарта. Текущая структура стандарта такова:

? методы описания:

– обзор и фундаментальные принципы;

– справочное руководство по языку Express;

? интегрированные информационные ресурсы:

– интегрированные прикладные ресурсы (черчение, конечноэлементный анализ, кинематика и пр.);

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

– конструкции, интерпретируемые приложением (реберный каркас, геометрические ограничения, надписи на чертеже и пр.);

? прикладные протоколы и абстрактные испытательные пакеты (черчение, проектирование с использованием конкретного геометрического представления, планирование процесса обработки на станках с ЧПУ и пр.);

? методы реализации (текстовый обменный файл, интерфейсы для доступа к данным на языках C++, Fortran, IDL);

? методологические основы аттестационных испытаний.

Мозаичные модели

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

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

? представления трехмерных данных в нейтральном формате для использования в любом приложении (включая машины для быстрого прототипирования и изготовления);

? расчета других сеточных представлений модели (сетки для метода конечных элементов, четырехугольной базовой сетки для поверхностей подразделения);

? быстрого определения столкновений (collisions) твердых тел.

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

Отметим типичные недостатки мозаичных моделей, созданных различными алгоритмами:

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

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

? неправильные нормали - заданная нормаль треугольника может не совпадать с нормалью, рассчитанной по координатам его вершин;

? неправильные пересечения - две треугольные грани могут пересекаться не только по ребрам и вершинам, но и внутри треугольной поверхности;

? внутренние грани - в модели могут присутствовать лишние грани внутри замкнутой поверхности;

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

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

Формат STL

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

Формат VRML

VRML (Virtual Reality Modeling Language) - язык моделирования виртуальной реальности, уже довольно давно применяемый в сети Интернет для описания интерактивной трехмерной графики и мультимедийных приложений. VRML-документ представляет собой обычный текстовый файл, который содержит описания трехмерных фигур и свойств их поверхностей (цвет, текстура материала, освещение и т. п.).

Язык VRML впервые предложен Марком Песке (Mark Pesce) в 1993 г., а его первая спецификация (VRML 1.0) подготовлена на основе формата Open Inventor фирмы SGI и представлена на второй конференции WWW в октябре 1994 г. Дальнейшее развитие проходило уже не только на основе разработок фирмы SGI; к созданию формата подключились такие фирмы, как Sony Research, Mitra и многие другие. Во втором выпуске формата (VRML 2.0) его интерактивные возможности были значительно расширены. Стандарт VRML 2.0 поддерживает анимацию и звуковые эффекты; для него существует поддержка на уровне языков Java и JavaScript. VRML 2.0 был рассмотрен открытой дискуссионной группой и одобрен многими компаниями, а в августе 1996 г. был принят его стандарт. В декабре 1997 г. VRML 2.0 официально заменен на VRML 97. Новый стандарт практически идентичен спецификациям VRML 2.0 с учетом редакционных поправок и некоторых незначительных функциональных различий. Таким образом, текущим VRML-стандартом сегодня является VRML 97, а в работе находится новый формат - VRML 200x. Однако средства и методы представления 3D-графики в Интернет продолжают постоянно развиваться и уже не ограничиваются только языком VRML.

Поверхности подразделения

Очевидным недостатком мозаичных моделей является значительный объем данных, необходимый для представления поверхностей с требуемой точностью. Несмотря на ряд разработанных способов компактного хранения данных в мозаичной модели, объем ее данных все еще является непреодолимым препятствием для их передачи по сети Интернет. Прорыв в этой области произошел лишь с разработкой теории поверхностей подразделения (subdivision surfaces).

Поверхности подразделения представляют собой мозаичные модели, которые итеративно строятся по базовой сетке (base mesh), с каждой итерацией приближаясь к форме моделируемой поверхности. Таким образом, две составные части поверхности подразделения - это базовая сетка и алгоритм ее сглаживания. Исторически теория поверхностей подразделения началась с работы американского художника-дизайнера Чайкина (Chaikin), который предложил способ итеративного построения кривой по контрольным точкам. Аналогично Безье, построение кривой Чайкин начинает с характеристического многоугольника, задаваемого набором точек {P0, P1, …, Pn} (рис. 15).

Рис. 15

На следующем этапе образуется новая последовательность контрольных точек {Q0, R0, Q1, R1, …, Qn, Rn} такая, что

Таким образом, точки Qi и Ri делят отрезок PiPi+1 в соотношении 1:2:1 (рис. 16).

Процесс продолжается итеративно (рис. 17) до тех пор, пока не будет получена кривая требуемой степени детализации (рис. 18).

Вскоре после изобретения Чайкина было доказано, что генерируемая его алгоритмом кривая есть не что иное, как квадратичный однородный B-сплайн.

Рис. 16

Рис. 17

Рис. 18

Метод Чайкина получил название обрезание углов (corner cutting) и лег в основу целого семейства алгоритмов, предложенных его последователями. Первым таким алгоритмом стал предложенный Ду (Doo) и Сабиным (Sabin) метод построения квадратичной однородной B-сплайновой поверхности по базовой четырехугольной сетке (каждая грань в такой сетке является выпуклым четырехугольником).

Рис. 19

Вскоре они смогли распространить свой метод на любые базовые сетки, в которых каждая грань может иметь произвольное число вершин - 3, 4, 5… Полученная поверхность при этом локально (за исключением конечного числа точек) является квадратичным однородным B-сплайном. Метод Ду-Сабина состоит в том, что на очередном шаге каждая грань заменяется гранью меньшего размера с тем же количеством вершин. При этом каждая вершина уменьшенной грани есть среднее арифметическое исходной вершины (Vertex), центров двух смежных ребер (Edge Points) и центра самой грани (Face Point) - рис. 19.

В результате получается несвязная сетка (рис. 20), в которой затем каждая новая вершина соединяется со всеми другими вершинами, полученными из одной и той же старой вершины, образуя новые грани (рис. 21).

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

Рис. 20 Рис. 21

Рис. 22

Аспиранты университета Юты Катмул (Catmull) и Кларк (Clark) смогли расширить метод обрезания углов для построения однородных кубических B-сплайнов. Предложенный ими метод, как и метод Ду-Сабина, может работать на базовых сетках произвольной топологии (получаемая поверхность является локально подобной кубическому B-сплайну). Алгоритм сглаживания состоит в итеративном построении новой сетки, вершинами которой являются

? вершины-грани - центры граней исходной сетки;

? вершины-ребра - центры ребер исходной сетки;

? вершины-вершины - n точек, полученные из вершины каждой n-угольной грани по правилу

где Q - среднее арифметическое центров граней, смежных с данной гранью,

R - среднее арифметическое центров ребер, смежных с данной вершиной,

S - исходная вершина.

При этом ребра новой сетки строятся по правилу:

? вершина-грань соединяется со всеми вершинами-ребрами, прообразы которых были смежными исходной грани в исходной сетке;

? вершина-вершина соединяется со всеми вершинами-ребрами, прообразам которых была инцидентна исходная вершина.

Работу метода иллюстрирует рис. 23.

Рис. 23

Рис. 24

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

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

Вопросы для самоконтроля

1. Опишите типичные схемы обмена геометрическими данными между CAD-системами.

2. Опишите формат IGES.

3. Опишите формат DXF. Какова область его применения?

4. Опишите формат STEP. В чем его преимущества перед IGES?

5. Что такое мозаичные модели, и каковы области их применения?

6. Опишите формат STL. Каковы его недостатки?

7. Приведите алгоритм Чайкина. Какие кривые строятся с его помощью?

8. Опишите метод Ду-Сабина. Какие поверхности подразделения строятся этим методом?

9. Опишите метод Катмула-Кларка и приведите его отличия от метода Ду-Сабина.

Дополнительная литература

Описанию стандартов обмена данными между САПР-системами посвящена глава 14 книги [8]. Структура STL-файла описана в той же книге в главе 12. Кривые и поверхности подразделения достаточно подробно описаны на многих Интернет-ресурсах, например на [33]. Первоисточники по той же теме представлены в [19], [20] и [17].

математический автоматизация проектный инженерный



Лекция 6. Вариационное моделирование: алгебраический подход

Параметры, ограничения и вариационные модели

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

Геометрическое ограничение - это связывание точек, ребер и граней геометрической модели логическим или параметрическим отношением. Примерами ограничений служат инцидентность точки и кривой, касание кривой и поверхности, параллельность двух прямых, расстояние между двумя точками, угол между плоскостями и пр. Ограничение является декларативной (а не конструктивной) конструкцией - оно не задает никакой процедуры расположения одного геометрического элемента относительно другого. Более того, ограничения могут образовывать циклы (например, n попарных расстояний расстояния между n точками), для удовлетворения которым приходится одновременно модифицировать все элементы. Декларативная параметрическая модель с геометрическими ограничениями называется вариационной. Параметры ограничений (величины длин и углов) расширяют традиционный набор параметров геометрической модели (размеры и координаты конструктивных элементов). Для удовлетворения ограничениям вариационной модели используются специальные символьные и численные алгоритмы, которые мы разберем ниже.



Создание эскизов и проектирование сборок

Двумя традиционными областями CAD, где в настоящий момент широко используется вариационное моделирование, являются создание плоских эскизов и трехмерных сборок. Эскиз (sketch) служит основой для создания большинства конструктивных элементов в системах твердотельного моделирования. Например, чтобы сделать отверстие или выемку в детали с помощью продукта CATIA V5 Part Design, пользователь задает плоскость, в которой рисует профиль этого отверстия в виде замкнутого плоского контура, а затем указывает размер выемки/выреза в направлении нормали этой плоскости. Аналогично при создании трехмерного тела путем заметания сначала необходимо сделать двумерный контур. При создании таких контуров (с помощью инструментального средства Sketcher, входящего в Part Design) широко используются двумерные геометрические примитивы (точки, отрезки, дуги, кривые), на взаимное расположение и характерные размеры которых накладываются геометрические ограничения.

При проектировании механизмов, состоящих из нескольких сот или тысяч деталей, пользователь CAD задает ограничения на их взаимное расположение, называемые ограничениями сборки (например, с помощью продукта CATIA V5 Assembly Design). Как правило, ограничения выражают свойства сопряжения плоских граней, соосности цилиндрических элементов и т.д.

Задача размещения геометрических объектов и ее характеристики

Задача размещения геометрических объектов (другое ее название - задача удовлетворения геометрическим ограничениям) на плоскости (2D) или в пространстве (3D) задается

? набором объектов (каждый объект характеризуется своим типом и начальными значениями параметров);

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

Набор объектов, как правило, включает в себя точки, прямые, окружности, эллипсы и параметрические кривые, а для трехмерных задач - еще и плоскости, аналитические и параметрические поверхности. Параметры объектов - это их координаты и размеры, например: параметрами двумерного эллипса являются координаты его центра, направление главной полуоси и радиусы полуосей (для трехмерного эллипса необходимо также задать направление нормали плоскости эллипса). Логическое ограничение инцидентности и параметрическое ограничение расстояния могут задаваться между двумя любыми объектами (однотипными или разнотипными). Ограничения параллельности, касания и заданного угла могут задаваться только между направленными объектами. К таковым традиционно относят все объекты, кроме точки, двумерной окружности и сферы. Два специальных вида ограничения - абсолютная и относительная фиксация. Абсолютная фиксация запрещает изменение положения или ориентации объекта в пространстве задачи, относительная фиксация группирует несколько объектов между собой, запрещая им менять относительные расстояния и углы (такие наборы объектов называются жесткими множествами).

Решением геометрической задачи является такое означивание параметров ее объектов, которое удовлетворяет всем заданным ограничениям. Любая геометрическая задача или ее часть может иметь конечное или бесконечное число решений либо не иметь их вообще. Задача без решений называется переопределенной, задача с конечным множеством решений называется хорошо определенной, а с бесконечным - недоопределенной. (Заметим, что на практике ограничения удовлетворяются с некоторыми заданными допусками, поэтому понятия недо-, переи хорошей определенности имеют лишь теоретический смысл.) Часто свойство хорошей определенности полезно рассматривать в контексте группы изометрий двумерной плоскости или трехмерного пространства. В частности, задача, которая имеет конечное количество решений по модулю группы изометрий, называется жесткой (rigid). Двумя важными свойствами геометрической задачи являются избыточность и сингулярность. Понятие избыточности относится к ограничению - если удаление ограничения не приводит к появлению новых решений задачи, такое ограничение называется избыточным. Сингулярность - свойство не структурное (синтаксическое), но численное, характеризующую такую задачу, бесконечно малое изменение параметра (или группы параметров) которой ведет к изменению структуры пространства ее решений.

Вариационный геометрический решатель

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

? собственно решение задачи (то есть размещение геометрических объектов в соответствии с заданными ограничениями);

? диагностика пере-, недо и хорошо определенных частей задачи, а также расчет степеней свободы геометрических объектов;

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

? автоматическое наложение минимального набора ограничений, делающих задачу хорошо определенной.

Некоторые системы CAD (например, Pro/Engineer, CATIA, T-FLEX) имеют в своем составе собственные геометрические решатели, но большинство коммерческих систем пользуются разработкой английской компании D-Cubed (ныне - дочерняя компания Siemens PLM Software), называемой DCM, Dimensional Constraint Manager. Этот полнофункциональный геометрический решатель представляет собой библиотеку функций для прямого и обратного (callback) вызовов, которые могут быть встроены в любое ядро параметрического моделирования. Решатель существует в двух вариантах - двумерный и трехмерный. Другим доступным вычислительным модулем для разработчиков САПР является решатель LGS (LEDAS Geometric Solver) производства российской компании ЛЕДАС, имеющий не только две версии (2D и 3D), но также различные конфигурации, оптимизированные по набору функций и их стоимости для использования в разных приложениях.

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

Простейшим способом решения геометрической задачи размещения объектов является ее декартово моделирование. Каждому объекту сопоставляется набор вещественных координат, которые полностью описывают его положение на плоскости или в пространстве (например, двумерной точке P можно сопоставить две координаты - x и y). Каждое ограничение представляется одним или несколькими уравнениями. Например, ограничение расстояния между точками

P1 = (x1, y1) и P2 = (x2, y2)

представляется алгебраическим уравнением

(x1 -x2)2 + (y1 - y2)2 - d2 = 0,

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

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

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

Метрический тензор геометрической задачи

Все базовые геометрические объекты (точки, прямые, плоскости, сферы, цилиндры, конусы и т.п.), а также все геометрические ограничения над ними могут быть представлены элементами трехмерного аффинного пространства - точками и векторами с наложенными на них метрическими ограничениями - длины и угла. Напомним, что метрическим тензором набора векторов {v1, …, vn} называется квадратная симметрическая матрица, элементами которой являются скалярные произведения (vi, vj). Отметим следующие важные свойства метрического тензора:

? симметричность;

? неотрицательность диагональных элементов (они равны квадратам длин векторов);

? ранг, не превосходящий размерность пространства;

? если сумма некоторых векторов равна нулю, то сумма соответствующих им элементов в любой строке (столбце) метрического тензора тоже равна нулю.

Эти свойства метрического тензора могут быть использованы при моделировании геометрической задачи в терминах точек и векторов. Прежде всего, каждый вектор с неизвестной нормой представляется в виде произведения его длины (она будет переменной алгебраической задачи) и единичного вектора. Из всего набора единичных векторов выбираются три (два для двумерного пространства) базовых, углы между которыми зафиксированы. Все остальные векторы выражаются через выбранный базис (v = v1e1 + v2e2 + v3e3). Для этого в алгебраическую формулировку исходной геометрической задачи добавляется три (два для 2D) неизвестных коэффициента, связанных уравнением

v1 + v2 + v3 = 1.

Далее, в наборе векторов ищется независимый набор циклов - векторов, сумма которых (некоторые из слагаемых, возможно, взяты с обратным знаком) равна нулю. Для каждого цикла генерируются три (два в 2D) уравнения - сумма коэффициентов соответствующих векторов в разложении по базисному вектору равна нулю. Наконец, осталось учесть заданные углы между векторами. Предположим, между единичными векторами u и v задан угол ?. Векторы эти имеют следующие разложения по базису (e1, e2, e3) с использованием переменных u1, u2, u3, v1, v2, v3:

u = u1e1 + u2e2 + u3e3,

v = v1e1 + v2e2 + v3e3.

Тогда в алгебраической постановке задачи генерируется следующее уравнение:

u1v1 + u2v2 + u3v3 = cos

Методы символьного упрощения систем алгебраических уравнений

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

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

Другие методы символьной подстановки основаны на поиске в системе уравнений специального вида. Конечно, шаблоны для такого поиска существенно зависят от способа алгебраического моделирования геометрических ограничений. Например, при тензорном моделировании все уравнения системы являются линейными или квадратичными, а значит, велика вероятность найти среди них уравнение вида axy = 0. Информацию, содержащуюся в таком уравнении, можно использовать двумя способами. Первый состоит в том, что все вхождения термов bxy в другие уравнения системы можно опустить (независимо от значения b). Второй способ состоит в анализе двух возможностей, вытекающих из данного уравнения - подстановки вместо переменной x значения 0, либо той же подстановки для переменной y. Если какая-то из этих подстановок ведет к противоречию (получению уравнения вида a = 0 для ненулевой константы a), значит единственной возможностью остается вторая, и изо всех уравнений системы можно удалить термы, содержащие эту переменную.

Наконец, еще одним важным частным случаем символьной редукции является нахождение в системе уравнения вида aix2 = 0, где знаки всех ai одинаковы, и замена всюду в системе входящих в него переменных на нули.

Декомпозиция Далмеджа - Мендельсона

Для описания этого метода нам понадобится ввести понятие графа уравнений как двудольного графа, одна доля которого состоит из вершин, соответствующих переменным задачи, а вторая - из вершин, соответствующих уравнениям. При этом вершина-переменная связана ребром с вершиной-уравнением тогда и только тогда, когда соответствующая переменная входит в соответствующее уравнение. Напомним, что паросочетанием (matching) в двудольном графе называется любой набор его ребер, среди которых нет двух инцидентных. Говорят, что вершина входит в паросочетание, если она инцидентна одному из его ребер. Максимальным называется паросочетание, которое на содержится ни в каком другом. Далмедж (Dulmage) и Мендельсон (Mendelsohn) показали, что максимальное паросочетание графа уравнений обладает следующими свойствами:

? все уравнения, не входящие в максимальное паросочетание, являются переопределенными (алгебраически лишними) в системе;

? уравнения и переменные, входящие в максимальное паросочетание, образуют максимальную хорошо определенную подсистему;

? переменные, не входящие в максимальное паросочетание, являются недоопределенными (алгебраически лишними).

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

Рис. 25

Метод Ньютона-Рафсона

Традиционным методом решения систем нелинейных уравнений является итеративный метод Ньютона-Рафсона, который основан на линейной аппроксимации гладкой функции F: Rn ?Rm в окрестности текущей точки x(k):

F(x) F(x(k)) + JF(x(k))(x - x(k)),

где JF(x(k)) - матрица Якоби (первых частных производных) функции F, вычисленная в точке x(k) (приближении к решению, достигнутом на шаге k).

Согласно этой формуле, если мы хотим найти нуль функции (F(x) = 0), находясь в его окрестности, то от точки x(k) надо перейти к точке x(k+1)=x(k) + x, решив систему линейных уравнений с неизвестными x:

JF(x(k))x = -F(x(k))

Несмотря на то, что линейная аппроксимация функции, на которой основан метод Ньютона - Рафсона, справедлива только для достаточно малой окрестности ее нуля, вышеописанный метод стартует из произвольной точки. При этом, как правило, после выполнения небольшого числа итераций (не более пятидесяти) метод сходится к одному из решений уравнения F(x) = 0. Бассейны притяжения каждого нуля в комплексной плоскости образуют области с бесконечно сложными границами, называемые фракталами (рис. 26).

Рис. 26

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

Решение систем линейных уравнений

Напомним, что на каждом шаге метода Ньютона - Рафсона необходимо решать систему линейных уравнений Ax = b. В общем случае мы имеем дело с прямоугольной матрицей A неизвестного ранга. Такая система линейных уравнений может не иметь решений, иметь единственное решение или же бесконечно много решений. Какое же решение подходит для метода Ньютона? Прежде всего, среди всех приближений к решению необходимо выбрать то, которое минимизирует норму вектора невязки: х = ||Ax - b||. Понятно, что для х= 0 мы имеем точное решение, в противном случае - приближение к нему. Независимо от конкретного значения х, в общем случае может существовать бесконечно много векторов x, удовлетворяющих условию ||Ax - b|| = х. Как известно, данное множество является аффинным пространством: х= {x* + y | y хKer A}, где x* - произвольный вектор, удовлетворяющий ||Ax* - b|| = х, а Ker A - линейное пространство решений однородной системы уравнений Ax = 0. Среди всех x с точки зрения метода Ньютона - Рафсона лучше всего подходит элемент с минимальной нормой (||x|| min). Таким образом, метод решения систем линейных уравнений, возникающих на каждом шаге метода Ньютона - Рафсона, должен находить решение:

? минимальное по норме вектора невязки,

? минимальное по собственной норме.

Именно такое решение выдает метод SVD (singular value decomposition), основанный на представлении произвольной mхn матрицы A в виде произведения A = UDVT, где U и V - ортогональные mхm и nхn матрицы соответственно, а D - диагональная матрица, содержащая сингулярные значения матрицы A.

Метод SVD имеет сравнительно высокую временную сложность. Поэтому на практике вместо него используют другие методы, позволяющие найти какое-либо решение x* с минимальной невязкой, а также базис пространства Ker A, после чего вычислить ортогональную проекцию x* на Ker A и отнять ее из x*. Очевидно, полученный вектор будет минимальным по норме. В качестве метода нахождения решения x* и базиса Ker A можно использовать исключение Гаусса - Жордана, с помощью которого вычисляется RREF-форма (reduced row echelon form) матрицы A.



Методы координатного и градиентного спуска

Метод Ньютона-Рафсона быстро сходится в окрестности решения, но он имеет два существенных недостатка:

? если начальное приближение далеко от решения, метод может делать много итераций, не приближающихся к решению;

? стоимость одной итерации чрезвычайно высока (кубически зависит от размера системы уравнений).

Чтобы преодолеть оба этих недостатка, метод Ньютона-Рафсона зачастую используют в комбинации с более простыми методами, не требующими решения системы линейных уравнений на каждом шаге. Такими методами являются метод координатного спуска (другое его название - метод релаксации) и градиентный метод. Оба алгоритма являются итеративными методами последовательного приближения и имеют общую схему. На шаге k задача решения системы из m уравнений над n переменными F(x) = 0 сводится к минимизации вещественной функции одного неизвестного Fi(x(k)(t))2 = 0, где вектор переменных x заменяется (линейной) вектор-функцией x(k)(t) от одной переменной t. Решив эту задачу минимизации относительно t (то есть найдя t* - значение, на котором достигается минимум), полагаем x(k+1) = x(k)(t*). Заметим, что вектор-функция x(k)(t) меняется на каждом шаге алгоритма. Для метода координатного спуска на шаге k она имеет вид:

где x(k-1) - значение на предыдущем шаге. Таким образом, на каждом шаге фиксируем значения всех переменных, кроме одной (очередной). Для градиентного метода используется линейная функция в направлении градиента:

Минимизация неотрицательной функции одной переменной может выполняться численными или аналитическими методами. При решении геометрических задач зачастую приходится иметь дело с системами квадратичных уравнений, для которых Fi(x(k)(t))2 будет многочленом четвертой степени, минимумы которого находятся с помощью метода Кардано.

Методы координатного и градиентного спуска имеют линейную скорость сходимости (то есть норма вектора невязки убывает линейно с ростом числа шагов), поэтому применять их собственно для поиска решения с высокой точностью нецелесообразно. Однако комбинация одного из этих методов с методом Ньютона-Рафсона (имеющим квадратичную скорость сходимости в окрестности решения) оказывается достаточно эффективной для решения задач с произвольным начальным приближением к решению.

Вопросы для самоконтроля

1. Дайте определение вариационной параметрической модели

2. Опишите области приложения вариационного моделирования

3. Дайте определение задаче размещения геометрических объектов и объясните смысл понятий недоопределенность, переопределенность, хорошая определенность, жесткость, избыточность и сингулярность

4. Что такое вариационный геометрический решатель? Приведите примеры

5. В чем разница между декартовым и относительным моделированиями задачи удовлетворения геометрическим ограничениям?

6. Опишите тензорное моделирование задачи размещения геометрических объектов. В чем состоят его преимущества?

7. Опишите методы символьного упрощения систем алгебраических уравнений

8. Опишите методы декомпозиции систем алгебраических уравнений

9. Опишите метод Ньютона-Рафсона. Какие методы решения систем линейных алгебраических уравнений могут использоваться совместно с ним?

10. Опишите методы релаксации и градиентного спуска. В чем их преимущества и недостатки по сравнению с методом Ньютона- Рафсона?

Дополнительная литература

С различными методами вариационного моделирования можно ознакомиться в главе 8 книги [37]. Про некоторые методы, используемые в геометрическом решателе DCM, можно получить представление из работы [34], а для ознакомления с LGS рекомендуется прочитать [22]. Обзорное описание на русском языке методов решения геометрических задач в ограничениях содержится в [16].



Лекция 7. Вариационное моделирование: диагностика и декомпозиция задачи

Диагностика геометрических задач

Как мы уже знаем, каждая геометрическая задача (или любая ее подзадача) является переопределенной, хорошо определенной или недоопределенной. Однако наряду с этими очевидными характеристиками задачи на практике полезно рассматривать и другие: избыточные ограничения, группы зависимостей и оставшиеся степени свободы геометрических объектов. Напомним, что ограничение называется избыточным (redundant), если его удаление не приводит к появлению новых решений задачи. Группа параметрических ограничений называется зависимой, если изменение параметра одного из них создает переопределенную задачу, у которой, однако, снова появляются решения, если мы изменим параметр другого ограничения из группы. (Таким образом, параметры ограничений в группе зависят друг от друга.) Мгновенной степенью свободы геометрического объекта называется его бесконечно малая трансформация, сохраняющая удовлетворенными все наложенные на объект ограничения.

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

Методы упрощения геометрических задач

Работая с системой CAD, пользователь ожидает линейного увеличения времени отклика системы с ростом размера геометрической модели. Чистый алгебраический подход, однако, не обеспечивает линейную сложность решения задачи - обычно требуемое время кубически зависит от размера входных данных (так как решение системы линейных уравнений, выполняемое на каждой итерации метода Ньютона-Рафсона, имеет кубическую сложность). Такая временная сложность алгоритмов становится особенно критичной при решении больших задач, содержащих сотни и тысячи ограничений. Чтобы ускорить время решения задачи, было предложено много разных методов, которые упрощают исходную геометрическую задачу, разбивая ее на совокупность более простых. Отметим, что зачастую такая декомпозиция может состоять в выделении одной нетривиальной подзадачи и нескольких тривиальных, решения которых получаются из решения нетривиальной подзадачи путем использования несложных формул. С реализационной точки зрения такую группу методов декомпозиции можно рассматривать отдельно как методы упрощения, однако с математической точки зрения это является именно декомпозицией, то есть разбиением на подзадачи.

Определение и классификация методов декомпозиции

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

? методы рекурсивного деления;

? методы рекурсивной сборки (подразделяются на методы нахождения структурно жестких подзадач и методы, основанные на шаблонах;

? распространение степеней свободы (или методы отсечения).

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

Граф ограничений

Для объяснения принципа работы методов декомпозиции нам понадобится понятие графа ограничений. Напомним, что неориентированный мультиграф G - это структура, состоящая из двух множеств: множества вершин V и множества ребер E. Между вершинами и ребрами задано отношение инцидентности. Каждое ребро инцидентно одной, двум или большему количеству вершин. Два ребра называются инцидентными, если они инцидентны общей вершине. Говорят, что между двумя вершинами v1 и v2 существует путь, если можно задать последовательность ребер, каждое из которых инцидентно предыдущему ребру в последовательности, первое ребро инцидентно v1, а последнее - v2. Граф ограничений (constraint graph) задачи удовлетворения ограничениям получается ассоциированием множества вершин с множеством объектов задачи, а множества ребер - с множеством ограничений (ребро инцидентно вершинам, являющимся аргументами соответствующего ограничения). Ниже приведен чертеж геометрической задачи и соответствующий граф ограничений (рис. 27).

Рис. 27



Методы рекурсивного деления

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

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

Произвольная пара вершин в двусвязном графе называется парой сочленений (articulation pair), если их удаление (вместе со всеми инцидентными им ребрами) делает граф несвязным. Двусвязный граф, не имеющий пар сочленения, называется трисвязным графом. Максимальный трисвязный подграф называется компонентой тройной связности. Для декомпозиции геометрической задачи на подзадачи, соответствующие компонентам тройной связности ее графа ограничений, необходимо зафиксировать относительные позиции объектов, соответствующих парам сочленения (для того, чтобы потом «склеить» решенные фрагменты в общее решение, используя пары сочленения).

Методы рекурсивной сборки

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

1. Фаза идентификации - найти жесткую (rigid) подзадачу (не имеющую внутренних степеней свободы), называемую кластером:

– шаг слияния: два кластера, связанные достаточным количеством ограничений для формирования жесткой подзадачи, заменяются одним кластером;

– шаг расширения: геометрический объект, связанный с неким кластером достаточным количеством ограничений для жесткого размещения, добавляется в этот кластер.

2. Фаза сокращения:

– каждый найденный кластер образует отдельную подзадачу; вхождения кластеров друг в друга образуют частичный порядок решения подзадач;

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

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

? анализ графа ограничений в соответствии с абстрактными степенями свободы;

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

На рис. 28 ниже приведен пример декомпозиции геометрической задачи на кластеры.

Рис. 28

Формирование кластеров с помощью анализа графа ограничений

Данная группа полиномиальных методов, основанная на понятии структурной жесткости, была впервые предложена и затем эволюционировала в работах группы американских математиков под руководством Кристофа Хоффманна (Christoph M. Hoffmann). Абстрактной степенью свободы геометрического объекта является минимально возможное количество параметров, задающее однозначное положение данного объекта в рассматриваемом пространстве. Например, точка имеет две степени свободы в двумерном пространстве и три в трехмерном, прямая имеет две степени свободы в трехмерном пространстве и четыре в трехмерном и т.п. Абстрактной степенью свободы ограничения является число степеней свободы, которое обычно удаляет из задачи данное ограничение. Например, ограничение расстояния между двумя точками удаляет одну степень свободы из задачи, но если параметр расстояния равен нулю, то количество удаляемых степеней свободы составляет два для двумерных задач и три для трехмерных. Задача (или ее подзадача) называется структурно жесткой, если суммарное количество степеней свободы всех объектов не превосходит суммы абстрактных степеней свободы ограничений плюс число степеней свободы абстрактного полноразмерного жесткого множества (D = 3 в двумерном пространстве, D = 6 в трехмерном). Все методы анализа структурной жесткости основаны на вычислении максимального потока в сети, порожденной по графу ограничений:

? сеть состоит из четырех уровней - фиктивная вершина-источник, вершины-ограничения, вершины-объекты и фиктивная вершина-сток;

? фиктивная вершина-источник соединена в такой сети дугами с вершинами, представляющими ограничения; пропускная способность каждой такой дуги равна числу абстрактных степеней свободы соответствующего ограничения;

? каждая вершина-ограничение соединена дугами со всеми вершинами, представляющими объекты-аргументы данного ограничения; пропускная способность каждой из таких дуг не ограничена;

? каждая вершина-объект соединена дугой с фиктивной вершиной-стоком; пропуская способность такой дуги равна числу абстрактных степеней свободы соответствующего геометрического объекта.

Максимальный поток по такой сети демонстрирует оптимальное распределение степеней свободы ограничений по степеням свободы объектов. Для нахождения максимального жесткого кластера на вход каждого ограничения подается дополнительный поток величины D.

Хоффманн предложил три алгоритма декомпозиции, основанных на анализе максимального потока в сети ограничений:

? конденсирующий алгоритм;

? пограничный алгоритм;

? модифицированный пограничный алгоритм.

Все они отличаются друг от друга только фазой сокращения. Конденсирующий алгоритм заменяет найденный кластер в задаче одним жестким множеством (описываемым D степенями свободы), тогда как два других разделяют множество объектов кластера на пограничные и внутренние, не удаляя явно из задачи первое подмножество. Применяя алгоритмы этой группы на практике, следует быть осторожным - структурная жесткость далеко не всегда означает отсутствие внутренних степеней свободы в подзадаче. Самый известный контрпример на эту тему называется «два банана» (рис. 29).

Рис. 29

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

Формирование кластеров на основе шаблонов

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

Эвристическое формирование псевдокластеров

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

? не являются аргументами неудовлетворенных в начальной позиции ограничений;

? существует как минимум одно ограничение между объектами.

Распространение степеней свободы

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



Вопросы для самоконтроля

1. Какие понятия и методы используются для диагностики геометрических задач с ограничениями?

2. Что такое декомпозиция геометрической задачи с ограничениями? Для чего она применяется?

3. Классифицируйте известные методы декомпозиции геометрической задачи

4. Что такое точка и пара сочленения? Опишите метод декомпозиции задачи с геометрическими ограничениями, основанный на рекурсивном делении графа ограничений.

5. Опишите общую схему декомпозиции задачи с геометрическими ограничениями методом «снизу вверх».

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

7. Опишите методы, используемые для поиска структурно жестких геометрических подзадач.