Разделение триангулированной многосвязной области на подобласти без ветвления внутренних границ
И.Р. Кадыров, С.П. Копысов, А.К. Новиков
Удмуртский федеральный исследовательский центр УрО РАН , г. Ижевск, 426067, Россия
Аннотация
В работе рассмотрены два подхода к разделению триагулированной многосвязной области на связные подобласти без ветвления внутренних границ.
Предложен модифицированный алгоритм построения графа Риба для определения топологии триангулированной поверхности трехмерной области. На основе разделения графа Риба выполняется формирование подобластей триангуляции без ветвления внутренних границ.
В основе другого подхода лежит формирование упорядоченного множества слоев – подмножеств 3-симплексов триангуляции, использующих ее топологические свойства, такие как связность по вершинам и граням. По построению слои не содержат ветвлений внутренних границ. Вместе с тем, для многосвязных расчетных областей характерно получение несвязных слоев. Разработан алгоритм объединения слоев в связные подобласти триангуляции на основе графа подслоев, вершины которого соответствуют связным компонентам дуального графа каждого слоя. Таким образом, объединение слоев сводится к объединению вершин и ребер графа подслоев – задаче много меньшей размерности, отображению разделения графа подслоев на триангуляцию.
Для предложенных алгоритмов проведено сравнение при разделении триангулированных многосвязных областей, имеющих поверхности разного типа и рода. Приведены оценки сложности алгоритмов и проведено сравнение качества разделения по числу 2-симплексов, общих для полученных подобластей триангуляции.
Ключевые слова: неструктурированная сетка, многосвязная область, определение топологии, граф Риба, граф связности слоев, триангуляция, разделение сетки без ветвления
Благодарности. Работа выполнена при частичной финансовой поддержке РФФИ (проекты № 16-01-00129-a, 17-01-00402-a).
Литература
1. Korneev V., Langer U. Domain decomposition methods and preconditioning // Encyclopedia of Computational Mechanics. – Wiley-Blackwell, 2004, – P. 617–647.
2. Копысов С.П., Кузьмин И.М., Недожогин Н.С., Новиков А.К. Параллельные алгоритмы формирования и решения системы дополнения Шура на графических ускорителях // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2012. – Т. 154, кн. 3. – С. 202–215.
3. Мартыненко С.И. Формализация вычислений при численном решении краевых задач // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2008. – Т. 150, кн. 1. – C. 76–90.
4. Lei Y., Baojun L., Zhangquan L., Wenbin H., Ping H. Finite element mesh deformation with the skeleton-section template // Comput.-Aided Des. – 2016. – V. 43. – P. 11–25. – doi: 10.1016/j.cad.2015.11.002.
5. Kopysov S.P., Kuzmin I.M., Novikov A.K., Nedozhogin N.S., Tonkov L.E. Radial basis function for parallel mesh-to-mesh interpolation in solving fluid-structure interaction problem // Izv. Inst. Mat. Inform. Udmurt. Gos. Univ. – 2018. – V. 51. – P. 42–50.
6. Копысов С.П., Новиков А.К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Матем. моделирование. – 2002. – Т. 14, № 9. – С. 91–96.
7. Якобовский М.В. Инкрементный алгоритм декомпозиции графов // Вестн. Нижегор. ун-та им.Н.И. Лобачевского. Сер. Матем. моделирование и оптимальное управление. – 2005. – № 1. – С. 243–250.
8. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // J. Parallel Distrib. Comput. – 1998. – V. 48. – P. 96–129.
9. Новиков А.К., Копысов С.П., Пиминова Н. К. Послойное разделение конечно-элементных сеток для мультиядерных архитектур // Суперкомпьютерные дни в России: Труды Междунар. конф. – М.: Изд-во Моск. ун-та, 2016. – С. 493–504.
10. Au O.K.-C., Tai C.-L., Chu H.-K., Cohen-Or D., Lee T.-Y. Skeleton extraction by mesh contraction // ACM Trans. Graph. – 2008. – V. 27, No 3. – Art. 44, P. 1–10.
11. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. – М.: Физматлит, 2009. – 288 с.
12. Зимовнов А.В., Местецкий Л.М. Построение криволинейного скелета трехмерной модели по плоским проекциям // Вестн. ТвГУ. Сер. Прикл. матем. – 2016. – № 3. – С. 67–83.
13. Иванов А.О., Тужилин А.А., Фоменко А. Т. Компьютерное моделирование кривых и поверхностей // Фундамент. и прикл. матем. – 2009. – Т. 15, № 5. – C. 63–94.
14. Berretti S., Bimbo A.D., Pala P. 3D Mesh decomposition using Reeb graphs // Image Vision Comput. – 2009. – V. 27, No 10. – P. 1540– 1554. – doi: 10.1016/j.imavis.2009.02.004.
15. Постников М.М. Введение в теорию Морса. – М.: Наука, 1971. – 568 с.
16. Hajij M., Dey T., Li Х. Segmenting a surface mesh into pants using Morse theory // Graphical Models. – 2016. – V. 88. – P. 12–21. – doi: 10.1016/j.gmod.2016.09.003.
17. Lupescu A. Note on an algorithm for computing the Reeb graph // Int. J. Geom. – 2017. – V. 6, No 1. – P. 89–94.
18. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 c.
19. Harvey W., Wang Y., Wenger R. A Randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes // Proc. Twenty-sixth Annual Symposium on Computational Geometry (SoCG '10). – N. Y.: АСМ, 2010. – P. 267–276.
Поступила в редакцию
13.03.18
Кадыров Ильяс Ринатович, инженер-программист
Удмуртский федеральный исследовательский центр УрО РАН (УдмФИЦ УрО РАН)
ул. Т. Барамзиной, д. 34, г. Ижевск, 426067, Россия
E-mail: slasheeck@gmail.com
Копысов Сергей Петрович, доктор физико-математических наук, главный научный сотрудник
Удмуртский федеральный исследовательский центр УрО РАН (УдмФИЦ УрО РАН)
ул. Т. Барамзиной, д. 34, г. Ижевск, 426067, Россия
E-mail: s.kopysov@gmail.com
Новиков Александр Константинович, кандидат физико-математических наук, старший научный сотрудник
Удмуртский федеральный исследовательский центр УрО РАН (УдмФИЦ УрО РАН)
ул. Т. Барамзиной, д. 34, г. Ижевск, 426067, Россия
E-mail: alexander.k.novikov@gmail.com
Для цитирования: Кадыров И.Р., Копысов С.П., Новиков А.К. Разделение триангулированной многосвязной области на подобласти без ветвления внутренних границ // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2018. – Т. 160, кн. 3. – С. 544–560.
For citation: Kadyrov I.R., Kopysov S.P., Novikov А.К. Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 3, pp. 544–560. (In Russian)
Контент доступен под лицензией Creative Commons Attribution 4.0 License.
