СПОСОБ КОНВЕРТАЦИИ ТРЕХМЕРНЫХ МОДЕЛЕЙ С ИСПОЛЬЗОВАНИЕМ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ Российский патент 2016 года по МПК G06T11/00 

Область техники

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

Предшествующий уровень техники

Из существующего уровня техники известны технические решения «Parameterizing а 3d modeled object for tessellation)) [Патент US №2014184599, з. 28.12.2012 г.] и «Decoupled parallel meshing in computer aided design)) [Патент US №2014039847, з. 25.06.2012 г.]. Оба технических решения описывают применение параллельной обработки трехмерных моделей для решения задач построения сеток (триангуляции). При этом оба метода указывают только один уровень иерархии в многоуровневой иерархической структуре, на котором применяют параллельные вычисления (например, уровень деталей или уровень граней), что существенно ограничивает потенциал применимости к произвольным сложным трехмерным моделям.

Наиболее близким к заявленному способу является техническое решение «Способ улучшения характеристик при обработке данных в межпроцессной цифровой модели» [Патент РФ №2444787, МПК G06T 17/00, з. 09.05.2007 г., опубл. 10.03.2012 г.].

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

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

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

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

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

Сущность изобретения

Задачей, на решение которой направлено заявляемое изобретение, является ускорение конвертации трехмерных моделей из исходного формата в конечный. Примерами подобных форматов могут служить форматы хранения трехмерных моделей, такие как STEP (семейство международных стандартов ISO 10303, утвержденных Международной организацией по стандартизации), JT (международный стандарт ISO 14306:2012), формат X3D (ISO/IEC 19775-1:2008), формат IGES (отраслевой стандарт, утвержденный Американским национальным институтом стандартов).

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

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

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

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

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

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

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

Краткое описание чертежей

Сущность изобретения поясняется рисунками:

Рис. 1 - Примеры составляющих элементов трехмерной модели: сборка (11), подсборка (12) и деталь (13).

