Постановка задачи

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

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

В течение всего жизненного цикла изделия различными системами проектирования (CAD), изготовления (CAM), инженерных расчётов (CAE) и другими системами используется одна и та же геометро-графическая информация. Каждая из этих систем использует как ранее накопленную и введенную в электронный архив, так и создает свою, только ей присущую, информацию, которая и формирует в совокупности полную электронную модель проектируемого изделия.

ГОСТ 2.052-2015 определяет электронную модель как «модель изделия, выполненную в компьютерной среде» и уточняет понятие электронной геометрической модели изделия как модель, описывающую преимущественно геометрическую форму, размеры и иные свойства изделия, зависящие от его формы и размеров [3].

Приведем ряд определений, содержащихся в ГОСТ 2.052-2015, и поясним их комментариями, отражающими авторский взгляд на обсуждаемую проблему.

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

При различных структурах данных и алгоритмах решения одних и тех же проблемных задач каждая из составляющих CALS технологий решает функциональную задачу преобразования размерности пространства данных, либо оставляет её без изменения [4]. В процессе формирования электронной модели изделия происходит работа в двух пространствах: пространстве изображений (2D) и пространстве объекта (3D) (рис. 1).

 

Рис.1 Информационный процесс формирования электронной модели изделия.

 

Обратим внимание на тот факт, что требуется как работа внутри указанных пространств, так и постоянное преобразование данных из одного пространства в другое. Так, например, системы автоматизированного черчения (CAD) имеют на входе и на выходе информацию о плоских (2D) геометрических объектах в виде чертежа, в то время как системы автоматизированного проектирования (CAD) и инженерных расчетов (CAE) работают как с плоскими (2D), так и пространственными (3D) объектами. Системы автоматизации сборки (CAA) и моделирования поведения объекта (CAS), как правило, не изменяют размерности пространства моделирования. Системы визуализации (CAVE), быстрого прототайпинга или аддитивных технологий (CARP), управления станками с ЧПУ (CAM) преобразуют данные об объекте для перехода в двумерное пространство (т.е. понижают размерность). Заметим, что процесс анализа объекта и задействованные при этом алгоритмы, позволяющие синтезировать изображения, разработаны значительно лучше, чем процессы анализа изображений и синтеза по ним 3D моделей пространственного объекта.

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

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

Как отмечал профессор Полозов В.С. [5], системы геометрического моделирования могут быть разделены на две большие группы:

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

По уточнению Роткова С.И. [6, 7], вторая группа делится на две категории:

• несвязанные системы 1-го рода, в которых по модели 3D объекта генерируется набор 2D изображений. При этом в системе решается прямая задача инженерной геометрии, а именно, проецирование модели объекта на заданную картинную плоскость;
• несвязанные системы 2-го рода, в которых по набору 2D изображений генерируется модель 3D объекта, и затем (при необходимости) формируется новый набор 2D изображений, отличный от предыдущего. В таких системах одновременно решаются как прямая, так и обратная задача инженерной геометрии.

Известны программные реализации функционального оператора 2D→3D в некоторых системах, например, таких как Autodesk Inventor и Solid Edge [8], которые используют интерактивный подход к решению проблемы синтеза 3D геометрической модели объекта по проекциям.

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

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

Наиболее полно удовлетворяют требованиям пользователей САПР системы 2-го рода, так как приемы работы в них максимально приближены к естественным приемам работы конструкторов и проектировщиков (примерами таких систем являются системы ИНГРАФО [5], КИТЕЖ [9, 10]). Но большинство существующих несвязанных систем являются системами 1-го рода, и они позволяют получать 3D образы пространственных объектов с помощью такой исходной информации, которая наиболее удобна для ввода в ЭВМ и решения задачи получения изображений с точки зрения программистов и математиков, а не конструкторов.

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

Вопрос о снятии хотя бы части этих ограничений является необходимым для совершенствования систем моделирования 2-го рода, особенно в свете развития и внедрения CALS- и BIM-технологий.

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

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

При этом будем считать, что:

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

• каждый файл может быть создан в различных системах геометрии и графики;

• файлы содержат информацию о геометрических элементах в векторном, а не растровом, виде.

Задачу чтения и распаковки информации из файла, которая может быть задана как в одном из стандартных форматов (IGES, STEP, DXF), так и во внутренней структуре данных системы геометрии и графики, в данной работе мы не рассматриваем.

