Метод и инструментальные средства автоматизации управления характеристиками структур данных полигональных 3D-моделей

А.В. Балабанов,
с.н.с., к.т.н., fca07@mail.ru,

ИПУ РАН, г. Москва

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

A method and software-based tools are developed to automatize the controlling of characteristics of polygonal 3D-models data structure. The method is based on dividing original 3D-model in structure classes, systematizing these classes in terms of both complexity and precision of representing the graphics data by means of the data structure network models, performing the operations of merging the objects of the structure classes, and transforming their characteristics in order to synthesize the 3D-model data structure within required algorithmic and geometric precision. The developed tools include algorithms and their program implementations for performing the decomposition of polygonal 3D-models, using the criteria of equivalence of forms and the sizes of finite elements, and posteriorly reducing the geometric and the algorithmic complexity.

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

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

Разработанный метод основан на работах автора, посвященных построению 3D-моделей объектов по различным наборам входных данных [1 – 3] и исследованиям в области синтеза структур интерактивных систем объемного геометрического моделирования [4 – 6]. Метод заключается в декомпозиции исходной полигональной 3D-модели на объекты структурных классов, систематизации полученного множества объектов при помощи сетевых моделей структур данных и выполнении на основе сетей операций качественного и количественного преобразования множества объектов структурных классов с целью получения 3D-моделей с требуемой геометрической и алгоритмической сложностью.

Введем определение структурного класса для полигональных 3D-моделей. Структурным классом называется множество (S={s}) связных частей таблицы описания полигональной 3D-модели с одинаковыми (или принадлежащими заданному диапазону) значениями характеристик конечных элементов, таких как множество узлов (N), множество связей между узлами (R) и множество полных отклонений узлов (D), которые вычисляются как сумма их действительного (Dact) и потенциального (Dp) отклонений от геометрической формы теоретического эталона 3D-модели. Элемент sÎS называется объектом структурного класса. Математическая запись определения структурного класса приведена в (1).

(1)

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

(2)

С целью оценки сложности исходной полигональной 3D-модели, генерации множества альтернативных вариантов ее построения и выбора оптимального варианта, полученное множество объектов структурных классов необходимо систематизировать в виде сетевой модели структуры данных, как показано на рис. 1. Полюсы сети соответствуют формам внешнего представления структуры данных полигональной 3D-модели на входе и выходе задачи управления ее характеристиками. Остальными вершинами являются объекты структурных классов, полученные в результате декомпозиции исходной полигональной 3D-модели и представленные в сети с разной алгоритмической сложностью и геометрической точностью [4]. По оси X изменяется точность объектов структурных классов, по оси Z – сложность объектов структурных классов, по оси Y изменяется тип структурных классов. На верхнем уровне сети (по оси Y) расположен класс с наибольшим количеством объектов, на нижнем уровне – с наименьшим. Объекты каждого структурного класса образуют полный ориентированный граф, множество ребер которого соответствует возможным операциям преобразования характеристик объектов – сложности и точности. Диапазон и шаг изменения сложности и точности выбираются в зависимости от решаемой задачи. В сети на рис. 1, в качестве примера, приведены три значения для сложности и точности, которым соответствуют множества из трех вершин по осям X и Z; на практике этих значений может быть значительно больше. Если при декомпозиции получено несколько объектов с одинаковыми характеристиками, такие объекты отображаются в сети одной вершиной, что соответствует выполнению операций объединения уже на стадии построения сетевой модели.

рис. 1 Сетевая модель структуры данных

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

На каждом уровне между объектами одного класса выполняются операции объединения по следующему правилу. Правило 1: Объекты объединяются попарно, при этом характеристики сложности и точности объектов приводятся к единому виду. Для получившегося в результате объединения нового объекта выбираются минимальные значения сложности и точности из числа объединяемых объектов, причем точность может быть меньше у одного из объектов, а сложность – у другого. Если минимальные значения сложности и точности не соответствуют установленным диапазонам значений для объединяемых объектов (хотя бы для одного), выполняется операция преобразования точности (сложности) и переход к соответствующей вершине сети (смещение по X и/или Z). Операции объединения проводятся до тех пор, пока в структурном классе не останется объектов, к которым можно применить Правило 1.

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

рис. 2 Декомпозиция по критерию эквивалентности формы конечных элементов

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

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

рис. 3 Пример выполнения операции декомпозиции по критерию эквивалентности формы конечных элементов и операции преобразования характеристик объектов

На рис. 3 приведен пример выполнения операции декомпозиции по критерию эквивалентности формы конечных элементов и операции преобразования точности и сложности при помощи специально разработанных программных средств. На верхнем рисунке слева изображена исходная полигональная 3D-модель в формате *.stl. На верхнем рисунке справа – результат декомпозиции. На нижнем рисунке слева показан результат выполнения операций уменьшения точности и сложности 3D-модели за счет уменьшения числа конечных элементов; в примере на рис. 3 из триангуляции удалено 1000 узлов. На нижнем рисунке справа показан результат синтеза объектов структурных классов после выполнения операций преобразования их характеристик (окружностью обозначен результат преобразования).

рис. 4 Иллюстрация алгоритма удаления узла

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

рис. 5 Декомпозиция по критерию эквивалентности размера конечных элементов

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

рис. 6 Результат обработки конечных элементов различного размера

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

рис. 7 Результат автономной обработки различных структурных классов

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

рис. 8 Пример выполнения операции декомпозиции по критерию эквивалентности размера конечных элементов и операции преобразования характеристик объектов

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

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

Литература

1. Artamonov E.I., Balabanov A.V., Romakin V.A. Structured Design of Interactive Electronic Technical Manuals Based on Virtual Reality Means / Preprints of the IFAC Conference on Manufacturing Modelling, Management and Control (MIM ’2013). Saint-Petersburg: IFAC Publication, 2013. P. 1114-1118.

2. Артамонов Е.И., Ромакин В.А., Балабанов А.В. Операции на виртуальных моделях объектов машиностроения // Материалы 36-й Междунар. конф. «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (IT+S&E*09)». – Открытое образование, 2009. – С. 70-72.

3. Артамонов Е.И., Ромакин В.А., Балабанов А.В. Программные средства виртуальной настройки роботов // Автоматизация в промышленности. 2010. № 5. С. 54-55.

4. Балабанов А. В. Синтез структур специализированных интерактивных систем на основе объемных геометрических моделей и средств виртуальной реальности // Информационные технологии в проектировании и производстве. – 2013. №3. С. 23-29.

5. Балабанов А. В. Кодирование и оценка структур данных интерактивных систем объемного геометрического моделирования // Информационные технологии в проектировании и производстве. – 2014. №2. С. 22-24.

6. Балабанов А. В. Метод разработки эффективных алгоритмов построения 3D-моделей для специализированных компьютерных систем быстрого прототипирования // Информационные технологии в проектировании и производстве. – 2015. №2. С. 41-46.