Структуры данных для хранения геометрической информации.

Поскольку в качестве языка программирования был выбран объектно- ориентированный язык С++, то было решено представить все множество геометрических объектов в виде иерархии классов, пронаследованных от одного единственного (общего) предка [28], называемого «базовым классом». Данный базовый класс назовем Geometricltem (сразу же необходимо отметить, что подобный же подход использован при реализации стандарта ISO 10303 (STEP), который реализован на объектно-ориентированном языке ЭКСПРЕСС). Такая реализация имеет следующие преимущества:

а)Возможно получение единой структуры, подчиненной общим правилам.

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

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

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

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

В свою очередь, класс Раггау реализован как класс-шаблон [28].

Еще один аргумент в пользу массива указателей на объекты. Как следует из описания операционной системы Microsoft Windows [1], указатель (не void*) занимает в памяти 8 байт. При этом указатель всегда занимает в статической памяти одинаковое число байт, независимо от того, на объект какого типа он указывает.

Обратимся к рассмотрению реализации методов класса Geometricltem. Часть методов в нем объявлены как виртуальные методы. Виртуальность, вообще говоря, это одно из важнейших свойств ООП. Это свойство неоднократно будет использовано в нашей работе, «...если у статических методов код и экземпляр объекта связываются во время компиляции, то у виртуальных связь устанавливается во время выполнения программы... Суть виртуального метода заключается в общности использования его действия по одному и тому же имени всеми объектами дерева иерархии, при этом каждый из объектов реализует это действие по-своему. Виртуальность как понятие в данном случае говорит о том, что при вызове такого метода <программиста> больше интересует само действие, чем конкретный экземпляр, посредством методов которого оно будет производиться».[5]

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

Прочие структуры данных.

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

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

3.2 Внутренний формат представления данных

В процессе работы над конвертером был проведен анализ нескольких систем на предмет наличия в них возможности чтения/записи наиболее распространенных обменных форматов. Результаты анализа приведены в таблице 3.1.

Таблица 3.1 Результаты анализа наиболее распространенных систем проектирования

В формате IGES плоскость определена как сущность №108. Она определяется 4- мя коэффициентами в уравнении

А* ХТ+В *ZT+C *ZT=D

Кроме того, записываются XT,YT,ZT координаты размещения символа отображения плоскости, размер символа отображения плоскости и указатель на замкнутую кривую, лежащую в этой плоскости (внешнюю границу), который обычно равен 0.

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

Таким образом, нам предстоит решить 2 проблемы:

- выбрать способ внутреннего представления данных;

- определить, какие сущности будут входить во внутреннее представление.

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

Внутренний формат будет содержать только 3 типа поверхностей: NURBS поверхности, поверхности вращения и линейчатые поверхности.

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

3.3 Выбор NURBS в качестве внутреннего представления кривых и поверхностей

Впервые NURBS были применены в системе Taiger фирмы Boeing в 1979 году [35]. Первый опыт оказался настолько удачным, что NURBS были внесены на рассмотрение в качестве стандартных сущностей формата IGES в августе 1981 года.

Математическое определение NURBS кривых и поверхностей относительно просто. NURBS кривая - это кусочная рациональная полиномиальная функция вида (векторное представление):

(3.1)

где wi - это веса, pi - это контрольные точки, а Ni,_P(u) это нормализованная базисная функция степени р, рекурсивно заданная как:

(3.2)

где Uj это узлы, образующие «вектор узлов»

(3.3)

Порядок, число узлов и число контрольных точек имеют следующую зависимость между собой: m=n+p+l. Для не униформы и непериодических B-сплайнов вектор узлов принимает следующие значения:

 (3.4)

где концевые узлы а и b повторяются в соответствии с множителем р+1. В большинстве практических применений а=0 и b=1. Базисная функция (3.2) определена на всей кривой. NURBS кривая (3.1) с вектором узлов (3.4) имеет Безье-подобный вид. Она интерполирует концевые точки, и касается первого и последнего отрезков контрольного полигона.

NURBS поверхность, в свою очередь, определяется как:

(3.5)

где wi - это веса, Рi - это контрольная сетка, а Ni,p(u) и Nj,q(v) - это нормализованные В-сплайны степени p и й в направлении u и v, соответственно. Они определяются векторами узлов:

(3.6a)

(3.6b)

где концевые узлы повторяются в соответствии с множителями р+1 и q+l, соответсвенно, и r=n+p+1 и s=m+q+l.

Аналитические и геометрические свойства NURBSов

Уравнение NURBS-кривой (3.1) может быть записано в следующей эквивалентной форме:

 (3.7)

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

Генерализация: если все веса установлены в 1, то

где 0 и 1 в U повторяются в соответствии с множителем р+1, a B_i,p(u) определяет полигон Бернштейна степени р.

Локальность: R_i,P(u)=0 если

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

Кроме того, NURBS кривая обладает следующими геометрическими характеристиками: информационный совместимость nurbs валидация

- Безье и нерациональные В-сплайны являются специальными случаями

- Локальная аппроксимация: если контрольная точка перемещается или изменяется узел, это влияет только на p+1 участок кривой;

если , то кривая C(u) всегда лежит внутри выпуклой оболочки Pi-p,…,Pi;

NURBSы инвариантны к аффинному и перспективному преобразованиям;

функция дифференцируема также, как базисная функция;