Алгоритм синтеза образа объекта по его проекционным изображениям состоит из 4 основных этапов:

1.            Этап создания каркасной модели.

1.1.     Анализ проекций.

1.2.     Создание массивов 3-х мерных координат и связей между ними (рёбер) – формирование предварительной каркасной модели.

1.3.     Выявление и удаление ложных геометрических элементов.

2.            Преобразование каркасной модели в граничную модель.

3.            Создание конструктивной модели.

4.            Визуализация.

Здесь следует пояснить используемые далее понятия геометрического моделирования и геометрических моделей разных типов [5, 11, 12, 13, 14, 15].

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

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

ГОСТ 2.052-2015 устанавливает следующие виды геометрических моделей объекта: каркасную, граничную (поверхностную), конструктивную твердотельную. Каркасная геометрическая модель (каркасная модель) определяется как «трехмерная геометрическая модель, представленная совокупностью точек, отрезков и кривых, определяющих в пространстве форму изделия».

Определение 4. Каркасной моделью (КМ) (wire frame) геометрического объекта называется совокупность

KM = {V, R, A}, где  

V - вектор координат X_i, Y_i, Z_i вершин объекта, где  i = 1,…,n;

R - информационный массив, содержащий данные о ребрах R_ij, соединяющих вершины V_i и V_j объекта. Такой информационный массив называется матрицей смежности ориентированного или неориентированного графа и может быть представлен в памяти ЭВМ самыми разными способами, в том числе двумерным массивом данных размерностью n´n, либо списковыми структурами [4, 16].

A - информационный массив атрибутов вершин V_i и ребер R_ij. Каждому ребру может быть поставлен в соответствие квалификационный признак (атрибут), характеризующий данное ребро: линейное или нелинейное, коэффициенты уравнений линий – носителей ребер, каким типом линии, согласно ГОСТ 2.303-68, 2.305-2008 [17, 18], изображаются проекции ребра (основная, штриховая, штрихпунктирная, волнистая и т.д.), толщина изображающих проекции линий (основная, тонкая, утолщенная), цвет линий.

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

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

{Vi - вершина из V, Тi - атрибут истинности вершины, Ki - валентность вершины, V1i, ... , Vki - набор смежных ей вершин из V, где k = 1...Ki, i = 1...NV}.

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

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

Конкретизируем другие определения ГОСТ 2-052.2015.

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

Определение 5. Поверхностной (граничной) моделью  (ГМ) (boundary representation или b-rep) пространственного объекта называется совокупность

ГМ = {G, V, R, A},  где 

V, R - информационные массивы, используемые в КМ,

G - информационный массив граней (отсеков поверхностей),  где i -тый элемент массива ( i - ая грань) G_i  =  {(V_1i, V_2i, V_3i, ...V_ni) Î F_i, где F_i Î F, а V_1i, …, V_ni Î V} задается своими вершинами, перечисленными в порядке обхода грани против часовой стрелки, начиная с произвольно выбранной вершины. При этом контур, охватывающий грань G_i , может быть  как односвязным, так  и неодносвязным, без самопересечений.

A - информационный массив атрибутов вершин V_i, ребер R_ij и граней G_i, куда, в свою очередь входят следующие массивы:

F - информационный массив, содержащий коэффициенты уравнений

F_i (x, y, z) = 0 поверхностей, которые являются носителями граней G_i;

L – информационный массив, содержащий коэффициенты уравнений

L_ij (x, y, z) = 0 кривых 1 или 2 порядка, которые являются носителями ребер R_ij.

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

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

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

Определение 6.  Твердотельной (конструктивной) моделью (Constructive Solid Geometry или CSG- rep) называется совокупность

СМ = {G(R), B(M), A},  где 

G(R) - граф сборки конструкции [4, 16], либо бинарная древовидная структура [19], определяющие порядок и характер взаимодействия составляющих объектов,

    R - ребра графа, атрибутами которого могут быть параметры формы и положения i-ой модели относительно j-ой модели и знаки регуляризированных [4] теоретико-множественных операций объединения, вычитания и пересечения.

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

Параметрами положения могут быть вектор переноса Т и вектор поворота Е, задающий углы поворота i-го объекта на заданные углы относительно координатных осей.

