Способ параллельной обработки трехмерных тел в b-rep представлении



Способ параллельной обработки трехмерных тел в b-rep представлении
Способ параллельной обработки трехмерных тел в b-rep представлении
Способ параллельной обработки трехмерных тел в b-rep представлении
Способ параллельной обработки трехмерных тел в b-rep представлении

Владельцы патента RU 2597480:

Общество с ограниченной ответственностью "КАДЭКС" (RU)

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

 

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

Настоящее изобретение относится к области обработки трехмерных тел в B-Rep представлении, а именно обработке трехмерных тел с использованием параллельных вычислений.

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

Из существующего уровня техники известны технические решения «Parameterizing a 3d modeled object for tessellation» [Заявка на патент № US2014184599, з. 28.12.2012 г.] и «Tessellation of a Parameterized 3D Modeled Object», заявка на патент № US2014184598, з. 28.12.2012 г.]. Оба технических решения описывают способы обработки трехмерных моделей для решения задач построения сеток (триангуляции).

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

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

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

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

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

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

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

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

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

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

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

Рис. 1 - Тело, имеющее B-Rep представление (11). B-Rep (Boundary representation) - способ представления тела с помощью структуры данных, содержащей сведения о границах объема (вершинах, ребрах, гранях) и их соединении друг с другом [http://wap.ism-06-2.ru/shpora.php?razdel=5&id=402&].

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

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

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

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

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

0, 1, …, 7 - вершины;

F0, F1,…, F5 - грани.

Рис. 5 и 6 - графы зависимостей граней тела, изображенного на рис. 4, полный и оптимизированный.

Рис.7 - пример фрагмента сложного графа зависимостей граней тела.

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

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

В качестве примера тела, иллюстрирующего применение способа, выбран прямоугольный параллелепипед (см. Рис. 4). Для тела в B-Rep представлении (Рис. 4) создаем набор элементов, составляющих данное представление и выстроенных по иерархическому принципу. Например, для тела в B-Rep представлении (Рис. 4) создаем массив вершин (V0-V7), массив граней (F0-F5), составляющих данное B-Rep представление (Рис. 4). Количество и содержание этих массивов зависит от конкретного трехмерного тела.

Затем одновременно создаем 2 таблицы:

1. Таблицу, содержащую номера всех граней и номера принадлежащих ей вершин (см. Табл. 1);

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

F0 V0 V1 V2 V3
F1 V4 V1 V5 V2
F2 V6 V5 V3 V2
F3 V7 V0 V4 V1
F4 V7 V6 V0 V3
F5 V7 V6 V5 V4

Табл.1. Соответствие грани и номеров принадлежащих ей вершин

V0 F0 F3 F4
V1 F0 F1 F3
V2 F0 F1 F2
V3 F0 F2 F4
V4 F1 F3 F5
V5 F1 F2 F5
V6 F2 F4 F5
V7 F3 F4 F5

Табл.2. Соответствие вершины и номеров граней, к которым принадлежит данная вершина

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

F0 F4 F3 F2 F1
F1 F5 F3 F2
F2 F5 F4
F3 F5 F4
F4 F5
F5  

Табл.3. Таблица зависимостей между гранями

Далее для тела в B-Rep представлении формируем граф зависимостей граней, в котором ребра обозначают отношение зависимости «предшествующая» - «последующая» грань. На Рис.5 хорошо видно, что такой граф содержит избыточные ребра, например, между гранями F0 и F4 существуют три пути, соединяющих их: F0-F2-F4, F0-F3-F4 и F0-F4. Это обусловлено тем, что некоторые грани одновременно связаны с несколькими «предшествующими» гранями. Эта избыточность может увеличить время обработки тела, т.к. потребуются дополнительные проверки условия того, что все «предшествующие» грани были обработаны до начала обработки каждой «последующей» грани. Соответственно для того, чтобы ускорить процесс обработки, можно оптимизировать граф, то есть сократить зависимость грани от «предшествующих» ей граней до минимума. Оптимизируем граф, исключая для каждой грани те «предшествующие» грани, которые являются «предшествующими» для других «предшествующих» граней (см. Табл.4).

F0 F1
F1 F3 F2
F2 F4
F3 F4
F4 F5
F5  

Табл.4. Таблица зависимостей между гранями

В примере выше, для F4 исключаем F0 как «предшествующую», т.к. F0 является «предшествующей» для F2 и F3, которые сами являются «предшествующими» к F4. На основании таблицы формируем оптимизированный граф (Рис. 6). После чего начинаем обработку в соответствии с оптимизированным графом. После завершения обработки F1 и при переходе к обработке «последующих» граней F2 и F3 (Рис. 6) возникает возможность применения параллельных вычислений в силу независимости обработки F2 и F3 друг от друга. Для повышения эффективности параллельных вычислений может быть использован способ, называемый «воровством задач» (от англ. “work stealing”).

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

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

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

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



 

Похожие патенты:

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

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

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

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

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

Изобретение относится к области геофизики и может быть использовано для моделирования пласта-коллектора. Описывается способ моделирования месторождения.

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

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

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

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

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

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

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

Изобретение относится к средствам идентификации и выбора слоев флюида и флюидонасыщенных пластов из одного или более массивов, представляющих геологическую структуру. Предложен способ идентификации и выбора слоев флюида и флюидонасыщенных пластов в одном или более массивах, представляющих геологическую структуру, включающий: а) загрузку множества массивов, причем каждый массив содержит верхний участок, центр масс и объем; b) присвоение метки межфлюидного контакта каждому соответствующему массиву, причем каждая метка межфлюидного контакта обозначается как пустая; c) выбор метки межфлюидного контакта, которая назначается одному из множества массивов с верхним участком, являющимся межфлюидным контактом; d) перевод выбранной пустой метки межфлюидного контакта в межфлюидный контакт, представляющий главный межфлюидный контакт помеченного массива; е) выбор каждого массива из множества массивов, которое является одним из массивов в том же тектоническом блоке и в том же стратиграфическом слое, что и главный межфлюидный контакт помеченного массива; f) идентификацию каждого массива, выбранного как один из подобных в том же тектоническом блоке и в том же стратиграфическом слое, что и главный межфлюидный контакт помеченного массива, являющийся продолжением главного межфлюидного контакта помеченного массива; g) повторение шагов c) - f) для каждой метки межфлюидного контакта, присвоенной одному из множества массивов с верхним участком, являющимся межфлюидным контактом; и h) выделение каждого главного межфлюидного контакта и каждого помеченного массива, идентифицированного как соответствующее продолжение главного межфлюидного контакта помеченного массива из множества массивов в группе массивов слоев флюида. Предложено также энергонезависимое устройство-носитель программы, содержащее команды, выполняемые компьютером для реализации указанногоспособа. 3 н. и 17 з.п. ф-лы, 35 ил.

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

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

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

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

Изобретение относится к области обработки данных. Технический результат - повышение точности определения городских объектов при построении моделей городских объектов, на основе данных лазерного сканирования и фотографических данных. Способ распознавания городских объектов заключается в обработке первичных данных, содержащих фотографические данные и данные лазерного сканирования, представляющие собой облако точек, и содержит этапы, на которых: выполняют очистку полученных данных лазерного сканирования и проверку полученных первичных фотографических данных; выполняют предварительную обработку очищенных данных лазерного сканирования, при которой: осуществляется построение нормалей к каждой из точек облака точек; осуществляется построение плоскостей для совокупностей точек облака точек; осуществляется построение рельефа местности по построенным нормалям и плоскостям с помощью фотограмметрических алгоритмов на основе фотографических данных; выполняют последовательное распознавание статичных городских объектов из набора очищенных данных лазерного сканирования и фотографических данных; и осуществляют построение полигональной модели каждого из обнаруженных объектов. 2 н. и 18 з.п. ф-лы, 8 ил.
© Патентный поиск, поиск патентов на изобретения - FindPatent.RU 2012-2024
Политика конфиденциальности 2016-09-10 2016-09-11T22:54:51
Наверх