Поиск соседних ячеек в неструктурированой сетке

[Andreiwse 0]

Здравствуйте!
 

Пользуюсь сеткой в формате .NEU - габитовский формат. Данный формат как и другие мне известные имеет следующую структуру:

Матрица точек
номер точки1 - координаты точки1 
.

.
номер точкиN - координаты точкиN
 

 

Матрица ячеек 
номер ячейки1 - номера точек из которых состоит ячейка1

.

.
номер ячейкиМ - номера точек из которых состоит ячейкаМ
где N- кол-во точек, M - кол-во ячеек.  

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

Вопрос1  Есть ли способы ускорение расчета нужной мне информации?
Вопрос2  Есть ли форматы сеток в которых эта информация есть в явном виде?

 

[piden 2 874]

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

[Blurp 1 678]

@Andreiwse, у вас исходные данные - что-то типа, как в этой теме?

[Andreiwse 0]

@Andreiwse, у вас исходные данные - что-то типа, как в этой теме?

вот пример файла.

NEU.txt

[piden 2 874]

Мне нужна следующая информация: для каждой ячейки знать номера ячеек с которыми она контактирует

Для чего?

[Blurp 1 678]

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую.

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

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

[Andreiwse 0]

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

Да, я делаю свой решатель. 

За ссылку спасибо, в есть кое что полезное. 

 

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую.

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

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

Не стоит Ваше время на реализацию поиска соседей используя данный формат. 

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

 

 

 

 

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

 

[piden 2 874]

В каких сеточных форматах есть именно то, что мне нужно в готовом виде

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

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Изменено 30 октября 2015 пользователем piden

[Andreiwse 0]

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

Формат который мне нужен, я сам получаю из формата .NEU,  - то есть у меня есть понимание что мне  нужно. Но это мне не помогает. 

Если ВЫ знаете другие форматы, пишите в лоб как есть, 

[piden 2 874]

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Изменено 30 октября 2015 пользователем piden

[Andreiwse 0]

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Да, я попробовал все форматы из Poinwise, я ничего не нашел.

Мне нужно что бы для тетраэдральной сетки была следующая матрица:

1   23 44 67 89

2   34  7  99 55

3  12  14 33 45

.

.

Где первая колонка это номера ячеек, четыре остальные колонки это номера соседних ячеек для данной ячейки. Например, ячейка 1 контактирует с ячейками 23 44 67 89. 

[Blurp 1 678]

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

[Andreiwse 0]

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

Контакт в моем случае это фейсом, и поэтому для каждой тетраидальной ячейки может быть только 4 соседа, если эта ячейка не является граничной. 

[luka 1]

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

[Blurp 1 678]

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком.

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик

Изменено 31 октября 2015 пользователем Blurp

[Andreiwse 0]

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком.

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик

[

Есть ограничения, я могу пользоваться только своим кодом.

благодарю Вас за попытку помочь.  

[Blurp 1 678]

Есть ограничения, я могу пользоваться только своим кодом.

Понимаю.

Ответно благодарю вас за то, что заставили пошевелить мозгами. Хоть задачу не решил, но залез в такие дебри....вплоть до попыток прикрутить для решения MySQL сервер, либо файловую БД SQLite Но, увы, в SQL запросах не силен 

А так, на всякий случай, если заинтересуетесь, то SQLite халявна. 

[Blurp 1 678]

В принципе и TetGen фриварный. И, по идее, функцию поиска соседей оттуда можно утянуть.
А так, нашел еще тут в PDFке одной упоминание про какой-то генератор Pyramid и что якобы он информацию о соседях пишет в аутпут-файло, но более про этот генератор ничего не раскопал.
 

[HFL 34]

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

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

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

Изменено 2 ноября 2015 пользователем HFL

[Andreiwse 0]

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

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

Если я правильно понял. И у Вас и у меня по сути реализован конвертор формата из стандартного (unv, neu) в свой формат. Я тоже это делаю один раз для одной сетки. 

У меня без паралелеливания 400 тыс ячеек считает за 4 часа. А у Вас во сколько раз паралеливание дало выигрыш?

 

Изменено 2 ноября 2015 пользователем Andreiwse