В(М) - банк моделей пространственных объектов, каждый из которых может быть как непроизводной, так и составной [13] фигурой. Модели объектов, составляющих банк, могут быть сформированы различными средствами и способами [9, 10] и заданы в своей собственной системе координат, не связанной с системой координат проектируемого объекта. Каждой модели поставлено в соответствие символическое имя, по которому идет поиск информации, и имя файла, в котором хранится вся информация, относящаяся к модели.

А - атрибуты моделей (материал, плотность, цвет и т.д.)

Модель материального тела или конструктивная (constructive solid geometry, CSG) модель дает возможность определить качественные характеристики объекта и его структуру.

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

При этом отметим, что ГОСТ 2.052-2015 совершенно не определяет другие виды представления геометрической информации, которые применяются в различных программных разработках и также входящих в понятие электронной модели изделия, а именно, точечную модель или облако точек (cloud representation) и растровую или воксельную (voxel representation).

Разработке алгоритмов решения полной задачи синтеза моделей по проекционным изображениям посвящено достаточно малое количество публикаций в литературе по геометрическому моделированию в силу нетривиальности как самой задачи, так и её программной реализации. Удалось получить информацию лишь о некоторых коллективах, которые смогли создать устойчиво работающий программный продукт промышленного уровня, реализующий различные подходы к решению поставленной проблемы. Это фирма MATRA DATAVISION (Франция) [20], университет Бен-Гуриона (Израиль), Ижевский государственный технический институт - группа проф. В.Н. Кучуганова [21] и коллектив программистов НИИ Механики ННГУ и ННГАСУ под руководством проф. С.И. Роткова [11].

Задача синтеза 3D модели по чертежным изображениям известна как задача «чтения чертежа» или как обратная задача начертательной геометрии [12].

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

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

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

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

В алгоритме преобразования 2D в 3D можно выделить семь основных шагов:

1.     Анализ проекций;

2.     Создание массивов 3-х мерных координат (точечная модель);

3.     Создание предварительной каркасной модели;

4.     Анализ ложных геометрических элементов – уточнение каркасной модели;

5.     Создание граничной модели;

6.     Создание конструктивной модели.

7.     Визуализация.

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

Заметим также, что многие системы геометрического моделирования работают с каркасными и граничными моделями, в том числе и осуществляют преобразования между ними. Модели в этом случае изначально сконструированы в трёхмерном пространстве и поэтому представляют собой реальные трёхмерные тела. Мы же будем рассматривать модели объекта, восстановленные по чертежу, допускающему неоднозначное толкование (по причине неудачного выбора проекционных видов, либо их недостаточности). Задача восстановления образа 3D-объекта по такому чертежу подразумевает получение на первом этапе каркасной модели, в общем случае, несущей в себе ложные геометрические элементы, обусловленные процессом “чтения чертежа” [12]. Такую каркасную модель будем называть предварительной каркасной моделью.

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

Появление ЛГЭ каркаса обусловлено существованием на чертеже конкурирующих геометрических элементов.

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

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

 

Рис. 2.  Пример мультипликативного решения задачи синтеза

 

Рис. 3. Пример проекций, не позволяющих однозначно восстановить 3D-образ пространственного объекта (два варианта)

 

Осуществить преобразование предварительной каркасной модели в граничную, значительно сложнее, чем преобразование каркасной модели, представляющей собой реальное физическое тело [14].

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

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

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

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

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

Методы более широкого использования топологии появились сравнительно недавно, в 80-е годы XX века. Wesley и Markowsky [22, 23] - одни из первых исследователей, которые стали использовать идеи топологии. Их алгоритмы охватывают многие, в том числе и неоднозначные случаи. Однако геометрическая информация ещё широко используется, (например, рассчитываются нормали поверхностей). Поэтому область применения их метода также ограничена геометрическими телами с прямыми ребрами и плоскими гранями.

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

Например, метод Dutton и Brigham [24] использует технику планарной вставки, в которой каркас представлен в виде плоского двумерного графа, где ни одно из ребер не пересекается, за исключением вершин. Полученные области представляют грани геометрического тела. Этот метод стал возможным благодаря эффективному алгоритму вставки Tarjan [25]. Алгоритм пригоден только для тел без отверстий, полостей и без неоднозначности распознавания, что и является его основным недостатком.