если некоторый вес устанавливается равным нулю, то положение

соответствующей ему контрольной точки не влияет на кривую в целом;

3.4 Проблемы сохранения точности и валидации внутреннего формата

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

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

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

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

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

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

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

Большинство форматов имеют сущность «обрезанная поверхность». Как правило, она представляет собой 2 ссылки: ссылку на обрезаемую поверхность и на набор границ (одна внешняя, остальные внутренние). В различных форматах границы могут быть представлены по-разному. В формате STEP, например, границами являются пространственные кривые, усеченные вершинами (x,y,z представление). В формате IGES в качестве границ могут выступать как полигоны в (u,v)-представлении (в пространстве поверхности), так и набор пространственных кривых (x,y,z).

Проблема заключается в том, при импорте, в частности, IGES-файлов, многие системы не умеют производить обрезку по пространственным кривым, и требуют наличия кривой обрезки в (u,v)-представлении. Следовательно, возникает задача - при преобразовании (в данном примере, из STEP в IGES) преобразовывать границы обрезки из пространственных кривых в (u,v) - полигоны в пространстве поверхности.

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

Обычный способ - это проецировать пространственную кривую на поверхность. Данный путь весьма трудоёмкий и влечет за собой большее количество вычислений.

В ADC реализован новый способ, более быстрый и простой. Идея состоит в том, чтобы преобразовать пространственную кривую в полигон с определённым шагом, а затем спроецировать все точки полигона на поверхность.

Рис.3.3. Алгоритм преобразования обрезанной поверхности

На рисунке 3.3 приведен алгоритм записи обрезанной поверхности в выходной файл.

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

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

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

Рис.3.4. Алгоритм проецирования точек контура обрезки на поверхность

На рисунке 3.4 приведен алгоритм проецирования точек контура обрезки на поверхность. Входными данными являются поверхность, величина стрелки прогиба и полигон обрезки.

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

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

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

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

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

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

Существует два нежелательных случая.

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

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

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

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

В данной реализации величина стрелки прогиба задаётся пользователем вручную. Пример влияния выбора величины стрелки прогиба на результат преобразования файлов приведен в главе 4.

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

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

Еще одной трудностью может стать необходимость перепараметризации. Легко представить себе следующий случай. В системе-источнике существует NURBS-кривая, усеченная двумя точками. Точки при этом задаются в параметрическом виде. Пусть NURBS-кривая имеет параметрический диапазон [0;1], а точки усечения имеют значения 0.3 и 0.6 соответственно.

В свою очередь, в системе-приемнике отсутствует тип NURBS-кривая. Вместо этого все кривые представляются в виде сплайнов Безье. На первый взгляд проблема неочевидна, и ход действий представляется таким:

NURBS-кривая -> Безье - кривая -> Усечение по параметру -> Безье - кривая

Однако данный вариант является ошибочным. Ведь параметризация у NURBS - кривых и Безье - кривых абсолютно разная. Следовательно, параметрическая точка 0.3 может оказаться на Безье-кривой совсем в другом месте, чем она была на NURBS- кривой. Устранение этого эффекта носит название «перепараметризации». Правильный вариант преобразования должен быть следующим:

NURBS -кривая -> Усечение по параметру -> NURBS - кривая -> Безье - кривая

Передача дополнительной (конструкторской, технологической) информации чертежа.

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

а) нет единого способа представления информации, относящейся к разным стандартам (ЕСКД, ИСО, др.), а также нет единого способа преобразования этой информации между стандартами;

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

В качестве иллюстрации приведём пример разработки алгоритмов сохранения и чтения основной надписи чертежа (штампа). Информация о штампе хранится в базе данных. Названия полей базы соответствуют ЕСКД названиям полей штампа (Чертил, Проверил, …). Была поставлена задача: при сохранении файлов формата STEP сохранять эту информацию внутри STEP файла. При загрузке STEP файлов - считывать соответствующие сущности (если они имеются), и записывать в специальный текстовый файл, который затем автоматически подгружается в систему.

Стандарт STEP не предусматривает сохранение информации о штампе в соответствии с ЕСКД. Однако некоторая информация о создателях и проверяющих все же существует. Такие сущности, как: PERSON, ORGANIZATION, DATEANDTIME, SECURITYCLASSIFICATION, PERS ON_ ANDORGANIZ ATIONROLE, APPROVAL ROLE, APPROVAL STATUS, APPROVAL и ряд других пригодны для использования в качестве носителей подобной информации. В качестве основной сущности-определения была выбрана сущность PERSON AND ORGANIZATION ROLE, параметром которой является идентификатор лица, имевшего то или иное отношение к чертежу. В результате многочисленных экспериментов были установлены следующие зависимости:

Таблица 3.3. Зависимости между полями основной надписи чертежа и сущностями языка STEP

При сохранении STEP файла из системы информация записывается непосредственно в выбранные сущности с указанными в таблице параметрами. Дополнительно сохраняются дата и время в соответствии с требованиями формата STEP. Хотим заметить, что получившиеся файлы были протестированы с помощью инструмента StepCheck Online (http://www.iti.org/cec/steptest/rvsf/index.htm) и полностью соответствовали спецификации ISO.

Также при разработке программного средства была сформирована методика информационной совместимости в соответствии со стандартом STEP (Приложение).

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

Приложение. Метод информационной совместимости в соответствии со стандартом внутреннего языка моделирования