СПОСОБЫ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ПОВЕРХНОСТНЫХ ТРИАНГУЛЯЦИЙ И ТЕТРАЭДРАЛЬНЫХ СЕТОК
А.А. Данилов
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 519.63
СПОСОБЫ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ПОВЕРХНОСТНЫХ ТРИАНГУЛЯЦИЙ И ТЕТРАЭДРАЛЬНЫХ СЕТОК
А.А. Данилов
Представлен краткий обзор методов задания геометрии области и построения неструктурированных тетраэдральных сеток. Рассмотрены способы построения поверхностных треугольных сеток – аналитическое задание, взаимодействие с ядром САПР, перестроение имеющейся триангуляции, метод конструктивной блочной геометрии. Рассмотрена комбинация двух методов для построения тетраэдральной сетки внутри области. Представленный набор методов покрывает широкий спектр областей и позволяет строить сетки с заданными свойствами. Ключевые слова: тетраэдральные сетки, поверхностные триангуляции, САПР, конструктивная блочная геометрия, триангуляция Делоне, алгоритм продвигаемого фронта.
Введение
Одним из наиболее сложных этапов построения дискретной модели в компьютерном моделировании является построение расчетной сетки. Конформные треугольные и тетраэдральные неструктурированные сетки позволяют достаточно точно аппроксимировать сколь угодно сложную геометрию области. Треугольная сетка называется конформной, если любые два треугольника сетки имеют либо ровно одну общую вершину, либо ровно одно целое общее ребро, либо не имеют общих точек. В конформных тетраэдральных сетках любые две ячейки могут иметь также одну целую общую грань. Построение сетки состоит из двух этапов. Сначала строится поверхностная конформная триангуляция области. Затем внутри области строится тетраэдральная сетка, сохраняющая заданный след на границе области.
Существует два основных подхода к построению тетраэдральных сеток – методы, основанные на триангуляции Делоне, и алгоритм продвигаемого фронта. Использование триангуляции Делоне не гарантирует совпадение следа сетки на границе с заданной поверхностной триангуляцией. Для исправления сетки предлагают несколько методик: локальные перестроения сеток [1], измельчение сеток [2], накладывание ограничений на свойства триангуляции Делоне [3]. Метод продвигаемого фронта [4], напротив, сохраняет след сетки на границе области, однако может столкнуться с проблемами внутри области. Перспективным направлением видится комбинация методов Делоне и продвигаемого фронта [5].
В статье представлен краткий обзор некоторых методов построения поверхностных триангуляций, а также предложен метод построения тетраэдральной сетки внутри области на основе комбинации методов продвигаемого фронта и Делоне. В разделе 1 рассмотрены методы построения поверхностных сеток: аналитическое задание области, взаимодействие с ядром САПР, перестроение имеющихся сеток, метод конструктивной блочной геометрии. В разделе 2 кратко описан алгоритм классического продвигаемого фронта, а также метод на основе разбиения Делоне, который предложил Поль Луи Джордж [6]. В разделе 3 обсуждаются способы улучшения качества полученной сетки.
Все рассмотренные алгоритмы реализованы как библиотека программ AniAFT из пакета Ani3D [7]. Вместе с двумерной версией пакета программ Ani2D [8] оба пакета предоставляют инструменты для построения неструктурированных сеток, анизотропной адаптации сеток на основе заданной метрики, конечно-элементной дискретизации, решения систем линейных уравнений и другого. Эти пакеты свободно доступны для использования.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
87
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Способы задания поверхностной триангуляции
Обычно для построения поверхностной триангуляции всю границу области разбивают на части с общими криволинейными границами. После дискретизации криволинейных границ на поверхности может быть построена триангуляция в каждой части отдельно. Для построения триангуляции можно использовать классический двумерный алгоритм продвигаемого фронта. Так как все части поверхности имеют общую дискретизацию границ, то общая поверхностная сетка получится конформной.
В этом разделе будут рассмотрены следующие способы задания области: аналитическое задание области, взаимодействие с ядром САПР, перестроение начальной поверхностной триангуляции, методы конструктивной блочной геометрии.
С помощью аналитического задания области удобнее всего задавать простые объекты: шар, куб, цилиндр, а также многогранники с плоскими гранями. Более сложные объекты, полученные с помощью пересечения или объединения нескольких простых объектов, удобно задавать с помощью конструктивной блочной геометрии. Еще более сложные объекты, разработанные в САПР, могут быть обработаны с помощью взаимодействия с ядром САПР. Также объект может быть задан в виде поверхностной триангуляции, например, экспортирован из сторонней САПР или получен в результате трехмерного сканирования. В этих случаях может потребоваться дополнительная обработка сетки для улучшения ее качества.
Аналитическое задание области. Этот способ позволяет описывать граничную поверхность области с помощью параметризующих функций. Вся поверхность разбивается на части, каждая из которых может быть параметризована некоторой гладкой функцией. Линии пересечения частей также должны быть явно параметризованы. Этот метод задания границы удобен лишь в очень простых случаях, а также для задания объектов с плоскими гранями.
Информация об области задается как набор параметризованных гладких поверхностей с кусочно-гладкими параметризованными границами. Процесс построения начального фронта сводится к двум основным шагам. Сначала для каждой гладкой линии строится дискретизация с учетом желаемого размера элементов в сетке. Затем для каждой гладкой части поверхности формируется начальный фронт из имеющихся разбиений граничных кривых, и с помощью алгоритма продвигаемого фронта строится поверхностная триангуляция. После построения триангуляция разглаживается с учетом параметризующих функций и функции, задающей желаемый размер элементов сетки в пространстве.
Взаимодействие с САПР. Часто объекты моделируются с помощью САПР. Большинство из существующих САПР предлагают интерфейс для взаимодействия с внутренним ядром и получения информации о топологии и геометрии области. Одним из примеров такой САПР может служить открытая система Open CASCADE Technology [9]. У каждой системы САПР свой интерфейс для взаимодействия, и общих стандартов в этой области пока нет. В качестве универсального интерфейса можно использовать пакет Common Geometry Module (CGM) [10]. Этот пакет также имеет открытый код и свободен для использования. CGM предоставляет общий интерфейс к разным системам САПР (OpenCASCADE, ACIS и Pro/ENGINEER).
Создание интерфейса между генератором сеток и САПР с помощью пакета CGM является сугубо технической задачей. На рис. 1 показаны пример области, заданной в САПР OpenCASCADE, полученная поверхностная триангуляция и разрез построенной тетраэдральной сетки.
88 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Данилов
Рис. 1. Пример взаимодействия с САПР (26 248 треугольников, 72 158 тетраэдров)
Перестроение поверхностной сетки. В некоторых случаях область уже может быть задана своей поверхностной триангуляцией. Однако сетки, полученные экспортом из САПР, часто обладают тем свойством, что количество треугольников на плоских участках минимально, а сами треугольники могут иметь разный размер и очень вытянутую форму. В этом случае построение тетраэдральной сетки внутри области с сохранением заданного следа на поверхности может быть сильно затруднено или приведет к сетке с очень плохим качеством.
Для перестроения имеющейся сетки может быть использован метод, основанный на выделении почти плоских участков [11]. Пользователь задает параметры, определяющие допустимую степень отклонения выделяемых участков от плоскостей. Например, это может быть максимальный угол между нормалью треугольника и нормалью к плоскости. Очередной участок выбирается, начиная с треугольника с наибольшей площадью. Далее к нему по очереди добавляются соседние треугольники, если они не нарушают заданных пользователем критериев. После разбиения всей поверхности на почти плоские участки создается новая дискретизация границ этих участков (ломаных линий на поверхности). Далее для каждого участка его граничная дискретизация проектируется на плоскость, в плоскости строится новая триангуляция и проектируется обратно на поверхность. Так как участок поверхности является почти плоским, то искажения геометрии области будут незначительными.
а)
б)
Рис. 2. Два примера перестроения поверхностных сеток: а – экспорт из САПР, в начальной сетке 912 треугольников, в новой – 4 506 треугольников, 21 671 тетраэдр;
б – трехмерное сканирование модели, в начальной сетке 345 944 треугольников, в новой – 94 100 треугольников, 217 011 тетраэдров
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
89
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Тот же метод может быть применен и для разгрубления слишком подробной поверхностной сетки. Например, полученные с помощью трехмерного сканирования сетки обычно содержат очень много треугольников, и часто пользователю не нужна такая подробная поверхностная сетка. За счет разбиения на почти плоские участки и построения более грубой сетки на них можно получить новую поверхностную сетку с меньшим количеством треугольников.
На рис. 2 показаны два примера перестроения сеток. В первом начальная сетка была получена с помощью экспорта из САПР, а во втором – с помощью трехмерного сканирования.
Конструктивная блочная геометрия. Некоторые объекты довольно сложно задать с помощью аналитического представления, и в то же время они достаточно просты, чтобы моделировать их в сложных САПР. Важными примерами таких объектов являются пересечения и объединения простых объектов (примитивов), таких как шар, куб, цилиндр. Такой способ задания объектов принято называть конструктивной блочной геометрией [12].
Для простых примитивов поверхностная сетка строится с помощью аналитического задания области. Далее поверхностные сетки двух примитивов пересекаются, и на их основе строится новая поверхностная сетка для объединения, пересечения или разности двух примитивов. Новый объект, в свою очередь, тоже можно рассматривать как новый примитив. Общая идея пересечения поверхностных сеток состоит в следующем. Сначала строится ломаная линия пересечения поверхностных сеток, разбивающая треугольники в сетках на несколько связных частей. Далее полоску треугольников вдоль линии пересечения перестраивают заново для конформного соединения нужных частей поверхности. На рис. 3 показаны примеры поверхностных сеток для разных объектов.
Рис. 3. Примеры сеток для областей, заданных с помощью конструктивной блочной геометрии
Тетраэдральный генератор сеток. После того, как поверхностная сетка построена, можно приступать к построению тетраэдральной сетки внутри области. В этой статье предлагается комбинация двух методов. Первый метод – классический алгоритм продвигаемого фронта. Он срабатывает не всегда и может оставить после работы часть еще не разбитой на тетраэдры области. Для разбиения этих проблемных участков применяется второй метод, основанный на триангуляции Делоне.
Алгоритм продвигаемого фронта используется для построения тетраэдральной сетки внутри заданной ограниченной области. Область задается поверхностной ориентированной конформной триангуляцией, называемой фронтом. После этого шаг за шагом строятся тетраэдры на границе фронта с продвижением его внутрь области. В каждый момент времени текущий фронт отделяет часть с построенной тетраэдральной сеткой от еще не рассмотренной части. Если в конце фронт окажется пустым, то тетраэдральная сетка будет построена для всей области. Если во фронте остаются треугольники, но ни один новый тетраэдр построить не удается, то алгоритм останавливается, и применяется второй метод, описанный в следующем подразделе.
90 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Данилов
На каждом шаге из фронта выбирается треугольник с наибольшей площадью, и на нем как на основании строится тетраэдр с учетом желаемого размера элементов сетки. После этого тетраэдр проверяется на пересечения с фронтом. В случае пересечений подбирается другой тетраэдр. Новый тетраэдр добавляется в сетку, а фронт продвигается внутрь области.
Метод позволяет строить сетки в сложных геометрических областях, в том числе анизотропных и имеющих разрезы (рис. 4). Также метод позволяет контролировать желаемый размер элементов сетки и может выбирать его автоматически (рис. 5).
Рис. 4. Пример анизотропной области. Слева область растянута по оси Z в 50 раз. В центре и справа показаны разрезы тетраэдральной сетки плоскостями OXZ и OXY
Рис. 5. Квазиравномерный, пользовательский и автоматический выбор шага сетки
Метод на основе разбиения Делоне применяется после алгоритма продвигаемого фронта, когда бóльшая часть сетки уже построена. Здесь представлена только общая идея метода, предложенного П. Л. Джорджем [6]. Сначала для выпуклой оболочки множества вершин фронта строится тетраэдральное разбиение Делоне. Далее нужный фронт пересекается с полученной сеткой, измельчая ее. После этого из сетки выкидываются тетраэдры, лежащие за пределами области. Новая сетка не будет совпадать с заданным фронтом на границе. Для восстановления конформности новые точки пересечения сдвигаются внутрь области. Предложенный метод гарантирует построение сетки, однако она может содержать практически вырожденные элементы.
Улучшение сеток
На практике качество тетраэдральной сетки зависит от качества поверхностной сетки. Как правило, более 95% объема области заполняется сеткой с хорошим качеством с помощью алгоритма продвигаемого фронта. Оставшаяся часть разбивается методом на основе триангуляции Делоне и может иметь элементы с очень плохим качеством. В этом случае необходимо дальнейшее улучшение сетки, часто путем комбинации сдвижки узлов и топологических перестроений сеток [13, 14]. Для этого могут использоваться как простые эвристики, так и сложные методы оптимизации критериев качества [15, 16]. В пакете программ Ani3D имеется мощный инструмент для адаптации сеток – пакет AniMBA.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
91
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Заключение
В статье представлен краткий обзор методов, применяемых в библиотеке AniAFT, основным разработчиком которой является автор статьи. Рассмотрены как методы построения поверхностных треугольных сеток, так и алгоритмы для построения тетраэдральных сеток. Представлены некоторые примеры работы алгоритмов.
Работа выполнена при финансовой поддержке грантов РФФИ 08-01-00159-a, 0901-00115-а и программы Президиума РАН 21-П «Фундаментальные науки – медицине». Автор выражает благодарность Рао Гаримелле за помощь в разработке интерфейса с САПР, Кириллу Никитину за реализацию методов конструктивной блочной геометрии и Юрию Василевскому за поддержку, участие в обсуждениях и ценные советы.
Литература
1. Borouchaki H., Hecht F., Saltel E., George P.-L. Reasonably efficient Delaunay based mesh generator in 3 dimensions // Proc. of 4th IMR. – 1995. – P. 3–14.
2. Du Q., Wang D. Recent progress in robust and quality Delaunay mesh generation // J. of Comp. and App. Math. – 2006. – V. 195. – P. 8–23.
3. Shewchuk J. R. Constrained Delaunay tetrahedralizations and provably good boundary recovery // Proc. of 11th IMR. – 2002. – P. 193–204.
4. Ito Y., Shih A., Soni B. Reliable isotropic tetrahedral mesh generation based on an advancing front method // Proc. of 13th IMR. – 2004. – P. 95–106.
5. Yang Y., Yong J., Sun J. An algorithm for tetrahedral mesh generation based on conforming constrained Delaunay tetrahedralization // Computers & Graphics. – 2005. – V. 29. – P. 606–615.
6. George P.-L., Borouchaki H., Saltel E. 'Ultimate' robustness in meshing an arbitrary polyhedron // Int. J. Numer. Meth. Eng. – 2003. – V. 58. – P. 1061–1089.
7. 3D Generator of Anisotropic Meshes [Электронный ресурс]. – Режим доступа: http://sourceforge.net/projects/ani3d/, свободный. Язык английский.
8. 2D Generator of Anisotropic Meshes [Электронный ресурс]. – Режим доступа: http://sourceforge.net/projects/ani2d/, свободный.
9. Open CASCADE Technology, 3D modeling & numerical simulation [Электронный ресурс] – Режим доступа:: http://www.opencascade.org/, свободный.
10. The Common Geometry Module [Электронный ресурс]. – Режим доступа: http://cubit.sandia.gov/cgm.html, свободный.
11. Василевский Ю., Вершинин А., Данилов А., Пленкин А. Технология построения тетраэдральных сеток для областей, заданных в САПР // Матричные методы и технологии решения больших задач (под ред. Е.Е. Тыртышникова). – М: ИВМ РАН, 2005. – С. 21–32.
12. Никитин К. Технология построения поверхностных регулярных триангуляций для областей, составленных из примитивов: Дипломная работа. – М.: МГУ, 2007.
13. George P.-L., Borouchaki H. Delaunay triangulation and meshing. Application to finite elements. – Hermes, 1998.
14. Agouzal A., Lipnikov K., Vassilevski Yu. Adaptive generation of quasi-optimal tetrahedral meshes // East-West Journal. – 1999. – V. 7. – P. 223–244.
15. Ivanenko S. Variational methods for adaptive grid generation // Comp. Math. and Math. Physics. – 2003. – V. 42. – P. 830–844.
16. Garanzha V. Max-norm optimization of spatial mappings with application to grid genera-
tion, construction of surfaces and shape design // Proc. of Minisymp. in Int. Conf. OFEA. – 2001. – P. 61–74.
Данилов Александр Анатольевич
– Институт вычислительной математики РАН, аспирант, a.a.danilov@gmail.com
92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 519.63
СПОСОБЫ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ПОВЕРХНОСТНЫХ ТРИАНГУЛЯЦИЙ И ТЕТРАЭДРАЛЬНЫХ СЕТОК
А.А. Данилов
Представлен краткий обзор методов задания геометрии области и построения неструктурированных тетраэдральных сеток. Рассмотрены способы построения поверхностных треугольных сеток – аналитическое задание, взаимодействие с ядром САПР, перестроение имеющейся триангуляции, метод конструктивной блочной геометрии. Рассмотрена комбинация двух методов для построения тетраэдральной сетки внутри области. Представленный набор методов покрывает широкий спектр областей и позволяет строить сетки с заданными свойствами. Ключевые слова: тетраэдральные сетки, поверхностные триангуляции, САПР, конструктивная блочная геометрия, триангуляция Делоне, алгоритм продвигаемого фронта.
Введение
Одним из наиболее сложных этапов построения дискретной модели в компьютерном моделировании является построение расчетной сетки. Конформные треугольные и тетраэдральные неструктурированные сетки позволяют достаточно точно аппроксимировать сколь угодно сложную геометрию области. Треугольная сетка называется конформной, если любые два треугольника сетки имеют либо ровно одну общую вершину, либо ровно одно целое общее ребро, либо не имеют общих точек. В конформных тетраэдральных сетках любые две ячейки могут иметь также одну целую общую грань. Построение сетки состоит из двух этапов. Сначала строится поверхностная конформная триангуляция области. Затем внутри области строится тетраэдральная сетка, сохраняющая заданный след на границе области.
Существует два основных подхода к построению тетраэдральных сеток – методы, основанные на триангуляции Делоне, и алгоритм продвигаемого фронта. Использование триангуляции Делоне не гарантирует совпадение следа сетки на границе с заданной поверхностной триангуляцией. Для исправления сетки предлагают несколько методик: локальные перестроения сеток [1], измельчение сеток [2], накладывание ограничений на свойства триангуляции Делоне [3]. Метод продвигаемого фронта [4], напротив, сохраняет след сетки на границе области, однако может столкнуться с проблемами внутри области. Перспективным направлением видится комбинация методов Делоне и продвигаемого фронта [5].
В статье представлен краткий обзор некоторых методов построения поверхностных триангуляций, а также предложен метод построения тетраэдральной сетки внутри области на основе комбинации методов продвигаемого фронта и Делоне. В разделе 1 рассмотрены методы построения поверхностных сеток: аналитическое задание области, взаимодействие с ядром САПР, перестроение имеющихся сеток, метод конструктивной блочной геометрии. В разделе 2 кратко описан алгоритм классического продвигаемого фронта, а также метод на основе разбиения Делоне, который предложил Поль Луи Джордж [6]. В разделе 3 обсуждаются способы улучшения качества полученной сетки.
Все рассмотренные алгоритмы реализованы как библиотека программ AniAFT из пакета Ani3D [7]. Вместе с двумерной версией пакета программ Ani2D [8] оба пакета предоставляют инструменты для построения неструктурированных сеток, анизотропной адаптации сеток на основе заданной метрики, конечно-элементной дискретизации, решения систем линейных уравнений и другого. Эти пакеты свободно доступны для использования.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
87
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Способы задания поверхностной триангуляции
Обычно для построения поверхностной триангуляции всю границу области разбивают на части с общими криволинейными границами. После дискретизации криволинейных границ на поверхности может быть построена триангуляция в каждой части отдельно. Для построения триангуляции можно использовать классический двумерный алгоритм продвигаемого фронта. Так как все части поверхности имеют общую дискретизацию границ, то общая поверхностная сетка получится конформной.
В этом разделе будут рассмотрены следующие способы задания области: аналитическое задание области, взаимодействие с ядром САПР, перестроение начальной поверхностной триангуляции, методы конструктивной блочной геометрии.
С помощью аналитического задания области удобнее всего задавать простые объекты: шар, куб, цилиндр, а также многогранники с плоскими гранями. Более сложные объекты, полученные с помощью пересечения или объединения нескольких простых объектов, удобно задавать с помощью конструктивной блочной геометрии. Еще более сложные объекты, разработанные в САПР, могут быть обработаны с помощью взаимодействия с ядром САПР. Также объект может быть задан в виде поверхностной триангуляции, например, экспортирован из сторонней САПР или получен в результате трехмерного сканирования. В этих случаях может потребоваться дополнительная обработка сетки для улучшения ее качества.
Аналитическое задание области. Этот способ позволяет описывать граничную поверхность области с помощью параметризующих функций. Вся поверхность разбивается на части, каждая из которых может быть параметризована некоторой гладкой функцией. Линии пересечения частей также должны быть явно параметризованы. Этот метод задания границы удобен лишь в очень простых случаях, а также для задания объектов с плоскими гранями.
Информация об области задается как набор параметризованных гладких поверхностей с кусочно-гладкими параметризованными границами. Процесс построения начального фронта сводится к двум основным шагам. Сначала для каждой гладкой линии строится дискретизация с учетом желаемого размера элементов в сетке. Затем для каждой гладкой части поверхности формируется начальный фронт из имеющихся разбиений граничных кривых, и с помощью алгоритма продвигаемого фронта строится поверхностная триангуляция. После построения триангуляция разглаживается с учетом параметризующих функций и функции, задающей желаемый размер элементов сетки в пространстве.
Взаимодействие с САПР. Часто объекты моделируются с помощью САПР. Большинство из существующих САПР предлагают интерфейс для взаимодействия с внутренним ядром и получения информации о топологии и геометрии области. Одним из примеров такой САПР может служить открытая система Open CASCADE Technology [9]. У каждой системы САПР свой интерфейс для взаимодействия, и общих стандартов в этой области пока нет. В качестве универсального интерфейса можно использовать пакет Common Geometry Module (CGM) [10]. Этот пакет также имеет открытый код и свободен для использования. CGM предоставляет общий интерфейс к разным системам САПР (OpenCASCADE, ACIS и Pro/ENGINEER).
Создание интерфейса между генератором сеток и САПР с помощью пакета CGM является сугубо технической задачей. На рис. 1 показаны пример области, заданной в САПР OpenCASCADE, полученная поверхностная триангуляция и разрез построенной тетраэдральной сетки.
88 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Данилов
Рис. 1. Пример взаимодействия с САПР (26 248 треугольников, 72 158 тетраэдров)
Перестроение поверхностной сетки. В некоторых случаях область уже может быть задана своей поверхностной триангуляцией. Однако сетки, полученные экспортом из САПР, часто обладают тем свойством, что количество треугольников на плоских участках минимально, а сами треугольники могут иметь разный размер и очень вытянутую форму. В этом случае построение тетраэдральной сетки внутри области с сохранением заданного следа на поверхности может быть сильно затруднено или приведет к сетке с очень плохим качеством.
Для перестроения имеющейся сетки может быть использован метод, основанный на выделении почти плоских участков [11]. Пользователь задает параметры, определяющие допустимую степень отклонения выделяемых участков от плоскостей. Например, это может быть максимальный угол между нормалью треугольника и нормалью к плоскости. Очередной участок выбирается, начиная с треугольника с наибольшей площадью. Далее к нему по очереди добавляются соседние треугольники, если они не нарушают заданных пользователем критериев. После разбиения всей поверхности на почти плоские участки создается новая дискретизация границ этих участков (ломаных линий на поверхности). Далее для каждого участка его граничная дискретизация проектируется на плоскость, в плоскости строится новая триангуляция и проектируется обратно на поверхность. Так как участок поверхности является почти плоским, то искажения геометрии области будут незначительными.
а)
б)
Рис. 2. Два примера перестроения поверхностных сеток: а – экспорт из САПР, в начальной сетке 912 треугольников, в новой – 4 506 треугольников, 21 671 тетраэдр;
б – трехмерное сканирование модели, в начальной сетке 345 944 треугольников, в новой – 94 100 треугольников, 217 011 тетраэдров
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
89
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Тот же метод может быть применен и для разгрубления слишком подробной поверхностной сетки. Например, полученные с помощью трехмерного сканирования сетки обычно содержат очень много треугольников, и часто пользователю не нужна такая подробная поверхностная сетка. За счет разбиения на почти плоские участки и построения более грубой сетки на них можно получить новую поверхностную сетку с меньшим количеством треугольников.
На рис. 2 показаны два примера перестроения сеток. В первом начальная сетка была получена с помощью экспорта из САПР, а во втором – с помощью трехмерного сканирования.
Конструктивная блочная геометрия. Некоторые объекты довольно сложно задать с помощью аналитического представления, и в то же время они достаточно просты, чтобы моделировать их в сложных САПР. Важными примерами таких объектов являются пересечения и объединения простых объектов (примитивов), таких как шар, куб, цилиндр. Такой способ задания объектов принято называть конструктивной блочной геометрией [12].
Для простых примитивов поверхностная сетка строится с помощью аналитического задания области. Далее поверхностные сетки двух примитивов пересекаются, и на их основе строится новая поверхностная сетка для объединения, пересечения или разности двух примитивов. Новый объект, в свою очередь, тоже можно рассматривать как новый примитив. Общая идея пересечения поверхностных сеток состоит в следующем. Сначала строится ломаная линия пересечения поверхностных сеток, разбивающая треугольники в сетках на несколько связных частей. Далее полоску треугольников вдоль линии пересечения перестраивают заново для конформного соединения нужных частей поверхности. На рис. 3 показаны примеры поверхностных сеток для разных объектов.
Рис. 3. Примеры сеток для областей, заданных с помощью конструктивной блочной геометрии
Тетраэдральный генератор сеток. После того, как поверхностная сетка построена, можно приступать к построению тетраэдральной сетки внутри области. В этой статье предлагается комбинация двух методов. Первый метод – классический алгоритм продвигаемого фронта. Он срабатывает не всегда и может оставить после работы часть еще не разбитой на тетраэдры области. Для разбиения этих проблемных участков применяется второй метод, основанный на триангуляции Делоне.
Алгоритм продвигаемого фронта используется для построения тетраэдральной сетки внутри заданной ограниченной области. Область задается поверхностной ориентированной конформной триангуляцией, называемой фронтом. После этого шаг за шагом строятся тетраэдры на границе фронта с продвижением его внутрь области. В каждый момент времени текущий фронт отделяет часть с построенной тетраэдральной сеткой от еще не рассмотренной части. Если в конце фронт окажется пустым, то тетраэдральная сетка будет построена для всей области. Если во фронте остаются треугольники, но ни один новый тетраэдр построить не удается, то алгоритм останавливается, и применяется второй метод, описанный в следующем подразделе.
90 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Данилов
На каждом шаге из фронта выбирается треугольник с наибольшей площадью, и на нем как на основании строится тетраэдр с учетом желаемого размера элементов сетки. После этого тетраэдр проверяется на пересечения с фронтом. В случае пересечений подбирается другой тетраэдр. Новый тетраэдр добавляется в сетку, а фронт продвигается внутрь области.
Метод позволяет строить сетки в сложных геометрических областях, в том числе анизотропных и имеющих разрезы (рис. 4). Также метод позволяет контролировать желаемый размер элементов сетки и может выбирать его автоматически (рис. 5).
Рис. 4. Пример анизотропной области. Слева область растянута по оси Z в 50 раз. В центре и справа показаны разрезы тетраэдральной сетки плоскостями OXZ и OXY
Рис. 5. Квазиравномерный, пользовательский и автоматический выбор шага сетки
Метод на основе разбиения Делоне применяется после алгоритма продвигаемого фронта, когда бóльшая часть сетки уже построена. Здесь представлена только общая идея метода, предложенного П. Л. Джорджем [6]. Сначала для выпуклой оболочки множества вершин фронта строится тетраэдральное разбиение Делоне. Далее нужный фронт пересекается с полученной сеткой, измельчая ее. После этого из сетки выкидываются тетраэдры, лежащие за пределами области. Новая сетка не будет совпадать с заданным фронтом на границе. Для восстановления конформности новые точки пересечения сдвигаются внутрь области. Предложенный метод гарантирует построение сетки, однако она может содержать практически вырожденные элементы.
Улучшение сеток
На практике качество тетраэдральной сетки зависит от качества поверхностной сетки. Как правило, более 95% объема области заполняется сеткой с хорошим качеством с помощью алгоритма продвигаемого фронта. Оставшаяся часть разбивается методом на основе триангуляции Делоне и может иметь элементы с очень плохим качеством. В этом случае необходимо дальнейшее улучшение сетки, часто путем комбинации сдвижки узлов и топологических перестроений сеток [13, 14]. Для этого могут использоваться как простые эвристики, так и сложные методы оптимизации критериев качества [15, 16]. В пакете программ Ani3D имеется мощный инструмент для адаптации сеток – пакет AniMBA.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
91
ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК
Заключение
В статье представлен краткий обзор методов, применяемых в библиотеке AniAFT, основным разработчиком которой является автор статьи. Рассмотрены как методы построения поверхностных треугольных сеток, так и алгоритмы для построения тетраэдральных сеток. Представлены некоторые примеры работы алгоритмов.
Работа выполнена при финансовой поддержке грантов РФФИ 08-01-00159-a, 0901-00115-а и программы Президиума РАН 21-П «Фундаментальные науки – медицине». Автор выражает благодарность Рао Гаримелле за помощь в разработке интерфейса с САПР, Кириллу Никитину за реализацию методов конструктивной блочной геометрии и Юрию Василевскому за поддержку, участие в обсуждениях и ценные советы.
Литература
1. Borouchaki H., Hecht F., Saltel E., George P.-L. Reasonably efficient Delaunay based mesh generator in 3 dimensions // Proc. of 4th IMR. – 1995. – P. 3–14.
2. Du Q., Wang D. Recent progress in robust and quality Delaunay mesh generation // J. of Comp. and App. Math. – 2006. – V. 195. – P. 8–23.
3. Shewchuk J. R. Constrained Delaunay tetrahedralizations and provably good boundary recovery // Proc. of 11th IMR. – 2002. – P. 193–204.
4. Ito Y., Shih A., Soni B. Reliable isotropic tetrahedral mesh generation based on an advancing front method // Proc. of 13th IMR. – 2004. – P. 95–106.
5. Yang Y., Yong J., Sun J. An algorithm for tetrahedral mesh generation based on conforming constrained Delaunay tetrahedralization // Computers & Graphics. – 2005. – V. 29. – P. 606–615.
6. George P.-L., Borouchaki H., Saltel E. 'Ultimate' robustness in meshing an arbitrary polyhedron // Int. J. Numer. Meth. Eng. – 2003. – V. 58. – P. 1061–1089.
7. 3D Generator of Anisotropic Meshes [Электронный ресурс]. – Режим доступа: http://sourceforge.net/projects/ani3d/, свободный. Язык английский.
8. 2D Generator of Anisotropic Meshes [Электронный ресурс]. – Режим доступа: http://sourceforge.net/projects/ani2d/, свободный.
9. Open CASCADE Technology, 3D modeling & numerical simulation [Электронный ресурс] – Режим доступа:: http://www.opencascade.org/, свободный.
10. The Common Geometry Module [Электронный ресурс]. – Режим доступа: http://cubit.sandia.gov/cgm.html, свободный.
11. Василевский Ю., Вершинин А., Данилов А., Пленкин А. Технология построения тетраэдральных сеток для областей, заданных в САПР // Матричные методы и технологии решения больших задач (под ред. Е.Е. Тыртышникова). – М: ИВМ РАН, 2005. – С. 21–32.
12. Никитин К. Технология построения поверхностных регулярных триангуляций для областей, составленных из примитивов: Дипломная работа. – М.: МГУ, 2007.
13. George P.-L., Borouchaki H. Delaunay triangulation and meshing. Application to finite elements. – Hermes, 1998.
14. Agouzal A., Lipnikov K., Vassilevski Yu. Adaptive generation of quasi-optimal tetrahedral meshes // East-West Journal. – 1999. – V. 7. – P. 223–244.
15. Ivanenko S. Variational methods for adaptive grid generation // Comp. Math. and Math. Physics. – 2003. – V. 42. – P. 830–844.
16. Garanzha V. Max-norm optimization of spatial mappings with application to grid genera-
tion, construction of surfaces and shape design // Proc. of Minisymp. in Int. Conf. OFEA. – 2001. – P. 61–74.
Данилов Александр Анатольевич
– Институт вычислительной математики РАН, аспирант, a.a.danilov@gmail.com
92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)