Топологический метод Ganter и Uicker [26], основанный на более ранней работе Cobb [27], а также теории графов, рассматривает тело как граф «ребро-вершина», который даёт возможность найти множество независимых замкнутых путей, называемых циклами. Ряд циклов затем преобразуется в истинные грани путём сочетания циклов таким образом, что они минимизируют (редуцируют) взаимосвязь рёбер. Грани затем могут быть ориентированы относительно друг друга, если это потребуется. Недостатком реализации этого метода является то, что при его использовании необходим интерактивный редактор граней, чтобы справиться с определёнными аномалиями, которые могут возникнуть в ходе выполнения алгоритма, а также, тот факт, что каркас априорно считается истинным (т.е. не несущим в себе ложные геометрические элементы). Большим преимуществом метода является отсутствие ограничений характера геометрического тела, поэтому целесообразно использовать его как основу улучшения алгоритма, не требующего вмешательства человека. Такая попытка была предпринята Couter и Brewer [28]. Большая часть их алгоритма использует алгоритм Ganter и Uicker [26]. Разница наблюдается в процессе преобразования первоначального набора циклов в истинные грани. Усовершенствование происходит за счёт логического устройства, которое автоматически находит и устраняет аномалии, т.е. недействительные грани.

Большое внимание преобразованию предварительной каркасной модели в поверхностное представление уделено в работе R. Lequette [29]. В ней используется следующий принцип: каркасная модель, состоящая из вершин, конструктивных и очерковых ребер дополняется касательными ребрами (ребро между поверхностями, вдоль которого не нарушается порядок непрерывности касательной к поверхности). Исследуются пары ребер и выделяются возможные поверхности по принципу:

1.     Два прямых ребра определяют плоскость.

2.     Прямая и дуга определяют цилиндр, конус или плоскость (в зависимости от ряда факторов).

3.     Две дуги определяют сферу или тороидальную поверхность.

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

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

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

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

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

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

1.   Если в ходе преобразования каркаса выяснилось, что он содержит ложные геометрические элементы и необходимо их выявить;

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

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

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

Такой каркас первоначально проходит обработку алгоритмом выявления истинных граней объекта [16, 26]. 

На первом шаге алгоритма строится фундаментальная система циклов графа (ФСЦ). Эта система, являясь базисом пространства всех циклов графа, позволяет путём линейного комбинирования составляющих её циклов получить любой другой цикл графа.

 

Рис. 4 Пример объекта, заданного тремя ортогональными проекциями

 

Рис. 5 Объект, проекции которого показаны на рис.4

 

Рис. 6 Каркасная модель объекта, восстановленная по проекциям

 

Следующим шагом алгоритма является преобразование полученной фундаментальной системы.

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

Если каркас не включает в себя ложные геометрические элементы, то он называется истинным.

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

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

Ложной гранью называется грань, которая не может отделить твёрдое тело от пустого пространства.

Процесс преобразования каркасной модели пространственного объекта в граничную подразделяется на несколько этапов:

•         создание математической модели каркаса - неориентированного графа;

•         генерирование фундаментальной системы циклов графа;

•         процесс преобразования (редукции) ФСЦ в истинные грани с одновременным поиском и удалением ложных геометрических элементов [16, 26].

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

Итак, предполагается, что каркасная модель объекта представлена графом, а значит, множествами его вершин и ребер. Заметим, что для реального объекта граф считается связным (в случае наличия отверстий вводятся дополнительные ребра). Известно, что для конечного связного графа определено цикломатическое число k = ke - kv + 1, где ke - число ребер, а kv - число вершин. Из этого соотношения следует, что k есть число ребер, не принадлежащих произвольно выбранному остову.

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

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

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

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

Выбирается вершина с максимальным числом смежности (валентностью) – корень дерева. Такой корень позволяет построить низкое и широкое дерево. Все смежные ей вершины заносятся в специальный список S.

В список Ostov заносится информация о данной вершине и первых ветвях.

Далее, берется первая вершина V1 из списка S и рассматриваются по очереди смежные ей вершины V11, ... , V1k. Если, например, вершина V11, смежная вершине V1, не принадлежит списку S, то она заносится в конец этого списка, причем одновременно уничтожается информация о соединении V1 и V11 из списка Graf (для того, чтобы при последующих шагах алгоритма уже внесенные в остов ребра не рассматривались). Далее эту информацию заносят в список Ostov (для того, чтобы построить еще одну ветвь остовного дерева).

