С начала кратко, о чём будет пост: о построение тетраэдальных сеток (сеток, элементы которых - тетраэдры), получение этих сеток из сеток на треугольных призмах и параллелепипедальных сеток (далее буду называть их кубическими - это короче и проще выговаривать и читать).
Теперь то, что привело меня к этому: для курсового проекта требовалось строить тетраэдальные сетки, причём большие (в итоге получилось 132651 узлов и 750000 тетраэдров), что руками делать не очень быстро. Есть различные методы построения, но я выбрал достаточно простой (форма области была не важна) - строится кубическая сетка, затем она разбивается на тетраэдры. И столкнулся с некоторыми проблемами - так, как я сначала разбивал сетку - она получала не комфорной, ну и первом делом я полез в гугл и, что самое печально я не нашёл того, чего искал. Возможно я конечно плохо искал, но всё равно. Поэтому путь это будет хотя бы тут.
Ну чтож, а теперь начнём с краткого обзора алгоритмов построения тетраэдальных сеток(и соответсвено треугольных, если смотреть двухмерное разбиение).
1. Алгоритм исчерпывания
Выходные данные: граничный фронт (множество треугольников - разбиение границы области)
Принцип работы алгоритма достаточно простой и понятный, берём треугольник из фронта, откладываем по нормали к нему точку на определённую длину, если нет пересечений с тетраэдрами то добавляем тетраэдр в разбиение, если есть пытаемся модифицировать его(переносим точку) и добавляем в разбиение. Исходный треугольник удаляем из фронта, полученные(из тетраэдра) добавляем в него. Заканчиваем когда больше не можем строить тетраэдры.
Плюсы и минусы: явным минусом является необходимость начального фронта - его тоже ещё надо построить, а так же нахождение оптимальной для задачи стратегии выбора шага по нормали и модификации тетраэдров. Плюсам является то, что не важна геометрия области.
2. Простой фронтальный метод
Это не название а разновидность метода. Алгоритм исчерпывания тоже является фронтальным методом, однако у них есть значительное отличие.
Входные данные: граничный фронт и внутренние узлы
Принцип работы алгоритма ещё проще, чем в предыдущем: берём треугольник из фронта, добавляем к нему узел и получаем тетраэдр. Новые треугольники идут в фронт.
Плюсы и минусы: опять-таки входные данные, но тут их ещё больше требуется - кроме фронта нам нужны ещё внутренние точки. Плюсом является то, что с помощью данного алгоритма можно построить сетку, с определёнными особенностями, например тетраэдры вытянутые по оси z.
3. С помощью вложенных сеток
Входные данные: тетраэдальная сетка(возможно - один тетраэдр)
Принцип работы алгоритма: к исходной сетки строится вложенная(возможно несколько раз)
Плюсы и минусы: тут тоже исходные данные, если в предыдущих методах нам нужно было только разбиение границы, то здесь всей области. Ещё большим минусом является то, что если мы ходим построить сетку из большого числа тетраэдров она получится очень мелкой.
4. Построение из кубической сетки или сетки на треугольных призмах
Выходные данные: кубическая сетка или сетка на треугольных призмах
Принцип работы алгоритма: всё просто и понятно разбиваем исходные элементы на тетраэдры так, чтобы получилась комфорная сетка.
Плюсы и минусы: требование таких сеток большим минусом не является, особенно для кубической сетки - её строить легко, поэтому здесь метод даже выигрывает. Главным минусом является минус исходных сеток, по сравнению и "чисто тетраэдальными" сетками - тетраэдрами можно хорошо аппроксимировать более геометрически сложные области, чем параллелипипедами или призмами.
Конечно это далеко не все алгоритмы. Плюс есть алгоритмы, позволяющие улучшить качество тетраэдальных сеток, но их я рассматривать не буду. Перейду сразу к тому: как правильно разбить треугольную призму на тетраэдры, а потом как разбить куб.
Пусть есть вот такая призма(не все невидимые линии правильно показаны, точнее показа правильно только одна из трёх, но не суть).
Из неё получаются следующие три тетраэдра: (2, 4, 5, 6), (1, 2, 3, 6) и (1, 2, 4, 6).
Теперь перейдём к параллелепипедам: по суть мы разбиваем один параллелепипед на две призмы, а эти призмы на тетраэдры. Главная проблема - это правильная локальная нумерация призм друг по отношению к другу. Возьмём эту призму и добавим к ней ещё два узла, тем самым получим парллелепипед:
На кривости рисунка из-за копипаста обращать внимание не будем. Если взять симметричную нумерацию(7->2, 8->5), как с делал изначально сетка получится не комфорная, что в некоторых(даже думаю в большинстве) случаев будет проблемой. Правильно же локальную нумерацию во второй(левой) призме ввести следующим образом(глоб. -> лок.): 3 -> 1, 1 -> 2, 7 -> 3, 6 -> 4, 4 -> 5, 8 -> 6. И тогда, используя предыдущее разбиение мы получим наши заветные 6 тетраэдров: (2, 4, 5, 6), (1, 2, 3, 6), (1, 2, 4, 6), (1, 6, 4, 8), (3, 1, 7 8) и (3, 1, 6, 8).
Саму сетку мы разбили, однако осталось ещё одна проблема - разбиение границ. Об этом расскажу в следующий раз, а то пост и так получился каким-то длинным.
Теперь то, что привело меня к этому: для курсового проекта требовалось строить тетраэдальные сетки, причём большие (в итоге получилось 132651 узлов и 750000 тетраэдров), что руками делать не очень быстро. Есть различные методы построения, но я выбрал достаточно простой (форма области была не важна) - строится кубическая сетка, затем она разбивается на тетраэдры. И столкнулся с некоторыми проблемами - так, как я сначала разбивал сетку - она получала не комфорной, ну и первом делом я полез в гугл и, что самое печально я не нашёл того, чего искал. Возможно я конечно плохо искал, но всё равно. Поэтому путь это будет хотя бы тут.
Ну чтож, а теперь начнём с краткого обзора алгоритмов построения тетраэдальных сеток(и соответсвено треугольных, если смотреть двухмерное разбиение).
1. Алгоритм исчерпывания
Выходные данные: граничный фронт (множество треугольников - разбиение границы области)
Принцип работы алгоритма достаточно простой и понятный, берём треугольник из фронта, откладываем по нормали к нему точку на определённую длину, если нет пересечений с тетраэдрами то добавляем тетраэдр в разбиение, если есть пытаемся модифицировать его(переносим точку) и добавляем в разбиение. Исходный треугольник удаляем из фронта, полученные(из тетраэдра) добавляем в него. Заканчиваем когда больше не можем строить тетраэдры.
Плюсы и минусы: явным минусом является необходимость начального фронта - его тоже ещё надо построить, а так же нахождение оптимальной для задачи стратегии выбора шага по нормали и модификации тетраэдров. Плюсам является то, что не важна геометрия области.
2. Простой фронтальный метод
Это не название а разновидность метода. Алгоритм исчерпывания тоже является фронтальным методом, однако у них есть значительное отличие.
Входные данные: граничный фронт и внутренние узлы
Принцип работы алгоритма ещё проще, чем в предыдущем: берём треугольник из фронта, добавляем к нему узел и получаем тетраэдр. Новые треугольники идут в фронт.
Плюсы и минусы: опять-таки входные данные, но тут их ещё больше требуется - кроме фронта нам нужны ещё внутренние точки. Плюсом является то, что с помощью данного алгоритма можно построить сетку, с определёнными особенностями, например тетраэдры вытянутые по оси z.
3. С помощью вложенных сеток
Входные данные: тетраэдальная сетка(возможно - один тетраэдр)
Принцип работы алгоритма: к исходной сетки строится вложенная(возможно несколько раз)
Плюсы и минусы: тут тоже исходные данные, если в предыдущих методах нам нужно было только разбиение границы, то здесь всей области. Ещё большим минусом является то, что если мы ходим построить сетку из большого числа тетраэдров она получится очень мелкой.
4. Построение из кубической сетки или сетки на треугольных призмах
Выходные данные: кубическая сетка или сетка на треугольных призмах
Принцип работы алгоритма: всё просто и понятно разбиваем исходные элементы на тетраэдры так, чтобы получилась комфорная сетка.
Плюсы и минусы: требование таких сеток большим минусом не является, особенно для кубической сетки - её строить легко, поэтому здесь метод даже выигрывает. Главным минусом является минус исходных сеток, по сравнению и "чисто тетраэдальными" сетками - тетраэдрами можно хорошо аппроксимировать более геометрически сложные области, чем параллелипипедами или призмами.
Конечно это далеко не все алгоритмы. Плюс есть алгоритмы, позволяющие улучшить качество тетраэдальных сеток, но их я рассматривать не буду. Перейду сразу к тому: как правильно разбить треугольную призму на тетраэдры, а потом как разбить куб.
Пусть есть вот такая призма(не все невидимые линии правильно показаны, точнее показа правильно только одна из трёх, но не суть).
Теперь перейдём к параллелепипедам: по суть мы разбиваем один параллелепипед на две призмы, а эти призмы на тетраэдры. Главная проблема - это правильная локальная нумерация призм друг по отношению к другу. Возьмём эту призму и добавим к ней ещё два узла, тем самым получим парллелепипед:
Саму сетку мы разбили, однако осталось ещё одна проблема - разбиение границ. Об этом расскажу в следующий раз, а то пост и так получился каким-то длинным.
Комментариев нет:
Отправить комментарий