Рис. 2 - Тело, имеющее граничное представление (B-Rep) (21) и два полигональных представления (LOD) (22) и (23). B-Rep (Boundary representation) - способ представления тела с помощью структуры данных, содержащей сведения о границах объема (вершинах, ребрах, гранях) и их соединении друг с другом [http://wap.ism-06-2.ru/shpora.php?razdel=5&id=402&]. LOD (Level Of Detail) - различные уровни детализации тела [http://www.ixbt.com/video2/terms2k5.shtml#lod];

Рис. 3 и 4 - B-Rep представление и его внутренняя структура. На рис. 3 и 4 использованы следующие обозначения:

V1, V2 - вершины;

E1, E2, E3 - ребра;

F1, F2, F3 - грани.

Рис. 5 и 6 - Полигональное представление и его внутренняя структура. На рис. 5 и 6 использованы следующие обозначения:

ГП1, ГП2, ГП3 - группы полигонов.

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

Рис. 8 Блок-схема процесса конвертации.

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

Д1, Д2, Дn - детали

Т11, Т12, Т1n, Т21, Т22, Т2n - тела

Прочие обозначения на рис.9 соответствуют обозначениям на рис.3-6.

Подробное описание изобретения

Под элементом трехмерной модели понимают любую ее составляющую часть. Например, корневыми составляющими частями (элементами) трехмерной модели могут являться сборки либо детали. Элементами сборок являются подсборки (Рис. 7), т.е. вложенные сборки, либо детали. Уровень вложенности сборок может быть произвольным. При этом детали и/или подсборки могут повторяться многократно в старших подсборках (т.е. образуя полиерархию элементов). Элементами деталей являются тела. В большинстве случаев деталь состоит из одного тела, однако некоторые форматы трехмерных моделей допускают использование нескольких тел в рамках одной детали. Элементами тел являются виды представлений. Такими видами представлений могут быть граничное представление (B-Rep), полигональное представление (LOD) (Рис.2). Элементами граничного представления (Рис.3 и 4) могут являться грани, ребра, вершины. Элементы граничного представления упорядочены по иерархическому принципу (Рис.4), где старшие элементы состоят из младших элементов. Например, каждая грань в рамках граничного представления состоит из ребер, а каждое ребро состоит из вершин. В зависимости от исходного формата трехмерной модели иерархический принцип может применяться и к другим элементам граничного представления, таким как поверхности и кривые. Элементами полигонального представления (Рис.5 и 6) могут являться группы полигонов.

Последовательность действий, применяемых в заявленном способе, изображена на Рис. 8. Сначала иерархическую многоуровневую структуру трехмерной модели (Рис. 7) в исходном формате преобразуют посредством группировки элементов, начиная от корневого уровня структуры и заканчивая уровнем деталей. В результате такой группировки формируют массив деталей (91) (см. Рис 9.). Если трехмерная модель представляет собой одну деталь, тогда массив (91) формируют из одной данной детали. Массив деталей соответствует уровню деталей (1) на Рис. 7 иерархической структуры трехмерной модели. К массиву деталей (91) применяют параллельную обработку.

Для каждой детали из массива (91) формируют массив тел, составляющих данную деталь. В случае одного тела в рамках детали массив формируют из одного тела. Таким образом, формируют массивы тел (92) (см. Рис 9). Массивы тел соответствуют уровню (2) на Рис. 7 иерархической структуры трехмерной модели. К массиву тел (92) применяют параллельную обработку.

Для каждого тела из массива (92) формируют массив представлений, составляющих данное тело. В случае одного представления в рамках тела массив формируют из одного представления. Таким образом формируют массивы представлений (93) (см. Рис.9). Массивы представлений соответствуют уровню (3) на Рис. 7 иерархической структуры трехмерной модели. К массиву представлений (93) применяют параллельную обработку.

Количество уровней иерархической структуры и соответственно содержание массивов элементов, формируемых на каждом уровне, зависит от конкретной трехмерной модели.

Из каждого массива представлений (93) как минимум для одного вида представления (B-Rep, LOD) создают набор массивов элементов, составляющих данное представление и выстроенных по иерархическому принципу. Например, для граничного (B-Rep) представления создают набор массивов (94) из массивов вершин (94A), массивов ребер (94B), массивов граней (94C), составляющих данное граничное представление (Рис.9). Массивы данных элементов формируют для каждого тела отдельно, то есть формирования массивов элементов, включающих грани двух и более тел, вершины двух и более тел и т.д., не происходит. Количество и содержание этих массивов зависит от конкретной трехмерной модели.

Для каждого полигонального представления (LOD) также формируют массивы элементов (95) (Рис 9). Такими массивами могут являться, например, массивы групп полигонов (чаще всего треугольников), где каждая группа соответствует грани граничного представления (B-Rep) данного тела. Количество и содержание этих массивов зависит от конкретной трехмерной модели.

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

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

Для более эффективной реализации «вложенного параллелизма» заявленный способ предусматривает реализацию концепции «воровства задач». Концепция «воровства задач» заключается в том, что каждое вычислительное устройство при завершении обработки своих имеющихся элементов пытается найти другие необработанные элементы. При этом может происходить отбирание («воровство») элементов у другого вычислительного устройства, над которыми оно уже начало работать. В заявленном способе реализация данной концепции состоит в том, что при обработке любого массива (деталей, тел, элементов B-Rep представления и т.д.) каждое работающее вычислительное устройство (ВУ) сначала разбивает массив на части (подмассивы) и после этого приступает к обработке сформированных подмассивов. За время, пока работает ВУ 1, другое ВУ 2 может закончить обработку собственных сформированных массивов элементов. ВУ 2, обнаружив, что у него не осталось собственных сформированных подмассивов, может приступить к обработке какого-то подмассива, который был сформирован ВУ 1. В это время ВУ 3 также может закончить обработку своих массивов и начать поиск массивов элементов, еще не обработанных другими ВУ. Не найдя свободных сформированных подмассивов, ВУ 3, например, может разделить какой-то существующий подмассив, уже обрабатываемый, например, ВУ 1, на два подмассива и начать обрабатывать свой подмассив и т.д.

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

Реализация этой концепции обусловлена дисбалансом параллельных вычислений между вычислительными устройствами. Трехмерная модель, как правило, состоит из тел разной сложности. Например, тело 1 может состоять из 10 граней, а тело 2 - из 10000 граней. Соответственно для обработки тела 1 может потребоваться значительно меньше вычислительных операций, чем для тела 2. Граничное представление, как правило, состоит из геометрических элементов разных типов, например из плоскостей, цилиндрических, сферических и других элементарных поверхностей, Б-сплайн поверхностей, поверхностей вращения и т.д. Обработка каждого типа поверхностей требует значительно отличающихся объемов вычислительных операций. Например, расчет проекции точки на плоскость требует количества операций на несколько порядков меньше, чем расчет проекции на Б-сплайн поверхность. Таким образом, параллельная обработка трехмерной модели может быть сопряжена со значительным дисбалансом требуемых вычислений и, как следствие, простаиванием одного или более вычислительных устройств. Реализация в заявленном способе концепции «воровства задач» значительно уменьшает негативное влияние этой проблемы.

В заявленном способе элементы могут быть обработаны по меньшей мере двумя вычислительными устройствами

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

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

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

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

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