Берется следующая вершина, смежная V1 - V12. Если она оказалась в списке S (например, V12 = Vj ), то это говорит о том, что найдено ребро V1Vj, которое нужно удалить для формирования остовного дерева. После выбора одной из двух вершин, инцидентных найденному ребру, происходит подъем из нее по остовному дереву до корневой вершины, с запоминанием пути L1. Затем из оставшейся концевой вершины начинается восхождение по остовному дереву до встречи с первой такой вершиной, которая содержится в пути L2. Пройденный путь L2 также запоминается.

Объединив пути L1 и L2, получаем замкнутый путь L, который и является циклом, получающимся добавлением к остовному дереву ребра V1Vj.

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

Пример построения остовного дерева для некоторой каркасной модели показан на рис. 5. Ребра, которые требуется удалять для формирования остовного дерева и формирования циклов, помечены «крестиком».

 

Рис. 7

 

В процессе построения остовного дерева получена фундаментальная система циклов графа: (3-4-1-2), (10-9-1-2), (11-10-2-3), (5-14-9-1-4-8),

(6-7-8-5), (12-7-8-4-1-2-3-11), (6-13-14-9-1-4-8-5), (12-13-14-9-1-2-3-11).

Количество циклов соответствует цикломатическому числу (в данном случае k = ke - kv + 1 = 21 – 14 +1 = 8).

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

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

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

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

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

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

Алгоритм преобразования предварительной каркасной модели в граничную реализован в программе KMinGM, разработанной членами авторского коллектива данной статьи [16], новая ее версия на текущий момент проходит тестирование и отладку.

Выводы

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

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

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

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

Литература

1.     Глушков, В.М. Основы безбумажной информатики / В.М. Глушков. – М.: Наука, 1982. – 552 с.

2.     Т. В. Мошкова, Т.В. Проблема синтеза модели 3D объекта по его проекционным изображениям. Аналитический обзор / Мошкова, Т.В., С. И. Ротков, В. А. Тюрина // Научная визуализация, 2018, том 10, номер 1, стр. 135-156, DOI: 10.26583/sv.10.1.11

3.     ГОСТ 2.052-2015 Электронная модель изделия.

4.     Ротков, С.И. Средства геометрического моделирования и компьютерной графики пространственных объектов для CALS-технологий: Дис. докт. техн. наук: 05.01.01 / С.И. Ротков. – Н. Новгород, 1999. – 287 с.

5.     Полозов, В.С. Моделирование и синтез операторов геометрического расчета и машинной графики в системах автоматизированного проектирования и автоматизации технологической подготовки производства: Автореф. дис. … докт. тех. наук: 05.01.01. / В.С. Полозов. - М.: МАИ, 1983. - 41 с.

6.     Ротков, С.И. Анализ некоторых систем геометрии и графики пространственных объектов / С.И. Ротков // Проблемы информационных систем: сб.ст. - М.: МЦНТИ, 1988. - № 5.

7.     Ротков, С.И. Интеграция 2D и 3D систем геометрии и графики / С.И. Ротков //  Сб. трудов международ. конф. "Графикон-93", С. Петербург, 1993.

8.     Рубен Боргоньен: Учимся 3D-моделированию вместе с Solid Edge: пер. с англ. Общества с ограниченной ответственностью «Сименс Индастри Софтвер». – М.: ДМК Пресс, 2012. – 594 с.: ил.

9.     Зудин, А.А. Использование системы «КИТЕЖ» для моделирования пространственных объектов сложных технических форм и структур / А.А. Зудин, С.В. Митин, С.И. Ротков, В.П. Шубин // Тез. докл. Всесоюзного научно-технического семинара «Опыт разработки и внедрения САПР объектов химического и нефтяного машиностроения». – М.: Наука, 1988.

10. Зудин, А.А. Новая технология геометрического моделирования твердых тел / А.А. Зудин, С.И. Ротков // Сб. тезисов Междунар. конф. «VAI-91». –  Новосибирск, 1991.

11. Аристова, Е.В. Система геометрического моделирования  пространственных объектов КИТЕЖ / Е.В. Аристова, А.А. Зудин, С.Е. Лабутин, С.В. Митин, С.И. Ротков, В.П. Шубин // Сб. трудов 4-ой Междунар. конф. по комп.  графике и визуализации ГРАФИКОН-94. - Н. Новгород. - 1994. - С. 72 – 74.

12. Котов, И.И. Алгоритмы машинной графики / И.И. Котов, В.С. Полозов,  Л.В. Широкова. – М.: Машиностроение, 1977. – 232 с.

13. Полозов, В.С. Геометрические и графические задачи: Автоматизированное проектирование / В.С. Полозов, О.А. Будеков, С.И. Ротков, Л.В. Широкова. – М.: Машиностроение, 1983. - 280 с.

14. Ротков, С.И. Преобразование каркасной модели трёхмерного геометрического объекта в конструктивную модель / С.И. Ротков, В.А. Тюрина // Труды 6-й Междунар. конф. по комп. графике и визуализации Графикон-96. - С.- Петербург, 1996. - С. 56 – 58.

15. Тюрина, В.А. Информационная модель каркаса трёхмерного геометрического объекта для задачи синтеза 3D объекта по ортогональным проекциям / В.А. Тюрина, С.И. Ротков // Начертательная геометрия,        инженерная и компьютерная графика: Сборник статей. - Н. Новгород, 1999. - Вып.4. - С. 149 – 156.

16. Тюрина, В.А. Разработка методов преобразований каркасной модели в задаче синтеза образа 3D-объекта по его проекциям: Дисс. канд. техн. наук: 05.01.01 / В.А. Тюрина. – Н. Новгород, 2003. – 170 с.

17. ГОСТ 2.303-68 Линии.

18. ГОСТ 2.305-2008 Изображения: виды, разрезы, сечения.

19. Оре, О. Теория графов / О. Оре. – М.: Наука, 1977.

20. EUCLID. Technical Report. MATRA Datavision, France, 1988.–200 p.

21. Кучуганов, В.Н. Автоматический анализ машиностроительных чертежей / В.Н. Кучуганов. – Иркутск: Изд-во Иркутск. Ун-та, 1985.–112 с.

22. Markowsky G. Fleshing out projections / G. Markowsky, M.A. Wesley // IBM J. Res& Develop. November, 1981. – Vol. 25, № 6. –               P. 934 – 954.

23. Markowsky, G. Generation of solid models from two-dimensional and three- dimensional data / G. Markowsky, M.A. Wesley // in Pickett, MS and Boyse, J M (eds). Solid modelling by computer: from theory to application: Plenum, 1986. – P. 23 – 51.

24. Dutton, R. Efficiently Identifying the Faces of a Solid / R. Dutton, R.C. Brigham // Computers and Graphics in mechanical engineering. 1983. – Vol.7, № 2. – P. 143 – 147.

25. Tarjan, R. An Efficient Planarity Algorithm / R. Tarjan // Computer Science Department. – Report № CS – 244 – 71: Stanford University, November, 1971.

26. Ganter, M.A. From Wire-Frame to Solid Geometric: Automated Conversion of Data Representations / M.A. Ganter, J.J. Uicker // Computers in mechanical engineering. – sept. 1983. – Vol. 2, № 2. – P. 40 – 45.

27. Cobb, E.C. On the Extraction of Solid Geometry from a Wire Frame Geometric Data Base / E.C. Cobb // M.S. Thesis: University of  Wisconsin-Madison. – 1978.

28. Courter, M. Automated Conversion of Curvelinean Wire-Frame Models to Surface Boundary Models; A Topological Approach / M. Courter, J. Brewer // SIGGRAF-86. – Dallas, 18-22 aug.1986. – Vol. 20, № 4.

29. Lequette, R. Automatic construction of curvilinear solids from wire frame views / R. Lequette // France. – 1988. – Vol.20, №4. – P.171–178.

---

Problem of transformation the wireframe model of the 3D object, restored from its technical drawing

Authors: T.V. Moshkova¹, S.I. Rotkov², M.M. Smychek³, V.A. Tyurina⁴

University of Architecture and Civil Engineering of Nizhny Novgorod

¹ ORCID: 0000-0003-1003-2914

² ORCID: 0000-0002-0662-7619

³ ORCID: 0000-0002-4657-1074

⁴ ORCID: 0000-0002-0234-9041

 

Abstract

The article describes ways of solving the problem of transforming the framework model of a three-dimensional object, reconstructed from the information contained in its technical drawing. This task is one of the stages of the automated synthesis of the 3D model of an object by a set of its 2D images and refers to the hard-formable. A brief review of the literature sources, both Russian and foreign, on the problem posed is presented, and a variant of the solution is proposed.
This article is a fragment of a plenary report by Sergei I. Rotkov, E.V. Popov, Т.V. Moshkova, V.А.Tyurin, D.Yu.Vasin, S.Romenensky, N.L. Makarov, V.M. L.Chekpasova "The problem of converting paper archives of drawing and design documentation into an electronic model of a product and associated geometric-graphic tasks" at the 27th International Conference on Computer Graphics and Visualization "GRAPHICON-2017", September 24-28, 2017, Perm, PGNIU.

 

Keywords: the inverse problem of engineering geometry, the synthesis of the object model, the electronic model of the product, the wireframe model, preliminary frame model, the boundary model, the false geometric elements.

References

               

1.     Glushkov, V.M. Osnovy bezbumazhnoj informatiki / V.M. Glushkov. – M.: Nauka, 1982. – 552 s. [In Russian]

2.     T. V. Moshkova, T.V. Problema sinteza modeli 3D ob"ekta po ego proekcionnym izobrazheniyam. Analiticheskij obzor / Moshkova, T.V., S. I. Rotkov, V. A. Tyurina // Nauchnaya vizualizaciya, 2018, tom 10, nomer 1, str. 135-156, DOI: 10.26583/sv.10.1.11. [In Russian]

3.     GOST 2.052-2015 Elektronnaya model' izdeliya. [In Russian]

4.     Rotkov, S.I. Sredstva geometricheskogo modelirovaniya i komp'yuternoj grafiki prostranstvennyh ob"ektov dlya CALS-tekhnologij: Dis. dokt. tekhn. nauk: 05.01.01 / S.I. Rotkov. – N. Novgorod, 1999. – 287 s. [In Russian]

5.     Polozov, V.S. Modelirovanie i sintez operatorov geometricheskogo rascheta i mashinnoj grafiki v sistemah avtomatizirovannogo proektirovaniya i avtomatizacii tekhnologicheskoj podgotovki proizvodstva: Avtoref. dis. … dokt. tekh. nauk: 05.01.01. / V.S. Polozov. - M.: MAI, 1983. - 41 s. [In Russian]

6.     Rotkov, S.I. Analiz nekotoryh sistem geometrii i grafiki prostranstvennyh ob"ektov / S.I. Rotkov // Problemy informacionnyh sistem: sb.st. M.: MCNTI, 1988. - № 5. [In Russian]

7.     Rotkov, S.I. Integraciya 2D i 3D sistem geometrii i grafiki / S.I. Rotkov //  Sb. trudov mezhdunarod. konf. "Grafikon-93", S. Peterburg, 1993. [In Russian]

8.     Ruben Borgon'en: Uchimsya 3D-modelirovaniyu vmeste s Solid Edge: per. s angl. Obshchestva s ogranichennoj otvetstvennost'yu «Simens Indastri Softver». – M.: DMK Press, 2012. – 594 s.: il. [In Russian]

9.     Zudin, A.A. Ispol'zovanie sistemy «KITEZH» dlya modelirovaniya prostranstvennyh ob"ektov slozhnyh tekhnicheskih form i struktur / A.A. Zudin, S.V. Mitin, S.I. Rotkov, V.P. SHubin // Tez. dokl. Vsesoyuznogo nauchno-tekhnicheskogo seminara «Opyt razrabotki i vnedreniya SAPR ob"ektov himicheskogo i neftyanogo mashinostroeniya». – M.: Nauka, 1988. [In Russian]

10. Zudin, A.A. Novaya tekhnologiya geometricheskogo modelirovaniya tverdyh tel / A.A. Zudin, S.I. Rotkov // Sb. tezisov Mezhdunar. konf. «VAI-91». –  Novosibirsk, 1991. [In Russian]

11. Aristova, E.V. Sistema geometricheskogo modelirovaniya  prostranstvennyh ob"ektov KITEZH / E.V. Aristova, A.A. Zudin, S.E. Labutin, S.V. Mitin, S.I. Rotkov, V.P. SHubin // Sb. trudov 4-oj Mezhdunar. konf. po komp.  grafike i vizualizacii GRAFIKON-94. - N. Novgorod. - 1994. - S. 72 – 74. [In Russian]

12. Kotov, I.I. Algoritmy mashinnoj grafiki / I.I. Kotov, V.S. Polozov,  L.V. SHirokova. – M.: Mashinostroenie, 1977. – 232 s. [In Russian]

13. Polozov, V.S. Geometricheskie i graficheskie zadachi: Avtomatizirovannoe proektirovanie / V.S. Polozov, O.A. Budekov, S.I. Rotkov, L.V. SHirokova. – M.: Mashinostroenie, 1983. - 280 s. [In Russian]

14. Rotkov, S.I. Preobrazovanie karkasnoj modeli tryohmernogo geometricheskogo ob"ekta v konstruktivnuyu model' / S.I. Rotkov, V.A. Tyurina // Trudy 6-j Mezhdunar. konf. po komp. grafike i vizualizacii Grafikon-96. - S.- Peterburg, 1996. - S. 56 – 58. [In Russian]

15. Tyurina, V.A. Informacionnaya model' karkasa tryohmernogo geometricheskogo ob"ekta dlya zadachi sinteza 3D ob"ekta po ortogonal'nym proekciyam / V.A. Tyurina, S.I. Rotkov // Nachertatel'naya geometriya,        inzhenernaya i komp'yuternaya grafika: Sbornik statej. - N. Novgorod, 1999. - Vyp.4. - S. 149 – 156. [In Russian]

16. Tyurina, V.A. Razrabotka metodov preobrazovanij karkasnoj modeli v zadache sinteza obraza 3D-ob"ekta po ego proekciyam: Diss. kand. tekhn. nauk: 05.01.01 / V.A. Tyurina. – N. Novgorod, 2003. – 170 s. [In Russian]

17. GOST 2.303-68 Linii. [In Russian]

18. GOST 2.305-2008 Izobrazheniya: vidy, razrezy, secheniya. [In Russian]

19. Ore, O. Teoriya grafov / O. Ore. – M.: Nauka, 1977. [In Russian]

20. EUCLID. Technical Report. MATRA Datavision, France, 1988.–200 p.

21. Kuchuganov, V.N. Avtomaticheskij analiz mashinostroitel'nyh chertezhej / V.N. Kuchuganov. – Irkutsk: Izd-vo Irkutsk. Un-ta, 1985.–112 s. [In Russian]

22. Markowsky G. Fleshing out projections / G. Markowsky, M.A. Wesley // IBM J. Res& Develop. November, 1981. – Vol. 25, № 6. – P. 934 – 954.

23. Markowsky, G. Generation of solid models from two-dimensional and three- dimensional data / G. Markowsky, M.A. Wesley // in Pickett, MS and Boyse, J M (eds). Solid modelling by computer: from theory to application: Plenum, 1986. – P. 23 – 51.

24. Dutton, R. Efficiently Identifying the Faces of a Solid / R. Dutton, R.C. Brigham // Computers and Graphics in mechanical engineering. 1983. – Vol.7, № 2. – P. 143 – 147.

25. Tarjan, R. An Efficient Planarity Algorithm / R. Tarjan // Computer Science Department. – Report № CS – 244 – 71: Stanford University, November, 1971.

26. Ganter, M.A. From Wire-Frame to Solid Geometric: Automated Conversion of Data Representations / M.A. Ganter, J.J. Uicker // Computers in mechanical engineering. – sept. 1983. – Vol. 2, № 2. – P. 40 – 45.

27. Cobb, E.C. On the Extraction of Solid Geometry from a Wire Frame Geometric Data Base / E.C. Cobb // M.S. Thesis: University of  Wisconsin-Madison. – 1978.

28. Courter, M. Automated Conversion of Curvelinean Wire-Frame Models to Surface Boundary Models; A Topological Approach / M. Courter, J. Brewer // SIGGRAF-86. – Dallas, 18-22 aug.1986. – Vol. 20, № 4.

29. Lequette, R. Automatic construction of curvilinear solids from wire frame views / R. Lequette // France. – 1988. – Vol.20, №4. – P.171–178.